Erdős Problem #662

Erdős Problem 662 --- collection record

PROVENANCE AND STATUS

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/662.tex.

REUSED SOURCE 1

Consider the triangular lattice with minimal distance between two points $1$. Denote by $f(t)$ the number of distances from any points $\leq t$. For example $f(1)=6$, $f(\sqrt{3})=12$, and $f(3)=18$. Let $x_1,\ldots,x_n\in \mathbb{R}^2$ be such that $d(x_i,x_j)\geq 1$ for all $i\neq j$. Is it true that, provided $n$ is sufficiently large depending on $t$, the number of distances $d(x_i,x_j)\leq t$ is less than or equal to $f(t)$ with equality perhaps only for the triangular lattice? In particular, is it true that the number of distances $\leq \sqrt{3}-\epsilon$ is less than $1$? A problem of Erdős, Lovász, and Vesztergombi. This is essentially verbatim the problem description in [Er97e], but this does not make sense as written; there must be at least one typo. Suggestions about what this problem intends are welcome. Erdős also goes on to write 'Perhaps the following stronger conjecture holds: Let $t_1<t_2<\cdots$ be the set of distances occurring in the triangular lattice. $t_1=1$ $t_2=\sqrt{3}$ $t_3=3$ $t_4=5$ etc. Is it true that there is an $\epsilon_n$ so that for every set $y_1,\ldots,$ with $d(y_i,y_j)\geq 1$ the number of distances $d(y_i,y_j)<t_n$ is less than $f(t_n)$?' Again, this is nonsense interpreted literally; I am not sure what Erdős intended. References [Er97e] Erdős, Paul, Some of my favourite unsolved problems . Math. Japon. $1997$, 527-537.

1) FORMAL RESTATEMENT The problem statement as written is inconsistent/ambiguous, so I separate a literal reading from a minimal corrected reading.

(Literal text.) Take the triangular lattice scaled so that its minimal interpoint distance is $1$. Define $f(t)$ to be "the number of distances from any points $\le t$", with examples $f(1)=6$, $f(\sqrt3)=12$, and $f(3)=18$. Given $x_1,\ldots,x_n\in\mathbb{R}^2$ with $d(x_i,x_j)\ge 1$ for $i\neq j$, ask whether (for $n$ large depending on $t$) the "number of distances $d(x_i,x_j)\le t$" is at most $f(t)$, with equality perhaps only for the triangular lattice.

Ambiguity 1: "number of distances $d(x_i,x_j)\le t$" could mean (a) the number of unordered pairs $\{i,j\}$ with $d(x_i,x_j)\le t$, or (b) the number of distinct distance values $\le t$ attained by the set, or (c) for a fixed $i$, the number of indices $j\neq i$ with $d(x_i,x_j)\le t$ (a local neighbour count). If interpreted as (a) or (b), the numerical examples for $f(t)$ do not match standard meanings.

Ambiguity 2 / typo: the examples are consistent with $f(t)$ meaning a local neighbour count in the triangular lattice, but then $f(3)=18$ is incorrect; it should read $f(2)=18$ (see Lemma 1 below).

(Minimal corrected statement.) Define $f(t)$ to be the number of lattice points of the triangular lattice within Euclidean distance $\le t$ of a fixed lattice point, excluding the point itself. Given a finite set $\{x_1,\ldots,x_n\}\subset\mathbb{R}^2$ with pairwise distances $\ge 1$, define the local count $N_t(i):=|\{j\neq i: |x_i-x_j|\le t\}|$. Conjecture (plausible intent): for each fixed $t$, and for all sufficiently large $n$ (depending on $t$), one has $\max_i N_t(i)\le f(t)$, with equality only for subsets of the triangular lattice (up to rigid motion).

2) QUICK LITERATURE/CONTEXT CHECK I do not assume any external circle-packing results beyond what I prove below. The statement itself notes that it does not make sense as written.

3) ATTACK PLAN First, disprove any literal interpretation that would bound a global count of pairs by the constant $f(t)$. Second, adopt the minimal corrected "local neighbour count" formulation and prove whatever rigorous bounds are accessible (e.g. $t=1$ kissing number).

4) WORK

