インテジャーズ

INTEGERS

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

105:円分多項式の係数と鈴木の定理

105に関して、次の著しい事実が知られています:

n \leq 104に対する第n円分多項式の係数は0, \pm 1であるが、第105円分多項式の係数には-2が現れる。

次数の低い円分多項式を手計算しても係数が0, \pm 1しか現れないため、普通は「これが永遠に続くのではないか?」と思ってもおかしくありません。しかし、n=105に至ってそれが破れてしまうことは大変に面白く感じます。実は円分多項式の係数はnの素因数分解の様子に深く影響を受けます。本記事を読むことにより、105=3\cdot 5\cdot 7および3+5 > 7という事実が第105円分多項式の係数に-2が現れる理由であるということが理解されるでしょう。

この記事では、まず円分多項式の基本事項を解説し、次に「n \leq 104に対する第n円分多項式の係数は0, \pm 1である」という事実の証明を行います。そして、最後に

任意の整数は円分多項式の係数として実現できる

という非常に美しい定理(鈴木の定理)の証明を解説します。

本記事は数学サイト「高校数学の美しい物語」の『円分多項式とその性質』
mathtrain.jp
という記事に影響を受けており、Thangaduraiという人の書いた解説記事を元に日本語で私が興味を持った部分を再構成したものとなっています。私が初めて円分多項式を学んだのは高木貞治博士の『初等整数論講義』を読んだときですが、105に関する事実は確か書いてありませんでした。

円分多項式の基本事項

自然数nに対し、1の原始n乗根\zeta_n\zeta_n := e^{\frac{2\pi i}{n}} \in \mathbb{C}とします。このとき、\{\zeta_n^m \mid 0 \leq m \leq n-1\}1n乗根全体のなす集合となるため、

\displaystyle X^n-1 = \prod_{m=0}^{n-1}(X-\zeta_n^m)

が成り立ちます。これに対し、1の原始n乗根を根にもつようなモニック多項式

\displaystyle \Phi_n(X) := \prod_{\substack{m=1 \\ (m, n)=1}}^n(X-\zeta_n^m)

n円分多項式と呼びます。1の原始n乗根全体のなす集合が\{ \zeta_n^m \mid 0 \leq m \leq n-1, \ (n, m)=1 \}に一致することに注意します。ここで、(n, m)=1nmが互いに素であることを表す数学記号です。

\deg \Phi_n(X) = \varphi (n)

および

\displaystyle X^n-1 = \prod_{d \mid n} \Phi_n(X)

は容易に分かります(\varphi (n)はEulerのトーシェント関数)。

補題1 \Phi_n(X) \in \mathbb{Z}[X].

証明. nに関する帰納法で証明する。n=1のときは\Phi_1(X)=X-1よりOK。n\geq 2とし、n未満の場合は正しいと仮定する。

\displaystyle F(X) := \prod_{\substack{d \mid n \\ d < n}}\Phi_n(X) \in \mathbb{Z}[ X]

とおく(帰納法の仮定から整数係数)。モニック多項式に関する割り算の原理より、q(X), r(X) \in \mathbb{Z}[ X] が存在して、q(X)はモニックな、r(X)0であるか次数が\deg F(X)未満の多項式であり、

X^n-1 = F(x)q(X)+r(X)

が成り立つ。一方、X^n-1=F(X)\Phi_n(X)である。\mathbb{C}[ X ] における割り算の原理の一意性および、q(X), F(X)がともにモニックであることから、F(X)=q(X) \in \mathbb{Z}[ X ] が従う。 Q.E.D.

補題2 \displaystyle \Phi_n(X) =\prod_{d \mid n}(X^{\frac{n}{d}}-1)^{\mu (d)}.

\mu (n)Möbius関数です。

この補題によって、\Phi_n(X)を定義よりは効率的に計算できます。また、本記事で紹介する様々な補題や定理の証明で活躍します。

証明. nを固定し、xを任意のnの約数dに対して\left|\Phi_d(x)\right| > 0を満たすような十分大きい実数とする。このとき、

\displaystyle x^n-1 = \prod_{d\mid n}\Phi_d(x)

の両辺の自然対数をとることによって

