Failure of the second backward step is located by level
ProvedErdos195.second_step_failure_levelsA tree witness defines a strict total order on : for with , iff the -th binary digit of is exactly when . 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); is tree-safe if it is -safe for some . For an in-order pair of ( before ) call its third term and its fourth term. An open path in is a family of in-order pairs , , , with for and no third term in . Its sink fourth term is a true-sink fourth term of if and every in-order pair of with has (condition C1 for appending ).
Theorem. Let be a finite word, , , , , , and let be -safe. Assume passes C1 in (every in-order pair of with has ). If is not tree-safe for any witness, then there exist with fully open in () and a fully open in-order pair of (third and fourth terms not in , neither equal to ) at the same level and node with opposite digits of and at level ; moreover exactly one of:
- (high) and ;
- (level ) , , and the -th digits of and agree (the blocker has the orientation of );
- (low) and is already released at in : or .
The low case uses that agree modulo , so below level the pair of would sit at the same node with the orientation of and conflict with unless released. This covers blockers among old pairs of as well as new pairs , extending milestone #161 (new pairs only, level ) towards a full criterion for the second step of #158–#159.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem second_step_failure_levels (θ : ℕ → ℤ → Bool) (T : List ℤ) (a b : ℤ) (hab : a ≠ b)
(hb : b ∈ T) (hwT : 3 * b - 2 * a ∉ T) (htT : 2 * b - a ∉ T)
(hS : Safe (treeLt θ) (T ++ [3 * b - 2 * a]))
(hC1 : ∀ x y : ℤ, x ∈ T ++ [3 * b - 2 * a] → y ∈ T ++ [3 * b - 2 * a] →
(T ++ [3 * b - 2 * a]).idxOf x < (T ++ [3 * b - 2 * a]).idxOf y →
2 * b - a = 2 * y - x → 3 * y - 2 * x ∈ T ++ [3 * b - 2 * a])
(hbad : ¬ ∃ θ' : ℕ → ℤ → Bool, Safe (treeLt θ') (T ++ [3 * b - 2 * a] ++ [2 * b - a])) :
∃ x a' b' : ℤ, x ∈ T ∧ 2 * (2 * b - a) - x ∉ T ++ [3 * b - 2 * a] ∧
3 * (2 * b - a) - 2 * x ∉ T ++ [3 * b - 2 * a] ∧
a' ∈ T ++ [3 * b - 2 * a] ∧ b' ∈ T ++ [3 * b - 2 * a] ∧
(T ++ [3 * b - 2 * a]).idxOf a' < (T ++ [3 * b - 2 * a]).idxOf b' ∧
2 * b' - a' ∉ T ++ [3 * b - 2 * a] ∧ 3 * b' - 2 * a' ∉ T ++ [3 * b - 2 * a] ∧
2 * b - a ≠ 2 * b' - a' ∧ 2 * b - a ≠ 3 * b' - 2 * a' ∧
padicValInt 2 (b' - a') = padicValInt 2 ((2 * b - a) - x) ∧
a' % 2 ^ padicValInt 2 (b' - a') = x % 2 ^ padicValInt 2 (b' - a') ∧
¬ (bitOne b' (padicValInt 2 (b' - a')) ↔ bitOne (2 * b - a) (padicValInt 2 (b' - a'))) ∧
((padicValInt 2 (b - a) < padicValInt 2 (b' - a') ∧
x % 2 ^ (padicValInt 2 (b - a) + 1) = a % 2 ^ (padicValInt 2 (b - a) + 1)) ∨
(padicValInt 2 (b' - a') = padicValInt 2 (b - a) ∧
x % 2 ^ (padicValInt 2 (b - a) + 1) = b % 2 ^ (padicValInt 2 (b - a) + 1) ∧
(bitOne b' (padicValInt 2 (b - a)) ↔ bitOne b (padicValInt 2 (b - a)))) ∨
(padicValInt 2 (b' - a') < padicValInt 2 (b - a) ∧
(2 * (3 * b - 2 * a) - x ∈ T ∨ 3 * (3 * b - 2 * a) - 2 * x ∈ T))) := by sorry
end Erdos195