Distinct Consecutive Differences

Additive Combinatorics

Imre Ruzsa, József Solymosi, Endre Szemerédi, and I recently uploaded On distinct consecutive differences. We say {A = \{a_1 < \ldots < a_k\} \subset \mathbb{R}} is convex if for all {1 \leq i \leq k-2}, one has

\displaystyle a_{i+2} - a_{i+1} > a_{i+1}- a_{i}.

We also adopt Vinogradov’s asymptotic notation. The fundamental question in the area is the following. 

{\ } Conjecture 1 (Erdős): Suppose {A \subset \mathbb{R}} is convex. Then for any {\epsilon >0}, one has 

\displaystyle |A+A| \gg |A|^{2-\epsilon}. \ \ \ \spadesuit{\ }

Progress towards Conjecture 1 was originally made by Hegyvári, with significant improvements by several authors. There is a natural barrier in that for convex {A} 

\displaystyle |A+A| \gg |A|^{3/2},\ \ \ \ \ (1)

that was obtained by several methods. In the current work, we present one that allows of a generalization of indepedent interest. 

{\ } Theorem 1 (Distinct Consecutive differences): Let {A \subset \mathbb{R}} such that the consecutive differences are distinct. Let {B \subset \mathbb{R}} be arbitrary. Then 

\displaystyle |A+B| \gg |A| |B|^{1/2} .\ \ \ \spadesuit{\ }

Note that Theorem 1 immediately implies (1). It turns out that Theorem 1 is best possible, up to the constant. In the extremal construction we present, {A} and {B} have very different structure and so it is natural to ask if one can improve upon Theorem 1 in the case {B= A}. The proof is short and purely combinatorial, in a similar spirit to a proof of the Szemerédi-Trotter theorem for cartesian products found in these notes of Solymosi. 

We also provide a short proof that for convex {A}, 

\displaystyle |A+A-A| \gg |A|^2,

which is certainly implied by Conjecture 1. It is interesting to note that the proof is quite inflexible in that for each {x} we find one representation of 

\displaystyle x = a+ b - c, \ \ \ a,b,c \in A.

For instance, I do not see how to find {|A|^2} elements with at least 100 representations as {a+b-c}. 

We also present a proof of an improvement to (1). It is somewhat annoying that all improvements to (1) lead to quite small quantitive bounds. The interested reader should first see this short paper of Schoen and Shkredov, as well as this previous blog post and and this other previous blog post. I also have some informal notes on the spectral method of Shkredov, which I can distribute upon request.

Leave a Reply