1
$\begingroup$

Let $\alpha,\beta$ be primitive $n$-th roots of unity in an extension of $\mathbb{F}_p$ ($p$ prime).

Let $S$ be the set of irreducible factors (over $\mathbb{F}_p$) of $x^n-1$.

Is there a function $F:S\rightarrow S$ satisfying the following condition?

For every integer $i$, if $p(x)\in S$ is the minimal polynomial of $\alpha^i$ over $\mathbb{F}_p$, then $F(p(x))$ is the minimal polynomial of $\beta^i$ over $\mathbb{F}_p$.

If such function $F$ exists, how is it defined?

If $\alpha$ and $\beta$ have the same minimal polynomial, then taking $F$ to be the identity on $S$ works. I feel we should be able to find a function $F$ satisfying the above condition even when $\alpha$ and $\beta$ have different minimal polynomials.

$\endgroup$
6
  • $\begingroup$ If $\alpha$ and $\beta$ are primitive $n$th roots of unity, then don't they have the same minimal polynomial? $\endgroup$ Commented Aug 22, 2013 at 12:40
  • 2
    $\begingroup$ @GerryMyerson: I think they don't. The $n$-th cyclotomic polynomail $Q_n(x)$ is the product of $\Phi(n)/d$ irreducible polynomials, each of degree $d$, where $d$ is the multiplicative order of $p$ modulo $n$. These factors are different, I'll write up an example. $\endgroup$
    – Gils
    Commented Aug 22, 2013 at 12:44
  • $\begingroup$ @GerryMyerson: Found this example on the net: Take $p=11$ and $n=12$. Then $Q_n(x)=(x^2+5x+1)(x^2-5x+1)$. Every root of each of these irreducible factors is a $12$-th root of unity. $\endgroup$
    – Gils
    Commented Aug 22, 2013 at 12:46
  • $\begingroup$ Yes, sorry. Or $p=7$, $n=3$, $(x-2)(x-4)$. $\endgroup$ Commented Aug 22, 2013 at 12:47
  • $\begingroup$ If $\alpha$ is a chosen primitive $n$th root of unity (in some extension field of $\mathbb{F}_p$, then $\alpha^i$ and $\alpha^j$ share the same minimal polynomial, iff $i$ and $j$ belong to the same cyclotomic coset modulo $n$, i.e. $ip^k\equiv j\pmod n$ for some non-negative integer $k$. $\endgroup$ Commented Aug 22, 2013 at 17:19

2 Answers 2

2
$\begingroup$

The following solves the problem of finding the minimal polynomial of $\alpha^i$ given the minimal polynomial of $\alpha$. If you know the exponent $e$ in $\beta=\alpha^e$, then you can apply this to your question. This has much higher complexity than taking the reciprocal as I indicated in a comment under the OP.

Assume that we know the minimal polynomial $m(x)$ os a primitive $n$th root $\alpha$, and that we want to calculate the minimal polynomial of another primitive root $\beta=\alpha^i$, $\gcd(i,n)=1$. First we find the modular inverse $j$ of $i$, so this is an integer with the property $ji\equiv1\pmod n.$ We then know that $\beta^j=\alpha$. Thus we know that $\beta$ is a zero of the polynomial $m(x^j)$. As $\beta$ is also a zero of $x^n-1$ we know that $\beta$ is a zero of $$ m_j(x):=\gcd(x^n-1,m(x^j)). $$ I claim that $m_j(x)$ is the minimal polynomial of $\beta$. Let $\gamma$ be any zero of $m_j(x)$. As $m_j(x)\mid x^n-1$, we know that $\gamma$ has to be an $n$th root of unity, so $\gamma=\alpha^t$ for some integer $t$. As $\gamma^j$ is a zero of $m(x)$, we know that $\gamma^j$ is a conjugate of $\alpha$, i.e. $\gamma^j=\alpha^{p^k}$ for some non-negative integer $k$. But this means that $$ \gamma=\gamma^{ij}=\alpha^{ip^k}=\beta^{p^k} $$ is a conjugate of $\beta$. Thus all the zeros of $m_j(x)$ are conjugates of $\beta$ proving the claim.

As an example let's take the irreducible factor $m(x)=x^2+5x+1$ of $x^{12}-1$ in the ring $\mathbb{Z}_{11}[x]$ given by Gils in a comment. We could check that the roots of $m(x)$ are, indeed, primitive twelfth roots of unity, but I'll skip that. We observe right away that $m(x)$ is palindromic, i.e. equal to its own reciprocal polynomial. This was to expected. For if $\alpha$ is a zero of $m(x)$, then the other zero is the Frobenius conjugate $\alpha^{11}=\alpha^{11-12}=\alpha^{-1}$. But we can use $j=5$ here as $\gcd(5,12)=1$. The above piece of theory tells us to calculate (Mathematica did this for me) $$ m_5(x):=\gcd(m(x^5),x^{12}-1)=\gcd(x^{10}+5x^5+1,x^{12}-1)=x^2+6x+1=x^2-5x+1. $$ This is the other factor given by Gils. Its roots are $\alpha^5$ and $\alpha^{-5}=\alpha^7$. As an auxiliary check we observe that this time we knew that $\alpha^6=-1$ as that is the sole primitive second root of unity. Therefore $\alpha^7=\alpha\alpha^6=-\alpha$. Indeed, we immediately see that $m_5(x)=m(-x)$. This gives us another proof for the fact that $\alpha^7=-\alpha$ is a zero of $m_5(x)$

This method may not always be very low complexity, because the polynomial $m(x^j)$ may have a rather high degree, and calculating the gcd thus takes a while (with the pen & paper method). Some help can be gotten by replacing $x^n-1$ with the characteristic zero $n$th cyclotomic polynomial $\phi_n(x)$ of degree $\phi(n)<n$.

$\endgroup$
6
  • $\begingroup$ May be not quite what you asked. Hopefully still helps. $\endgroup$ Commented Aug 22, 2013 at 18:13
  • $\begingroup$ So, if I understand correctly, for the mere question of existence of such function $F$, the answer is: Yes. Such function exists because for primitive $n$-th roots of unity $\alpha,\beta$ and integers $i,j$, we know that if $\alpha^i$ and $\alpha^j$ have the same minimal polynomial, then $i\equiv jp^k\pmod{n}$ for some integer $k$, and therefore $\beta^i$ and $\beta^j$ have the same minimal polynomial. Is that right? $\endgroup$
    – Gils
    Commented Aug 22, 2013 at 20:01
  • $\begingroup$ And that also shows that the function $F$ sends a polynomial of degree $d$ to a polynomial of degree $d$, because the function $\alpha^i\mapsto\beta^i$ is a bijection of the $n$-th roots of unity, matching between sets of Galois conjugates in both directions. Is that right? $\endgroup$
    – Gils
    Commented Aug 22, 2013 at 20:06
  • $\begingroup$ Correct, Gils. I'm a bit worried about not actually answering your question as stated. This is a method for finding the minimal polynomial of $\alpha^i$ given the minimal polynomial of $\alpha$. So to apply this to the question you asked, we need to first write $\beta$ as a power of $\alpha$. If $n$ is large, that is a very tall order (known as the discrete logarithm problem). $\endgroup$ Commented Aug 22, 2013 at 20:08
  • $\begingroup$ Thank you very much. The two observations in my comments are the most important to me, so your answer does satisfy me. As for efficient computation of $F$ - this is interesting, but less important to me. Will think about it too. $\endgroup$
    – Gils
    Commented Aug 22, 2013 at 20:13
0
$\begingroup$

If you choose a prime $\pi$ lying over $p$ in $\mathbb Z[\zeta_n]$, where $\zeta_n$ is a primitive $n$th root of $1$ in $\overline{\mathbb Q}$, it is possible to choose liftings to char=$0$ of those minimal polynomials so that the Galois group upstairs permutes them as desired, since the Galois group is transitive upstairs, and the lifts to char=$0$ can be chosen to correspond to intermediate fields upstairs, even if mod $p$ they give trivial maps on the fields themselves. I think. :)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .