Shironetsu Blog

@shironetsuのブログ

円分多項式の係数を計算する - 〈105〉を超えて

物理・数学

Introduction

1 の原始 n 乗根全てを根に持つ多項式で、モニック(最高次の係数が 1)なものを n 次の 円分多項式 (cyclotomic polynomial) と呼ぶ. これを \Phi_n(X)で表す.

定義からすぐに導けるように,

\begin{align} \Phi_n(X) = \prod_{\begin{array}{cc} 1 \leq k < n \\ {\rm gcd}(n,k) = 1 \end{array}} \left(X-\exp{\frac{2\pi \sqrt{-1}\,k}{n}}\right). \end{align}

これを展開する方法は後で説明することにして, 最初のいくつかを見よう.

\begin{align} \Phi_1(X) &= X-1\\ \Phi_2(X) &= X+1\\ \Phi_3(X) &= X^2+X+1\\ \Phi_4(X) &= X^3+X^2+X+1\\ \Phi_5(X) &= X^4+X^3+X^2+X+1\\ \Phi_6(X) &= X^2-X+1\\ \Phi_7(X) &= X^6+X^5+X^4+X^3+X^2+X+1\\ \Phi_8(X) &= X^4+1\\ \Phi_9(X) &= X^6+X^3+1\\ \Phi_{10}(X) &= X^4-X^3+X^2-X+1\\ \Phi_{11}(X) &= X^{10}+X^9+X^8+X^7+X^6+X^5+X^4+X^3+X^2+X+1\\ \Phi_{12}(X) &= X^4-X^2+1 \end{align}

この範囲で各項の係数には 1,0,-1 しか現れない. 延々と計算を続けると, n=100 に至っても係数はやはり 1,0,-1 のいずれかで, 円分多項式とはそういうものなのだと予想したくなる. ところが, n=105 に至って平穏は破られ, 係数に -2 が出現する:

\begin{align} \require{autobold} \Phi_{105}(X) = & \phantom{+}X^{48}+ X^{47}+ X^{46}- X^{43}- X^{42}-\boldsymbol{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}\boldsymbol{-2X^{7}}- X^{6} - X^{5} + X^{2}+ X + 1. \end{align}

最初かどうかは定かではないが1883年にMigottiが気付いたことらしい [1, 2].

円分多項式の係数に関する諸現象の全ての起点がこの n=105 と言っても過言ではないだろう. なぜ 105 なのか?という疑問を持つのは当然として, 比較的注目されにくい点として,

なぜ 7 次の項なのか?

という謎を追究したい(41次のほうを無視したのは全体の次数 48-7=41 から来ているから).

実は,

円分多項式の 0 次から 6 次の項には 1,0,-1 しか現れない


ことが示される. 0から数えて6まではフラットで, 7 になって突然...というのは少しBorwein 積分 を思い出す.

この事実は本記事の後半で, 計算機を使った方法によって確かめられる. 円分多項式の係数を計算するための基本的なツールを概観していこう.

鈴木の定理

-2 以外の数がいつ現れるかも見よう. まず +2 が n=165 で現れる.

\begin{align} \Phi_{165}(X) = &\phantom{+}X^{80}+X^{79}+X^{78}-X^{75}-X^{74}-X^{73}-X^{69}-X^{68}-X^{67}+X^{65}\\ &\boldsymbol{+2X^{64}+2X^{63}}+X^{62}-X^{60}-X^{59}-X^{58}-X^{54}-X^{53}-X^{52}+X^{50}\\ &+\boldsymbol{2X^{49}+2X^{48}+2X^{47}}+X^{46}-X^{44}-X^{43}-X^{42}-X^{41}-X^{40}-X^{39}\\ &-X^{38}-X^{37}-X^{36}+X^{34}\boldsymbol{+2X^{33}+2X^{32}+2X^{31}}+X^{30}-X^{28}-X^{27}\\ &-X^{26}-X^{22}-X^{21}-X^{20}+X^{18}\boldsymbol{+2X^{17}+2X^{16}}+X^{15}-X^{13}-X^{12}\\ &-X^{11}-X^{7}-X^{6}-X^{5}+X^{2}+X+1 \end{align}

-3 は n=385.

\begin{align} \Phi_{385}(X) = &\phantom{+}X^{240}+X^{239}+X^{238}+X^{237}+X^{236}-X^{233}-X^{232}-X^{231}-X^{230}-2X^{229}\\ &-X^{228}-X^{227}-X^{2\,\!26}-X^{225}+X^{222}+X^{221}+X^{220}+X^{219}+X^{2\,\!18}+X^{205}\\ &+X^{204}+X^{203}+X^{202}+X^{201}-X^{198}-X^{197}-X^{196}-X^{195}-2X^{194}-X^{193}\\ &-X^{192}-X^{191}-X^{190}+X^{187}+X^{186}+2X^{185}+2X^{184}+2X^{183}+X^{182}+X^{181}\\ &-X^{178}-X^{177}-X^{176}-X^{175}-2X^{174}-X^{173}-X^{172}-X^{171}+X^{169}+X^{168}\\ &+2X^{167}+2X^{166}+X^{165}+X^{164}+X^{163}-X^{159}-X^{158}-X^{157}-2X^{156}-2X^{155}\\ &-X^{154}-X^{153}-X^{152}+X^{150}+X^{149}+X^{148}+X^{147}+X^{146}+X^{145}+X^{144}\\ &-X^{140}-2X^{139}-X^{138}-X^{137}-X^{136}+X^{134}+X^{133}+2X^{132}+2X^{131}+2X^{130}\\ &+2X^{129}+2X^{128}+X^{127}+X^{126}-X^{124}-2X^{123}-2X^{122}\boldsymbol{-3X^{121}-3X^{120}-3X^{119}}\\ &-2X^{118}-2X^{117}-X^{116}+X^{114}+X^{113}+2X^{112}+2X^{111}+2X^{110}+2X^{109}+2X^{108}\\ &+X^{107}+X^{106}-X^{104}-X^{103}-X^{102}-2X^{101}-X^{100}+X^{96}+X^{95}+X^{94}\\ &+X^{93}+X^{92}+X^{91}+X^{90}-X^{88}-X^{87}-X^{86}-2X^{85}-2X^{84}-X^{83}\\ &-X^{82}-X^{81}+X^{77}+X^{76}+X^{75}+2X^{74}+2X^{73}+X^{72}+X^{71}-X^{69}\\ &-X^{68}-X^{67}-2X^{66}-X^{65}-X^{64}-X^{63}-X^{62}+X^{59}+X^{58}+2X^{57}\\ &+2X^{56}+2X^{55}+X^{54}+X^{53}-X^{50}-X^{49}-X^{48}-X^{47}-2X^{46}-X^{45}\\ &-X^{44}-X^{43}-X^{42}+X^{39}+X^{38}+X^{37}+X^{36}+X^{35}+X^{22}+X^{21}\\ &+X^{20}+X^{19}+X^{18}-X^{15}-X^{14}-X^{13}-X^{12}-2X^{11}-X^{10}-X^{9}\\ &-X^{8}-X^{7}+X^{4}+X^{3}+X^{2}+X+1 \end{align}

