Freimanの定理

1 は定義から、$a_0+a'_0$ を起点に $a_1,\dots,a_d,a'_1,\dots,a'_{d'}$ を並べればよい。2：$P+P=2a_0+\sum_i\{0,\dots,2L_i-2\}a_i$、$P-P=-\sum_i(L_i-1)a_i+\sum_i\{0,\dots,2L_i-2\}a_i$ である。$P$ が真なら $\lvert P+P\rvert\le2^d\operatorname{vol}(P)=2^d\lvert P\rvert$ となる。3：$\lvert A+A\rvert\le\lvert P+P\rvert\le2^d\lvert P\rvert\le2^dK\lvert A\rvert$ である。$\square$

法 $N$ の写像は群の準同型なので Freiman $s$-準同型である。$a_i,a'_i\in A$ について $\sum_{i=1}^s a_i\equiv\sum_{i=1}^s a'_i\pmod N$ とすると、$\bigl\lvert\sum_i(a_i-a'_i)\bigr\rvert\le\sum_i\lvert a_i-a'_i\rvert< s\cdot N/s=N$ なので、$N$ の倍数であるこの整数は $0$ である。とくに $a\equiv a'$ なら（$a_1=a$、$a'_1=a'$、残りを同じ元にとって）$a=a'$ なので単射であり、逆写像も Freiman $s$-準同型である。$\square$

$x=(x_1,\dots,x_d)$（$0\le x_i\le L_i-1$）について $p(x):=a_0+\sum x_ia_i$ とおき、$\phi(p(x))=\phi(a_0)+\sum_ix_ib_i$ を $x_1+\cdots+x_d$ についての帰納法で示す。和が $0$ なら明らかである。$x_j\ge1$ となる $j$ をとると $L_j\ge2$ で、$x-e_j$（$e_j$ は $j$ 番目の単位ベクトル）も範囲内にあり、 $$p(x)+a_0=p(x-e_j)+(a_0+a_j)$$ の 4 つの元はすべて $P$ に属する。$\phi$ は Freiman $2$-準同型なので $\phi(p(x))+\phi(a_0)=\phi(p(x-e_j))+\phi(a_0+a_j)$、すなわち $\phi(p(x))=\phi(p(x-e_j))+b_j$ であり、帰納法の仮定から主張が従う。よって $\phi(P)$ は書かれた形の一般化等差数列で、$P$ が真で $\phi$ が単射なので $x\mapsto\phi(p(x))$ は単射、すなわち $\phi(P)$ も真である。$\square$

$k\le2$ では $\lvert A+A\rvert\ge2k-1>3k-4$ なので仮定がみたされず、$k\ge3$ としてよい。$a_0:=\min A$、$g:=\gcd\{a-a_0\mid a\in A\}$ とおき、$A^*:=\{(a-a_0)/g\mid a\in A\}$ とする。$A^*$ は $\min A^*=0$、$\gcd A^*=1$ をみたし、$x\mapsto(x-2a_0)/g$ は $A+A$ から $A^*+A^*$ への全単射なので $\lvert A^*+A^*\rvert=\lvert A+A\rvert$ である。$\ell:=\max A^*$ とする。

HSZ05 Theorem 1 は、$U,V\subset\{0,1,\dots,b\}$、$0\in U\cap V$、$b\in V$、$\gcd V=1$ のとき $\lvert U+V\rvert\ge\min\{b+\lvert U\rvert,\ \lvert U\cup(U+b)\rvert+\lvert V\rvert-2\}$ であることを述べる。これは LS95 Lemma 1（p. 85）を書き換えた形で、証明は LS95 §3（pp. 87–90）にあり、Kneser の定理を使う（この記事では証明しない）。$U=V=A^*$、$b=\ell$ とすると、$A^*\cap(A^*+\ell)=\{\ell\}$ なので $\lvert A^*\cup(A^*+\ell)\rvert=2k-1$ で、 $$\lvert A+A\rvert=\lvert A^*+A^*\rvert\ge\min\{k+\ell,\ 3k-3\}$$ を得る。仮定 $\lvert A+A\rvert\le3k-4$ から右辺は $k+\ell$ で、$\ell+1\le\lvert A+A\rvert-k+1$ である。$A^*\subset\{0,1,\dots,\ell\}$ なので、$A$ は長さ $\ell+1$ の等差数列 $\{a_0,a_0+g,\dots,a_0+\ell g\}$ に含まれる。$\square$

$\bar A\subset\mathbb{Z}/\ell\mathbb{Z}$ を $A$ の像とする。$0$ と $\ell$ は同じ類になり、$A\cap\{0,\dots,\ell-1\}$ は $\bar A$ に全単射で写るので $\lvert\bar A\rvert=k-1$ である。$A+A\subset\{0,\dots,2\ell\}$ の元を法 $\ell$ の類で分けて数える。$\bar A+\bar A$ の各類は $A+A$ の元を少なくとも 1 つ含む。$a\in A\cap\{0,\dots,\ell-1\}$ の類は、相異なる 2 元 $a=a+0$ と $a+\ell$ を含み、類 $0$ は $0,\ell,2\ell$ の 3 元を含む。$0\in\bar A$ なので $\bar A\subset\bar A+\bar A$ であり、 $$\lvert A+A\rvert\ge\lvert\bar A+\bar A\rvert+\lvert\bar A\rvert+1=\lvert\bar A+\bar A\rvert+k$$ である。$\lvert\bar A\rvert=k-1>\ell/2$ なので、どの $g\in\mathbb{Z}/\ell\mathbb{Z}$ についても $\bar A$ と $g-\bar A$ は交わり（鳩の巣原理）、$\bar A+\bar A=\mathbb{Z}/\ell\mathbb{Z}$ である。よって $\lvert A+A\rvert\ge\ell+k$ である。$\square$

$T\subset X$ を、平行移動 $t+B$（$t\in T$）たちが互いに交わらないような部分集合のうち、包含について極大なものとする。$T+B$ は $\lvert T\rvert$ 個の互いに交わらない $t+B$ の合併で $X+B$ に含まれるので、$\lvert T\rvert\lvert B\rvert\le\lvert X+B\rvert\le K\lvert B\rvert$、すなわち $\lvert T\rvert\le K$ である。$x\in X$ とする。$x\in T$ なら $x\in T+B-B$ である。$x\notin T$ なら、極大性から $(x+B)\cap(t+B)\neq\emptyset$ となる $t\in T$ があり、$x+b=t+b'$（$b,b'\in B$）なので $x=t+b'-b\in T+B-B$ である。$\square$

Plünnecke–Ruzsaの不等式 により $\lvert A+(2A-A)\rvert=\lvert3A-A\rvert\le K^4\lvert A\rvert$ なので、lem-fr-covering（$X=2A-A$、$B=A$）により、$\lvert T\rvert\le K^4$ をみたす $T\subset2A-A$ で $2A-A\subset T+A-A$ となるものがある。$n\ge1$ について $(n+1)A-A\subset nT+A-A$ を帰納法で示す。$n=1$ はいま得た包含で、$n$ で成り立てば $$(n+2)A-A=A+\bigl((n+1)A-A\bigr)\subset nT+(2A-A)\subset nT+T+A-A=(n+1)T+A-A$$ である。指数が $r$ なので $-a=(r-1)a$ であり、$\langle A\rangle$ の元は $A$ の元のいくつかの和、すなわちある $n\ge1$ について $nA$ の元である。$0\in A-A$ から $nA\subset(n+1)A-A\subset nT+A-A\subset\langle T\rangle+A-A$ となり、$\langle A\rangle\subset\langle T\rangle+A-A$ である。$\langle T\rangle=\{\sum_{t\in T}c_tt\mid0\le c_t\le r-1\}$ なので $\lvert\langle T\rangle\rvert\le r^{\lvert T\rvert}\le r^{K^4}$ で、Plünnecke–Ruzsa の不等式から $\lvert A-A\rvert\le K^2\lvert A\rvert$ なので、$\lvert\langle A\rangle\rvert\le r^{K^4}K^2\lvert A\rvert$ である。$\square$

$sA-sA$ は $0$ を含み $-1$ 倍で閉じている。素数 $q>\max(sA-sA)$ をとると、$sA-sA$ の $0$ でない元 $x$ は $q$ で割り切れない。$\lambda\in\{1,\dots,q-1\}$ について、$\phi_\lambda(x)\in\{0,\dots,q-1\}$ を $\lambda x$ の法 $q$ の代表とする。$x\not\equiv0$ なら $\lambda\mapsto\phi_\lambda(x)$ は $\{1,\dots,q-1\}$ の全単射なので、$\phi_\lambda(x)$ が $N$ の倍数となる $\lambda$ は $(q-1)/N$ 個以下である。$sA-sA$ の $0$ でない元は $N-1$ 個以下なので、そのどれかについて $N\mid\phi_\lambda(x)$ となる $\lambda$ は $(N-1)(q-1)/N< q-1$ 個以下で、どの $0$ でない $x\in sA-sA$ についても $N\nmid\phi_\lambda(x)$ となる $\lambda$ がある。これを固定し $\phi:=\phi_\lambda$ とする。

$a\neq a'$（$a,a'\in A$）なら $a-a'$ は $sA-sA$ の $0$ でない元（両辺に同じ元を $s-1$ 個足す）なので $\phi(a)\neq\phi(a')$ である。$\{0,\dots,q-1\}$ を、整数 $j=0,\dots,s-1$ について $jq/s\le y<(j+1)q/s$ で定まる $s$ 個の区間に分けると、各区間の 2 元の差は $q/s$ 未満であり、鳩の巣原理からある区間 $I$ について $A':=\{a\in A\mid\phi(a)\in I\}$ は $\lvert A'\rvert\ge\lvert A\rvert/s$ をみたす。$\psi(a)$ を $\phi(a)$ の法 $N$ の類とし、$\psi\colon A'\to\psi(A')$ が Freiman $s$-同型であることを示す。

