A sum-product phenomenon on reciprocals

Question

Let $A \subset \mathbb F_p \setminus \{0\} $ and let $A+1/A = \{x+1/y:x,y \in A\}$.

Question: For fixed $c>0$, if $|A| \geq cp$, is $|A+1/A|$ at least $(1-o(1))p$ when $p \rightarrow \infty$?

Known: This is false for $c<1/4$ according to Seva's comments.

Take $A$ to be $I \cap I^{-1}$ where $I=[1,m]$ and $m=(1/2-\epsilon)p$. It's sure that $A+1/A=A+A$ is not the whole $\mathbb F_p$. The hard part is that $A$ contains $(m/p)^2p(1-o(1))$ elements.

Let $X$ be the indicator function of $\{(x,1/x):x \in \mathbb F_p \setminus 0 \}$, and $Y$ the indicator function of $\{(x,y):x,y \in [1,m]\}$. The size of $A$ is the value of the inner product $\langle X,Y\rangle$.

To compute the inner product, we decompose $Y$ into a sum of Fourier coefficients.

Let $e(x)=\exp(2\pi i x/p)$, and let $K_\omega$ be the $\omega$-th coefficient of the Fourier transform of the indicator function of the interval $[1,m]$, i.e. $K_\omega = \underset{x=1}{\overset{m}{\sum}} e(\omega x)/p$, where $\omega=0,1,2,...,p-1$.

By the Fourier transform on cartesian products, $\langle X,Y\rangle = \underset{\psi=0}{\overset{p-1}{\sum}} \underset{\omega=0}{\overset{p-1}{\sum}} K_\psi K_\omega \langle e(\psi x)e(\omega y),X \rangle $.

Let $I_0$ be the term where $\psi$ and $\omega$ are both $0$, $I_1$ the sum of the terms where exactly one of $\psi$ and $\omega$ is $0$, and $I_2$ the sum of the terms where both $\psi$ and $\omega$ are nonzero. We have $\langle X,Y\rangle = I_0+I_1+I_2$ and $I_0=m^2(p-1)/p^2$.

To estimate $I_1$ and $I_2$, we need to bound the sum of $|K_\omega|$ over nonzero $\omega$. There is $K_\omega=\frac{e(\omega(m+1))-e(\omega)}{e(\omega)-1}/p$. As $|e(\omega)-1|=2\sin(\pi\omega/p)>4\omega/p$ when $0<\omega<p/2$, we have $|K_\omega|<\frac{2p}{4 \omega} /p = 1/2\omega$ when $0<\omega<p/2$. Thus the sum of $|K_\omega|$ over nonzero $\omega$ is $O(\log p)$.

The terms $K_\psi K_\omega \langle e(\psi x)e(\omega y),X \rangle$ appearing in $I_1$ has norm $K_\psi m/p$ when $\psi$ is nonzero or $K_\omega m/p$ when $\omega$ is nonzero, so $I_1=O(\log p)$.

If both $\psi$ and $\omega$ are nonzero, the term $\langle e(\psi x)e(\omega y),X \rangle$ can be estimated by the Kloosterman sum and it's $O(\sqrt{p})$. Summing over all nonzero $\psi$ and $\omega$, we have $I_2=O(\sqrt{p} \log^2 p)$.

Thus $\langle X,Y\rangle = I_0+I_1+I_2 = m^2(p-1)/p^2 + O(\log p)+O(\sqrt{p} \log^2 p) = (m/p)^2p(1-o(1))$.

This shows that the answer is false for any $c<1/4$.

Answer 1

The claim is true for $c > 1/4$, although the proof I have either requires the machinery of the arithmetic regularity lemma, or the (morally equivalent) language of additive limits (as discussed in this blog post of mine, or in this paper of Szegedy). I will sketch a proof with the latter approach, which is shorter (it avoids a lot of "epsilon management"). One can expand this argument into a lengthier argument using instead the arithmetic regularity lemma (which would most likely give some tower-exponential type quantitative dependencies on constants), analogously to how arguments using graph limits (graphons) can often be converted into lengthier arguments relying instead on the Szemeredi regularity lemma, but I will leave this to the interested reader.

In what follows I assume familiarity with the language of nonstandard analysis and Loeb measure.

Suppose for contradiction that the claim failed, thus there is $c>1/4$ and $\varepsilon>0$ and a sequence $A_i \subset {\mathbb F}_{p_i}^*$ of sets of density $c + o(1)$ indexed by some primes $p_i$ going off to infinity such that $|A_i + 1/A_i| \leq (1-\varepsilon+o(1)) p_i$. Taking an ultralimit, one obtains an internal subset $A$ of of a pseudofinite field ${\mathbb F} = {\mathbb F}_{p}$ (associated to a nonstandard prime $p$) of Loeb measure $c$ such that $A + \phi(A)$ has Loeb measure at most $1-\varepsilon$, where $\phi$ denotes the almost-everywhere defined inversion map $n \mapsto n^{-1}$. In particular the convolution $1_A * 1_{\phi(A)}$ avoids a set of positive measure.