Lemma 1 (what $f(t)$ equals for small $t$ in the triangular lattice, and locating the typo). Let $\Lambda$ be the triangular lattice generated by $u=(1,0)$ and $v=(\tfrac12,\tfrac{\sqrt3}{2})$, so the minimal nonzero distance in $\Lambda$ is $1$. For $t\ge 0$, let $f(t):=|\{p\in \Lambda\setminus\{0\}: |p|\le t\}|$. Then $f(1)=6$, $f(\sqrt3)=12$, $f(2)=18$, and $f(3)=36$.

Proof. Every lattice point has the form $p=a u + b v$ with $a,b\in\mathbb{Z}$. A direct computation gives $|p|^2 = a^2 + ab + b^2$. Thus $|p|\le t$ is equivalent to $a^2+ab+b^2\le t^2$. For $t=1$, the only integer solutions with $(a,b)\neq (0,0)$ are the six unit vectors $(\pm1,0),(0,\pm1),(\pm1,\mp1)$, giving $f(1)=6$. For $t=\sqrt3$, one additionally gets the six solutions with $a^2+ab+b^2=3$, namely permutations/signs of $(1,1)$, totaling $12$. For $t=2$, one further includes the six solutions with $a^2+ab+b^2=4$ (e.g. $(\pm2,0),(0,\pm2),(\pm2,\mp2)$), giving $18$. For $t=3$, the additional solutions have $a^2+ab+b^2\in\{7,9\}$, and an explicit enumeration yields $36$ total points within radius $3$. (I verified these counts by exhaustive enumeration of integer pairs $(a,b)$ in a suitable bounding box.) $\square$

Lemma 2 (kissing number $6$ at radius $t=1$). Let $S=\{x_0,x_1,\ldots,x_m\}\subset\mathbb{R}^2$ satisfy $|x_i-x_j|\ge 1$ for all $i\neq j$. If additionally $|x_i-x_0|\le 1$ for all $i=1,\ldots,m$, then $m\le 6$.

Proof. Fix $i\neq j$ in $\{1,\ldots,m\}$ and let $\theta_{ij}$ be the angle at $x_0$ between the segments $x_0x_i$ and $x_0x_j$. By the law of cosines, $|x_i-x_j|^2 = |x_i-x_0|^2 + |x_j-x_0|^2 -2|x_i-x_0||x_j-x_0|\cos\theta_{ij}$. Using $|x_i-x_j|\ge 1$ and $|x_i-x_0|\le 1$, $|x_j-x_0|\le 1$, we obtain $1 \le |x_i-x_j|^2 \le 1^2+1^2 - 2\cdot 1\cdot 1\cdot \cos\theta_{ij} = 2-2\cos\theta_{ij}$. Therefore $\cos\theta_{ij}\le 1/2$ and hence $\theta_{ij}\ge \pi/3=60^\circ$. Now order the points $x_1,\ldots,x_m$ by their polar angle around $x_0$; consecutive points in this cyclic order have angular separation at least $\pi/3$. Summing these $m$ separations around the full circle gives $2\pi \ge m(\pi/3)$, so $m\le 6$. $\square$

Counterexample 3 (disproves a literal global-pair-count interpretation). Interpret "the number of distances $d(x_i,x_j)\le t$" as the number of unordered pairs $\{i,j\}$ with $|x_i-x_j|\le t$. Then for $t=1$ the claimed bound "$\le f(1)=6$" is false for arbitrarily large $n$.

Verification. Take $n$ points to be a large finite subset of the triangular lattice $\Lambda$ (scaled so minimal distance is $1$). Then every lattice edge of length $1$ contributes a pair at distance $1\le t$, and a finite patch of $\Lambda$ has $\Theta(n)$ such edges. In particular, for $n\ge 10$ there are certainly more than $6$ unit-distance pairs, contradicting the literal global bound by $f(1)=6$. $\square$

FAST REALITY CHECK (values of $f(t)$). Using the coordinate formula $|a u+b v|^2=a^2+ab+b^2$ and enumerating integer pairs $(a,b)$, I obtained: - $f(1)=6$, $f(\sqrt3)=12$, $f(2)=18$, $f(3)=36$. Thus the example "$f(3)=18$" in the problem text is inconsistent with the natural local-neighbour definition and appears to be a typo for "$f(2)=18$".

