5
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
6
$\begingroup$

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}$.

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Sorry, can you elaborate a bit more on why $|A| \ge p/10\log^*p$? $\endgroup$
    – Sandeep Silwal
    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$
    – Sam Zbarsky
    Commented Nov 26, 2019 at 0:14
  • $\begingroup$ What is meant by $\log^*p$, please? $\endgroup$
    – Gerry Myerson
    Commented Nov 26, 2019 at 2:39
  • $\begingroup$ @GerryMyerson en.wikipedia.org/wiki/Iterated_logarithm $\endgroup$
    – Sam Zbarsky
    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$
    – Gerry Myerson
    Commented Nov 26, 2019 at 9:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .