Erdős problem #782 — wave 7l report
Date: 2026-07-27 (UTC)
Result at a glance
The live problem remains open. I found an explicit five-term quasi-progression
\[ 1^2,\;3^2,\;4^2,\;5^2,\;6^2 =1,9,16,25,36 \]whose consecutive gaps are \(8,7,9,11\), of diameter \(11-7=4\). This is an elementary certificate of a \(5\)-QP(4), and therefore also a \(5\)-QP(5). It corrects the observational sentence in Brown--Freedman--Shiue (2003) that they had not found a \(5\)-QP(5). It does not produce arbitrary length and does not answer their stronger question about a \(5\)-QP(1).
An exact factor-pair search proves the following finite statement: among the positive squares, there is no five-term quasi-progression of diameter at most \(3\) whose least consecutive gap is at most \(100,000,000\). Thus, in this fully searched regime, diameter \(4\) is sharp. This is a finite computational theorem, not a uniform nonexistence theorem.
For the cube question, the most recent directly relevant source I found is the April 2026 preprint of Bremner--Elsholtz--Ulas. It proves infinitely many dimension-\(3\) Hilbert cubes, but says that no dimension-\(\geq4\) example is known. Hence neither question in #782 is closed.
Claim labels
- (a) elementary-rigorous: proved below using only displayed identities and finite logic.
- (b) rigorous-modulo-named-theorem/source: depends on an explicitly named theorem or on the correctness of a cited paper.
- (c) plausible/structural-unverified: a literature-survey statement or diagnosis, not a theorem proved here.
- (d) computational-only: exact finite output of the supplied deterministic checker; it is not extrapolated beyond its stated range.
Step 0: live-page check, before doing mathematics
I accessed both the problem and its discussion thread through the Bright Data browser path because direct datacenter access is Cloudflare-walled:
- <https://www.erdosproblems.com/782>
- <https://www.erdosproblems.com/forum/thread/782>
The following is the verbatim current statement, copied from the live
page's “View the LaTeX source” view:
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,\ldots,x_k$ where, for some $d$ and all $1\leq i<k$,\[x_i+d\leq x_{i+1}\leq x_i+d+C.\]Do the squares contain arbitrarily large cubes\[a+\left\{ \sum_i \epsilon_ib_i : \epsilon_i\in \{0,1\}\right\}?\]
The live status panel showed:
OPEN;0 claimed proofs for this problem;Currently working on this problem None;Interested in collaborating None.
The listed remarks were:
> A question of Brown, Erdős, and Freedman [BEF90]. It is a classical fact that the squares do not contain arithmetic progressions of length \(4\).
>
> An affirmative answer to the first question implies an affirmative answer to the second.
>
> Solymosi [So07] conjectured the answer to the second question is no. Cilleruelo and Granville [CiGr07] have observed that the answer to the second question is no conditional on the Bombieri-Lang conjecture.
There was one comment, by Dogmachine at 17:31 on 9 August 2025:
> This question is likely very difficult to settle unconditionally, because it has a similar flavor to other seemingly hopeless problems such as the existence of perfect cuboids, perfect 3 x 3 magic squares whose entries are distinct squares, Büchi's problem, among others.
The page warns that comments are unverified. This comment claims neither a proof nor current work. Consequently none of the mandatory stop conditions fired.
Throughout the finite computation below, “squares” means the positive squares, as in Brown--Erdős--Freedman's definition of QP for sets of positive integers. Adding or removing the single square \(0\) cannot affect the arbitrary-length question, but it can change tiny finite searches, so the convention is stated explicitly.
Primary-source literature audit
1. The original paper
(b) T. C. Brown, P. Erdős, and A. R. Freedman, Quasi-progressions and descending waves, J. Combin. Theory Ser. A 53 (1990), 81--95. Author-hosted scan:
<https://www.sfu.ca/~vjungic/tbrown/tom-35.pdf>
The paper defines a \(k\)-QP(\(d\)) by
\[ \operatorname{diam}\{x_{i+1}-x_i:1\leq iIn particular, its proof that CP implies arbitrarily large cubes verifies the implication quoted on the live page.
2. The directly relevant 2003 computation/construction
(b) T. C. Brown, A. R. Freedman, and P. J.-S. Shiue, Progressions of squares, Australas. J. Combin. 27 (2003), 187--192:
<https://ajc.maths.uq.edu.au/pdf/27/ajc_v27_p187.pdf>
Theorem 2 proves infinitely many \(4\)-QP(1)s in the squares by a Pell-equation construction. The paper then says:
> We do not know whether or not there exists any 5-QP(1) among the squares. In fact, we have not found a 5-QP(5) among the squares.
It gives the \(5\)-QP(6)
\[ 1^2,41^2,58^2,71^2,82^2 \]with gaps \(1680,1683,1677,1683\). The supplied checker recomputes these gaps and also recomputes their \(4\)-QP(1) example
\[ 125^2,625^2,875^2,1068^2 \]with gaps \(375000,375000,374999\).
The new five-term certificate in this report shows that the quoted “not found” sentence was an overlooked small example, not a nonexistence result. Exact-phrase searches found the original sentence but no erratum or later correction. This correction does not affect their theorem.
3. Solymosi and the Bombieri--Lang conditional result
The cited chapter exists as J. Solymosi, Elementary additive combinatorics, in Additive Combinatorics, CRM Proc. Lecture Notes 43, AMS (2007), 29--38. I verified its bibliographic existence in the AMS volume listing, but could not obtain the chapter PDF itself. I therefore do not attribute details to it beyond what two accessible primary papers explicitly reproduce.
(b) J. Cilleruelo and A. Granville, Lattice points on circles, squares in arithmetic progressions and sumsets of squares, arXiv:math/0608109; CRM Proc. Lecture Notes 43 (2007), 241--262:
<https://arxiv.org/abs/math/0608109>
On page 4 they state Solymosi's conjecture as: there is some \(d>0\) for which no affine cube of dimension \(d\) consists of distinct squares. They also give the Bombieri--Lang reduction. A dimension-\(d\) cube supplies at least \(2^{d-2}\) distinct \(x\) for which
\[ y^2=(x^2+b_1)(x^2+b_2)(x^2+b_1+b_2), \]whereas the Bombieri--Lang consequence they invoke gives an absolute bound on rational points in this genus-\(2\) family. Thus \(d\) is conditionally absolutely bounded.
4. Unconditional finite-height bounds
(b) R. Dietmann and C. Elsholtz, Hilbert cubes in arithmetic sets, Rev. Mat. Iberoam. 31 (2015), 1477--1498, DOI 10.4171/RMI/877:
<https://ems.press/content/serial-article-files/38576?nt=1>
Their Theorem 1.1 gives, for sufficiently large \(N\),
\[ H(a_0;a_1,\ldots,a_d)\subseteq\{\text{squares}\}\cap[1,N] \quad\Longrightarrow\quad d\leq 7\log\log N. \]The proof actually obtains \(d\leq 6.96\log\log N+O(1)\). Since this bound grows with \(N\), it does not decide whether \(d\) is absolutely bounded.
(b) C. Elsholtz and L. Wurzinger, Sumsets in the set of squares, Q. J. Math. 75 (2024), 1243--1254, DOI 10.1093/qmath/haae044:
<https://research-explorer.ista.ac.at/download/18930/18931>
Its introduction still describes absolute boundedness of the Hilbert-cube dimension as Solymosi's conjecture and records \(d=O(\log\log N)\) as the unconditional state.
5. The April 2026 advance
(b) A. Bremner, C. Elsholtz, and M. Ulas, There are infinitely many Hilbert cubes of dimension 3 in the set of squares, arXiv:2604.05459v1, submitted 7 April 2026:
<https://arxiv.org/abs/2604.05459>
The preprint proves \(H_3(N)\gg N^{1/8}\) for reduced dimension-\(3\) cubes and gives explicit parametric families. The checker independently verifies its smallest all-distinct example:
\[ H(100;2400,4389,8736) =\{10^2,50^2,67^2,83^2,94^2,106^2,115^2,125^2\}. \](c) The authors say that, as far as they know, no Hilbert cube of dimension at least \(4\) has been found. This is a current literature-survey statement, not a nonexistence theorem. The preprint explicitly asks whether dimension \(4\) exists and whether dimensions are unbounded.
Literature-search conclusion
I found no primary source claiming that either unboundedness question is solved, no claimed \(5\)-QP(1), and no dimension-\(4\) square cube. The 2024 peer-reviewed paper and April 2026 preprint both treat absolute boundedness as open. This is consistent with the live page's OPEN status. The live remarks omit the 2003 quasi-progression paper, the 2015 \(7\log\log N\) bound, and the 2026 dimension-\(3\) construction.
New explicit five-term construction
Certificate
(a) Take
\[ (x_1,x_2,x_3,x_4,x_5)=(1,9,16,25,36). \]All five entries are positive integer squares. Their gaps are
\[ (x_2-x_1,x_3-x_2,x_4-x_3,x_5-x_4)=(8,7,9,11). \]With \(d=7\) and \(C=4\), every gap belongs to \([7,11]\). Hence
\[ x_i+7\leq x_{i+1}\leq x_i+7+4 \qquad(1\leq i<5). \]Therefore the positive squares contain a \(5\)-QP(4). In particular they contain a \(5\)-QP(5), contrary to the 2003 paper's observational “not found” sentence.
This is deliberately not promoted to a solution of #782: it treats \(k=5\) only, while #782 requires one fixed \(C\) for every \(k\).
Exact finite computation
Factor-pair reduction
Let \(r_0<\cdots For fixed \(d,C\), form a directed graph \(G_{d,C}\) on nonnegative integer roots, with an edge \(u\to v\) precisely when
Every edge is enumerated without a root cutoff. Indeed,
\[ n=v^2-u^2=(v-u)(v+u)=pq. \]The factors \(p=v-u\) and \(q=v+u\) have the same parity, and conversely every same-parity factorization \(n=pq\), \(p\leq q\), gives
\[ u=\frac{q-p}{2},\qquad v=\frac{q+p}{2}. \]Equivalently:
- if \(n\) is odd, enumerate factor pairs \(pq=n\);
- if \(4\mid n\), enumerate \(rs=n/4\) and use \(u=s-r,\ v=s+r\);
- if \(n\equiv2\pmod4\), there are no edges.
This is a bijection, so there is no hidden upper bound on the roots. The checker separately compares the factor-pair output to literal testing of \(v^2-u^2=n\) for every \(1\leq n\leq2000\).
The core logic is:
for d in range(1, D + 1):
edges = union(edges_for(n) for n in range(d, d + C + 1))
if directed_path_of_length_four(edges, positive_start=True):
return witness
return NONE
The complete optimized C++ implementation is embedded in the standalone Python verifier, which writes it to a temporary directory, compiles it, runs it, parses its output, and deletes the temporary files. Thus the .py file is the only required source file.
Sharp searched regime
(d) The exhaustive run returned:
QP witness: [1, 9, 16, 25, 36] gaps: [8, 7, 9, 11] diameter: 4
Dimension-3 cube roots: [10, 50, 67, 83, 94, 106, 115, 125]
Factor-pair audit: PASS for n=1..2000
NONE C=3 terms=5 max_min_gap=100000000
FIRST C=4 terms=5 d_window=7 roots=1,3,4,5,6
ALL CHECKS PASSED
Because every diameter-\(0,1,2,\) or \(3\) QP is also a path in a diameter-\(3\) window starting at its least gap, the NONE C=3 line simultaneously proves:
> There is no five-term quasi-progression of positive squares with gap diameter at most \(3\) and least gap at most \(10^8\).
Together with the explicit diameter-\(4\) witness of least gap \(7\), this gives the exact table:
| regime | minimum possible diameter |
|---|---:|
| five positive squares; least square-gap \(\leq10^8\) | \(4\) |
It also shows computationally that \(7\) is the smallest possible least gap for a \(5\)-QP(4).
This result says nothing about diameter \(0\)--\(3\) once the least gap exceeds \(10^8\), and therefore it is not a global determination of the least diameter for five terms.
Reproduction
Standalone verifier:
runs/erdos782_wave7l_reverify.py
SHA-256 6720e2d1bf99c50dd0e83a0deb4169e6bb8b8d6cd73181433e8c5c60c1eff792
Commands:
# Full report run: about 3 CPU-minutes and 420 MB RAM
python3 runs/erdos782_wave7l_reverify.py
# Fast smoke test through least gap 1,000,000
python3 runs/erdos782_wave7l_reverify.py --quick
# Any explicit bound at least 7
python3 runs/erdos782_wave7l_reverify.py --max-gap 20000000
Environment and measured full-run cost:
Python 3.12.3
g++ (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.0
elapsed=164.63 seconds
cpu=99%
peak RSS=416396 KB
The optimized exploratory source is also retained as runs/erdos782_probe.cpp (SHA-256 abe892696b6252374e8d66344e6df1c2de478291f483a2a8b09c9c8d397b7245). A separate full execution of that source took 176.70 seconds and returned the same NONE result. After the standalone full run, only \(O(1)\) checks concerning representations of 2400 and command-line range validation were added; the embedded full scanner was unchanged, and the final quick run passed.
An elementary fixed-generator bound for cubes
Let
\[ H(a_0;a_1,\ldots,a_d) \]be a cube in the positive squares with all generators positive. Define
\[ R(n)=\#\{(p,q):pq=n,\ p(a) The factor-pair bijection shows that there are at most \(R(a_1)\) possible distinct values among \(a_2,\ldots,a_d\).
If the generators are required to be distinct, this immediately gives
\[ d\leq 1+R(a_1)\leq 1+\frac{\tau(a_1)}2. \]If repeated generators are allowed, no positive value can occur three times: three copies of \(b\) would put
\[ a_0,\ a_0+b,\ a_0+2b,\ a_0+3b \]in the squares, a four-term arithmetic progression, contrary to Fermat's theorem quoted on the live page. Therefore:
\[ \boxed{d\leq1+2R(a_1)\leq1+\tau(a_1).} \]This last multiplicity step is (b), modulo the classical no-four-squares-in-AP theorem. The bound is uniform in \(a_0\) but not in \(a_1\), since \(\tau(a_1)\) is unbounded. It cleanly explains why fixing an early generator makes the extension problem finite while not answering #782.
For the checked cube \(H(100;2400,4389,8736)\), the script finds exactly \(R(2400)=12\) positive difference-of-square representations and confirms that \((67,83)\) and \((94,106)\) are two of them.
Exact remaining wall
Quasi-progressions
Write each gap as
\[ r_{i+1}^2-r_i^2=d+e_i,\qquad 0\leq e_i\leq C. \]Eliminating \(d\) gives the bounded-second-difference system
\[ r_{i+2}^2-2r_{i+1}^2+r_i^2=e_{i+1}-e_i, \qquad |e_{i+1}-e_i|\leq C. \]This is the precise connection to generalized Büchi-type Diophantine systems mentioned informally in the live comment.
Equivalently, in the factor graph above, #782 asks for one \(C\) for which directed paths have unbounded length as \(d\) varies. A negative solution asks for a bound \(L(C)\) on every such path, for each fixed \(C\).
The missing lemma is therefore one of the following mutually exclusive uniform statements:
1. Positive route: construct, for one fixed \(C\), integral solutions of the displayed system of every length (or unbounded paths in \(G_{d,C}\)).
2. Negative route: prove that for every fixed \(C\), the lengths of integral solutions are uniformly bounded independently of \(d\) and of the error word \((e_i)\).
Ordinary divisor estimates do not supply (2): each window has finitely many factor-pair edges, but the number of representations is not uniformly bounded as \(d\) varies, and endpoint matching across successive gaps is the hard Diophantine condition. Finite computation cannot replace the missing uniformity.
The current scanner scales essentially linearly over this range. A segmented extension to \(d=10^{12}\) would cost roughly \(10^4\) times the measured run, about \(1.65\times10^6\) core-seconds or \(460\) core-hours; at a realistic \$0.05--\$0.10 per core-hour, roughly \$23--\$46. The present SPF implementation would also require about 4 TB, so such a run would need segmented factorization. Even that finite range could not close the problem.
Hilbert cubes
The unconditional \(d\leq7\log\log N\) bound grows with height and therefore leaves unbounded dimension possible. The elementary fixed-\(a_1\) bound above grows with \(\tau(a_1)\) and likewise is not absolute.
The exact missing input on the negative side is an absolute, coefficient-uniform bound for rational/integral points on
\[ y^2=(x^2+b_1)(x^2+b_2)(x^2+b_1+b_2), \]or a substitute strong enough to bound \(2^{d-2}\) uniformly. Bombieri--Lang supplies this only conditionally in the cited argument. On the positive side, even one dimension-\(4\) example is currently missing according to the April 2026 source; an unbounded construction would need a genuinely scalable mechanism, not merely the now-known dimension-\(3\) families.
Honest scope
- The explicit \(5\)-QP(4) is a genuine construction and corrects a published search observation.
- The \(10^8\) cutoff result is exact but finite.
- The fixed-generator cube bound is rigorous but depends on \(a_1\).
- No uniform arbitrary-\(k\) construction, no uniform obstruction, and no dimension-\(4\) square cube is claimed here.
PARTIAL: Verified a 5-QP(4) of positive squares, correcting the 2003 “no 5-QP(5) found” observation; exhaustively proved diameter at least 4 for five terms with least gap at most \(10^8\), while both arbitrary-length questions remain open.