Pickの定理

$\Delta x:=x_2-x_1$、$\Delta y:=y_2-y_1$、$g:=\gcd(|\Delta x|,|\Delta y|)$ とし、$\Delta x=gu$、$\Delta y=gv$（$\gcd(u,v)=1$）と書く。線分上の点は $(x_1+t\Delta x,\,y_1+t\Delta y)$（$0\leq t\leq1$）と表され、これが格子点であることは $tgu$ と $tgv$ がともに整数であることと同値である。Bézoutの等式により $au+bv=1$ となる整数 $a,b$ があるので、このとき $tg=a(tgu)+b(tgv)$ も整数である。逆に $tg$ が整数なら $tgu$、$tgv$ も整数である。よって格子点に対応する $t$ は $t=k/g$（$k=0,1,\dots,g$）のちょうど $g+1$ 個である。

$\Gamma$ 上の格子点の個数（両端を含む）を $k$ とする。$\Gamma$ の両端は $P_1$ と $P_2$ の頂点なので格子点であり、$k\geq2$ である。$P$ の格子点は、$P_1$ の内部、$P_2$ の内部、$\Gamma$ の両端以外の点、$\partial P$ のいずれか 1 つに属し、$\Gamma$ の両端以外の $k-2$ 個の格子点は $P$ の内部にある。したがって
$$ I(P)=I(P_1)+I(P_2)+(k-2) $$
である。また $\Gamma$ 上の $k$ 個の格子点は $B(P_1)$ と $B(P_2)$ の両方で数えられており、そのうち両端の 2 個だけが $\partial P$ に残るので
$$ B(P)=B(P_1)+B(P_2)-2k+2 $$
である。よって
$$ f(P)=I(P_1)+I(P_2)+k-2+\frac{B(P_1)+B(P_2)}{2}-k+1-1=f(P_1)+f(P_2) $$
である。面積の等式は面積の加法性による。最後の主張は、2 つの等式の差をとれば従う。

