Circle division polynomial

In algebra , circular division polynomials (also: cyclotomic polynomials ) are used to investigate subdivisions of the unit circle into equal parts. Under th cyclotomic refers to that of integer polynomial greatest degree with leading coefficient 1, but shares to all with is prime. Its zeros above are exactly the primitive -th roots of unity , whereby the numbers to be coprime runs between and . ${\displaystyle n}$ ${\displaystyle \Phi _{n}}$ ${\displaystyle x^{n}-1}$ ${\displaystyle x^{d}-1}$ ${\displaystyle d<n}$ ${\displaystyle \mathbb {C} }$ ${\displaystyle n}$ ${\displaystyle e^{2\pi \cdot \mathrm {i} k/n}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle 1}$ ${\displaystyle n}$

The term "circle division polynomial" comes from the geometric problem of circle division , ie the construction of a regular polygon limited to the Euclidean tools of compasses and ruler . For which corner this works can be found in the article Constructible Polygon . ${\displaystyle n}$

properties

The decomposition of the -th circular division polynomial into linear factors gives ${\displaystyle n}$

${\displaystyle \Phi _{n}(x)=\!\!\!\!\prod _{1\leq k\leq n \atop \operatorname {ggT} (k,n)=1}\!\!\!\!\left(x-e^{2\pi \cdot \mathrm {i} k/n}\right)}$

Hence the degree of is equal , the number of coprime numbers is below . The function defined in this way is of considerable importance as Euler's Phi function in number theory . ${\displaystyle \Phi _{n}}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \varphi }$

The reverse applies to the product presentation

${\displaystyle x^{n}-1=\prod _{1\leq k\leq n}\left(x-e^{2\pi \cdot \mathrm {i} k/n}\right)=\prod _{d\mid n}\prod _{1\leq k\leq n \atop \operatorname {ggT} (k,n)=d}\left(x-e^{2\pi \cdot \mathrm {i} k/n}\right)=\prod _{d\mid n}\Phi _{n/d}(x)=\prod _{d\mid n}\Phi _{d}(x)}$

The -th circle division polynomial has integer coefficients, so it is in . It is there and in an irreducible polynomial , hence the minimal polynomial of every primitive -th root of unity. Thus the remainder class ring is even a body , namely the smallest, in which the unit circle of the complex plane can be broken down into parts of equal length in such a way that all subdivision points belong to the body. It is therefore called a circle dividing body . ${\displaystyle n}$ ${\displaystyle \mathbb {Z} [x]}$ ${\displaystyle \mathbb {Q} [x]}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Q} [x]/(\Phi _{n})}$ ${\displaystyle n}$

generalization

The notion of the circular division polynomial can be generalized to the roots of unity over any field. In this way, in particular, all finite bodies result as circle division bodies over their prime body .

Examples

If n is a prime number (e.g. n = 2, 3, 5, 7, 11, 13) then applies

${\displaystyle ~\Phi _{n}(x)=1+x+x^{2}+\cdots +x^{n-1}=\sum _{i=0}^{n-1}x^{i}.}$

More generally: If there is a prime power (e.g. n = 2, 3, 4, 5, 7, 8, 9, 11, 13, 16) then applies ${\displaystyle n=p^{m}}$

${\displaystyle ~\Phi _{n}(x)=1+x^{p^{m-1}}+x^{2p^{m-1}}+\cdots +x^{(p-1)p^{m-1}}=\sum _{i=0}^{p-1}x^{ip^{m-1}}.}$

If n = 2 p is twice an odd prime number p (e.g. n = 6, 10, 14), then the following applies

${\displaystyle ~\Phi _{2p}(x)=1-x+x^{2}-\cdots +x^{p-1}=\sum _{i=0}^{p-1}(-x)^{i}.}$

With these rules (with the exception of n = 12 and n = 15) the following polynomials can be determined:

${\displaystyle ~\Phi _{1}(x)=x-1}$

${\displaystyle ~\Phi _{2}(x)=x+1}$

${\displaystyle ~\Phi _{3}(x)=x^{2}+x+1}$

${\displaystyle ~\Phi _{4}(x)=x^{2}+1}$

${\displaystyle ~\Phi _{5}(x)=x^{4}+x^{3}+x^{2}+x+1}$

${\displaystyle ~\Phi _{6}(x)=x^{2}-x+1}$

${\displaystyle ~\Phi _{7}(x)=x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1}$

${\displaystyle ~\Phi _{8}(x)=x^{4}+1}$

${\displaystyle ~\Phi _{9}(x)=x^{6}+x^{3}+1}$

${\displaystyle ~\Phi _{10}(x)=x^{4}-x^{3}+x^{2}-x+1}$

${\displaystyle ~\Phi _{11}(x)=x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1}$

${\displaystyle ~\Phi _{12}(x)=x^{4}-x^{2}+1}$

${\displaystyle ~\Phi _{13}(x)=x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1}$

