on distinct distances and polynomial partitioning

Overview

Guth and Katz proved that any set $P$ of $N$ points in the Euclidean plane determines at least

$$c\frac{N}{\log N}$$

distinct nonzero distances (Guth & Katz, 2015). This gives the sharp power of $N$ in Erdős’s distinct-distance problem, whose square-grid construction shows that one cannot hope for more than order $N/\sqrt{\log N}$ in general (Erdős, 1946; Garibaldi, Iosevich & Senger, 2011).

The proof is a model example of modern incidence geometry. It does not count distances directly. It counts equal-distance quadruples, identifies them with partial orientation-preserving rigid symmetries of the point set, converts those symmetries into intersections of lines in ${\mathbb{R}}^3$, and then proves the needed line-incidence estimates using polynomial partitioning and ruled-surface geometry. The two technical novelties are complementary: polynomial ham-sandwich partitioning controls highly incident points, while the flecnode polynomial and the classical theory of ruled surfaces control ordinary two-line intersections.

The Distinct-Distance Problem

For a finite set

$$P\subset {\mathbb{R}}^2,|P|=N,$$

define the set of nonzero distances

$$D(P)=\{|p-q|:p,q\in P,p\ne q\}.$$

Erdős asked how small $|D(P)|$ can be as a function of $N$ (Erdős, 1946). The square grid gives the basic obstruction. If $P$ is a $\sqrt{N}\times \sqrt{N}$ lattice grid, then squared distances have the form

$$a^2+b^2,|a|,|b|\le \sqrt{N}.$$

By the Landau—Ramanujan theorem, the number of integers up to order $N$ that are sums of two squares is of order

$$\frac{N}{\sqrt{\log N}}.$$

Thus

$$|D(P)|\lesssim \frac{N}{\sqrt{\log N}}$$

for this configuration. Erdős conjectured that this is sharp up to constants.

Guth and Katz prove the weaker but power-sharp lower bound

$$|D(P)|\gtrsim \frac{N}{\log N}.$$

The logarithmic gap between $\log N$ and $\sqrt{\log N}$ remains. What the paper settles is the exponent: every $N$-point set in the plane determines $N^{1-o(1)}$ distinct distances.

Distance Quadruples

The first move is to replace distinct distances by collisions among distances. Define the set of distance quadruples

$$Q(P)=\{(p_1,p_2,p_3,p_4)\in P^4:|p_1-p_2|=|p_3-p_4|\ne 0\}.$$

If there are few distinct distances, then many ordered pairs must share the same distance.

Let

$$D(P)=\{d_1,\dots ,d_m\},m=|D(P)|.$$

Let $n_i$ be the number of ordered pairs $(p,q)\in P^2$ with $p\ne q$ and $|p-q|=d_i$. Then

$$\sum _{i=1}^m{n}_i=N^2-N,|Q(P)|=\sum _{i=1}^m{n}_i^2.$$

Cauchy’s inequality gives

$$(N^2-N{)}^2\le \left(\sum _{i=1}^m{n}_i^2\right)m=|Q(P)||D(P)|.$$

Therefore

$$|D(P)|\ge \frac{(N^2-N{)}^2}{|Q(P)|}.$$

Thus the theorem follows from the upper bound

$$|Q(P)|\lesssim N^3\log N.$$

The rest of the paper is an incidence-geometric proof of this quadruple estimate.

Orientation-Preserving Rigid Motions

Let $G$ be the group of orientation-preserving rigid motions of the plane. An element of $G$ is either a translation or a rotation about a point.

Given a distance quadruple

$$(p_1,p_2,p_3,p_4)\in Q(P),$$

there is a unique $g\in G$ such that

$$g(p_1)=p_3,g(p_2)=p_4.$$

Existence follows because the two ordered segments have the same nonzero length. Uniqueness follows after requiring orientation preservation: a translation taking $p_1$ to $p_3$ followed by a uniquely determined rotation about $p_3$ sends $p_2$ to $p_4$.

For $k\ge 2$, define

$$G_k(P)=\{g\in G:|P\cap gP|\ge k\}.$$

These are not subgroups in general. They are partial symmetries: a motion in $G_k(P)$ maps at least $k$ points of $P$ back into $P$.

If

