Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.