The $\sigma$-algebra ${\mathcal L}$ of Loeb-measurable subsets of ${\mathbb F}$ has two notable factors. One is the Kronecker factor ${\mathcal K}$, generated by the eigenfunctions of $L^\infty({\mathcal L})$ with respect to the translation action (or equivalently, by the Fourier phases $n \mapsto \mathrm{st} e( an/p )$ for some non-standard $a \in {\mathbb F}$); the other is the pullback $\phi^* {\mathcal K}$ of the Kronecker factor ${\mathcal K}$ by the inversion map $\phi$. Because of Kloosterman sum estimates, the two factors ${\mathcal K}, \phi^* {\mathcal K}$ are orthogonal. The Kronecker factor is (up to some canonical isomorphisms) a compact abelian group (with Loeb measure restricting to the Haar probability measure on that group); in fact that compact abelian group is nothing more than the Pontryagin dual of the group of Fourier phases. Because this latter group is torsion-free (it is isomorphic as a group to the pseudofinite field ${\mathbb F}$), the Kronecker factor is then a connected compact abelian group.

Because the Kronecker factor is characteristic for convolutions (see the previous references), we have the identity $$ 1_A * 1_{\phi(A)} = {\bf E}(1_A|{\mathcal K}) * {\bf E}(1_{\phi(A)}|{\mathcal K})$$ Loeb-almost everywhere. In particular, $$ \mathrm{supp}({\bf E}(1_A|{\mathcal K})) + \mathrm{supp}({\bf E}(1_\phi(A)|{\mathcal K}))$$ fails to have full measure (here I gloss over a technical but fixable issue involving null sets). Applying Kemperman's theorem $$ \mu( A + B ) \geq \min( \mu(A)+\mu(B), 1 )$$ valid for any connected compact group with Haar probability measure (actually for the technical reason mentioned earlier one should actually use Pollard's theorem here, or the variant of Kemperman's theorem in this blog post of mine), we conclude that $$ \mu(\mathrm{supp}({\bf E}(1_A|{\mathcal K}))) + \mu(\mathrm{supp}({\bf E}(1_\phi(A)|{\mathcal K}))) < 1,$$ thus ${\bf E}(1_A|{\mathcal K})$ is supported in a ${\mathcal K}$-measurable set $E$ of measure at most $\alpha$ and ${\bf E}(1_\phi(A)|{\mathcal K})$ is supported in a set of measure at most $1-\alpha$ for some $0 \leq \alpha \leq 1$. Since $\phi$ is measure-preserving, we conclude that ${\bf E}(1_A|\phi^* {\mathcal K})$ is supported on a $\phi^* {\mathcal K}$-measurable set $F$ of measure at most $1-\alpha$. In particular we have the pointwise bounds $$ 1_A \leq 1_E$$ and $$ 1_A \leq 1_F$$ Loeb-almost everywhere, hence $$ 1_A \leq 1_E 1_F.$$ Loeb-almost everywhere. Integrating and using the orthogonality of ${\mathcal K}$ and $\phi^* {\mathcal K}$, we conclude that $$ c \leq \alpha(1-\alpha)$$ and hence $$ c \leq 1/4,$$ giving the desired contradiction.

Remark: I think that a refinement of this argument in fact gives the lower bound $|A + 1/A| \geq (\min(2\sqrt{c}, 1)-o(1)) p$ for any fixed $0 \leq c \leq 1$, and a variant of Seva's construction should show that this bound is asymptotically best possible.

Answer 2

Here is a partial answer based on (and slightly extending) my earlier comments.

• If $c>1/2$, then $A+A^{-1}=\mathbb F_p$ by the pigeonhole principle. We assume therefore that $c\le 1/2$.

• For any $c<1/4$ and sufficiently small $\epsilon>0$, there is a set $A$ with $|A|>cp$ and $|A+A^{-1}|<(1-\epsilon +o(1))p$. To see this let $m:=(1/2-\epsilon)p$ and $I:=[1,m]$ and notice that, by a simple averaging, there exists $x\in\mathbb F_p$ with $|(I+x)\cap I^{-1}|\ge m^2/p>(1/4-\epsilon)p$. Now let $A:=(I+x)\cap I^{-1}$. (This explains my comment about an overkill.)

• If I am not mistaken, then, subject to the finite field $(3n-4)$-conjecture, if $|A|>(1/3+\epsilon)p$, then $|A+A^{-1}|=(1-o(1))p$.