Forum Inbox Favourites Tags
More
FAQ Prizes Problem Lists Definitions Links
Forum
Inbox Favourites Tags FAQ Prizes Problem Lists Definitions Links
Dual View Random Solved Random Open
OPEN This is open, and cannot be resolved with a finite computation.
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$?
The open status of this problem reflects the current belief of the owner of this website. There may be literature on this problem that I am unaware of, which may partially or completely solve the stated problem. Please do your own literature search before expending significant effort on solving this problem. If you find any relevant literature not mentioned here, please add this in a comment.
Comment activity that has not yet been incorporated into the remarks
There are claims of partial results and/or a path to a solution in the comments.
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.

View the LaTeX source

View history

External data from the database - you can help update this
Formalised statement? No (Create a formalisation here)
The original source is ambiguous as to what the problem is - please add a comment if you have an opinion.
4 comments on this problem
Likes this problem None
Interested in collaborating None
Currently working on this problem None
This problem looks difficult None
This problem looks tractable None
The results on this problem could be formalisable None
I am working on formalising the results on this problem None

When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:

T. F. Bloom, Erdős Problem #662, https://www.erdosproblems.com/662, accessed 2026-07-12
Order by oldest first or newest first. (The most recent comments are highlighted in a red border.)

  • I got GPT-5.4 Pro to do a search through literature to find the right statement. There are 2 variants possible, both solved. Here's a note on it.

    Przemek Chojecki — 11:00 on 23 Apr 2026

  • From the examples of $f(t)$, it seems that this counts the number of points on a triangular lattice within a ball of radius $t$ centered on some point in the lattice.
    Perhaps the original question is asking whether the triangular lattice is the densest way to pack points in $\mathbb{R}^2$ under the restriction that the pairwise distance between points is at least 1.

    Adenwalla — 01:09 on 06 Jan 2026

    • Even then the given values of $f(t)$ aren't quite right; $f(1)=6$ and $f(\sqrt3)=12$ are fine, but the next few should be $f(2)=18$, $f(\sqrt7)=30$ and $f(3)=36$.
      In any case, I do agree that the idea behind the question was likely to ask about the densest possible packing of points with minimal distance 1 between any pair of them. However, this is equivalent to asking about the densest packing of diameter 1 circles, but László Fejes Tóth proved already in 1942 the optimality of the hexagonal packing (which puts the centers of the circles on a triagonal lattice) so it didn't really make much sense to ask about it half a century later.

      qawsed — 10:19 on 06 Jan 2026

All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.

Log in to add a comment.

Back to the forum