5) VERIFICATION - Lemma 1: the squared-distance identity $|a u+b v|^2=a^2+ab+b^2$ is a direct computation; the counts for $t\in\{1,\sqrt3,2,3\}$ were verified by exhaustive enumeration. - Lemma 2: the only inequality step is $|x_i-x_j|^2\le 2-2\cos\theta_{ij}$, which follows by bounding the radii by $1$. This is valid because the radii appear with a negative sign in the cosine term. - Counterexample 3: any finite patch of the triangular lattice with $n$ vertices has at least $n-1$ edges, and all such edges have length $1$, giving at least $n-1>6$ pairs with distance $\le 1$ when $n\ge 8$.

6) FINAL: UNRESOLVED (i) Strongest proved partial result: under the corrected local-neighbour interpretation, the $t=1$ case holds with the sharp bound $\max_i N_1(i)\le 6$ (Lemma 2). Also, the intended lattice counts satisfy $f(1)=6,f(\sqrt3)=12,f(2)=18,\ldots$ (Lemma 1). (ii) First gap (crisp): for fixed $t>1$, prove or disprove the corrected inequality $\max_i N_t(i)\le f(t)$ for all finite $1$-separated sets in the plane (perhaps for all $n$, not just large $n$). (iii) Top 3 next moves (concrete): 1. For specific radii (e.g. $t=\sqrt3$ or $t=2$), treat the problem as packing circles of radius $1/2$ inside a circle of radius $t+1/2$ and attempt an exact extremal argument. 2. Try to prove a stability statement: if a point has near-maximal $N_t(i)$, then the neighbours must lie close to the corresponding shells of the triangular lattice. 3. Computation: for fixed small $t$ (e.g. $t=2$), perform exact search/optimization for maximum $N_t(i)$ using circle packing heuristics to see if values exceed the lattice count. (iv) Minimal counterexample structure (for the corrected statement): a counterexample would be a 1-separated set with a point $x_0$ having more than $f(t)$ neighbours within distance $t$, i.e. an unusually dense packing of equal circles in a disk. Any such configuration would likely be highly symmetric and live near the boundary of the disk (where area-based bounds are weakest).

COMPLETION ESTIMATE

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Consider the triangular lattice with minimal distance between two points $1$. Denote by $f(t)$ the number of distances from any points $\leq t$. For example $f(1)=6$, $f(\sqrt{3})=12$, and $f(3)=18$. Let $x_1,\ldots,x_n\in \mathbb{R}^2$ be such that $d(x_i,x_j)\geq 1$ for all $i\neq j$. Is it true that, provided $n$ is sufficiently large depending on $t$, the number of distances $d(x_i,x_j)\leq t$ is less than or equal to $f(t)$ with equality perhaps only for the triangular lattice? In particular, is it true that the number of distances $\leq \sqrt{3}-\epsilon$ is less than $1$? A problem of Erdős, Lovász, and Vesztergombi. This is essentially verbatim the problem description in [Er97e], but this does not make sense as written; there must be at least one typo. Suggestions about what this problem intends are welcome. Erdős also goes on to write 'Perhaps the following stronger conjecture holds: Let $t_1<t_2<\cdots$ be the set of distances occurring in the triangular lattice. $t_1=1$ $t_2=\sqrt{3}$ $t_3=3$ $t_4=5$ etc. Is it true that there is an $\epsilon_n$ so that for every set $y_1,\ldots,$ with $d(y_i,y_j)\geq 1$ the number of distances $d(y_i,y_j)<t_n$ is less than $f(t_n)$?' Again, this is nonsense interpreted literally; I am not sure what Erdős intended. References [Er97e] Erdős, Paul, Some of my favourite unsolved problems . Math. Japon. $1997$, 527-537.

1) FORMAL RESTATEMENT The problem statement as written is inconsistent/ambiguous, so I separate a literal reading from a minimal corrected reading.

(Literal text.) Take the triangular lattice scaled so that its minimal interpoint distance is $1$. Define $f(t)$ to be "the number of distances from any points $\le t$", with examples $f(1)=6$, $f(\sqrt3)=12$, and $f(3)=18$. Given $x_1,\ldots,x_n\in\mathbb{R}^2$ with $d(x_i,x_j)\ge 1$ for $i\neq j$, ask whether (for $n$ large depending on $t$) the "number of distances $d(x_i,x_j)\le t$" is at most $f(t)$, with equality perhaps only for the triangular lattice.

