9
$\begingroup$

Since Cyclotomic polynomials are irreducible over $\mathbb{Q}$, $\phi_n(x)$, $\phi_m(x)$ are coprime as polynomials in $\mathbb{Z}[x]$.

  1. Working over $\mathbb{Q}$, $(\phi_n(x)$, $\phi_m(x))=(1)$. This implies that $(\phi_n(x), \phi_m(x))=(c)$ for some $c \in \mathbb{N}$ when this ideal is considered in $\mathbb{Z}[X]$. Can this $c$ be evaluated as a function of $n,m$?
  2. What can be said about $f(x) = gcd(\phi_n(x),\phi_m(x))$, when the polynomials are considered as scalars, i.e. evaluated at some $x$? $\forall x: f(x) | c$ from question 1, but can something stronger be said? More concretely, what is the image of $f$?

EDIT:

This paper by Apostol, provided in the comments to Greg's answer, gives a pretty good answer, which Greg guessed.

It basically calculates the resultant of 2 cyclotomic polynomials, which gives a number that is divisible by the optimal constant $c=(\phi_n(x), \phi_m(x))$, and it is either 1 (when $\frac{n}{m}$ is not a prime power) or a power of a prime ($p^{\phi(m)}$ when $\frac{n}{m}$ is a power of $p$).

When it is $1$ (the common case), we have a full answer for both questions. When it is a prime power, we only have an upper bound for the multiplicity ($\phi(m)$, when $m|n$).

This elementary paper gives some weaker result but it is simpler.

$\endgroup$
  • $\begingroup$ Thanks anon, I removed the tag (originally I had a 3rd question about factoring Cyclotomic polynomials over finite fields but I found it on the site and removed it from the post). $\endgroup$ – Ofir Dec 13 '12 at 8:10
6
$\begingroup$

The resultant $R$ of two polynomials $f,g$ has the property that there exist other polynomials $p,q$ such that $p(x)f(x)+q(x)g(x) = R$ identically. (Originally I had stated that $|R|$ is the least such positive integer, but this seems to be incorrect; see the comments.)

Therefore your question 1 is related to calculating the resultant of distinct cyclotomic polynomials $\phi_n, \phi_m$. Experimentally, the answer seems to be $1$ unless $m$ divides $n$ (or vice versa), in which case it seems to be a power of $n/m$. Just eyeballing some data, it seems the answer is $\exp(\phi(m)\Lambda(n/m))$, where $\Lambda$ is the von Mangoldt function.

$\endgroup$
  • $\begingroup$ I've seen proofs of the exitence of $f,g$ to make $R$ but never a proof its the least. Can you give some sort of reference to a proof? $\endgroup$ – dinoboy Dec 13 '12 at 1:30
  • 4
    $\begingroup$ Greg, the resultant is not, in general, the least integer. See my paper, On resultants, Proc. Amer. Math. Soc. 89 (1983), 419-420, ams.org/journals/proc/1983-089-03/S0002-9939-1983-0715856-2/… $\endgroup$ – Gerry Myerson Dec 13 '12 at 1:33
  • 4
    $\begingroup$ See also Tom Apostol, Resultants of cyclotomic polynomials, Proc. Amer. Math. Soc. 24 (1970), 457-462, ams.org/journals/proc/1970-024-03/S0002-9939-1970-0251010-X/… $\endgroup$ – Gerry Myerson Dec 13 '12 at 1:36
  • $\begingroup$ @GerryMyerson - Thank you for those papers, they fully answer my first question and they are readable too... $\endgroup$ – Ofir Dec 13 '12 at 10:20
  • $\begingroup$ @GregMartin - Your empirical answer coincides with Apostol's paper. $\endgroup$ – Ofir Dec 13 '12 at 10:23
4
$\begingroup$

Note that $(x^m-1,x^n-1)=x^{n,m} - 1$ in $\mathbb{Z}[x]$.
i.e. $\exists p(x),q(x)\in \mathbb{Z}[x]$ such that $$(x^m-1)p(x)+(x^n-1)q(x)=x^{(n,m)}-1$$.

