Show COMBINATORIALLY the number of irreducible monic polynomials is the number of primitive necklaces












3














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) = sumlimits_{d|n} q^d muBig(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.










share|cite|improve this question




















  • 1




    What is a primitive necklace?
    – KReiser
    Nov 27 '18 at 1:01










  • @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.)
    – Théophile
    Nov 27 '18 at 1:15












  • 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.
    – RickyLiuWho
    Nov 27 '18 at 1:16
















3














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) = sumlimits_{d|n} q^d muBig(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.










share|cite|improve this question




















  • 1




    What is a primitive necklace?
    – KReiser
    Nov 27 '18 at 1:01










  • @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.)
    – Théophile
    Nov 27 '18 at 1:15












  • 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.
    – RickyLiuWho
    Nov 27 '18 at 1:16














3












3








3







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) = sumlimits_{d|n} q^d muBig(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.










share|cite|improve this question















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) = sumlimits_{d|n} q^d muBig(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.







combinatorics algebraic-combinatorics necklace-and-bracelets






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Nov 27 '18 at 0:47

























asked Nov 27 '18 at 0:32









RickyLiuWho

162




162








  • 1




    What is a primitive necklace?
    – KReiser
    Nov 27 '18 at 1:01










  • @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.)
    – Théophile
    Nov 27 '18 at 1:15












  • 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.
    – RickyLiuWho
    Nov 27 '18 at 1:16














  • 1




    What is a primitive necklace?
    – KReiser
    Nov 27 '18 at 1:01










  • @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.)
    – Théophile
    Nov 27 '18 at 1:15












  • 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.
    – RickyLiuWho
    Nov 27 '18 at 1:16








1




1




What is a primitive necklace?
– KReiser
Nov 27 '18 at 1:01




What is a primitive necklace?
– KReiser
Nov 27 '18 at 1:01












@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.)
– Théophile
Nov 27 '18 at 1:15






@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.)
– Théophile
Nov 27 '18 at 1:15














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.
– RickyLiuWho
Nov 27 '18 at 1:16




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.
– RickyLiuWho
Nov 27 '18 at 1:16















active

oldest

votes











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3015154%2fshow-combinatorially-the-number-of-irreducible-monic-polynomials-is-the-number-o%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown






























active

oldest

votes













active

oldest

votes









active

oldest

votes






active

oldest

votes
















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3015154%2fshow-combinatorially-the-number-of-irreducible-monic-polynomials-is-the-number-o%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Ellipse (mathématiques)

Quarter-circle Tiles

Mont Emei