\displaystyle \log (x^n-1) = \sum_{d \mid n}\log \Phi_d(x)

を得る。よって、Möbiusの反転公式により

\displaystyle \log \Phi_n(x) = \prod_{d \mid n}\mu (d)\log (x^{\frac{n}{d}}-1)

が成立することがわかる。すなわち、無数のxに対して所望の等式が成立することが示された。これより、多項式としての等号が成り立つことがわかる。 Q.E.D.
この記事では用いませんが、次の事実が成り立ちます。

事実1 \Phi_n(X)\mathbb{Q}上既約である。

\Phi_n(X)\zeta_nの最小多項式であればよいので、これは

\mathrm{Gal}(\mathbb{Q}(\zeta_n)/\mathbb{Q}) \simeq (\mathbb{Z}/n\mathbb{Z})^{\times}

および

[ \mathbb{Q}(\zeta_n):\mathbb{Q}] = \varphi (n)

と同値であることがわかります。この事実は格子点正多角形 - INTEGERSなどで既に用いていますが、証明はまだ書いていません。大きく分けて二通りの証明法がありますが、私の好きな証明は割と準備が必要なので将来の記事に託すこととします。一方で、n=p^k (pは素数、kは自然数)の場合は次のようにEisensteinの既約判定法により証明できます:

証明. 補題2より

\displaystyle \Phi_{p^k}(X) = \frac{X^{p^k}-1}{X^{p^{k-1}}-1} = (X^{p^{k-1}})^{p-1}+(X^{p^{k-1}})^{p-2}+\cdots +X^{p^{k-1}}+1

なので、q=p^kと略記すれば

\begin{equation}\begin{split}\Phi_q(X+1) &\equiv (X^q+1)^{p-1}+\cdots +(X^q+1)+1 \\ &=\frac{(X^q+1)^p-1}{(X^q+1)-1} \equiv \frac{X^{pq}}{X^q} = X^{q(p-1)} \pmod{p}\end{split}\end{equation}

が分かる。また、\Phi_q(X+1)の定数項はpなので、\Phi_q(X+1)はEisenstein多項式である。平行移動で既約性は変わらないため、証明が完了する。 Q.E.D.

定義 \displaystyle \Phi_n(X) = \sum_{i=0}^{\varphi (n)}a_i^{(n)}X^iと表示し、\mathrm{Coeff}(\Phi_n(X))
\mathrm{Coeff}(\Phi_n(X)) := \{ a_i^{(n)} \mid 1 \leq i \leq \varphi (n) \} \subset \mathbb{Z}
によって定義する。

上記証明中の式から\mathrm{Coeff}(\Phi_{p^k}(X)) \subset \{ 0, 1 \}が分かります。

補題3 nのsquare-free partをNとする(例えばn=12のときはN=6=2\cdot 3)。このとき、\Phi_n(X) = \Phi_N(x^{\frac{n}{N}})が成り立つ。特に、\mathrm{Coeff}(\Phi_n(X)) \cup \{0 \} = \mathrm{Coeff}(\Phi_N(X))

証明. square-free partの約数しかMöbius関数には寄与しないことに注意して補題2を用いて計算すればよい:

\begin{equation}\begin{split}\Phi_n(X) &= \prod_{d \mid n}(X^{\frac{n}{d}}-1)^{\mu (d)} = \prod_{d \mid N}(X^{\frac{n}{d}}-1)^{\mu (d)} = \prod_{d \mid N}( (X^{\frac{n}{N}})^{\frac{N}{d}}-1)^{\mu (d)} \\ &= \Phi_N(X^{\frac{n}{N}}).\end{split}\end{equation}
Q.E.D.

補題4 n3以上の奇数とする。このとき、\Phi_{2n}(X)=\Phi_n(-X).

証明. 補題2より

