Erdős Problem #661

Erdős Problem 661 --- 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/661.tex.

REUSED SOURCE 1

Are there, for all large $n$, some points $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^2$ such that the number of distinct distances $d(x_i,y_j)$ is\[o\left(\frac{n}{\sqrt{\log n}}\right)?\] One can also ask this for points in $\mathbb{R}^3$. In $\mathbb{R}^4$ Lenz observed that there are $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^4$ such that $d(x_i,y_j)=1$ for all $i,j$, taking the points on two orthogonal circles. More generally, if $F(2n)$ is the minimal number of such distances, and $f(2n)$ is minimal number of distinct distances between any $2n$ points in $\mathbb{R}^2$, then is $F =o(f)$? See also [89] .

1) FORMAL RESTATEMENT For each $n\ge 1$, consider two $n$-point sets $X=\{x_1,\ldots,x_n\}\subset\mathbb{R}^2$ and $Y=\{y_1,\ldots,y_n\}\subset\mathbb{R}^2$. Let \[ D(X,Y):=\left|\{\,|x_i-y_j|:1\le i,j\le n\,\}\right| \] be the number of distinct bipartite distances. Question: do there exist, for all sufficiently large $n$, choices of $X,Y$ with \[ D(X,Y)=o\!\left(\frac{n}{\sqrt{\log n}}\right)\ ? \] (One may also ask the same question in $\mathbb{R}^3$.)

2) QUICK LITERATURE/CONTEXT CHECK I did not find (and do not assume) a standard theorem resolving this; the problem appears open on erdosproblems.com as of early 2026.

3) ATTACK PLAN Proof-track ideas (to show existence of very small $D(X,Y)$): - Use special configurations where $|x_i-y_j|$ depends on a low-complexity parameter, e.g. $x_i$ and $y_j$ constrained to curves/lines so distances become a 1D additive structure. - Try to imitate the $\mathbb{R}^4$ Lenz construction by seeking near-constant distances via orthogonality-like constraints (circles/spheres), but in $\mathbb{R}^2$ this is much harder.

Disproof-track ideas (to show lower bounds): - Incidence-geometry: interpret distance equations $|x-y|=r$ as incidences between points and circles, then try to force many radii. - Reduce to sumset/difference-set bounds in special cases (e.g. points on parallel lines).

I can give a clean $O(n)$ construction and show that in the "two parallel lines" model one cannot beat $\Omega(n)$.

4) WORK

Lemma 1 (a simple $O(n)$ construction in $\mathbb{R}^2$). For each $n$, let $X:=\{(i,0): i=0,1,\ldots,n-1\}$ and $Y:=\{(j,1): j=0,1,\ldots,n-1\}$. Then $D(X,Y)\le n$.

Proof. For $x=(i,0)\in X$ and $y=(j,1)\in Y$ we have $|x-y|^2=(i-j)^2+1$. Thus distinct distances are in bijection with distinct values of $(i-j)^2$ as $i,j$ range over $\{0,\ldots,n-1\}$. The integer difference $i-j$ ranges over $\{-(n-1),\ldots,n-1\}$, so $|i-j|$ ranges over $\{0,1,\ldots,n-1\}$ and $(i-j)^2$ takes at most $n$ values. Therefore $|x-y|$ takes at most $n$ values and $D(X,Y)\le n$. $\square$

Lemma 2 (parallel-line lower bound). Suppose $X\subset L_0$ and $Y\subset L_1$ where $L_0,L_1$ are two parallel lines at fixed distance $h>0$, and write the coordinates so that $L_0=\{(t,0):t\in\mathbb{R}\}$ and $L_1=\{(t,h):t\in\mathbb{R}\}$. Let $A:=\{a: (a,0)\in X\}$ and $B:=\{b: (b,h)\in Y\}\subset\mathbb{R}$. Then $D(X,Y)=|\{|a-b|:a\in A,b\in B\}|$. In particular, if $|A|=|B|=n$ then $D(X,Y)\ge n$.

Proof. The squared distance between $(a,0)$ and $(b,h)$ is $(a-b)^2+h^2$, so distinct distances are determined exactly by distinct values of $|a-b|$. To lower bound these, let $m:=\min(A\cup B)$. If $m\in A$, then $m\le b$ for all $b\in B$, hence $\{|m-b|:b\in B\}=\{b-m:b\in B\}$ has size $|B|=n$ because $b\mapsto b-m$ is injective on $B$. Thus $|\{|a-b|:a\in A,b\in B\}|\ge n$. If instead $m\in B$, the same argument with roles reversed gives at least $|A|=n$ distinct absolute differences. $\square$

FAST REALITY CHECK (brute force on the $3\times 3$ grid $\{0,1,2\}^2$). I minimized $D(X,Y)$ over all choices of $X,Y\subset\{0,1,2\}^2$ with $|X|=|Y|=n$. Results (squared-distance distinct counts, then witnesses): - $n=1$: min found $D=1$, e.g. $X=\{(0,0)\}$, $Y=\{(0,0)\}$. - $n=2$: min found $D=1$, e.g. $X=\{(0,0), (1,1)\}$, $Y=\{(0,1), (1,0)\}$. - $n=3$: min found $D=2$, e.g. $X=\{(0,0), (0,2), (1,1)\}$, $Y=\{(0,1), (1,0), (1,2)\}$. - $n=4$: min found $D=2$, e.g. $X=\{(0,0), (0,2), (1,1), (2,0)\}$, $Y=\{(0,1), (1,0), (1,2), (2,1)\}$. - $n=5$: min found $D=4$, e.g. $X=\{(0,0), (0,2), (1,1), (2,0), (2,2)\}$, $Y=\{(0,0), (0,2), (1,1), (2,0), (2,2)\}$. These checks show that extremely small $D(X,Y)$ can occur for small $n$ (e.g. $D=1$ for $n=2$), but do not address asymptotics.

5) VERIFICATION - Lemma 1: I checked that $(i-j)^2$ indeed takes exactly the $n$ values $0^2,1^2,\ldots,(n-1)^2$ by taking $j=0$ and $i=0,\ldots,n-1$. So $D(X,Y)=n$ for that construction. - Lemma 2: the key injectivity step uses that the minimum element $m$ of $A\cup B$ lies in exactly one of the sets or both; in all cases, distances from $m$ to the opposite set produce $n$ distinct values.

6) FINAL: UNRESOLVED (i) Strongest proved partial result: there is a simple construction with $D(X,Y)=n$ (Lemma 1), and in the special model where $X$ and $Y$ lie on two parallel lines one always has $D(X,Y)\ge n$ (Lemma 2), so parallel-line constructions cannot achieve $o(n)$. (ii) First gap (crisp): either construct $X,Y\subset\mathbb{R}^2$ with $D(X,Y)=o(n/\sqrt{\log n})$ or prove a lower bound $D(X,Y)\gg n/\sqrt{\log n}$ for all $X,Y$. (iii) Top 3 next moves (concrete): 1. Try 2D analogues of Lenz-type orthogonality: points on circles/ellipses with constrained chord lengths, and count the resulting distance spectrum. 2. Incidence approach: for each radius $r$, circles of radius $r$ centered at points of $X$ contain at most $n$ points of $Y$; bound total incidences to force many radii. 3. Computation: search over structured families (grids, cyclic polygons, lattice slices) for unusually small $D(X,Y)$ to identify candidate extremizers. (iv) Minimal counterexample structure (if the answer is "yes"): one would need configurations where the $n^2$ distances $|x_i-y_j|$ collapse into $o(n/\sqrt{\log n})$ radii, meaning that for most $x\in X$ the set of distances to $Y$ is itself very small and highly overlapping across different $x$, suggesting strong algebraic or incidence structure (many points of $Y$ lying on many common circles with centers in $X$).

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.

