Entropy-inequality method (Katz–Tardos): Shannon-entropy linear programming for the sums-and-entries / distinct-distances problem

Statement

The Katz–Tardos entropy-inequality method (N. H. Katz and G. Tardos, "A new entropy inequality for the Erdős distance problem," *Towards a Theory of Geometric Graphs*, Contemporary Mathematics 342, AMS, 2004, pp. 119–126) is a technique for proving lower bounds on the size of a sumset (or, more precisely, a "sums-and-entries" combinatorial object) by replacing an explicit combinatorial pigeonhole/counting argument with a linear program over Shannon-entropy inequalities.

The combinatorial target it bounds. Fix an $M\times k$ matrix $A$ with all $Mk$ entries distinct, and let $$S(A) := \{a_{ij}+a_{il} : j\neq l\}$$ be the set of pairwise sums of entries in the same row. Define $\mathrm{SE}(k,\alpha)$ to be the assertion $$M \ll \#S(A)^{\alpha}.$$ This "sums and entries problem" is a proxy for the Erdős distinct-distances problem: a set of $n$ points spanning few distinct distances forces many rows of an associated coordinate matrix to have equal pairwise sums (via the classical bisector/perpendicular-bisector reduction used already by Solymosi–Tóth and Tardos), so any bound $\mathrm{SE}(k_0,\alpha_0)$ translates mechanically into a distinct-distances lower bound of the shape $n^{c(\alpha_0)}$. Successive improvements to $\alpha_0$ (via $k=3,5,7,\dots$) trace the known lower-bound history: Solymosi–Tóth get the base case, Tardos's elementary pigeonhole argument gives $\mathrm{SE}(5,11/4)\Rightarrow n^{44/51}$, and the *elementary* (purely combinatorial, no entropy) Katz–Tardos pigeonhole argument pushes this to $\mathrm{SE}(5,19/7)\Rightarrow n^{19/22}\approx n^{0.8636}$.

The entropy-inequality step is what goes beyond the elementary argument. Instead of hand-crafting one more layer of "heavy/light row" pigeonholing for each larger $k$ (which becomes combinatorially unmanageable), Katz and Tardos:

1. Let $R$ be the random variable = a uniformly random row of $A$ (so $H(R)=\log N$ for $N$ rows). 2. For disjoint subsets $U,V\subseteq\{1,\dots,k\}$ define the pattern random variable $p_{U,V}(R)$ = the set of all sums $R_i+R_j$ ($i\in U,j\in V$) and all differences $R_i-R_j$ ($i,j$ both in $U$ or both in $V$), and its joint entropy $H(U,V):=H(p_{U,V}(R))$. 3. Basic Shannon-entropy facts pin down $H(U,V)$ at the extremes: $H(U,V)=0$ when $U=\varnothing,\ \#V=1$; $H(U,V)\le\log\#S(A)$ when $\#U=\#V=1,\ U\ne V$ (since patterns of size 1 live inside $S(A)$); $H(U,V)=\log N$ when $U\cap V\ne\varnothing$ (a nonempty overlap makes the pattern determine the whole row, since entries are distinct); and monotonicity $H(U,V)\le H(U',V')$ for $U\subseteq U',V\subseteq V'$. 4. The submodularity principle (Theorem 8.3 in Garibaldi–Iosevich–Senger, an entropy analogue of Shannon subadditivity/data-processing): if $X,Y$ jointly determine $A$ and each of $X,Y$ determine $B$, then $H(A)+H(B)\le H(X)+H(Y)$. Applied to unions/intersections of index sets this gives $H(U\cup U',V\cup V') + H(U\cap U',V\cap V') \le H(U,V)+H(U',V')$ whenever $(U\cap U')\cup(V\cap V')\ne\varnothing$. 5. Average $H(U,V)$ over all disjoint $(U,V)$ with $\#U=i,\#V=j$ to get normalized information averages $H_{i,j}$ (scaled by $1/\log N$), which then satisfy a small closed system of linear inequalities purely from the facts above: symmetry $H_{i,j}=H_{j,i}$, monotonicity $H_{i,j}\le H_{i+1,j}$, boundary value $H_{0,1}=1$, the key link $H_{1,1}\ge 1-\frac{\log\#S(A)}{\log N}$ (this is literally the statement $\mathrm{SE}(k,\alpha)$ rewritten in entropy terms), a discrete-convexity inequality $H_{i-1,j}+H_{i+1,j}\ge 2H_{i,j}$, and superadditivity $H_{i,j}\ge H_{i+1,j}+H_{i,j+1}$. 6. Solve the linear program: minimize/maximize $H_{1,1}$ (equivalently, the resulting bound $\alpha$) subject to this system, over all $i+j\le k$, letting $k\to\infty$. Using only facts (i)–(xii) already recovers $\mathrm{SE}(5,11/4)$; adding one further "lucky" submodularity-derived inequality (fact (xiii): $5H_{1,1}-H_{2,1}+2H_{3,0}\le 3$, itself proved by a small submodularity computation on pairs of rows sharing a 3-index pattern) and re-optimizing pushes the achievable exponent, in the $k\to\infty$ limit, to $$\alpha \to \frac{48-14e}{55-16e} \approx 0.864137,$$ where $e$ is the base of the natural logarithm — an artifact of the continuum/LP relaxation limit of the discrete system, not a combinatorial coincidence.