+3 は n=595, -4 は n=1365...と延々と続けられるが一旦やめておく. 実は

円分多項式の係数には全ての整数が現れる


ことが鈴木の与えた定理によって保証されている [3, 4]. ちなみにこの論文はわずか1ページ強しかない.

鈴木の定理の概要を述べる前に, 本記事を通して使うことになる記号と用語を定めておく.

  • 円分多項式 \Phi_n(X) の n を位数(order)と呼ぶことにする.
    これはかなり苦し紛れだがご容赦いただきたい. "n-th cyclotomic polynomial" と呼ばれるばかりであまり統一された呼び名がない. ただ, 後述するOEIS上のdescriptionでは" order of cyclotomic polynomial"という語が見られるし, 全ての根が \mathbb{C} の乗法に関する位数になることを考慮に入れるとまずまず良い呼び名なのではないかと思う.
  • 位数 n の円分多項式の, k 次の項の係数を, a(n,k)と表す. すなわち,
\begin{align} \Phi_n(X) = \sum_{k \geq 0}a(n,k) X^k. \end{align}

この下で, 鈴木の定理の内容を述べると以下のようになる(実際にtheoremのステートメントにされているのは円分多項式には全ての整数が現れるという部分だけ):

t を3以上の奇数とする. t 個の奇素数 p_1, p_2, \cdots , p_t が \begin{gather} p_1< p_2 < \cdots < p_t,\\ p_1+p_2 > p_t \end{gather} を満たすとき, n=p_1p_2\cdots p_t について, \begin{align} &a(n,p_t) = -t + 1, & &a(n,p_t-2) = -t+2,\\ &a(2n,p_t) = t-1, & &a(2n,p_t-2) = t-2 \end{align} が成り立つ. 任意の t に対して上の条件を満たす p_1, p_2, \cdots , p_t が存在することが, 素数定理によって示されるため, 自明な0を含めて円分多項式の係数は全ての整数値を取る.


t=3 の場合, n=105=3\cdot 5\cdot 7 は3つの素因数が上の条件を満たす:

\begin{gather} 3< 5 < 7,\\ 3+5 > 7 \end{gather}

定理の示すところによると,

\begin{align} a(105, 7) = -2, \hspace{12pt} a(105,5) = -1 \end{align}

だが, 実際これは成り立っていることを上で見た.

t=5 の場合, 最小の位数は

\begin{align} 11\cdot 13\cdot 17 \cdot 19\cdot 23=1062347 \end{align}

と, 一気に大きくなる. t=7 では

\begin{align} 23\cdot 29\cdot 31\cdot 37\cdot 41 \cdot 43 \cdot 47 = 63392725189. \end{align}

爆発的に増加する.

鈴木の定理は全ての整数 m に対して a(n,k)=m を満たす最小の位数 n が存在することを保証してくれる. しかし, 定理のステートメントに現れるそれより実際の位数はずっと小さい.

メビウス関数と反転公式

円分多項式 \Phi_n(X) を X の多項式として具体的に計算する方法について説明しよう. 円分多項式は 1 の原始 n 乗根を根に持つ多項式なのだった. そのため, ある n に対してその約数を位数に持つ円分多項式をすべて乗じると, 1 の n 乗根全てをちょうど1つずつ根に持つ多項式になる. すなわち,

\begin{align} X^n - 1 = \prod_{d \mid n} \Phi_d(X). \end{align}

形式的にこの両辺の対数を取る.

\begin{align} \log(X^n-1) = \sum_{d \mid n} \log\Phi_d(X) \end{align}

反転公式を使うと,

\begin{align} \log\Phi_n(X) &= \sum_{d\mid n} \mu\left(\frac{n}{d}\right) \log(X^d-1)\\ \Phi_n(X) &= \prod_{d\mid n} (X^d-1)^{\mu(n/d)} \end{align}
・・・・・・(☆)

が導かれる. ただし \mu はメビウス関数.

n=105 の場合には,

\begin{align} \Phi_{105}(X) &= \frac{(X^{105}-1)(X^3-1)(X^5-1)(X^7-1)}{(X^{35}-1)(X^{21}-1)(X^{15}-1)(X-1)} \end{align}

という風に計算できる. とはいえ手計算ではなかなか大変. 円分多項式の各項の次数-係数を与えるC++コードはたとえばこう書ける:

#include <iostream>
#include <map>
#include <vector>

using namespace std;
using polynomial = map<int, int>;

int main()
{
    int n;
    cin >> n;

    /*整数nの素因数をリスト化*/
    
    int m = n;
    vector<int> prime_factors;
    for (int d = 2; d * d <= m; ++d)
    {
        if (m % d)
        {
            continue;
        }
        prime_factors.push_back(d);
        do
        {
            m /= d;
        } while (m % d == 0);
    }
    if (m > 1)
    {
        prime_factors.push_back(m);
    }

    /*メビウス関数による円分多項式の公式の分母と分子を計算*/

    int size = prime_factors.size();
    polynomial numerator = {{0, 1}};
    polynomial denominator = {{0, 1}};

    for (int i = 0; i < (1 << size); ++i)
    {
        int k = n;
        int parity = 0;
        for (int j = 0; j < size; ++j)
        {
            if (i & (1 << j))
            {
                k /= prime_factors.at(j);
                parity ^= 1;
            }
        }

        /*メビウス関数が1なら分子, -1なら分母*/

        polynomial *poly = (parity == 1) ? &denominator : &numerator;
        polynomial copy(*poly);
        for (auto iter = poly->begin(); iter != poly->end(); ++iter)
        {
            int deg = iter->first;
            int coef = iter->second;
            copy[deg + k] -= coef;
        }
        *poly = copy;
    }
    int deg_num = numerator.rbegin()->first;
    int deg_den = denominator.rbegin()->first;
    int deg_quo = deg_num - deg_den;
    int sign = numerator.rbegin()->second;

    /*配列にコピー*/

    int num[deg_num + 1];
    int den[deg_den + 1];
    int quo[deg_quo + 1];

    for (int i = 0; i <= deg_num; ++i)
    {
        num[i] = numerator[i];
    }
    for (int i = 0; i <= deg_den; ++i)
    {
        den[i] = denominator[i];
    }

    for (int i = deg_quo; i >= 0; --i)
    {
        int c = sign * num[i + deg_den];
        quo[i] = c;
        for (int j = 0; j <= deg_den; ++j)
        {
            num[i + j] -= c * den[j];
        }
        cout << i << " " << c << endl;
    }
}

