Erdős·erdos:197
Erdős Problem 197
No independent check recorded yet. A formal artifact, declaration or published object is attached, but no rebuild of it is recorded here.
Fidelity F2: The correspondence is declared through an alignment table and written divergences.
arithmetic progressions·Source
AI activity
How grades workNo AI contribution recorded against this statement.
Fidelity
How fidelity is gradedF2 declared. The correspondence is declared through an alignment table and written divergences.
Declared by the projects
5As each project's formalization.yaml states it.
No two-set solution of Erdős #197 with eventual lag ratio below 2 (partial result)
- authors
- Alex Lopez
- method
- agent — Claude Opus 5.5 (claude-opus-5-5)
- review
- self-assessed (none)
- sorry
- 0 unproved goals declared
- sources
- Theorem A: no two-set solution of Erdős #197 with eventual lag ratio below 2 (docs/proof.md in this repository) — other; Erdős Problem #197 — background; On permutations containing no long arithmetic progressions — background; Structural rigidity in the Erdős–Graham two-set permutation problem — background
- related
- google-deepmind/formal-conjectures/blob/5d8b04d3d41b745cc3f2f3cdd5ed04b60c500983/FormalConjectures/ErdosProblems/197.lean — other
- divergences
- The write-up states the problem for ℕ = {1, 2, …}; the Lean statement uses Lean's ℕ = {0, 1, 2, …}, as formal-conjectures does. The proof is unchanged, and the two versions imply each other by the shift x ↦ x ± 1, which preserves 3-term progressions and changes lag ratios by an amount tending to 0. No other divergences known.
- checked by
- nobody independent of its authors yet
The anchored gadget [M, 2M+6] is infeasible: Erdős #197 (partial result)
- authors
- Alex Lopez
- method
- agent — Claude Fable 5.1, Claude Opus 5.5 (claude-opus-5-5)
- review
- self-assessed (none)
- sorry
- 0 unproved goals declared
- sources
- Theorem I and Corollary I: the anchored gadget [M, 2M+6] is infeasible (docs/proof.md in this repository) — other; Erdős Problem #197 — background; On permutations containing no long arithmetic progressions — background; Structural rigidity in the Erdős–Graham two-set permutation problem — background
- related
- google-deepmind/formal-conjectures/blob/5d8b04d3d41b745cc3f2f3cdd5ed04b60c500983/FormalConjectures/ErdosProblems/197.lean — other; the-omega-institute/trureturing/pull/9626 — other; Alex-lop/erdos-197-bounded-lag — other
- divergences
- The write-up speaks of linear orders of [M, 2M + 6]; the Lean statement encodes a linear order by an injective ranking σ : ℕ → ℕ (x comes before y iff σ x < σ y), which is equivalent for a finite set. The write-up's ℕ and Lean's ℕ = {0, 1, 2, …} (as in formal-conjectures) give the same statements, and the proof does not use positivity. In Corollary I, 2 * P + 6 - v is truncated subtraction, equal to 2P − v + 6 for every P ≥ v. No other divergences known.
- checked by
- nobody independent of its authors yet
Rotation codings are not permutable: Erdős #197 (partial result)
- authors
- Alex Lopez
- method
- agent — Claude Fable 5.2, Claude Opus 5.5 (claude-opus-5-5)
- review
- self-assessed (none)
- sorry
- 0 unproved goals declared
- sources
- Theorem K, d = 1: rotation codings are not permutable (docs/proof.md in this repository) — other; Erdős Problem #197 — background; On permutations containing no long arithmetic progressions — background; Structural rigidity in the Erdős–Graham two-set permutation problem — background
- related
- Alex-lop/erdos-197-rho-partition — builds-on; google-deepmind/formal-conjectures/blob/5d8b04d3d41b745cc3f2f3cdd5ed04b60c500983/FormalConjectures/ErdosProblems/197.lean — other
- divergences
- fract is Int.fract (r − ⌊r⌋ ∈ [0, 1)), n * α casts n : ℕ to ℝ, the window (a, b) is Set.Ioo a b with 0 ≤ a < b ≤ 1 (an interval that does not wrap around 0), and Irrational is Mathlib's. An enumeration is f : ℕ ≃ A with formal-conjectures' ¬HasMonotoneAP (Subtype.val ∘ f) 3 unfolded; the bound AP start is named x instead of a. ℕ is Lean's {0, 1, 2, …}, as in formal-conjectures. The working note's Theorem K is stated for open windows U ⊆ 𝕋^d and d ≥ 1; only d = 1 with an interval window is formalized.
- checked by
- nobody independent of its authors yet
The Quarter Lemma, and the exact ρ-partitions are not permutable: Erdős #197 (partial result)
- authors
- Alex Lopez
- method
- agent — Claude Fable 5.1, Claude Opus 5.5 (claude-opus-5-5)
- review
- self-assessed (none)
- sorry
- 0 unproved goals declared
- sources
- Quarter Lemma, Theorem L* and Theorem 7.2: the exact ρ-partitions are not permutable (docs/proof.md in this repository) — other; Erdős Problem #197 — background; On permutations containing no long arithmetic progressions — background; Enumerating permutations that avoid three term arithmetic progressions — background
- related
- Alex-lop/erdos-197-interval-gadget — builds-on; Alex-lop/erdos-197-tower-obstruction — other; google-deepmind/formal-conjectures/blob/5d8b04d3d41b745cc3f2f3cdd5ed04b60c500983/FormalConjectures/ErdosProblems/197.lean — other; Alex-lop/erdos-197-bounded-lag — other
- divergences
- The write-up speaks of linear orders; in the Quarter Lemma the order of [α, β] is an injective ranking σ : ℕ → ℕ (x comes before y iff σ x < σ y), which is equivalent for a finite set, and the leading parity π and leading quarter Q are parameters characterised by the hypotheses hπ and hQ (their existence is the zigzag lemma, proved as Erdos197Rho.phases, which is not a statement of Challenge.lean). In Theorem 7.2 an enumeration is f : ℕ ≃ C with formal-conjectures' ¬HasMonotoneAP (Subtype.val ∘ f) 3 unfolded; log₂ is Real.logb 2, the floor is Int.floor and % 2 is Int.emod, so ⌊…⌋ % 2 ∈ {0, 1} also for negative floors, and the classes are restricted to n ≥ 1 (Lean's Real.logb 2 0 = 0). The write-up's run boundaries r_j = ⌈2^(φ + j/(2k + 1))⌉ are proved equivalent to the floor definition inside Lean (Erdos197Rho.rho_runs, for natural indices j). ℕ is Lean's {0, 1, 2, …}, as in formal-conjectures; β − 4 is truncated subtraction, the true value since β ≥ 8. No other divergences known.
- checked by
- nobody independent of its authors yet
A tower obstruction for Erdős #197: drifting near-dyadic run colourings fail (partial result)
- authors
- Alex Lopez
- method
- agent — Claude Fable 5.1, Claude Opus 5.5 (claude-opus-5-5)
- review
- self-assessed (none)
- sorry
- 0 unproved goals declared
- sources
- Theorem R*, Lemma S and Corollaries R0*, R2*: a tower obstruction for permutable sets (docs/proof.md in this repository) — other; Erdős Problem #197 — background; On permutations containing no long arithmetic progressions — background; Structural rigidity in the Erdős–Graham two-set permutation problem — background
- related
- Alex-lop/erdos-197-interval-gadget — builds-on; google-deepmind/formal-conjectures/blob/5d8b04d3d41b745cc3f2f3cdd5ed04b60c500983/FormalConjectures/ErdosProblems/197.lean — other; the-omega-institute/trureturing/pull/9626 — other; Alex-lop/erdos-197-bounded-lag — other
- divergences
- The write-up speaks of linear orders of S of type ω; the Lean statements speak of an enumeration f : ℕ ≃ S without monotone 3-term APs (formal-conjectures' predicate, unfolded), which is the same notion for infinite S, and the proof uses the positions f.symm as an injective ranking. Lemmas W* and S are stated in the write-up for orders of any type; in Lean (witness, step) the order is an injective ranking ρ : ℕ → ℕ on S, i.e. an order that embeds in ω. The refereed text states Lemmas W*, S, Theorem R* and Corollary R0* for S ⊆ ℤ; docs/proof.md and the Lean statements are over Lean's ℕ = {0, 1, 2, …}, as in formal-conjectures (the ℤ forms of R* and R0* follow by restricting to the tower and translating it into ℕ; not proved in Lean). Hypotheses with a deficit 2α − β are written without subtraction (2α_1 + 16d ≤ u + β_1, 2α_{k+1} + 16·4^k·d ≤ α_k + β_{k+1}, 4a_{j+1} ≤ a_j + 2b_{j+1}), which is equivalent over the integers. In Corollary R2* the ratio is the real number (r (k + 1) : ℝ) / r k and the colour classes are {n | ∃ k, k % 2 = c ∧ r k ≤ n ∧ n < r (k + 1)} for c < 2. No other divergences known.
- checked by
- nobody independent of its authors yet
Follow and discuss
All discussionFollow this problem
An email when it has a new claim, check, bounty or discussion. You confirm once and can stop with one click.
Discussion and bounties for this problem load here.
Seen recently
What the monitors picked up in the last thirty days, not yet graded.
Something wrong or missing here? Request a correction or add a claim, with its sources.
Claims and corrections from readers
All of themFormal material
Formal statements · 1
Cited proofs · 0
No proof artifact cited by the formal record.
Also known as · 3
- https://www.erdosproblems.com/197
- https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/ErdosProblems/197.lean
- FormalConjectures/ErdosProblems/197.lean
Cite this record
qed.bot, “Erdős Problem 197”, https://qed.bot/s/erdos-197, as of 20 Nov 2026.