$$|P\cap gP|=k,$$

then $g$ accounts for

$$2\left(\genfrac{}{}{0ex}{}{k}{2}\right)$$

ordered distance quadruples. Indeed, choose two distinct points $q_i,q_j\in P\cap gP$, let $p_i=g^{-1}{q}_i$ and $p_j=g^{-1}{q}_j$, and use the quadruples

$$(p_i,p_j,q_i,q_j),(p_j,p_i,q_j,q_i).$$

Conversely, every quadruple assigned to $g$ arises this way.

Writing $G_{=k}(P)$ for the motions with exactly $k$ common points, one obtains

$$|Q(P)|=\sum _{k=2}^{N}2\left(\genfrac{}{}{0ex}{}{k}{2}\right)|G_{=k}(P)|.$$

After summation by parts this becomes

$$|Q(P)|=\sum _{k=2}^N(2k-2)|G_k(P)|.$$

Therefore it is enough to prove

$$|G_k(P)|\lesssim N^3{k}^{-2},2\le k\le N.$$

The logarithm in the final theorem comes exactly from summing

$$\sum _{k=2}^{N}k\cdot N^3{k}^{-2}\lesssim N^3\log N.$$

The Elekes-Sharir Transformation

For points $p,q\in {\mathbb{R}}^2$, define

$$S_{pq}=\{g\in G:g(p)=q\}.$$

This is a one-dimensional curve in the three-dimensional Lie group $G$. A motion $g$ lies in $G_k(P)$ if and only if it lies on at least $k$ of the curves

$$\{S_{pq}:p,q\in P\}.$$

Thus the partial-symmetry problem is an incidence problem between points of $G$ and curves in $G$.

Elekes and Sharir introduced this symmetry-group viewpoint and reduced the distinct-distance problem to a three-dimensional incidence problem (Elekes & Sharir, 2010). Guth and Katz use a particularly convenient coordinate chart in which the curves become lines.

Let $G^{\prime }\subset G$ be the non-translation motions. Each $g\in G^{\prime }$ has a unique fixed point $(x,y)$ and a rotation angle $\theta$ with

$$0<\theta <2\pi .$$

Define

$$\rho :G^{\prime }\to {\mathbb{R}}^3,\rho (x,y,\theta )=\left(x,y,\cot \frac{\theta }{2}\right).$$

If

$$p=(p_x,p_y),q=(q_x,q_y),$$

then $\rho (S_{pq}\cap G^{\prime })$ is the line

$$L_{pq}=\left(\frac{p_x+q_x}{2},\frac{p_y+q_y}{2},0\right)+t\left(\frac{q_y-p_y}{2},\frac{p_x-q_x}{2},1\right).$$

Let

$$\mathfrak{L}=\{L_{pq}:p,q\in P\}.$$

There are exactly $N^2$ distinct lines. A non-translation motion in $G_k(P)$ becomes a point of ${\mathbb{R}}^3$ incident to at least $k$ lines of $\mathfrak{L}$.

Translations are handled separately by an elementary argument. If a quadruple is assigned to a translation, then

$$p_3-p_1=p_4-p_2,$$

so $p_4$ is determined by $p_1,p_2,p_3$. Hence the translation part contributes at most $N^3$ quadruples and satisfies the same $N^3{k}^{-2}$ partial-symmetry bound.

Lines in Planes and Reguli

The line set $\mathfrak{L}$ is not arbitrary. It has crucial nonconcentration properties:

• no more than $N$ lines of $\mathfrak{L}$ lie in a single plane,
• no more than $O(N)$ lines of $\mathfrak{L}$ lie in a single regulus.

A regulus is a doubly ruled quadratic surface. A standard model is

$$z=xy.$$

It contains two one-parameter families of lines, and every line in one ruling intersects every line in the other ruling. If $N^2$ lines were allowed to concentrate in a single regulus, they could create on the order of $N^4$ two-line intersections, far too many for the desired estimate.

The plane bound is relatively direct. For fixed $p$, the $N$ lines

$$\{L_{pq}:q\in P\}$$

are pairwise skew and have distinct directions, so a plane cannot contain two of them. Summing over $p$ gives at most $N$ lines in any plane.

The regulus bound uses more geometry. For fixed $p$, extend the family to