出力例:

15
8 1
7 -1
6 0
5 1
4 -1
3 1
2 0
1 -1
0 1

意味するところは,

\begin{align} \Phi_{15}(X) &= X^8-X^7+X^5-X^4+X^3-X+1. \end{align}

このプログラムを使って, ある整数が最初に現れる円分多項式の位数を計算していく. 正負を分けて考えたいので, 2以上の自然数 m に対して, a(n, k) = \pm m を満たす k が存在する最小の位数 n を n^{\pm}_m で表すことにする. 結果を貼ろう. 300行以上あるのでダーッとスクロールしてほしい.

mn^{+}_mn^{-}_m
2165105
3595385
417851365
517852145
628052805
731353135
865456545
965457917
101046510465
111046510465
121046510465
131046510465
141046510465
151130511305
161130511305
171130511305
181130511305
191130511305
201130511305
211130511305
221501515015
231130517255
242061517255
251725517255
262061520615
272061525935
282656526565
292656526565
302656526565
312656526565
322656526565
332656526565
342656526565
352656526565
362656526565
372656526565
382656526565
392656526565
402656526565
412656526565
422656526565
432656526565
442656526565
452656526565
462656526565
472656526565
482656526565
492656526565
502656540755
512656526565
524075526565
534075526565
544075526565
552656540755
562656540755
574075540755
584075540755
592656540755
604075540755
614075540755
624075540755
634075540755
644075540755
654075540755
664075540755
674075540755
684075540755
694075540755
704075540755
714075540755
724075540755
734075540755
744075540755
754075540755
764075540755
774075540755
784075540755
794075540755
804075540755
814075540755
824075540755
834075540755
844075540755
854075540755
864075540755
874075540755
884075540755
894075540755
904075540755
914075540755
924075540755
934075540755
944075540755
954075540755
964075540755
974075540755
984075540755
994075540755
1004075540755
1014075540755
1024075540755
1034075540755
1044075540755
1054075540755
1064075540755
1074075540755
1084075540755
1094075540755
1104075540755
1114075540755
1124075540755
1134075540755
1144075540755
1154075540755
1164075540755
1174075540755
1184075540755
1194075540755
1204075540755
1214075540755
1224075540755
1234075540755
1244075540755
1254075540755
1264075540755
1274075540755
1284075540755
1294075540755
1304075540755
1314075540755
1324075540755
1334075540755
1344075540755
1354075540755
1364075540755
1374075540755
1384075540755
1394075540755
1404075540755
1414075540755
1424075540755
1434075540755
1444075540755
1454075540755
1464075540755
1474075540755
1484075540755
1494075540755
1504075540755
1514075540755
1524075540755
1534075540755
1544075540755
1554075540755
1564075540755
1574075540755
1584075540755
1594075540755
1604075540755
1614075540755
1624075540755
1634075540755
1644075540755
1654075540755
1664075540755
1674075540755
1684075540755
1694075540755
1704075540755
1714075540755
1724075540755
1734075540755
1744075540755
1754075540755
1764075540755
1774075540755
1784075540755
1794075540755
1804075540755
1814075540755
1824075540755
1834075540755
1844075540755
1854075540755
1864075540755
1874075540755
1884075540755
1894075540755
1904075540755
1914075540755
1924075540755
1934075540755
1944075540755
1954075540755
1964075540755
1974075540755
1984075540755
1994075540755
2004075540755
2014075540755
2024075540755
2034075540755
2044075540755
2054075540755
2064075540755
2074075540755
2084075540755
2094075540755
2104075540755
2114075540755
2124075540755
2134075540755
2144075540755
2154075540755
2164075540755
2174075540755
2184075540755
2194075540755
2204075540755
2214075540755
2224075540755
2234075540755
2244075540755
2254075540755
2264075540755
2274075540755
2284075540755
2294075540755
2304075540755
2314075540755
2324075540755
2334075540755
2344075540755
2354075540755
2364075540755
2374075540755
2384075540755
2394075540755
2404075540755
2414075540755
2424075540755
2434075540755
2444075540755
2454075540755
2464075540755
2474075540755
2484075540755
2494075540755
2504075540755
2514075540755
2524075540755
2534075540755
2544075540755
2554075540755
2564075540755
2574075540755
2584075540755
2594075540755
2604075540755
2614075540755
2624075540755
2634075540755
2644075540755
2654075540755
2664075540755
2674075540755
2684075540755
26940755-
2704075540755
2714075540755
2724075540755
2734075540755
2744075540755
2754075540755
2764075540755
2774075540755
2784075540755
2794075540755
2804075540755
281-40755
2824075540755
2834075540755
28440755-
28540755-
2864075540755
2874075540755
2884075540755
2894075540755
2904075540755
2914075540755
2924075540755
2934075540755
2944075540755
2954075540755
2964075540755
29740755-
2984075540755
2994075540755
3004075540755
3014075540755
30240755-
3034075540755
3044075540755
3054075540755
3064075540755
3074075540755
3084075540755
3094075540755
3104075540755
3114075540755
31240755-
3134075540755
3144075540755
3154075540755
316-40755
3174075540755
31840755-
319-40755
32040755-
3214075540755
3224075540755
3234075540755
324-40755
3254075540755
3264075540755
3274075540755
3284075540755
3294075540755
3304075540755
3314075540755
3324075540755
3334075540755
33440755-
3354075540755
3364075540755
3374075540755
338-40755
3394075540755
3404075540755
34140755-
3424075540755
343--
3444075540755
34540755-
346-40755
34740755-
3484075540755
3494075540755
35040755-
351-40755
3524075540755
353--
354--
355--
3564075540755
357--
358--
3594075540755

（空欄は60000以上)

分かりやすいように10回以上現れる数は同じ色で塗り分けた.

