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.


2 Answers 2


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 \begin{equation} \label{claim} |A+f(A)| \gg \min \left \{ \sqrt{p|A|}, \frac{|A|^2}{\sqrt{p}} \right \}. \end{equation} 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.

  • $\begingroup$ Sorry, can you elaborate a bit more on why $|A| \ge p/10\log^*p$? $\endgroup$ Commented Nov 25, 2019 at 22:46
  • 1
    $\begingroup$ @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). $\endgroup$ Commented Nov 26, 2019 at 0:14
  • $\begingroup$ What is meant by $\log^*p$, please? $\endgroup$ Commented Nov 26, 2019 at 2:39
  • $\begingroup$ @GerryMyerson en.wikipedia.org/wiki/Iterated_logarithm $\endgroup$ Commented Nov 26, 2019 at 4:49
  • 2
    $\begingroup$ 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$." $\endgroup$ Commented Nov 26, 2019 at 9:25

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.