Cirkulärt polynom

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 6 februari 2021; kontroller kräver 3 redigeringar .

Cirkulärt polynom , eller cirkeldelningspolynom , är ett polynom av formen

\Phi _{n}(x)=\prod _{k}(x-\xi _{n}^{k})

var

\xi _{n}^{k}=\cos {\frac {2\pi k}n}+i\sin {\frac {2\pi k}n}

är roten till enhet $n$ , och produkten tas över alla naturliga tal mindre än och coprime till . $k$ $n$ $n$

Egenskaper

Koefficienterna för ett cirkulärt polynom är heltal.
Graden av det cirkulära polynomet , där är Euler-funktionen . ${\mathop {{\mathrm {deg}}}}\,\Phi _{n}=\varphi (n)$ $\varphi$
Det cirkulära polynomet uppfyller förhållandet

\prod _{{d|n}}\Phi _{{d}}(x)=x^{n}-1

där produkten tas över alla positiva delare av , inklusive 1 och sig själv . Denna jämlikhet kan skrivas om på följande sätt:

d

n

n

\Phi _{n}(x)={\frac {x^{n}-1}{\prod _{{d|n,\,d<n}}\Phi _{d}(x))) .

För ett polynom kan du ange ett explicit uttryck genom Möbius-funktionen : $\Phi _{n}(x)$

\Phi _{n}(x)=\prod _{{d|n}}(x^{d}-1)^{{\mu (n/d)))

Ett specialfall av föregående formel: om är ett primtal , då $n=p$

\Phi _{n}(x)={\frac {x^{p}-1}{x-1}}=x^{p-1}+x^{p-2}+\cdots +1

Om , var är ett udda tal större än ett då: $n=2m$ $m$

\Phi _{2m}(x)=\Phi _{m}(-x)

Om är det maximala naturliga talet som delar , och fritt från kvadrater (radikal ), och , då $m$ $n$ $n$ $d=n/m$

\Phi _{n}(x)=\Phi _{m}(x^{d})

Om är ett primtal som inte delar , alltså $sid$ $n$

\Phi _{pn}(x)={\frac {\Phi _{n}(x^{p})}{\Phi _{n}(x)))

Över fältet av rationella tal är alla polynom irreducerbara , men över ändliga enkla fält kan dessa polynom reduceras. Så om är ett primtal, sönderdelas polynomet modulo i linjära faktorer, och polynomet sönderfaller till produkten av ( olika) polynom av grad 2 (icke reducerbara över ringen ), med fria termer lika med 1. $\Phi _{n}(x)$ $sid$ $sid$ $\Phi _{p-1}(x)$ $\Phi _{p+1}(x)$ $\mathbb {Z} _{p}$
- Till exempel:

\Phi _{8}(x)=x^{4}+1=(x^{2}+4x+1)(x^{2}-4x+1){\pmod {7}}

\Phi _{12}(x)=x^{4}-x^{2}+1=(x^{2}+5x+1)(x^{2}-5x+1){ \pmod {11}}

\Phi _{14}(x)=(x^{2}-6x+1)(x^{2}-5x+1)(x^{2}-3x+1){\pmod { 13}}

Mer generellt är följande faktum: Om p är ett primtal, n är ett naturligt tal, så expanderar polynomet modulo p till en produkt av polynom av grad n. Om n också är enkelt, är polynomen av grad n involverade i nedbrytningen irreducerbara över ringen . $\Phi _{\Phi _{n}(p)}(x)$ $\mathbb {Z} _{p}$

Exempel

Här är en sammanfattning av de första 30 cirkulära polynomen [1] .

\Phi _{1}(x)=x-1

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

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

\Phi _{4}(x)=x^{2}+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

\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

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

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

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

\Phi _{17}(x)=x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x ^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{ 2}+x+1

\Phi _{18}(x)=x^{6}-x^{3}+1

\Phi _{19}(x)=x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x ^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6}+x^{5}+x^{ 4}+x^{3}+x^{2}+x+1

\Phi _{20}(x)=x^{8}-x^{6}+x^{4}-x^{2}+1

\Phi _{21}(x)=x^{12}-x^{11}+x^{9}-x^{8}+x^{6}-x^{4}+x ^{3}-x+1

\Phi _{22}(x)=x^{10}-x^{9}+x^{8}-x^{7}+x^{6}-x^{5}+x ^{4}-x^{3}+x^{2}-x+1

\Phi _{23}(x)=x^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x ^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{ 8}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{24}(x)=x^{8}-x^{4}+1

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

\Phi _{26}(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

\Phi _{27}(x)=x^{18}+x^{9}+1

\Phi _{28}(x)=x^{12}-x^{10}+x^{8}-x^{6}+x^{4}-x^{2}+1

\Phi _{29}(x)=x^{28}+x^{27}+x^{26}+x^{25}+x^{24}+x^{23}+x ^{22}+x^{21}+x^{20}+x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{ 14}+x^{13}+x^{12}+x^{11}+x^{10}+x^{9}+x^{8}+x^{7}+x^{6} +x^{5}+x^{4}+x^{3}+x^{2}+x+1

\Phi _{30}(x)=x^{8}+x^{7}-x^{5}-x^{4}-x^{3}+x+1

Från denna sammanfattning kan vi dra slutsatsen att koefficienter som inte är noll för ett cirkulärt polynom alltid är lika, men detta antagande är felaktigt. Det första motexemplet ger det 105:e polynomet: $\pm1,$

{\begin{aligned}\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{aligned}}

Applikationer

En av de viktigaste tillämpningarna av cirkulära polynom är satsen om den multiplikativa gruppen av ett ändligt fält:

Sats. Den multiplikativa gruppen av ett ändligt fält är en cyklisk grupp. $K^{*}$ $K$

Bevis. Låt fältet bestå av ett element, då innehåller dess multiplikativa grupp (gruppen av inverterbara element) alla element i fältet, förutom noll, det vill säga den består av element. Enligt Lagrangesatsen delar ordningen av ett element i en grupp ordningen för denna grupp, därför, för alla element , , det vill säga alla element från är rötterna till ekvationen . Sedan $K$ $n+1$ $K^{*}$ $n$ $a\in K^{*}$ $a^{n}=1$ $K^{*}$ $x^{n}-1=0$

\prod \limits _{a\in K^{*}}(xa)=x^{n}-1

eftersom alla rötter på vänster sida är rötter på höger sida och grad, och de ledande termerna för båda polynomen är lika.

Därför att

x^{n}-1=\prod \limits _{d|n}\Phi _{d}(x)

och ,

\deg \Phi _{d}(x)=\varphi (d)\geqslant 1

då har polynomet exakt rötter i (och därmed minst en). Dess rötter är element i ordningsgruppen , det vill säga den cykliska gruppen som bildas av någon av dem innehåller olika element och måste sammanfalla med hela gruppen , vilket innebär cykliciteten för denna grupp. $\Phi _{n}(x)$ $\varphi (n)$ $K$ $K^{*}$ $n$ $n$ $K^{*}$

Se även

cirkulärt fält

Litteratur

Irland K., Rosen M. En klassisk introduktion till modern talteori . M.: Mir, 1987.
Van der Waerden B. L. Algebra. M.: Mir, 1975.

Anteckningar

↑ OEIS A013595 .