見ての通りこの範囲ではほとんど40755=3\cdot 5\cdot 11\cdot 13\cdot 19だ. 位数40755で突如として3桁の数が係数として大量に登場するのである. 検証できていないが, 小さいほうから位数を上げていったとき, 現れる係数のバリエーションが跳ね上がる位数が一般に存在するのではないかと予想している.

OEIS上に登録されている関連する数列として以下のふたつを挙げる.

Migotti の定理

Migottiが初めて示したことを述べる前に, 以下の3つの事実について証明なしで述べる(証明はThangadurai[2]を参照. (☆)とメビウス関数の性質を使えばすぐに示される).

Square-free kernel

n が

\begin{gather} n = {p_1}^{e_1} {p_2}^{e_2} \cdots {p_\ell}^{e_{\ell}}, \\ p_1 < p_2 < \cdots < p_\ell,\hspace{12pt} e_i \geq 1 \end{gather}

と素因数分解されるとき,

\begin{align} \kappa(n) = p_1p_2\cdots p_\ell \end{align}

を n の square-free kernel (無平方核) と呼ぶ. n の互いに異なる素因数全ての積である. ABC予想の根基と同じもの.

位数 n の円分多項式について,

\begin{align} \Phi_{n}(X) = \Phi_{\kappa(n)} \left(X^{n/\kappa(n)}\right) \end{align}

が成り立つ. 従って,

