$p-1$ elements in $\mathbb{Z}_p\times\mathbb{Z}_p$ with a sum $(0,0)$

Question

Given prime $p\ge 11$, $S$ is a subset of $\mathbb{Z}_p\times\mathbb{Z}_p$ with $3p-3$ elements. Prove: $S$ has a subset $T$ with $p-1$ elements, such that$\sum_{x\in T}x\equiv (0,0)\pmod{p}$.

Answer 1

In this post a sum over sets means the additive-combinatorial sum, i.e. $\sum A_i=\{a_1+...+a_i : a_1 \in A_1, ..., a_i \in A_i\}$.

Lemma. Let $(a_1,a_2,... ,a_{2p−2})$ be a sequence of $2p−2$ elements of $\mathbb Z_p$, where $p$ is a prime. Then either

• there exists a subsequence $A$ of length $p-1$, in which the sum of the elements equals zero, or
• $p$ elements take the same value in the sequence.

Proof: We may assume $a_1 \leq a_2 \leq ... \leq a_{2p-2}$. If there are $p$ consecutive values, then we are in the second case, otherwise $a_1 \neq a_{p}$, $a_2 \neq a_{p+1}$, $...$, $a_{p-1} \neq a_{2p-2}$, and we can define the sets $B_i=\{a_i,a_{i+p-1}\}$. By the Cauchy-Davenport theorem, $|\sum B_i|-1 \geq \sum (|B_i|-1)$ if $\sum B_i$ is not the whole $\mathbb Z_p$, but this is impossible because $\sum (|B_i|-1) = p-1$. So $0\in ∑B_i$ and it's possible to pick one element in each $B_i$ to get a zero sum.

Now we prove the main theorem.

Let $X$ be a sequence where the number of occurences of $x$ is one less than the number of occurences of $x$ in $S$ as the first index, i.e. $|\{i:X_i=x\}|=|\{y: (x,y)\in S\}|-1$. The sequence has length $2p-3$ if every element appears in $S$ as the first index, and at least $2p-2$ otherwise.

If $X$ has length $2p-3$, we may assume that the elements we choose have first indices $1,2,3...(p-1)$, and we try to find appropriate second indices. Let $Y_i$ be the set of second indices of the elements of $S$ having first index $i$ ($i \neq 0$). We may assume $\sum |Y_i| \geq 2p-2$, for otherwise we can choose all the elements $(0,x)$ ($x \neq 0$). Thus $\sum (|Y_i|-1) \geq p-1$. By the Cauchy-Davenport theorem, $|\sum Y_i|-1 \geq \sum (|Y_i|-1)$ if $\sum Y_i$ is not the whole $\mathbb Z_p$, but this is impossible because $\sum (|Y_i|-1) \geq p-1$. So $0\in ∑Y_i$ and there is an appropriate choice of second indices.

If $X$ has length at least $2p-2$, we may find a $(p-1)$-subsequence $A$ in $X$ that sum to zero, or there are $p$ elements with the same first index (this case is trivial). The sequence $A$ is our choice of first indices, and the point is again trying to find appropriate second indices. Let $Y_i$ be the set of k-sums of second indices of the elements of $S$ having first index $i$ ($i \in A$), where $k$ is the number of occurences of $i$ in $A$. As $k$ is smaller than the number of elements in $S$ having first index $i$ (by the definition of $X$), the set $Y_i$ has size at least (number of occurences of $i$ in $A$)+1. Now $|\sum Y_i|-1 \geq \sum (|Y_i|-1)$ if $\sum Y_i$ is not the whole $\mathbb{Z} _p$, but this is impossible because $\sum (|Y_i|-1) \geq |A| = p-1$. So $0\in ∑Y_i$ and there is an appropriate choice of second indices.