Erdős (Erdos) Problem #782: status in 2026

Erdős Problem #782

Do the squares contain arbitrarily long quasi-progressions? That is, does there exist some constant C>0 such that, for any k, the squares contain a sequence x_1,…,x_k where, for some d and all 1≤ i<k, x_i+d≤ x_i+1≤ x_i+d+C. A question of Brown, Erdős, and Freedman [BEF90].

Status (as of 2026-11-11): Open according to erdosproblems.com (status last updated 2025-08-31).

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim.

Try it with your chatbot Submit a claim Follow (RSS)

Cite

@misc{cairn-erdos-782,
  title        = {Erdős Problem #782},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/erdos-782}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Ferdos-782.json)](https://cairn-commons.com/problems/erdos-782)

Claims

Verified

Disputed

Refuted

On the literature board

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.

Get a task — one click

Your chatbot works on it — 5–10 minutes, in its own tab

Paste its answer here — check it and publish it under your name

What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.

The problem

The question

erdos_782.parts.i. Do the squares contain arbitrarily long quasi-progressions? That is, does there exist some constant $C > 0$ such that, for any $k$ , the squares contain a sequence $x_{1}, \dots, x_{k}$ where, for some $d$ and all $1 \leq i < k$ , $x_{i} + d \leq x_{i + 1} \leq x_{i} + d + C .$

A question of Brown, Erdős, and Freedman [BEF90]. This is the first question. Here $C$ and $d$ are positive integers; $d \geq 1$ excludes constant sequences.

erdos_782.parts.ii. Do the squares contain arbitrarily large cubes $a + {i \sum ϵ_{i} b_{i} : ϵ_{i} \in {0, 1}} ?$

A question of Brown, Erdős, and Freedman [BEF90]. This is the second question. The generators $b_{i}$ are nonzero integers, as in [BEU26]. Solymosi [So07] conjectured that the answer is no, and Cilleruelo and Granville [CiGr07] observed that the answer is no conditional on the Bombieri-Lang conjecture.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.ErdosProblems.«782» (2 statements).

theorem erdos_782.parts.i :
    ∃ C : ℕ, 0 < C ∧ ∀ k : ℕ, ContainsQuasiProgression {n : ℕ | IsSquare n} C k

theorem erdos_782.parts.ii :
    ∀ d : ℕ, ∃ (a : ℤ) (b : Fin d → ℤ),
      (∀ i, b i ≠ 0) ∧ hilbertCube a b ⊆ {n : ℤ | IsSquare n}

What counts as progress

A Lean proof of one of the statements above, pinned as the claim's formal statement.
Partial results: special cases, weaker bounds, reductions — as verified claims.
Computations and numerical evidence with published code (reproducible).
Literature: the problem may have been solved or partly solved already — check erdosproblems.com/782. Report it as a literature claim.
A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

erdosproblems.com/782
[BEF90] Brown, T. C. and Erdős, P. and Freedman, A. R., _Quasi-progressions and descending waves_. J. Combin. Theory Ser. A 53 (1990), 81-95.
[BFS03] Brown, T. C., Freedman, A. R. and Shiue, P. J.-S., _Progressions of squares_. Australas. J. Combin. 27 (2003), 187-192.
[BEU26] Bremner, A., Elsholtz, C. and Ulas, M., _There are infinitely many Hilbert cubes of dimension 3 in the set of squares_. arXiv:2604.05459 (2026).
[CiGr07] Cilleruelo, J. and Granville, A., _Lattice points on circles, squares in arithmetic progressions and sumsets of squares_. Additive combinatorics (2007), 241-262.
[DiEl12] Dietmann, R. and Elsholtz, C., _Hilbert cubes in progression-free sets and in the set of squares II_. arXiv:1207.1461 (2012).
[So07] Solymosi, J., _Elementary additive combinatorics_. Additive combinatorics (2007), 29-38.

Source and licence

Imported from Formal Conjectures (Erdős problems), commit 2f91d251c07f. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.