Generalizations of Cauchy-Davenport Theorem

The Cauchy-Davenport Theorem says that if $A_1, \ldots, A_k$ are subsets of ${\mathbb Z}_p$, $p$ prime, then $| \sum_i A_i | \geq \min (p, \sum_i |A_i| -k +1)$.

I am looking for a generalization that bounds the number of ways each element $a \in \sum_i A_i$ can be represented as $a=\sum_i a_i$ with $a_i \in A_i$.

Specifically, I am interested in the case where $\sum_i |A_i| -k +1 \geq p$. Let $N_{min}$ denote the minimum number of ways any element can be written as a sum, and let $N_{max}$ denote the maximum number of ways any element can be written as a sum. Can we bound the ratio $N_{max}/N_{min}$? My vague conjecture would be that for $\sum_i |A_i| -k +1 \gg p$ we can bound the ratio by a constant, but I have no progress toward a proof.

I am aware of two papers by Pollard from the '70s and some followup work looking at sort-of-related questions, but am not aware of anything that comes close to addressing the above.

• There is some literature on a related problem (in the broader setting of semigroups), starting with J.H.B. Kerperman's paper: On complexes in a semigroup, Indag. Math., Vol. 18 (1956), 247-254. – Salvo Tringali Jan 18 '13 at 11:16

Take $A_1= ...=A_k=\{0,1,2,...,t\}\subset Z/pZ$, where $\sum |A_i|-k+1=k(t+1)-k+1=p$. Hence all classes are represented as a sum.

2 examples: $p=101, t=k=10$, or $t=1, k=p-1$.

But the sumset $A_1 + ...+ A_k$ will represent the class $0$ just once, namely only with all $a_i=0$. More generally, the very small and very large classes ($\leq p-1$) are represented just a few times.

On the other hand, classes near $k t/2\approx p/2$ will be represented very often.

In fact, the expected value of the sum is $kt/2$, and there is some small standard deviation interval around it, which will get the bulk of all combinations.

On average, a class will have $(t+1)^k/p$ many representations, for classes near $kt/2$ this will be even higher. Therefore, in the above situation the ratio $N_{\max}/N_{\min}\geq ((t+1)^k/p)/1$ is not bounded by an absolute constant. (For example, if $t=1$, $k = p-1$).

If you choose $k$ and $t$ larger so that $kt \approx 5p$, for example, I still expect that the sums are clustered near the expected value.

• Your specific example is correct, but I was specifically interested in what happens when $\sum_i |A_i| -k +1 \gg p$. – user30706 Jan 18 '13 at 1:29