Now since $x^{(n,m)}-1 | x^n -1$ and $x^{(n,m)}-1|x^m-1$ in $\mathbb{Z}[x]$
we can say that $$\frac{x^m-1}{x^{(n,m)}-1}p(x)+\frac{x^n-1}{x^{(n,m)}-1}q(x)=1$$.
Now whenever $a|b$ and $a<b$ we have $\phi_b(x)|\frac{x^b-1}{x^a-1}$ in $\mathbb{Z}[x]$.

As a result whenever $min(n,m)>(n,m)$

we have $\phi_m(x)|\frac{x^m-1}{x^{(n,m)}-1}$ and $\phi_n(x)|\frac{x^n-1}{x^{(n,m)}-1}$ in $\mathbb{Z}[x]$ we can say $$\phi_m(x)\cdot\frac{x^m-1}{\phi_m(x)\cdot(x^{(n,m)}-1)}p(x)+\phi_n(x)\cdot\frac{x^n-1}{\phi_n(x)(x^{(n,m)}-1)}q(x)=1$$ Thus, we have $1$ is the least number expressible by $(\phi_n(x), \phi_m(x))$ whenever $min(n,m)>(n,m)$. Or a better way to put it would be $$1\in (\phi_n(x), \phi_m(x))$$ when seen as an ideal in $\mathbb{Z}[x]$

The case where $n=mk$ we see that $$\frac{x^{mk}-1}{x^m-1}=(x^m)^{k-1} + (x^m)^{k-2}+ ... + (x^m) + 1 \equiv k \pmod{x^m-1}$$ $$\implies \frac{x^{mk}-1}{x^m-1} + (x^m-1)\cdot d(x) = k $$ for some $d(x)\in \mathbb{Z}[x]$
Since $\phi_m(x)|x^m-1$ and $\phi_{mk}(x)|\frac{x^{mk}-1}{x^m-1}$ we get that $$\phi_{mk}(x)\cdot\frac{x^{mk}-1}{\phi_{mk}(x)\cdot(x^m-1)} + \phi_m(x)\cdot\frac{x^m-1}{\phi_m(x)}\cdot d(x) = k$$ $$\implies k\in (\phi_m(x),\phi_{mk}(x))$$ when seen as an ideal in $\mathbb{Z}[x]$

However, it is not necessarily $k$ as illustrated by taking $m=1$ and $n=6$ and can be $k$ as illustrated by the example $m=1$ and $n=3$. In fact, using the properties using a bit of algebraic number theory/cyclotomic fields. Once can show, $$(\phi_m(x),\phi_{mk}(x))\cap \mathbb{Z} = \begin{cases} \mathbb{Z}& k\neq p^r\\ p\mathbb{Z}, &k=p^r\\ \end{cases}$$ To see this let $z_n=exp(\frac{2\pi i}{n})$ denote the nth primitive roots of unity.

Let $I_{m,k}=(\phi_m(x),\phi_{mk}(x))$ and $I_m=(\phi_m(x))$. Then we have a canonical map $$R:=\frac{\mathbb{Z}[x]}{I_m}\longrightarrow \frac{\mathbb{Z}[x]}{I_{m,k}}$$ which tells us we have to determine the ideal $(\phi_{mk}(z_m))$ in $R$.

Now $$\phi_{mk}(z_m)=\prod_{(a,mk)=1}^{mk}(z_m-(z_{mk})^a)$$ $$\implies (\phi_{mk}(z_m))=\prod_{(a,mk)=1}^{mk}((z_m-(z_{mk})^a)) $$ Since $z_m$ is a unit $$(\phi_{mk}(z_m))=\prod_{(a,mk)=1}^{mk}((1-(z_{mk})^az_m^{-1}))$$ Now note $1-u$ is a unit for all $t$-th roots of unity where $t$ not a power of a prime.(Calculate $\phi_n(1)$ to see this.) Thus the RHS will be a unit if k is not a power of a prime. Furthermore, if $k=p^r$, Sieving out non-units you get $$(\phi_{mk}(z_m))=\prod_{(a,k)=1 }^{k}((1-(z_{k})^a))$$ $$(\phi_{mk}(z_m))= (\phi_k(1))=(p)$$ And thus $\frac{R}{(p)}=\frac{R}{I_mk}= \frac{\mathbb{Z}[x]}{I_{m,k}}$ Which gives us the result since $pR\cap \mathbb{Z}=p\mathbb{Z}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.