\begin{equation}\begin{split}\Phi_{2n}(X) &= \prod_{d \mid 2n}(X^d-1)^{\mu(2n/d)} \\ &= \prod_{2 \mid d \mid 2n}(X^d-1)^{\mu (2n/d)}\prod_{d \mid n}(X^d-1)^{\mu (2n/d)} \\ &= \prod_{d \mid n}\left\{ (X^d-1)^{\mu (2n/d)}(X^{2d}-1)^{\mu (n/d)}\right\} \\ &=\prod_{d \mid n}(X^d+1)^{\mu (n/d)} \ (\text{奇数}m\text{に対して}\mu (2m) = -\mu (m)) \\ &= \prod_{d\mid n}((-X)^d-1)^{\mu (n/d)} (\text{Möbius関数が寄与するのは}2^{\omega (n)}\text{個(偶数)})\\ &= \Phi_n(-X)\end{split}\end{equation}
と変形できる。 Q.E.D.

数論的関数\omega (n)については数論的関数 ω(n) - INTEGERSを参照してください。

補題5 n2以上の整数とするとき、X^{\varphi (n)}\Phi_n(X^{-1}) = \Phi_n(X).特に、a_i^{(n)} = a_{\varphi (n)-i}^{(n)} (0 \leq i \leq \varphi (n))が成り立つ(係数の対称性)。

証明. 補題2より

\displaystyle \Phi_n(X^{-1}) = \prod_{d \mid n}\left( \frac{1}{X^d}-1 \right)^{\mu (n/d)} = (-1)^{\sum_{d \mid n} \mu (n/d)}\cdot X^{\sum_{d\mid n}d\mu (n/d)}\prod_{d \mid n}(X^d-1)^{\mu (n/d)}
と変形でき、\displaystyle \sum_{d \mid n}\mu (n/d) = 0および\displaystyle \sum_{d\mid n}d\mu(n/d) = \varphi (n)なので証明が完了する。 Q.E.D.

n=pqの場合

一次不定方程式に関する次の事実は初等整数論において非常に基本的です。

事実2 a, b, cは整数であり、a, bが互いに素であるとする。このとき、不定方程式ax+by=cは整数解をもつ。解の一つを(x_0, y_0)とするとき、一般解は整数パラメータtを用いて(x, y) = (x_0+bt, y_0-at)で与えられる。

一方、次の命題はあまり見たことがない可能性もあるため、証明をつけます。

命題1 a, bを互いに素な自然数とする。このとき、ax+by=(a-1)(b-1)を満たす非負整数解が唯一つ存在する。また、その解x, yx \leq a-2, y \leq b-2を満たす。

証明. 非負整数解が存在すれば最後の不等式の条件を満たすことはax+by=(a-1)(b-1)の両辺の大きさを比較すれば明らか。a, bは互いに素なので、事実2から(非負とは限らない)整数解x_0, y_0が存在する。一般整数解はx=x_0+bt, y=y_0-at (t \in \mathbb{Z})で与えられるが、0 \leq x_0+bt < bを満たすようなtが唯一つ存在する。そのようなtに対して、y=y_0-at \geq 0であることを示せばよい(tの一意性から非負整数解の一意性も従う)。x_0+bt \leq b-1およびax_0+by_0=(a-1)(b-1)より

\displaystyle y_0-at = \frac{1}{b}\{ (a-1)(b-1)-ax_0-abt\} \geq \frac{1}{b}-1 > -1

と評価でき、y_0-at \geq 0であることが示された。 Q.E.D.

p, qを相異なる奇素数としましょう。このとき、Migotti(1883)を始めとして多数の人々により\mathrm{Coeff}(\Phi_{pq}(X)) \subset \{ 0, \pm 1\}が証明されています。ここでは、Lam-Leungに基づいて次の定理を証明します。

定理1 (p-1)(q-1)=rp+sqを満たす非負整数r, sを考える(このようなr, sは命題1により
一意に存在する)。このとき、

\displaystyle \Phi_{pq}(X) = \left( \sum_{i=0}^rX^{ip}\right) \left( \sum_{j=0}^sX^{jq} \right) - \left( \sum_{i=r+1}^{q-1}X^{ip}\right) \left( \sum_{j=s+1}^{p-1}X^{jq} \right) X^{-pq}

