Graham's conjecture asserts that any subset AA of the two-dimensional integer lattice Z2\mathbb{Z}^2 with divergent reciprocal-square sum, ∑a∈A∖{0}1/∥a∥2=∞\sum_{a\in A\setminus\{0\}}1/\|a\|^2=\infty, must contain infinitely many axis-parallel squares, i.e. quadruples {(x,y),(x+d,y),(x,y+d),(x+d,y+d)}\{(x,y),(x+d,y),(x,y+d),(x+d,y+d)\} with d≥1d\ge 1. The condition is the natural two-dimensional analogue of a divergent harmonic sum, and the conjecture is the lattice analogue of the still-open k=4k=4 case of Erdős's conjecture that a set of positive integers with divergent reciprocal sum contains arbitrarily long arithmetic progressions. Recent work of Bloom–Sisask and Pilatte settled orientation-free three-point companions of this problem (three-term progressions in one dimension; isosceles right triangles in arbitrary orientation in the lattice), so any such AA is now known to contain infinitely many isosceles right triangles, but these results do not force even the axis-parallel three-vertex corners of squares, and the complete square is a genuinely four-variable counting problem for which no logarithmic-density technique exists. The conjecture remains open in its original generality.

Background

A three-term arithmetic progression is a triple x,x+d,x+2dx, x+d, x+2d with d≠0d\ne 0. Erdős conjectured in the 1970s that any set AA of positive integers whose reciprocal sum ∑n∈A1/n\sum_{n\in A}1/n diverges must contain arithmetic progressions of every length. This is far stronger than Szemerédi's theorem, which gives progressions only from positive upper density (divergent reciprocal sums correspond to the much weaker logarithmic density). Bloom and Sisask (2020) proved that any set of integers without a three-term progression has size at most N/(log⁡N)1+cN/(\log N)^{1+c} in {1,…,N}\{1,\dots,N\}, thereby establishing the first non-trivial case k=3k=3 of Erdős's conjecture; the cases k≥4k\ge 4 remain open, and surveys as recent as December 2025 still list the general conjecture as unsettled. The two-dimensional analogue replaces integers by lattice points. For a∈Z2a\in\mathbb{Z}^2 write ∥a∥\|a\| for the Euclidean norm; the series ∑a∈A∖{0}1/∥a∥2\sum_{a\in A\setminus\{0\}}1/\|a\|^2 plays the role of the harmonic sum, since a full lattice shell at radius rr contributes on the order of 1/r1/r per shell. An axis-parallel square in A⊂Z2A\subset\mathbb{Z}^2 is a set of four points {(x,y),(x+d,y),(x,y+d),(x+d,y+d)}⊂A\{(x,y),(x+d,y),(x,y+d),(x+d,y+d)\}\subset A with d≥1d\ge 1. The density version of the square problem is classical: by the multidimensional Szemerédi theorem of Fürstenberg and Katznelson, every subset of the grid of positive upper density contains an axis-parallel square, with a combinatorial proof for grids given by Solymosi (2004) answering a question of Erdős and Graham. In the logarithmic-density regime, Shkredov and Solymosi (2021) conjectured that any A⊂Z2A\subset\mathbb{Z}^2 with ∑a∈A∖{0}1/∥a∥2=∞\sum_{a\in A\setminus\{0\}}1/\|a\|^2=\infty contains infinitely many isosceles right triangles (three points forming two equal perpendicular sides, in any orientation). Pilatte (2022) proved this by generalizing the Bloom–Sisask machinery from the equation a1−2a2+a3=0a_1-2a_2+a_3=0 to equations T1a1+T2a2+T3a3=0T_1a_1+T_2a_2+T_3a_3=0 with commuting nonsingular transformations, showing more generally that such AA contains infinitely many non-trivial solutions of any nonsingular three-variable lattice equation, and infinitely many copies directly similar to any fixed lattice triangle. These theorems, however, produce isosceles right triangles in arbitrary orientations — copies directly similar to a fixed triangle, rotated copies included — whereas three of the four vertices of an axis-parallel square form an axis-parallel corner of fixed orientation, and the translation-invariant linear relations defining axis-parallel corners fall outside the nonsingular three-variable equations covered by Pilatte's machinery. Even the three-vertex (axis-parallel corner) part of the square problem at logarithmic density therefore remains open: Shkredov–Solymosi explicitly distinguish their tilted-corner conjecture from axis-parallel corners, for which the best density bound is N2/(log⁡log⁡N)CN^2/(\log\log N)^C (Shkredov), too weak to force convergence of ∑1/∥a∥2\sum 1/\|a\|^2 — and a fortiori the full four-vertex square remains open. Graham's conjecture — stated in his survey chapter "Euclidean Ramsey Theory" in the Handbook of Discrete and Computational Geometry and quoted by Pilatte (Remark 1.7) — predicts that the divergent reciprocal-square sum already forces infinitely many complete axis-parallel squares; Pilatte notes its difficulty is comparable to the open k=4k=4 case of Erdős's progression conjecture, because a square is a four-point, two-parameter configuration and no method currently proves any four-variable statement at logarithmic density.

