Help in understanding why the arithmetic derivative is well-defined.
I'm reading into the arithmetic derivative at the moment and I just don't get why it is well-defined. For reference, Ufnarovski tried explaining it here on page 2. I would like to understand the not explicitly stated induction. Thanks in advance!
number-theory elementary-number-theory definition arithmetic-derivative
add a comment |
I'm reading into the arithmetic derivative at the moment and I just don't get why it is well-defined. For reference, Ufnarovski tried explaining it here on page 2. I would like to understand the not explicitly stated induction. Thanks in advance!
number-theory elementary-number-theory definition arithmetic-derivative
add a comment |
I'm reading into the arithmetic derivative at the moment and I just don't get why it is well-defined. For reference, Ufnarovski tried explaining it here on page 2. I would like to understand the not explicitly stated induction. Thanks in advance!
number-theory elementary-number-theory definition arithmetic-derivative
I'm reading into the arithmetic derivative at the moment and I just don't get why it is well-defined. For reference, Ufnarovski tried explaining it here on page 2. I would like to understand the not explicitly stated induction. Thanks in advance!
number-theory elementary-number-theory definition arithmetic-derivative
number-theory elementary-number-theory definition arithmetic-derivative
edited Dec 2 '18 at 18:00
Servaes
22.4k33793
22.4k33793
asked Dec 2 '18 at 14:44
Flammable Maths
835
835
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
To be perfectly frank, any notion is well defined so long as there are no contradictions. Here, we are really just defining a special function from $mathbb{N}$ to $mathbb{N}cup{0}$. So long as it is defined on all inputs then we are technically done.
There is a small wrinkle that we also want this function to satisfy some properties, but that isn't a real issue; once you have the function written down you just need to verify that the properties hold. In this case, we need to verify two properties:
1) $p'=1$ for all primes $p$
2) $(ab)'=a'b+ab'$ for any $a,binmathbb{N}$
That property 1 is true is obvious from the definition.
That property 2 is true is less obvious, but the paper you linked goes through the small bit of math necessary to show that the Leibniz rule holds.
So what have we shown? That the function $(cdot)':mathbb{N}rightarrowmathbb{N}cup{0}$ as defined satisfies the two properties we wanted. What is brushed over very lightly is the author's comments that state this function is the only way we can define the notion of arithmetic derivative that we want. But this issue has nothing to do with the fact that our derivative is well-defined. Uniqueness and being well-defined are two separate ideas.
But let's talk about uniqueness anyway, since that is a part of your post. Suppose you have a two functions $f$ and $g$ that are arithmetic derivatives. What are $f(1)$ and $g(1)$? By the fact that $f$ and $g$ satisfy the Leibniz rule we know that $f(1)=g(1)=0$; the paper even shows the derivation of this fact. Let this sink in; any arithmetic derivative must send $1$ to $0$. Now let's try and do some (strong) induction:
Assume that for all natural numbers $1leq kleq n$ we have shown that $f(k)=g(k)$. What can we say about $n+1$? If it is prime, then by our first property we see that $f(n+1)=g(n+1)=1$. If it is composite then we may write it as the product of two naturals $a$ and $b$, both of which are less than $n$. Well what is $f(ab)$? By the Leibniz rule and by our inductive hypothesis, we know the following: $$f(n+1)=f(ab)=f(a)b+af(b)=g(a)b+ag(b)=g(ab)=g(n+1)$$
Thus it must by the case that $f$ and $g$ are the same function, and the arithmetic derivative is unique.
That was absolutely helpful and a great insight! Thank you very much :)
– Flammable Maths
Dec 2 '18 at 15:19
1
@FlammableMaths You are very welcome!
– BlarglFlarg
Dec 2 '18 at 15:19
add a comment |
The expression marked (1) is a bit contrived, but it is well-defined because the author implicitly assumes that $n_i>0$ for all $i$ in the expression $n=prod_{i=1}^kp_i^{n_i}$. This determines the $p_i$ and $n_i$ uniquely, because (positive) integers have unique factorizations. Rewriting expression (1) as
$$n'=nsum_{i=1}^kfrac{n_i}{p_i}=sum_{i=1}n_ifrac{n}{p_i},$$
shows that $n'$ is an integer, because the $p_i$ divide $n$ and the $n_i$ are integers by definition.
It is noteworthy that during the proof, the author mentions that the formula works even if $n_i = 0$ for some $i.$ But that is just for the convenience of being able to make an arbitrary factorization of $n$ into two factors, one of which may not be divisible by some prime factor of $n.$ For the purpose of showing that the formula gives a unique answer for any $n,$ we want to use the Leibniz rule to eliminate any factors whose exponents are zero, as is usual when writing a "unique" prime factorization.
– David K
Dec 2 '18 at 16:49
1
For the person who keeps trying to change $n_i>0$ to $n_igeq 0,$ please comment why you think that change is required, and do not just keep resubmitting it until you find reviewers who let it through.
– David K
Dec 2 '18 at 16:50
add a comment |
Unique prime factorization and the Leibniz rule are enough. You can induct on the number of prime factors or on the total number of factors. As an example, suppose $n=p^3q^2r$ with $p,q,r$ prime. You can expand it to $n=pppqqr$ and use Leibniz to get $$n'=p'ppqqr+pp'pqqr+ppp'qqr+pppq'qr+pppqq'r+pppqqr'=3p^2q^2r+2p^3qr+p^3q^2$$
The point is that any intermediate decomposition of $n$ can be further decomposed into the unique set of prime factors.
If you look at the formula for the arithmetic derivative in the article, you can just use strong induction on $n$. Assume $n=pq$, with $p,q$ not assumed to be prime. If you know the derivatives of $p,q$ are given by the formula because they are smaller than $n$, you can show the formula holds for $n$.
add a comment |
I did a Google search on "arithmetic derivative" and the first two hits were to wikipedia and OEIS.org/wiki. They clearly start by defining it for primes and then, just as for the calculus derivative, the derivative is defined for any product of factors by the Leibniz rule. The key fact is that every integer has an essentially unique factorization into prime factors coupled with the fact that multiplication is associative and commutative. If this were not the case, then there is no reason to expect that you can have a well-defined derivative. The existence and uniqueness of the derivative has to be proved, but unique factorization with associativity and commutativity implies both of these.
You might want to consider a variation of the arithmetic derivative where $, p'=1 ,$ for all primes $,p,$ and $, (ab)'=a'b+2ab', $ for all rational $,a,b.,$ What goes wrong here?
Perhaps a simple example will make things clearer. Consider a
magma or groupoid
which is a set $A$ with a binary operation $*$. The binary operation
is not assumed to be associative or commutative. Suppose that the
magma has a subset of generators $G$. That means that for every
element $x$ of $A$ there exists a finite number of generator elements
whose product equals $x$. Note that unless $A$ is freely generated by $G$,
then there can be more than one way to generate $x$. Now suppose we
want to define a morphism $f$ of $A$ to another magma $B$. We can
choose to define $f$ on all the generators $G$. Then we require the
morphism equation $,f(x*y) = f(x)*f(y),$ for all $x,y$ in $A$.
If $A$ is freely generated by $G$, then since each element $x$ in $A$
has a unique expression as a word on $G$, then $f(x)$ is uniquely
determined by extension using the morphism equation. This is proved
by induction on the length of the word which expresses $x$.
If $,A,$ is not freely generated by $G$, then it may be that the
morphism $,f,$ can not be well-defined.
Here is a minimal counterexample.
Let $,A = {a,b},,$ with binary operation $,x*y = x,$ for all $,x,y,$
in $,A.,$ Let $,B = {0,1},,$ with binary operation $,0cdot x=0,$
and $,1cdot x=x,$ for all $,x,$ in $,B.,$ No single element of $,A,$
is a generator so $,G = A,$ is a generating set of $,A,$ but not free
generators since $,a*b=b.,$. Now suppose that $,f(a)=0, f(b)=1.,$ Check
that $,f(a*b) = f(b) = 1,$ but $, f(a)cdot f(b) = 0cdot 1 = 0.,$ Now
$, f(a*b) = 1 ,$ but $, f(a)*f(b) = 0.,$ Therefore $f$ is not a morphism.
3
So this unique prime factorization is already enough to prove the well-defined property?
– Flammable Maths
Dec 2 '18 at 15:04
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%2f3022717%2fhelp-in-understanding-why-the-arithmetic-derivative-is-well-defined%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
To be perfectly frank, any notion is well defined so long as there are no contradictions. Here, we are really just defining a special function from $mathbb{N}$ to $mathbb{N}cup{0}$. So long as it is defined on all inputs then we are technically done.
There is a small wrinkle that we also want this function to satisfy some properties, but that isn't a real issue; once you have the function written down you just need to verify that the properties hold. In this case, we need to verify two properties:
1) $p'=1$ for all primes $p$
2) $(ab)'=a'b+ab'$ for any $a,binmathbb{N}$
That property 1 is true is obvious from the definition.
That property 2 is true is less obvious, but the paper you linked goes through the small bit of math necessary to show that the Leibniz rule holds.
So what have we shown? That the function $(cdot)':mathbb{N}rightarrowmathbb{N}cup{0}$ as defined satisfies the two properties we wanted. What is brushed over very lightly is the author's comments that state this function is the only way we can define the notion of arithmetic derivative that we want. But this issue has nothing to do with the fact that our derivative is well-defined. Uniqueness and being well-defined are two separate ideas.
But let's talk about uniqueness anyway, since that is a part of your post. Suppose you have a two functions $f$ and $g$ that are arithmetic derivatives. What are $f(1)$ and $g(1)$? By the fact that $f$ and $g$ satisfy the Leibniz rule we know that $f(1)=g(1)=0$; the paper even shows the derivation of this fact. Let this sink in; any arithmetic derivative must send $1$ to $0$. Now let's try and do some (strong) induction:
Assume that for all natural numbers $1leq kleq n$ we have shown that $f(k)=g(k)$. What can we say about $n+1$? If it is prime, then by our first property we see that $f(n+1)=g(n+1)=1$. If it is composite then we may write it as the product of two naturals $a$ and $b$, both of which are less than $n$. Well what is $f(ab)$? By the Leibniz rule and by our inductive hypothesis, we know the following: $$f(n+1)=f(ab)=f(a)b+af(b)=g(a)b+ag(b)=g(ab)=g(n+1)$$
Thus it must by the case that $f$ and $g$ are the same function, and the arithmetic derivative is unique.
That was absolutely helpful and a great insight! Thank you very much :)
– Flammable Maths
Dec 2 '18 at 15:19
1
@FlammableMaths You are very welcome!
– BlarglFlarg
Dec 2 '18 at 15:19
add a comment |
To be perfectly frank, any notion is well defined so long as there are no contradictions. Here, we are really just defining a special function from $mathbb{N}$ to $mathbb{N}cup{0}$. So long as it is defined on all inputs then we are technically done.
There is a small wrinkle that we also want this function to satisfy some properties, but that isn't a real issue; once you have the function written down you just need to verify that the properties hold. In this case, we need to verify two properties:
1) $p'=1$ for all primes $p$
2) $(ab)'=a'b+ab'$ for any $a,binmathbb{N}$
That property 1 is true is obvious from the definition.
That property 2 is true is less obvious, but the paper you linked goes through the small bit of math necessary to show that the Leibniz rule holds.
So what have we shown? That the function $(cdot)':mathbb{N}rightarrowmathbb{N}cup{0}$ as defined satisfies the two properties we wanted. What is brushed over very lightly is the author's comments that state this function is the only way we can define the notion of arithmetic derivative that we want. But this issue has nothing to do with the fact that our derivative is well-defined. Uniqueness and being well-defined are two separate ideas.
But let's talk about uniqueness anyway, since that is a part of your post. Suppose you have a two functions $f$ and $g$ that are arithmetic derivatives. What are $f(1)$ and $g(1)$? By the fact that $f$ and $g$ satisfy the Leibniz rule we know that $f(1)=g(1)=0$; the paper even shows the derivation of this fact. Let this sink in; any arithmetic derivative must send $1$ to $0$. Now let's try and do some (strong) induction:
Assume that for all natural numbers $1leq kleq n$ we have shown that $f(k)=g(k)$. What can we say about $n+1$? If it is prime, then by our first property we see that $f(n+1)=g(n+1)=1$. If it is composite then we may write it as the product of two naturals $a$ and $b$, both of which are less than $n$. Well what is $f(ab)$? By the Leibniz rule and by our inductive hypothesis, we know the following: $$f(n+1)=f(ab)=f(a)b+af(b)=g(a)b+ag(b)=g(ab)=g(n+1)$$
Thus it must by the case that $f$ and $g$ are the same function, and the arithmetic derivative is unique.
That was absolutely helpful and a great insight! Thank you very much :)
– Flammable Maths
Dec 2 '18 at 15:19
1
@FlammableMaths You are very welcome!
– BlarglFlarg
Dec 2 '18 at 15:19
add a comment |
To be perfectly frank, any notion is well defined so long as there are no contradictions. Here, we are really just defining a special function from $mathbb{N}$ to $mathbb{N}cup{0}$. So long as it is defined on all inputs then we are technically done.
There is a small wrinkle that we also want this function to satisfy some properties, but that isn't a real issue; once you have the function written down you just need to verify that the properties hold. In this case, we need to verify two properties:
1) $p'=1$ for all primes $p$
2) $(ab)'=a'b+ab'$ for any $a,binmathbb{N}$
That property 1 is true is obvious from the definition.
That property 2 is true is less obvious, but the paper you linked goes through the small bit of math necessary to show that the Leibniz rule holds.
So what have we shown? That the function $(cdot)':mathbb{N}rightarrowmathbb{N}cup{0}$ as defined satisfies the two properties we wanted. What is brushed over very lightly is the author's comments that state this function is the only way we can define the notion of arithmetic derivative that we want. But this issue has nothing to do with the fact that our derivative is well-defined. Uniqueness and being well-defined are two separate ideas.
But let's talk about uniqueness anyway, since that is a part of your post. Suppose you have a two functions $f$ and $g$ that are arithmetic derivatives. What are $f(1)$ and $g(1)$? By the fact that $f$ and $g$ satisfy the Leibniz rule we know that $f(1)=g(1)=0$; the paper even shows the derivation of this fact. Let this sink in; any arithmetic derivative must send $1$ to $0$. Now let's try and do some (strong) induction:
Assume that for all natural numbers $1leq kleq n$ we have shown that $f(k)=g(k)$. What can we say about $n+1$? If it is prime, then by our first property we see that $f(n+1)=g(n+1)=1$. If it is composite then we may write it as the product of two naturals $a$ and $b$, both of which are less than $n$. Well what is $f(ab)$? By the Leibniz rule and by our inductive hypothesis, we know the following: $$f(n+1)=f(ab)=f(a)b+af(b)=g(a)b+ag(b)=g(ab)=g(n+1)$$
Thus it must by the case that $f$ and $g$ are the same function, and the arithmetic derivative is unique.
To be perfectly frank, any notion is well defined so long as there are no contradictions. Here, we are really just defining a special function from $mathbb{N}$ to $mathbb{N}cup{0}$. So long as it is defined on all inputs then we are technically done.
There is a small wrinkle that we also want this function to satisfy some properties, but that isn't a real issue; once you have the function written down you just need to verify that the properties hold. In this case, we need to verify two properties:
1) $p'=1$ for all primes $p$
2) $(ab)'=a'b+ab'$ for any $a,binmathbb{N}$
That property 1 is true is obvious from the definition.
That property 2 is true is less obvious, but the paper you linked goes through the small bit of math necessary to show that the Leibniz rule holds.
So what have we shown? That the function $(cdot)':mathbb{N}rightarrowmathbb{N}cup{0}$ as defined satisfies the two properties we wanted. What is brushed over very lightly is the author's comments that state this function is the only way we can define the notion of arithmetic derivative that we want. But this issue has nothing to do with the fact that our derivative is well-defined. Uniqueness and being well-defined are two separate ideas.
But let's talk about uniqueness anyway, since that is a part of your post. Suppose you have a two functions $f$ and $g$ that are arithmetic derivatives. What are $f(1)$ and $g(1)$? By the fact that $f$ and $g$ satisfy the Leibniz rule we know that $f(1)=g(1)=0$; the paper even shows the derivation of this fact. Let this sink in; any arithmetic derivative must send $1$ to $0$. Now let's try and do some (strong) induction:
Assume that for all natural numbers $1leq kleq n$ we have shown that $f(k)=g(k)$. What can we say about $n+1$? If it is prime, then by our first property we see that $f(n+1)=g(n+1)=1$. If it is composite then we may write it as the product of two naturals $a$ and $b$, both of which are less than $n$. Well what is $f(ab)$? By the Leibniz rule and by our inductive hypothesis, we know the following: $$f(n+1)=f(ab)=f(a)b+af(b)=g(a)b+ag(b)=g(ab)=g(n+1)$$
Thus it must by the case that $f$ and $g$ are the same function, and the arithmetic derivative is unique.
edited Dec 2 '18 at 15:21
answered Dec 2 '18 at 15:11
BlarglFlarg
2234
2234
That was absolutely helpful and a great insight! Thank you very much :)
– Flammable Maths
Dec 2 '18 at 15:19
1
@FlammableMaths You are very welcome!
– BlarglFlarg
Dec 2 '18 at 15:19
add a comment |
That was absolutely helpful and a great insight! Thank you very much :)
– Flammable Maths
Dec 2 '18 at 15:19
1
@FlammableMaths You are very welcome!
– BlarglFlarg
Dec 2 '18 at 15:19
That was absolutely helpful and a great insight! Thank you very much :)
– Flammable Maths
Dec 2 '18 at 15:19
That was absolutely helpful and a great insight! Thank you very much :)
– Flammable Maths
Dec 2 '18 at 15:19
1
1
@FlammableMaths You are very welcome!
– BlarglFlarg
Dec 2 '18 at 15:19
@FlammableMaths You are very welcome!
– BlarglFlarg
Dec 2 '18 at 15:19
add a comment |
The expression marked (1) is a bit contrived, but it is well-defined because the author implicitly assumes that $n_i>0$ for all $i$ in the expression $n=prod_{i=1}^kp_i^{n_i}$. This determines the $p_i$ and $n_i$ uniquely, because (positive) integers have unique factorizations. Rewriting expression (1) as
$$n'=nsum_{i=1}^kfrac{n_i}{p_i}=sum_{i=1}n_ifrac{n}{p_i},$$
shows that $n'$ is an integer, because the $p_i$ divide $n$ and the $n_i$ are integers by definition.
It is noteworthy that during the proof, the author mentions that the formula works even if $n_i = 0$ for some $i.$ But that is just for the convenience of being able to make an arbitrary factorization of $n$ into two factors, one of which may not be divisible by some prime factor of $n.$ For the purpose of showing that the formula gives a unique answer for any $n,$ we want to use the Leibniz rule to eliminate any factors whose exponents are zero, as is usual when writing a "unique" prime factorization.
– David K
Dec 2 '18 at 16:49
1
For the person who keeps trying to change $n_i>0$ to $n_igeq 0,$ please comment why you think that change is required, and do not just keep resubmitting it until you find reviewers who let it through.
– David K
Dec 2 '18 at 16:50
add a comment |
The expression marked (1) is a bit contrived, but it is well-defined because the author implicitly assumes that $n_i>0$ for all $i$ in the expression $n=prod_{i=1}^kp_i^{n_i}$. This determines the $p_i$ and $n_i$ uniquely, because (positive) integers have unique factorizations. Rewriting expression (1) as
$$n'=nsum_{i=1}^kfrac{n_i}{p_i}=sum_{i=1}n_ifrac{n}{p_i},$$
shows that $n'$ is an integer, because the $p_i$ divide $n$ and the $n_i$ are integers by definition.
It is noteworthy that during the proof, the author mentions that the formula works even if $n_i = 0$ for some $i.$ But that is just for the convenience of being able to make an arbitrary factorization of $n$ into two factors, one of which may not be divisible by some prime factor of $n.$ For the purpose of showing that the formula gives a unique answer for any $n,$ we want to use the Leibniz rule to eliminate any factors whose exponents are zero, as is usual when writing a "unique" prime factorization.
– David K
Dec 2 '18 at 16:49
1
For the person who keeps trying to change $n_i>0$ to $n_igeq 0,$ please comment why you think that change is required, and do not just keep resubmitting it until you find reviewers who let it through.
– David K
Dec 2 '18 at 16:50
add a comment |
The expression marked (1) is a bit contrived, but it is well-defined because the author implicitly assumes that $n_i>0$ for all $i$ in the expression $n=prod_{i=1}^kp_i^{n_i}$. This determines the $p_i$ and $n_i$ uniquely, because (positive) integers have unique factorizations. Rewriting expression (1) as
$$n'=nsum_{i=1}^kfrac{n_i}{p_i}=sum_{i=1}n_ifrac{n}{p_i},$$
shows that $n'$ is an integer, because the $p_i$ divide $n$ and the $n_i$ are integers by definition.
The expression marked (1) is a bit contrived, but it is well-defined because the author implicitly assumes that $n_i>0$ for all $i$ in the expression $n=prod_{i=1}^kp_i^{n_i}$. This determines the $p_i$ and $n_i$ uniquely, because (positive) integers have unique factorizations. Rewriting expression (1) as
$$n'=nsum_{i=1}^kfrac{n_i}{p_i}=sum_{i=1}n_ifrac{n}{p_i},$$
shows that $n'$ is an integer, because the $p_i$ divide $n$ and the $n_i$ are integers by definition.
edited Dec 2 '18 at 16:39
David K
52.6k340115
52.6k340115
answered Dec 2 '18 at 15:22
Servaes
22.4k33793
22.4k33793
It is noteworthy that during the proof, the author mentions that the formula works even if $n_i = 0$ for some $i.$ But that is just for the convenience of being able to make an arbitrary factorization of $n$ into two factors, one of which may not be divisible by some prime factor of $n.$ For the purpose of showing that the formula gives a unique answer for any $n,$ we want to use the Leibniz rule to eliminate any factors whose exponents are zero, as is usual when writing a "unique" prime factorization.
– David K
Dec 2 '18 at 16:49
1
For the person who keeps trying to change $n_i>0$ to $n_igeq 0,$ please comment why you think that change is required, and do not just keep resubmitting it until you find reviewers who let it through.
– David K
Dec 2 '18 at 16:50
add a comment |
It is noteworthy that during the proof, the author mentions that the formula works even if $n_i = 0$ for some $i.$ But that is just for the convenience of being able to make an arbitrary factorization of $n$ into two factors, one of which may not be divisible by some prime factor of $n.$ For the purpose of showing that the formula gives a unique answer for any $n,$ we want to use the Leibniz rule to eliminate any factors whose exponents are zero, as is usual when writing a "unique" prime factorization.
– David K
Dec 2 '18 at 16:49
1
For the person who keeps trying to change $n_i>0$ to $n_igeq 0,$ please comment why you think that change is required, and do not just keep resubmitting it until you find reviewers who let it through.
– David K
Dec 2 '18 at 16:50
It is noteworthy that during the proof, the author mentions that the formula works even if $n_i = 0$ for some $i.$ But that is just for the convenience of being able to make an arbitrary factorization of $n$ into two factors, one of which may not be divisible by some prime factor of $n.$ For the purpose of showing that the formula gives a unique answer for any $n,$ we want to use the Leibniz rule to eliminate any factors whose exponents are zero, as is usual when writing a "unique" prime factorization.
– David K
Dec 2 '18 at 16:49
It is noteworthy that during the proof, the author mentions that the formula works even if $n_i = 0$ for some $i.$ But that is just for the convenience of being able to make an arbitrary factorization of $n$ into two factors, one of which may not be divisible by some prime factor of $n.$ For the purpose of showing that the formula gives a unique answer for any $n,$ we want to use the Leibniz rule to eliminate any factors whose exponents are zero, as is usual when writing a "unique" prime factorization.
– David K
Dec 2 '18 at 16:49
1
1
For the person who keeps trying to change $n_i>0$ to $n_igeq 0,$ please comment why you think that change is required, and do not just keep resubmitting it until you find reviewers who let it through.
– David K
Dec 2 '18 at 16:50
For the person who keeps trying to change $n_i>0$ to $n_igeq 0,$ please comment why you think that change is required, and do not just keep resubmitting it until you find reviewers who let it through.
– David K
Dec 2 '18 at 16:50
add a comment |
Unique prime factorization and the Leibniz rule are enough. You can induct on the number of prime factors or on the total number of factors. As an example, suppose $n=p^3q^2r$ with $p,q,r$ prime. You can expand it to $n=pppqqr$ and use Leibniz to get $$n'=p'ppqqr+pp'pqqr+ppp'qqr+pppq'qr+pppqq'r+pppqqr'=3p^2q^2r+2p^3qr+p^3q^2$$
The point is that any intermediate decomposition of $n$ can be further decomposed into the unique set of prime factors.
If you look at the formula for the arithmetic derivative in the article, you can just use strong induction on $n$. Assume $n=pq$, with $p,q$ not assumed to be prime. If you know the derivatives of $p,q$ are given by the formula because they are smaller than $n$, you can show the formula holds for $n$.
add a comment |
Unique prime factorization and the Leibniz rule are enough. You can induct on the number of prime factors or on the total number of factors. As an example, suppose $n=p^3q^2r$ with $p,q,r$ prime. You can expand it to $n=pppqqr$ and use Leibniz to get $$n'=p'ppqqr+pp'pqqr+ppp'qqr+pppq'qr+pppqq'r+pppqqr'=3p^2q^2r+2p^3qr+p^3q^2$$
The point is that any intermediate decomposition of $n$ can be further decomposed into the unique set of prime factors.
If you look at the formula for the arithmetic derivative in the article, you can just use strong induction on $n$. Assume $n=pq$, with $p,q$ not assumed to be prime. If you know the derivatives of $p,q$ are given by the formula because they are smaller than $n$, you can show the formula holds for $n$.
add a comment |
Unique prime factorization and the Leibniz rule are enough. You can induct on the number of prime factors or on the total number of factors. As an example, suppose $n=p^3q^2r$ with $p,q,r$ prime. You can expand it to $n=pppqqr$ and use Leibniz to get $$n'=p'ppqqr+pp'pqqr+ppp'qqr+pppq'qr+pppqq'r+pppqqr'=3p^2q^2r+2p^3qr+p^3q^2$$
The point is that any intermediate decomposition of $n$ can be further decomposed into the unique set of prime factors.
If you look at the formula for the arithmetic derivative in the article, you can just use strong induction on $n$. Assume $n=pq$, with $p,q$ not assumed to be prime. If you know the derivatives of $p,q$ are given by the formula because they are smaller than $n$, you can show the formula holds for $n$.
Unique prime factorization and the Leibniz rule are enough. You can induct on the number of prime factors or on the total number of factors. As an example, suppose $n=p^3q^2r$ with $p,q,r$ prime. You can expand it to $n=pppqqr$ and use Leibniz to get $$n'=p'ppqqr+pp'pqqr+ppp'qqr+pppq'qr+pppqq'r+pppqqr'=3p^2q^2r+2p^3qr+p^3q^2$$
The point is that any intermediate decomposition of $n$ can be further decomposed into the unique set of prime factors.
If you look at the formula for the arithmetic derivative in the article, you can just use strong induction on $n$. Assume $n=pq$, with $p,q$ not assumed to be prime. If you know the derivatives of $p,q$ are given by the formula because they are smaller than $n$, you can show the formula holds for $n$.
answered Dec 2 '18 at 15:44
Ross Millikan
291k23196371
291k23196371
add a comment |
add a comment |
I did a Google search on "arithmetic derivative" and the first two hits were to wikipedia and OEIS.org/wiki. They clearly start by defining it for primes and then, just as for the calculus derivative, the derivative is defined for any product of factors by the Leibniz rule. The key fact is that every integer has an essentially unique factorization into prime factors coupled with the fact that multiplication is associative and commutative. If this were not the case, then there is no reason to expect that you can have a well-defined derivative. The existence and uniqueness of the derivative has to be proved, but unique factorization with associativity and commutativity implies both of these.
You might want to consider a variation of the arithmetic derivative where $, p'=1 ,$ for all primes $,p,$ and $, (ab)'=a'b+2ab', $ for all rational $,a,b.,$ What goes wrong here?
Perhaps a simple example will make things clearer. Consider a
magma or groupoid
which is a set $A$ with a binary operation $*$. The binary operation
is not assumed to be associative or commutative. Suppose that the
magma has a subset of generators $G$. That means that for every
element $x$ of $A$ there exists a finite number of generator elements
whose product equals $x$. Note that unless $A$ is freely generated by $G$,
then there can be more than one way to generate $x$. Now suppose we
want to define a morphism $f$ of $A$ to another magma $B$. We can
choose to define $f$ on all the generators $G$. Then we require the
morphism equation $,f(x*y) = f(x)*f(y),$ for all $x,y$ in $A$.
If $A$ is freely generated by $G$, then since each element $x$ in $A$
has a unique expression as a word on $G$, then $f(x)$ is uniquely
determined by extension using the morphism equation. This is proved
by induction on the length of the word which expresses $x$.
If $,A,$ is not freely generated by $G$, then it may be that the
morphism $,f,$ can not be well-defined.
Here is a minimal counterexample.
Let $,A = {a,b},,$ with binary operation $,x*y = x,$ for all $,x,y,$
in $,A.,$ Let $,B = {0,1},,$ with binary operation $,0cdot x=0,$
and $,1cdot x=x,$ for all $,x,$ in $,B.,$ No single element of $,A,$
is a generator so $,G = A,$ is a generating set of $,A,$ but not free
generators since $,a*b=b.,$. Now suppose that $,f(a)=0, f(b)=1.,$ Check
that $,f(a*b) = f(b) = 1,$ but $, f(a)cdot f(b) = 0cdot 1 = 0.,$ Now
$, f(a*b) = 1 ,$ but $, f(a)*f(b) = 0.,$ Therefore $f$ is not a morphism.
3
So this unique prime factorization is already enough to prove the well-defined property?
– Flammable Maths
Dec 2 '18 at 15:04
add a comment |
I did a Google search on "arithmetic derivative" and the first two hits were to wikipedia and OEIS.org/wiki. They clearly start by defining it for primes and then, just as for the calculus derivative, the derivative is defined for any product of factors by the Leibniz rule. The key fact is that every integer has an essentially unique factorization into prime factors coupled with the fact that multiplication is associative and commutative. If this were not the case, then there is no reason to expect that you can have a well-defined derivative. The existence and uniqueness of the derivative has to be proved, but unique factorization with associativity and commutativity implies both of these.
You might want to consider a variation of the arithmetic derivative where $, p'=1 ,$ for all primes $,p,$ and $, (ab)'=a'b+2ab', $ for all rational $,a,b.,$ What goes wrong here?
Perhaps a simple example will make things clearer. Consider a
magma or groupoid
which is a set $A$ with a binary operation $*$. The binary operation
is not assumed to be associative or commutative. Suppose that the
magma has a subset of generators $G$. That means that for every
element $x$ of $A$ there exists a finite number of generator elements
whose product equals $x$. Note that unless $A$ is freely generated by $G$,
then there can be more than one way to generate $x$. Now suppose we
want to define a morphism $f$ of $A$ to another magma $B$. We can
choose to define $f$ on all the generators $G$. Then we require the
morphism equation $,f(x*y) = f(x)*f(y),$ for all $x,y$ in $A$.
If $A$ is freely generated by $G$, then since each element $x$ in $A$
has a unique expression as a word on $G$, then $f(x)$ is uniquely
determined by extension using the morphism equation. This is proved
by induction on the length of the word which expresses $x$.
If $,A,$ is not freely generated by $G$, then it may be that the
morphism $,f,$ can not be well-defined.
Here is a minimal counterexample.
Let $,A = {a,b},,$ with binary operation $,x*y = x,$ for all $,x,y,$
in $,A.,$ Let $,B = {0,1},,$ with binary operation $,0cdot x=0,$
and $,1cdot x=x,$ for all $,x,$ in $,B.,$ No single element of $,A,$
is a generator so $,G = A,$ is a generating set of $,A,$ but not free
generators since $,a*b=b.,$. Now suppose that $,f(a)=0, f(b)=1.,$ Check
that $,f(a*b) = f(b) = 1,$ but $, f(a)cdot f(b) = 0cdot 1 = 0.,$ Now
$, f(a*b) = 1 ,$ but $, f(a)*f(b) = 0.,$ Therefore $f$ is not a morphism.
3
So this unique prime factorization is already enough to prove the well-defined property?
– Flammable Maths
Dec 2 '18 at 15:04
add a comment |
I did a Google search on "arithmetic derivative" and the first two hits were to wikipedia and OEIS.org/wiki. They clearly start by defining it for primes and then, just as for the calculus derivative, the derivative is defined for any product of factors by the Leibniz rule. The key fact is that every integer has an essentially unique factorization into prime factors coupled with the fact that multiplication is associative and commutative. If this were not the case, then there is no reason to expect that you can have a well-defined derivative. The existence and uniqueness of the derivative has to be proved, but unique factorization with associativity and commutativity implies both of these.
You might want to consider a variation of the arithmetic derivative where $, p'=1 ,$ for all primes $,p,$ and $, (ab)'=a'b+2ab', $ for all rational $,a,b.,$ What goes wrong here?
Perhaps a simple example will make things clearer. Consider a
magma or groupoid
which is a set $A$ with a binary operation $*$. The binary operation
is not assumed to be associative or commutative. Suppose that the
magma has a subset of generators $G$. That means that for every
element $x$ of $A$ there exists a finite number of generator elements
whose product equals $x$. Note that unless $A$ is freely generated by $G$,
then there can be more than one way to generate $x$. Now suppose we
want to define a morphism $f$ of $A$ to another magma $B$. We can
choose to define $f$ on all the generators $G$. Then we require the
morphism equation $,f(x*y) = f(x)*f(y),$ for all $x,y$ in $A$.
If $A$ is freely generated by $G$, then since each element $x$ in $A$
has a unique expression as a word on $G$, then $f(x)$ is uniquely
determined by extension using the morphism equation. This is proved
by induction on the length of the word which expresses $x$.
If $,A,$ is not freely generated by $G$, then it may be that the
morphism $,f,$ can not be well-defined.
Here is a minimal counterexample.
Let $,A = {a,b},,$ with binary operation $,x*y = x,$ for all $,x,y,$
in $,A.,$ Let $,B = {0,1},,$ with binary operation $,0cdot x=0,$
and $,1cdot x=x,$ for all $,x,$ in $,B.,$ No single element of $,A,$
is a generator so $,G = A,$ is a generating set of $,A,$ but not free
generators since $,a*b=b.,$. Now suppose that $,f(a)=0, f(b)=1.,$ Check
that $,f(a*b) = f(b) = 1,$ but $, f(a)cdot f(b) = 0cdot 1 = 0.,$ Now
$, f(a*b) = 1 ,$ but $, f(a)*f(b) = 0.,$ Therefore $f$ is not a morphism.
I did a Google search on "arithmetic derivative" and the first two hits were to wikipedia and OEIS.org/wiki. They clearly start by defining it for primes and then, just as for the calculus derivative, the derivative is defined for any product of factors by the Leibniz rule. The key fact is that every integer has an essentially unique factorization into prime factors coupled with the fact that multiplication is associative and commutative. If this were not the case, then there is no reason to expect that you can have a well-defined derivative. The existence and uniqueness of the derivative has to be proved, but unique factorization with associativity and commutativity implies both of these.
You might want to consider a variation of the arithmetic derivative where $, p'=1 ,$ for all primes $,p,$ and $, (ab)'=a'b+2ab', $ for all rational $,a,b.,$ What goes wrong here?
Perhaps a simple example will make things clearer. Consider a
magma or groupoid
which is a set $A$ with a binary operation $*$. The binary operation
is not assumed to be associative or commutative. Suppose that the
magma has a subset of generators $G$. That means that for every
element $x$ of $A$ there exists a finite number of generator elements
whose product equals $x$. Note that unless $A$ is freely generated by $G$,
then there can be more than one way to generate $x$. Now suppose we
want to define a morphism $f$ of $A$ to another magma $B$. We can
choose to define $f$ on all the generators $G$. Then we require the
morphism equation $,f(x*y) = f(x)*f(y),$ for all $x,y$ in $A$.
If $A$ is freely generated by $G$, then since each element $x$ in $A$
has a unique expression as a word on $G$, then $f(x)$ is uniquely
determined by extension using the morphism equation. This is proved
by induction on the length of the word which expresses $x$.
If $,A,$ is not freely generated by $G$, then it may be that the
morphism $,f,$ can not be well-defined.
Here is a minimal counterexample.
Let $,A = {a,b},,$ with binary operation $,x*y = x,$ for all $,x,y,$
in $,A.,$ Let $,B = {0,1},,$ with binary operation $,0cdot x=0,$
and $,1cdot x=x,$ for all $,x,$ in $,B.,$ No single element of $,A,$
is a generator so $,G = A,$ is a generating set of $,A,$ but not free
generators since $,a*b=b.,$. Now suppose that $,f(a)=0, f(b)=1.,$ Check
that $,f(a*b) = f(b) = 1,$ but $, f(a)cdot f(b) = 0cdot 1 = 0.,$ Now
$, f(a*b) = 1 ,$ but $, f(a)*f(b) = 0.,$ Therefore $f$ is not a morphism.
edited Dec 3 '18 at 0:00
answered Dec 2 '18 at 15:01
Somos
12.9k11034
12.9k11034
3
So this unique prime factorization is already enough to prove the well-defined property?
– Flammable Maths
Dec 2 '18 at 15:04
add a comment |
3
So this unique prime factorization is already enough to prove the well-defined property?
– Flammable Maths
Dec 2 '18 at 15:04
3
3
So this unique prime factorization is already enough to prove the well-defined property?
– Flammable Maths
Dec 2 '18 at 15:04
So this unique prime factorization is already enough to prove the well-defined property?
– Flammable Maths
Dec 2 '18 at 15:04
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.
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%2f3022717%2fhelp-in-understanding-why-the-arithmetic-derivative-is-well-defined%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