qedbot

Erdős·erdos:197

Erdős Problem 197

conjecture formal record: open source: open F2 declared

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 work

No AI contribution recorded against this statement.

F2 declared. The correspondence is declared through an alignment table and written divergences.

declares divergences from its source reviewed by its authors only

Declared by the projects

5

As each project's formalization.yaml states it.

No two-set solution of Erdős #197 with eventual lag ratio below 2 (partial result)Alex-lop/erdos-197-bounded-lag · joined by anchor · no independent check

Read formalization.yaml

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
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)Alex-lop/erdos-197-interval-gadget · joined by anchor · no independent check

Read formalization.yaml

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
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)Alex-lop/erdos-197-kronecker · joined by anchor · no independent check

Read formalization.yaml

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
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)Alex-lop/erdos-197-rho-partition · joined by anchor · no independent check

Read formalization.yaml

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
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)Alex-lop/erdos-197-tower-obstruction · joined by anchor · no independent check

Read formalization.yaml

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
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 discussion

Discussion and bounties for this problem load here.

Something wrong or missing here? Request a correction or add a claim, with its sources.

Formal 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.

This record as plain text, with each claim, its grades and its sources.