Return to Answer

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-1$, for otherwise we can choose all the elements $(0,x)$ ($x \neq 0$). Thus $\sum |Y_i|-1 \geq p$. 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$. 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 also 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.

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.

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.

The proof is along the lines of the last paragraph of this blogpost by removing $A_1$ in the proof in the blogpost.

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 $\underset{i} \sum |Y_i|=2p-1$, for otherwise we can choose all the elements $(0,x)$ ($x \neq 0$). Thus $\underset{i} \sum |Y_i|-1=p$. By the Cauchy-Davenport theorem, $|\sum Y_i|-1 \geq \underset{i} \sum |Y_i|-1$ if $\sum Y_i$ is not the whole $\mathbb Z_p$, but this is impossible because $\underset{i} \sum |Y_i|-1=p$. ($\sum Y_i$ is the additive-combinatorial sumset of all the $Y_i$s.) 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 also 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 \underset{i} \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.

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-1$, for otherwise we can choose all the elements $(0,x)$ ($x \neq 0$). Thus $\sum |Y_i|-1 \geq p$. 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$. 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 also 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.

We need a lemma that replaces the $p$ in the Erdős-Ginzburg-Ziv theorem by $p-1$. This line of proof is modified from the proof on Zoltán Lóránt Nagy's PhD thesis, p.10.

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 there exists a subsequence $A$ of length $p-1$, in which the sum of the elements equals zero.

Proof. Let $b_n$ ($n=1 ... 2p-2$) indicate whether the element $a_n$ is in the subsequence, i.e. $b_n=1$ if $a_n \in A$ and $b_n=0$ otherwise.

Define the polynomial $f=\underset {n}\sum b_n+1$ and $g=\underset {n}\sum a_nb_n$.

The polynomial $P=(1-f^{p-1})(1-g^{p-1})- \gamma \underset{n} \prod (1-b_n)$ takes the value $0$ unlesss* $f=0$ and $g=0$, which means there are $p-1$ $b_n$s that are $1$ and the elements they indicate sum to $0$. By choosing $\gamma$ appropriately, we can let the degree of $P$ be $2p − 2$ and the monomial $\underset{n} \prod b_n$ having its coefficient nonzero. By the Combinatorial Nullstellensatz, the polynomial $P$ is nonzero for some choice of $b_n$s, i.e. there is a subsequence $A$ of length $p-1$, in which the sum of the elements equals zero.

*"A unlesss B" means "A iff (the negation of B)". The wording in the PhD thesis, "if and only if", is wrong.

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 $\underset{i} \sum |Y_i|=2p-1$, for otherwise we can choose all the elements $(0,x)$ ($x \neq 0$). Thus $\underset{i} \sum |Y_i|-1=p$. By the Cauchy-Davenport theorem, $|\sum Y_i|-1 \geq \underset{i} \sum |Y_i|-1$ if $\sum Y_i$ is not the whole $\mathbb Z_p$, but this is impossible because $\underset{i} \sum |Y_i|-1=p$. ($\sum Y_i$ is the additive-combinatorial sumset of all the $Y_i$s.) 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. This is our choice of first indices, and the point is also 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 \underset{i} \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.

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.

The proof is along the lines of the last paragraph of this blogpost by removing $A_1$ in the proof in the blogpost.

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 $\underset{i} \sum |Y_i|=2p-1$, for otherwise we can choose all the elements $(0,x)$ ($x \neq 0$). Thus $\underset{i} \sum |Y_i|-1=p$. By the Cauchy-Davenport theorem, $|\sum Y_i|-1 \geq \underset{i} \sum |Y_i|-1$ if $\sum Y_i$ is not the whole $\mathbb Z_p$, but this is impossible because $\underset{i} \sum |Y_i|-1=p$. ($\sum Y_i$ is the additive-combinatorial sumset of all the $Y_i$s.) 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 also 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 \underset{i} \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.