4
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

2
$\begingroup$

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.

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

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.