3
$\begingroup$

Let $A, B \subseteq \mathbb{Z}_p$, $p$ prime, $|B| \leq |A|$.

If $N_t$ denotes the number of elements of $\mathbb{Z}_p$ having at least $t$ representations as $a+b$, $a \in A, b \in B$, Pollard's inequality states that $$N_1 + \dots + N_t \geq \min(t(|A|+|B|-t), tp).$$

The only proof I know of this result is basically by induction on $|B|$, as shown in Nathanson's book.

Since the case $t=1$ is the Cauchy-Davenport inequality, is there a proof of Pollard's inequality by induction on $t$?

$\endgroup$

2 Answers 2

1
$\begingroup$

As far as I know, there is essentially just one proof of Pollard's inequality which, as you write, goes basically by induction on $|B|=\min\{|A|,|B|\}$. You can also check the original Pollard's paper (A generalisation of the theorem of Cauchy and Davenport, J. London Math. Soc. (2) 8 (1974), pp. 460–462) and its follow-up extension onto three or more set summands (Addition properties of residue classes, J. London Math. Soc. (2) 11 (1975), no. 2, pp. 147–152).

$\endgroup$
1
  • 2
    $\begingroup$ One can also prove Pollard's inequality by submodularity arguments: terrytao.wordpress.com/2011/12/26/… , although ultimately this is again basically an induction on the measure of one of the sets $A,B$. $\endgroup$
    – Terry Tao
    Feb 25, 2015 at 16:51
0
$\begingroup$

One can also prove Pollard's inequality similarly as Cauchy-Davenport, the key point is to investigate the minimizing problem of the quantity $$min_{|A|+|B|fixed}F(A,B), \quad where \quad F(A,B)=\sum_{i=1}^tN_i, t\leq min\{|A|,|B|\}fixed$$

The advantage is that we only need to prove the worst case, and in the worst case we can get some additional properties for free

This quantity $F(A, B)$ has the following 2 property:

  1. This quantity $F(A,B)$ is invariance under a translation of $A$ or $B$, i.e. when change $A$ to $A+d$ or $B$ to $B+d$, $\forall d\in \mathbb{Z_p}$, $F(A,B)=F(A+d,B)=F(A,B+d)$.
  2. change pair $(A,B)$ to $(A\cup B, A\cap B)$ make $|A|+|B|=|A\cup B|+| A\cap B|$ invaricane but $F(A\cup B, A\cap B)\leq F(A,B)$, the following is a picture help to illustract why $F(A\cup B, A\cap B)\leq F(A,B)$ is true.

enter image description here

Through finite times operation of type 1 and type 2 we can reduce the problem to the trivial case, $$ N_{1}+\cdots+N_{|B|} \geq \min (|B|\cdot |A|, |B|\cdot p) \quad (*) $$ and then we can prove the trivial case $(*)$ just by counting twice argument, because morally we have $N_{1}+\cdots+N_{|B|} =\#\{(a,b)|a\in A, b\in B\}= \min (|B|\cdot |A|, |B|p)$

$\endgroup$
1
  • 1
    $\begingroup$ The details of your argument are very unclear, but it seems that you have basically reinvented Pollard's original proof, which uses induction on $\min\{|A|,|B|\}$ (namely, induction is used to replace the original pair $(A,B)$ with the new pair $(A\cup B,A\cap B)$). $\endgroup$
    – Seva
    Jan 24, 2021 at 10:26

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.