3
$\begingroup$

Let A be a finite subset of $\mathbb{N}$, $\mathbb{R}$, or a sufficiently small subset of $\mathbb{F}_{p}$.

Do we have a lower bound of the form $|A|^{1+\delta}$ on the following quantity:

$$\max (|\{a+b : a,b \in A\}|, |\{a^2+b^2 : a,b \in A\}| ) ? $$

In other words, is either the sumset of $A$ or the sumset of the square set of $A$ guaranteed to be large?

This is very similar to the sum-product problem (which is formally connected to the variant question of lower bounding $\max(|2A|, |2A^2|)$). My hope is that this problem might be easier than the sum-product problem and better bounds may be available.

$\endgroup$
1

3 Answers 3

6
$\begingroup$

A more general result than what you want appears as Theorem 1 in http://arxiv.org/pdf/1002.2554. (A slightly weaker result had appeared before as Theorem 3.1 in http://arxiv.org/pdf/0909.5471).

Curiously, it is open if at least one of $A^2+A^2$ and $A^3+A^3$ is necessarily large.

$\endgroup$
9
  • $\begingroup$ Thank you, Boris! This addresses the finite field case. Unfortunately, the exponents are worse than what is currently known for the sum-product problem, however. $\endgroup$
    – Mark Lewko
    Sep 6, 2015 at 17:11
  • $\begingroup$ @MarkLewko The problem with the exponents is that we have exactly one proof technique for proving sum-product-type estimates for small sets in finite fields, and this proof technique is quite wasteful. However, I do not know of any applications where the numeric exponents make qualitative difference (unless one somehow would able to prove the sharp exponents, which we currently cannot). If in your application the exponents do matter, I would be very interested. $\endgroup$
    – Boris Bukh
    Sep 6, 2015 at 17:17
  • $\begingroup$ @MarkLewko The result in $\mathbb{R}$ is available with better exponents. See Corollary 3.2 in ams.org/mathscinet-getitem?mr=1772612. By the general algebro-geometric nonsense, a bound in $\mathbb{F}_p$ automatically implies the same bound in $\mathbb{C}$. $\endgroup$
    – Boris Bukh
    Sep 6, 2015 at 17:26
  • $\begingroup$ I'm not sure I'd agree we only have one proof technique now. See the recent paper of Roche-Newton, Rudnev and Shkredov which derives sum-product estimates from an incidence bound which is proved via the polynomial method. This strikes me as quite different than the initial approach. My application was to try to improve / give an alternate / more robust / more general approach to some results which are based on sum-product estimates. It might be interesting to check if expansion estimates of this form could be used to deduce incidence estimates for curves which I believe is open in F_p. $\endgroup$
    – Mark Lewko
    Sep 6, 2015 at 17:28
  • 1
    $\begingroup$ @OliverRoche-Newton Since the method of Elekes-Nathanson-Ruzsa gives a lower bound for $\max\{|B+B|, |B^{3/2}+B^{3/2}\}$, taking $B=A^2$ might say something about the question of $A^2+A^2$ vs $A^3+A^3$ (over $\mathbb{R}$ at least). $\endgroup$ Oct 8, 2015 at 16:20
12
$\begingroup$

Six years later it's hard to know if this is still a question of interest. For the record (since I stumbled across the question), the answer is yes and it's a consequence of a more general phenomenon.

The main theorem of the paper of Stevens and Warren (Thm 5 in https://arxiv.org/abs/2102.05446) states that for any convex (or concave) functions $f, g:\mathbb{R}\rightarrow \mathbb{R}$ we have $$ |A+B|^{38}|f(A)+g(B)|^{38} \gtrsim |A|^{49}|B|^{49} $$ where $\gtrsim$ hides factors of $\log(|A|)$.

Then the answer to the original question follows by setting $A = B$ and $f = g$ with $f(x) = x^2$. This gives, with $S = \{a^2 : a \in A\}$ $$ \max\{|A+A|,|S+S|\} \gtrsim |A|^{49/38} $$ i.e. an exponent of $1.28947\ldots$

$\endgroup$
0
$\begingroup$

I believe I can make some progress in the real case using a variant of Elekes' approach to the sum-product problem based on the Szemeredi-Trotter theorem for unit paraboloids.

Let $A$ be a finite set of real numbers and $S = \{a^2 : a \in A\}$.

Consider the subset $B \subset \mathbb{R}^2$ given by

$$(a+b, c^2+d^2 : a,b,c,d \in A).$$

Clearly $|B| = |A+A| \times |S+S| $. Now for a given pair $u,v \in \mathbb{R}$ define the paraboloid $p_{(u,v)}$ to be the set of solutions to the equation

$$y= (x-u)^2 + v^2.$$

Now each such paraboloid will contain at least $|A|$ points from $B$, namely the points of the form

$$ (u+a, a^2+v^2)$$

where $a$ varies over $A$ and $u$ and $v$ are fixed (depending on $p_{(u,v)}$). Let $L=\{p_{(u,v)} : u,v \in A \} $ denote the set of parabolas generate as described above, we must have

$$|I(B,L)| \geq |A|^3 $$

On the other hand, by the Szemeredi-Trotter theorem (for "unit" paraboloids), we have

$$|A|^3 \leq |I(B,L)| \lesssim |A+A|^{2/3} |S+S|^{2/3} |A|^{4/3} + |A+A||S+S| + |A|^2$$

which implies $|A|^{5/2}\lesssim |A+A| \times |S+S|$. This, in turn, implies that

$$|A|^{5/4} \leq \max(|A+A|,|S+S|).$$

$\endgroup$
2
  • $\begingroup$ This appears to be a special case of Corollary 3.2 of the Elekes-Nathanson-Ruzsa result linked in Boris's comment: ams.org/mathscinet-getitem?mr=1772612 $\endgroup$
    – Terry Tao
    Sep 6, 2015 at 20:41
  • 1
    $\begingroup$ Theorem 1.2 of Li and Roche-Newton's paper arxiv.org/pdf/1111.5159v1.pdf gives a slightly better lower bound of $|A|^{24/19}$. This result also gives the best lower bound on $|A+A|$ when $|AA|$ or $|S+S|$ is very small. $\endgroup$ Sep 10, 2015 at 23:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.