2018-01-09

ハイパーグラフ除去補題ー１

この記事から複数記事用いて「ハイパーグラフ除去補題」の証明を行います。

参考文献
T. Tao, A variant of the hypergraph removal lemma, J. Combin. Theory Ser. A 113 (2006), 1257–1280.
T. Tao, The Gaussian primes contain arbitrarily shaped constellations, J. Anal. Math. 99 (2006), 109–176.

多次元版Szemerédiの定理

正整数 $N$ に対して、 $[-N, N]:=\{n \in \mathbb{Z} \mid -N \leq n \leq N\}$ とする。また、 $d$ を正整数として、集合 $A \subset \mathbb{Z}^d$ の上漸近密度 $\overline{d}(A)$ を

$\displaystyle \overline{d}(A) := \limsup_{N \to \infty}\frac{\#\{A \cap [-N, N]^d\}}{\#[-N, N]^d}$

で定義する。 $\mathbb{Z}^d$ 内の形状とは $\mathbb{Z}^d$ の相異なる点の有限族 $(v_j)_{j \in J}$ のことをいう。すなわち、 $J$ は有限集合で、 $v_j \in \mathbb{Z}^d$ である。形状が $(v_j)_{j \in J}$ である星座とは $a \in \mathbb{Z}^d, r \in \mathbb{Z}_{> 0}$ を用いて $(a+rv_j)_{j \in J}$ と表される有限族のことをいう。

多次元版Szemerédiの定理 (Furstenberg-Katznelson) $A \subset \mathbb{Z}^d$ を上漸近密度が正であるような集合とする。このとき、任意の $\mathbb{Z}^d$ 内の形状 $(v_j)_{j \in J}$ に対して、構成する点が全て $A$ の元であるような、形状が $(v_j)_{j \in J}$ である星座が無数に存在する。

これは一応今回の主役ではないが、副産物として証明される。

有限加法群に対するSzemerédiの定理

空でない有限集合 $Z$ と関数 $f\colon Z \to \mathbb{R}$ に対して、期待値を

$\displaystyle \mathbb{E}(f) = \mathbb{E}(f \mid Z) = \mathbb{E}(f(x) \mid x \in Z) := \frac{1}{\#Z}\sum_{x \in Z}f(x)$

と定義する。これまで同様ビッグオー記号やスモールオー記号を使用する。 $o_{x \to 0}(X)$ は絶対値が或る $c(x)X$ で押さえられて、 $\displaystyle \lim_{x \to 0}c(x)=0$ が成り立つ。 $c(x)$ の $x$ 以外の依存パラメータを $o_{x \to 0; y_1, \dots, y_m}$ のように添え字を付ける形で表す。 $\mathbf{1}_{\bullet}$ は特性関数。

有限加法群に対するSzemerédiの定理 $Z, Z'$ を有限加法群とし、 $(\phi_j)_{j \in J}$ を群準同型 $\phi_j\colon Z \to Z'$ の有限族とする。集合 $A \subset Z'$ が $0 < \delta < 1$ に対して

$\displaystyle \left.\mathbb{E}\left(\prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \delta$

を満たすならば、

$\displaystyle \mathbb{E}(\mathbf{1}_A(x) \mid x \in Z') = o_{\delta \to 0; \#J}(1)$

が成り立つ。

正整数 $N$ に対して、 $\mathbb{Z}_N := \mathbb{Z}/N\mathbb{Z}$ とする。

有限加法群に対する多次元Szemerédi $\Longrightarrow$ 多次元版Szemerédiの定理の証明. 任意の形状について、それを含むような(集合として)より大きな形状に対して多次元版Szemerédiの定理の主張を証明できればよい。よって、任意に整数 $M \geq 3$ をとって、 $[-M, M]^d$ の元達からなる形状に対して証明する。また、この形状は原点対称であるから、 $r$ としては零でないことを保証できればよい。 $\overline{d}(A) = \sigma > 0$ とすると、 $A(N):=A \cap [-N, N]^d$ とするとき $\#A(N) \geq \frac{\sigma}{2}\#[-N, N]^d$ が成り立つようないくらでも大きい整数 $N$ が存在する。そのような $N$ をとって固定し、 $N' := 6MN$ とする。 $Z:=\mathbb{Z}_{N'}, \ Z':=\mathbb{Z}_{N'}^d$ とする(これらは有限加法群である)。 $v \in [-M, M]^d$ に対して、群準同型写像 $\phi_v\colon Z \to Z'$ を $\phi_v(r'):=r'v$ と定める。 $\pi_{N'}$ で標準射影 $\mathbb{Z} \to \mathbb{Z}_{N'}$ および $\mathbb{Z}^d \to \mathbb{Z}_{N'}^d$ を表す $\iota := \left.\pi_{N'}\right|_{[-N, N]^d} \colon \mathbb{Z}^d \to \mathbb{Z}_{N'}^d$ は単射である。 $A':=\iota(A(N) ) \subset Z'$ とする。このとき、

$\displaystyle \mathbb{E}(\mathbf{1}_{A'}(x) \mid x \in Z') = \frac{\#A(N)}{\#Z'} \gg_{d, M} \sigma$

である。よって、有限加法群に対するSzemerédiの定理より、 $d, M, \sigma$ のみに依存する $\delta > 0$ が存在して

$\displaystyle \left.\mathbb{E}\left(\prod_{v \in [-M, M]^d}\mathbf{1}_{A'}(x+r'v) \ \right| \ x \in Z', r' \in Z\right) > \delta$

でなければならない。すなわち、任意の $v \in [-M, M]^d$ に対して $x+r'v \in A'$ となるような $(x, r') \in Z' \times Z$ が少なくとも $\delta (N')^{d+1}$ 個存在する。そのような $(x, r')$ のうち、 $r' \neq 0$ であるようなものをとる( $r'=0$ であるようなものは高々 $(N')^d$ 個しかないので、 $\delta$ は $N$ には依存しないことに注意して、 $N$ を十分大きくとれば $r' \neq 0$ であるようなものが存在しなくてはならないことがわかる)。 $0 \in [-M, M]^d$ なので、 $x \in A'$ であり、 $a:=\iota^{-1}(x) \in A(N)$ と定める。 $a \in [-N, N]^d$ である。次に、 $e_1:=(1, 0, \dots, 0) \in [-M, M]^d$ を考えて、 $r:=\mathrm{pr}_1(\iota^{-1}(x+r'e_1)-a) \in \mathbb{Z}$ と定める( $\mathrm{pr}_1$ は第一成分を取り出す射影)。このとき、 $r \in [-2N, 2N]$ である。第一成分を取り出すことと $\pi_{N'}$ をとることは可換であることから、 $\pi_{N'}(r) = r'$ である。従って、任意の $v \in [-M, M]^d$ に対して $\pi_{N'}(a+rv) = x+r'v$ が成り立つ。一方、 $\iota^{-1}(x+r'v) \in [-N, N]^d$ であることから、

$(a+rv)-\iota^{-1}(x+r'v) \in (-3MN, 3MN)^d$

が成り立つ。よって、 $N'$ の取り方から、任意の $v \in [-M, M]^d$ に対して $a+rv=\iota^{-1}(x+r'v') \in A(N)$ が示された。 $r'\neq 0$ であることから $r \neq 0$ である。 $N \to \infty$ とすることによって、所望の星座が無数に存在することもわかる。 Q.E.D.

ハイパーグラフ

グラフの辺は二頂点を結ぶものであるが、複数の頂点を連結させたハイパーエッジを考えたものをハイパーグラフという。

ハイパーグラフ - Wikipedia

ここでは、連結させる頂点の個数を一定にしたハイパーグラフのみを扱う。

定義１ $J$ を有限集合とし、 $d \geq 0$ を整数とする。このとき、 $\binom{J}{d}$ を

$\displaystyle \binom{J}{d} := \{e \subset J \mid \#e = d\}$

と定義する。 $\binom{J}{d}$ の部分集合 $H$ のことを、 $d$ 一様ハイパーグラフという。

$2$ 一様ハイパーグラフが通常のグラフである。

定義２ ハイパーグラフ系とは４つ組 $V=(J, (V_j)_{j \in J}, d, H)$ であって、 $J$ : 有限集合、 $(V_j)_{j \in J}$ : 空でない有限集合の族、 $d \geq 1$ 、 $H \subset \binom{J}{d}$ : $d$ 一様ハイパーグラフであるようなものをいう。 $e \subset J$ に対して、 $\displaystyle V_e:=\prod_{j \in e}V_j$ と定義し、標準射影を $\pi_e\colon V_J \twoheadrightarrow V_e$ とする。 $e \subset J$ に対して、 $V_J$ 上の $\sigma$ 加法族 $\mathcal{A}_e$ を $\displaystyle \mathcal{A}_e := \{\pi_e^{-1}(E) \mid E \subset V_e\}$ で定義する。

有限集合上の $\sigma$ 加法族に関する基礎知識は仮定する( $\mathbb{Z}_N$ で記述していたが、有限集合上の $\sigma$ 加法族に関する一般論を展開しているため、 $V_J$ としても同様のことが成り立つ): タオのセメレディ論文の§6を読む (その一) - INTEGERS

定義３ $V=(J, (V_j)_{j \in J}, d, H)$ をハイパーグラフ系として、 $\mathcal{B}$ を $V_J$ 上の $\sigma$ 加法族とする。このとき、 $\mathcal{B}$ の複雑度 $\mathrm{cpx}(\mathcal{B})$ を、 $\mathcal{B}$ を $\sigma$ 加法族として生成する集合の個数の最小値と定める。

定義から明らかに

$\mathrm{cpx}(\mathcal{B}_1 \vee \mathcal{B}_2) \leq \mathrm{cpx}(\mathcal{B}_1)+\mathrm{cpx}(\mathcal{B}_2)$

が成り立つ( $\vee$ は $\sigma$ 加法族の合併)。 $\mathcal{B}$ のアトム全体のなす集合を $\mathrm{Atom}(\mathcal{B})$ で表すと、

$\displaystyle \#\mathcal{B} \leq 2^{\#\mathrm{Atom}(\mathcal{B})} \leq 2^{2^{\mathrm{cpx}(\mathcal{B})}}$

なる評価ができることがわかる。

ハイパーグラフ除去補題

次が今回の主定理：

定理 (ハイパーグラフ除去補題) $V=(J, (V_j)_{j \in J}, d, H)$ をハイパーグラフ系とする。ハイパーエッジ $e \in H$ 毎に $E_e \in \mathcal{A}_e$ であって、 $0 < \delta < 1$ に対して

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}\mathbf{1}_{E_e}(x) \ \right| \ x \in V_J\right) \leq \delta$

が成り立つようなものをとる。このとき、各 $e \in H$ に対して或る $E_e' \in \mathcal{A}_e$ が存在して

$\displaystyle \bigcap_{e \in H}E_e' = \emptyset,$

$\displaystyle \mathbb{E}\left(\mathbf{1}_{E_e \setminus E_e'}(x) \mid x \in V_J\right) = o_{\delta \to 0; \#J}(1)$

が成り立つ。更に、 $e' \subset J, \ \#e' < d$ に対して部分 $\sigma$ 加法族 $\mathcal{B}_{e'} \subset \mathcal{A}_{e'}$ が存在して、

$\mathrm{cpx}(\mathcal{B}_{e'}) = O_{\delta, \#J}(1)$

かつ任意の $e \in H$ に対して

$\displaystyle E_e' \in \bigvee_{e' \subsetneq e}\mathcal{B}_{e'}$

が成り立つ。

$\sigma$ 加法族の複雑度の評価から、 $\#\mathcal{B}_{e'} = O_{\delta, \#J}(1)$ が成り立つことに注意。

ハイパーグラフ除去補題 $\Longrightarrow$ 有限加法群に対するSzemerédiの定理の証明. 最初に $Z'$ が

$\displaystyle \{\phi_i(r)-\phi_j(r) \mid i, j \in J, r \in Z\}$

で生成されている場合に証明する。

$\displaystyle \left.\mathbb{E}\left(\prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \delta$

を仮定する。 $\#J \geq 2$ としてよい*1。このとき、ハイパーグラフ系 $V=(J, (V_j)_{j \in J}, d, H)$ を $V_j = Z \ ({}^{\forall}j \in J)$ , $d=\#J-1$ , $H=\binom{J}{d}$ と定める。 $e = J \setminus \{j\} \in H$ に対して $E_e \subset V_J=Z^J$ を

$\displaystyle E_e:=\left\{(x_i)_{i \in J} \in Z^J \ \left| \ \sum_{i \in J}\left(\phi_i(x_i)-\phi_j(x_i)\right) \in A\right\}\right.$

と定義する。 $\sum_{i \in J}\left(\phi_i(x_i)-\phi_j(x_i)\right)$ は $x_j$ に依存しないため、 $E_e \in \mathcal{A}_e$ であることがわかる。群準同型 $\Phi \colon V_J \to Z' \times Z$ を

$\displaystyle \Phi ( (x_i)_{i \in J}) := \left(\sum_{i \in J}\phi_i(x_i), -\sum_{i \in J}x_i\right)$

と定める。このとき、

$\displaystyle \bigcap_{e \in H}E_e = \Phi^{-1}\left(\{(x, r) \in Z'\times Z \mid x+\phi_j(r) \in A, \ {}^{\forall}j \in J\}\right)$ −①

が成り立つ。 $\Phi$ は全射である。理由: $\mathrm{Im}(\Phi)$ は任意の $i, j \in J, r \in Z$ に対して $(\phi_i(r)-\phi_j(r), 0)$ を含む*2。よって、最初に設けた仮定より $Z'\times \{0\} \subset \mathrm{Im}(\Phi)$ がわかる。また、任意の $j \in J, r \in Z$ に対して $(-\phi_j(r), r) \in \mathrm{Im}(\Phi)$ でもある*3。すると、任意の $(x, r) \in Z' \times Z$ に対して、 $\Phi(\mathbf{x}_j)=(x+\phi_j(r), 0)$ , $\Phi(\mathbf{y}_j) = (-\phi_j(r), r)$ となるような $\mathbf{x}_j, \mathbf{y}_j$ を取れば( $j$ は何でもよい)、 $\Phi(\mathbf{x}_j+\mathbf{y}_j) = (x, r)$ となる。

よって、 $\Phi$ は群準同型であることから $Z'$ の $Z'\times Z$ による一様被覆なのでGT1,4の補題を適用でき、

$\displaystyle \mathbf{x} \in \Phi^{-1}\left(\{(x, r) \in Z'\times Z \mid x+\phi_j(r) \in A, \ {}^{\forall}j \in J\}\right) \Longleftrightarrow \prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) = 1 \ (\Phi(\mathbf{x}) = (x, r) )$

であることから①と仮定より

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}\mathbf{1}_{E_e}(\mathbf{x}) \ \right| \ \mathbf{x} \in V_J\right) = \left.\mathbb{E}\left(\prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \delta$

を得る。よって、ハイパーグラフ除去補題より $e \in H$ 毎に $E_e' \in \mathcal{A}_e$ が存在して、

$\displaystyle \bigcap_{e \in H}E_e' = \emptyset$ −②

および

$\displaystyle \#(E_e \setminus E_e') = o_{\delta \to 0; \#J}(\#V_J) \quad ({}^{\forall}e \in H)$

が成り立つ(後半は期待値の定義よりわかる)。なお、多次元Szemerédiの導出には $\sigma$ 加法族の複雑度に関する主張は不要である。①より

$\displaystyle \Phi^{-1}(A \times \{0\}) \subset \bigcap_{e \in H}E_e$

なので、これと②より

$\displaystyle \Phi^{-1}(A \times \{0\}) \subset \bigcup_{e \in H}(E_e \setminus E_e')$

が成り立つ。よって、或る $e = J\setminus \{j\}$ が存在して

$\displaystyle \#\{(E_e\setminus E_e') \cap \Phi^{-1}(A \times \{0\})\} \geq \frac{\#\Phi^{-1}(A \times \{0\})}{\#J}$ −③

となる(以下、固定)。理由: そのような $e$ が存在しなかったと仮定すると、 $\#H = \#J$ に注意して

$\begin{align}\#\Phi^{-1}(A \times \{0\}) &= \#\left\{\bigcup_{e \in H}(E_e \setminus E_e') \cap \Phi^{-1}(A \times \{0\})\right\} \\ &\leq \sum_{e \in H} \#\{(E_e\setminus E_e') \cap \Phi^{-1}(A \times \{0\})\} < \#H\cdot \frac{\#\Phi^{-1}(A \times \{0\})}{\#J} = \#\Phi^{-1}(A \times \{0\})\end{align}$

となって矛盾する。

$\Phi^{-1}(A \times \{0\})$ は超平面 $\{(x_i)_{i \in J} \mid \sum_{i \in J}x_i=0\}$ に含まれているので、 $\pi_e\colon V_J \to V_e$ は $V_e$ の各点で $\#Z$ 重になっているが、制限写像 $\left.\pi_e\right|_{\Phi^{-1}(A\times \{0\})}$ は単射となる。よって、 $E_e\setminus E_e' \in \mathcal{A}_e$ に注意して、

$\displaystyle \#\{(E_e\setminus E_e') \cap \Phi^{-1}(A\times \{0\})\} \leq \frac{\#(E_e\setminus E_e')}{\#Z} = o_{\delta \to 0; \#J}(\#V_J/\#Z)$ −④

が成り立つ。 $\Phi$ の全射性から

$\displaystyle \frac{\#\Phi^{-1}(A \times \{0\})}{\#V_J} = \frac{\#A}{\#(Z'\times Z)} = \frac{\#A}{\#Z\cdot \#Z'}$

である。③と④を合わせると

$\displaystyle \#A = \#Z\cdot \#Z' \cdot \frac{\#\Phi^{-1}(A\times \{0\})}{\#V_J} \leq \#Z\cdot \#Z' \cdot \frac{\#J\cdot \#\{(E_e\setminus E_e') \cap \Phi^{-1}(A\times \{0\})\}}{\#V_J} \leq o_{\delta \to 0; \#J}(\#Z')$

となって所望の漸近挙動に到達する。以下、最初に設けた仮定をはずす。 $J^{\ast}:=J\sqcup \{\bullet\}$ とし、 $\phi_{\bullet}\colon Z \to Z'$ をゼロ写像とする。 $G$ を

$\displaystyle \{\phi_i(r)-\phi_j(r) \mid i, j \in J^{\ast}, r \in Z\}$

が生成する $Z'$ の部分群とする。 $Z'/G$ の代表系 $\mathcal{R}$ を一つとる。 $y \in \mathcal{R}$ に対して

$\displaystyle \mathbb{E}_y := \left.\mathbb{E}\left(\prod_{j \in J^{\ast}}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in y+G, r \in Z\right)$

とすると、

$\displaystyle \mathbb{E}(\mathbb{E}_y \mid y \in \mathcal{R}) = \left.\mathbb{E}\left(\prod_{j \in J^{\ast}}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \left.\mathbb{E}\left(\prod_{j \in J}\mathbf{1}_A(x+\phi_j(r) ) \ \right| \ x \in Z', r \in Z\right) \leq \delta$

となる。これより、高々 $O(\sqrt{\delta}\#Z'/\#G)$ 個の例外を除く $y \in \mathcal{R}$ に対して $\mathbb{E}_y \leq \sqrt{\delta}$ が成り立つ。理由: $\mathbb{E}_y > \sqrt{\delta}$ が成り立つような $y \in \mathcal{R}$ の個数が $\sqrt{\delta}\#Z'/\#G$ より大きかったとする。すると、

$\displaystyle \mathbb{E}(\mathbb{E}_y \mid y \in \mathcal{R}) \geq \frac{\#G}{\#Z'}\sum_{\substack{y \in \mathcal{R} \\ \mathbb{E}_y > \sqrt{\delta}}}\mathbb{E}_y > \frac{\#G}{\#Z'}\cdot \frac{\sqrt{\delta}\#Z'}{\#G} \cdot \sqrt{\delta} = \delta$

となって矛盾する。 $\mathbb{E}_y \leq \sqrt{\delta}$ なる $y$ について、最初のケースを $Z' \mapsto G$ , $A \mapsto (A-y) \cap G$ として適用すると( $J^{\ast}$ を考えたことによって $\phi_j$ の像が $G$ となって適用可能であることが分かる)

$\displaystyle \#\{A \cap (y+G)\} = \#\{(A-y) \cap G\} = o_{\sqrt{\delta} \to 0; \#J}(\#G)$

が得られる。よって、

$\displaystyle \#A \leq o_{\sqrt{\delta} \to 0; \#J}(\#G) \cdot \frac{\#Z'}{\#G} + \#G\cdot O\left(\frac{\sqrt{\delta}\#Z'}{\#G}\right) = o_{\delta \to 0; \#J}(\#Z')$

となって証明が完了する。 Q.E.D.

重み付きハイパーグラフ除去補題

ハイパーグラフ除去補題を重みつきにバージョアップさせる(これを後々使いたい)。

定理 (重み付きハイパーグラフ除去補題) $V=(J, (V_j)_{j \in J}, d, H)$ をハイパーグラフ系とする。ハイパーエッジ $e \in H$ 毎に関数 $f_e\colon V_e \to [0, 1]$ であって、 $0 < \delta < 1$ に対して

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}f_e(\pi_e(x) ) \ \right| \ x \in V_J\right) \leq \delta$

が成り立つようなものをとる。このとき、各 $e \in H$ に対して或る $E_e' \in \mathcal{A}_e$ が存在して

$\displaystyle \bigcap_{e \in H}E_e' = \emptyset,$

$\displaystyle \mathbb{E}\left(f_e(\pi_e(x) )\mathbf{1}_{V_J \setminus E_e'}(x) \mid x \in V_J\right) = o_{\delta \to 0; \#J}(1)$

が成り立つ。更に、 $e' \subset J, \ \#e' < d$ に対して部分 $\sigma$ 加法族 $\mathcal{B}_{e'} \subset \mathcal{A}_{e'}$ が存在して,

$\#\mathcal{B}_{e'} = O_{\delta, \#J}(1)$

かつ任意の $e \in H$ に対して

$\displaystyle E_e' \in \bigvee_{e' \subsetneq e}\mathcal{B}_{e'}$

が成り立つ。

$E_e \in \mathcal{A}_e$ に対して、 $E_e=\pi_e^{-1}(\overline{E}_e)$ となるような $\overline{E}_e \subset V_J$ をとって $f_e:=\mathbf{1}_{\overline{E}_e}$ とする。このとき、 $f_e\circ \pi_e = \mathbf{1}_{E_e}$ , $\mathbf{1}_{E_e}\mathbf{1}_{V_J\setminus E_e'} = \mathbf{1}_{E_e \setminus E_e'}$ が成り立つのでハイパーグラフ除去補題になる。

証明. $e \in H$ に対して、

$\displaystyle E_e := \{x \in V_J \mid f_e(\pi_e(x) ) \geq \delta^{\frac{1}{2\#H}}\}$

と $E_e$ を定義すると、 $\pi_e$ を合成していることから $E_e \in \mathcal{A}_e$ である。今、

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}f_e(\pi_e(x) ) \ \right| \ x \in V_J\right) \leq \delta$

と仮定していることから、

$\displaystyle \left.\mathbb{E}\left(\prod_{e \in H}\mathbf{1}_{E_e}(x) \ \right| \ x \in V_J\right) \leq \sqrt{\delta}$

が得られる。理由: $\displaystyle x \in \bigcap_{e \in H}E_e$ であれば $\displaystyle \prod_{e \in H}f_e(\pi_e(x) )\geq \sqrt{\delta}$ が成り立つので、

$\displaystyle \#\bigcap_{e \in H}E_e > \sqrt{\delta}\#V_J$

と仮定すると

$\displaystyle \sum_{x \in V_J}\prod_{e \in H}f_e(\pi_e(x) ) > \sqrt{\delta}\#V_J \times \sqrt{\delta} = \delta \#V_J$

となって矛盾する。従って、ハイパーグラフ除去補題によって複雑度の条件等適切な性質を満たす $E_e' \in \mathcal{A}_e$ 達が存在して

$\displaystyle \mathbb{E}\left(\mathbf{1}_{E_e}(x)\mathbf{1}_{V_J\setminus E_e'}(x) \mid x \in V_J \right) = o_{\delta \to 0; \#J}(1)$

が成り立つ。 $x \in V_J$ 毎に

$\displaystyle f_e(\pi_e(x) ) \leq \mathbf{1}_{E_e}(x) + \delta^{\frac{1}{2\#H}}$

が成り立つので

$\displaystyle \mathbb{E}\left(f_e(\pi_e(x) )\mathbf{1}_{V_J \setminus E_e'}(x) \mid x \in V_J\right) \leq \mathbb{E}\left(\mathbf{1}_{E_e}(x)\mathbf{1}_{V_J\setminus E_e'}(x) \mid x \in V_J \right) + \delta^{\frac{1}{2\#H}} = o_{\delta \to 0; \#J}(1)$

が得られる。 Q.E.D.

*1: $J=\{j\}$ のときは群準同型 $Z' \times Z \to Z'; \ (x,r) \mapsto x+\phi_j(r)$ が全射なので、群準同型性から $Z$ の各点でのファイバーの濃度は等しく、GT1,4の補題から

$\displaystyle \mathbb{E}(\mathbf{1}_A(x+\phi_j(r) ) \mid x \in Z', r \in Z) = \mathbb{E}(\mathbf{1}_A(x) \mid x \in Z')$

が成り立つ。これよりこの場合には主張が成り立つことがわかる。場合分けをする理由はハイパーグラフ系の定義で $d \geq 1$ が必要であるから。

*2: $i$ 成分が $r$ , $j$ 成分が $-r$ , 残りが $0$ であるような組を考えればよい。

*3: $i$ 成分が $-r$ で残りが $0$ であるような組を考える。

2018-01-07

29179の各桁の総和は29179の二乗の各桁の総和に等しい

整数整数-29179

$29179$ の各桁の数の総和は

$2+9+1+7+9=28$

ですが、 $29179^2=851414041$ の各桁の数の総和も

$8+5+1+4+1+4+0+4+1=28$

となっています。このような正整数は( $10$ の冪のような自明な例を除いても)無数に存在します。

定理 (Hare-Laishram-Stoll) $q \geq 2$ とする。 $q$ 進法において、 $n$ の各桁の総和と $n^2$ の各桁の総和が一致するような $q$ の倍数ではない正整数 $n$ が無数に存在する。

以下、簡単のため $q \geq 6$ の場合に限定して定理の証明を行います。

準備

補題１ $1 \leq b < q^k$ , $a, k \geq 1$ とする(全て整数)。このとき、

$\begin{align} s_q(aq^k+b) &= s_q(a)+s_q(b) \\ s_q(aq^k-b) &= s_q(a-1)+k(q-1)-s_q(b-1)\end{align}$

が成り立つ。

証明. 一つ目の等式は自明。 $b-1=\sum_{i=0}^{k-1}b_iq^i$ と書く( $q$ 進展開)。このとき、一つ目の式と $s_q$ の定義より

$\begin{align} s_q(aq^k-b) &= s_q\left( (a-1)q^k+q^k-b\right) = s_q(a-1)+s_q(q^k-b) \\ &= s_q(a-1)+s_q\left(\sum_{i=0}^{k-1}(q-1-b_i)q^i\right) \\ &= s_q(a-1)+\sum_{i=0}^{k-1}(q-1-b_i) = s_q(a-1)+k(q-1)-s_q(b-1) \end{align}$

と二つ目の式も証明される。 Q.E.D.

$(\cdot )_q$ は $q$ 進表示を表し、その中では $e^k=\underbrace{e\cdots e}_k$ のように略記する。

補題２ $k \geq 2, n \geq k+2, 0 \leq e \leq q-2$ とし、 $u:=( (q-1)^k0(q-1)^ne)_q$ とおく。このとき、

$s_q(u^2) = (n+1)(q-1)+f(q, e)$

が成り立つ。ただし、 $f(q, e) = s_q( (q-e)^2)+s_q(2(q-1)(q-e) )-s_q(2(q-e)-1)$ である。

証明.

$u = (q^k-1)q^{n+2}+(q^n-1)q+e = q^{n+k+2} -(q-1)q^{n+1}-(q-e)$

なので

$u^2=q^{2n+2k+4}-2(q-1)q^{2n+k+3}+(q-1)^2q^{2n+2}-2(q-e)q^{n+k+2}+2(q-1)(q-e)q^{n+1}+(q-e)^2$

が成り立つ。よって、補題１より

$\begin{align} s_q(u^2) &= s_q(q^{n+k+2}-2(q-1)q^{n+1}+(q-1)^2q^{n-k}-2(q-e))\\ &\quad + s_q(2(q-1)(q-e)q^{n+1}+(q-e)^2) \\ &= s_q(q^{k+1}-2(q-1) )+ s_q( (q-1)^2q^{n-k}-2(q-e) ) +s_q(2(q-1)(q-e) )+s_q( (q-e)^2) \\ &= (k+1)(q-1)-s_q(2(q-1)-1)+s_q( (q-1)^2-1)+(n-k)(q-1)-s_q(2(q-e)-1) \\ &\quad +s_q(2(q-1)(q-e) )+s_q( (q-e)^2) \\ &= (n+1)(q-1)-s_q(2q-3)+s_q(q^2-2q)+f(q, e)\end{align}$

と計算できる。 $s_q(2q-3)=s_q(q+q-3)=q-2, \ s_q(q^2-2q)=s_q(q-2)=q-2$ なので証明が完了する。 Q.E.D.

定理の証明

$t \geq 10$ とし、 $k:=(5t-1)(q-1)+1$ とする。 $u, v$ を

$\begin{align} u &:= ( (q-1)^{t+2}0(q-1)^{2t-5})_q = q^{3t-2}-(q-1)q^{2t-5}-1 \\ v &:= ( (q-1)^t0(q-1)^{t+2}1)_q = q^{2t+4}-(q-1)q^{t+3}-(q-1)\end{align}$

と定める。 $i$ を十分大きい整数とし、 $n:=(u0^iv)_q$ とおく。この $n$ が $s_q(n)=s_q(n^2)=k$ を満たすことを示す。そうすれば、 $i$ の任意性または $t$ の任意性によって所望の無限性が保証されることがわかる。 $n \equiv 1 \pmod{q}$ なので、 $n$ は $q$ の倍数ではない。また、構成から

$s_q(n) = ( (t+2)+(2t-5)+t+(t+2))(q-1)+1= (5t-1)(q-1)+1 = k$

である。よって、示すべきことは $s_q(n^2)=k$ のみとなった。 $i \gg 0$ にとっているので、補題１から

$s_q(n^2) = s_q(u^2)+s_q(2uv)+s_q(v^2)$

とできる。補題１を使えば $f(q, 0)=0, \ f(q, 1) = q$ は容易に確認できるので、補題２より

$s_q(u^2) = (2t-4)(q-1), \quad s_q(v^2) = (t+3)(q-1)+q$

がわかる。 $s_q(2uv)$ を計算したい。

$\begin{align}uv&=q^{5t+2}-(q-1)q^{4t+1}-(q-1)q^{4t-1}+(q-1)(q-2)q^{3t-2}-q^{2t+4}+(q-1)^2q^{2t-5}\\ &\quad +(q-1)q^{t+3}+(q-1)\end{align}$

と展開できるので、補題１を使って

$\begin{align} s_q(2uv) &= s_q(2q^{t+3}-2(q-1)q^2-2(q-1) ) \\ &\quad + s_q(2(q-1)(q-2)q^{3t-2}-2q^{2t+4}+2(q-1)^2q^{2t-5}+2(q-1)q^{t+3}+2(q-1) ) \\ &= 1+(t+3)(q-1)-s_q(2(q-1)q^2+2q-3) \\ &\quad + s_q(2(q-1)(q-2)q^{t+3}-2q^9+2(q-1)^2)+s_q(2(q-1)q^{t+3}+2(q-1) ) \\ &= 1+(t+3)(q-1)-(s_q(2(q-1) )+s_q(2q-3) ) \\ &\quad +s_q(2q^2-6q+3)+(t+3)(q-1)-s_q(2q^9-2(q-1)^2-1)+2s_q(2(q-1) )\\ &= 2+2(t+3)(q-1)+s_q(2(q-3)q+3)-(1+9(q-1)-s_q(2(q-1)^2) ) \\ &= (2t-1)(q-1)\end{align}$

と計算できる。よって、

$s_q(n^2) = (2t-4)(q-1)+(2t-1)(q-1)+(t+3)(q-1)+q = (5t-1)(q-1)+1 = k$

が示された。 Q.E.D.

素数の場合

冒頭であげた $29179$ は素数です。
$n$ を素数に限定すると、二乗しても各桁の総和が変わらないようなものは

$\begin{align}&19, 199, 379, 739, 1747, 1999, 3169, 3259, 4519, 4789, 4951, 5689, 5851, 5869, 6481, \\ &6679, 7489, 8389, 9199, 10729, 12799, 12889, 13789, 14149, 14851, 14869, 15679, \\ &17389, 17497, 17659, 17929, 22699, 26479, 26497, 26839, 28297, 28549, 29179\end{align}$

が見つかります。果たして、他にもあるでしょうか？

2018-01-06

大学入試数学〜素数〜

高校数学

京大2018前期理系問2
京大2018前期文系問3
名大2018前期理系問3
岐阜大2018前期問1
横浜市大2018前期I(1), III(1)
大阪市大2018前期文系問1
東北大2018後期文系問4
早稲田2018[基幹理工、創造理工、先進理工学部]III
京大2017前期文系問2
金沢大2017前期文系問2
京大2016前期理系問2
東工大2016前期理系問4
東北大2016前期理系問2
名大2016前期文系問3
岡山大2016前期理系問1
東工大2015前期理系問5
九大2015前期理系問5
九大2015前期文系問4
一橋2015前期問1
東大2014前期文科問4
東大2014前期理科問5
阪大2014理系挑戦枠問2
北大2014後期理系問1
一橋2014前期問1
京大2013前期文系問3
阪大2013前期理系問3
名大2013前期文系問3
名大2013前期理系問3
阪大2012前期文系問2, 理系問2
東大2009前期文科問2
東大2009前期理科問1
京大2009前期文系問5, 理系(甲)問5
名大2009前期理系問4(b)
東北大2008前期理系問6
京大2007前期文系問3, 理系問3
東北大2007前期文系問1, 理系問1
東工大前期問1
京大2006前期理系問4
東工大2006後期問2
一橋2006前期問1
阪大2004前期理系問2
一橋2004前期問5
京大2003前期文系問4
阪大2003前期文系問2
名大2003前期文系問3(a)
九大2002前期文系問2
九大2002前期理系問2
京大2002前期理系問4
一橋1999前期問1
京大1997前期理系問2
京大1996後期文系問2
京大1996後期理系問1
京大1995前期理系問2
京大1994前期文系問2
京大1990前期文系問2, 理系問2
阪大1987前期文系問1
阪大1987前期理系問1
東工大1986前期問1
東工大1984前期問1
京大1977前期文系問5
名大1977前期理系問2
九大1967前期文系問2, 理系問2

「素因数」は含むが、「複素数」は含まない。随時更新予定(情報提供募集)。