円分多項式の係数の計算

#はじめに

- [円分多項式](https://ja.wikipedia.org/wiki/%E5%86%86%E5%88%86%E5%A4%9A%E9%A0%85%E5%BC%8F)
- 次数が105になって初めて係数に0,1,-1以外が現れるということなので、具体的に計算してみた。

#係数を計算するプログラム

円分多項式の係数を計算して、latex形式で出力する。

```c#
public static void Run()
{
    var poly_list = new List<List<int>>();
    poly_list.Add(new List<int>() { 1 });
    int n_max = 385;
    for (int n = 1; n <= n_max; n++)
    {
        var poly = new List<int>();
        for (int j = 0; j <= n; j++) poly.Add(0);
        poly[0] = 1;
        poly[n] = -1;
        for (int d = 1; d < n; d++)
        {
            if (n % d != 0) continue;
            poly = Devide(poly, poly_list[d]);
        }
        poly_list.Add(poly);
        Console.WriteLine("\\Phi_{{{0}}}&={1}\\\\", n, Str(poly));
    }
}
static List<int> Devide(List<int> numerator, List<int> denominator)
{
    var result = new List<int>();
    for (int i = 0; i <= numerator.Count - denominator.Count; i++)
    {
        result.Add(numerator[i]);
        for (int j = 1; j < denominator.Count; j++)
        {
            numerator[i + j] -= numerator[i] * denominator[j];
        }
    }
    return result;
}
static string Str(List<int> poly)
{
    var sb = new StringBuilder();
    var dim = poly.Count - 1;
    for (int i = 0; i <= dim; i++)
    {
        int c = poly[i];
        if (c == 0) continue;
        if (c > 0 && i > 0)
        {
            sb.Append("+");
        }
        if (c < 0)
        {
            sb.Append("-");
            c = -c;
        }
        var d = dim - i;
        if (c > 1 || d == 0)
        {
            sb.Append(c);
        }
        if (d == 1)
        {
            sb.Append("x");
        }
        else if (d > 1)
        {
            sb.AppendFormat("x^{{{0}}}", d);
        }
    }
    return sb.ToString();
}
```

#出力結果

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

#おわりに

- 係数に初めて2が現れるのは次数105、初めて3が現れるのは次数385であることが分かった。
- 以下、次数1365で4、次数1785で5、次数2805で6、次数3135で7、次数6545で8と9、と続く。