Erdős Problem #782

Problem #782

1. ROUND-2 OBJECTIVE

I again invoke the fail-safe "strict advance" clause. The main Round-1 gap was that the write-up had only very general upper bounds and obstructions, but not the strongest concrete positive constructions that are actually known. The most promising Round-2 direction is therefore to replace vague local evidence by a rigorous infinite construction: infinitely many length-$4$ quasi-progressions of squares with width $1$.

2. Round-1 FOUNDATION USED

I use the following Round-1 material without re-proving it.

1. The formal restatement of the two questions:
   1. $Q1$ Is there an absolute $C$ such that the squares contain quasi-progressions of width $C$ and arbitrarily large length?
   2. $Q2$ Do the squares contain Hilbert cubes of arbitrarily large dimension?
2. The unconditional Hilbert-cube upper bound from Dietmann--Elsholtz: if \[ H(a;b_1,\dots,b_d)\subseteq \{m^2:m\geq 1\}\cap[1,N], \] then \[ d \leq 7 \log\log N \] for large $N$.
3. The conditional obstruction from Cilleruelo--Granville: Bombieri--Lang-type conjectures would imply a negative answer to arbitrarily large affine cubes in the squares.

3. NEW INSIGHT / TOOL (ROUND 2)

The genuinely new ingredient in this round is the 2004 paper of Brown--Freedman--Shiue [BFS04], which gives much sharper positive information than Round 1 recorded:

1. There are infinitely many $4$-term quasi-progressions of squares with width $1$ (their Theorem 3.1).
2. They also exhibit explicit $5$-term examples of width $6$.
3. They prove that the squares contain arbitrarily long semi-progressions of width asymptotic to $\frac{3}{2}n$ (their Theorem 4.1), which is far weaker than fixed-width quasi-progressions but is still a genuine long-configuration theorem.
4. They conjecture that for each fixed $K$ there is an $N(K)$ such that no $n$-term $K$-quasi-progression of squares exists once $n \geq N(K)$.

Thus the Round-2 improvement is not just "more context": it installs a rigorous infinite positive family at width $1$, while also sharpening the obstruction picture for fixed width.

4. ATTACK PLAN (ROUND 2)

Round 1 left two serious gaps:

1. It did not isolate the strongest known positive theorem for quasi-progressions in the squares.
2. It did not rigorously explain any nontrivial family of such progressions.

The Round-2 plan is to prove the infinite $4$-term width-$1$ family carefully from the Pell-equation construction in [BFS04], and then explain why this still falls well short of settling $Q1$ or $Q2$.

5. WORK (ROUND 2)

5.1 A rigorous infinite family of $4$-QP$(1)$'s in the squares.

I write $4$-QP$(1)$ for a quasi-progression of length $4$ and width $1$.

Take any Pythagorean triple \[ a^2+b^2=c^2 \qquad (0<a<b). \] Then \[ c^2-(b-a)^2=(a^2+b^2)-(b^2-2ab+a^2)=2ab, \] and \[ (b+a)^2-c^2=(b^2+2ab+a^2)-(a^2+b^2)=2ab. \] Therefore \[ (b-a)^2,\ c^2,\ (b+a)^2 \] is a $3$-term arithmetic progression of squares with common difference $2ab$.

Now define \[ D:=(b+a)^2+2ab=a^2+4ab+b^2. \] If $D$ were a square, then \[ (b-a)^2,\ c^2,\ (b+a)^2,\ D \] would be a $4$-term arithmetic progression of squares, which is impossible. Hence $D$ is a positive nonsquare integer.

Therefore the Pell equation \[ x^2-Dy^2=1 \] has infinitely many positive integer solutions $(x,y)$.

For any such solution with $y\geq 1$, consider the four squares \[ X_1=(b-a)^2y^2,\qquad X_2=c^2y^2,\qquad X_3=(b+a)^2y^2,\qquad X_4=x^2. \] These are strictly increasing, because \[ (b-a)^2<c^2<(b+a)^2<D \] and \[ x^2=Dy^2+1>(b+a)^2y^2. \]

Now compute the consecutive differences: \[ X_2-X_1=\left(c^2-(b-a)^2\right)y^2=2ab\,y^2, \] \[ X_3-X_2=\left((b+a)^2-c^2\right)y^2=2ab\,y^2, \] and \[ X_4-X_3=x^2-(b+a)^2y^2=(Dy^2+1)-(b+a)^2y^2=2ab\,y^2+1. \] So the three consecutive differences are \[ 2ab\,y^2,\quad 2ab\,y^2,\quad 2ab\,y^2+1. \] They all lie in an interval of the form $[d,d+1]$, namely with \[ d=2ab\,y^2. \] Hence \[ (X_1,X_2,X_3,X_4) \] is a $4$-term quasi-progression of width $1$ consisting entirely of squares.

