Bdtyktl

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!

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.

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.

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$.

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.