TejasviTomar
October 2026 · Preprint

Certified upper bounds for two sum-difference exponents

Tejasvi Singh Tomar

In plain words

Katz and Tao proved in 1999 that if two sets of numbers have at most N members each, and some pairs, one from each set, give at most N distinct sums, those pairs give at most N to the power 11/6 distinct differences; Bourgain linked such bounds to the Kakeya problem. One new proof lowers 11/6 to 1.8273, improving the exponent recorded for an Erdős problem; another, through Kleinwaks' transfer theorem, lowers his bound 1.3124 for a related constant of Gyarmati, Hennecart and Ruzsa to 1.2970. The main bounds are checked in Lean.

Abstract

For finite sets A, B of real numbers and G ⊆ A × B, Katz and Tao proved in 1999 that {a − b : (a, b) ∈ G} has at most N11/6 elements whenever A, B and {a + b : (a, b) ∈ G} have at most N elements. We lower the exponent 11/6 to 1.827297. Without non-Shannon inequalities we obtain the exponent 1.829429, but this exponent is valid in all abelian groups. We also prove |X − Y| ≤ |X + Y|1.422300 for all finite sets X, Y of integers. This improves the exponent 1.4543 of Kleinwaks, and through his transfer theorem it lowers the upper bound for the sum-difference constant of Gyarmati, Hennecart and Ruzsa from 1.3124 to 1.296914. Both proofs establish entropy inequalities for a random pair. We construct several copies of the pair on a common probability space, glued by the copy lemma for the first problem and independent for the second, and use cross forms, which are integer combinations of coordinates of different copies. With rational weights found by linear programming, we combine Shannon inequalities among the joint entropies of these forms and, for the first problem, also non-Shannon inequalities that we prove from the copy lemma. For each bound, a checker recomputes the inequalities from their definitions and verifies the combination in exact rational arithmetic, and a second checker confirms the result. The proofs of the exponents 1.827297 and 1.422300 and of the bound 1.296914 have also been checked in the Lean 4 proof assistant.

Three horizontal black lines. The top and bottom lines each carry a row of 24 evenly spaced yellow dots, and the middle line carries 7 yellow dots close together at its centre. Thin teal segments join dots on the bottom line to dots on the top line, each passing through one of the 7 central dots, so that they form an hourglass of crossing lines fanning out in many directions.
Illustration of the question. Each segment stands for a pair (a, b), drawn from a on the bottom line to b on the top line; it crosses the middle line at (a + b)/2, so the crossing points correspond to the distinct sums of the pairs, and its direction is set by the difference b − a. In this example both sets are the numbers 0 to 23 and the pairs are those with sums from 20 to 26: 156 segments, 24 points on each outer line, 7 crossing points and 47 directions. Katz and Tao proved that when the three lines hold at most N points each, there are at most N to the power 11/6 directions; the paper lowers the exponent to 1.8272963. Bourgain linked such bounds to Kakeya sets, which contain a unit segment in every direction.