Proof of Pollard's inequality

Question

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$?

Answer 1

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).

Answer 2

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.

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)$