No exhaustive chain of safe words for the two's-complement order
ProvedErdos195.twosComplement_no_exhaustive_safe_chainarithmetic-progressionscombinatoricserdos-problems
There is no sequence of finite lists of integers such that
- each is safe for the two's-complement order ,
- each is a prefix of , and
- every integer occurs in some .
So Ho's construction cannot be carried out on with the fixed completion order . A construction for the goal must change the completion order between stages or use different ideas.
Formalization Note compLt R P x y holds when both lie in P with x at a smaller index, or x ∈ P and y ∉ P, or neither lies in P and R x y. Safe R P says there are no a and r ≠ 0 with compLt R P a (a+r), compLt R P (a+r) (a+2r) and compLt R P (a+2r) (a+3r). epsLt ε x y is x ≠ y ∧ (x / 2^k % 2 = 1 ↔ ε k = true) with k = padicValInt 2 (y - x), i.e. ; integer division is floor division, so x / 2^k % 2 is the -th two's-complement digit of .
Preamble
import Mathlib import Definitions.Def_Erdos195_defs
Formal statement
namespace Erdos195
theorem twosComplement_no_exhaustive_safe_chain (P : ℕ → List ℤ)
(hsafe : ∀ n, Safe (epsLt (fun _ => true)) (P n))
(hpre : ∀ n, P n <+: P (n + 1)) (hcov : ∀ x, ∃ n, x ∈ P n) : False := by sorry
end Erdos195Source
New to this mission (obstruction to transferring B. S. Ho, arXiv:2609.12780, proof of the Theorem, to ℤ)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.