Application of Cauchy-Davenport

Question

Let $ p $ be a prime number and $ A \subset \mathbb{Z}/p\mathbb{Z} $. Suppose $ 0 \notin A $ and for $ a \in A $ define $ d(a)= \min\{k|-a \in \underbrace{A+A+ \dots +A}_\text{k times} \} $. I want to show that $$ \sum_{a \in A}d(a) \leq p-1 $$ Using a simple generalization of the Cauchy-Davenport inequality, one has that $$ |\underbrace{A'+A'+ \dots +A'}_\text{k times}| \geq \min\{p,k|A|+1\} $$where $ A'=A \cup \{0\} $ but I haven't figured out how to use this to prove the statement.

As a side question, if $ 0 $ would belong to $ A $, then I guess $ d(0)=1 $ or is it $ 0 $ as this maybe is the definition of adding $ A $ $ 0$ times if that makes any sense? Otherwise, I don't see why in the original statement we can take $ 0 \notin A $.

I would appreciate any help concerning the main question. Thank you!

Answer 1

The case where $|A|$ divides $p-1$ is easy: in this case, we can show that for all $a\in A$, we have $$ d(a)\le\frac{p-1}{|A|} $$ (set $k=\frac{p-1}{|A|}$ and apply the version of the Cauchy-Davenport Theorem that you quoted, noting that $-a\in\underbrace{A'+\cdots+A'}_{k}$ if and only if $d(a)\le k$). The desired result then follows immediately.

If $|A|$ does not divide $p-1$, then it is not necessarily true that $d(a)\le\frac{p-1}{|A|}$ for all $a\in A$: indeed, take $p=11$ and take $A=\{1,2,3\}$: then $d(11)=4>\frac{10}{3}$.

However, if we set $$ k=\left\lfloor\frac{p-1}{|A|}\right\rfloor $$ then we have $$ |\underbrace{A'+\cdots+A'}_{k}|\ge\min\left\{p, \left\lfloor\dfrac{p-1}{|A|}\right\rfloor|A|+1\right\} $$ and so $d(a)\le\left\lfloor\frac{p-1}{|A|}\right\rfloor$ for all $a\in A$, with at most $$ p - \left\lfloor\dfrac{p-1}{|A|}\right\rfloor|A|-1 $$ exceptions.

Now note that we also have $$ |\underbrace{A'+\cdots+A'}_{k+1}|\ge\min\left\{p, \left\lceil\dfrac{p-1}{|A|}\right\rceil|A|+1\right\}\ge p $$ and it follows that $d(a)\le k+1$ for all $a\in A$. To sum up, we now know that:

• $d(a)\le k+1$ for all $a\in A$
• $d(a)=k+1$ for at most $p - \left\lfloor\dfrac{p-1}{|A|}\right\rfloor|A|-1$ values of $a$.

Therefore, we have \begin{align} \sum_{a\in A}d(a)&\le k|A| + p - \left\lfloor\dfrac{p-1}{|A|}\right\rfloor|A|-1\\ &=\left\lfloor\dfrac{p-1}{|A|}\right\rfloor|A| + p - \left\lfloor\dfrac{p-1}{|A|}\right\rfloor|A|-1 \\ &=p-1 \end{align}