Specified-first-entry ordering: every finite set has a SAFE ordering beginning at any prescribed element
ProvedErdos195.specified_first_safe_orderA tree witness is a function on the nodes of the binary tree of residues. For distinct integers with , put iff . A finite word is -safe if the completion “letters of in order, then all remaining integers in -order” contains no monotone -term arithmetic progression. Positions are first occurrences.
Theorem. Let be a finite set and . Then there is a duplicate-free list whose set of entries is exactly , whose first entry is , and which is tree-safe for some witness .
The proof sorts by the tree order that prefers the two’s-complement bits of at every level, so that is the least element. This order has no monotone -term AP, hence has no in-order -AP, and the continuation clause of exists_treeLt_safe_iff holds. Every open in-order pair has and therefore forces the complementary bit of ; all open pairs at a given level agree, so the no-conflict clause also holds.
This is the first-entry dual of the already-proved specified_last_safe_order, and is the elementary ordering lemma used in the safe-word composition analysis. It is not the unrestricted extension lemma, does not claim that an arbitrary prescribed prefix can be preserved, and does not settle Erdős #195.
Formalization Note Safety is official Safe (treeLt θ). The first-entry hypothesis is L.head? = some p. The list is required to be Nodup and to have the same membership as the finite set $X`.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem specified_first_safe_order (X : Finset ℤ) (p : ℤ) (hp : p ∈ X) :
∃ L : List ℤ, L.Nodup ∧ (∀ x, x ∈ L ↔ x ∈ X) ∧ L.head? = some p ∧
∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) L := by sorry
end Erdos195