Headline consequence for the Erdős distance problem. Katz–Tardos (2004) obtain the (at time of writing, still record) lower bound $$\hat D(n) = \Omega\!\left(n^{(48-14e)/(55-16e)}\right) \approx \Omega(n^{0.864})$$ for the pinned distinct-distances function $\hat D(n) := \min_{|P|=n}\max_{p\in P}\#\{d(p,q):q\in P\}$ — i.e. some single point of any $n$-point planar set sees at least this many distinct distances (Sheffer, arXiv:1406.1949, "Problem 36"; erdosproblems.com/604). By repeatedly deleting the point realizing the maximum, the same bound gives $\hat D_\Sigma(n)=\Omega(n^{1.864})$ for the summed version (Sheffer, "Problem 37"). This exponent was, for over a decade, also the best known bound for the *unpinned* distinct-distances problem (before Guth–Katz's 2010/2015 polynomial-partitioning breakthrough, arXiv:1011.4105, gave $\Omega(n/\log n)$ for the unpinned count) — but Guth–Katz's method does not localize to a single pin (the Elekes–Sharir reduction it relies on aggregates incidences over all pins simultaneously), so the Katz–Tardos entropy bound remains, as of this writing, the best known lower bound for the still-open pinned problem Erdős #604 — pinned distinct-distances at a single point.

Facts