が成り立つ。また、0 \leq k \leq  (p-1)(q-1)なるkに対して

  • a_k^{(pq)}=1 \Longleftrightarrow {}^{\exists}i \in [ 0, r], {}^{\exists}j \in [ 0, s] \ \text{s. t.} \ k=ip+jq
  • a_k^{(pq)}=-1 \Longleftrightarrow {}^{\exists}i \in [ r+1, q-1], {}^{\exists}j \in [ s+1, p-1] \ \text{s. t.} \ k+pq=ip+jq
  • a_k^{(pq)}=0 \Longleftrightarrow \text{otherwise}

が成り立つ。

証明. \zeta_{pq}^{q}1の原始p乗根であり、\zeta_{pq}^{p}1の原始q乗根なので、

\displaystyle \Phi_p(\zeta_{pq}^q)= \Phi_q(\zeta_{pq}^p) =0

すなわち、

\displaystyle \sum_{i=0}^{q-1}(\zeta_{pq}^p)^i=\sum_{j=0}^{p-1}(\zeta_{pq}^q)^j=0

が成り立つ。よって、

\displaystyle \sum_{i=0}^r(\zeta_{pq}^p)^i = -\sum_{i=r+1}^{q-1}(\zeta_{pq}^p)^i

および

\displaystyle \sum_{j=0}^s(\zeta_{pq}^q)^j = -\sum_{i=s+1}^{p-1}(\zeta_{pq}^q)^j

が成り立ち、辺々掛け合わせることによって

\displaystyle \left( \sum_{i=0}^{q-1}(\zeta_{pq}^p)^i \right) \left( \sum_{j=0}^s(\zeta_{pq}^q)^j \right) - \left( \sum_{i=r+1}^{q-1}(\zeta_{pq}^p)i \right) \left( \sum_{i=s+1}^{p-1}(\zeta_{pq}^q)^j \right) = 0

が得られる。つまり、

\displaystyle f(X) := \left( \sum_{i=0}^rX^{pi} \right) \left( \sum_{j=0}^sX^{qj} \right) - \left( \sum_{i=r+1}^{q-1}X^{pi} \right) \left( \sum_{j=s+1}^{p-1}X^{qj} \right)X^{-pq}

とおくとき、\zeta_{pq}f(X)の根であることがわかった。同様に考えれば、f(X)は任意の1の原始pq乗根を根にもつことがわかる。f(X) = f_1(X)-f_2(X)と略記するとき、f_2(X)に現れる項の次数の最小値は

(r+1)p+(s+1)q-pq=1

なので、f_2(X)は多項式、すなわちf(X) \in \mathbb{Z}[ X] であることがわかる。また、f_2(X)に現れる項の次数の最大値は

(q-1)p+(p-1)q-pq = (p-1)(q-1)-1

であるのに対し、f_1(X)の次数は

pr+sq = (p-1)(q-1)

なので、\deg f(X) = (p-1)(q-1) = \varphi (pq) = \deg \Phi_{pq}(X)がわかる。以上により、f(X)は任意の1の原始pq乗根を根にもつような\varphi (pq)次のモニック整数多項式であることが示されたので、f(X) = \Phi_{pq}(X)が従う。
係数の判定条件については次の主張からすぐ分かるし、主張の証明も簡単である。

主張 i, i' \in [ 0, q-1], j, j' \in [ 0, p-1] であり、ip+jq = i'p+j'q \ \text{or} \ i'p+j'q - pqならば
i=i'かつj=j'が成り立つ。

Q.E.D.

この定理によって、最初の目的が達成されます:

系1 n \leq 104ならば\mathrm{Coeff}(\Phi_n(X)) \subset \{0, \pm 1\}.

証明. 補題3より、平方因子を持たない場合のみを考えればよい。更に、補題4によって奇数のみを考えればよいこともわかる。このとき、Eisenstein既約判定法を用いた証明と定理1から、素因数の個数が2個以下の場合はOKだとわかる。相異なる3つの奇素数の積となる自然数の最小値は3\cdot 5\cdot 7=105であるため、n \leq 104に対しては円分多項式の係数が0, \pm 1のいずれかであることが証明された。 Q.E.D.

逆に相異なる3つの奇素数の積であれば円分多項式の係数が0, \pm 1になるわけではありません。n=105の場合はその素因数に対して3+5 > 7なる関係が成り立つことが、係数に-2が現れる原因になっていることが次のセクションで判明します。ここで、\Phi_{105}(X)を眺めましょう:

\begin{equation}\begin{split}\Phi_{105}(X) &= x^{48} + x^{47} + x^{46} - x^{43} - x^{42} - 2x^{41} - x^{40} - x^{39} + x^{36} + x^{35} + x^{34}\\  & \ + x^{33} +x^{32} +x^{31} -x^{28} -x^{26} -x^{24} -x^{22} -x^{20} +x^{17} +x^{16} +x^{15}\\ & \ +x^{14} +
x^{13} + x^{12} - x^9 - x^8 - 2x^7 - x^6 - x^5 + x^2 + x + 1\end{split}\end{equation}

鈴木の定理

円分多項式の係数に-2が現れることは分かりましたが、他の整数はどのぐらい現れるのでしょうか?実は全ての整数が現れることが

J. Suzuki, On coefficients of cyclotomic polynomials, Proc. Japan Acad. Ser. A Math. Sci. 63 (1987), no. 7, 279-280.

において証明されています。すなわち、次の定理が成り立ちます:

定理2 \displaystyle \bigcup_{n=1}^{\infty}\mathrm{Coeff}(\Phi_n(X)) = \mathbb{Z}.

証明には次の素数に関する補題を使います。

補題6 k \geq 3を任意の整数とする。このとき、k個の素数p_1 < p_2 < \cdots < p_kであって、p_1+p_2 > p_kを満たすものが存在する。

証明. 背理法で証明する。すなわち、ある整数k \geq 3で主張が成り立たないと仮定する。このとき、任意の自然数lに対して

\pi (2^l)-\pi (2^{l-1}) < k -①

が成り立つ(\pi (x)は素数個数関数)。実際、k個の素数p_1 < p_2 < \cdots < p_kが全て[ 2^{l-1}, 2^l] に含まれたとすると、背理法の仮定によって2p_1 < p_1 + p_2 \leq p_kとなって矛盾する。よって、①に対して望遠鏡和を取ることによって*1
\pi (2^l) < klを得る。一方、Chebyshevの定理によって、ある正の定数Cが存在して

\displaystyle \pi(x) \geq C\frac{x}{\log x} (x \to \infty)

が成り立つ。よって、十分大きいlに対して矛盾する不等式

\displaystyle C\frac{2^l}{l\cdot \log 2} < kl

が導かれる。 Q.E.D.

鈴木の定理の証明. 奇数k \geq 3を固定する。また、p_1 < \cdots < p_kであってp_1+p_2 > p_k -②を満たすようなk個の素数を取る(補題6によって存在する)。n:=p_1\cdots p_kとし、このnに関する\Phi_n(X)を考える。証明のキーアイデアは\pmod{X^{p_k+1}}で合同を考えることである(環\mathbb{Z}[ X] に対して単項イデアル(X^{p_k+1})による剰余を考えるということ)。まず、②によって1 \leq i, j \leq kに対してp_ip_j \geq p_k+1が成り立つので、補題2より

\begin{equation}\begin{split} \Phi_n(X) &= \prod_{d \mid n}(X^d-1)^{\mu (n/d)} \equiv \frac{\prod_{i=1}^k X^{p_i}-1}{X-1} \\ &= \frac{X^{p_k}-1}{X-1}(1-X^{p_1})\cdots (1-X^{p_{k-1}}) \pmod{X^{p_k+1}}\end{split}\end{equation}

が成り立つ。ここで、最後の不号の入れ替えはkが奇数であることに注意する。②より、1 \leq i, j \leq kに対してp_i+p_j \geq p_k+1が成り立つので

(1-X^{p_1})\cdots (1-X^{p_{k-1}}) \equiv (1-X^{p_1}-\cdots - X^{p_{k-1}}) \pmod{X^{p_k+1}}

である。従って、

\Phi_n(X) \equiv (1+X+\cdots +X^{p_k-1})(1-X^{p_1}-\cdots -X^{p_k}) \pmod{X^{p_k+1}}