Are there, for all large $n$, some points $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^2$ such that the number of distinct distances $d(x_i,y_j)$ is\[o\left(\frac{n}{\sqrt{\log n}}\right)?\] One can also ask this for points in $\mathbb{R}^3$. In $\mathbb{R}^4$ Lenz observed that there are $x_1,\ldots,x_n,y_1,\ldots,y_n\in \mathbb{R}^4$ such that $d(x_i,y_j)=1$ for all $i,j$, taking the points on two orthogonal circles. More generally, if $F(2n)$ is the minimal number of such distances, and $f(2n)$ is minimal number of distinct distances between any $2n$ points in $\mathbb{R}^2$, then is $F =o(f)$? See also [89] .

1) FORMAL RESTATEMENT For each $n\ge 1$, consider two $n$-point sets $X=\{x_1,\ldots,x_n\}\subset\mathbb{R}^2$ and $Y=\{y_1,\ldots,y_n\}\subset\mathbb{R}^2$. Let \[ D(X,Y):=\left|\{\,|x_i-y_j|:1\le i,j\le n\,\}\right| \] be the number of distinct bipartite distances. Question: do there exist, for all sufficiently large $n$, choices of $X,Y$ with \[ D(X,Y)=o\!\left(\frac{n}{\sqrt{\log n}}\right)\ ? \] (One may also ask the same question in $\mathbb{R}^3$.)

2) QUICK LITERATURE/CONTEXT CHECK I did not find (and do not assume) a standard theorem resolving this; the problem appears open on erdosproblems.com as of early 2026.

3) ATTACK PLAN Proof-track ideas (to show existence of very small $D(X,Y)$): - Use special configurations where $|x_i-y_j|$ depends on a low-complexity parameter, e.g. $x_i$ and $y_j$ constrained to curves/lines so distances become a 1D additive structure. - Try to imitate the $\mathbb{R}^4$ Lenz construction by seeking near-constant distances via orthogonality-like constraints (circles/spheres), but in $\mathbb{R}^2$ this is much harder.

Disproof-track ideas (to show lower bounds): - Incidence-geometry: interpret distance equations $|x-y|=r$ as incidences between points and circles, then try to force many radii. - Reduce to sumset/difference-set bounds in special cases (e.g. points on parallel lines).

I can give a clean $O(n)$ construction and show that in the "two parallel lines" model one cannot beat $\Omega(n)$.

4) WORK

Lemma 1 (a simple $O(n)$ construction in $\mathbb{R}^2$). For each $n$, let $X:=\{(i,0): i=0,1,\ldots,n-1\}$ and $Y:=\{(j,1): j=0,1,\ldots,n-1\}$. Then $D(X,Y)\le n$.

Proof. For $x=(i,0)\in X$ and $y=(j,1)\in Y$ we have $|x-y|^2=(i-j)^2+1$. Thus distinct distances are in bijection with distinct values of $(i-j)^2$ as $i,j$ range over $\{0,\ldots,n-1\}$. The integer difference $i-j$ ranges over $\{-(n-1),\ldots,n-1\}$, so $|i-j|$ ranges over $\{0,1,\ldots,n-1\}$ and $(i-j)^2$ takes at most $n$ values. Therefore $|x-y|$ takes at most $n$ values and $D(X,Y)\le n$. $\square$

Lemma 2 (parallel-line lower bound). Suppose $X\subset L_0$ and $Y\subset L_1$ where $L_0,L_1$ are two parallel lines at fixed distance $h>0$, and write the coordinates so that $L_0=\{(t,0):t\in\mathbb{R}\}$ and $L_1=\{(t,h):t\in\mathbb{R}\}$. Let $A:=\{a: (a,0)\in X\}$ and $B:=\{b: (b,h)\in Y\}\subset\mathbb{R}$. Then $D(X,Y)=|\{|a-b|:a\in A,b\in B\}|$. In particular, if $|A|=|B|=n$ then $D(X,Y)\ge n$.

