Elekes–Sharir(–Guth–Katz) reduction: distinct distances → point-line incidences in SE(2)

Statement

The Elekes–Sharir framework (Elekes & Sharir, "Incidences in three dimensions and distinct distances in the plane," arXiv:1005.0982, publ. *Combin. Probab. Comput.* 20(4) (2011) 571–608) is a reduction, "in the spirit of the Erlangen program," that converts a distance-counting problem on a planar point set $P$, $|P|=n$, into a point-line (or point-curve) incidence problem inside the group $SE(2)$ of orientation-preserving rigid motions of the plane, viewed as a 3-dimensional parameter space.

Core algebraic fact. A 4-tuple $(a,p,b,q)\in P^4$ has $|ap|=|bq|>0$ if and only if there exists a proper rigid motion (rotation + translation) $\tau\in SE(2)$ with $\tau(a)=b,\ \tau(p)=q$. So counting equal-length segment pairs is equivalent to counting rigid motions that simultaneously map one ordered pair of points to another.

Parametrization (Guth–Katz's linearizing coordinates, arXiv:1011.4105; also terrytao.wordpress.com/2011/03/05). Every orientation-preserving rigid motion that is a rotation by angle $\theta\ (|\theta|<\pi)$ about center $P=(o_x,o_y)$ is identified with the point $$(o_x,\ o_y,\ \cot(\theta/2))\ \in\ \mathbb R^3;$$ pure translations are sent to points "at infinity," so the identification is with a dense subset of $SE(2)$. For two fixed points $A,B\in\mathbb R^2$, the set of rigid motions taking $A\mapsto B$, $$\ell_{AB} := \{\tau\in SE(2) : \tau(A)=B\},$$ is a line in this $\mathbb R^3$ parametrization: elementary trigonometry shows the rotation center $P$ of any $\tau\in\ell_{AB}$ must lie on the perpendicular bisector of $AB$, and $P$ depends linearly on $\cot(\theta/2)$ (Tao, loc. cit.) — so the whole locus $\ell_{AB}$ is a straight line, not merely a curve.

Consequence. $(a,p,b,q)\in Q:=\{(a,p,b,q)\in P^4 : |ap|=|bq|>0\}$ exactly when the lines $\ell_{ab}$ and $\ell_{pq}$ (both in the $O(n^2)$-line family induced by all ordered pairs of $P$) intersect in $\mathbb R^3$ — the common point is the rigid motion witnessing $\tau(a)=b,\tau(p)=q$. Thus $$|Q| = \#\{\text{incidences between } n^2 \text{ points/pairs realized as } \Theta(n^2) \text{ lines in } \mathbb R^3\}\quad(\text{up to bookkeeping}),$$ and bounding $|Q|$ from above via an incidence theorem, combined with a Cauchy–Schwarz lower bound relating $|Q|$ to the number $x$ of distinct distances, yields a lower bound on $x$.

Historical nuance (important for correct citation). Elekes and Sharir's *original* 2010/2011 reduction (arXiv:1005.0982) mapped rigid motions to helices or parabolas in $\mathbb R^3$ (a more naive, non-linearized parametrization) and only obtained the incidence bound $O(s^3/k^{12/7})$ on rotations taking $\ge k$ points of an $s$-point set to $k$ others — enough to conjecture, but not prove, the sharp $\Omega(n/\log n)$ target (they explicitly conjectured the sharp companion bound $O(s^3/k^2)$, noting it "would imply the lower bound $\Omega(s/\log s)$"). Guth and Katz's contribution (2010/2015, arXiv:1011.4105) was to find the $\cot(\theta/2)$ coordinate that linearizes the curves into genuine straight lines — turning the incidence problem into the far more tractable "how many intersection points can $\Theta(n^2)$ lines in $\mathbb R^3$ have" — and then to prove the needed line-incidence bound via the polynomial method. The combined technique is accordingly sometimes called the Elekes–Sharir–Guth–Katz framework (see the *Polynomial Methods and Incidence Theory* textbook, Ch. 7, "The Elekes–Sharir–Guth–Katz Framework"). The Sharir survey "On Distinct Distances and Incidences: Elekes's Transformation and the New Algebraic Developments" further records that the underlying transformation idea is due to Elekes alone circa 2000, lay dormant roughly a decade "mainly because of the lack of effective tools for tackling the incidence problem," and was only completed once Guth–Katz's 2010 polynomial-partitioning breakthrough on the joints problem supplied those tools.

Facts

- Double-counting step (Cauchy–Schwarz), exact form (adamsheffer.wordpress.com/2013/05/25, reproducing Elekes–Sharir/Guth–Katz's argument): partition $P^2\setminus\{(u,u):u\in P\}$ into $x$ distance classes $E_1,\dots,E_x$ by distinct distance value, $|E_i|=m_i$, $\sum_i m_i = n^2-n$. Then $|Q| = \sum_i m_i^2 \ge \left(\sum_i m_i\right)^2/x = (n^2-n)^2/x$ by Cauchy–Schwarz (Sheffer's blog states the closely related sharpened form $|Q|\ge (n^2-n-x)^2/x$, accounting for the trivial diagonal quadruples $a=b,p=q$). So any upper bound $|Q|=O(f(n))$ immediately gives $x = \Omega(n^4/f(n))$ — this is the mechanical engine that turns a line-incidence bound into a distinct-distances lower bound. - The line-incidence bound needed. The $n(n-1)$ ordered pairs of $P$ give $\Theta(n^2)$ lines $\ell_{ab}$ in $\mathbb R^3$ (via the parametrization above). $|Q|$ equals (up to constant factors and bookkeeping for multiplicity/parallel lines) the number of intersecting pairs among these $\Theta(n^2)$ lines. A trivial bound (any two of $\Theta(n^2)$ lines might meet) gives only $|Q|=O(n^4)$, hence $x=\Omega(1)$ — useless. The whole difficulty of the Guth–Katz theorem is proving a much better bound, $|Q| = O(n^3\log n)$, which by the Cauchy–Schwarz step above gives the sharp $x=\Omega(n/\log n)$. - Why generic line-incidence bounds (e.g. Szemerédi–Trotter in $\mathbb R^3$) don't immediately work: $\Theta(n^2)$ lines in $\mathbb R^3$ could in principle all lie in a common plane, where Szemerédi–Trotter-type bounds only give $O(n^{8/3})$ incidences — far too weak, and also would only need to be beaten, not the generic case. The structural fact that rescues the argument (Guth–Katz, arXiv:1011.4105, proved via the flecnode polynomial — see Flecnode polynomial / ruled-surface geometry (G. Salmon)) is that no plane or regulus (doubly-ruled quadric surface) can contain more than $O(n)$ of the $\ell_{ab}$ lines — because too many coplanar/co-reguli lines among the $\ell_{ab}$ would force a degenerate (e.g. collinear or co-circular) structure on $P$ itself, contradicting genericity or reducible to easier cases. This "few lines per plane/regulus" property is exactly the extra input the polynomial-partitioning method (cell decomposition via the polynomial ham-sandwich theorem, applied to points with many incident lines, plus flecnode-polynomial/ruled-surface analysis for points with only two incident lines) is built to exploit, turning the naive $O(n^4)$ into $O(n^3\log n)$. - The framework only reduces the problem — it does not by itself solve it. Elekes–Sharir supply the reduction (points/pairs ↦ lines in $SE(2)\cong\mathbb R^3$ ↦ incidences) and the weaker $O(s^3/k^{12/7})$ incidence bound; Guth–Katz supply (a) the linearizing $\cot(\theta/2)$ coordinate that makes the curves into lines, and (b) the actual sharp incidence bound via the polynomial method. Both halves are needed for the final $\Omega(n/\log n)$ theorem. - Only the multiplicative constant/log-power is open, not the exponent: Guth–Katz's $\Omega(n/\log n)$ is one $\sqrt{\log n}$ factor short of the fully conjectured $\Omega(n/\sqrt{\log n})$ (see Erdős #89 — distinct distances in the plane); no further improvement via this framework has appeared through 2026 (checked via arXiv scan, see erdos/89.md provenance). - Localization failure: the incidence bound produced by this framework is a *global* count over all $\Theta(n^2)$ line-pairs at once; it does not localize to show that some *single* point $x\in P$ alone realizes almost all the distinct distances. This is exactly why the "pinned" strengthening Erdős #604 — pinned distinct-distances at a single point remains stuck at the pre-2015 Katz–Tardos entropy-method bound $\Omega(n^{0.8641\ldots})$ even though the unpinned problem Erdős #89 — distinct distances in the plane is essentially settled by this same framework — a genuine, named technique-transfer gap. - Finite-field / $\mathbb F_q$ analogue exists: the group $SF(2,q)$ of "positively oriented rigid motions" over $\mathbb F_q^2$ plays the role of $SE(2)$, and the same quadruple/incidence paradigm has been carried out for three-point configurations over finite fields (arXiv:1201.5039, "Three-point configurations determined by subsets of $\mathbb F_q^2$ via the Elekes-Sharir paradigm") — evidence the framework is a genuinely portable reduction template, not merely a one-off trick for $\mathbb R^2$.

Technique

Recombination-ready recipe — how to apply the Elekes–Sharir reduction to a new congruence/rigid-motion-counting problem:

1. Recognize the target as a "congruent-configuration-counting" problem. You need a statement of the shape: "how many pairs (or $k$-tuples) of point-configurations in $\mathbb R^2$ are related by a rigid motion / similarity / other low-dimensional transformation group element?" Distinct distances is the $k=2$ case (pairs $(a,p)$, $(b,q)$ with $|ap|=|bq|$, witnessed by *some* $\tau\in SE(2)$ with $\tau(a,p)=(b,q)$); the same paradigm has been used for congruent triangles, repeated/few distinct distances among $k$-point patterns, and (via $SF(2,q)$) finite-field three-point configurations. 2. Parametrize the transformation group as a low-dimensional real (or finite-field) algebraic variety. For $SE(2)$ this is the 3-dimensional space of (rotation-center, angle) pairs. The key technical move is finding coordinates in which the relevant "moves-$A$-to-$B$" loci become the lowest possible algebraic degree (Guth–Katz's insight: use $\cot(\theta/2)$, not $\theta$ or $(\cos\theta,\sin\theta)$ directly, to get straight *lines* rather than helices/conics) — this single coordinate choice is what separates the original Elekes–Sharir $O(s^3/k^{12/7})$ bound from the sharp Guth–Katz result. 3. Build the "moves $u$ to $v$" locus $\ell_{uv}$ for every relevant ordered pair $(u,v)$ of your point configuration, giving a family of $\Theta(n^2)$ (or $\Theta(n^k)$) curves/lines in the parameter space. 4. Translate the counting target into an incidence-counting problem: two data points $(u,v)$ and $(u',v')$ satisfy your target relation iff $\ell_{uv}$ and $\ell_{u'v'}$ intersect — so the number of relation-instances equals the number of intersecting line/curve pairs (an incidence count), which off-the-shelf incidence machinery (Szemerédi–Trotter in low dimensions, or the polynomial method / polynomial partitioning in $\mathbb R^3$ and above, see Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt)) can attack. 5. Rule out the degenerate configurations (many lines coplanar / co-regulus / concurrent) that would blow up the incidence count — typically via an algebraic argument (flecnode polynomial + ruled-surface classification in the Guth–Katz case) showing degeneracy of the transformation-space curves forces degeneracy back in the original point set, which can be handled as an easy separate case. 6. Close the loop with a Cauchy–Schwarz (or other convexity) double-count: relate the raw incidence count $|Q|$ to the quantity you actually want (e.g. number of distinct distances $x$) via $|Q|\ge(\text{total pairs})^2/x$, then substitute the incidence upper bound for $|Q|$ and solve for $x$.

WHEN it applies: problems phrased as counting how many pairs/tuples of a finite planar point set are related by *some* element of a fixed low-dimensional Lie group of plane transformations (rigid motions, similarities) — i.e., any "how many times can a fixed local pattern of relation X recur among $n$ points" question where X is expressible as "$\exists\, \tau$ in a $\le 3$-real-dimensional transformation group with $\tau(\text{tuple}_1)=\text{tuple}_2$." Classic instances: distinct/repeated distances (Erdős #89 — distinct distances in the plane, Erdős #604 — pinned distinct-distances at a single point, Erdős #661 — bipartite distinct-distances o(n/√log n) question is OPEN ($50); the underlying two-set function D(m,n) is SOLVED up to a log factor (Elekes construction 1995/1999, matching lower bounds by Mathialagan 2019)), and (via the $\mathbb F_q$ analogue) finite-field point-configuration counting.

WHY it works (the mechanism, for recombination): it is an instance of the general "Erlangen program" move — replace a geometric equivalence relation among configurations (here: "congruent," i.e. related by an isometry) with the group of transformations realizing it, then study *that group as a geometric object in its own right*. Because $SE(2)$ is itself only 3-dimensional, the space of "motions taking $A$ to $B$" for fixed $A,B$ collapses to a *curve* (here, with the right coordinates, a *line*) rather than a higher-dimensional set — this dimension collapse is exactly what turns an a priori $4$-fold ($P^4$) counting problem into a 3-dimensional incidence problem tractable by 2010s incidence-geometry technology (polynomial partitioning). The framework is powerful precisely because (a) the transformation group is low-dimensional so incidence theory applies, and (b) a cheap convexity inequality (Cauchy–Schwarz) converts *any* incidence upper bound into a distinct-value lower bound "for free" — meaning all the hard work is concentrated into a single, reusable incidence-theoretic sub-problem, and any future improvement to that sub-problem (e.g. closing the $\sqrt{\log n}$ gap in Erdős #89 — distinct distances in the plane) automatically improves the geometric conclusion with no further conceptual work.

Related

- Erdős #89 — distinct distances in the plane — Erdős distinct distances in the plane; this framework, combined with Guth–Katz's polynomial-method incidence bound, gives the near-tight $\Omega(n/\log n)$ answer, one $\sqrt{\log n}$ factor short of the $\Omega(n/\sqrt{\log n})$ conjecture. - Erdős #604 — pinned distinct-distances at a single point — pinned distinct distances (stronger, still-open form); the reduction's *global* (non-localizing) nature is the concrete, named reason this framework's success on #89 has not transferred here, leaving the older Katz–Tardos entropy bound $n^{0.8641\ldots}$ as the record. - Erdős #661 — bipartite distinct-distances o(n/√log n) question is OPEN ($50); the underlying two-set function D(m,n) is SOLVED up to a log factor (Elekes construction 1995/1999, matching lower bounds by Mathialagan 2019) — bipartite/two-point-set distinct-distances variant, same underlying incidence machinery, still open. - Erdős #1083 — distinct distances in R^d (d≥3) is OPEN; the solved d=2 case (#89, Guth–Katz) is the literal numerical input to every known partial bound, via Solymosi–Vu's dimension-reduction recursion — higher-dimensional distinct-distances generalization; cites this framework's neighborhood. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — supplies the actual incidence bound (cell decomposition via the polynomial ham-sandwich theorem) that this framework's reduction needs as its second half; the two techniques are historically and logically inseparable in the Guth–Katz proof. - Flecnode polynomial / ruled-surface geometry (G. Salmon) — G. Salmon's 19th-century algebraic tool Guth–Katz use to bound points where only two $\ell_{ab}$-lines meet, and to establish the "$O(n)$ lines per plane/regulus" property this reduction's incidence bound depends on. - Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — Katz–Tardos's earlier (2004), mechanistically distinct entropy-inequality technique, still the record holder exactly where this framework's reduction fails to localize (#604).