多項式法

次数 $D$ 以下の多項式の空間 $W$ は、次数 $D$ 以下の単項式 $x_1^{a_1}\cdots x_n^{a_n}$（$a_1+\cdots+a_n\le D$）を基底にもち、その個数は $\binom{D+n}{n}$ である（$a_0:=D-\sum_ia_i$ を加えて、和が $D$ の非負整数の $(n+1)$ 組を数える。二項係数）。$f\mapsto(f(s))_{s\in S}$ は $W$ から $K^S$ への線形写像で、$\dim W>\lvert S\rvert=\dim K^S$ なので核は $0$ でない。$\square$

$n=1$ なら、$0$ でない 1 変数多項式の根は次数以下の個数しかないことによる。$n\ge2$ とし、$f=\sum_{j=0}^{t_n}f_j(x_1,\dots,x_{n-1})\,x_n^j$ と書く。$(s_1,\dots,s_{n-1})\in S_1\times\cdots\times S_{n-1}$ を固定すると、$x_n$ の多項式 $\sum_jf_j(s_1,\dots,s_{n-1})x_n^j$ は次数 $t_n$ 以下で $S_n$ の $t_n+1$ 個以上の点で消えるので、係数 $f_j(s_1,\dots,s_{n-1})$ はすべて $0$ である。$\deg_{x_i}f_j\le t_i$ なので、帰納法の仮定から各 $f_j=0$、よって $f=0$ である。$\square$

まず次を示す。$g\in K[x_i]$ が最高次の係数 $1$ の $s$ 次多項式なら、任意の $F\in K[x_1,\dots,x_n]$ は $F=qg+r$、$\deg q\le\deg F-s$、$\deg r\le\deg F$、$\deg_{x_i}r< s$ と書け、さらに $j\neq i$ について $\deg_{x_j}r\le\deg_{x_j}F$ である。実際、$F=\sum_kc_kx_i^k$（$c_k$ は $x_i$ を含まない多項式）と書き、1 変数の割り算で $x_i^k=a_kg+b_k$（$\deg b_k< s$、$k< s$ なら $a_k=0$、$b_k=x_i^k$、$k\ge s$ なら $\deg a_k=k-s$）とすると、$q:=\sum_kc_ka_k$、$r:=\sum_kc_kb_k$ が条件をみたす（$\deg(c_ka_k)\le\deg c_k+k-s\le\deg F-s$、$\deg(c_kb_k)\le\deg c_k+k$）。
この割り算を $F=f$、$g=g_1$ から始めて、余りを順に $g_2,\dots,g_n$ で割ると、
$$ f=\sum_{i=1}^nh_ig_i+r,\qquad\deg h_i\le\deg f-\lvert S_i\rvert,\qquad\deg_{x_i}r< \lvert S_i\rvert\ (i=1,\dots,n) $$
を得る（$g_i$ で割るとき、それまでに得た $\deg_{x_j}r< \lvert S_j\rvert$（$j< i$）は保たれる）。$f$ と各 $g_i$ は $S_1\times\cdots\times S_n$ で消えるので $r$ も消え、lem-pm-grid（$t_i=\lvert S_i\rvert-1$）により $r=0$ である。$\square$

$S_i$ を $t_i+1$ 元の部分集合に取り替えてよい。$f$ が $S_1\times\cdots\times S_n$ で消えると仮定すると、thm-pm-cn1 により $f=\sum_ih_ig_i$、$\deg h_i\le\deg f-(t_i+1)$ である。$h_ig_i$ の全次数 $\deg f$ の部分は、$h_i$ の全次数 $\deg f-t_i-1$ の部分と $x_i^{t_i+1}$ の積なので、そこに現れる単項式は $x_i$ の指数が $t_i+1$ 以上である。全次数が $\deg f$ より小さい単項式は $x_1^{t_1}\cdots x_n^{t_n}$ と異なる。よって $\sum_ih_ig_i$ の $x_1^{t_1}\cdots x_n^{t_n}$ の係数は $0$ で、$f$ の係数が $0$ でないことに反する。$\square$

