Mixing
Easy way to prove property of prime indicator
$begingroup$
Let $mu$ be the Möbius function, and let $nu(n)$ be the number of distinct prime factors of $n$. Then we can define $p = mu * nu$, i.e.
$$
p(n) = sum_{d mid m} mu(d) nu(n/d).
$$
An exercise in an introductory textbook I already put back on the library shelf and can't find anymore asks:
Prove that $p$ only takes the values 0 and 1.
The obvious solution seems to be through Möbius inversion: if we define $q(n)$ to be 1 when $n$ is prime and $0$ otherwise, then $nu = 1 * q$ so that $q = mu * nu = p$. However, the formulation of the question suggests that there is an easy way to prove that $p$ only takes values $0, 1$ without identifying it entirely.
How might one do that?
elementary-number-theory mobius-inversion dirichlet-convolution
asked Feb 1 at 19:03
Mees de VriesMees de Vries
17.6k13060
$endgroup$
add a comment |
$begingroup$
Let $mu$ be the Möbius function, and let $nu(n)$ be the number of distinct prime factors of $n$. Then we can define $p = mu * nu$, i.e.
$$
p(n) = sum_{d mid m} mu(d) nu(n/d).
$$
An exercise in an introductory textbook I already put back on the library shelf and can't find anymore asks:
Prove that $p$ only takes the values 0 and 1.
The obvious solution seems to be through Möbius inversion: if we define $q(n)$ to be 1 when $n$ is prime and $0$ otherwise, then $nu = 1 * q$ so that $q = mu * nu = p$. However, the formulation of the question suggests that there is an easy way to prove that $p$ only takes values $0, 1$ without identifying it entirely.
How might one do that?
elementary-number-theory mobius-inversion dirichlet-convolution
asked Feb 1 at 19:03
Mees de VriesMees de Vries
17.6k13060
$endgroup$
add a comment |
$begingroup$
Let $mu$ be the Möbius function, and let $nu(n)$ be the number of distinct prime factors of $n$. Then we can define $p = mu * nu$, i.e.
$$
p(n) = sum_{d mid m} mu(d) nu(n/d).
$$
An exercise in an introductory textbook I already put back on the library shelf and can't find anymore asks:
Prove that $p$ only takes the values 0 and 1.
The obvious solution seems to be through Möbius inversion: if we define $q(n)$ to be 1 when $n$ is prime and $0$ otherwise, then $nu = 1 * q$ so that $q = mu * nu = p$. However, the formulation of the question suggests that there is an easy way to prove that $p$ only takes values $0, 1$ without identifying it entirely.
How might one do that?
elementary-number-theory mobius-inversion dirichlet-convolution
asked Feb 1 at 19:03
Mees de VriesMees de Vries
17.6k13060
$endgroup$
Let $mu$ be the Möbius function, and let $nu(n)$ be the number of distinct prime factors of $n$. Then we can define $p = mu * nu$, i.e.
$$
p(n) = sum_{d mid m} mu(d) nu(n/d).
$$
An exercise in an introductory textbook I already put back on the library shelf and can't find anymore asks:
Prove that $p$ only takes the values 0 and 1.
The obvious solution seems to be through Möbius inversion: if we define $q(n)$ to be 1 when $n$ is prime and $0$ otherwise, then $nu = 1 * q$ so that $q = mu * nu = p$. However, the formulation of the question suggests that there is an easy way to prove that $p$ only takes values $0, 1$ without identifying it entirely.
How might one do that?
elementary-number-theory mobius-inversion dirichlet-convolution
elementary-number-theory mobius-inversion dirichlet-convolution
asked Feb 1 at 19:03
Mees de VriesMees de Vries
17.6k13060
asked Feb 1 at 19:03
Mees de VriesMees de Vries
17.6k13060
asked Feb 1 at 19:03
Mees de VriesMees de Vries
17.6k13060
asked Feb 1 at 19:03
Mees de VriesMees de Vries
17.6k13060
asked Feb 1 at 19:03
Mees de VriesMees de Vries
17.6k13060
17.6k13060
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
There is the generalization of your first solution, showing $mu ast f$ for additive functions is always easy to find :
Let $f(n)$ be additive that is $f(nm) =f(n)+f(m)$ for $gcd(n,m)=1$.
Let $g(p^k) = f(p^k)-f(p^{k-1})$ and $g(n) = 0$ if $n$ isn't a prime power
Then $f(n) = sum_{p^k | n} f(p^k) = sum_{p^k | n} g(p^k) = sum_{d | n} g(d)$
Whence $sum_{d | n} mu(d) f(n/d)= g(n)$
answered Feb 1 at 21:02
reunsreuns
20.8k21353
$endgroup$
$begingroup$
This is a nice observation, but it doesn't really answer my question.
$endgroup$
– Mees de Vries
Feb 1 at 21:07
$begingroup$
@MeesdeVries Can you rephrase your question to make clear how it doesn't answer to it ? Your function is additive thus we can easily find the values taken by $muast f$
$endgroup$
– reuns
Feb 1 at 21:08
$begingroup$
But I already know what $p$ is -- it's in the question body. I'm specifically asking for an argument that does not show what $p$ is precisely, but only demonstrates the fact that $p$ only takes the values $0, 1$ because I'm curious what the intention was of the person who set the question.
$endgroup$
– Mees de Vries
Feb 1 at 21:10
$begingroup$
@MeesdeVries I think you asked what special property of $nu$ implies $sum_{d | n} mu(d) nu(n/d) in {0,1}$ and the answer is that $nu$ is additive with $nu(p^k) - nu(p^{k-1}) in {0,1}$.
$endgroup$
– reuns
Feb 1 at 21:16
$begingroup$
Yes, but from that statement it is also immediate that $p$ is the indicator function of the primes. The question in the textbook did not ask what $mu * nu$ was, only to prove that one property. That suggests to me that there should be some easy, by-inspection method to see that $p$ should only take the values $0, 1$, without identifying the function entirely. (I could be wrong of course, but that would just mean my question has no answer.)
$endgroup$
– Mees de Vries
Feb 1 at 21:19
add a comment |
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
});
}
});
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%2f3096612%2feasy-way-to-prove-property-of-prime-indicator%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There is the generalization of your first solution, showing $mu ast f$ for additive functions is always easy to find :
Let $f(n)$ be additive that is $f(nm) =f(n)+f(m)$ for $gcd(n,m)=1$.
Let $g(p^k) = f(p^k)-f(p^{k-1})$ and $g(n) = 0$ if $n$ isn't a prime power
Then $f(n) = sum_{p^k | n} f(p^k) = sum_{p^k | n} g(p^k) = sum_{d | n} g(d)$
Whence $sum_{d | n} mu(d) f(n/d)= g(n)$
answered Feb 1 at 21:02
reunsreuns
20.8k21353
$endgroup$
$begingroup$
This is a nice observation, but it doesn't really answer my question.
$endgroup$
– Mees de Vries
Feb 1 at 21:07
$begingroup$
@MeesdeVries Can you rephrase your question to make clear how it doesn't answer to it ? Your function is additive thus we can easily find the values taken by $muast f$
$endgroup$
– reuns
Feb 1 at 21:08
$begingroup$
But I already know what $p$ is -- it's in the question body. I'm specifically asking for an argument that does not show what $p$ is precisely, but only demonstrates the fact that $p$ only takes the values $0, 1$ because I'm curious what the intention was of the person who set the question.
$endgroup$
– Mees de Vries
Feb 1 at 21:10
$begingroup$
@MeesdeVries I think you asked what special property of $nu$ implies $sum_{d | n} mu(d) nu(n/d) in {0,1}$ and the answer is that $nu$ is additive with $nu(p^k) - nu(p^{k-1}) in {0,1}$.
$endgroup$
– reuns
Feb 1 at 21:16
$begingroup$
Yes, but from that statement it is also immediate that $p$ is the indicator function of the primes. The question in the textbook did not ask what $mu * nu$ was, only to prove that one property. That suggests to me that there should be some easy, by-inspection method to see that $p$ should only take the values $0, 1$, without identifying the function entirely. (I could be wrong of course, but that would just mean my question has no answer.)
$endgroup$
– Mees de Vries
Feb 1 at 21:19
add a comment |
$begingroup$
There is the generalization of your first solution, showing $mu ast f$ for additive functions is always easy to find :
Let $f(n)$ be additive that is $f(nm) =f(n)+f(m)$ for $gcd(n,m)=1$.
Let $g(p^k) = f(p^k)-f(p^{k-1})$ and $g(n) = 0$ if $n$ isn't a prime power
Then $f(n) = sum_{p^k | n} f(p^k) = sum_{p^k | n} g(p^k) = sum_{d | n} g(d)$
Whence $sum_{d | n} mu(d) f(n/d)= g(n)$
answered Feb 1 at 21:02
reunsreuns
20.8k21353
$endgroup$
$begingroup$
This is a nice observation, but it doesn't really answer my question.
$endgroup$
– Mees de Vries
Feb 1 at 21:07
$begingroup$
@MeesdeVries Can you rephrase your question to make clear how it doesn't answer to it ? Your function is additive thus we can easily find the values taken by $muast f$
$endgroup$
– reuns
Feb 1 at 21:08
$begingroup$
But I already know what $p$ is -- it's in the question body. I'm specifically asking for an argument that does not show what $p$ is precisely, but only demonstrates the fact that $p$ only takes the values $0, 1$ because I'm curious what the intention was of the person who set the question.
$endgroup$
– Mees de Vries
Feb 1 at 21:10
$begingroup$
@MeesdeVries I think you asked what special property of $nu$ implies $sum_{d | n} mu(d) nu(n/d) in {0,1}$ and the answer is that $nu$ is additive with $nu(p^k) - nu(p^{k-1}) in {0,1}$.
$endgroup$
– reuns
Feb 1 at 21:16
$begingroup$
Yes, but from that statement it is also immediate that $p$ is the indicator function of the primes. The question in the textbook did not ask what $mu * nu$ was, only to prove that one property. That suggests to me that there should be some easy, by-inspection method to see that $p$ should only take the values $0, 1$, without identifying the function entirely. (I could be wrong of course, but that would just mean my question has no answer.)
$endgroup$
– Mees de Vries
Feb 1 at 21:19
add a comment |
$begingroup$
There is the generalization of your first solution, showing $mu ast f$ for additive functions is always easy to find :
Let $f(n)$ be additive that is $f(nm) =f(n)+f(m)$ for $gcd(n,m)=1$.
Let $g(p^k) = f(p^k)-f(p^{k-1})$ and $g(n) = 0$ if $n$ isn't a prime power
Then $f(n) = sum_{p^k | n} f(p^k) = sum_{p^k | n} g(p^k) = sum_{d | n} g(d)$
Whence $sum_{d | n} mu(d) f(n/d)= g(n)$
answered Feb 1 at 21:02
reunsreuns
20.8k21353
$endgroup$
There is the generalization of your first solution, showing $mu ast f$ for additive functions is always easy to find :
Let $f(n)$ be additive that is $f(nm) =f(n)+f(m)$ for $gcd(n,m)=1$.
Let $g(p^k) = f(p^k)-f(p^{k-1})$ and $g(n) = 0$ if $n$ isn't a prime power
Then $f(n) = sum_{p^k | n} f(p^k) = sum_{p^k | n} g(p^k) = sum_{d | n} g(d)$
Whence $sum_{d | n} mu(d) f(n/d)= g(n)$
answered Feb 1 at 21:02
reunsreuns
20.8k21353
edited Feb 1 at 21:10
answered Feb 1 at 21:02
reunsreuns
20.8k21353
answered Feb 1 at 21:02
reunsreuns
20.8k21353
answered Feb 1 at 21:02
reunsreuns
20.8k21353
20.8k21353
$begingroup$
This is a nice observation, but it doesn't really answer my question.
$endgroup$
– Mees de Vries
Feb 1 at 21:07
$begingroup$
@MeesdeVries Can you rephrase your question to make clear how it doesn't answer to it ? Your function is additive thus we can easily find the values taken by $muast f$
$endgroup$
– reuns
Feb 1 at 21:08
$begingroup$
But I already know what $p$ is -- it's in the question body. I'm specifically asking for an argument that does not show what $p$ is precisely, but only demonstrates the fact that $p$ only takes the values $0, 1$ because I'm curious what the intention was of the person who set the question.
$endgroup$
– Mees de Vries
Feb 1 at 21:10
$begingroup$
@MeesdeVries I think you asked what special property of $nu$ implies $sum_{d | n} mu(d) nu(n/d) in {0,1}$ and the answer is that $nu$ is additive with $nu(p^k) - nu(p^{k-1}) in {0,1}$.
$endgroup$
– reuns
Feb 1 at 21:16
$begingroup$
Yes, but from that statement it is also immediate that $p$ is the indicator function of the primes. The question in the textbook did not ask what $mu * nu$ was, only to prove that one property. That suggests to me that there should be some easy, by-inspection method to see that $p$ should only take the values $0, 1$, without identifying the function entirely. (I could be wrong of course, but that would just mean my question has no answer.)
$endgroup$
– Mees de Vries
Feb 1 at 21:19
add a comment |
$begingroup$
This is a nice observation, but it doesn't really answer my question.
$endgroup$
– Mees de Vries
Feb 1 at 21:07
$begingroup$
@MeesdeVries Can you rephrase your question to make clear how it doesn't answer to it ? Your function is additive thus we can easily find the values taken by $muast f$
$endgroup$
– reuns
Feb 1 at 21:08
$begingroup$
But I already know what $p$ is -- it's in the question body. I'm specifically asking for an argument that does not show what $p$ is precisely, but only demonstrates the fact that $p$ only takes the values $0, 1$ because I'm curious what the intention was of the person who set the question.
$endgroup$
– Mees de Vries
Feb 1 at 21:10
$begingroup$
@MeesdeVries I think you asked what special property of $nu$ implies $sum_{d | n} mu(d) nu(n/d) in {0,1}$ and the answer is that $nu$ is additive with $nu(p^k) - nu(p^{k-1}) in {0,1}$.
$endgroup$
– reuns
Feb 1 at 21:16
$begingroup$
Yes, but from that statement it is also immediate that $p$ is the indicator function of the primes. The question in the textbook did not ask what $mu * nu$ was, only to prove that one property. That suggests to me that there should be some easy, by-inspection method to see that $p$ should only take the values $0, 1$, without identifying the function entirely. (I could be wrong of course, but that would just mean my question has no answer.)
$endgroup$
– Mees de Vries
Feb 1 at 21:19
$begingroup$
This is a nice observation, but it doesn't really answer my question.
$endgroup$
– Mees de Vries
Feb 1 at 21:07
$begingroup$
This is a nice observation, but it doesn't really answer my question.
$endgroup$
– Mees de Vries
Feb 1 at 21:07
$begingroup$
@MeesdeVries Can you rephrase your question to make clear how it doesn't answer to it ? Your function is additive thus we can easily find the values taken by $muast f$
$endgroup$
– reuns
Feb 1 at 21:08
$begingroup$
@MeesdeVries Can you rephrase your question to make clear how it doesn't answer to it ? Your function is additive thus we can easily find the values taken by $muast f$
$endgroup$
– reuns
Feb 1 at 21:08
$begingroup$
But I already know what $p$ is -- it's in the question body. I'm specifically asking for an argument that does not show what $p$ is precisely, but only demonstrates the fact that $p$ only takes the values $0, 1$ because I'm curious what the intention was of the person who set the question.
$endgroup$
– Mees de Vries
Feb 1 at 21:10
$begingroup$
But I already know what $p$ is -- it's in the question body. I'm specifically asking for an argument that does not show what $p$ is precisely, but only demonstrates the fact that $p$ only takes the values $0, 1$ because I'm curious what the intention was of the person who set the question.
$endgroup$
– Mees de Vries
Feb 1 at 21:10
$begingroup$
@MeesdeVries I think you asked what special property of $nu$ implies $sum_{d | n} mu(d) nu(n/d) in {0,1}$ and the answer is that $nu$ is additive with $nu(p^k) - nu(p^{k-1}) in {0,1}$.
$endgroup$
– reuns
Feb 1 at 21:16
$begingroup$
@MeesdeVries I think you asked what special property of $nu$ implies $sum_{d | n} mu(d) nu(n/d) in {0,1}$ and the answer is that $nu$ is additive with $nu(p^k) - nu(p^{k-1}) in {0,1}$.
$endgroup$
– reuns
Feb 1 at 21:16
$begingroup$
Yes, but from that statement it is also immediate that $p$ is the indicator function of the primes. The question in the textbook did not ask what $mu * nu$ was, only to prove that one property. That suggests to me that there should be some easy, by-inspection method to see that $p$ should only take the values $0, 1$, without identifying the function entirely. (I could be wrong of course, but that would just mean my question has no answer.)
$endgroup$
– Mees de Vries
Feb 1 at 21:19
$begingroup$
Yes, but from that statement it is also immediate that $p$ is the indicator function of the primes. The question in the textbook did not ask what $mu * nu$ was, only to prove that one property. That suggests to me that there should be some easy, by-inspection method to see that $p$ should only take the values $0, 1$, without identifying the function entirely. (I could be wrong of course, but that would just mean my question has no answer.)
$endgroup$
– Mees de Vries
Feb 1 at 21:19
add a comment |
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.
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%2f3096612%2feasy-way-to-prove-property-of-prime-indicator%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