$a_i,a'_i\in A'$ について $y:=\sum_{i=1}^s\phi(a_i)-\sum_{i=1}^s\phi(a'_i)$ とおくと、$\lvert y\rvert\le\sum_i\lvert\phi(a_i)-\phi(a'_i)\rvert< s\cdot q/s=q$ であり、$x:=\sum a_i-\sum a'_i\in sA-sA$ について $\phi(x)\equiv\lambda x\equiv y\pmod q$ である。準同型であること：$x=0$ なら $y\equiv0\pmod q$ と $\lvert y\rvert< q$ から $y=0$ で、法 $N$ でも $\sum\psi(a_i)=\sum\psi(a'_i)$ である。逆写像が準同型であること：$\sum\psi(a_i)=\sum\psi(a'_i)$ なら $N\mid y$ である。必要なら $a_i$ と $a'_i$ の組を入れ替えて $y\ge0$ とすると、$0\le y< q$ と $\phi(x)\equiv y\pmod q$、$0\le\phi(x)< q$ から $\phi(x)=y$ で、$N\mid\phi(x)$ となる。$\lambda$ の選び方から $x=0$、すなわち $\sum a_i=\sum a'_i$ である。とくに $\psi$ は $A'$ の上で単射である（$a_1=a$、$a'_1=a'$、残りを同じ元にとる）。$\square$

$a_1+a_2-a_3-a_4=a'_1+a'_2-a'_3-a'_4$ なら $a_1+a_2+a'_3+a'_4=a'_1+a'_2+a_3+a_4$ である。$\psi$ は Freiman $8$-準同型なので $4$-準同型でもあり、$\psi(a_1)+\psi(a_2)+\psi(a'_3)+\psi(a'_4)=\psi(a'_1)+\psi(a'_2)+\psi(a_3)+\psi(a_4)$ となって、$\Psi$ は well-defined である。$\psi^{-1}$ についても同じく $\Psi':2B-2B\to2A'-2A'$ が定まり、$\Psi$ と $\Psi'$ は互いに逆である。$u_j=p_j-q_j$（$p_j,q_j\in2A'$、$j=1,\dots,4$）が $u_1+u_2=u_3+u_4$ をみたせば、$p_1+p_2+q_3+q_4=p_3+p_4+q_1+q_2$ は両辺とも $A'$ の $8$ 元の和の等式なので、$\psi$ が Freiman $8$-準同型であることから $\Psi(u_1)+\Psi(u_2)=\Psi(u_3)+\Psi(u_4)$ である。$\Psi'$ についても同じで、$\Psi$ は Freiman $2$-同型である。