インテジャーズ

INTEGERS

数、特に整数に関する記事。

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

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

参考文献
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-Latznelson) 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個しかないので、\deltaNには依存しないことに注意して、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

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

定義1 Jを有限集合とし、d \geq 0を整数とする。このとき、\binom{J}{d}
\displaystyle \binom{J}{d} := \{e \subset J \mid \#e = d\}
と定義する。\binom{J}{d}の部分集合Hのことを、d一様ハイパーグラフという。

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

定義2 ハイパーグラフ系とは4つ組V=(J, (V_j)_{j \in J}, d, H)であって、J: 有限集合、(V_j)_{j \in J}: 空でない有限集合の族、d \geq 1H \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

定義3 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_eV_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')

となって所望の漸近挙動に到達する。以下、最初に設けた仮定をはずす。G

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

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

\displaystyle \mathbb{E}_y :=  \left.\mathbb{E}\left(\prod_{j \in J}\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}\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として適用すると

\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であるような組を考える。

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 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 )_qq進表示を表し、その中ではe^k=\underbrace{e\cdots e}_kのように略記する。

補題2 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

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

\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とおく。このns_q(n)=s_q(n^2)=kを満たすことを示す。そうすれば、iの任意性またはtの任意性によって所望の無限性が保証されることがわかる。n \equiv 1 \pmod{q}なので、nqの倍数ではない。また、構成から

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にとっているので、補題1から

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

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

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}

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

\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}

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

大学入試数学〜素数〜

京大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

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