I have uploaded to the arXiv my paper “Sum-difference exponents for boundedly many slopes, and rational complexity“. This is the second spinoff of my previous project with Bogdan Georgiev, Javier Gómez–Serrano, and Adam Zsolt Wagner that I recently posted about. One of the many problems we experimented using the AlphaEvolve tool with was that of computing sum-difference constants. While AlphaEvolve did modest improve one of the known lower bounds on sum-difference constants, it also revealed an asymptotic behavior to these constants that had not been previously observed, which I then gave a rigorous demonstration of in this paper.
In the original formulation of the sum-difference problem, one is given a finite subset 
of 
with some control on projections, such as
and one then asks to obtain upper bounds on the quantity
This is related to Kakeya sets because if one joins a line segment between 
and 
for every 
, one gets a family of line segments whose set of directions has cardinality (1), but whose slices at heights 
have cardinality at most 
.
Because 
is clearly determined by 
and 
, one can trivially get an upper bound of 
on (1). In 1999, Bourgain utilized what was then the very recent “Balog–Szemerédi–Gowers lemma” to improve this bound to 
, which gave a new lower bound of 
on the (Minkowski) dimension of Kakeya sets in 
, which improved upon the previous bounds of Tom Wolff in high dimensions. (A side note: Bourgain challenged Tom to also obtain a result of this form, but when they compared notes, Tom obtained the slightly weaker bound of 
, which gave Jean great satisfaction.) Currently, the best upper bound known for this quantity is 
.
One can get better bounds by adding more projections. For instance, if one also assumes
then one can improve the upper bound for (1) to 
. The arithmetic Kakeya conjecture asserts that, by adding enough projections, one can get the exponent arbitrarily close to 
. If one could achieve this, this would imply the Kakeya conjecture in all dimensions. Unfortunately, even with arbitrarily many projections, the best exponent we can reach asymptotically is 
.
It was observed by Ruzsa that all of these questions can be equivalently formulated in terms of Shannon entropy. For instance, the upper bound of (1) turns out to be equivalent to the entropy inequality
holding for all discrete random variables 
(not necessarily independent) taking values in . In the language of this paper, we write this as
Similarly we have
As part of the AlphaEvolve experiments, we directed this tool to obtain lower bounds for 
for various rational numbers 
, defined as the best constant in the inequality
We did not figure out a way for AlphaEvolve to efficiently establish upper bounds on these quantities, so the bounds provided by AlphaEvolve were of unknown accuracy. Nevertheless, they were sufficient to give a strong indication that these constants decayed logarithmically to 
as 
:
The first main result of this paper is to confirm that this is indeed the case, in that
whenever 
is in lowest terms and not equal to 
, where 
are absolute constants. The lower bound was obtained by observing the shape of the examples produced by AlphaEvolve, which resembled a discrete Gaussian on a certain lattice determined by 
. The upper bound was established by an application of the “entropic Plünnecke–Ruzsa calculus”, relying particularly on the entropic Ruzsa triangle inequality, the entropic Balog–Szemerédi–Gowers lemma, as well as an entropy form of an inequality of Bukh.
The arguments also apply to settings where there are more projections under control than just the 
projections. If one also controls projections 
for various rationals 
and 
denotes the set of slopes of the projections under control, then it turns out that the associated sum-difference constant 
still decays to , but now the key parameter is not the height 
of 
, but rather what I call the rational complexity of with respect to , defined as the smallest integer 
for which one can write as a ratio 
where 
are integer-coefficient polynomials of degree at most and coefficients at most 
. Specifically, decays to at a polynomial rate in , although I was not able to pin down the exponent of this decay exactly. The concept of rational complexity may seem somewhat artificial, but it roughly speaking measures how difficult it is to use the entropic Plünnecke–Ruzsa calculus to pass from control of 
, and 
to control of 
.
While this work does not make noticeable advances towards the arithmetic Kakeya conjecture (we only consider regimes where the sum-difference constant is close to , rather than close to ), it does highlight the fact that these constants are extremely arithmetic in nature, in that the influence of projections 
on is highly dependent on how efficiently one can represent as a rational combination of the 
.