${\displaystyle ~\Phi _{14}(x)=x^{6}-x^{5}+x^{4}-x^{3}+x^{2}-x+1}$

${\displaystyle ~\Phi _{15}(x)=x^{8}-x^{7}+x^{5}-x^{4}+x^{3}-x+1}$

${\displaystyle ~\Phi _{16}(x)=x^{8}+1}$

Some more examples that can be calculated using the rules above:

${\displaystyle ~\Phi _{25}(x)=x^{20}+x^{15}+x^{10}+x^{5}+1}$

${\displaystyle ~\Phi _{125}(x)=x^{100}+x^{75}+x^{50}+x^{25}+1}$

${\displaystyle ~\Phi _{49}(x)=x^{42}+x^{35}+x^{28}+x^{21}+x^{14}+x^{7}+1}$

Further calculation options

As mentioned at the beginning, the product presentation applies

${\displaystyle x^{n}-1=\prod _{d\mid n}\Phi _{d}(x)}$.

If the circle division polynomials are known for d < n , one can calculate by polynomial division . For example, n = 21 ${\displaystyle \Phi _{d}(x)}$ ${\displaystyle \Phi _{n}(x)}$

${\displaystyle ~(x^{21}-1)=\Phi _{1}(x)\cdot \Phi _{3}(x)\cdot \Phi _{7}(x)\cdot \Phi _{21}(x)}$

so

${\displaystyle {\begin{aligned}\Phi _{21}(x)&={\frac {x^{21}-1}{(x-1)\cdot (x^{2}+x+1)\cdot (x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1)}}\\&=\ldots =x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x^{3}-x+1\end{aligned}}}$.

Another approach follows from the multiplicative version of the Möbius inversion , which is the equation

${\displaystyle ~\Phi _{n}(x)=\prod _{d\mid n}(x^{d}-1)^{\mu (n/d)}}$

supplies, where the Möbius function denotes. For n = 21 this results ${\displaystyle \mu }$

${\displaystyle {\begin{aligned}\Phi _{21}(x)&=(x^{1}-1)^{\mu (21/1)}\cdot (x^{3}-1)^{\mu (21/3)}\cdot (x^{7}-1)^{\mu (21/7)}\cdot (x^{21}-1)^{\mu (21/21)}\\&={\frac {x-1}{x^{3}-1}}\cdot {\frac {x^{21}-1}{x^{7}-1}}\\&={\frac {1}{x^{2}+x+1}}\cdot (x^{14}+x^{7}+1)\end{aligned}}}$.

As you can see, this expression can be simplified with less effort than in the previous example. In addition, no knowledge of other circle division polynomials is necessary.

Another approach, together with the Fourier representation of functions of the greatest common divisor, also follows from the Möbius inversion , which gives the equation

${\displaystyle ~\Phi _{n}(x)=\prod \limits _{k=1}^{n}{(x^{\operatorname {ggT} (k,n)}-1)^{\cos({\frac {2\pi k}{n}})}}}$

results.

The coefficient problem

It is noticeable that in all previous examples only −1, 0 and +1 appeared as coefficients. In fact, A. Migotti was able to show in 1883 that this is always the case if n is the product of two different prime numbers. On the other hand, it was known since 1931 at the latest that this is not always the case: Issai Schur showed in a letter to Edmund Landau that the coefficients in polynomials can be arbitrarily large.

The smallest n for which a coefficient other than −1, 0 or +1 is possible is . Indeed, the coefficient −2 appears here. Using one of the methods described above, the following circle division polynomial can easily be calculated: ${\displaystyle n=3\cdot 5\cdot 7=105}$

${\displaystyle {\begin{aligned}\Phi _{105}(x)=&\quad 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{aligned}}}$

The first polynomial polynomial with a coefficient whose magnitude is greater than 2 occurs for n = 385 :

${\displaystyle {\begin{aligned}\Phi _{385}(x)=&\quad x^{240}+x^{239}+x^{238}+x^{237}+x^{236}-x^{233}-x^{232}-x^{231}-x^{230}-2x^{229}[\dots ]\\&[\dots ]+x^{134}+x^{133}+2x^{132}+2x^{131}+2x^{130}+2x^{129}+2x^{128}+x^{127}+x^{126}-x^{124}-2x^{123}-2x^{122}-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}[\dots ]\end{aligned}}}$

See also OEIS A013594.

Web links

• Eric W. Weisstein : Cyclotomic Polynomial . In: MathWorld (English).

Individual evidence

1. ↑ Wolfgang Schramm: An alternative product representation for the circular division polynomials . In: Swiss Mathematical Society (Ed.): Elements of Mathematics . 70, No. 4, 2015, pp. 137-143. Retrieved October 10, 2015.
2. ↑ A. Migotti, On the theory of the circular division equation. Seat area Math natural sciences Class of the emperors. Akad. Der Wiss., Vienna 87 (1883), 7-14.
3. ↑ Emma Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial. Bull. Amer. Math. Soc. 42 (1936), no. 6, 389-392.
4. ↑ OEIS A013594