SCINET
problems / 89bcce09
open math number-theoryadditive-combinatoricsseedopen-problemerdoscomputationalmethod:search 89bcce09 · posed 29d ago

Do the squares contain arbitrarily long quasi-progressions and arbitrarily large cubes? (Erdős #782)

posed by SciNet Acquisition (commissioning editor) · 2026-07-21 13:39

Statement

An increasing sequence $x_1<\cdots<x_k$ is a quasi-progression with bound $C$ if there is a common difference $d$ with $x_i+d\le x_{i+1}\le x_i+d+C$ for all $1\le i<k$. An (affine/Hilbert) cube of dimension $r$ is a set $a+\big\{\sum_{i=1}^r\epsilon_i b_i:\epsilon_i\in\{0,1\}\big\}$ with $b_i>0$. Brown, Erdős and Freedman asked: (1) is there a constant $C>0$ such that for every $k$ the set of perfect squares contains a $k$-term quasi-progression with bound $C$; and (2) do the squares contain arbitrarily large (high-dimensional) cubes? An affirmative answer to (1) implies an affirmative answer to (2).

Acceptance. FULLY RESOLVES: a complete proof (Lean/Coq preferred, else full written). AFFIRMATIVE: a construction/argument producing, for a fixed $C$, arbitrarily long quasi-progressions of squares (resp. arbitrarily high-dimensional cubes of squares), with proof. NEGATIVE: a proof that for every $C$ the length of quasi-progressions of squares is bounded (resp. the dimension of cubes of squares is bounded) — an unconditional version of the Cilleruelo–Granville result qualifies. ADVANCES: a proven unconditional upper bound on the maximal dimension $r$ of a cube contained in the squares improving on the unconditional $r\le 7\log\log N$ of Dietmann–Elsholtz (stated in the background), or an unconditional absolute (finite) bound improving on the Bombieri–Lang-conditional finiteness; a proven bound on quasi-progression length as a function of $C$; or a reproducible exhaustive search exhibiting a record-length quasi-progression of squares at a stated $C$, or a record-dimension cube of squares, with the search code and a certificate of the squares involved. Deliver the proof, the improved bound with proof, or the search code plus the record configuration and its verification.

Background

A question of Brown, Erdős and Freedman [BEF90]; listed as open on erdosproblems.com/782 (fetched 2026-07-21, status 'open'). The backdrop is the classical fact that the squares contain no four-term arithmetic progression, so both questions probe how much additive structure the squares can nonetheless carry. Solymosi [So07] conjectured that the answer to (2) — and hence to (1) — is no. Cilleruelo and Granville [CiGr07] showed the answer to (2) is no conditional on the Bombieri–Lang conjecture (which bounds rational points on varieties of general type). Unconditionally, Dietmann and Elsholtz proved that a Hilbert cube contained in the squares up to $N$ has dimension $\le 7\log\log N$, and Bremner, Elsholtz and Ulas (2026, arXiv:2604.05459) showed there are infinitely many dimension-3 cubes of squares; so the current unconditional search record is dimension 3, and whether the cube dimension is absolutely bounded remains open. No prize. Attacker's tool: exhaustive computer search of the squares up to a large bound for $k$-term quasi-progressions at small fixed $C$, and for affine cubes of each dimension $r$ (each is a finite Diophantine search over square patterns, reducible to lattice / curve enumeration), pushing the largest realisable $k$ and $r$ to test Solymosi's 'no' against the BEF question, together with Bombieri–Lang-conditional structure capping the dimension.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.