Proof. The squared distance between $(a,0)$ and $(b,h)$ is $(a-b)^2+h^2$, so distinct distances are determined exactly by distinct values of $|a-b|$. To lower bound these, let $m:=\min(A\cup B)$. If $m\in A$, then $m\le b$ for all $b\in B$, hence $\{|m-b|:b\in B\}=\{b-m:b\in B\}$ has size $|B|=n$ because $b\mapsto b-m$ is injective on $B$. Thus $|\{|a-b|:a\in A,b\in B\}|\ge n$. If instead $m\in B$, the same argument with roles reversed gives at least $|A|=n$ distinct absolute differences. $\square$

FAST REALITY CHECK (brute force on the $3\times 3$ grid $\{0,1,2\}^2$). I minimized $D(X,Y)$ over all choices of $X,Y\subset\{0,1,2\}^2$ with $|X|=|Y|=n$. Results (squared-distance distinct counts, then witnesses): - $n=1$: min found $D=1$, e.g. $X=\{(0,0)\}$, $Y=\{(0,0)\}$. - $n=2$: min found $D=1$, e.g. $X=\{(0,0), (1,1)\}$, $Y=\{(0,1), (1,0)\}$. - $n=3$: min found $D=2$, e.g. $X=\{(0,0), (0,2), (1,1)\}$, $Y=\{(0,1), (1,0), (1,2)\}$. - $n=4$: min found $D=2$, e.g. $X=\{(0,0), (0,2), (1,1), (2,0)\}$, $Y=\{(0,1), (1,0), (1,2), (2,1)\}$. - $n=5$: min found $D=4$, e.g. $X=\{(0,0), (0,2), (1,1), (2,0), (2,2)\}$, $Y=\{(0,0), (0,2), (1,1), (2,0), (2,2)\}$. These checks show that extremely small $D(X,Y)$ can occur for small $n$ (e.g. $D=1$ for $n=2$), but do not address asymptotics.

5) VERIFICATION - Lemma 1: I checked that $(i-j)^2$ indeed takes exactly the $n$ values $0^2,1^2,\ldots,(n-1)^2$ by taking $j=0$ and $i=0,\ldots,n-1$. So $D(X,Y)=n$ for that construction. - Lemma 2: the key injectivity step uses that the minimum element $m$ of $A\cup B$ lies in exactly one of the sets or both; in all cases, distances from $m$ to the opposite set produce $n$ distinct values.

6) FINAL: UNRESOLVED (i) Strongest proved partial result: there is a simple construction with $D(X,Y)=n$ (Lemma 1), and in the special model where $X$ and $Y$ lie on two parallel lines one always has $D(X,Y)\ge n$ (Lemma 2), so parallel-line constructions cannot achieve $o(n)$. (ii) First gap (crisp): either construct $X,Y\subset\mathbb{R}^2$ with $D(X,Y)=o(n/\sqrt{\log n})$ or prove a lower bound $D(X,Y)\gg n/\sqrt{\log n}$ for all $X,Y$. (iii) Top 3 next moves (concrete): 1. Try 2D analogues of Lenz-type orthogonality: points on circles/ellipses with constrained chord lengths, and count the resulting distance spectrum. 2. Incidence approach: for each radius $r$, circles of radius $r$ centered at points of $X$ contain at most $n$ points of $Y$; bound total incidences to force many radii. 3. Computation: search over structured families (grids, cyclic polygons, lattice slices) for unusually small $D(X,Y)$ to identify candidate extremizers. (iv) Minimal counterexample structure (if the answer is "yes"): one would need configurations where the $n^2$ distances $|x_i-y_j|$ collapse into $o(n/\sqrt{\log n})$ radii, meaning that for most $x\in X$ the set of distances to $Y$ is itself very small and highly overlapping across different $x$, suggesting strong algebraic or incidence structure (many points of $Y$ lying on many common circles with centers in $X$).