\begin{align} a(n, k) &= \left\{\begin{array}{cc} a\left(\kappa(n), k\kappa(n)/n\right) & \frac{n}{\kappa(n)} \mid k\\ 0 & {\rm otherwise} \end{array}\right. \end{align}

偶数位数

n を奇数とする. このとき.

\begin{align} \Phi_{2n}(X) = \Phi_n(-X). \end{align}

従って,

\begin{align} a(2n, k) &= (-1)^ka(n,k). \end{align}

対称性

n \geq 2 に対して,

\begin{align} \Phi_{n}(X) = X^{\phi(n)}\Phi_n(1/X). \end{align}

従って,

\begin{align} a(n, k) &= a(n,\phi(n) - k). \end{align}

ただし \phi(n) はオイラーのトーシェント関数.

2つの素数の積

Migottiは次のことを示した [1].

異なる2つの素数 p,q に対して, 位数 pq の円分多項式の係数は 1,0,-1 のいずれか.


(☆)の関係を使えばこのことは比較的簡単に確かめられる. まず, \Phi_{pq}(X)の具体的な形は, 等比級数を使って,

\begin{align} \Phi_{pq}(X) &= \frac{(X^{pq}-1)(X-1)}{(X^p-1)(X^q-1)}\\ &=(1-X)(1-X^{pq})\sum_{i=0}^\infty X^{ip} \sum_{j=0}^\infty X^{jq}.\\ \end{align}

と表せる. 無限和が現れているが, 実際の次数は \phi(pq) = (p-1)(q-1) だから, X^{pq}がかかる高次の項は無視してよく, 0 \leq k \leq \phi(pq)の範囲で a(pq, k)は

\begin{align} (1-X)\sum_{i=0}^\infty X^{ip} \sum_{j=0}^\infty X^{jq} \end{align}

の k 次の項に一致する. i,j \geq 0 に対して ip+jq=k の解の個数を s(k) とすると, 上の式から, 0\leq k \leq \phi(pq) の範囲で,

\begin{align} a(pq,k) = s(k)-s(k - 1) \end{align}

が成立する. s(k) はこの範囲で 0,1 のどちらかなので(2つ持つとすれば i,j \geq 0 の条件に矛盾する), a(pq,k) は 1,0,-1 のいずれかになる. □

この証明は 多項式の割り算によらずに a(pq,k) を計算する方法も与えている. p=3, q=5 の場合を見てみよう.

\begin{align} \begin{array}{|ccc|} \hline k & (i,j) & s(k) & a(15,k)\\ \hline 0 & (0,0) & 1 & 1 \\ 1 & \times & 0 & -1 \\ 2 & \times & 0 & 0 \\ 3 & (1,0) & 1 & 1 \\ 4 & \times & 0 & -1 \\ 5 & (0,1) & 1 & 1 \\ 6 & (2,0) & 1 & 0 \\ 7 & \times & 0 & -1 \\ 8 & (1,1) & 1 & 1 \\ \hline \end{array} \end{align}

これは確かに上で見た結果と一致している. ここでは s(k) の取りうる値を評価するにとどめたが, LemとLeung は明示的な表式に簡潔な証明を与えている [ 5].

さて, この章の命題を組み合わせると, 以下のことが分かる.

p,q が異なる2つの奇素数であるとき, 位数 n=2^{\alpha} p^{\beta} q^{\gamma} の円分多項式の係数には 1,0,-1 しか現れない. すなわち. \begin{align} a(2^\alpha p^\beta q^\gamma, k) \in \{1,0,-1\}. \end{align}


逆に, 1,0,-1 以外が係数に現れるとすれば, 異なる3つ以上の奇素数を約数に持つことになる. そのような整数の最小の例は 3\cdot 5\cdot 7=105 であって, 実際, 位数105で初めて 1,0,-1 以外の係数が現れるということは, 繰り返し述べてきたことである.

最小出現次数

Migottiの証明では等比級数を使った. これは良いアイデアである. ほとんど同語反復だが,

円分多項式は「円分多項式の係数」という数列の母函数である


ということに着目すれば, なすべきことは自ずと見えてくる.

以下 n \geq 2 とする. というのも,

\begin{align} \sum_{d\mid n} \mu(d) = \left\{\begin{array}{cc} 1 & n = 1\\ 0 & n\geq 2 \end{array}\right. \end{align}

と, n=1 のときだけ例外的な扱いが必要になるため. また, 記法を簡略化するため, メビウス関数は非整数に対して 0 を取るものとして定義域を拡張しておく.

さて, 二項定理を使うことで,

\begin{align} \Phi_n(X) &= \prod_{d\mid n} \left(1-X^d\right)^{\mu(n/d)}\\ &=\prod_{i=1}^\infty \left(1-X^i\right)^{\mu(n/i)}\\ &=\prod_{i=1}^\infty \sum_{m=0}^\infty \binom{\mu(n/i)}{m}(-X^i)^m\\ &=\sum_{k=0}^\infty \left(\sum_{ \begin{array}{cc} m_1+2m_2+3m_3+\cdots = k \\ \forall i\in \mathbb{N},\ m_i \in \mathbb{Z}_{\geq 0} \end{array} } (-1)^{m_1+m_2+m_3+\cdots} \binom{\mu(n)}{m_1}\binom{\mu(n/2)}{m_2}\binom{\mu(n/3)}{m_3}\cdots \right) X^k \end{align}

から,

\begin{align} a(n,k) = \sum_{ \begin{array}{cc} m_1+2m_2+\cdots+k m_k = k \\ \forall i\in \mathbb{N},\ m_i \in \mathbb{Z}_{\geq 0} \end{array} } (-1)^{m_1+m_2+\cdots+m_k} \binom{\mu(n)}{m_1}\binom{\mu(n/2)}{m_2}\cdots\binom{\mu(n/m)}{m_k} \end{align}
・・・・・・(☆☆)

が導かれる. これが円分多項式の係数を求める明示公式である. 1974年, Endo はこの式を用いて 次数 k\leq 6 で円分多項式の係数が 1,0,-1 に限られることを示した [6].

上の式において, 和を取る範囲が

\begin{gather} m_1+2m_2+\cdots+k m_k = k \\ \forall i\in \mathbb{N},\ m_i \in \mathbb{Z}_{\geq 0} \end{gather}

となっていることに注目. k の分割全体の和を取るのである. \mu(n/i) = \lambda_i と書くことにすると, 最初のいくつかは

\begin{align} a(n,0) &= 1\\ a(n,1) &= - \binom{\lambda_1}{1}\\ a(n,2) &= \binom{\lambda_1}{2} - \binom{\lambda_2}{1}\\ a(n,3) &= -\binom{\lambda_1}{3} + \binom{\lambda_1}{1}\binom{\lambda_2}{1} - \binom{\lambda_3}{1}\\ a(n,4) &= \binom{\lambda_1}{4} - \binom{\lambda_1}{2}\binom{\lambda_2}{1} +\binom{\lambda_2}{2} + \binom{\lambda_1}{1}\binom{\lambda_3}{1} - \binom{\lambda_4}{1} \end{align}

となる. 各項の下にヤング図形を並べてみたくなる.

余談だが, \mu(n/i) を数列 s_i に一般化して, これに対して決まる

\begin{align} \prod_{i=1}^\infty \left(1-X^i\right)^{s_i}\\ \end{align}

を考えると, s_i = 1 の場合, 五角数定理に登場する無限積(デデキントの η 函数の q^{-1/24}倍), s_i=-1 の場合, 分割数の母函数になる. 項数が無限か有限かの違いがあるとはいえ, 円分多項式の係数はそれらの仲間だと言える.

話を戻して, 上の式を使うと, 1次の項a(n,1) = -\mu(n) が 1,0,-1 になるのは明らか.

2次以上の項を評価していく……前に, 位数 n はこれ以降 square-free(無平方) の場合のみを考えることにする. なぜなら, これから考えるのは a(n,k) = m を満たす最小の次数 k を考えることだから. 位数 n も次数 k も, square-free kernel \kappa(n) の位数を持つ円分多項式の方が, より低位数・低次数に同じ係数が現れる. すると, a(n,k) は \mu(n) と, k 以下の素数それぞれを約数に持つか持たないかで決まる. つまり, p を k を超えない最大の素数として. squar-free な n が

\begin{gather} n = 2^{e_2} 3^{e_3} 5^{e_7} \cdots p^{e_p} r \\ (2^{e_2} 3^{e_3} 5^{e_7} \cdots p^{e_p}, r) = 1 \end{gather}

と素因数分解されるとき, 各成分が0, 1 のいずれかである e_2, e_3, e_5, \cdots , e_p の列と, \mu(n) が 1, -1 のどちらの値を取るかだけ考えればよい. ビット全探索の使いどころである.

#include <iostream>
#include <vector>
using namespace std;

int binom(int mu, int k)
{
    if (k == 0)
        return 1;
    else if (mu == 0)
        return 0;
    else if (mu == -1)
        return ((k & 1) == 0) ? 1 : -1;
    else if (mu == 1)
        return (k == 1) ? 1 : 0;
}

class Partition_generator
{
public:
    Partition_generator(int n);
    int *next();
    int size();
    bool has_next();

private:
    int n;
    int *arr;
    int h;
};

Partition_generator::Partition_generator(int n)
{
    this->n = n;
    arr = new int[n + 1];
    for (int i = 0; i <= n; ++i)
        arr[i] = 0;
    this->h = 1;
    arr[1] = n;
}

int Partition_generator::size()
{
    return h + 1;
}

int *Partition_generator::next()
{
    int x = arr[h - 1] + 1;
    int y = arr[h] - 1;
    --h;
    while (x <= y)
    {
        arr[h] = x;
        y -= x;
        ++h;
    }
    arr[h] = x + y;
    return arr;
}

bool Partition_generator::has_next()
{
    return h != 0;
}

const int primes[25] = {
    2, 3, 5, 7, 11,
    13, 17, 19, 23, 29,
    31, 37, 41, 43, 47,
    53, 59, 61, 67, 71,
    73, 79, 83, 89, 97};

int main()
{
    int n;
    cin >> n;

    Partition_generator pg(n);
    vector<int *> mult; //nの分割に現れる数の重複度
    while (pg.has_next())
    {
        int *m = new int[n + 1];
        for (int i = 0; i <= n; ++i)
            m[i] = 0;
        int *part = pg.next();
        int size = pg.size();
        for (int i = 0; i < size; ++i)
        {
            ++m[part[i]];
            ++m[0]; //総和
        }
        mult.push_back(m);
    }

    int part_num = mult.size(); //nの分割数
    int m_p = 0;                //nを超えない最大の素数のインデックス
    while (primes[m_p] <= n)
        ++m_p;
    int *primes_leq = new int[m_p];
    for (int i = 0; i < m_p; ++i)
        primes_leq[i] = primes[i];
    int **prime_power = new int *[n + 1];
    for (int i = 1; i <= n; ++i)
    {
        int i_copy = i;
        prime_power[i] = new int[m_p];
        for (int j = 0; j < m_p; ++j)
        {
            prime_power[i][j] = 0;
            int p = primes_leq[j];
            while (i_copy % p == 0)
            {
                i_copy /= p;
                ++prime_power[i][j];
            }
        }
    }

    int bin[m_p];
    int N = 1 << m_p;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < m_p; ++j)
            bin[j] = (i >> j) & 1;

        int mu[n + 1];
        for (int j = 1; j <= n; ++j)
        {
            int e = 0;
            bool is_zero = false;
            for (int l = 0; l < m_p; ++l)
            {
                int s = bin[l] - prime_power[j][l];
                if (s < 0 || 1 < s)
                {
                    is_zero = true;
                    break;
                }
                else
                    e += s;
            }
            mu[j] = is_zero ? 0 : (((e & 1) == 0) ? 1 : -1);
        }

        for (int parity = -1; parity <= 1; parity += 2)
        {
            int cycl_coef = 0;
            for (int j = 0; j < part_num; j++)
            {
                int *m = mult.at(j);
                int prod = ((m[0] & 1) == 0) ? 1 : -1;
                for (int l = 1; l <= n; ++l)
                    prod *= binom(parity * mu[l], m[l]);
                cycl_coef += prod;
            }
            cout << i << " " << parity * mu[1] << " " << cycl_coef << endl;
        }
    }
    return 0;
}

