Erdős Problem #1089

Erdős Problem 1089: the fixed-distance limit

1. Statement and outcome

Let $g_d(n)$ be the least number of distinct points in $\mathbb R^d$ that always determine at least $n$ distinct positive distances. For each fixed $n\ge2$ we prove \[ \binom{d+1}{n-1}+1\le g_d(n)\le\binom{d+n-1}{n-1}+1, \qquad \lim_{d\to\infty}\frac{g_d(n)}{d^{n-1}}=\frac1{(n-1)!}. \] The lower bound is relevant when $d+1\ge n-1$; otherwise the displayed binomial coefficient is interpreted as zero. The proof gives both bounds explicitly. The known upper bound is due to Bannai, Bannai and Stanton; the problem page credits the matching construction to Aletheia. This is a reconstruction, with no claim of novelty.

2. A large set with few distances

Put $s=n-1$ and suppose $d+1\ge s$. For every $s$-element subset $S$ of $\{1,\ldots,d+1\}$ take its incidence vector $v_S\in\{0,1\}^{d+1}$. All these vectors lie in the affine hyperplane $\sum x_i=s$, which is isometric to $\mathbb R^d$. For distinct $S,T$, \[ \|v_S-v_T\|^2=|S\triangle T|=2(s-|S\cap T|)\in\{2,4,\ldots,2s\}. \] Thus $\binom{d+1}{s}$ points can have at most $s$ distances, proving the lower bound, including the necessary extra one in the definition of $g_d(n)$.

3. A polynomial upper bound

Let $A=\{a_1,\ldots,a_N\}\subset\mathbb R^d$ determine exactly $t\le s$ positive distances $r_1,\ldots,r_t$. If $N=1$ the claimed bound is immediate, so assume $t\ge1$. Define the polynomial in two vector variables \[ F(x,y)=\prod_{j=1}^t\left(r_j^2-\|x-y\|^2\right). \] Its total degree in all $2d$ scalar variables is $2t$. On the chosen points, \[ F(a_i,a_j)=0\quad(i\ne j),\qquad F(a_i,a_i)=D:=\prod_{j=1}^t r_j^2>0. \] There are $\binom{d+t}{t}$ monomials in $d$ variables of degree at most $t$, by the stars-and-bars count. Suppose $N$ exceeds this number. Linear algebra then supplies real numbers $c_i$, not all zero, such that \[ \sum_{i=1}^N c_i a_i^\alpha=0\qquad\text{for every multi-index }\alpha\text{ with }|\alpha|\le t. \] Expand $F(x,y)$ as a sum of terms $b_{\alpha,\beta}x^\alpha y^\beta$. Each nonzero term has $|\alpha|+|\beta|\le2t$, so at least one of its two degrees is at most $t$. Consequently every term vanishes after summing against $c_i c_j$, and \[ \sum_{i,j}c_i c_j F(a_i,a_j)=0. \] But the diagonal formula makes the same quantity $D\sum_i c_i^2>0$, a contradiction. Therefore \[ N\le\binom{d+t}{t}\le\binom{d+s}{s}. \] Any larger point set has at least $s+1=n$ distances. This establishes the desired upper bound without assuming the few-distance theorem as an external input.

4. Limit and assessment

For fixed $s$, both $\binom{d+1}{s}$ and $\binom{d+s}{s}$ equal $d^s/s!+O_s(d^{s-1})$. The bounds therefore squeeze $g_d(s+1)/d^s$ to $1/s!$. The two-parameter bounds and the requested fixed-$n$ limit are proved; no exact formula for every small pair $(d,n)$ is asserted. Source and attribution: https://www.erdosproblems.com/1089, including its references to Bannai--Bannai--Stanton $1983$ and Aletheia $2026$.

Completion rate estimate: 100%.

FORMAL RESTATEMENT

Fix integers $d\ge 1$ and $n\ge 1$. For a finite set $P\subset\mathbb{R}^d$ of $m$ distinct points, let $D(P)$ be the set of distances determined by $P$: \[D(P)=\{\|x-y\|: x,y\in P,\ x\neq y\}. \] Define $g_d(n)$ to be the least integer $M$ such that every $M$-point set $P\subset\mathbb{R}^d$ satisfies $|D(P)|\ge n$. Equivalently, $g_d(n)-1$ is the maximum size of a point set in $\mathbb{R}^d$ that determines at most $n-1$ distinct distances.

QUICK LITERATURE/CONTEXT CHECK

I will not use external results beyond what is explicitly stated in the problem text. The problem text states: $g_d(n)\gg d^{n-1}$ is "easy" (Erdős); Erdős--Straus proved an upper bound $g_d(n)\le c^{d^{1-b_n}}$ for constants $c,b_n>0$; and small values include $g_1(3)=4$, $g_2(3)=6$, $g_3(3)=7$. It also states: the $2^d$ vertices of the $d$-cube determine only $d$ distances, hence $g_d(d+1)>2^d$.

ATTACK PLAN

This is naturally a question about $s$-distance sets in Euclidean space.

• (Lower bounds on $g_d(n)$) Construct large sets in $\mathbb{R}^d$ with at most $n-1$ distinct distances.
• (Upper bounds on $g_d(n)$) Prove general upper bounds on the size of $s$-distance sets in $\mathbb{R}^d$ via linear algebra (polynomial method).

WORK

Lemma 1089.1 (Maximal $(n-1)$-distance sets). Let $M_d(s)$ denote the maximum size of a finite point set in $\mathbb{R}^d$ that determines at most $s$ distinct distances. Then for every $n\ge 1$, \[g_d(n)=M_d(n-1)+1. \]

