Conclusion_1#

Given $n$ integers $\{a_1,a_2,\dots,a_n\}$ , $\exists\ I\subseteq \{1,2,\dots,n\}$ and $|I|\ne 0,\ s.t.\ n|\sum_{i\in I}{a_i}$
(可考虑部分和，以及利用鸽巢原理)
(其中 $n$ 为最佳,可取 $n-1$ 个 $1$.)

Conclusion_2#

Erdo ̋s,Ginzburg\ and\ Ziv\ Theorem (1961)

Given $2n-1$ integers $\{a_1,a_2,\dots,a_n\}$,$\exists\ I\subseteq \{1,2,\dots,2n-1\}$ and $|I|=n,\ s.t.\ n|\sum_{i\in I}{a_i}$
(可使用反证法，取p-1次方，导出矛盾)
(其中 $2n-1$ 为最佳,可取 $n-1$ 个 $0,1$.)

General_Problem#

$G$ 为有限交换群, $A$ 是由 $G$ 中元素构成的可重集。
(1) $|A|$ 多大时， $\exists\ B \subseteq A$ and $|B|\ne 0,\ s.t.\ \sigma(B)=0$.(称为$Davenport$常数,记作 $D(G)$ )
(2) $k\in \mathbb{Z}_{>0}$ and $exp(G)|k$ , $|A|$ 多大时， $\exists B \subseteq A$ and $|B|=k,\ s.t.\ \sigma(B)=0$.(记作 $S(G)$ )(称 $B$ 为 $k$ 元 $Zero-sum-subset$ )

$exp(G):=\underset{x\in G}{max}\ ord(x)$
$G=C_{n_1}\oplus C_{n_2}\oplus\cdots\oplus C_{n_l},\ n_1|n_2|\cdots|n_l,\ exp(G)=n_l$

$\sigma(B):=\sum_{x\in B}x$, 约定 $\sigma(\emptyset)=0$

(Con.1中, $G=\mathbb{Z} /n\mathbb{Z}=C_n$)
(Con.2中, $G=C_n,k=n=exp(C_n)$ )

Concerning_Problem#

考虑 $G$ 秩为 $2$ 且 $n=p$ 的情形,即
$A=\{(a_1,b_1),(a_2,b_2),\dots,(a_m,b_m)\}\subset\mathbb{Z}^2$
(1) 当 $m$ 多大时, $\exists B \subseteq A$ and $|B|\ne 0,\ s.t.\ \sigma(B)\equiv (0,0)\ (mod\ p)$
(2) 当 $m$ 多大时, $\exists B \subseteq A$ and $|B|=p,\ s.t.\ \sigma(B)\equiv (0,0)\ (mod\ p)$

$Ans_1\ =\ 2p-1$ ($2p-2$ 反例: $p-1$ 个 $(0,1),(1,0)$ )
$Ans_2\ =\ 4p-3$ ($4p-4$ 反例: $p-1$ 个 $(0,0),(0,1),(1,0),(1,1)$ )
(注意到解决Con.1的鸽巢原理无法应用于此处)
(Problem_2 又被称为 $Kemnitz’\ Conjecture$ )

For_Con.1#

$n=p,\ a_1,a_2,\dots,a_m\in \mathbb{Z}_{>0}$
$S_k:=\{B\subset A\ |\ \sigma(B)\equiv k\ (mod\ p)\},\ k=0,1,\dots,p-1$
$f(x):=(1-x^{a_1})(1-x^{a_2})\cdots(1-x^{a_m})\in \mathbb{F}_p/(x^p-1)$
$f(x)=\sum_{B\subset A}(-1)^{|B|}x^{\sigma(B)}=\sum_{k=0}^{p-1}(\sum_{B\in S_k}(-1)^{|B|})x^k\ \ (\star)$
上式可看作是余式，所以表示方式是唯一的.
另一方面,又有 $(1-x^{a_j})=(1-x)(\cdots)$ ,则 $f(x)=(1-x)^pg(x)$
$(1-x)^p=1-\binom{p}{1}x+ \binom{p}{2}x^2+\cdots+(-1)^px^p \overset{mod\ p}{==}1-x^p\overset{mod\ x^p-1}{==}0$
$\Rightarrow\ f(x)=0$ 结合 $(\star)$ $\Rightarrow$ $\forall\ 0\le k\le p-1,\ \sum_{B\in S_k}(-1)^{|B|}\equiv 0\ (mod\ p)$
特别的，$k=0$ 时，$\emptyset \in S_k$ 而 $\sum_{B\in S_k}(-1)^{|B|}\equiv 0\ (mod\ p)$
$\Rightarrow\ \exists\ B\in S_0$ and $|B|\ne 0,\ s.t.\ \sigma(B)\equiv 0\ (mod\ p)$.