- The entropy-inequality argument is a strict refinement of the elementary Katz–Tardos combinatorial argument, not a separate proof: the elementary "heavy/light row" pigeonhole argument (bounding heavy numbers by $n^{3-\alpha}$ representations, then chaining differences of sums $s_{lm}(i)$ through octuples via repeated Cauchy–Schwarz/dyadic-pigeonhole) already gives $\mathrm{SE}(5,19/7)\Rightarrow n^{19/22}\approx0.8636$ *without* any explicit entropy — the entropy formalism is introduced precisely because pushing the elementary argument to $k=7,9,\dots$ by hand becomes intractable, while the entropy/LP formulation systematizes "which chain of pigeonhole steps is optimal" as a linear program that can be solved uniformly for all $k$ at once. - The gap between the elementary bound ($19/22\approx0.8636$) and the full entropy-LP bound ($(48-14e)/(55-16e)\approx0.8641$) is small in this instance but the *method* of getting there — replacing a finite sequence of ad hoc combinatorial steps with an LP over the full space of Shannon-type (submodularity/monotonicity) inequalities on a designed random variable — generalizes far beyond this one problem. - Ruzsa's construction gives a barrier: I. Ruzsa constructed, for every even $k$, a matrix example showing $\mathrm{SE}(k,\alpha)$ *fails* once $\alpha > \frac{k-2}{2k-1}\to \frac12$ as $k\to\infty$ in his normalization — an explicit demonstration that this entire "sums and entries" proof strategy (elementary or entropy-based) has an intrinsic ceiling and cannot, by itself, ever reach the full conjectured exponent $1-o(1)$ for the Erdős distance problem (Garibaldi–Iosevich–Senger, Ch. 7 §4, "Ruzsa's construction," pp. 78–79). - The technique long predates, and is mechanistically unrelated to, the later Elekes–Sharir–Guth–Katz polynomial-partitioning approach (see Elekes–Sharir(–Guth–Katz) reduction: distinct distances → point-line incidences in SE(2)): Katz–Tardos entropy stays entirely inside additive-combinatorics/information-theory (Shannon entropy of sums of matrix-row entries), while Elekes–Sharir–Guth–Katz reduces to point-line incidences in $SE(2)\subset\mathbb R^3$ via the polynomial method. They currently hold the record on *disjoint* sub-problems of the same parent question (Katz–Tardos: pinned/#604; Guth–Katz: unpinned/#89), and it is an open technical question whether the two can be composed (see Erdős #604 — pinned distinct-distances at a single point "Attack surface"). - Katz–Tardos's original 2004 paper is a chapter in an AMS Contemporary Mathematics conference volume (*Towards a Theory of Geometric Graphs*, ed. J. Pach) and is not posted on arXiv; the technique is transmitted primarily through the secondary/textbook exposition in Garibaldi–Iosevich–Senger's *The Erdős Distance Problem* (GSM 137, AMS) and cited verbatim (exponent, attribution) in Sheffer's 2014 survey (arXiv:1406.1949). - The general "replace a combinatorial cardinality bound by a Shannon-entropy bound on an auxiliary random variable, then exploit subadditivity/submodularity" idea is the same core mechanism used throughout entropy-method additive combinatorics (Tao's entropy Plünnecke–Ruzsa/Freiman theorems, Madiman's entropic sumset inequalities) — see the broader survey page Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) for that general family; this page is specifically the Katz–Tardos instance where the entropy inequalities are turned into an explicit finite/limiting linear program over normalized joint-entropy averages $H_{i,j}$ of row-patterns, which is the distinguishing technical signature of this particular method.

Technique

WHEN it applies: whenever a combinatorial lower bound reduces to showing that a matrix (or more generally a structured family of "rows"/tuples with distinct entries) cannot have too many rows relative to the size of a derived sumset/pattern set $S(A)$ — i.e. whenever the target has the shape $\mathrm{SE}(k,\alpha)$: "$M$ objects, each contributing $k$ distinguishable values, force at least $M^{1/\alpha}$-ish distinct pairwise sums." This shape recurs whenever a geometric/combinatorial hypothesis (e.g. "few distinct distances," "few distinct dot products," "few distinct sums of a Cartesian product") can first be linearized into an equal-sums-in-a-row condition on some auxiliary matrix via an algebraic reduction (perpendicular-bisector coordinates for distances; the analogous radial/dot-product reduction for the dot-products variant, see the Elekes–Sharir predecessor techniques and Elekes–Sharir(–Guth–Katz) reduction: distinct distances → point-line incidences in SE(2)).