$${\mathfrak{L}}_p^{\prime }=\{L_{pq}:q\in {\mathbb{R}}^2\}.$$

Guth and Katz show that if a regulus contains at least five lines from ${\mathfrak{L}}_p^{\prime }$, then one entire ruling of that regulus lies in ${\mathfrak{L}}_p^{\prime }$. Since a regulus has only two rulings, this can happen for at most two values of $p$. The remaining values of $p$ contribute only boundedly many lines each. Hence a regulus contains only $O(N)$ lines from $\mathfrak{L}$ (Guth & Katz, 2015).

This is where the geometry of the specific Elekes-Sharir lines matters. The final incidence theorem is false without excluding planar and regulus concentration.

The Incidence Theorem

The key incidence statement is:

Guth-Katz Line Incidence Estimate

Let $\mathfrak{L}$ be a set of $N^2$ lines in ${\mathbb{R}}^3$. Suppose no more than $N$ lines lie in a common plane and no more than $O(N)$ lines lie in a common regulus. For $2\le k\le N$, the number of points incident to at least $k$ lines of $\mathfrak{L}$ is

$$\lesssim N^3{k}^{-2}.$$

For $k\ge 3$, Guth and Katz prove a more flexible estimate. If $\mathfrak{L}$ is a set of $L$ lines in ${\mathbb{R}}^3$, no more than $B$ of them in any plane, and ${\mathfrak{S}}_k$ is the set of points incident to at least $k$ lines, then

$$|{\mathfrak{S}}_k|\le C\left(L^{3/2}{k}^{-2}+LB{k}^{-3}+L{k}^{-1}\right).$$

Taking $L=N^2$ and $B=N$ gives the desired

$$|{\mathfrak{S}}_k|\lesssim N^3{k}^{-2}$$

for $3\le k\le N$.

The case $k=2$ is separate. Two-line intersections are too common to be controlled by the same critical-point and flat-point arguments used for joints. Guth and Katz prove

$$|{\mathfrak{S}}_2|\lesssim N^3$$

under both the plane and regulus hypotheses by using ruled surfaces and the flecnode polynomial.

Polynomial Partitioning

Polynomial partitioning is the topological half of the proof. The input is the Stone—Tukey polynomial ham-sandwich theorem (Stone & Tukey, 1942).

Polynomial Partitioning

If $\mathfrak{S}$ is a finite set of $S$ points in ${\mathbb{R}}^n$ and $J\ge 1$, then there is a nonzero real polynomial $p$ of degree

$$d\lesssim 2^{J/n}$$

such that ${\mathbb{R}}^n\setminus Z(p)$ is a union of $2^J$ open cells, each containing at most $2^{-J}S$ points of $\mathfrak{S}$.

The proof repeatedly bisects finite point sets by polynomial hypersurfaces. At step $j$, one has $2^j$ sign classes from the previously chosen polynomials. A new polynomial bisects all these classes simultaneously. The product of the chosen polynomials defines the final partitioning surface.

In the incidence proof, one applies this to the set $\mathfrak{S}$ of $k$-rich points. There are two regimes.

In the cellular regime, many $k$-rich points lie in the open cells. A line not contained in $Z(p)$ crosses at most $d+1$ cells, so the average number of lines entering a full cell is controlled. Applying planar-type incidence estimates inside a cell and summing gives the desired bound.

In the algebraic regime, most $k$-rich points lie on $Z(p)$. If a line contains more points of $Z(p)$ than the degree of $p$, it must be contained in $Z(p)$. Under the uniformity hypotheses used in the proof, this forces a positive fraction of the lines to lie in a low-degree algebraic surface. One then analyzes critical and flat points of that surface. If too many incidences occur, many lines must concentrate in planar components, contradicting the plane-counting hypothesis unless the desired bound already holds.

This is the main new partitioning mechanism. Earlier polynomial-method arguments, such as Dvir’s finite-field Kakeya proof and the Guth-Katz joints theorem, were closer to pure vanishing arguments (Dvir, 2009; Guth & Katz, 2010; Elekes, Kaplan & Sharir, 2011; Kaplan, Sharir & Shustin, 2010). The distinct-distance proof needs both vanishing and spatial decomposition.

