Show that the number of monic irreducible polynomials of degree $n$ over a finite field of size $q$ is the same as the number of primitive necklaces of size $n$ with $q$ colors. I have the formula

$$M(q,n) = \sum\limits_{d|n} q^d \mu\Big(\frac{n}{d}\Big)$$

which counts primitive necklaces. The goal is to show this counts monic irreducibles over a finite field combinatorially. I can use Mobius inversion. I know this question has been asked before, but the previous answers require a lot of algebra.

I tried a special case when $q = 3$ and $n = 2$. Let the colors of the beads of a necklace be red (R), yellow (Y) and blue (B). Then the primitive necklaces are $RY$, $RB$ and $YB$. I computed the irreducible polynomials of degree $2$ as well, they are: $x^2 + 1, x^2 + x + 2$ and $x^2 + 2x + 2$. It is really unclear how I could map necklaces to these polynomials. If I just consider these as $3$-tuples then we have $(1, 0, 1), (1, 1, 2)$ and $(1, 2, 2)$ so it isn't even clear how to map the colors.

  • 1
    $\begingroup$ What is a primitive necklace? $\endgroup$ – KReiser Nov 27 '18 at 1:01
  • $\begingroup$ @KReiser A necklace is primitive if it cannot be obtained by repeating a smaller necklace. (So $RRRY$ is primitive, but $RRRR$ and $RYRY$ are not, for example.) $\endgroup$ – Théophile Nov 27 '18 at 1:15
  • $\begingroup$ A necklace is a cyclic sequence of colored beads. A necklace is called primitive if it is aperiodic, i.e. no non-trivial cyclic permutation yields the same necklace. $\endgroup$ – RickyLiuWho Nov 27 '18 at 1:16
  • $\begingroup$ mathoverflow.net/questions/769/… $\endgroup$ – Mike Earnest Feb 11 at 21:19

Your Answer

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

Browse other questions tagged or ask your own question.