The popularity gap

In this paper we prove that every set $A\subset\mathbb{Z}$ satisfying the inequality $\sum_{x}\min(1_A*1_A(x),t)\le(2+\delta)t|A|$ for $t$ and $\delta$ in suitable ranges, then $A$ must be very close to an arithmetic progression. We use this result to improve the estimates of Green and Morris for the probability that a random subset $A\subset\mathbb{N}$ satisfies $|\mathbb{N}\setminus(A+A)|\ge k$; specifically we show that $\mathbb{P}(|\mathbb{N}\setminus(A+A)|\ge k)=\Theta(2...

For $p$ being a large prime number, and $A \subset \mathbb{F}_p$ we prove the following: $(i)$ If $A(A+A)$ does not cover all nonzero residues in $\mathbb{F}_p$, then $|A| < p/8 + o(p)$. $(ii)$ If $A$ is both sum-free and satisfies $A = A^*$, then $|A| < p/9 + o(p)$. $(iii)$ If $|A| \gg \frac{\log\log{p}}{\sqrt{\log{p}}}p$, then $|A + A^*| \geqslant (1 - o(1))\min(2\sqrt{|A|p}, p)$. Here the constants $1/8$, $1/9$, and $2$ are the best possible. The proof involves \em...

For a compact abelian group $G$, a corner in $G \times G$ is a triple of points $(x,y)$, $(x,y+d)$, $(x+d,y)$. The classical corners theorem of Ajtai and Szemer\'edi implies that for every $\alpha > 0$, there is some $\delta > 0$ such that every subset $A \subset G \times G$ of density $\alpha$ contains a $\delta$ fraction of all corners in $G \times G$, as $x,y,d$ range over $G$. Recently, Mandache proved a "popular differences" version of this result in the finite field c...

Our main result is that if A is a finite subset of an abelian group with |A+A| < K|A|, then 2A-2A contains an O(log^{O(1)} K)-dimensional coset progression M of size at least exp(-O(log^{O(1)} K))|A|.

We determine the structure of a finite subset $A$ of an abelian group given that $|2A|<3(1-\epsilon)|A|$, $\epsilon>0$; namely, we show that $A$ is contained either in a "small" one-dimensional coset progression, or in a union of fewer than $\epsilon^{-1}$ cosets of a finite subgroup. The bounds $3(1-\epsilon)|A|$ and $\epsilon^{-1}$ are best possible in the sense that none of them can be relaxed without tightened another one, and the estimate obtained for the size of the c...

Let G be an arbitrary Abelian group and let A be a finite subset of G. A has small additive doubling if |A+A| < K|A| for some K>0. These sets were studied in papers of G.A. Freiman, Y. Bilu, I. Ruzsa, M.C.--Chang, B. Green and T.Tao. In the article we prove that if we have some minor restrictions on K then for any set with small doubling there exists a set Lambda, |Lambda| << K log |A| such that |A\cap Lambda| >> |A| / K^{1/2 + c}, where c > 0. In contrast to the previous res...

Improving upon the results of Freiman and Candela-Serra-Spiegel, we show that for a non-empty subset $A\subseteq\mathbb F_p$ with $p$ prime and $|A|<0.0045p$, (i) if $|A+A|<2.59|A|-3$ and $|A|>100$, then $A$ is contained in an arithmetic progression of size $|A+A|-|A|+1$, and (ii) if $|A-A|<2.6|A|-3$, then $A$ is contained in an arithmetic progression of size $|A-A|-|A|+1$. The improvement comes from using the properties of higher energies.

We prove that for any finite set A of real numbers its difference set D:=A-A has large product set and quotient set, namely, |DD|, |D/D| \gg |D|^{1+c}, where c>0 is an absolute constant. A similar result takes place in the prime field F_p for sufficiently small D. It gives, in particular, that multiplicative subgroups of size less than p^{4/5-\eps} cannot be represented in the form A-A for any A from F_p.

Which finite sets $P \subseteq \mathbb{Z}^r$ with $|P| \ge 3$ have the following property: for every $A \subseteq [N]^r$, there is some nonzero integer $d$ such that $A$ contains $(\alpha^{|P|} - o(1))N^r$ translates of $d \cdot P = \{d p : p \in P\}$, where $\alpha = |A|/N^r$? Green showed that all 3-point $P \subseteq \mathbb{Z}$ have the above property. Green and Tao showed that 4-point sets of the form $P = \{a, a+b, a+c, a+b+c\} \subseteq \mathbb{Z}$ also have the prop...

Let $A$ be a subset of the cyclic group $\mathbf{Z}/p\mathbf{Z}$ with $p$ prime. It is a well-studied problem to determine how small $|A|$ can be if there is no unique sum in $A+A$, meaning that for every two elements $a_1,a_2\in A$, there exist $a_1',a_2'\in A$ such that $a_1+a_2=a_1'+a_2'$ and $\{a_1,a_2\}\neq \{a_1',a_2'\}$. Let $m(p)$ be the size of a smallest subset of $\mathbf{Z}/p\mathbf{Z}$ with no unique sum. The previous best known bounds are $\log p \ll m(p)\ll \sq...