Ruled Surfaces and Flecnodes

The $k=2$ estimate requires a different tool because a point where two lines meet on a surface need not be singular or flat. The relevant obstruction is ruledness.

An algebraic surface $Z\subset {\mathbb{R}}^3$ is ruled if through every point of $Z$ there is a line contained in $Z$. Planes and reguli are the basic doubly ruled surfaces. Apart from planes and reguli, irreducible ruled surfaces are singly ruled: a generic point lies on exactly one generator line.

The classical detector for ruled surfaces is the flecnode polynomial. If

$$Z=\{p(x,y,z)=0\},$$

a flecnode is a point where some line has third-order contact with $Z$. Equivalently, for some nonzero direction $v$,

$$p=0,{\nabla }_{v}p=0,{\nabla }_v^{2}p=0,{\nabla }_v^{3}p=0.$$

Eliminating $v$ gives a polynomial

$$\mathrm{Fl}(p)$$

of controlled degree. Salmon’s theorem says that a surface is ruled precisely when the flecnode polynomial vanishes identically on it (Salmon, 1915).

Guth and Katz use this as follows. If a low-degree surface contains too many lines, then both $p$ and $\mathrm{Fl}(p)$ vanish on too many common lines. A Bezout-type lemma forces a common factor. That common factor cuts out a ruled component. Thus a large collection of lines in a low-degree surface forces ruled structure.

Once the ruled components are isolated, the plane and regulus exclusions become decisive. On a singly ruled surface, two generator lines rarely meet. Intersections are confined to a controlled exceptional set: critical points, exceptional lines, and a bounded number of additional degeneracies. Since planes and reguli cannot contain too many of the Elekes-Sharir lines, the total number of two-line intersections is $O(N^3)$.

Assembly of the Proof

The proof now closes formally.

First, the Elekes-Sharir coordinate transformation gives $N^2$ lines $\mathfrak{L}$ in ${\mathbb{R}}^3$, with at most $N$ lines in any plane and $O(N)$ in any regulus. The Guth-Katz incidence theorem gives

$$|G_k(P)|\lesssim N^3{k}^{-2}$$

for the non-translation motions. The translation motions satisfy the same estimate by the elementary vector equation

$$p_3-p_1=p_4-p_2.$$

Therefore

$$|G_k(P)|\lesssim N^3{k}^{-2}$$

for all $2\le k\le N$.

Second, substitute this into the partial-symmetry identity:

$$|Q(P)|=\sum _{k=2}^N(2k-2)|G_k(P)|\lesssim \sum _{k=2}^{N}k{N}^3{k}^{-2}\lesssim N^3\log N.$$

Finally, Cauchy’s inequality gives

$$|D(P)|\ge \frac{(N^2-N{)}^2}{|Q(P)|}\gtrsim \frac{N}{\log N}.$$

The logarithm is not an artifact of Cauchy’s inequality alone. It reflects the harmonic summation over possible sizes of partial symmetries. The square grid shows that many of these bounds are sharp up to constants within the framework (Guth & Katz, 2015).

Scope and Limitations

The theorem gives the correct power of $N$, but it does not prove Erdős’s conjectured

$$|D(P)|\gtrsim \frac{N}{\sqrt{\log N}}.$$

The square grid still separates the known lower bound from the expected optimum by a factor of $\sqrt{\log N}$.

The proof is strongly real-geometric. Polynomial partitioning uses topology through the ham-sandwich theorem, and the line-incidence estimates rely on real algebraic geometry. This matters: several Szemerédi—Trotter-type incidence statements fail over finite fields, where the whole ambient space can behave like a highly incident configuration (Szemerédi & Trotter, 1983).

The result is also specifically two-dimensional. In higher dimensions, the optimal order of the minimum number of distinct distances remains a different problem. The Elekes-Sharir reduction uses the three-dimensional group of orientation-preserving rigid motions of the plane and the fact that the relevant incidence objects become lines in ${\mathbb{R}}^3$.

Finally, the proof does not classify near-extremizers. The grid motivates the conjectured answer and appears in the sharpness discussion, but the theorem itself is a universal lower bound rather than a structural theorem for configurations with few distances.

Transferable Mechanisms

