The derivative of a number (2014)
rjlipton.com
rjlipton.com
In this case, we can construct a morphism. Since D(n) follows the product rule, we only need to find a function f of x for each prime p which at some x has a value of p and a derivative of 1. Then we can compose those functions by multiplication for all other natural numbers. f_p(x) = x + p is one such set of functions, giving us the complete function F_n(x) = Π_(p∈P(n)) x + p, where P(n) is the set of prime factors of n. Note, the product of the empty set is defined to be 1, so F_1(x) = 1.
Finally, the homomorphism between D and the derivatives of functions is that D(n) = F'_n(0), so in some sense, D really is a derivative.
My understanding is that this is only the case if they’re isomorphic—even a pair of homomorphisms between the objects is not itself sufficient to identify them as the same. But I also don’t know any category theory, so I might be spouting nonsense :-)
For anyone curious, while Category Theory is very concerned with morphisms, they also come up in many other places. In particular, Abstract Algebra (groups and rings and such) may be a more approachable introduction to morphisms than Category Theory, and then Category Theory flows pretty naturally from the concepts of Abstract Algebra.
If you look at the first page in 2014, the time of the article, you'll find this: https://en.wikipedia.org/w/index.php?title=Arithmetic_deriva...
> E. J. Barbeau was most likely the first person to formalize this definition.
This suggests to me that Shelly's earlier definition in 1911 was not generally known. Indeed, Wikipedia has been a significant driver in rescuing earlier results in mathematics from obscurity.
But you can't cite what you don't know. So I wouldn't expect an emeritus professor, or anyone, to have either a time machine or a crystal ball.
> Would you have found out about those earlier sources without Wikipedia?
I'm not an expert in this domain. The author is.
Would you do something like that using your real name?
> "it wasn't on Wikipedia" is hardly an excuse when it comes to ethics
which is what I actually wrote, in a post where I'm not even talking about the particular situation. I expressed dismay about a failure to properly attribute ideas, and then I explained that I don't care about what was written in 2014 on Wikipedia, experts should know better anyway. If you've decided to read an accusation in what I wrote, that is absolutely on you. The most negative thing I wrote about the author was:
> You'd expect an emeritus professor to have enough time on their hands to check their sources...
And, again, I would have absolutely no problem saying that in public with my real name. I've said much "worse".
lim (p0+h)(p1+h)...(pk+h) - p0*p1*...*pk
D(n) = h->0 ------------------------------------ .
h
This motivates the D(p)=1 definition, meaning we can take D to be defined just by the Leibniz rule. (Note that D(1) = D(1*1) = 1*D(1) + D(1)*1 = 2*D(1), implying that D(1)=0, so that part of the definition is redundant.)Others have pointed out that the definition also works for any unique factorization domain, and in the case of polynomials, the Leibniz rule guarantees D agrees with the standard derivative, which is also a nice sanity check.
https://jvns.ca/blog/2016/04/24/how-regular-expressions-go-f....
As an example basic HTML cannot (?) be parsed by RegExp because tag-pairs can contain tag-pairs:
<div> <div> </div> </div>
eludes RegExp matching, it seems to me, because a typical standard RegExp would only match "<div> <div> </div>" and would not see the 2nd </div>.Can RegExp Derivatives do it better?
Derivatives of RegExps don't automatically unlock parsing of context-free grammars, afaik. For that you need recursion. They do however unlock some very elegant parser designs.
Conor McBride, The Derivative of a Regular Type is its Type of One-Hole Contexts
http://strictlypositive.org/diff.pdf
related to Huet's Zipper and Hinze, Paterson Finger Trees, with a huge of follow-on literature:
https://personal.cis.strath.ac.uk/conor.mcbride/Holes.pdf
https://conal.net/blog/posts/differentiation-of-higher-order...
and numerous old posts by sigfpe (Dan Piponi), e.g.
http://blog.sigfpe.com/2008/06/blessed-mans-formula-for-hole...
Another important concept is that of a curve and its ring of functions in algebraic geometry; for the integers, the curve is the prime spectrum of Z, i.e. the prime ideals generated by each prime number <p>. The ring of regular functions is precisely the ring of integers, operating as functions on prime numbers by n(p) = n modulo p.
I wonder if D has any interpretation in terms of nonlinear differential operators on Spec(Z).
> number derivative is a function defined for integers, based on prime factorization, by analogy with the product rule for the derivative of a function that is used in mathematical analysis.
I was just skimming the wikipedia article but this seems like a good argument.
Broadly, there is a class of functions refered to as "derivations" that can be viewed as a generalization of the derivative. In particular, a derivation satisfies 2 properties:
1) It is linear
2) It satisfies the product rule.
Any function that satisfies these rules is often called a "derivative".
Notably, the function discussed in the article fails the linearity test, which is a pretty big problem for calling it a derivative.
The definition presented here is a loose analogy to derivatives rather than an actual generalization, which doesn't fully justify using the name IMO.
It does, but this one's on a rig (= ring - negatives), not a vector space over any field.
EDIT: Actually, according to wikipedia, that is exactly what is done in differential algebra
Every ring is a module over itself. But you wouldn't want the definition you propose; instead, you'd want `D(ab) = aD(b) + D(a)b`. If you really like some sort of linearity to be present, you could observe that this property forces every derivation to be linear as a transformation of `R_0`-modules, where `R_0` is the subring `ker(D)` of "constants".
It's been many years since I had calculus at uni, and never any abstract math. Why is the product rule picked as the "interesting" attribute of derivatives, ie to serve as the basis for the generalization?
Is there some deeper connection of the product rule in ordinary derivatives that singles out the product rule over the other properties a derivative has?
For me, a key aspect of derivatives is that it allows for something like Taylor expansion or integrals to exist. Are there any equivalent things to these product-rule-generalized derivatives?
Having said that, there are many usages of other derivations where the calculus inspiration is clear, even if the geometric meaning that motivated the calculus is lost.
For instance, we often talk about polynomials over arbitrary fields. In general, there is no way to graph such polynomials. There is no notion of tangent lines, slope, "continuous", or even "less than". There is, however, still the notion of roots and the multiplicity of roots. These notions turn out to be quite important.
When working with any polynomial, you can define the "formal derivative" as a derivation that also satisfies D(x) = 1, D(a) = 0 (where a is an element of the underlying field). This operator behaves as you would naively expect a derivative to behave over polynomials. In Galois theory, it is important to distinguish between polynomials that have repeated roots, and those that do not. If you have a polynomial f(x), you can determine this by taking its formal derivative f'(x). Then, you can easily compute their greatest common divisor [0]. If this is a constant, then you know f has no repeated roots.
[0] Using Euclid's algorithm, this is a purely mechanical process that can be done without needing to factor either f or f'. A similar trick has actually been used to attack real word cryptography. If there are secret primes p and q, and a public number pq, many cryptosystems assume that it is infeasible to determine what p and q are. However, if there is a bad random number generator, you might get 2 different keys that share a prime, so have the public numbers pq and ps, then you can easily determine that p is a common factor, from which you can easily recover q and s. This means that you can look for a large collection of public keys and try this attack on possible pair of them.
Other basic rules would be addition:
(f(x) + g(x))' = f'(x) + g'(x)
This is just linearity (together with constant multiplication)
And function composition (the chain rule):
(f ∘ g)' = (f' ∘ g)⋅g'
We would need to somehow figure out what should correspond to function composition.
So if we want something that captures some important algebraic properties of derivatives the product rule would be a good place to look.
This ”derivative” is not linear though, and that was sort of what motivated my question.
No, that’s the derivative of the function that return n whatever its argument, which also can be written as λx.n or in a zillion different ways.
That can be written as n, but is different from the number n.
Also, one man’s “pretty confusingly is another man’s “similar things should have similar names”. There’s a rich history in mathematics of overloading the meaning of terms and symbols as long as there’s some similarity between them, for example when using × for both the multiplication of numbers and of matrices (where the former is commutative, but the latter isn’t, barring some exceptions such as 1 × 1 matrices).
(See also the comment elsewhere in this thread which says “Mathematicans like to call two things with the same "structure" by the same name, even if it's not obvious how they're otherwise related” (https://news.ycombinator.com/item?id=40327885)
Think of any binary number as a sequence of 0s and 1s in a certain order
For example, 16 in binary is the sequence: 1000
Reading the sequence from right to left, two bits at a time, for each one of those two bits, we can note if the value of the “earlier” bit in the sequence changed
I can note a change as 1 and a not change as 0, then the above sequence becomes:
0 (0-0 no change) 0 (0-0 no change) 1 (0-1 changed)
Result: 100
In decimal: 8
Now if I want to “integrate” that sequence, I can do the reverse, but now I have ambiguity, if I start with 0, the sequence would be the original:
0 0 (0 means no change) 0 (0 means no change) 1 (1 change)
Result: 1000
But if we start with 1 instead:
1 1 (0 no change) 1 (0 no change) 0 (1 change)
Result: 0111
Intuitively you can think of this as tracking a “discrete rate of change”
Usually the derivative or slope of a function gives a real value, now imagine “zooming into” the function until you can’t track a real value anymore, only whether what you are looking at is changing or not every time you look
You can always just split the thing into it’s sequential elements, then get a pair-wise derivative in between the elements
The sequence of pair-wise derivatives is then the equivalent of the derivative of the original sequence
If you do this to the limit where the “space” between the elements is 0, then you get the continuous case
https://arxiv.org/abs/1305.0954
[BiEntropy - The Approximate Entropy of a Finite Binary String]This is super interesting:
> We successfully test the algorithm in the fields of Prime Number Theory (where we prove explicitly that the sequence of prime numbers is not periodic)
What we do, and what ML algorithms try to imitate, when learning, is exactly that: finding loops (periodic sequences) within the data (or rather, fitting the data to continuous “loopy” representations)
The Derivative of a Number - https://news.ycombinator.com/item?id=8198607 - Aug 2014 (47 comments)
if I(n) is the integral of n, then shouldn't I(D(n)) == n?
But if D(prime) = 1, then what prime is the answer to I(1) ??
If this can't be done, then what were doing here isn't differentiation as I understand it. So why call this the derivative of a number? Why not call it something else?
Although you might also want to consider that "integration" (really, indefinite integrals, AKA antiderivative) is only defined up to a constant. So why couldn't it be the same for this "number derivative"? Perhaps the "antiderivative" is only defined up to something. It'd be a fun exercise, if you're interested. Can you figure out under what conditions do you get D(a) = D(b)? Put differently, given an integer c, what are the solutions to D(x) = c?
... for some given function, we can simply recognize the difference between: (a) the function definition; (b) properties of the function.
For the (calculus) derivative: (a) means "rate of change"; (b) means the usual derivative properties e.g. the product rule and chain rule
For the arithmetic derivative [1] (or number derivative): (a) means "1 for any prime; everything else calculated via the product rule" [2]; (b) means the same as above
There are other examples of the above a/b split in mathematics. Finding examples is left as an exercise for the reader.
[1] https://oeis.org/wiki/Arithmetic_derivative
[2] Yes, the definition of (a) makes (b) obvious.
Throw in Leibniz’s rule and the reader is reduced to reading the fine print to understand.
The articles (Wikipedia included) are as guilty of this as whoever chose this name.
It turns out that the definition here exactly matches the usual derivative for polynomials.
If so, can you connect the dots?
Or did you mean the properties (part "b" above)?
> 1 for any prime; everything else calculated via the product rule
does indeed have a surprising amount to do with differentiation!
If you take the usual polynomial functions in one variable (lets say x is the variable and all our things are complex numbers) then these can be factored: e.g. x^2 + 3x + 2 = (x+1)(x+2). They form a (so called) unique factorization domain, which essentially means that factorization into "primes" works exactly the same as it does for integers. In the example above (x+1) and (x+2) are examples of prime factors which can't be factored any further.
If you take the definition "1 for any prime; everything else calculated via the product rule" and apply it to this system where our "numbers" are polynomials and our "primes" are the polynomials we can't factor any further you get a definition of an "arithmetic derivative" for polynomials.
The fun fact then is that this arithmetic derivative we just defined is exactly the same as the usual definition of the derivative from calculus:
D[(x+1)(x+2)] = (x+1)D[(x+2)] + (x+2)D[(x+1)] = (x+1) + (x+2) = 2x+3
whereas
d/dx (x^2 + 3x + 2) = 2x + 3
There are things other than the integers for which it makes sense to talk about "the primes". One example is: polynomials (with coefficients in, let's say, the complex numbers). In this case it turns out that the "primes" are exactly the linear polynomials (ax+b) where a is nonzero.
There's a bit of ambiguity there, just as there is in the integers; 7 and -7 are "the same prime number", and x+3 and 5x+15 are "the same prime polynomial"; if we're going to say D(p)=1 then we need to pick which "version" of p has this property, and the obvious choice is the one of the form (x+a).
So, now, if we apply the same definition as for integers to polynomials with these conventions, it says: (1) D(x+a) = 1 and (2) D(fg) = fD(g) + D(f)g when f,g are polynomials. And that turns out to give the exact same result as the "ordinary" derivative for polynomials.
Whether "exactly identical to" implies "a surprising amount to do with" depends on how easily surprised you are, I guess.
... I glossed over the sense in which the "primes" are precisely the linear polynomials, so here are a few words about that for anyone who's curious.
If we look at polynomials with complex-number coefficients, a beautiful theorem says that they can all be written as A (x-r1) (x-r2) ... (x-rk), and then one polynomial divides another if and only if its set of rj is a subset of the other's (handling repeated roots in the "obvious" way). It's pretty easy to get from this that the linear polynomials are (1) the irreducible ones, i.e., the ones that can't be factored into lower-degree polynomials, and (2) the prime ones, i.e., the ones with the property that if p divides ab then p divides either a or b. (These properties are equivalent for the integers, as well as for polynomials with complex coefficients, but there are other settings in which they come out different, and both of them are useful, so they have different names.)
(What happens if we use real rather than complex coefficients? The Wikipedia "Arithmetic derivative" page claims that we still get the usual derivative, but that looks wrong to me, because if we work over the real numbers then x^2+1 is both prime and irreducible, but its derivative isn't 1. Maybe I'm missing something.)
See theorem (20) on page 18 of this pdf for a theorem along these lines
https://cs.uwaterloo.ca/journals/JIS/VOL6/Ufnarovski/ufnarov...
But one will not consistently win such a battle. Many people will resist for various reasons, whether it be "stubbornness" or simply feeling like the other person shows no signs of trying to understand what they mean.
I propose that better goals include: (i) understanding what people are saying; (ii) applying the concepts to some productive end. By "productive" I mean some forward progress in an empirical or mathematical sense, whether it be prediction or proof.
So give up the battle. Why? Not because you are wrong. [2] Because "being right" about a definition is rather silly. We're talking about concepts being communicated by language and symbols. The goal is shared understanding of the concepts (which happens inside a brain), not merely enforcing a mapping of brain states to ink on a page (words) or vibrations in a physical medium (sound).
[1]: Whether you win or lose, the distinction between (a: definition) and (b: properties) still exists.
[2]: And not because you are "right" either. You can, at best, be consistent in your definitions and use them in useful ways.
Even better would be a differentiating name, but I realize that’s unlikely.
I recommend rephrasing that as "the definition (part "a" above) of arithmetic derivative is different than calculus definition of derivative."
Do you see? Stating it this way reduces the war of words. Your point is made clear. [1] Then other people can say "Ok, sure, but don't you see how the properties (part "b" above) are the same? And isn't that interesting?"
Think of this another way. Imagine an alternate history where the arithmetic derivative was discovered, named, and socialized first. Then imagine calculus came along later. If so, would calculus be wrong to use the same word, "derivative"? ... I won't answer that question because it is invalid. Better to dissolve the question [2].
My point? Let's try to shift away from historical battles over turf and terminology. Let's find ways to share insight.
[1] Unless your intended point was: "how dare you use the word differently?"
[2] https://www.lesswrong.com/posts/Mc6QcrsbH5NRXbCRX/dissolving...
I woke up, noticed the title & blog (and references), went through the same tortured route and confusion, before stumbling on the fine print, and coming to same “oh, for crying out loud” reaction.
If I were to guess... I'd say you (and many people, including myself, often) are weary of people redefining words in a way that seems wasteful, distortive (such as 'stealing' words that formerly had clear technical meanings), purely commercial, or self-promotional.
For me, at least, the intent of the redefinition matters. But I detect no self-interest or obvious neglect in the case of the arithmetic primes.