Ambiguity 1: "number of distances $d(x_i,x_j)\le t$" could mean (a) the number of unordered pairs $\{i,j\}$ with $d(x_i,x_j)\le t$, or (b) the number of distinct distance values $\le t$ attained by the set, or (c) for a fixed $i$, the number of indices $j\neq i$ with $d(x_i,x_j)\le t$ (a local neighbour count). If interpreted as (a) or (b), the numerical examples for $f(t)$ do not match standard meanings.

Ambiguity 2 / typo: the examples are consistent with $f(t)$ meaning a local neighbour count in the triangular lattice, but then $f(3)=18$ is incorrect; it should read $f(2)=18$ (see Lemma 1 below).

(Minimal corrected statement.) Define $f(t)$ to be the number of lattice points of the triangular lattice within Euclidean distance $\le t$ of a fixed lattice point, excluding the point itself. Given a finite set $\{x_1,\ldots,x_n\}\subset\mathbb{R}^2$ with pairwise distances $\ge 1$, define the local count $N_t(i):=|\{j\neq i: |x_i-x_j|\le t\}|$. Conjecture (plausible intent): for each fixed $t$, and for all sufficiently large $n$ (depending on $t$), one has $\max_i N_t(i)\le f(t)$, with equality only for subsets of the triangular lattice (up to rigid motion).

2) QUICK LITERATURE/CONTEXT CHECK I do not assume any external circle-packing results beyond what I prove below. The statement itself notes that it does not make sense as written.

3) ATTACK PLAN First, disprove any literal interpretation that would bound a global count of pairs by the constant $f(t)$. Second, adopt the minimal corrected "local neighbour count" formulation and prove whatever rigorous bounds are accessible (e.g. $t=1$ kissing number).

4) WORK

Lemma 1 (what $f(t)$ equals for small $t$ in the triangular lattice, and locating the typo). Let $\Lambda$ be the triangular lattice generated by $u=(1,0)$ and $v=(\tfrac12,\tfrac{\sqrt3}{2})$, so the minimal nonzero distance in $\Lambda$ is $1$. For $t\ge 0$, let $f(t):=|\{p\in \Lambda\setminus\{0\}: |p|\le t\}|$. Then $f(1)=6$, $f(\sqrt3)=12$, $f(2)=18$, and $f(3)=36$.

Proof. Every lattice point has the form $p=a u + b v$ with $a,b\in\mathbb{Z}$. A direct computation gives $|p|^2 = a^2 + ab + b^2$. Thus $|p|\le t$ is equivalent to $a^2+ab+b^2\le t^2$. For $t=1$, the only integer solutions with $(a,b)\neq (0,0)$ are the six unit vectors $(\pm1,0),(0,\pm1),(\pm1,\mp1)$, giving $f(1)=6$. For $t=\sqrt3$, one additionally gets the six solutions with $a^2+ab+b^2=3$, namely permutations/signs of $(1,1)$, totaling $12$. For $t=2$, one further includes the six solutions with $a^2+ab+b^2=4$ (e.g. $(\pm2,0),(0,\pm2),(\pm2,\mp2)$), giving $18$. For $t=3$, the additional solutions have $a^2+ab+b^2\in\{7,9\}$, and an explicit enumeration yields $36$ total points within radius $3$. (I verified these counts by exhaustive enumeration of integer pairs $(a,b)$ in a suitable bounding box.) $\square$

Lemma 2 (kissing number $6$ at radius $t=1$). Let $S=\{x_0,x_1,\ldots,x_m\}\subset\mathbb{R}^2$ satisfy $|x_i-x_j|\ge 1$ for all $i\neq j$. If additionally $|x_i-x_0|\le 1$ for all $i=1,\ldots,m$, then $m\le 6$.