Proof. By definition, $g_d(n)$ is the smallest integer $M$ such that every $M$-point set has at least $n$ distances. Equivalently, $M-1$ is the largest size of a set having at most $n-1$ distances. That largest size is precisely $M_d(n-1)$. Hence $g_d(n)=M_d(n-1)+1$. $\square$

Lemma 1089.2 (Explicit $s$-distance sets of size $\binom{d}{s}$). Fix integers $d\ge 1$ and $1\le s\le d$. Let \[P_{d,s}=\{x\in\{0,1\}^d: x \text{ has exactly }s\text{ ones}\}. \] Then $|P_{d,s}|=\binom{d}{s}$ and $P_{d,s}$ determines exactly $s$ distinct distances. Consequently, \[M_d(s)\ge \binom{d}{s}\quad\text{and}\quad g_d(s+1)>\binom{d}{s}. \]

Proof. The cardinality $|P_{d,s}|=\binom{d}{s}$ is immediate. The distance claim is exactly Lemma 1088.1 proved above: between distinct $x,y\in P_{d,s}$, the squared distance is $|A\triangle B|\in\{2,4,\dots,2s\}$, and each value occurs. Thus $P_{d,s}$ has exactly $s$ distinct positive distances. Therefore $M_d(s)\ge |P_{d,s}|=\binom{d}{s}$, and by Lemma 1089.1, $g_d(s+1)=M_d(s)+1>\binom{d}{s}$. $\square$

Lemma 1089.3 (Polynomial-method upper bound for $s$-distance sets). Let $P\subset\mathbb{R}^d$ be a finite set of $m$ points that determines at most $s$ distinct positive distances. Then \[m\le \binom{d+2s}{2s}. \] In particular, \[g_d(n)=M_d(n-1)+1\le \binom{d+2(n-1)}{2(n-1)}+1. \]

Proof. Let the distinct positive squared distances among pairs in $P$ be $\alpha_1,\dots,\alpha_s\in\mathbb{R}_{>0}$. For each point $p\in P$, define a polynomial in $d$ variables \[F_p(x):=\prod_{j=1}^s\big(\|x-p\|^2-\alpha_j\big). \] Each factor $\|x-p\|^2-\alpha_j$ is a polynomial of total degree $2$ in $x$, hence $F_p$ has total degree at most $2s$. Now evaluate $F_p$ on $P$:

• If $q\in P$ with $q\neq p$, then $\|q-p\|^2\in\{\alpha_1,\dots,\alpha_s\}$, so one factor vanishes and $F_p(q)=0$.
• If $q=p$, then $\|p-p\|^2=0$, so \[F_p(p)=\prod_{j=1}^s(0-\alpha_j)=(-1)^s\prod_{j=1}^s\alpha_j\neq 0. \]

Thus the evaluation matrix $(F_p(q))_{p,q\in P}$ is diagonal with nonzero diagonal entries. In particular, the set of polynomials $\{F_p: p\in P\}$ is linearly independent over $\mathbb{R}$. Therefore $m=|P|$ is at most the dimension of the real vector space of polynomials in $d$ variables of total degree $\le 2s$, which equals $\binom{d+2s}{2s}$. This proves $m\le \binom{d+2s}{2s}$. Applying Lemma 1089.1 with $s=n-1$ yields the stated upper bound on $g_d(n)$. $\square$

FAST REALITY CHECK (local computation). I verified the construction in Lemma 1089.2 for small $(d,s)$ by enumerating $P_{d,s}$ and computing distinct squared distances; e.g.

d=6, s=3, |P|=20, distinct squared distances=[2, 4, 6]

which matches the claim "exactly $s$ distances".

VERIFICATION

• Lemma 1089.3: the diagonal evaluation argument is sound because $\alpha_j>0$ ensures $F_p(p)\neq 0$.
• The bound counts polynomials of degree $\le 2s$ (not homogeneous); the dimension formula $\binom{d+2s}{2s}$ is standard and follows from counting monomials.
• No hidden assumptions about "general position" are used.

FINAL

UNRESOLVED

(i) Strongest proved partial result. For fixed $n$ and all $d$, \[\binom{d}{n-1} < g_d(n) \le \binom{d+2(n-1)}{2(n-1)}+1. \] In particular, $g_d(n)=\Omega(d^{n-1})$ and $g_d(n)=O(d^{2n-2})$.

(ii) First gap (crisp). Determine the correct exponent of $d$ (or decide whether the growth is superpolynomial/subexponential) for fixed $n$ as $d\to\infty$, and in particular decide whether the limit \[\lim_{d\to\infty} \frac{g_d(n)}{d^{n-1}} \] exists.

(iii) Top 3 next moves.

• Strengthen the polynomial-method bound by incorporating additional structure (e.g. restricting to the sphere, using harmonic polynomials) to push the exponent down from $2(n-1)$ toward $n-1$.
• Search for improved lower-bound constructions of $(n-1)$-distance sets of size asymptotic to $c\,d^{n-1}$ with a computable constant $c$.
• For fixed $n$, do computational optimization for moderate $d$ to guess whether $M_d(n-1)$ is closer to $\binom{d}{n-1}$ or to the upper bound $\binom{d+2(n-1)}{2(n-1)}$.

(iv) Minimal counterexample structure. Failure of the limit $g_d(n)/d^{n-1}$ to converge would require two sequences of near-extremal $(n-1)$-distance sets in $\mathbb{R}^d$ whose sizes differ by a nonvanishing fraction of $d^{n-1}$. Any such extremal family would likely be highly symmetric (e.g. coming from combinatorial designs or spherical codes), because random-like sets typically generate many distances.