# Nontrivial expansion in sumsets

Let $$A \subset \mathbb{Z}/p$$, let $$f$$ be a function on $$\mathbb{Z}/p$$ and let $$B:=\{f(a): a \in A\}$$.

Can we conclude that $$|A+B|$$ is large if $$f$$ is a sufficiently "nice" function? For instance say that $$f(a)=a^2$$. Then can we say that if $$|A|=1000\sqrt{p}$$ or even if $$|A|=\frac{p}{\log^{*}(p)}$$, then $$|A+B| \ge p/100$$?

The idea should be that $$A+B$$ is only small if $$A,B$$ are related by some additive structure, and if $$f$$ is a sufficiently random function then it should kill any structure so that $$A+B$$ should be large.

Here is a partial "yes", to complement Sam Zbarsky's negative answer to the question.

There are a bunch of different papers on this topic focusing on different functions $$f$$ and in different ranges. To simplify things, I will focus on $$f(x)=x^2$$, since you mentioned it.

For $$|A|< p^{5/8}$$, a result of Pham, Vinh and de Zeeuw gives $$|A+f(A)| \gg |A|^{6/5}$$.

For larger sets, I cannot find a reference from the top of my head, but I am quite confident that exponential sum techniques could prove that $$$$\label{claim} |A+f(A)| \gg \min \left \{ \sqrt{p|A|}, \frac{|A|^2}{\sqrt{p}} \right \}.$$$$ See for example Theorem 7 in this paper of Balog, Broughan and Shparlinksi, which implies this result for $$f(x)=x^{-1}$$. I am pretty sure that I have seen this result with $$f(x)=x^2$$ in the literature at some point, but cannot remember where right now. If this claim is correct then it is optimal, as you can construct a set $$A$$ of any given size with $$|A+A^2| \ll \sqrt{|A|p}$$.

We can't. This is written for $$f(a)=a^2$$ but it should work for any "sufficiently random" function, in fact it uses "randomness".

Let $$A=\left\{a\in \left[1,\frac{p}{\sqrt{\log^*p}}\right]\,\Bigg\vert\, f(a)\in \left[1,\frac{p}{\sqrt{\log^*p}}\right]\right\}$$

Then it's not hard to see that $$|A|\ge \frac{p}{10\log^*p}$$ (essentially using the fact that squares on intervals $$[a,a+\lfloor p/2a\rfloor]$$ are approximately uniformly distributed, and looking at $$a<\frac{p}{3\sqrt{\log^* p}}$$. However, $$|A+A|\le\left|\left[1,\frac{2p}{\sqrt{\log^*p}}\right]\right|=\frac{2p}{\sqrt{\log^*p}}$$

Edited to add: I think this should work for any function $$f$$ by introducing random offsets to the two intervals; that is we'll get some set $$A$$ so that both $$A$$ and $$f(A)$$ fit in an interval of size $$\frac{p}{\sqrt{\log^*p}}$$, but $$\mathbb E|A|\ge \frac{p}{10\log^*p}$$. Thus, some choice of offsets gives a counterexample.

• Sorry, can you elaborate a bit more on why $|A| \ge p/10\log^*p$? Nov 25, 2019 at 22:46
• @SandeepSilwal divide the interval $[p^{2/3},p/(3\log^*p)]$ into intervals of the form $[a,a+\lfloor p/(2a)\rfloor]$, with about $\log^*p$ numbers left over. The elements of each interval are sent to a sequence whose successive differences are $(2+o(1))a$ and which has $\lfloor p/(2a)\rfloor+1$ elements. Thus at least $\frac{p}{4a\sqrt{\log^*p}}$ of them lie in the interval $[1,p/\sqrt{\log^* p}]$, which makes a fraction of $\frac{1}{2\sqrt{\log^*p}}$. Summing over all such intervals, we get the desired result (and the constant 10 has a safety margin). Nov 26, 2019 at 0:14
• What is meant by $\log^*p$, please? Nov 26, 2019 at 2:39
• @GerryMyerson en.wikipedia.org/wiki/Iterated_logarithm Nov 26, 2019 at 4:49
• In case anyone else is curious, it's "the number of times the logarithm function must be iteratively applied before the result is less than or equal to $1$." Nov 26, 2019 at 9:25