Sum-difference exponents for boundedly many slopes, and rational complexity

New Nikodym set constructions over fi... Climbing the cosmic distance ladder: ...

Sum-difference exponents for boundedly many slopes, and rational complexity

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 {E} of ${{\bf R}^2}$ with some control on projections, such as

$\displaystyle |\{ a: (a,b) \in E \}| \leq N$

$\displaystyle |\{ b: (a,b) \in E \}| \leq N$

$\displaystyle |\{ a+b: (a,b) \in E \}| \leq N$

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 {(a,0)}

and

for every ${(a,b) \in E}$ , one gets a family of line segments whose set of directions has cardinality (1), but whose slices at heights {0,1,1/2}

have cardinality at most {N}

Because {a-b} is clearly determined by {a} and {b} , one can trivially get an upper bound of ${N^2}$ on (1). In 1999, Bourgain utilized what was then the very recent “Balog–Szemerédi–Gowers lemma” to improve this bound to ${N^{2-\frac{1}{13}}}$ , which gave a new lower bound of ${\frac{13d+12}{25}}$ on the (Minkowski) dimension of Kakeya sets in ${{\bf R}^d}$ , 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 ${N^{2-\frac{1}{14}}}$ , which gave Jean great satisfaction.) Currently, the best upper bound known for this quantity is ${N^{2-\frac{1}{6}}}$ .

One can get better bounds by adding more projections. For instance, if one also assumes

$\displaystyle |\{ a+2b: (a,b) \in E \}| \leq N$

then one can improve the upper bound for (1) to ${N^{2-\frac{1}{4}}}$ . The arithmetic Kakeya conjecture asserts that, by adding enough projections, one can get the exponent arbitrarily close to {1}

. 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 ${1.67513\dots}$ .

It was observed by Ruzsa that all of these questions can be equivalently formulated in terms of Shannon entropy. For instance, the upper bound ${N^{2-\frac{1}{6}}}$ of (1) turns out to be equivalent to the entropy inequality

$\displaystyle {\bf H}(X-Y) \leq (2-\frac{1}{6}) \max( {\bf H}(X), {\bf H}(Y) , {\bf H}(X+Y) )$

holding for all discrete random variables {X, Y}

(not necessarily independent) taking values in ${{\bf R}^2}$ . In the language of this paper, we write this as

$\displaystyle SD(\{0,1,\infty\}; -1) \leq 2-\frac{1}{6}.$

Similarly we have

$\displaystyle SD(\{0,1,2,\infty\}; -1) \leq 2-\frac{1}{4}.$

As part of the AlphaEvolve experiments, we directed this tool to obtain lower bounds for ${SD(\{0,1,\infty\}; \frac{a}{b})}$ for various rational numbers ${\frac{a}{b}}$ , defined as the best constant in the inequality

$\displaystyle {\bf H}(X+\frac{a}{b} Y) \leq SD(\{0,1,\infty\}; \frac{a}{b}) \max( {\bf H}(X), {\bf H}(Y) , {\bf H}(X+Y) ).$

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 {2}

as ${a+b \rightarrow \infty}$ :

The first main result of this paper is to confirm that this is indeed the case, in that

$\displaystyle 2 - \frac{c_2}{\log(2+|a|+|b|)} \leq SD(\{0,1,\infty\}; \frac{a}{b}) \leq 2 - \frac{c_1}{\log(2+|a|+|b|)}$

whenever

is in lowest terms and not equal to ${0, 1, \infty}$ , where ${c_1,c_2>0}$ 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 {a,b}

. 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 ${0,1,\infty}$ projections. If one also controls projections ${X + r_i Y}$ for various rationals ${r_1,\dots,r_k}$ and {R} denotes the set of slopes of the projections under control, then it turns out that the associated sum-difference constant ${SD(\{0,1,\infty,r_1,\dots,r_k\}; s)}$ still decays to {2} , but now the key parameter is not the height {|a|+|b|} of {s} , but rather what I call the rational complexity of {s} with respect to {R} , defined as the smallest integer {D} for which one can write {s} as a ratio ${P(r_1,\dots,r_k)/Q(r_1,\dots,r_k)}$ where {P,Q} are integer-coefficient polynomials of degree at most {D} and coefficients at most ${2^D}$ . Specifically, ${SD(\{0,1,\infty,r_1,\dots,r_k\}; s)}$ decays to {2} at a polynomial rate in {D} , 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 {X, Y, X+Y} , and ${X+r_i Y}$ to control of {X+sY} .

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 {2} , rather than close to {1} ), it does highlight the fact that these constants are extremely arithmetic in nature, in that the influence of projections ${X+r_iY}$ on {X+sY} is highly dependent on how efficiently one can represent {s} as a rational combination of the ${r_i}$ .