/-
Copyright 2026 The Formal Conjectures Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
https://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
-/
module
public import FormalConjecturesUtilErdős Problem 782
References:
[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.
@[expose] public sectionnamespace Erdos782
ContainsQuasiProgression S C k says that S contains a $k$-term quasi-progression of
diameter $C$: terms $x_1,\ldots,x_k\in S$ and a difference $d\geq 1$ with
$x_i+d\leq x_{i+1}\leq x_i+d+C$ for all $1\leq i<k$ (indexed from $0$ in Lean). The condition
$d\geq 1$ makes the terms strictly increasing, as in [BFS03].
def ContainsQuasiProgression (S : Set ℕ) (C k : ℕ) : Prop :=
∃ (x : ℕ → ℕ) (d : ℕ), 0 < d ∧ (∀ i < k, x i ∈ S) ∧
∀ i, i + 1 < k → x i + d ≤ x (i + 1) ∧ x (i + 1) ≤ x i + d + CThe Hilbert cube with presentation $(a_0; b_1,\ldots,b_d)$, that is, $$a_0+\left{ \sum_i \epsilon_ib_i : \epsilon_i\in {0,1}\right}.$$ The index set of the sum is the set of $i$ with $\epsilon_i=1$.
def hilbertCube {d : ℕ} (a₀ : ℤ) (b : Fin d → ℤ) : Set ℤ :=
{x | ∃ ε : Finset (Fin d), x = a₀ + ∑ i ∈ ε, b i}The base point $a_0$ lies in its Hilbert cube: take all $\epsilon_i=0$.
@[category API, AMS 11]
theorem mem_hilbertCube_self {d : ℕ} (a₀ : ℤ) (b : Fin d → ℤ) :
a₀ ∈ hilbertCube a₀ b :=
⟨∅, d:ℕa₀:ℤb:Fin d → ℤ⊢ a₀ = a₀ + ∑ i ∈ ∅, b i All goals completed! 🐙⟩The squares $1, 25, 49$ form a $3$-term arithmetic progression, hence the squares contain a $3$-term quasi-progression of diameter $0$.
@[category test, AMS 11]
theorem containsQuasiProgression_squares_three :
ContainsQuasiProgression {n : ℕ | IsSquare n} 0 3 := ⊢ ContainsQuasiProgression {n | IsSquare n} 0 3
refine ⟨fun i ↦ 1 + 24 * i, 24, ⊢ 0 < 24 All goals completed! 🐙, ?_, ?_⟩
⊢ ∀ i < 3, (fun i ↦ 1 + 24 * i) i ∈ {n | IsSquare n} i:ℕhi:i < 3⊢ (fun i ↦ 1 + 24 * i) i ∈ {n | IsSquare n}
i:ℕhi:0 < 3⊢ (fun i ↦ 1 + 24 * i) 0 ∈ {n | IsSquare n}i:ℕhi:1 < 3⊢ (fun i ↦ 1 + 24 * i) 1 ∈ {n | IsSquare n}i:ℕhi:2 < 3⊢ (fun i ↦ 1 + 24 * i) 2 ∈ {n | IsSquare n}
i:ℕhi:0 < 3⊢ (fun i ↦ 1 + 24 * i) 0 ∈ {n | IsSquare n} exact ⟨1, i:ℕhi:0 < 3⊢ (fun i ↦ 1 + 24 * i) 0 = 1 * 1 All goals completed! 🐙⟩
i:ℕhi:1 < 3⊢ (fun i ↦ 1 + 24 * i) 1 ∈ {n | IsSquare n} exact ⟨5, i:ℕhi:1 < 3⊢ (fun i ↦ 1 + 24 * i) 1 = 5 * 5 All goals completed! 🐙⟩
i:ℕhi:2 < 3⊢ (fun i ↦ 1 + 24 * i) 2 ∈ {n | IsSquare n} exact ⟨7, i:ℕhi:2 < 3⊢ (fun i ↦ 1 + 24 * i) 2 = 7 * 7 All goals completed! 🐙⟩
⊢ ∀ (i : ℕ),
i + 1 < 3 →
(fun i ↦ 1 + 24 * i) i + 24 ≤ (fun i ↦ 1 + 24 * i) (i + 1) ∧
(fun i ↦ 1 + 24 * i) (i + 1) ≤ (fun i ↦ 1 + 24 * i) i + 24 + 0 i:ℕa✝:i + 1 < 3⊢ (fun i ↦ 1 + 24 * i) i + 24 ≤ (fun i ↦ 1 + 24 * i) (i + 1) ∧
(fun i ↦ 1 + 24 * i) (i + 1) ≤ (fun i ↦ 1 + 24 * i) i + 24 + 0
i:ℕa✝:i + 1 < 3⊢ 1 + 24 * i + 24 ≤ 1 + 24 * (i + 1) ∧ 1 + 24 * (i + 1) ≤ 1 + 24 * i + 24 + 0
All goals completed! 🐙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.$$
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.
@[category research open, question, AMS 11]
theorem erdos_782.parts.i :
∃ C : ℕ, 0 < C ∧ ∀ k : ℕ, ContainsQuasiProgression {n : ℕ | IsSquare n} C k := ⊢ ∃ C, 0 < C ∧ ∀ (k : ℕ), ContainsQuasiProgression {n | IsSquare n} C k
All goals completed! 🐙Do the squares contain arbitrarily large cubes $$a+\left{ \sum_i \epsilon_ib_i : \epsilon_i\in {0,1}\right}?$$
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.
@[category research open, question, AMS 11]
theorem erdos_782.parts.ii :
∀ d : ℕ, ∃ (a : ℤ) (b : Fin d → ℤ),
(∀ i, b i ≠ 0) ∧ hilbertCube a b ⊆ {n : ℤ | IsSquare n} := ⊢ ∀ (d : ℕ), ∃ a b, (∀ (i : Fin d), b i ≠ 0) ∧ hilbertCube a b ⊆ {n | IsSquare n}
All goals completed! 🐙It is a classical fact that the squares do not contain arithmetic progressions of length $4$.
@[category research solved, AMS 11]
theorem erdos_782.variants.no_four_term_ap :
Set.IsAPOfLengthFree {n : ℕ | IsSquare n} 4 := ⊢ {n | IsSquare n}.IsAPOfLengthFree 4
All goals completed! 🐙Dietmann and Elsholtz [DiEl12, Theorem 1] proved that, for all sufficiently large $N$, if $a_0\geq 0$ and $b_1,\ldots,b_d$ are distinct positive integers such that the Hilbert cube $a_0+{0,b_1}+\cdots+{0,b_d}$ consists of squares in $[1,N]$, then $d\leq 7\log\log N$.
@[category research solved, AMS 11]
theorem erdos_782.variants.dietmann_elsholtz :
∃ N₀ : ℕ, ∀ N ≥ N₀, ∀ (d : ℕ) (a₀ : ℤ) (b : Fin d → ℤ),
0 ≤ a₀ → Function.Injective b → (∀ i, 0 < b i) →
hilbertCube a₀ b ⊆ {n : ℤ | IsSquare n ∧ 1 ≤ n ∧ n ≤ N} →
(d : ℝ) ≤ 7 * Real.log (Real.log N) := ⊢ ∃ N₀,
∀ N ≥ N₀,
∀ (d : ℕ) (a₀ : ℤ) (b : Fin d → ℤ),
0 ≤ a₀ →
Function.Injective b →
(∀ (i : Fin d), 0 < b i) →
hilbertCube a₀ b ⊆ {n | IsSquare n ∧ 1 ≤ n ∧ n ≤ ↑N} → ↑d ≤ 7 * Real.log (Real.log ↑N)
All goals completed! 🐙end Erdos782