We also adopt Vinogradov’s asymptotic notation. The fundamental question in the area is the following.
Conjecture 1 (Erdős): Suppose is convex. Then for any , one has
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
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 such that the consecutive differences are distinct. Let be arbitrary. Then
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, and have very different structure and so it is natural to ask if one can improve upon Theorem 1 in the case . 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 ,
which is certainly implied by Conjecture 1. It is interesting to note that the proof is quite inflexible in that for each we find one representation of
For instance, I do not see how to find elements with at least 100 representations as .
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.