For $n \in \mathbb{N}$, we know that $(\mathbb{Z}/n\mathbb{Z})^{*}$ is a cyclic group if and only if $ n=2$, 4, $p^{k}$, or $2p^{k}$ for an odd prime number $p$. Is there any known similar result for polynomials over $\mathbb{F}_{2}$?

In other words, can we determine all $P \in \mathbb{F}_{2}[x]$ for which $(\mathbb{F}_{2}[x]/(P))^{*}$ is a cyclic group?

  • 1
    $\begingroup$ The multiplicative group of a finite field is always cyclic. $\endgroup$ – Gerry Myerson May 23 '17 at 22:42
  • $\begingroup$ I didn't think much about this, but at least a partial answer (when $P$ is a power of an irreducible polynomial) is provided by proposition 1.6 in Michael Rosen's book Number Theory in Function Fields (2002 / GTM 210). $\endgroup$ – Gro-Tsen May 23 '17 at 22:48
  • 2
    $\begingroup$ @GerryMyerson The point is, $P$ is not assumed to be irreducible, so $\mathbb{F}_2[x]/(P)$ need not be a field. $\endgroup$ – Gro-Tsen May 23 '17 at 22:51
  • $\begingroup$ @Gro, I get that – I wasn't claiming a complete answer, just pointing out a starting place. $\endgroup$ – Gerry Myerson May 23 '17 at 22:53
  • $\begingroup$ Write $P(x) = Q_1(x)^{e_1}\cdots Q_r(x)^{e_r}$ with the $Q_i\in \mathbb F_2[x]$ irreducible and distinct. Then the Chinese Remainder Theorem gives $$ (\mathbb F_2[x]/(P))^* = (\mathbb F_2[x]/(Q_1^{e_1}))^* \times\cdots\times (\mathbb F_2[x]/(Q_r^{e_r}))^*. $$ As Gro-Tsen has pointed out, the individual factors are cyclic, and it's not hard to compute their orders in terms of the degree of the $Q_i$ and the $e_i$. Now you're reduced to the question of when a product of cyclic groups of known order is itself cyclic. $\endgroup$ – Joe Silverman May 23 '17 at 23:14

A polynomial satisfies this property if and only if it is a product of prime polynomials of distinct degrees, none raised to a power greater than one except for possibly one linear term raised to a power of degree at most $3$.

As Joe Silverman pointed out, if $Q_i$ are the prime factors of $P$ and $e_i$ are the exponents:

$$ (\mathbb F_2[x]/(P))^* = (\mathbb F_2[x]/(Q_1^{e_1}))^* \times\cdots\times (\mathbb F_2[x]/(Q_r^{e_r}))^*. $$

As Gerry Myerson points out, these individual factors are cyclic if $e_i=1$. As Gro-Tsen points out, these are not cyclic for greater $e_i$ unless $\deg Q_i = 1$ and $e_i \leq 3$. It is easy to check that they are cyclic, equal to $\mathbb Z/2$ or $\mathbb Z/4$, in the last case. Any group with a non-cyclic subgroup is not cyclic, so we may assume that $e_i=1$ if $\deg Q_i >1$ and $e_i \leq 3$ if $\deg Q_i=1$.

Now we use the well-known lemma:

A product of cyclic groups is cyclic if and only if the orders of the factors are relatively prime.

The "if" follows from the Chinese remainder theorem and the "only if" follows from finding $p^2-1$ elements of order $p$ for a prime dividing the orders of two of the factors.

The order of the factor $Q_i^{e_i}$ is $(2^{ \deg Q_i}-1) 2^{ \deg Q_i (e_i-1)}$. Hence they are relatively prime if and only if at most one of the $e_i$ is $>1$, and also the $2^{\deg Q_i}-1$ are relatively prime. The $2^{\deg Q_i}-1$ are relatively prime exactly when the degrees $\deg Q_i$ are relatively prime, as can be seen by observing that Euclid's algorithm for $2^a-1, 2^b-1$ functions the same as Euclid's algorithm for $a,b$. (This can also be seen by finite field theory - if two finite fields both contain primitive $\ell$th roots of unity for some $\ell$, they both contain the field generated by a primitive $\ell$th root of unity, and hence have a common subfield, and a common factor in their degrees. The converse is also easy.)

| cite | improve this answer | |
  • $\begingroup$ Thanks, Will. I deleted my answer due to your perspicacious comment and added a comment instead indicating the steps to answer the question. And while I was doing that, you typed in a complete answer. $\endgroup$ – Joe Silverman May 23 '17 at 23:16
  • $\begingroup$ Wait, (Gro-Tsen's comment about) Prop 1.6 of Rosen seems to be saying something else about the individual factors. Rosen finds a subgroup of $(\mathbb{F}_2[x]/(P^e))^*$ that has at least $\text{deg}(P)(e-1)/\text{ceil}(\log_p(e))$ minimal generators. Subgroups of cyclic groups are cyclic, so for the group to be cyclic, we need $e = 2,3$ and $\text{deg}(P) = 1$ if $e > 1$. $\endgroup$ – Kevin Casto May 23 '17 at 23:29
  • $\begingroup$ @KevinCasto You're right of course. I'll edit to fix. $\endgroup$ – Will Sawin May 23 '17 at 23:42
  • $\begingroup$ You might want to consult Proposition 3.1 of jtnb.cedram.org/jtnb-bin/fitem?id=JTNB_2009__21_3_517_0 $\endgroup$ – Chandan Singh Dalawat May 24 '17 at 3:50
  • $\begingroup$ @ChandanSinghDalawat Isn't that the mixed characteristic case and not equal characteristic? I agree it's related, but does it have direct relevance here? $\endgroup$ – Will Sawin May 24 '17 at 3:53

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.