Proof. Fix $i\neq j$ in $\{1,\ldots,m\}$ and let $\theta_{ij}$ be the angle at $x_0$ between the segments $x_0x_i$ and $x_0x_j$. By the law of cosines, $|x_i-x_j|^2 = |x_i-x_0|^2 + |x_j-x_0|^2 -2|x_i-x_0||x_j-x_0|\cos\theta_{ij}$. Using $|x_i-x_j|\ge 1$ and $|x_i-x_0|\le 1$, $|x_j-x_0|\le 1$, we obtain $1 \le |x_i-x_j|^2 \le 1^2+1^2 - 2\cdot 1\cdot 1\cdot \cos\theta_{ij} = 2-2\cos\theta_{ij}$. Therefore $\cos\theta_{ij}\le 1/2$ and hence $\theta_{ij}\ge \pi/3=60^\circ$. Now order the points $x_1,\ldots,x_m$ by their polar angle around $x_0$; consecutive points in this cyclic order have angular separation at least $\pi/3$. Summing these $m$ separations around the full circle gives $2\pi \ge m(\pi/3)$, so $m\le 6$. $\square$

Counterexample 3 (disproves a literal global-pair-count interpretation). Interpret "the number of distances $d(x_i,x_j)\le t$" as the number of unordered pairs $\{i,j\}$ with $|x_i-x_j|\le t$. Then for $t=1$ the claimed bound "$\le f(1)=6$" is false for arbitrarily large $n$.

Verification. Take $n$ points to be a large finite subset of the triangular lattice $\Lambda$ (scaled so minimal distance is $1$). Then every lattice edge of length $1$ contributes a pair at distance $1\le t$, and a finite patch of $\Lambda$ has $\Theta(n)$ such edges. In particular, for $n\ge 10$ there are certainly more than $6$ unit-distance pairs, contradicting the literal global bound by $f(1)=6$. $\square$

FAST REALITY CHECK (values of $f(t)$). Using the coordinate formula $|a u+b v|^2=a^2+ab+b^2$ and enumerating integer pairs $(a,b)$, I obtained: - $f(1)=6$, $f(\sqrt3)=12$, $f(2)=18$, $f(3)=36$. Thus the example "$f(3)=18$" in the problem text is inconsistent with the natural local-neighbour definition and appears to be a typo for "$f(2)=18$".

5) VERIFICATION - Lemma 1: the squared-distance identity $|a u+b v|^2=a^2+ab+b^2$ is a direct computation; the counts for $t\in\{1,\sqrt3,2,3\}$ were verified by exhaustive enumeration. - Lemma 2: the only inequality step is $|x_i-x_j|^2\le 2-2\cos\theta_{ij}$, which follows by bounding the radii by $1$. This is valid because the radii appear with a negative sign in the cosine term. - Counterexample 3: any finite patch of the triangular lattice with $n$ vertices has at least $n-1$ edges, and all such edges have length $1$, giving at least $n-1>6$ pairs with distance $\le 1$ when $n\ge 8$.

6) FINAL: UNRESOLVED (i) Strongest proved partial result: under the corrected local-neighbour interpretation, the $t=1$ case holds with the sharp bound $\max_i N_1(i)\le 6$ (Lemma 2). Also, the intended lattice counts satisfy $f(1)=6,f(\sqrt3)=12,f(2)=18,\ldots$ (Lemma 1). (ii) First gap (crisp): for fixed $t>1$, prove or disprove the corrected inequality $\max_i N_t(i)\le f(t)$ for all finite $1$-separated sets in the plane (perhaps for all $n$, not just large $n$). (iii) Top 3 next moves (concrete): 1. For specific radii (e.g. $t=\sqrt3$ or $t=2$), treat the problem as packing circles of radius $1/2$ inside a circle of radius $t+1/2$ and attempt an exact extremal argument. 2. Try to prove a stability statement: if a point has near-maximal $N_t(i)$, then the neighbours must lie close to the corresponding shells of the triangular lattice. 3. Computation: for fixed small $t$ (e.g. $t=2$), perform exact search/optimization for maximum $N_t(i)$ using circle packing heuristics to see if values exceed the lattice count. (iv) Minimal counterexample structure (for the corrected statement): a counterexample would be a 1-separated set with a point $x_0$ having more than $f(t)$ neighbours within distance $t$, i.e. an unusually dense packing of equal circles in a disk. Any such configuration would likely be highly symmetric and live near the boundary of the disk (where area-based bounds are weakest).