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.
Answer
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)
No comments:
Post a Comment