出力例

3
0 -1 1
0 1 0
1 1 -1
1 -1 0
2 1 1
2 -1 0
3 -1 -1
3 1 0

第1列は

\begin{align} e_2 + 2e_3 + 2^2 e_5 + 2^3 e_7 \cdots \end{align}

の値. 第2列は \mu(n). 第3列 は a(n,k). k=2,\cdots,7 の結果を以下にまとめる:

\begin{align} \begin{array}{|crr|} \hline e_2 & \mu(n) & a(n,2) \\ \hline 0 & 1 & 0 \\ 0 & -1 & 1 \\ 1 & 1 & 1 \\ 1 & -1 & 0 \\ \hline \end{array} \end{align}
\begin{align} \begin{array}{|ccrr|} \hline e_2 & e_3 & \mu(n) & a(n,3) \\ \hline 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 \\ 1 & 0 & 1 & -1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & -1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & -1 & -1 \\ \hline \end{array} \end{align}
\begin{align} \begin{array}{|ccrr|} \hline e_2 & e_3 & \mu(n) & a(n,4) \\ \hline 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & -1 & 0 \\ 0 & 1 & 1 & -1 \\ 0 & 1 & -1 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & -1 & -1 \\ \hline \end{array} \end{align}
\begin{align} \begin{array}{|cccrr|} \hline e_2 & e_3 & e_5 & \mu(n) & a(n,5) \\ \hline 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 & 1 \\ 1 & 0 & 0 & 1 & -1 \\ 1 & 0 & 0 & -1 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & -1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & -1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & -1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & -1 & -1 \\ 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & -1 & -1 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & -1 & -1 \\ \hline \end{array} \end{align}
\begin{align} \begin{array}{|cccrr|} \hline e_2 & e_3 & e_5 & \mu(n) & a(n,6) \\ \hline 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & -1 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & -1 & 0 \\ 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & -1 & 1 \\ 0 & 0 & 1 & 1 & -1 \\ 0 & 0 & 1 & -1 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & -1 & -1 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & -1 & -1 \\ 1 & 1 & 1 & 1 & -1 \\ 1 & 1 & 1 & -1 & 0 \\ \hline \end{array} \end{align}
\begin{align} \begin{array}{|ccccrr|} \hline e_2 & e_3 & e_5 & e_7 & \mu(n) & a(n,7) \\ \hline 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & -1 & 1 \\ 1 & 0 & 0 & 0 & 1 & -1 \\ 1 & 0 & 0 & 0 & -1 & 0 \\ 0 & 1 & 0 & 0 & 1 & -1 \\ 0 & 1 & 0 & 0 & -1 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & -1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & -1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & -1 & 0 \\ 0 & 1 & 1 & 0 & 1 & -1 \\ 0 & 1 & 1 & 0 & -1 & -1 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & -1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & -1 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 & -1 & -1 \\ 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & -1 & -1 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & -1 & -1 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & -1 & -1 \\ 0 & 1 & 1 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & -1 & -2 \\ 1 & 1 & 1 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & -1 & 0 \\ \hline \end{array} \end{align}

e_3=e_5=e_7=1, \mu(n) = -1 において -2 が現れている. これを満たす整数(無数に存在する)で最小の n が言うまでもなく 105 である. 上の計算から次のことが言える:

0 \leq k \leq 6 に対して, \begin{align} a(n,k) \in \{1,0,-1\}. \end{align}


整数 m に対して, a(n,k) = m を満たす最小の k を最小出現次数と呼ぶことにしよう. 上の命題は, 「2,-2 の最小出現次数が 7 である」と言い換えられる. では、3,-3 ではどうだろうか. 式(☆☆)を使って計算し続けることは可能だが, k の分割全体の和を取るため, 和を取るべき項数が非常に早く増加し, 計算時間の点で問題がある. より良いアルゴリズムを考えよう.

再帰的アルゴリズム

1991年, GrytczukとTropakはEndoの結果を発展させ, 計算機を使う方法で \pm 2, \pm 3,\cdots,\pm 9, 10 の最小出現次数を決定した [7].

再び式(☆)に立ち返ろう. 両辺の対数微分によって,