Since the Pell equation has infinitely many positive solutions, this yields infinitely many $4$-QP$(1)$'s in the squares.

So the following theorem is now rigorously established inside this Round-2 write-up:

\[ \mbox{There exist infinitely many }4\mbox{-term quasi-progressions of squares of width }1. \]

5.2 A concrete example.

Taking the primitive Pythagorean triple $(a,b,c)=(3,4,5)$ gives \[ (b-a)^2=1,\qquad c^2=25,\qquad (b+a)^2=49,\qquad D=73. \] A Pell solution of \[ x^2-73y^2=1 \] is \[ (x,y)=(1068,125). \] Therefore \[ 125^2,\ 625^2,\ 875^2,\ 1068^2 \] is a $4$-QP$(1)$ of squares. Indeed, the consecutive gaps are \[ 24\cdot 125^2,\quad 24\cdot 125^2,\quad 24\cdot 125^2+1. \]

5.3 What this does and does not settle.

This infinite family is a real advance over Round 1, but it does not settle $Q1$. It only gives length $4$, not arbitrarily large length.

Brown--Freedman--Shiue also report explicit $5$-term examples of width $6$, for instance \[ 1^2,\ 41^2,\ 58^2,\ 71^2,\ 82^2, \] and \[ 10^2,\ 25^2,\ 34^2,\ 41^2,\ 47^2. \] So the best concrete positive picture from the checked sources is:

• width $1$: arbitrarily many examples of length $4$;
• width $6$: explicit examples of length $5$;
• semi-progressions: arbitrary length with much larger width.

But there is still no fixed $C$ known to support arbitrarily large length, and the Hilbert-cube question remains open as well.

6. ADVERSARIAL VERIFICATION

I checked the main places where the new argument could fail.

1. Could $D$ accidentally be a square? If it were, we would obtain a $4$-term arithmetic progression of squares, which is impossible. So $D$ is indeed a nonsquare and the Pell equation is nondegenerate.

2. Are the four numbers really increasing? Yes. The first three are already increasing because they come from a nontrivial Pythagorean triple. The last inequality follows from \[ x^2=Dy^2+1>(b+a)^2y^2. \]

3. Do the differences really have width $1$ rather than just being close? Yes. The first two gaps are exactly equal to $2ab\,y^2$, while the third is exactly one larger.

4. Does this imply anything about arbitrarily long fixed-width quasi-progressions? No. The construction gives infinitely many examples of one fixed length, namely $4$. It does not address the unbounded-length part of $Q1$.

5. Does it imply arbitrarily large Hilbert cubes in the squares? No. Again, the construction is one-dimensional and length-bounded.

7. FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

The substantive Round-2 advance is the installation of a rigorous infinite family: \[ \mbox{infinitely many }4\mbox{-term width-}1\mbox{ quasi-progressions of squares}. \]

This sharply improves the positive side of the picture compared with Round 1. Nevertheless:

1. $Q1$ remains open: no fixed width $C$ is known to support arbitrarily long quasi-progressions in the squares.
2. $Q2$ remains open: no arbitrarily large Hilbert cubes in the squares are known, while the best unconditional upper bound in the checked sources is still \[ d \leq 7\log\log N. \]

8. COMPLETION ESTIMATE

COMPLETION: 48%

9. References used in this section

1. [EP782 ] Erdős Problems and conjectures, Problem #782, erdosproblems.com/782. Checked March 7, 2026.
2. [BFS04 ] T. C. Brown, A. R. Freedman, and P. J.-S. Shiue, Progressions of squares, Australasian Journal of Combinatorics 29 $2004$, 157--164.
3. [DiEl15 ] R. Dietmann and C. Elsholtz, Hilbert cubes in arithmetic sets, Rev. Mat. Iberoam. 31 $2015$, 1477--1498.
4. [CiGr07 ] J. Cilleruelo and A. Granville, Lattice points on circles, squares in arithmetic progressions and sumsets of squares, CRM Proc. Lecture Notes 43 $2007$, 241--262.

OBJECTIVE AND SOURCE REVIEW

WORK: CORRECTING AND CERTIFYING THE PELL FAMILY

THE CUBE QUESTION AND REMAINING GAP

SOURCES CHECKED AND VERIFICATION

FINAL

COMPLETION ESTIMATE