が示された。この表示から円分多項式の係数についてa_{p_k}^{(n)} = -k+1およびa_{p_k-2}^{(n)}=-k+2がわかる(実際、右の括弧内の各-X^{p_i}(k-1個ある)に対し、掛けるとX^{p_k}(またはX^{p_k-2})となるような項が左の括弧内に丁度一つずつある。また、右の括弧内の1については左の括弧内のどの項を掛けてもX^{p_k}を実現することはできないが、X^{p_k-2}は生み出せる)。k3以上の任意の奇数であったため、

\displaystyle \bigcup_{n=1}^{\infty}\mathrm{Coeff}(\Phi_n(X)) \supset \mathbb{Z}_{\leq -1}

が示された。n=p_1 \cdots p_kに対して補題4を適用することにより、\Phi_{2n}(X)=\Phi_n(-X)が成り立つので、

a_{p_k}^{(2n)} = (-1)^{p_k}a_{p_k}^{(n)} = k-1

および

a_{p_k-2}^{(2n)} = (-1)^{p_k-2}a_{p_k-2}^{(n)} = k-2

が分かる。すなわち、

\displaystyle \bigcup_{n=1}^{\infty}\mathrm{Coeff}(\Phi_n(X)) \supset \mathbb{Z}_{\leq -1} \cup \mathbb{Z}_{\geq 1}

が示された。例えば、a_1^{(4)}=0なので証明が完了する。 Q.E.D.

(おまけ)円分多項式のDirichletの算術級数定理に対する応用

素数に関する基本的な結果であるDirichletの算術級数定理は当ブログではまだ証明しておりません*2

Dirichletの算術級数定理
a, bが互いに素な自然数のとき、an+b (n \in \mathbb{N})の形をした素数が無数に存在する。

普通はDirichletのL関数を用いて証明するのですが、b=1のときに限定すれば円分多項式を用いて初等的に証明することができます。

補題7 a2以上の整数とする。このとき、任意の整数kに対して、\Phi_a(k)の素因数はaの約数であるか、ある自然数nを用いてan+1と書ける。

証明. X^a-1=\Phi_a(X)F(X)と書ける(F(X) \in \mathbb{Z}[ X] )。X=kを代入することによりk^a-1=\Phi_a(k)F(k)を得る。\Phi_a(k) \neq \pm 1のときを考えればよい。\Phi_a(k)の素因数を勝手にとってpとする。このとき、k^q \equiv 1 \pmod{p}が成り立つ。よって、k(\mathbb{Z}/p\mathbb{Z})^{\times}における位数をeとすればある自然数bが存在してa=ebと書ける。b \geq 2のときを考える。このとき、X^e-1\Phi_a(X)は共通因数をもたない(X^e-1の根は1の原始a乗根ではない)ので、X^e-1 \mid F(x)である。その商をG(x) \in \mathbb{Z} [ X ] とすれば

\Phi_a(X)G(X) = X^{e(b-1)}+X^{e(b-2)}+\cdots +X^e+1

が成り立つ。Xkを代入して、eの定義より成り立つk^e \equiv 1 \pmod{p}を適用することにより、b \equiv \Phi_a (k)G(k) \equiv 0 \pmod{p}が従う。よって、p \mid a=eb、すなわちpaの約数である。次にa=eと仮定する。このときはFermatの小定理によってe \mid p-1である。すなわち、ある自然数nが存在してp=an+1が成り立つ。 Q.E.D.

an+1型素数の無限性証明. \Phi_a(k)= \pm 1を満たすようなkは高々有限個しか存在しない。よって、\Phi_a(k) \neq \pm 1であるようなaの倍数kを選ぶことができる。\Phi_a(k)の素因数を一つとってpとする。k^a \equiv 1 \pmod{p}が成り立つので、特に(k, p)=1である。つまり、paを割り切らない。こうして、補題7からpan+1型の素数であることが判明した。an+1型の素数を一つ見つけさえすれば、同型の素数を量産することは容易い。実際、p=an+1のとき、aの代わりにapに対して同様の議論を行うことによってq=(ap)m+1と表せる素数qの存在がわかる(mは自然数)。そうして、q > pかつqan+1型素数である。 Q.E.D.

*1:望遠鏡和については integers.hatenablog.com を参照してください。

*2:追記) しました: integers.hatenablog.com