Show COMBINATORIALLY the number of irreducible monic polynomials is the number of primitive necklaces
up vote
3
down vote
favorite
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
asked Nov 27 at 0:32
RickyLiuWho
162
add a comment |
up vote
3
down vote
favorite
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
asked Nov 27 at 0:32
RickyLiuWho
162
1
What is a primitive necklace?
– KReiser
Nov 27 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 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 at 1:16
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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
asked Nov 27 at 0:32
RickyLiuWho
162
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
combinatorics algebraic-combinatorics necklace-and-bracelets
asked Nov 27 at 0:32
RickyLiuWho
162
asked Nov 27 at 0:32
RickyLiuWho
162
edited Nov 27 at 0:47
asked Nov 27 at 0:32
RickyLiuWho
162
asked Nov 27 at 0:32
RickyLiuWho
162
asked Nov 27 at 0:32
RickyLiuWho
162
162
1
What is a primitive necklace?
– KReiser
Nov 27 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 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 at 1:16
add a comment |
1
What is a primitive necklace?
– KReiser
Nov 27 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 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 at 1:16
1
1
What is a primitive necklace?
– KReiser
Nov 27 at 1:01
What is a primitive necklace?
– KReiser
Nov 27 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 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 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 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 at 1:16
add a comment |
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',
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
1
What is a primitive necklace?
– KReiser
Nov 27 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 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 at 1:16