Problem Statement

Let AA be a subset of the integer lattice Z2\mathbb{Z}^2 such that

∑a∈A∖{0}1∥a∥2=+∞,\sum_{a\in A\setminus\{0\}}\frac{1}{\|a\|^2}=+\infty,

where ∥a∥\|a\| denotes the Euclidean norm of aa. Must AA contain infinitely many axis-parallel squares, that is, quadruples of distinct points {(x,y),(x+d,y),(x,y+d),(x+d,y+d)}⊂A\{(x,y),(x+d,y),(x,y+d),(x+d,y+d)\}\subset A with integers x,yx,y and d≥1d\ge 1? This is Graham's conjecture as recorded in his "Euclidean Ramsey Theory" survey (Conjecture 8.4.6 of the 1997 Handbook of Discrete and Computational Geometry chapter) and quoted by Pilatte (Remark 1.7 of arXiv:2111.03838); no restriction on AA beyond the divergent reciprocal-square sum is imposed.

References

  1. Cédric Pilatte, "New bound for Roth's theorem with generalized coefficients", Discrete Analysis 2022:16, 21 pp.; arXiv:2111.03838; DOI 10.19086/da.55553; journal page: https://discreteanalysisjournal.com/article/55553-new-bound-for-roth-s-theorem-with-generalized-coefficients; https://arxiv.org/abs/2111.03838 (primary source; Remark 1.7 quotes Graham's conjecture; reference list gives the handbook citation)
  2. Ilya Shkredov and Jozsef Solymosi, "Tilted Corners in Integer Grids", arXiv:2103.01645 (2021); also published in INTEGERS: Electronic Journal of Combinatorial Number Theory 21A (2021), Article A20 (Ron Graham memorial volume), and in Number Theory and Combinatorics: A Collection in Honor of the Mathematics of Ronald Graham, De Gruyter, 2022, pp. 329–338; DOI 10.1515/9783110754216-020; https://arxiv.org/abs/2103.01645
  3. Thomas F. Bloom and Olof Sisask, "Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions", arXiv:2007.03528 (2020); https://arxiv.org/abs/2007.03528
  4. Ronald L. Graham, "Euclidean Ramsey Theory", chapter of Handbook of Discrete and Computational Geometry, CRC Press (2nd ed., 2004), DOI 10.1201/9781420035315.ch11; original first-edition version: CRC Press, 1997, pp. 164–177, where Pilatte locates Conjecture 8.4.6; https://doi.org/10.1201/9781420035315.ch11
  5. J. Solymosi, "A Note on a Question of Erdős and Graham", Combinatorics, Probability and Computing 13 (2004), DOI 10.1017/s0963548303005959; https://doi.org/10.1017/s0963548303005959
  6. Weiwen Zhang, "Roth-type theorems in additive combinatroics" [title as on arXiv], arXiv:2512.08455 (2025); https://arxiv.org/abs/2512.08455
  7. Máté Jánosik, Artúr Nádor, Zoltán Lóránt Nagy, and László Bence Simon, "Avoiding configurations of small size in the square grid", arXiv:2601.14465 (2026); https://arxiv.org/abs/2601.14465
  8. Gyula Károlyi and Jozsef Solymosi, "A Salem-Spencer-Type Construction for Large Subsets of Integer Grids with No Isosceles Right Triangles", arXiv:2607.22828 (2026); https://arxiv.org/abs/2607.22828
  9. Isaac Mammel, William Smith, and Carl Yerger, "Ramsey Theory on the Integer Grid: The "L" Problem", arXiv:2502.05162 (2025); https://arxiv.org/abs/2502.05162