1
$\begingroup$

Let $P\in\mathbb{F}_p[T]$ (not supposed irreducible). All roots $\xi$ of $P$ have a certain order $k$ such that $\xi^k=1$.

Question: is it possible to know the order of the roots of the given polynomial $P$, or at least a upper bound of the order?

It is clear that if $k$ is an order of (a root of) $P$ then by the description of factors of cycltomic polynomials $\Phi_k$ then

$$ \text{ord}_k(p)\leq \deg(P) $$

where $\text{ord}_k(p)$ is the order of $p$ in $(\mathbb{Z}/k\mathbb{Z})^*$ and that basically $$ \log_p(k)\leq \text{ord}_k(p) $$ because for $a$ to be the order of $p$ we must have $p^a\geq k$. So we have $$ \log_p(k)\leq\deg(P) $$ and hence $$ k\leq p^{\deg(P)} $$

This is a very big upper bound and for algorithms I would like to have a smaller bound or better a list of possible orders.

Thanks for your help!

$\endgroup$

1 Answer 1

3
$\begingroup$

Let $d = \deg P$. The list of possible orders is simply the list of divisors of $p^d-1$.

Proof that every such order appears: Let $n$ divide $p^d-1$. Let $\alpha$ be an element of $\mathbb F_{p^d}$ of order $n$, which exists since the multiplicative group of $\mathbb F_{p^d}$ is cyclic. Then $\alpha$ generates a subfield $\mathbb F_{p^e} \subseteq \mathbb F_{p^d}$ for some divisor $e$ of $d$. The minimal polynomial of $\alpha$ has degree $e$, so the $d/e$th power of it does the trick.

Proof that these are the only such orders that appear. Let $P$ be such a polynomial, and let $e$ be the least natural number such that $k$ divides $p^e-1$. Then every element of $\overline{\mathbb F_p}$ of order $k$ lies in $\mathbb F_{p^e}$, and none of them lie in any smaller finite field, so they all have minimal polynomials of degree $e$. Since $P$ has roots only these elements, $P$ is a product of these minimal polynomials, so $\deg P$ is a multiple of $e$. Thus $p^{ d}-1$ is a multiple of $p^e-1$ and hence is a multiple of $k$.

So your upper bound is sharp, but despite this, there is a list of size $p^{ o(d)}$ (by bounds for the divisor function).

$\endgroup$
7
  • $\begingroup$ If I take $\Phi_4=X^2+1$ (for example over $\mathbb{F}_3$) then $p^d-1=3^2-1=8$. But all the roots of $\Phi_4$ have order 4, and we have also $8$, $2$ and $1$ for divisors of $8$? What's the matter? $\endgroup$ Commented Apr 22, 2022 at 19:29
  • $\begingroup$ @GabrielSoranzo That's a list of possible orders. Not all possibilities necessarily occur for all polynomials of a given degree. $\endgroup$
    – Will Sawin
    Commented Apr 22, 2022 at 19:31
  • $\begingroup$ With $P=X^5-1$ in $\mathbb{F}_3$ the orders are the divisors of $5$ but $p^d-1=2\times 11^2$ so $5$ doesnt divide $p^d-1$?? I missed something? $\endgroup$ Commented Apr 22, 2022 at 19:35
  • $\begingroup$ $P=X^5-1$ is not irreducible. $\endgroup$ Commented Apr 22, 2022 at 19:54
  • 1
    $\begingroup$ @GabrielSoranzo Ah, I see what has happened. When you said "all roots have a certain order $k$" I assumed you meant the same order $k$ for all roots. My answer was under that assumption. For the question of simply what numbers can be the order of the roots of a polynomial of degree $d$, you indeed want to consider the divisors of $p^k-1$ for $k \leq \deg P$. $\endgroup$
    – Will Sawin
    Commented Apr 22, 2022 at 21:14

You must log in to answer this question.

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