Two inverted pairs sharing an odd letter: no-escape repairs force translates of the odd part
ProvedErdos195.two_inversion_translateA tree witness defines a strict total order on (milestone framework); its root bit decides the order between integers of different parity. A finite word of integers is -safe if the sequence "letters of in order, then all remaining integers in -order" has no monotone 4-term arithmetic progression; positions are first occurrences. Theorem (two inverted pairs sharing the odd letter). Let . Let be a word, odd, and even letters of , both after , such that , , , all lie outside . Let be -safe. Suppose that no odd before (resp. ) in has (resp. ). Then . Moreover, if is the earlier and the later of and , then
and some odd letter of lies strictly between and .
The first step is w-forcing: with root bit 1, an odd before an even with forces into every safe end-extension. Consequently, a repair of a word with two inversions that avoids escape letters must contain a translate of the whole odd part of by , and these translates come before the later forced letter. So the two-inversion problem does not factor into two independent single-inversion repairs (cf. the single-inversion criterion). It is a structural necessary condition, not a construction or an impossibility result for Erdős #195.
Formalization note: words are List ℤ, positions via List.idxOf, safety is Safe (treeLt θ).
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem two_inversion_translate (θ : ℕ → ℤ → Bool) (h00 : θ 0 0 = true) (T R : List ℤ)
(hS : Safe (treeLt θ) (T ++ R)) (b c c' : ℤ) (hb : b ∈ T) (hc : c ∈ T) (hc' : c' ∈ T)
(hbo : b % 2 = 1) (hce : c % 2 = 0) (hce' : c' % 2 = 0) (hcc : c ≠ c')
(hi : T.idxOf b < T.idxOf c) (hi' : T.idxOf b < T.idxOf c')
(ht : 2 * c - b ∉ T) (hw : 3 * c - 2 * b ∉ T) (ht' : 2 * c' - b ∉ T) (hw' : 3 * c' - 2 * b ∉ T)
(hesc : ∀ o ∈ T ++ R, o % 2 = 1 →
((T ++ R).idxOf o < (T ++ R).idxOf (3 * c - 2 * b) → 3 * (3 * c - 2 * b) - 2 * o ∉ T ++ R) ∧
((T ++ R).idxOf o < (T ++ R).idxOf (3 * c' - 2 * b) → 3 * (3 * c' - 2 * b) - 2 * o ∉ T ++ R)) :
3 * c - 2 * b ∈ R ∧ 3 * c' - 2 * b ∈ R ∧
∃ u u' : ℤ, ((u = 3 * c - 2 * b ∧ u' = 3 * c' - 2 * b) ∨ (u = 3 * c' - 2 * b ∧ u' = 3 * c - 2 * b)) ∧
(T ++ R).idxOf u < (T ++ R).idxOf u' ∧
(∀ o ∈ T, o % 2 = 1 → o + 2 * (u' - u) ∈ T ++ R ∧
(T ++ R).idxOf (o + 2 * (u' - u)) < (T ++ R).idxOf u') ∧
∃ o ∈ R, o % 2 = 1 ∧ (T ++ R).idxOf u < (T ++ R).idxOf o ∧ (T ++ R).idxOf o < (T ++ R).idxOf u' := by sorry
end Erdos195