格子点の個数を面積で評価する

139

はじめに

与えられた領域内の格子点の個数を、面積を使って大まかに評価したいときってありますよね。特に高校数学では積分の応用例とかでよく登場しますね。個人的には整数論でMinkowski空間とかを考える際にこういうことをしたくなります。格子多角形に限定するとピックの定理が有名ですが、一般の領域でこの状況を包括的に扱える道具がありそうで見つからなかったので、作ってみることにしました。これを使うと、多くの図形で面積$S$と格子点の個数$N$の差を、周長$L$を使って
$$ |S - N| = O(L) \quad (L \to \infty) $$
という形で評価できます。(ランダウの記号)

準備

区分的になめらかな曲線$C: [a, b] \mapsto (x(t), y(t))$に対して、そのマンハッタン長$L$を、
\begin{align} L = \int_{a}^{b} |x'(t)| dt + \int_{a}^{b} |y'(t)| dt \end{align}
で定める。これは$L^1$ノルム空間$(\R^2, \|\cdot\|_1)$における曲線の長さである。

馴染みない概念かもしれません。実際ふつうの弧長を使っても良かったのですが、マンハッタン長$L$は通常の長さよりも簡単に計算できるので使いやすい方を選びました。たとえば、楕円$\frac{x^2}{a^2} + \frac{y^2}{b^2} = 1$の長さは、
\begin{align} 4a\int_{0}^{\pi/2} \sqrt{1 - e^2\sin^2\theta} d\theta, \quad e = \sqrt{1 - \frac{b^2}{a^2}} \end{align}
と複雑ですが、マンハッタン長は
\begin{align} 4a + 4b \end{align}
となります。これは次の命題からわかります。証明は簡単なので省略します。

曲線$C$を有限個の曲線に分割して$C = C_1 + C_2 + \cdots + C_n$とし、各$C_i$について条件

$(\ast)$ $C_i$上で$x(t), y(t)$は広義単調^[1]である。

を満たすとする。$C_i$の始点を$(x_i, y_i)$、終点を$(x_{i+1}, y_{i+1})$とすると、$C$のマンハッタン長$L$は
\begin{align} L = \sum_{i=1}^{n} \{ |x_{i+1} - x_i| + |y_{i+1} - y_i| \} \end{align}
である。

曲線$C$に対し、$x(t)$または$y(t)$が極値をとる$t$の個数を$n$とする。これを単に$C$の極値の個数という。

極値とか言ってますが、命題1の条件$(\ast)$を満たす分割がとれるような$n$であればなんでもよいです。

定理

定理の主張

今回証明したいのが次の定理です。

$D \subset \R^2$が面積$S$をもつ有界領域で、その境界$C := \partial D$が区分的になめらかな閉曲線であるとする。$C$のマンハッタン長$L$と極値の個数$n$が有限のとき、内部の格子点の数$N$について、
$$|S - N| < L + 2n$$
が成り立つ。

証明は後回しにして系を紹介しましょう。少し弱い評価になってしまいますが、通常の意味での弧長で評価することもできます。

$D \subset \R^2$が面積$S$をもつ有界領域で、その境界$C := \partial D$が区分的になめらかな閉曲線であるとする。$C$の弧長$L'$と極値の個数$n$が有限のとき、内部の格子点の数$N$について、
\begin{align} |S - N| < 2L' + 2n \end{align}

\begin{align} L = \int_{a}^{b} |x'(t)| + |y'(t)| dt \leq \int_{a}^{b} 2 \sqrt{x'(t)^2 + y'(t)^2} dt = 2 L' \end{align}
であるから従う。

次はよくある設定ですね。

$D \subset \R^2$が面積$S$をもつ有界領域で、その境界$C := \partial D$が区分的になめらかな閉曲線であるとする。定数$r > 0$に対し、
\begin{align} rD := \{ (rx, ry) \mid (x, y) \in D \} \end{align}
とする。$rD$に含まれる格子点の数を$N_r$とすると、
\begin{align} \lim_{r \to \infty} \frac{N_r}{r^2} = S \end{align}
が成り立つ。

また、凸領域については次の評価が得られます。これについては単純に積分とかすれば証明できそうな気もします...

$D \subset \R^2$が面積$S$をもつ有界凸領域で、その境界$C := \partial D$が区分的になめらかな曲線であるとする。
\begin{align} L = \max_{(x, y) \in C} x - \min_{(x, y) \in C} x + \max_{(x, y) \in C} y - \min_{(x, y) \in C} y \end{align}
とする。（$L = $横幅+縦幅）このとき、内部の格子点の数$N$について、
\begin{align} |S - N| < 2L + 8 \end{align}

証明

証明の流れ

まずは証明の流れを説明します。

Step 1

各格子点に対して、それを中心とする一辺1の正方形のタイルを考えると、これらで平面全体を埋め尽くすことができます。そして、これらのタイルは次の3つに分けることができますね。

完全に$D$の内側にあるもの
部分的に$D$に入っているもの (すなわち曲線$C$と交わるもの)
完全に$D$の外側にあるもの

(1),(2)の正方形の個数を$N_1, N_2$とすれば、面積は$N_1 \leq S \leq N_1 + N_2$を満たします。このことから、$D$内にある格子点の数$N$について$|S - N| \leq N_2$という評価ができます。

Step 2

(2)のタイルの個数$N_2$をマンハッタン長$L$を使って評価します。長さ$L < \infty$の曲線が踏めるタイルの数はもちろん有限なので上から評価できるはずです。ここが一番大変で、改善の余地があるところです。

Step 1. $|S-N|$を曲線に近い格子点の個数$|V(C)|$で評価

各格子点$p \in \Z^2$に対して、$p$を中心とする一辺$1$の正方形の内部を$B(p)$とし、境界を含めたものを$\overline{B(p)}$とする。また、曲線$C$に対し格子点の集合$V(C)$を、
\begin{align} V(C) := \{p \in \Z^2 \mid B(p) \cap C \neq \emptyset\} \end{align}
で定める。

$C = \partial D$とする。格子点$p \in \Z^2$が$p \not\in V(C)$をみたすとき、次のいずれか一方が成り立つ。

$B(p) \subset D$である。
$\overline{B(p)} \subset D^c$である。

「$D$の境界$C$と交わらない正方形は、$D$の完全に内側にあるか外側にあるかだよ」と言っています。そりゃそうですね。

証明

$p \not\in V(C)$すなわち$B(p) \cap \partial D = \emptyset$と仮定すると、開集合による$D$の分割
\begin{align} B(p) = (B(p) \cap D) \cup (B(p) \cap (D^c)^{\circ}) \end{align}
が得られる。$B(p)$は連結だから、$B(p) \subset D$または$B(p) \subset (D^c)^\circ$である。後者の場合両辺の閉包を取れば$\overline{B(p)} \subset D^c$が得られる。

定理2の条件の下で、
\begin{align} |S - N| \leq |V(C)| \end{align}

$V(C)$を2つの集合$X, Y$に分割する。
\begin{align} X = V(C) \cap D, \quad Y = V(C) \cap D^c \end{align}
補題3より次が成り立つ。

$p \in (D \cap \Z^2) \setminus X$に対して、$B(p) \subset D$である。
$p \in (D^c \cap \Z^2) \setminus Y$に対して、$\overline{B(p)} \subset D^c$である。

したがって、$\R^2 = \bigcup_{p \in \Z^2} \overline{B(p)}$に注意すれば、
\begin{align} \bigcup_{p \in (D \cap \Z^2) \setminus X} B(p) \subset D \subset \bigcup_{p \in (D \cap \Z^2) \cup Y} \overline{B(p)} \end{align}
であるから、次の不等式が成り立つ。
\begin{align} N - |X| \leq S \leq N + |Y| \end{align}
よって、
\begin{align} |S - N| \leq |X| + |Y| = |V(C)| \end{align}
である。

Step 2. $|V(C)|$をマンハッタン長$L$で評価

$\Z^2$上の半順序$\leq$を、
\begin{align} (x_1, y_1) \leq (x_2, y_2) :\Longleftrightarrow x_1 \leq x_2 \land y_1 \leq y_2 \end{align}
で定める。$p, q \in \Z^2$に対し、$p < q :\Longleftrightarrow p \leq q \land p \neq q$とする。

曲線$C : [a, b] \mapsto c(t) = (x(t), y(t))$に対し、$x(t), y(t)$は広義単調増加であるとする。$V(C)$は$\Z^2$の全順序部分集合である。すなわち、
\begin{align} \forall p_1, p_2 \in V(C), \quad p_1 \leq p_2 \lor p_2 \leq p_1 \end{align}
が成り立つ。

$p_1, p_2 \in V(C)$をとる。$c(t_1) = p_1, c(t_2) = p_2$となる$t_1, t_2 \in [a, b]$をとる。$t_1 \leq t_2$として一般性を失わない。$p_1 = (x_1, y_1), p_2 = (x_2, y_2)$とする。このとき、
\begin{align} x_1 - \frac{1}{2} < x(t_1) < x_1 + \frac{1}{2}, \quad x_2 - \frac{1}{2} < x(t_2) < x_2 + \frac{1}{2} \end{align}
であるから、
\begin{align} & x_1 - \frac{1}{2} < x(t_1) \leq x(t_2) < x_2 + \frac{1}{2} \\ & \therefore x_1 - 1 < x_2 \\ & \therefore x_1 \leq x_2 \end{align}
である。同様にして、$y_1 \leq y_2$も示される。

定理2

命題4より、
\begin{align} |S - N| \leq |V(C)| \end{align}
なので、$|V(C)| \leq L$を示せば良い。$a = t_0 < t_1 < \cdots < t_n = b$を命題1の条件$(\ast)$を満たす分割とする。$C_i$を曲線$C$の$[t_i, t_{i+1})$上の制限とする。$V(C) = \bigcup_{i=1}^{n} V(C_i)$なので、
\begin{align} |V(C)| \leq \sum_{i=1}^{n} |V(C_i)| \end{align}
である。$|V(C_i)|$を上から評価しよう。$C_i$のパラメータ表示を$x(t), y(t)$とする。$x(t), y(t)$は広義単調増加であるとして一般性を失わない。このとき、$V(C_i)$は$\Z^2$の全順序部分集合であるから、
\begin{align} V(C_i) = \{ p_1, p_2, \ldots, p_k \}, \quad p_1 < p_2 < \cdots < p_k \end{align}
とおける。さて、$p_j = (x_j, y_j)$に対し$n_j = x_j + y_j$とおくと、$n_1 < n_2 < \cdots < n_k$なので、
\begin{align} n_k - n_1 = \sum_{j=1}^{k-1} (n_{j+1} - n_j) \geq k - 1 \end{align}
である。また、不等式
\begin{align} x_1 - \frac{1}{2} \leq x(t_i) < x_1 + \frac{1}{2}, &\quad y_1 - \frac{1}{2} \leq y(t_i) < y_1 + \frac{1}{2} \\ x_k - \frac{1}{2} < x(t_{i+1}) \leq x_k + \frac{1}{2}, &\quad y_k - \frac{1}{2} < y(t_{i+1}) \leq y_k + \frac{1}{2} \qquad (1) \end{align}
に注意すれば、
\begin{align} n_1 &= x_1 + y_1 > x(t_i) + y(t_i) - 1 \\ n_k &= x_k + y_k < x(t_{i+1}) + y(t_{i+1}) + 1 \qquad\qquad (2) \end{align}
であるから、
\begin{align} n_k - n_1 < x(t_{i+1}) + y(t_{i+1}) - x(t_i) - y(t_i) + 2 \end{align}
である。したがって、
\begin{align} |V(C_i)| = k < x(t_{i+1}) + y(t_{i+1}) - x(t_i) - y(t_i) + 3 \end{align}
である。これより、
\begin{align} |V(C)| \leq \sum_{i=1}^{n} |V(C_i)| < L + 3n \end{align}
という評価が得られる。

もう少し強い評価を得るために、共通部分$V(C_i) \cap V(C_{i+1})$について考えよう。もし格子点$p \in \Z^2$があって、$(x(t_{i+1}), y(t_{i+1})) \in B(p)$であれば、$p \in V(C_i) \cap V(C_{i+1})$である。よって、
\begin{align} \mu_i := \begin{cases} 1 & (\exists p \in \Z^2, x(t_{i+1}), y(t_{i+1}) \in B(p)) \\ 0 & (\text{otherwise}) \end{cases} \end{align}
とおけば、
\begin{align} |V(C)| \leq \sum_{i=1}^{n} (|V(C_i)| - \mu_i) \end{align}
となる。$\mu_i = 0$のとき、$x(t_{i+1}), y(t_{i+1})$のいずれかは半整数である。$x(t_{i+1})$が半整数なら、式(1)の不等式$x_k - \frac{1}{2} < x(t_{i+1})$は$x_k + \frac{1}{2} \leq x(t_{i+1})$と修正される。したがって式(2)は
\begin{align} n_k = x_k + y_k < x(t_{i+1}) + y(t_{i+1}) \end{align}
と修正できる。したがって、
\begin{align} |V(C)| \leq \sum_{i=1}^{n} (|V(C_i)| - \mu_i) < L + 2n \end{align}
が成り立つ。

予想

最後に予想を紹介します。

$D \subset \R^2$が面積$S$の領域で、その境界$C := \partial D$が閉曲線であるとする。$C$のマンハッタン長$L$が有限のとき、
$D$内部の格子点の数$N$について、
\begin{align} |S - N| \leq 2L + 4 \end{align}
が成り立つ。