$\Box$

For_Problem-1#

$A=\{(a_i,b_i)\ |\ a_i,b_i\in\mathbb{Z}_{>0}\ ,i=1,2,\dots,2p-1\}$
$f(X_1,X_2):=\prod_{i=1}^{2p-1}(1-X_1^{a_i}X_2^{b_i})\in \mathbb{F}_p[X_1,X_2]/(X_1^p-1,X_2^p-1)$
记为向量形式: $X=(X_1,X_2),\ \alpha_i=(a_i,b_i),\ X^{\alpha_i}=X_1^{a_i}X_2^{b_i}$ $S_{\alpha}:=\{B\subset A\ |\ \sigma(B)\equiv \alpha\ (mod\ p)\},\ \alpha=\{0,1,\dots,p-1\}^2$
$f(X_1,X_2)=\prod_{i=1}^{2p-1}(1-X^{\alpha_i})=\sum_{B\subset A}(-1)^{|B|}x^{\sigma(B)}$
$f(X)=\sum_{\alpha\in\{0,1,\dots,p-1\}^2}(\sum_{B\in S_{\alpha}}(-1)^{|B|})X^{\alpha}$
$Lemma:$ $(1-X_1^{a_i}X_2^{b_i})=(1-X_1)\cdot u_i(X_1,X_2)+(1-X_2)\cdot v_i(X_1,X_2)$
It’s a simple task. $A=\{f(X_1,X_2)\ |\ f(1,1)=0\},\ B=(X_1-1,X_2-1)$
$\mathbb{F} _p[X_1,X_2]/A\ =\ \mathbb{F} _p[X_1,X_2]/B$ $\Rightarrow A=B$

$f(X_1,X_2)=\prod_{i=1}^{2p-1}((1-X_1)\cdot u_i(X_1,X_2)+(1-X_2)\cdot v_i(X_1,X_2))=\sum(1-X_1)^s(1-X_2)^t(\cdots)$
$s+t=2p-1\ \Rightarrow\ s\ge p\ or\ t\ge p$
$(1-X_1)^p=0$ and $(1-X_2)^p=0\ \Rightarrow\ f(X_1,X_2)=0\ \Rightarrow$
$\forall\ \alpha\in\{0,1,\dots,p-1\}^2,\ \sum_{B\in S_{\alpha}}(-1)^{|B|}\equiv 0\ (mod\ p)$
$\emptyset\in S_{(0,0)}\ \Rightarrow\ \exists\ |B|\ne 0,\ s.t.\ \sigma(B)\equiv 0\ (mod\ p)$

$\Box$

Theorem’s_Proof#

$x=(x_1,x_2,\dots,x_n)\in \mathbb{F}_p^n$ According to Fermat’s Little Theorem,
$x\in \mathcal{Z}(F_1,F_2,\dots,F_m)\ \Leftrightarrow\ \prod_{j=1}^{m}(1-F_j(x)^{p-1})=1\in\mathbb{F}_p$ $\#\mathcal{Z}(F_1,F_2,\dots,F_m)\equiv \sum_{x\in\mathbb{F}_p}\prod_{j=1}^{m}(1-F_j(x)^{p-1})\ (mod\ p)$
约定 $x^0|_{x=0}=1.$
$Lemma:$
$\forall a\ge 0$

\begin{cases} F_1=x_1^{p-1}+x_2^{p-1}+\cdots x_{m}^{p-1}\ F_2=a_1x_1^{p-1}+a_2x_2^{p-1}+\cdots a_{m}x_{m}^{p-1}\ F_3=b_1x_1^{p-1}+b_2x_2^{p-1}+\cdots b_{m}x_{m}^{p-1} \end{cases}