Polinomio ciclotomico

In matematica, l'$n$-esimo polinomio ciclotomico, per ogni intero positivo $n$, è l'unico polinomio irriducibile a coefficienti interi che divide $z^{n}-1$ ma non divide $z^{k}-1$ per tutti i $k<n$. Le sue radici sono tutte le radici n-esime primitive dell'unità $e^{2i\pi {\frac {k}{n}}}$ con $k$ intero positivo minore di $n$ e coprimo ad esso. Si può quindi scrivere come:

$\Phi _{n}(z)=\prod _{\stackrel {1\leq k\leq n}{\gcd(k,n)=1}}\left(z-e^{2i\pi {\frac {k}{n}}}\right).$

Alternativamente, può essere definito come il polinomio monico a coefficienti interi che è il polinomio minimo sul campo dei razionali di qualunque radice n-esime primitiva dell'unità.

Proprietà

I polinomi ciclotomici sono polinomi monici a coefficienti interi che sono irriducibili sul campo dei razionali. Eccetto per $n$ uguale a 1 o 2, sono palindromi di grado pari.

Il grado di $\Phi _{n}$, ossia il numero di radici $n$-esime primitive dell'unità, è $\varphi (n)$, dove $\varphi$ indica la funzione di Eulero.

Una relazione importante che lega i polinomi ciclotomici e le radici primitive dell'unità è

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

mostrando che $z$ è radice del polinomio se e solo se è una radice $d$-esima primitiva dell'unità per qualche $d$ che divide $n$.

Applicando la formula di inversione di Möbius si ottiene

$\Phi _{n}(z)=\prod _{d\mid n}(z^{n/d}-1)^{\mu (d)}=\prod _{d\mid n}(z^{d}-1)^{\mu (n/d)},$

dove $\mu$ è la funzione di Möbius.

Da questo risultato si ricava una relazione di ricorrenza per il polinomio ciclotomico $\Phi _{n}(z)$, che può essere calcolato dividendo $z^{n}-1$ per i polinomi ciclotomici $\Phi _{d}(z)$ con $d$ divisore proprio di $n$, a partire da $\Phi _{1}(z)=z-1$:

$\Phi _{n}(z)={\frac {z^{n}-1}{\prod _{\stackrel {d\mid n}{d<n}}\Phi _{d}(z)}}.$

La formula offre un algoritmo per calcolare qualunque $\Phi _{n}(z)$, supponendo che siano disponibili la fattorizzazione intera e la divisione polinomiale. Molti sistemi di algebra computazionale, come Sage, Maple e Mathematica presentano funzioni interne per calcolare questi polinomi.

Computazioni veloci

Usando la formula precedente, se $n=p$ numero primo, allora

$\Phi _{p}(z)={\frac {z^{n}-1}{z-1}}=1+z+z^{2}+\cdots +z^{p-1}=\sum _{k=0}^{p-1}z^{k}.$

Sostituendo a $z$ un qualunque numero naturale $n$, $\Phi _{p}(n)$ è una repunit in base $n$: segue che se un repunit è un numero primo allora la sua lunghezza in cifre è un numero primo. In generale, i valori assunti dai polinomi ciclotomici sugli interi sono soggetti a numerose altre limitazioni; ad esempio, se $p$ è primo e $d\mid \Phi _{p}$, allora $d\equiv 1{\pmod {p}}$ oppure $d\equiv 0{\pmod {p}}$.

Altri casi particolari sono:

• $\Phi _{2n}(z)=\Phi _{n}(-z)$, per $n>1$ dispari;
• $\Phi _{p^{r}}(z)=\Phi _{p}(z^{p^{r-1}})$, per $p$ primo;
• $\Phi _{n}(z)=\Phi _{p_{1}\dots p_{s}}(z^{{p_{1}}^{r_{1}-1}\dots {p_{s}}^{r_{s}-1}})$, per $n=p_{1}^{r_{1}-1}\dots p_{s}^{r_{s}-1}$ con fattori $p_{i}$ distinti;
• $\Phi _{pn}(z)={\dfrac {\Phi _{n}(z^{p})}{\Phi _{n}(z)}}$, per un qualsiasi primo $p$ tale che $p\nmid n$.

Interi che appaiono come coefficienti

Il problema di trovare la grandezza dei coefficienti dei polinomi ciclotomici è stato oggetto di molte pubblicazioni.

Se $n$ ha al massimo due fattori primi dispari distanti, allora Migottie e A. S. Bang hanno dimostrato che i coefficienti di $\Phi _{n}$ appartengono all'insieme $\{-1,0,1\}$. Il primo polinomio il cui n è prodotto di tre diversi primi dispari è $\Phi _{105}$che ha coefficiente -2. L'inverso non è vero: $\Phi _{231}=\Phi _{3\cdot 7\cdot 11}$ha coefficienti solo in $\{-1,0,1\}$,

Sia $A(n)$ il massimo valore assoluto dei coefficienti di $\Phi _{n}(z)$. È noto che per ogni intero positivo $k$, il numero di $n$ minori di $x$ tali che $A(n)>n^{k}$è almeno $c(k)\cdot x$ con $c(k)$ positivo ed $x$ sufficientemente grande. Nella direzione opposta, per ogni funzione $\Psi (n)$ tendente a infinito, si ha $A(n)$ limitata superiormente da $n^{\Psi (n)}$per quasi tutti gli $n$.

Un insieme di teoremi di Bateman e Vaughan affermano che:

• per ogni $\varepsilon >0$ e per ogni $n$ sufficientemente grande, $A(n)<\exp {\left(n^{\frac {\log(2+\varepsilon )}{\log \log n}}\right)}$;
• per infiniti $n$ positivi, $A(n)<\exp \left({n^{\frac {\log 2}{\log \log n}}}\right)$.

Questo implica che i polinomi a una variabile (concretamente $z^{n}-1$ per infiniti $n$ interi positivi) possono avere fattori (come $\Phi _{n}$) i cui coefficienti sono superpolinomialmente maggiori dei coefficienti originali, risultato non troppo distante dal più generale limite di Landau-Mignotte.

Elenco di polinomi ciclotomici

I primi polinomi ciclotomici sono:

${\begin{aligned}\Phi _{1}(z)&=z-1\\\Phi _{2}(z)&=z+1\\\Phi _{3}(z)&=z^{2}+z+1\\\Phi _{4}(z)&=z^{2}+1\\\Phi _{5}(z)&=z^{4}+z^{3}+z^{2}+z+1\\\Phi _{6}(z)&=z^{2}-z+1\\\Phi _{7}(z)&=z^{6}+z^{5}+z^{4}+z^{3}+z^{2}+z+1\\\Phi _{8}(z)&=z^{4}+1\\\Phi _{9}(z)&=z^{6}+z^{3}+1\end{aligned}}$

Sempre sui coefficienti dei polinomi ciclotomici, si dimostra per induzione che il termine noto di $\phi _{n}$, per ogni $n\neq 1$, è esattamente $1$.

Voci correlate

• Radice dell'unità
• Estensione ciclotomica

Collegamenti esterni

• polinomio ciclotomico, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Cyclotomic Polynomial, su MathWorld, Wolfram Research.