$R=[x_0,x_0+a]\times[y_0,y_0+b]$（$a,b$ は正の整数）とすると、内部の格子点は $(a-1)(b-1)$ 個、周上の格子点は $2(a+b)$ 個なので
$$ f(R)=(a-1)(b-1)+(a+b)-1=ab=\operatorname{Area}(R) $$
である。
$T$ の直角の頂点を含む、$T$ を囲む最小の長方形を $R$ とする。$R$ は $T$ の斜辺で $T$ と三角形 $T'$ に分けられる。$R$ の中心を $(c_1,c_2)$ とすると $2c_1$、$2c_2$ は整数なので、中心のまわりの $180^\circ$ 回転 $(x,y)\mapsto(2c_1-x,\,2c_2-y)$ は格子点を格子点に移し、$T$ を $T'$ に移す。よって $I(T)=I(T')$、$B(T)=B(T')$、$\operatorname{Area}(T)=\operatorname{Area}(T')$ であり、lem-pick-additivity から
$$ 2f(T)=f(T)+f(T')=f(R)=\operatorname{Area}(R)=2\operatorname{Area}(T) $$
となる。

三角形 $T=ABC$ を囲む最小の長方形を $R=[x_0,x_1]\times[y_0,y_1]$ とする。$R$ の 4 辺のそれぞれに $T$ の頂点がある（$x$ 座標・$y$ 座標の最小値・最大値はどれも頂点で達成される）。頂点は 3 個しかないので、鳩の巣原理によりある頂点は $R$ の 2 辺に同時に乗り、$R$ の角にある。上の変換で動かして、$A=(x_0,y_0)$ としてよい。以下、面積が $0$ に退化する部分は省いて読む。
場合 1：$R$ の対角の角 $(x_1,y_1)$ が $T$ の頂点である場合。$C=(x_1,y_1)$ とする。長方形 $R$ の中心のまわりの $180^\circ$ 回転は $A$ と $C$ を入れ替え、直線 $AC$ の両側を入れ替えるので、これで動かして、$B=(p,q)$ が直線 $AC$ に関して点 $(x_1,y_0)$ と同じ側にあるとしてよい。このとき $x_0< p\leq x_1$、$y_0\leq q< y_1$ である。$R$ は対角線 $AC$ によって、直角三角形 $U=A\,(x_0,y_1)\,C$ と直角三角形 $L=A\,(x_1,y_0)\,C$ に分かれる。prop-pick-rectangle により $R$ と $U$ は等式を満たすので、lem-pick-additivity により $L$ も満たす。次に $L$ は折れ線 $A\,B\,C$ によって $T$ と四角形 $Q=A\,(x_1,y_0)\,C\,B$ に分かれる（$B$ が $L$ の周上にある場合は、折れ線のうち周上にない部分の線分で分ける）。$Q$ は、$B$ から下ろした縦の線分と $B$ から右へ引いた横の線分によって、直角三角形 $A\,(p,y_0)\,B$、長方形 $[p,x_1]\times[y_0,q]$、直角三角形 $B\,(x_1,q)\,C$ に分かれ、これらはどれも prop-pick-rectangle により等式を満たす。lem-pick-additivity を 2 回使うと $Q$ も等式を満たし、もう一度使うと $L$ と $Q$ から $T$ も等式を満たす。
場合 2：$(x_1,y_1)$ が $T$ の頂点でない場合。$A$ は辺 $x=x_1$ にも辺 $y=y_1$ にも乗らないので、残りの 2 頂点がこの 2 辺に 1 つずつ乗る。$B=(x_1,q)$（$y_0\leq q< y_1$）、$C=(p,y_1)$（$x_0\leq p< x_1$）とする。$R$ は $T$ と、3 つの直角三角形 $W_1=A\,(x_1,y_0)\,B$、$W_2=B\,(x_1,y_1)\,C$、$W_3=C\,(x_0,y_1)\,A$ に分かれ、各 $W_i$ の 2 つの脚は座標軸に平行である。$R$ から線分 $BC$ で $W_2$ を切り離し、残りから線分 $AB$ で $W_1$ を、さらに線分 $CA$ で $W_3$ を切り離すと $T$ が残る。$R$ と各 $W_i$ は prop-pick-rectangle により等式を満たすので、lem-pick-additivity を 3 回使って、切り離したあとの残りの図形が順に等式を満たし、最後に $T$ も満たす。

rem-pick-jordan の平面分離を使う。まず頂点のうち $y$ 座標が最小で、その中で $x$ 座標が最小の $V$ を選ぶと、隣の頂点 $U,W$ が作る角は凸で、その内側は $P$ の内部にある。三角形 $UVW$ に別の頂点がなければ $UW$ が対角線になる。別の頂点があれば、$V$ から辺 $UW$ へ向かう一次関数 $h$ の値が最小の頂点 $X$ を選ぶと、$VX$ が対角線になる。いずれも、候補線分が辺と交わらず内部を通ることを以下で確かめる。

頂点の個数 $n$ に関する数学的帰納法で示す。$n=3$ のときは prop-pick-triangle である。$n\geq4$ とし、頂点が $n$ 個未満の格子多角形については定理が成り立つとする。lem-pick-diagonal により $P$ には対角線 $D$ がある。$D$ は $P$ を 2 つの単純多角形 $P_1$、$P_2$ に分け、その頂点は $P$ の頂点なので $P_1$、$P_2$ は格子多角形である。$P_1$、$P_2$ の頂点の個数を $n_1$、$n_2$ とすると、$D$ の両端が両方で数えられるので $n_1+n_2=n+2$ であり、$n_1,n_2\geq3$ から $n_1,n_2\leq n-1$ である。帰納法の仮定により $P_1$、$P_2$ は定理の等式を満たし、lem-pick-additivity（$\Gamma=D$）により $P$ も満たす。

thm-pick-main により $2\operatorname{Area}(P)=2I(P)+B(P)-2$ は整数である。頂点以外に格子点を含まない三角形では $I=0$、$B=3$ なので、面積は $0+3/2-1=1/2$ である。

そのような正三角形があったとし、1 辺の長さを $s$ とする。2 つの格子点の距離の平方は、三平方の定理による距離の公式から整数なので、$s^2$ は正の整数である。正三角形の面積は $\frac{\sqrt3}{4}s^2$ であり、$\sqrt3$ は無理数なので、これは無理数である。一方 cor-pick-half-integer により面積は有理数であり、矛盾する。

$I_i:=I(H_i)$、$B_i:=B(H_i)$ とおく。$P$ の内部の格子点は、$G$ の境界上にない点、いずれかの $H_i$ の内部の点、いずれかの $\partial H_i$ 上の点のどれか 1 つに当たるので $I(P)=I(G)+\sum_i(I_i+B_i)$ であり、$B(G)=B(P)+\sum_iB_i$ である。thm-pick-main を $P$ と各 $H_i$ に使うと
$$ \operatorname{Area}(G)=\operatorname{Area}(P)-\sum_{i=1}^h\operatorname{Area}(H_i)=\Bigl(I(P)+\frac{B(P)}{2}-1\Bigr)-\sum_{i=1}^h\Bigl(I_i+\frac{B_i}{2}-1\Bigr) $$
であり、$I(P)$ と $B(P)$ を書き換えると
$$ \operatorname{Area}(G)=I(G)+\sum_i(I_i+B_i)+\frac{B(G)-\sum_iB_i}{2}-1-\sum_iI_i-\sum_i\frac{B_i}{2}+h=I(G)+\frac{B(G)}{2}-1+h $$
となる。