Arrays of dots with distinct slopes or lengths in the square grid: extremal sizes and the existence of n-dot distinct-difference arrays

How many dots can be placed in the $n\times n$ integer grid so that the difference vectors determined by pairs of dots remain mutually distinguishable — by slope, by length, or by either? Erdős, Graham, Ruzsa, and Taylor (1992) initiated the quantitative study of this family of questions, proving $n^{1/2}\ll D\ll n^{4/5}$ for the maximum number $D$ of grid points with pairwise distinct slopes, and posed three problems: whether the square-root barrier can be broken; whether an $n\times n$ array with exactly $n$ dots and all pairwise difference vectors distinct exists for every $n$; and the corresponding extremal question for distinct lengths, which goes back to Erdős and Guy (1970). The square-root challenge was answered affirmatively by Zhang (1993), and the current records stand at $g(n)\ge c\,n^{2/3}(\log\log n)^{1/3}(\log n)^{-1/3}$ versus $g(n)\le C\,n^{4/5}$ for the slope variant, and $h(n)\ge c\,n^{2/3}$ versus $h(n)\le C\,n\exp(-c'\log n/\log\log n)$ for the length variant. This problem asks for the asymptotic orders of $g(n)$ and $h(n)$ and for a resolution of the every-$n$ existence question — all three of which remain open.

Background

Fix a positive integer $n$ and consider the square integer grid $[n]^2=\{1,\dots,n\}\times\{1,\dots,n\}$. Any two grid points $p\neq q$ determine a difference vector $p-q=(a,b)$, defined up to overall sign; its slope is $b/a$ in lowest terms (vertical vectors have infinite slope) and its length is the Euclidean norm $\|(a,b)\|$. A set $S$ of grid points has the distinct difference property if no two unordered pairs of points of $S$ determine the same vector — equivalently, any two of the $\binom{|S|}{2}$ difference vectors differ in slope or in length. This is the planar analogue of a Sidon set (also called a Golomb ruler): a set of integers in which all pairwise differences are distinct. Two stronger requirements are studied separately: (i) all $\binom{|S|}{2}$ slopes are pairwise distinct; (ii) all pairwise Euclidean distances are distinct (in recent literature such sets are called distance Sidon sets).

Two traditions feed these questions. In engineering, an $n\times n$ permutation array (one dot in each row and each column) with the distinct difference property is a Costas array, introduced by Costas in 1965 as a frequency-hopping pattern for sonar and radar with ideal auto-correlation properties; an array with one dot per column and the distinct difference property is a sonar sequence. Infinite families of Costas arrays exist — the Welch and Golomb constructions, which build them explicitly from finite fields and produce orders tied to prime powers (see Drakakis's survey) — but it is not known whether they exist in every order: as of 2011 the smallest orders with no known example were 32 and 33. In combinatorial number theory, Erdős and Guy (1970) studied distinct distances between lattice points, and a classical counting theorem of Landau on sums of two squares — the number of integers up to $x$ expressible as $a^2+b^2$ is $\Theta(x/\sqrt{\log x})$ — bounds the supply of distinct distances inside the grid: since squared distances between grid points are sums of two squares, $[n]^2$ determines only $\Theta(n^2/\sqrt{\log n})$ distinct distances.

The source paper of this problem — Erdős, Graham, Ruzsa, and Taylor (Combinatorica, 1992) — studied these configurations quantitatively. Writing $g(n)$ for the maximum size of a slope-distinct subset of $[n]^2$, they proved $c\,n^{1/2}\le g(n)\le C\,n^{4/5}$, and asked whether the square-root barrier can be broken, i.e. whether $g(n)\ge n^{1/2+\varepsilon}$ for some fixed $\varepsilon>0$. For sonar sequences with $n$ rows they showed that the maximal number of columns $m$ satisfies $n-Cn^{11/20}<m<n+4n^{2/3}$, so arrays with one dot per column in a square grid can hold asymptotically as many dots as the grid side; they closed the paper by asking whether an $n\times n$ array with exactly $n$ dots and the distinct difference property exists for every $n$. For the length variant — the extremal question raised by Erdős and Guy (1970) — writing $h(n)$ for the maximum size of a distance Sidon subset of $[n]^2$, the counting bound above gives $h(n)=O(n/(\log n)^{1/4})$, while constructions available at the time gave only about $n^{(2-\varepsilon)/3}$; Lefmann and Thiele (1995) later improved the lower bound to $\Omega(n^{2/3})$.

The three questions are the slope-, length-, and combined-difference instances of a single extremal objective: how densely can dots be packed into the square grid while keeping pairwise difference vectors mutually distinguishable? Recent work treats them as sibling geometric Sidon subset-selection problems (Balogh–Clemen–Dumitrescu–Liu 2024 for slopes in general point sets; Clemen–Führer–Roche-Newton 2026 and Pohoata–Sheffer 2026 for distance Sidon sets), using incidence geometry (the Szemerédi–Trotter theorem on point-line incidences), additive combinatorics, and hypergraph independence arguments. Nevertheless the asymptotic orders of both $g(n)$ and $h(n)$ remain undetermined, and the every-$n$ existence question remains open.

Problem Statement

All three parts refer to the square integer grid $[n]^2=\{1,\dots,n\}\times\{1,\dots,n\}$. The difference vector of an unordered pair of distinct dots $p,q$ is $p-q$, taken up to sign; writing $p-q=\pm(a,b)$, its slope is $b/a$ in lowest terms when $a\neq 0$ (vertical vectors have infinite slope) and its length is the Euclidean norm $\|(a,b)\|$. Thus two difference vectors coincide exactly when they agree in both slope and length.

(a) Slope extremal function. Let $g(n)$ be the largest cardinality of a set $S\subseteq[n]^2$ such that the $\binom{|S|}{2}$ slopes determined by pairs of points of $S$ are pairwise distinct. Determine the order of growth of $g(n)$. Currently, for absolute constants $c,C>0$,

$$c\,n^{2/3}\frac{(\log\log n)^{1/3}}{(\log n)^{1/3}}\le g(n)\le C\,n^{4/5},$$

and it is open where in the range $[2/3,4/5]$ the true exponent lies, and whether logarithmic factors enter. (The source paper's specific challenge of obtaining sets of size $n^{1/2+\varepsilon}$ for a fixed $\varepsilon>0$ was answered affirmatively by Zhang, so the surviving question is the exact order.)

(b) Length extremal function. Let $h(n)$ be the largest cardinality of a set $S\subseteq[n]^2$ such that all $\binom{|S|}{2}$ Euclidean distances between points of $S$ are distinct. Determine the order of growth of $h(n)$. Currently, for absolute constants $c,c',C>0$,

$$c\,n^{2/3}\le h(n)\le C\,n\,\exp\!\left(-c'\,\frac{\log n}{\log\log n}\right),$$

and it is open whether $h(n)$ is polynomially smaller than $n$ or, at the other extreme, whether $h(n)\ge n^{1-\delta}$ for every fixed $\delta>0$.

(c) Dense existence. A set $S$ has the distinct difference property if no two distinct unordered pairs of points of $S$ determine the same difference vector — equivalently, any two of its difference vectors differ in slope or in length. Does there exist a set of exactly $n$ points in $[n]^2$ with the distinct difference property for every positive integer $n$? Costas arrays provide examples for infinitely many $n$ (satisfying the stronger one-dot-per-row-and-column condition), and the source paper's sonar-sequence bounds show that for arrays with $n$ rows and one dot per column the maximal number of columns $m$ satisfies $n-Cn^{11/20}<m<n+4n^{2/3}$, placing density one at the natural boundary; but no construction is known for every $n$, and no $n$ is known for which the relaxed question (with no placement restriction) has a negative answer.

References

1. Paul Erdős, Ron Graham, Imre Z. Ruzsa, Herbert Taylor: Bounds for arrays of dots with distinct slopes or lengths. Combinatorica 12(1) (1992) 39–44. DOI: 10.1007/BF01191203. https://doi.org/10.1007/BF01191203
2. Zhen Zhang: A note on arrays of dots with distinct slopes. Combinatorica 13(1) (1993) 127–128. DOI: 10.1007/BF01202795. https://doi.org/10.1007/BF01202795
3. Hanno Lefmann, Torsten Thiele: Point sets with distinct distances. Combinatorica 15(3) (1995) 379–408. DOI: 10.1007/BF01299744. https://doi.org/10.1007/BF01299744
4. P. Erdős, R. K. Guy: Distinct distances between lattice points. Elemente der Mathematik 25 (1970) 121–123. Zbl 0222.10053. https://eudml.org/doc/140989
5. Marcos Charalambides: A note on distinct distance subsets. Journal of Geometry 104(3) (2013) 439–442. DOI: 10.1007/s00022-013-0176-0. https://doi.org/10.1007/s00022-013-0176-0
6. Konstantinos Drakakis: Open problems in Costas arrays. Preprint arXiv:1102.5727 (2011). https://arxiv.org/abs/1102.5727
7. Simon R. Blackburn, Tuvi Etzion, Keith M. Martin, Maura B. Paterson: Two-dimensional patterns with distinct differences: constructions, bounds, and maximal anticodes. IEEE Transactions on Information Theory 56(3) (2010) 1216–1229. DOI: 10.1109/TIT.2009.2039046. Preprint arXiv:0811.3832. https://arxiv.org/abs/0811.3832
8. József Balogh, Felix Christian Clemen, Adrian Dumitrescu, Dingyuan Liu: Subset selection problems in planar point sets. Preprint arXiv:2412.14287 (2024). https://arxiv.org/abs/2412.14287
9. Felix Christian Clemen: Applications of sparse hypergraph colorings. Discrete Mathematics 349(2) (2026) 114822. DOI: 10.1016/j.disc.2025.114822. Preprint arXiv:2406.01499. https://arxiv.org/abs/2406.01499
10. Felix Christian Clemen, Jakob Führer, Oliver Roche-Newton: Geometric Sidon problems. Preprint arXiv:2606.05841 (2026). https://arxiv.org/abs/2606.05841
11. Cosmin Pohoata, Adam Sheffer: Sets with no isosceles triangles / repeated distances in Atlanta. Blog post on Cosmin Pohoata's blog, 27 April 2026. https://pohoatza.wordpress.com/2026/04/27/sets-with-no-isosceles-triangles-repeated-distances-in-atlanta/
12. R. L. Graham: Erratum. Combinatorica 12(4) (1992), page i. DOI: 10.1007/BF01305227. https://doi.org/10.1007/BF01305227
13. Máté Jánosik, Artúr Nádor, Zoltán Lóránt Nagy, László Bence Simon: Avoiding configurations of small size in the square grid. Preprint arXiv:2601.14465 (2026). https://arxiv.org/abs/2601.14465
14. Ernie Croot, Junzhe Mao, Cosmin Pohoata, Adam Sheffer, Chi Hoi Yip: A combinatorial large sieve for Sidon sets, distances, and norm forms. Preprint arXiv:2606.17487 (2026). https://arxiv.org/abs/2606.17487 (formal version of the result of reference 11)
15. S. W. Graham, C. J. Ringrose: Lower bounds for least quadratic non-residues. In: Analytic Number Theory (Progress in Mathematics), Birkhäuser (1990) 269–309. DOI: 10.1007/978-1-4612-3464-7_18. https://doi.org/10.1007/978-1-4612-3464-7_18