Arithmetic Derivative Graph and Thoughts

A recent thread on r/math brought the arithmetic derivative to my attention. It’s a very interesting idea. As I tried to rap my head around it, I wished I had a graph of its actions on some of the natural numbers. So I made one:

The Arithmetic Derivative as a graph on natural numbers

That one was made with neato and sage. It captures the graph structure nicely, but isn’t too legible, so I also made a directed one using dot.

The Arithmetic Derivative as a directed graph on natural numbers

Both contain the first 250 nodes and then fill in 5 steps outwards.

Now for some musings (warning: I’m a number and graph theory ignoramus, so these may be silly and abuse terminology):

  • Not everything converges to zero. 4 and 27 prove this, being their own derivative. There are also a number of graphs that seem to be heading to infinity.
  • I couldn’t find any cyclic subgraphs that weren’t singletons. I’m going to run a deeper search over night, but their rarity is surprising.
  • Anti-derivative is highly non-unique, like the normal one.
  • Numbers that don’t diverge to infinity obviously correspond to analytic functions via power series. For example, 4 corresponds 4exp and 126 corresponds to 126+125x+103x²+x³. What about the ones diverging to infinity? What is their growth rate?
  • We can find numbers that satisfy PDEs quite easily. For example, the wave equation with c=1 is satisfied by 18 and 46 and the diffusion equation with c=1 is satisfied by 57 and 166. What does this mean for numbers? Can this be useful in the study of PDEs?

Finally, some sage code in case you want to mess around with this stuff yourself:


def d(n): #arithmetic derivative
 if n == 0: return 0
 d=0
 for m in factor (n):
 d+=m[1]*n/m[0]
 return d

size=250

initial_nodes=range(size)
nodes=range(size)

for n in initial_nodes:
 N=n
 for m in range(5):
   N=d(N)
   if N not in nodes: nodes.append(N)

f=open("Arithmetic_Derivative_"+repr(size)+".gv",'w')

f.write("digraph Arithmetic_Derivative_"+repr(size)+"{\n")

for n in nodes:
 f.write("\t" + repr(n) + " -> " + repr(d(n))+";\n")

f.write("}")

f.close()

About these ads

Tags: ,