\begin{align} \frac{\Phi'_n(X)}{\Phi_n(X)} = \sum_{d\mid n} \mu\left(\frac{n}{d}\right)\frac{dX^{d-1}}{X^d-1} \end{align}

を得る. 左辺を \Gamma_n(X) としよう. 級数展開によって,

\begin{align} \Gamma_n(X) &\equiv \sum_{d\mid n} \mu\left(\frac{n}{d}\right)\frac{dX^{d-1}}{X^d-1}\\ &= \sum_{d\mid n} (-d)\mu\left(\frac{n}{d}\right)\left(X^{d-1}+X^{2d-1}+X^{3d-1}+\cdots\right)\\ &= \sum_{d\mid n} (-d)\mu\left(\frac{n}{d}\right)\sum_{i=1}^\infty X^{id-1}.\\ \end{align}

j\geq 0 次の項の係数を b(n,j) で表すことにすると,

\begin{align} b(n,j) &= \sum_{\begin{array}{cc} d\mid n, i\geq 1, \\ id\!-\!1 = j \end{array}} (-d)\mu\left(\frac{n}{d}\right)\\ &= \sum_{\begin{array}{cc} d\mid{\rm gcd}(n,j+1) \end{array}} (-d)\mu\left(\frac{n}{d}\right)\\ \end{align}

を得る. 非整数に対してメビウス関数の値を 0 としていたことを思い出し,

\begin{align} b(n,j) = \sum_{d\mid (j+1)} (-d)\mu\left(\frac{n}{d}\right) \end{align}

を得る.

\begin{align} \Phi_n'(X) &= \Phi_n(X)\Gamma_n(X) \end{align}

の各項は, いま,

\begin{align} a(n,1) + 2a(n,2)X &+ 3a(n,3)X^2 + 4a(n,4)X^3 + \cdots\\ &=\left(a(n,0) + a(n,1)X + a(n,2)X^2 + a(n,3)X^3 + \cdots\right)\\ &\hspace{16pt}\times\left(b(n,0) + b(n,1)X + b(n,2)X^2 + b(n,3)X^3 + \cdots\right). \end{align}

となっている. 両辺 X に関して同次の項を比較することで,

\begin{align} a(n,1) &= a(n,0)b(n,0)\\ 2a(n,2) &= a(n,0)b(n,1) + a(n,1)b(n,0)\\ 3a(n,3) &= a(n,0)b(n,2) + a(n,1)b(n,1) + a(n,2)b(n,0)\\ &\cdots \end{align}

を次々に得る. 一般に, k\geq 0 に対して,

\begin{align} a(n,k+1) = \frac{1}{k+1}\sum_{j=0}^{k} a(n,j)b(n,k-j). \end{align}

となる. これは 本質的に, 1 の原始 n 乗根に対する ニュートンの恒等式である. Grytczuk-Tropakは b(n,j) に関してやや異なる表式を用いたが, ここではこの方法を使おう.

#include <iostream>
#include <string>

using namespace std;

const int PRIMES = 28;
const int primes[PRIMES] = {
    -1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101, 103};

int value(int bin)
{
    int n = 1;
    for (int i = 1; i < PRIMES; ++i)
    {
        if (((bin >> i) & 1) == 1)
        {
            n *= primes[i];
        }
    }
    return n;
}

int main()
{
    int j_max;
    cin >> j_max;

    //根基のルックアップテーブルを作る
    const int n_max = 100;
    int *rad = new int[n_max];
    for (int n = 1; n < n_max; ++n)
    {
        int m = n;
        int i = 1;
        int bin = 0;
        int parity = 0;
        while (m > 1)
        {
            int p = primes[i];
            if (m % p == 0)
            {
                bin += (1 << i);
                parity ^= 1;
                while (m % p == 0)
                {
                    m /= p;
                }
            }
            ++i;
        }
        bin ^= parity;
        rad[n] = bin;
    }

    //ceil_p_ind[n]はnを超える最小の素数のインデックス
    // n=14 なら primes[6] = 13  < n < 17 = primes[7]なので7.
    // n=17 なら primes[7] = 17 == n < 19 = primes[8]なので8.
    int *ceil_p_ind = new int[n_max];
    for (int n = 1; n < n_max; ++n)
    {
        int i = 1;
        while (primes[i] <= n)
        {
            ++i;
        }
        ceil_p_ind[n] = i;
    }

    int **a = new int *[n_max];
    int **b = new int *[n_max];

    for (int j = 0; j < j_max; ++j)
    {
        cout << "degree = " << j + 1 << endl;
        int ceil = ceil_p_ind[j + 1];
        int range = 1 << ceil;
        b[j] = new int[range];
        for (int n = 0; n < range; ++n)
        {
            b[j][n] = 0;
            int r = rad[j + 1];
            int slots = 0;
            for (int i = 1; i < PRIMES; ++i)
            {
                slots += (r >> i) & 1;
            }
            int range_d = 1 << slots;
            for (int s = 0; s < range_d; ++s)
            {
                int d = 0,h = 0;
                for (int i = 1; i < PRIMES; ++i)
                {
                    if ((r >> i) & 1)
                    {
                        d ^= ((s >> h) & 1) ? (((s >> h) & 1) << i) + 1 : 0;
                        ++h;
                    }
                }
                if ((((~n) & d) >> 1) == 0)
                {
                    b[j][n] += -value(d) * (((n ^ d) & 1) == 0 ? 1 : -1);
                }
            }
        }

        a[j + 1] = new int[range];
        for (int n = 0; n < range; ++n)
        {
            int sum = 0;
            sum += b[j][n];
            for (int k = 1; k <= j; ++k)
            {
                int window_a = (1 << ceil_p_ind[k]) - 1;
                int window_b = (1 << ceil_p_ind[j - k + 1]) - 1;
                sum += a[k][n & window_a] * b[j - k][n & window_b];
            }
            a[j + 1][n] = sum / (j + 1);
            cout << n << " " << a[j + 1][n] << endl;
        }
    }
    return 0;
}

7
degree = 1
0 -1
1 1
degree = 2
0 0
1 1
2 1
3 0
 (略)
26 1
27 -1
28 0
29 -2
30 2
31 0

出力内容は先のプログラムとほぼ同じだが, \mu(n) の値が1,-1 ならそれぞれ最下位ビットに 0,1 を充てることにして, 素数の冪はひとつずつ上位にシフトさせている. 計算速度は格段に速く, 位数50程度までの計算が1日近くかかっていたところ, 数分で完了する. ただし, 巨大な配列を全てメモリ上に載せるため位数100程度が限界になる. 今後の改善点だろう.

ともかく, Grytczuk-Tropak が30年前に与えた結果よりかなり先まで進むことができた. 以下に結果を載せる.

第1列の数 m に対する最小出現次数が第2列のk_{\rm min}である.

a(n,k_{\rm min})=m を満たす最小の位数 n の, 各列の素数に対する冪を第3列以降に並べた. ただし \cdot は 0 を表す. たとえばm = 3 の最小出現次数は 17 で, これを実現する最小の位数は n=2\cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 = 646646. デカい.

\begin{align} \begin{array}{|rc|cccccccccccccccccccccccc|} \hline m & k_{\rm min} & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 & 73 & 79 & 83 & 89 \\ \hline 2 & 7 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -2 & 7 & \cdot & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 3 & 17 & 1 & \cdot & \cdot & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -3 & 17 & \cdot & \cdot & \cdot & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 4 & 23 & 1 & \cdot & \cdot & \cdot & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -4 & 23 & \cdot & \cdot & \cdot & \cdot & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 5 & 30 & \cdot & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -5 & 35 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 6 & 36 & \cdot & \cdot & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -6 & 39 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 7 & 43 & 1 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -7 & 43 & \cdot & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 8 & 46 & \cdot & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -8 & 47 & \cdot & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 9 & 47 & 1 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -9 & 47 & \cdot & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 10 & 52 & \cdot & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -10 & 53 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 11 & 53 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -11 & 53 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 12 & 53 & \cdot & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -12 & 53 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 13 & 53 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -13 & 53 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 14 & 59 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -14 & 59 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 15 & 59 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -15 & 59 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ \hline \end{array} \end{align}
\begin{align} \begin{array}{|rc|cccccccccccccccccccccccc|} \hline m & k_{\rm min} & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 & 73 & 79 & 83 & 89 \\ \hline 16 & 65 & \cdot & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -16 & 65 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 17 & 70 & \cdot & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -17 & 71 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 18 & 70 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -18 & 73 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 19 & 70 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -19 & 73 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 20 & 70 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -20 & 73 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 21 & 70 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -21 & 73 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & 1 & \cdot & \cdot & \cdot \\ 22 & 70 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -22 & 75 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ 23 & 70 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -23 & 77 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ 24 & 70 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ -24 & 77 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 25 & 76 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -25 & 77 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 26 & 76 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -26 & 77 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ 27 & 76 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot \\ -27 & 79 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 28 & 76 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & \cdot & \cdot \\ -28 & 79 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & 1 & \cdot & \cdot \\ 29 & 82 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -29 & 83 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ 30 & 82 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -30 & 83 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ \hline \end{array} \end{align}
\begin{align} \begin{array}{|rc|cccccccccccccccccccccccc|} \hline m & k_{\rm min} & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 & 73 & 79 & 83 & 89 \\ \hline 31 & 82 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -31 & 83 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ 32 & 82 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -32 & 83 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ 33 & 82 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -33 & 83 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot \\ 34 & 82 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -34 & 83 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & 1 & \cdot \\ 35 & 82 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot & 1 & \cdot & \cdot \\ -35 & 87 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot \\ 36 & 87 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot \\ -36 & 87 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & \cdot \\ 37 & 88 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & 1 & \cdot \\ -37 & 89 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & 1 & \cdot & \cdot & 1 & \cdot & \cdot \\ 38 & 89 & \cdot & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & 1 & \cdot & 1 & 1 & \cdot & 1 \\ -38 & 89 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & 1 & \cdot & 1 & \cdot & \cdot & 1 & \cdot & 1 & 1 & \cdot & 1 \\ 39 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot \\ -39 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot \\ 40 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 1 & \cdot \\ -40 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & 1 & \cdot \\ 41 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ -41 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot & \cdot \\ 42 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & 1 & \cdot & \cdot & \cdot \\ -42 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & 1 & \cdot & \cdot & \cdot \\ 43 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ -43 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ 44 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot \\ -44 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot \\ 45 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ -45 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ \hline \end{array} \end{align}
\begin{align} \begin{array}{|rc|cccccccccccccccccccccccc|}\hline m & k_{\rm min} & 2 & 3 & 5 & 7 & 11 & 13 & 17 & 19 & 23 & 29 & 31 & 37 & 41 & 43 & 47 & 53 & 59 & 61 & 67 & 71 & 73 & 79 & 83 & 89 \\ \hline 46 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & 1 & \cdot & \cdot & \cdot \\ -46 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & 1 & \cdot & \cdot & \cdot \\ 47 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & 1 & \cdot \\ -47 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & 1 & \cdot \\ 48 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot \\ -48 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot \\ 49 & 89 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & 1 \\ -49 & 89 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & 1 \\ 50 & 95 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ -50 & 95 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & \cdot & \cdot \\ 51 & 95 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & 1 & \cdot & \cdot \\ -51 & 95 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot & 1 & \cdot & \cdot \\ 52 & 95 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot \\ -52 & 95 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & 1 & \cdot & \cdot & \cdot \\ 53 & 95 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot \\ -53 & 95 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & \cdot & \cdot \\ 54 & 95 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot \\ -54 & 95 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot \\ 55 & 95 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot \\ -55 & 95 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot \\ 56 & 99 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot \\ -56 & 99 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & \cdot & \cdot & \cdot & \cdot \\ 57 & 99 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & 1 & \cdot \\ -57 & 99 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & \cdot & \cdot & \cdot & 1 & \cdot \\ 58 & 99 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot & 1 \\ -58 & 99 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & \cdot & 1 \\ 59 & 99 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & 1 & \cdot \\ -59 & 99 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & \cdot & 1 & \cdot \\ 60 & 99 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 \\ -60 & 99 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & \cdot & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline \end{array} \end{align}

この結果も面白い. Grytczuk-Tropak がギリギリ到達していなかった範囲だが, 最低出現次数を 53 とする係数は 7 個もあるのだ. 観察するともっと深い理解につながっていきそうだが, とりあえず結果を載せるにとどめておく.

まとめ

本記事では円分多項式の係数のもつ諸性質について述べた. 位数 105 において初めて 1,0,-1 以外の数が現れる理由に始まり, 全ての位数で 0 - 6 次の項もまたそうであることを示した. 最小出現次数に関しては, 新しい計算結果を与えた.

References

  1. Migotti, A., Aur Theorie der Kreisteilungsgleichung, and Z. B. der Math. "Naturwiss." Classe der Kaiserlichen Akademie der Wissenschaften, Wien 87 (1883): 7-14.
  2. Thangadurai, Ravindranathan. "On the coefficients of cyclotomic polynomials." Cyclotomic fields and related topics (Pune, 1999) (2000): 311-322. http://www.hri.res.in/~thanga/papers/th.pdf
  3. Suzuki, Jiro. "On coefficients of cyclotomic polynomials." Proceedings of the Japan Academy, Series A, Mathematical Sciences 63.7 (1987): 279-280. https://doi.org/10.3792/pjaa.63.279
  4. 105：円分多項式の係数と鈴木の定理 - INTEGERS http://integers.hatenablog.com/entry/2016/02/14/175138 (現在は非公開)
  5. Lam, Tsit-Yeun, and Ka Hin Leung. "On the cyclotomic polynomial Φ pq (X)." The American Mathematical Monthly 103.7 (1996): 562-564. https://doi.org/10.1080/00029890.1996.12004786
  6. Endo, Mikihito. "On the coefficients of the cyclotomic polynomials", Comment. Math. Univ. St. Pauli, 23, (1974), 121-126. http://doi.org/10.14992/00010358
  7. Grytczuk, A., and B. Tropak. "A numerical method for the determination of the cyclotomic polynomial coefficients." Computational number theory (Debrecen, 1989) (1991): 15-19.https://doi.org/10.1515/9783110865950.15