The first transferable mechanism is energy reduction. Instead of counting distinct values directly, count value-collisions and use Cauchy’s inequality to convert an upper bound for collisions into a lower bound for distinct values. This is the same broad principle behind additive energy in additive combinatorics, but here the energy is geometric and consists of equal-distance quadruples (Guth & Katz, 2015; Garibaldi, Iosevich & Senger, 2011).

The second mechanism is symmetry linearization. The hard combinatorial condition

$$|p_1-p_2|=|p_3-p_4|$$

is reinterpreted as the existence of a rigid motion sending one ordered segment to another. After choosing fixed-point coordinates, the curves $S_{pq}$ become lines. This is the crucial gain: a metric problem becomes a line-incidence problem (Elekes & Sharir, 2010; Guth & Katz, 2015).

The third mechanism is polynomial partitioning. A polynomial hypersurface gives a cell decomposition adapted to an arbitrary finite point set. The proof can then split into a cellular case, where crossing counts dominate, and an algebraic case, where many objects lie on a low-degree variety. This broad pattern became one of the central tools in incidence geometry after Guth-Katz (Stone & Tukey, 1942; Guth & Katz, 2015).

The fourth mechanism is obstruction isolation. Arbitrary collections of lines in ${\mathbb{R}}^3$ can have too many intersections because of planes and reguli. The Elekes-Sharir line family avoids these concentrations. The proof first identifies the dangerous algebraic surfaces, then uses problem-specific geometry to exclude them at the needed scale (Guth & Katz, 2015; Salmon, 1915).

The fifth mechanism is classical algebraic geometry as an incidence detector. The flecnode polynomial is not a modern combinatorial gadget; it is a nineteenth-century ruled-surface invariant. Guth and Katz use it exactly as a structural certificate: too many lines in a low-degree surface force ruledness, and ruledness forces a geometric classification (Salmon, 1915; Guth & Katz, 2015).

See Also

on lower bounds for incidences — The Guth-Katz proof is a foundational example of using incidence estimates to control an extremal configuration. Later point-tube and well-spaced incidence arguments refine the same broad philosophy in different geometric regimes.

on Heilbronn triangle problem — Both problems convert a geometric extremal question into an incidence problem, then separate the argument into concentration and nonconcentration cases.

on cap sets and the polynomial method — The cap-set proof and the Guth-Katz proof both use polynomials to constrain combinatorial configurations, but in distinct ways: finite-dimensional rank bounds in the cap-set problem and real polynomial partitioning plus algebraic surfaces in the distinct-distance problem.

References

🐻  Dvir, Z. 2009. On the size of Kakeya sets in finite fields. Journal of the American Mathematical Society 22(4), 1093–1097.

🐻  Elekes, G. & Sharir, M. 2010. Incidences in three dimensions and distinct distances in the plane. In Proceedings of the 26th Annual Symposium on Computational Geometry, pp. 413–422. , ACM.

🐻  Elekes, G., Kaplan, H. & Sharir, M. 2011. On lines, joints, and incidences in three dimensions. Journal of Combinatorial Theory, Series A 118(6), 962–977.

🐻  Erdős, P. 1946. On sets of distances of n points. The American Mathematical Monthly 53(5), 248–250.

🐻  Garibaldi, J., Iosevich, A. & Senger, S. 2011. The Erdős Distance Problem, American Mathematical Society,p.

🐻  Guth, L. & Katz, N.H. 2010. Algebraic methods in discrete analogs of the Kakeya problem. Advances in Mathematics 225(6), 2828–2839.

🐻  Guth, L. & Katz, N.H. 2015. On the Erdős distinct distances problem in the plane. Annals of Mathematics 181(1), 155–190.

🐻  Kaplan, H., Sharir, M. & Shustin, E. 2010. On lines and joints. Discrete & Computational Geometry 44(4), 838–843.

🐻  Salmon, G. 1915. A Treatise on the Analytic Geometry of Three Dimensions 5th ed.,p.

🐻  Stone, A.H. & Tukey, J.W. 1942. Generalized sandwich theorems. Duke Mathematical Journal 9(2), 356–359.

🐻  Szemerédi, E. & Trotter, W.T. 1983. Extremal problems in discrete geometry. Combinatorica 3(3–4), 381–392.