10 Responses to “Arithmetic Derivative Graph and Thoughts”

  1. George G. Says:

    It looks like the idea behind this construction is to transform problems in number theory into something resembling differential equations and then use powerful tools from the theory of differential equations to shed some light on the initial number-theoretic problem, if I understood it correctly.

    I have to say, it must have taken a lot of imagination to come up with something like this, but I’d like to see someone use this approach to actually solve a problem, no matter how simple or banal. Can you, say, prove that there are infinitely many primes, (or something equally easy) using this arithmetic derivative?

    Re: 2 point – you mean, you can’t find numbers N with the property that the m-th derivative of N is equal to N, for m>1? Kind of like sin function?

    Here’s an idea that accured to me after about 3 minutes of thinking (so it’s probably completely wrong) – try proving that such numbers do not exist, because if they did, they would correspond to a function u(x) via your construction in point 4, and u would have a property: u^(m)=u. All such functions are easy to find; prove that their Taylor expansions must mave a negative coefficient somewhere when m>1, and therefore they cant correspont to any number N.
    Like I said – it’s probably flawed on several levels, but this is what first came to my mind.

    Re: 5 point – please, elaborate. It’s not immediately clear to me how do pde-s fit into this, what with several variables, partial derivatives and everything.

    • George G. Says:

      OK, now I see why my proposed “proof” was wrong. It’s because there’s plenty of functions that satisfy U^(m)=U and don’t have any negative coefficients in Taylor expansions. So I was completely wrong. :D

      • christopherolah Says:

        :) But I actually think you may be on to something. That there are order 1 cyclic elements is obvious (eg. 4) — the question is whether there are ones of higher order that are cyclic.

        These need to not just have their nth derivative be themself, but have no earlier ones be so. That is a much stronger requirement.

        Then again, I suppose your could always take a sequence like that of sine and add that of 2exp to force it positive…

        • George G. Says:

          “Then again, I suppose your could always take a sequence like that of sine and add that of 2exp to force it positive…”

          That’s precisely the reason my “proof” failed completely, and the whole approach was probably wrong.

          Maybe there is a simple proof, and I just can’t notice it, but it’s also possible that this is a really hard theorem. I mean, number theory is full of innocent sounding problems that probably wont be solved for another couple of millenia or so, especially when it comes to prime numbers.

    • christopherolah Says:

      > It looks like the idea behind this construction is to transform problems in number theory into something resembling differential equations

      I find things like this fascinating…. Finding something like an isomorphism between disjoint ideas.

      On a similar note, holomorphic functional calculus is a really cool idea.

      > I have to say, it must have taken a lot of imagination to come up with something like this, but I’d like to see someone use this approach to actually solve a problem, no matter how simple or banal. Can you, say, prove that there are infinitely many primes

      Obviously there is a correspondence between the primes and numbers with an arithmetic derivative of one. So if there are an infinite number of numbers with arithmetic derivatives of 0, there are infinitely many primes. But such an argument would be circular, since our definition of the arithmetic derivative was in terms of prime numbers… If one could find an alternate way to describe the arithmetic derivative.

      > Re: 2 point – you mean, you can’t find numbers N with the property that the m-th derivative of N is equal to N, for m>1? Kind of like sin function?

      Yep. Allow me to formalize my terminology by stealing from group theory: = {dⁿ(m) | n ∈ ℕ} is the `group’ (any idea what the proper name for a set under a unary operation is?) generated by m and the order of m is defined as |m| = ||. m is cyclic if ∃n>0, dⁿ(m)=m.

      So exp is cyclic with order 1. exp(-x) is cylic with order 2. sin is cyclic with order four.

      Any p^p where p is prime is cyclic with order one (by power rule). Primes are not cyclic and have order 2. 1 is not cylic and has order 1.

      I checked all natural numbers up to 10⁵ for a 2-cylic one and found nothing.

      (I’ll address your proof in response to your other post.)

      > Re: 5 point – please, elaborate. It’s not immediately clear to me how do pde-s fit into this, what with several variables, partial derivatives and everything.

      Ah. Sorry for not being clear about that. I extended to multivariate calculus like so: Dᵢ(x₀, x₁ .. xᵢ … xⱼ) = Dxᵢ. That may not have been the best idea, actually.

      • George G. Says:

        You see, it’s not difficult to come up with various neat-looking connections like that. For example, when I was in school, I came up with the one that, at the time, looked very beautiful to me – it was a correspondence between irrotational vector fields and integer sequences. It was fascinating, but useless, because it didn’t really help to accomplish anything at all – it was cute, and that’s all it was.

        So the ultimate test of every new generalization/connection/isomorphism is: does it help to accomplish anything?
        Zeta function, for instance, is not only cute, but also incredibly useful. It can be used not only to prove really strong results, but also old, familiar ones, like the fact that there are infinitely many primes. If a method can’t be used to prove something simple, it probably won’t be much help in proving difficult things as well.

        About cycles: yeah, I get the picture.
        The conventional way to express the idea would be to talk about a map, the fixed points of it’s mth iteration, their orbits and the like. If you study fractals, you know this stuff.

        • christopherolah Says:

          What you say is sad, but very reasonable. I suppose the real problem is that it is not immediately obvious whether something will end up being useful. One comes to them seeing something beautiful, and then when one begins to explore them they sort of crumble.

          By the way, I wanted to thank you for taking the time to comment here. Having someone more mathematically competent than myself commenting is intensely valuable.

          • George G. Says:

            Aw, man! You don’t have to thank me for something like that… I rarely meet people with genuine curiosity about math, so naturally I have to comment.

  2. jlopez Says:

    Hi there,

    stumbled by your post by sheer chance and though I might chime in with some points.

    The “kind of a group” structure you are thinking of is actually something called “dynamical system”. What you have is the orbit of the number m under the action of the dynamical system associated to the arithmetic derivative. There are many points that diverge (IIRC every number of the form mp^p with m>1 will “diverge”, for instance every number in which factorization a prime appears with an exponent bigger than itself), many points “converge” to 0 (f.i. every prime) and the only fixed points of the system (numbers such that n’ = n) are the ones of the form p^p with p prime. The existence of cycles is a highly nontrivial problem, there is a conjecture stating that points are either fixed (p^p) divergent, or convergent to 0, i.e there are no cycles of lenght >=2. Many classical problems in number theory can be rewritten in terms of arithmetic derivatives, eg the twin prime conjecture would imply that there are infinitely many composite numbers such that n^(k) = 0 for large enough k, and the Goldbach conjecture that the equation n’ = 2b has a solution for every b>1.
    There is an active area of research about this kind of thing, I remember some recent papers by Buium talking about arithmetical PDE’s. Some of the basics of the theory can be found in the paper by Ufnarovski adn Åhlander:

    http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Ufnarovski/ufnarovski.html

    • christopherolah Says:

      > The “kind of a group” structure you are thinking of is actually something called “dynamical system”…

      Thanks for explaining this. I’ve read about complex dynamics and really ought to have thought apply that language to apply it to this :) I had no idea it could be such a general concept though, or even a sort of structure…

      >The existence of cycles is a highly nontrivial problem, there is a conjecture stating that points are either fixed (p^p) divergent, or convergent to 0, i.e there are no cycles of lenght >=2… Some of the basics of the theory can be found in the paper by Ufnarovski adn Åhlander:
      > http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Ufnarovski/ufnarovski.html

      This is very interesting. I’m reading the paper right now!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 465 other followers

%d bloggers like this: