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

112

はじめに

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

準備

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

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

曲線 $C$ を有限個の曲線に分割して $C = C_{1} + C_{2} + \dots + C_{n}$ とし、各 $C_{i}$ について条件

(*)

C_{i}

上で

x (t), y (t)

は広義単調^[1]である。

を満たすとする。

C_{i}

の始点を

(x_{i}, y_{i})

、終点を

(x_{i + 1}, y_{i + 1})

とすると、

C

のマンハッタン長

L

は

\begin{array}{r} L = \sum_{i = 1}^{n} {| x_{i + 1} - x_{i} | + | y_{i + 1} - y_{i} |} \end{array}

である。

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

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

定理

定理の主張

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

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

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

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

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

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

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

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

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

証明

証明の流れ

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

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)$ とし、境界を含めたものを $\overset{―}{B (p)}$ とする。また、曲線 $C$ に対し格子点の集合 $V (C)$ を、
$\begin{array}{r} V (C) := {p \in Z^{2} ∣ B (p) \cap C \neq \emptyset} \end{array}$
で定める。

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

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

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

証明

p \notin V (C)

すなわち

B (p) \cap \partial D = \emptyset

と仮定すると、開集合による

D

の分割

\begin{array}{r} B (p) = (B (p) \cap D) \cup (B (p) \cap (D^{c})^{\circ}) \end{array}

が得られる。

B (p)

は連結だから、

B (p) \subset D

または

B (p) \subset (D^{c})^{\circ}

である。後者の場合両辺の閉包を取れば

\overset{―}{B (p)} \subset D^{c}

が得られる。

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

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

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

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

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

$Z^{2}$ 上の半順序 $\leq$ を、
$\begin{array}{r} (x_{1}, y_{1}) \leq (x_{2}, y_{2}) :⟺ x_{1} \leq x_{2} \land y_{1} \leq y_{2} \end{array}$
で定める。 $p, q \in Z^{2}$ に対し、 $p < q :⟺ 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{array}{r} \forall p_{1}, p_{2} \in V (C), p_{1} \leq p_{2} \lor p_{2} \leq p_{1} \end{array}$
が成り立つ。

$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{array}{r} x_{1} - \frac{1}{2} < x (t_{1}) < x_{1} + \frac{1}{2}, x_{2} - \frac{1}{2} < x (t_{2}) < x_{2} + \frac{1}{2} \end{array}$
であるから、
$\begin{aligned} x_{1} - \frac{1}{2} < x (t_{1}) \leq x (t_{2}) < x_{2} + \frac{1}{2} \\ ∴ x_{1} - 1 < x_{2} \\ ∴ x_{1} \leq x_{2} \end{aligned}$
である。同様にして、 $y_{1} \leq y_{2}$ も示される。

定理2

命題4より、
$\begin{array}{r} | S - N | \leq | V (C) | \end{array}$
なので、 $| V (C) | \leq L$ を示せば良い。 $a = t_{0} < t_{1} < \dots < t_{n} = b$ を命題1の条件 $(*)$ を満たす分割とする。 $C_{i}$ を曲線 $C$ の $[t_{i}, t_{i + 1})$ 上の制限とする。 $V (C) = ⋃_{i = 1}^{n} V (C_{i})$ なので、
$\begin{array}{r} | V (C) | \leq \sum_{i = 1}^{n} | V (C_{i}) | \end{array}$
である。 $| V (C_{i}) |$ を上から評価しよう。 $C_{i}$ のパラメータ表示を $x (t), y (t)$ とする。 $x (t), y (t)$ は広義単調増加であるとして一般性を失わない。このとき、 $V (C_{i})$ は $Z^{2}$ の全順序部分集合であるから、
$\begin{array}{r} V (C_{i}) = {p_{1}, p_{2}, \dots, p_{k}}, p_{1} < p_{2} < \dots < p_{k} \end{array}$
とおける。さて、 $p_{j} = (x_{j}, y_{j})$ に対し $n_{j} = x_{j} + y_{j}$ とおくと、 $n_{1} < n_{2} < \dots < n_{k}$ なので、
$\begin{array}{r} n_{k} - n_{1} = \sum_{j = 1}^{k - 1} (n_{j + 1} - n_{j}) \geq k - 1 \end{array}$
である。また、不等式
$\begin{aligned} x_{1} - \frac{1}{2} \leq x (t_{i}) < x_{1} + \frac{1}{2}, & 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}, & y_{k} - \frac{1}{2} < y (t_{i + 1}) \leq y_{k} + \frac{1}{2} (1) \end{aligned}$
に注意すれば、
$\begin{aligned} 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 (2) \end{aligned}$
であるから、
$\begin{array}{r} n_{k} - n_{1} < x (t_{i + 1}) + y (t_{i + 1}) - x (t_{i}) - y (t_{i}) + 2 \end{array}$
である。したがって、
$\begin{array}{r} | V (C_{i}) | = k < x (t_{i + 1}) + y (t_{i + 1}) - x (t_{i}) - y (t_{i}) + 3 \end{array}$
である。これより、
$\begin{array}{r} | V (C) | \leq \sum_{i = 1}^{n} | V (C_{i}) | < L + 3 n \end{array}$
という評価が得られる。

もう少し強い評価を得るために、共通部分 $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{array}{r} μ_{i} := {\begin{cases} 1 & (\exists p \in Z^{2}, x (t_{i + 1}), y (t_{i + 1}) \in B (p)) \\ 0 & (otherwise) \end{cases} \end{array}$
とおけば、
$\begin{array}{r} | V (C) | \leq \sum_{i = 1}^{n} (| V (C_{i}) | - μ_{i}) \end{array}$
となる。 $μ_{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{array}{r} n_{k} = x_{k} + y_{k} < x (t_{i + 1}) + y (t_{i + 1}) \end{array}$
と修正できる。したがって、
$\begin{array}{r} | V (C) | \leq \sum_{i = 1}^{n} (| V (C_{i}) | - μ_{i}) < L + 2 n \end{array}$
が成り立つ。

予想

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

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

$n$ を求めるのは簡単っちゃ簡単ですが、やはり $L$ だけで評価できたほうが便利だよねぇ...

[1]: 広義単調増加または広義単調減少↩

投稿日：3月23日

更新日：3月23日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

dragoemon

148

32815

大学3年生です

他の人のコメント

感想4月1日

さくねこ

厳しく評価すると $| S - N | \leq \begin{array}{r} {\begin{cases} 4 & (0 < L \leq 2) \\ 6 & (2 < L \leq 4) \\ 9 & (4 < L \leq 6) \\ 4 \cdot ⌊ \frac{L}{2} ⌋ & (L > 6) \end{cases} \end{array}$
になりそうですね。閉曲線 $C$ に対して $| V (C) |$ を $C$ の長さ $L$ で評価するところまでは同様の方針で、回りくどいやり方かもしれませんが一応証明したので下に書きます。

定理. $C$ を $R^{2}$ 上の単純閉曲線, 本文同様に $V (C) := {p \in Z^{2} ∣ B (p) \cap C \neq 0}$ , $B (p)$ は格子点 $p \in Z^{2}$ を中心とする一辺 $1$ の正方形の内部とする.
$L$ を $C$ のマンハッタン距離とすると,
$| V (C) | \leq {\begin{cases} 4 & (0 < L \leq 2) \\ 6 & (2 < L \leq 4) \\ 9 & (4 < L \leq 6) \\ 4 \cdot ⌊ \frac{L}{2} ⌋ & (L > 6) \end{cases}$
が成り立つ.

$L \leq 6$ のとき, 定理1は成り立つ.

$V_{x} (C) := {x \in Z ∣ \exists y \in Z (x, y) \in V (C)}, V_{y} (C) := {y \in Z ∣ \exists x \in Z (x, y) \in V (C)}$
（つまり $C$ の通るタイルの $x, y$ 座標）とし，
$w_{x} := max V_{x} (C) - min V_{x} (C) + 1, w_{y} := max V_{y} (C) - min V_{y} (C) + 1$
（つまり $C$ の通るタイル全体の横幅と縦幅）とする.

$C$ を $x, y$ 方向に射影することで, 往復を含めてマンハッタン距離を考えると
$L > 2 (w_{x} - 2) + 2 (w_{y} - 2) = 2 (w_{x} + w_{y}) - 8$ .
また明らかに $| V (C) | \leq w_{x} w_{y}$ . $w_{x}, w_{y}$ が正の整数であることから
$| V (C) | \geq 5$ のとき, $w_{x} w_{y} \geq 5$ より $w_{x} + w_{y} \geq 5, L > 2$ .
$| V (C) | \geq 7$ のとき, $w_{x} w_{y} \geq 7$ より $w_{x} + w_{y} \geq 6, L > 4$ .
$| V (C) | \geq 10$ のとき, $w_{x} w_{y} \geq 10$ より $w_{x} + w_{y} \geq 7, L > 6$ .
それぞれ対偶をとることで示される.

$\bar{V} (C) := {p \in Z^{2} ∣ \overset{―}{B (p)} \cap C \neq 0}$ とする. $L > 6$ のとき,
$C$ がタイルの境界線（つまり、 ${(x, y) \in R^{2} ∣ x + \frac{1}{2} \in Z \lor y + \frac{1}{2} \in Z}$ ）に含まれるような場合について $| \bar{V} (C) | \leq 4 \cdot ⌊ \frac{L}{2} ⌋$ を示せば定理1は成り立つ.

明らかに $| V (C) | \leq | \bar{V} (C) |$ であり，
$C$ が格子の線に含まれない場合は, $L$ を増やさず $| \bar{V} (C) |$ を減らさないように以下のように $C$ を変形できることからよい.
（すなわち変形後の $C$ を $C^{'}$ , $L$ を $L^{'}$ , 定理の右辺を $f (L)$ と書くことにすれば, $| \bar{V} (C) | \leq | \bar{V} (C^{'}) | \leq f (L^{'}) \leq f (L)$ となって変形前でも成り立つことがわかる.）
・各 $p \in Z^{2}$ に対し $B (p)$ の内部の $C$ をそれぞれ変形する.
・入る点と出る点が同じ辺であれば, それを直線で繋ぐような経路に変形する.
・入る点と出る点が隣接する辺であれば, それを辺に沿って最短経路でつなぐような経路に変形する.
・入る点と出る点が向かい合う辺であれば、隣接するタイルについて先に変形し、それに合わせて変形する.
（説明を端折っていますが, 入る点と出る点が隣接する辺であるような経路がない場合などでも適宜似たような変形ができます.）
変形例

補題2において、さらに $C$ として以下に示すような経路を含まないもののみを考慮すればよい:
・辺の途中で戻るような経路
・頂点で180度向きを変えて戻るような経路
・頂点で同じ方向に90度向きを変えて進むのが2回続くような経路
経路

辺の途中で戻るような経路を含む場合は、単に往復する部分を削除してやれば（補題2と同様に $L$ を増やさず $| \bar{V} (C) |$ を減らさないので）問題ない.
残りの2種類の経路を含む場合は、下のように変形してやるとどちらの場合でも $L$ はちょうど2減るのに対して $| \bar{V} (C) |$ は高々3しか減らないことがわかる.
画像の名前
補題3同様に変形後の $C$ を $C^{'}$ , $L$ を $L^{'} (= L - 2)$ と書くと、変形後の $L^{'}$ は $4 < L^{'} \leq 6$ となりうることに注意すると, 補題1と合わせて
$| \bar{V} (C) | \leq | \bar{V} (C^{'}) | + 3 \leq (4 \cdot ⌊ \frac{L^{'}}{2} ⌋ + 1) + 3 = 4 \cdot ⌊ \frac{L}{2} ⌋$
となって変形前でも成り立つことがわかる.

補題4のもとで、補題3は正しい.

$C$ を頂点（経路が折れ曲がっている点）で分割し、各線分に対し下図の赤線で囲まれたような領域を割り当てる.（補題4の制限から各線分の長さは2以上であることに注意.）
画像の名前
各領域の面積は各線分の長さの2倍であるから, 明らかにそのような領域の面積の和は $2 L$ で、しかも $\bar{V} (C)$ を覆う. よって $| \bar{V} (C) | \leq 2 L = 4 \cdot ⌊ \frac{L}{2} ⌋$ .
（最後の等号は $C$ がタイルの境界線上を通るから, $L$ が偶数であることにより従う.）

長文失礼しました.

dragoemon

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

はじめに
準備
定理
定理の主張
証明
証明の流れ
Step 1. $| S - N |$ を曲線に近い格子点の個数 $| V (C) |$ で評価
Step 2. $| V (C) |$ をマンハッタン長 $L$ で評価
予想

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

はじめに

準備

定理

定理の主張

証明

証明の流れ

Step 1

Step 2

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

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

予想

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

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

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