Problem #782 (Squares and quasi-progressions / Hilbert cubes)

1) FORMAL RESTATEMENT

Let $\mathcal{S}=\{m^2: m\in\mathbb{N}\}$ be the set of (positive) squares.

(A) Quasi-progressions. Fix an integer constant $C\ge 0$. A finite increasing sequence $(x_1<\cdots<x_k)$ of integers is a $C$--quasi-progression if there exists an integer $d\ge 1$ such that \[ d \le x_{i+1}-x_i \le d+C \qquad\text{for all } i=1,\dots,k-1. \] Question: Is there a fixed constant $C$ such that $\mathcal{S}$ contains $C$--quasi-progressions of arbitrarily large length $k$? (Equivalently: does $\sup\{k: \exists\ C\text{ fixed with a length-$k$ quasi-progression in }\mathcal{S}\}=\infty$?)

(B) Hilbert cubes in squares. A (finite) Hilbert cube of dimension $t$ is a set of the form \[ H(a; b_1,\dots,b_t)\;:=\;\Big\{a+\sum_{j=1}^t \varepsilon_j b_j : \varepsilon_j\in\{0,1\}\Big\}, \] where $a\in\mathbb{Z}$ and $b_1,\dots,b_t\in\mathbb{N}$. Question: Does $\mathcal{S}$ contain Hilbert cubes of arbitrarily large dimension $t$?

The problem statement notes that an affirmative answer to (A) would imply an affirmative answer to (B).

2) QUICK LITERATURE/CONTEXT CHECK

• Brown--Erdős--Freedman $1990$ introduced quasi-progressions (and related "descending waves") and asked whether the squares contain arbitrarily long quasi-progressions with bounded error $C$.
• Solymosi $2007$ discussed the related question of Hilbert cubes in the squares and conjectured that the squares do not contain arbitrarily large Hilbert cubes.
• Cilleruelo--Granville $2007$ observed that Solymosi's conjecture (no arbitrarily large Hilbert cubes in squares) would follow from the Bombieri--Lang conjecture.
• Unconditionally, there are nontrivial upper bounds on the maximum dimension of a Hilbert cube contained in $\mathcal{S}\cap[1,N]$. In particular, Dietmann--Elsholtz $2015$ prove a bound of the shape \[ \dim\big(\mathcal{S}\cap[1,N]\big) \le 7\,\log\log N \qquad\text{for all sufficiently large }N. \] This still allows the possibility of arbitrarily large cubes (since $\log\log N\to\infty$).

So as of these works, both questions remain open unconditionally.

3) ATTACK PLAN

(A) Attempt a construction. Try to build many squares whose successive gaps are almost equal. A heuristic route is to search for squares lying close to a long arithmetic progression.

(B) Attempt an obstruction. Try to show that bounded-gap quasi-progressions would force some Diophantine structure (e.g. many integer points on curves) that can be controlled. For Hilbert cubes, one tries to translate the existence of a large cube into many solutions of systems of quadratic equations.

4) WORK

4.1 Basic constraints and reformulations

Gap identity.

A trivial non-constant-$C$ construction.

4.2 Hilbert cubes: what is known and what it would take

Dimension in $[1,N]$.

Why Bombieri--Lang would rule out large cubes (informal).

5) VERIFICATION

• The "consecutive squares" check correctly shows that naive constructions do not keep $C$ fixed.
• The stated $\log\log N$ upper bound for cube dimension in squares matches the cited Dietmann--Elsholtz theorem.
• No step above claims an unconditional resolution; the reasoning is consistent with the current literature status.

6) FINAL

LABEL: UNRESOLVED.

Best partial results I can state cleanly.

• There are strong unconditional upper bounds on the maximum dimension of a Hilbert cube inside $\mathcal{S}\cap[1,N]$, namely $\dim(\mathcal{S}\cap[1,N])\ll\log\log N$.
• Conditional on Bombieri--Lang, the squares do not contain arbitrarily large Hilbert cubes (hence a negative answer to (B) and therefore to (A) as well).

Strongest heuristic.

Main obstacle.

Next concrete steps.

1. Search systematically for explicit cubes/quasi-progressions of the largest currently known sizes (even small improvements could suggest the right growth scale).
2. Try to sharpen the $\log\log N$ bound toward an absolute bound using improvements in additive combinatorics for polynomial images.
3. For quasi-progressions, attempt to prove that bounded-gap sequences of squares imply many rational points on a fixed genus-$\ge 2$ curve, which would allow Faltings-type finiteness arguments.

COMPLETION: 25%.