$\lvert A\rvert+\lvert B\rvert>p$ なら、各 $g\in\mathbb{F}_p$ について $A$ と $g-B:=\{g-b\mid b\in B\}$ は個数の和が $p$ を超えるので交わり、$g\in A+B$ である。よって $A+B=\mathbb{F}_p$ である。
$\lvert A\rvert+\lvert B\rvert\le p$ とし、$\lvert A+B\rvert\le\lvert A\rvert+\lvert B\rvert-2$ と仮定する。$A+B\subset C$、$\lvert C\rvert=\lvert A\rvert+\lvert B\rvert-2$ となる $C$ をとり、$f(x,y):=\prod_{c\in C}(x+y-c)$ とおく。$f$ は $A\times B$ で消える。$f$ の全次数は $\lvert C\rvert$ で、最高次の部分は $(x+y)^{\lvert C\rvert}$ なので、$t_1=\lvert A\rvert-1$、$t_2=\lvert B\rvert-1$ について $x^{t_1}y^{t_2}$ の係数は $\binom{\lvert A\rvert+\lvert B\rvert-2}{\lvert A\rvert-1}$ である。$\lvert A\rvert+\lvert B\rvert-2< p$ なので、これは $p$ で割り切れず $\mathbb{F}_p$ で $0$ でない。thm-pm-cn2（$S_1=A$、$S_2=B$）から $f(a,b)\neq0$ となる $(a,b)\in A\times B$ があり、矛盾する。$\square$

$H_j=\{\ell_j=0\}$（$\ell_j$ は 1 次式）とし、$t_i:=\lvert S_i\rvert-1$、$N:=\sum_it_i$ とおく。$m< N$ と仮定する。$\ell_j(s)\neq0$ なので
$$ F(x):=\prod_{j=1}^m\ell_j(x)-c\prod_{i=1}^n\prod_{a\in S_i\setminus\{s_i\}}(x_i-a),\qquad c:=\frac{\prod_j\ell_j(s)}{\prod_i\prod_{a\in S_i\setminus\{s_i\}}(s_i-a)}\neq0 $$
とおける。$F(s)=0$ である。第 1 項の次数は $m< N$、第 2 項は全次数 $N$ で $x_1^{t_1}\cdots x_n^{t_n}$ の係数が $-c\neq0$ なので、thm-pm-cn2 から $F(x)\neq0$ となる $x\in S$ がある。$F(s)=0$ なので $x\neq s$ で、ある $i$ で $x_i\neq s_i$、すなわち $x_i\in S_i\setminus\{s_i\}$ となり第 2 項は $0$ である。また $x\in S\setminus\{s\}$ はある $H_j$ にのるので第 1 項も $0$ である。よって $F(x)=0$ となり矛盾する。$\square$

$\lvert K\rvert< \binom{q-1+n}{n}$ と仮定すると、lem-pm-interpolation（$D=q-1$）により、$K$ で消える $0$ でない $f$ で $\deg f\le q-1$ のものがある。$d:=\deg f$ とし、$f_d$ を $f$ の $d$ 次の斉次部分とする。$K\ne\emptyset$ なので $f$ は $0$ でない定数ではなく、$d\ge1$ である。
$b\neq0$ とし、$a$ を定義のとおりにとる。$\tau$ の多項式 $\varphi(\tau):=f(a+\tau b)$ は次数が $d$ 以下（$d\le q-1$）で、$\mathbb{F}_q$ の $q$ 個の点すべてで消えるので $\varphi=0$ である。$\varphi$ の $\tau^d$ の係数は $f_d(b)$ なので $f_d(b)=0$ である。$d\ge1$ なので $f_d(0)=0$ でもある。よって $f_d$ は $\mathbb{F}_q^n$ 全体で消え、$\deg_{x_i}f_d\le d\le q-1< q$ なので lem-pm-grid（$S_i=\mathbb{F}_q$）から $f_d=0$ となり、$f_d$ が $d$ 次の部分であることに反する。$\square$