WHY it works (the mechanism): - A chain of "pick a heavy/light row, average two determined quantities to pin down an entry, count representations" pigeonhole steps — the elementary Solymosi–Tóth/Tardos/Katz–Tardos argument — is *exactly* mirrored by a chain of Shannon-entropy submodularity/monotonicity inequalities on the joint entropies $H(U,V)$ of coordinate-subset "patterns" of a uniformly random row. Every combinatorial double-counting/averaging step used in the elementary proof (bounding the number of heavy numbers, bounding octuples via repeated dyadic pigeonholing) has a one-line translation into an entropy inequality (chain rule, subadditivity, or the submodularity principle, Theorem 8.3), because "number of representations/level-set size" is literally $\exp(H(\cdot))$ up to the max-entropy/uniform-distribution correspondence $\log|S|=H(\mathrm{Uniform}(S))$. - The payoff of doing this in entropy language rather than combinatorially is that the resulting inequalities are linear in the normalized averages $H_{i,j}$ (after averaging over all $\binom{s}{i}\binom{s-i}{j}$ choices of index subsets $U,V$ of size $i,j$), so instead of hand-designing a new combinatorial trick for every larger $k$, one writes down the *entire* family of valid linear (sub)entropy inequalities available at "order $k$" and lets linear programming find the best possible bound on $H_{1,1}$ (equivalently $\log\#S(A)$) that is *provable by any composition of these particular inequality types* — turning "keep inventing cleverer pigeonhole arguments" into "solve an LP whose optimum is a closed-form function of $k$," with the $k\to\infty$ limit computable analytically (giving the $e$-dependent closed form $(48-14e)/(55-16e)$). - This is a genuine example of the general entropy-method mechanism (see Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) Facts/Technique) — replace a finite set/count by the entropy of a uniform/auxiliary random variable so that flexible chain-rule/subadditivity manipulations become available — specialized here to a *linear-programming-solvable* closed system, which is what lets Katz–Tardos push strictly past what the elementary (non-LP) combinatorial argument could reach by hand.

How to actually use it to prove something (recipe): 1. Reduce your target combinatorial-geometry statement (e.g. "few distinct distances $\Rightarrow$ ...") to an instance of $\mathrm{SE}(k,\alpha)$: exhibit an $M\times k$ matrix of distinct entries (rows indexed by your objects, e.g. points/point-quadruples) whose row-pairwise-sums set $S(A)$ has size controlled by your target quantity. 2. Define $R$ = uniform random row; for all disjoint index-subset pairs $(U,V)$ define the pattern variable $p_{U,V}(R)$ and joint entropy $H(U,V)$. 3. Pin the entropy of the smallest/largest patterns using the *distinctness of entries* (gives $H(U,V)=\log N$ once $U\cap V\ne\varnothing$) and the *definition of $S(A)$* (gives $H(U,V)\le\log\#S(A)$ for singleton disjoint $U,V$). 4. Apply the submodularity principle (Theorem 8.3, an entropy version of Shannon subadditivity) to unions/intersections of these index sets to generate a family of linear inequalities on the normalized averages $H_{i,j}$; look for problem-specific "lucky" extra inequalities (as in fact (xiii)) by choosing a clever auxiliary random variable (e.g. a *non-uniformly weighted pair of rows* sharing a fixed sub-pattern) and applying submodularity to it — this is the creative step, analogous to choosing which combinatorial quantity to average in the elementary proof. 5. Solve the resulting LP for the best bound on $H_{1,1}$ (equivalently on $\alpha$ in $\mathrm{SE}(k,\alpha)$) as $k\to\infty$; translate back to the original geometric exponent via the problem-specific reduction from step 1. 6. Check against known barriers (e.g. Ruzsa's construction) to know whether the LP's ceiling is already the best this proof *strategy* can ever give, signaling that a genuinely different technique (e.g. polynomial partitioning) is needed to go further.

Related

- Entropy method — Shannon-entropy / coding-theoretic proof technique (Rao, Tao) — the general Shannon-entropy proof-technique family (Tao's entropy sumset/Freiman theorems, Rao's coding-theoretic sunflower proof, Shearer's lemma, entropy compression); this page is the Katz–Tardos-specific instance that turns entropy submodularity inequalities into an explicit linear program over row-pattern entropies. - Elekes–Sharir(–Guth–Katz) reduction: distinct distances → point-line incidences in SE(2) — the mechanistically unrelated later (2010–2015) technique that resolved the *unpinned* distinct-distances problem via point-line incidences in $SE(2)$; its non-localizing nature is exactly why the Katz–Tardos entropy bound remains the record for the pinned problem despite Elekes–Sharir–Guth–Katz's stronger unpinned result. - Erdős #604 — pinned distinct-distances at a single point — pinned distinct-distances conjecture; Katz–Tardos's $\Omega(n^{(48-14e)/(55-16e)})\approx\Omega(n^{0.864})$ is the still-standing (as of 2026) best known lower bound, unimproved since 2004. - Erdős #89 — distinct distances in the plane — the unpinned parent distinct-distances problem; Katz–Tardos's exponent was also the record here for over a decade before Guth–Katz's 2015 $\Omega(n/\log n)$, via a genuinely different technique. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — the incidence-geometry machinery (polynomial partitioning) that superseded Katz–Tardos for the unpinned problem but has not (yet) been composed with or adapted to reach the entropy method's pinned-problem territory.