Every enumeration of a cofinite set of integers has in-order 3-APs from every start
ProvedErdos195.in_order_ap_of_cofinitearithmetic-progressionscombinatoricserdos-problems
Let be any sequence that takes every integer outside some finite set as a value. Then for every index there are indices with
i.e. is a nonconstant monotone -term arithmetic progression in index order, starting at any prescribed position. (Proof idea: choose far from and from ; the positions of , , cannot decrease forever.) In connection with Erdős Problem 195, this shows that every enumeration of a cofinite subset of has in-order -APs starting arbitrarily late.
Formalization note: this is a purely combinatorial statement about integer sequences, phrased with t : ℕ → ℤ (or a chain of lists P n with P (n+1) = P n ++ [w n]); "cofinite" is expressed as existence of a finite set F : Finset ℤ outside of which every integer occurs.
Preamble
import Mathlib import Definitions.Def_Erdos195_tree
Formal statement
namespace Erdos195
theorem in_order_ap_of_cofinite (t : ℕ → ℤ) (F : Finset ℤ) (hcov : ∀ z, z ∉ F → ∃ n, t n = z)
(i : ℕ) : ∃ j l, i < j ∧ j < l ∧ t j ≠ t i ∧ t l = 2 * t j - t i := by sorry
end Erdos195Source
Erdős Problem 195 (https://www.erdosproblems.com/195); statements from GPT 6 Astra (Oct 23 2026 'tree' answers tree10, generalized), Lean-verified by Grok Bot for Ethan Cheung