Arithmetic derivative

Last updated April 17, 2024

In number theory, the Lagarias arithmetic derivative or 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.

Early history

The arithmetic derivative was introduced by Spanish mathematician Josè Mingot Shelly in 1911.^[1]^[2] The arithmetic derivative also appeared in the 1950 Putnam Competition.^[3]

Definition

For natural numbers $n$ , the arithmetic derivative $D (n)$ ^{[note 1]} is defined as follows:

$D (p) = 1$ for any prime $p$ .
$D (mn) = D (m) n + mD (n)$ for any $m,n\in \mathbb {N}$ (Leibniz rule).

Extensions beyond natural numbers

Edward J. Barbeau extended the domain to all integers by showing that the choice $D (- n) = - D (n)$ uniquely extends the domain to the integers and is consistent with the product formula. Barbeau also further extended it to the rational numbers, showing that the familiar quotient rule gives a well-defined derivative on $\mathbb {Q}$ :

D\!\left({\frac {m}{n}}\right)={\frac {D(m)n-mD(n)}{n^{2}}}.

^[4]^[5]

Victor Ufnarovski and Bo Åhlander expanded it to the irrationals that can be written as the product of primes raised to arbitrary rational powers, allowing expressions like $D({\sqrt {3}}\,)$ to be computed. ^[6]

The arithmetic derivative can also be extended to any unique factorization domain (UFD),^[6] such as the Gaussian integers and the Eisenstein integers, and its associated field of fractions. If the UFD is a polynomial ring, then the arithmetic derivative is the same as the derivation over said polynomial ring. For example, the regular derivative is the arithmetic derivative for the rings of univariate real and complex polynomial and rational functions, which can be proven using the fundamental theorem of algebra.

The arithmetic derivative has also been extended to the ring of integers modulo n.^[7]

Elementary properties

The Leibniz rule implies that $D (0) = 0$ (take $m = n = 0$ ) and $D (1) = 0$ (take $m = n = 1$ ).

The power rule is also valid for the arithmetic derivative. For any integers $k$ and $n \geq 0$ :

D(k^{n})=nk^{n-1}D(k).

This allows one to compute the derivative from the prime factorization of an integer, ${\textstyle x=\prod \limits _{p{\text{ prime}}}p^{n_{p}}}$ (in which ${\textstyle n_{p}=\nu _{p}(x)}$ is the p-adic valuation of $x$ ) :

D(x)=\sum \limits _{p{\text{ prime}}}n_{p}\,p^{n_{p}-1}D(p)=\sum _{\stackrel {p{\text{ divide }}x}{p{\text{ prime}}}}n_{p}{\frac {x}{p}}D(p)=x\sum _{\stackrel {p{\text{ divide }}x}{p{\text{ prime}}}}{\frac {n_{p}}{p}}D(p)

.

This shows that if one knows the derivative for all prime numbers, then the derivative is fully known. In facts, the family of arithmetic partial derivative ${\textstyle {\frac {\partial }{\partial p}}}$ relative to the prime number ${\textstyle p}$ , defined by ${\textstyle {\frac {\partial }{\partial p}}(q)=0}$ for all primes ${\textstyle q}$ , except for ${\textstyle q=p}$ for which ${\textstyle {\frac {\partial }{\partial p}}(p)=1}$ is a basis of the space of derivatives. Note that, for this derivative, we have ${\frac {\partial x}{\partial p}}=n_{p}{\frac {x}{p}}$ .

Usually, one takes the derivative such that ${\textstyle D(p)=1}$ for all primes $p$ , so that

D=\sum \limits _{p{\text{ prime}}}{\frac {\partial }{\partial p}}{\text{, and }}D(x)=x\sum \limits _{p{\text{ prime}}}{\frac {n_{p}}{p}}

.

With this derivative, we have for example:

D(60)=D(2^{2}\cdot 3\cdot 5)=60\cdot \left({\frac {2}{2}}+{\frac {1}{3}}+{\frac {1}{5}}\right)=92,

or

D(81)=D(3^{4})=4\cdot 3^{3}\cdot D(3)=4\cdot 27\cdot 1=108.

And the sequence of number derivatives for $x = 0, 1, 2, \dots$ begins (sequence A003415 in the OEIS ):

0,0,1,1,4,1,5,1,12,6,7,1,16,1,9,\ldots

Related functions

The logarithmic derivative $\operatorname {ld} (x)={\frac {D(x)}{x}}=\sum _{\stackrel {p\,\mid \,x}{p{\text{ prime}}}}{\frac {\nu _{p}(x)}{p}}$ is a totally additive function: $\operatorname {ld} (x\cdot y)=\operatorname {ld} (x)+\operatorname {ld} (y).$

The arithmetic partial derivative of $x$ with respect to $p$ is defined as $x_{p}^{\prime }={\frac {\nu _{p}(x)}{p}}x.$ So, the arithmetic derivative of $x$ is given as $D(x)=\sum _{\stackrel {p\,\mid \,x}{p{\text{ prime}}}}x_{p}^{\prime }.$

An arithmetic function $f$ is Leibniz-additive if there is a totally multiplicative function $h_{f}$ such that $f(mn)=f(m)h_{f}(n)+f(n)h_{f}(m)$ for all positive integers $m$ and $n$ . A motivation for this concept is the fact that Leibniz-additive functions are generalizations of the arithmetic derivative $D$ ; namely, $D$ is Leibniz-additive with $h_{D}(n)=n$ .

The function $\delta$ given in Section 3.5 of the book by Sandor and Atanassov is, in fact, exactly the same as the usual arithmetic derivative $D$ .

Inequalities and bounds

E. J. Barbeau examined bounds on the arithmetic derivative^[8] and found that

D(n)\leq {\frac {n\log _{2}n}{2}}

and

D(n)\geq \Omega (n)\,n^{\frac {\Omega (n)-1}{\Omega (n)}}

where $Ω(n)$ , a prime omega function, is the number of prime factors in $n$ . In both bounds above, equality always occurs when $n$ is a power of 2.

Dahl, Olsson and Loiko found the arithmetic derivative of natural numbers is bounded by^[9]

D(n)\leq {\frac {n\log _{p}n}{p}}

where $p$ is the least prime in $n$ and equality holds when $n$ is a power of $p$ .

Alexander Loiko, Jonas Olsson and Niklas Dahl found that it is impossible to find similar bounds for the arithmetic derivative extended to rational numbers by proving that between any two rational numbers there are other rationals with arbitrary large or small derivatives (note that this means that the arithmetic derivative is not a continuous function from $\mathbb {Q}$ to $\mathbb {Q}$ ).

Order of the average

We have

\sum _{n\leq x}{\frac {D(n)}{n}}=T_{0}x+O(\log x\log \log x)

and

\sum _{n\leq x}D(n)=\left({\frac {1}{2}}\right)T_{0}x^{2}+O(x^{1+\delta })

for any δ > 0, where

T_{0}=\sum _{p}{\frac {1}{p(p-1)}}.

Relevance to number theory

Victor Ufnarovski and Bo Åhlander have detailed the function's connection to famous number-theoretic conjectures like the twin prime conjecture, the prime triples conjecture, and Goldbach's conjecture. For example, Goldbach's conjecture would imply, for each $k > 1$ the existence of an $n$ so that $D (n) = 2 k$ . The twin prime conjecture would imply that there are infinitely many $k$ for which $D 2 (k) = 1$ .^[6]

Notes

↑ In this article we use Oliver Heaviside's notation $D (n)$ for the arithmetic derivative of $n$ . There are various other notations possible, such as $n'$ ; a full discussion is available here for general differential operators, of which the arithmetic derivative can be considered one. Heaviside's notation is used here because it highlights the fact that the arithmetic derivative is a function over the integers and yields itself better notation-wise to function iteration $D k$ for second and higher-order arithmetic derivatives.

Related Research Articles

In number theory, an arithmetic, arithmetical, or number-theoretic function is generally any function f(n) whose domain is the positive integers and whose range is a subset of the complex numbers. Hardy & Wright include in their definition the requirement that an arithmetical function "expresses some arithmetical property of n". There is a larger class of number-theoretic functions that do not fit this definition, for example, the prime-counting functions. This article provides links to functions of both classes.

In calculus, the chain rule is a formula that expresses the derivative of the composition of two differentiable functions $f$ and $g$ in terms of the derivatives of $f$ and $g$ . More precisely, if $is the function such that for every x, then the chain rule is, in Lagrange's notation,$

The derivative is a fundamental tool of calculus that quantifies the sensitivity of change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is the slope of the tangent line to the graph of the function at that point. The tangent line is the best linear approximation of the function near that input value. For this reason, the derivative is often described as the instantaneous rate of change, the ratio of the instantaneous change in the dependent variable to that of the independent variable. The process of finding a derivative is called differentiation.

In mathematics, a square-free integer (or squarefree integer) is an integer which is divisible by no square number other than 1. That is, its prime factorization has exactly one factor for each prime that appears in it. For example, 10 = 2 ⋅ 5 is square-free, but 18 = 2 ⋅ 3 ⋅ 3 is not, because 18 is divisible by 9 = 3². The smallest positive square-free numbers are

In number theory, given a prime number $p$ , the $p$ -adic numbers form an extension of the rational numbers which is distinct from the real numbers, though with some similar properties; $p$ -adic numbers can be written in a form similar to decimals, but with digits based on a prime number $p$ rather than ten, and extending to the left rather than to the right.

<span class="mw-page-title-main">Taylor's theorem</span> Approximation of a function by a truncated power series

In calculus, Taylor's theorem gives an approximation of a $-times differentiable function around a given point by a polynomial of degree, called the -th-order Taylor polynomial . For a smooth function, the Taylor polynomial is the truncation at the order of the Taylor series of the function. The first-order Taylor polynomial is the linear approximation of the function, and the second-order Taylor polynomial is often referred to as the quadratic approximation . There are several versions of Taylor's theorem, some giving explicit estimates of the approximation error of the function by its Taylor polynomial.$

<span class="mw-page-title-main">Euler's totient function</span> Number of integers coprime to and not exceeding n

In number theory, Euler's totient function counts the positive integers up to a given integer $n$ that are relatively prime to $n$ . It is written using the Greek letter phi as $or, and may also be called Euler's phi function . In other words, it is the number of integers k in the range 1 \leq k \leq n for which the greatest common divisor gcd(n, k) is equal to 1. The integers k of this form are sometimes referred to as totatives of n .$

A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for structuring the other symbols that occur in a formula. As formulas are entirely constituted with symbols of various types, many symbols are needed for expressing all mathematics.

In number theory, an additive function is an arithmetic function f(n) of the positive integer variable n such that whenever a and b are coprime, the function applied to the product ab is the sum of the values of the function applied to a and b:

<span class="mw-page-title-main">Harmonic number</span> Sum of the first n whole number reciprocals; 1/1 + 1/2 + 1/3 + ... + 1/n

In mathematics, the $n$ -th harmonic number is the sum of the reciprocals of the first $n$ natural numbers:

In mathematics, summation is the addition of a sequence of numbers, called addends or summands; the result is their sum or total. Beside numbers, other types of values can be summed as well: functions, vectors, matrices, polynomials and, in general, elements of any type of mathematical objects on which an operation denoted "+" is defined.

In calculus, the product rule is a formula used to find the derivatives of products of two or more functions. For two functions, it may be stated in Lagrange's notation as

In mathematics and classical mechanics, the Poisson bracket is an important binary operation in Hamiltonian mechanics, playing a central role in Hamilton's equations of motion, which govern the time evolution of a Hamiltonian dynamical system. The Poisson bracket also distinguishes a certain class of coordinate transformations, called canonical transformations, which map canonical coordinate systems into canonical coordinate systems. A "canonical coordinate system" consists of canonical position and momentum variables that satisfy canonical Poisson bracket relations. The set of possible canonical transformations is always very rich. For instance, it is often possible to choose the Hamiltonian itself $as one of the new canonical momentum coordinates.$

In mathematics, the Legendre transformation, first introduced by Adrien-Marie Legendre in 1787 when studying the minimal surface problem, is an involutive transformation on real-valued functions that are convex on a real variable. Specifically, if a real-valued multivariable function is convex on one of its independent real variables, then the Legendre transform with respect to this variable is applicable to the function.

Multi-index notation is a mathematical notation that simplifies formulas used in multivariable calculus, partial differential equations and the theory of distributions, by generalising the concept of an integer index to an ordered tuple of indices.

In mathematics, differential algebra is, broadly speaking, the area of mathematics consisting in the study of differential equations and differential operators as algebraic objects in view of deriving properties of differential equations and operators without computing the solutions, similarly as polynomial algebras are used for the study of algebraic varieties, which are solution sets of systems of polynomial equations. Weyl algebras and Lie algebras may be considered as belonging to differential algebra.

In mathematics, the derivative is a fundamental construction of differential calculus and admits many possible generalizations within the fields of mathematical analysis, combinatorics, algebra, geometry, etc.

This is a summary of differentiation rules, that is, rules for computing the derivative of a function in calculus.

In number theory, the prime omega functions $and count the number of prime factors of a natural number Thereby counts each distinct prime factor, whereas the related function counts the total number of prime factors of honoring their multiplicity. That is, if we have a prime factorization of of the form for distinct primes, then the respective prime omega functions are given by and . These prime factor counting functions have many important number theoretic relations.$

In analytic number theory, a Dirichlet series, or Dirichlet generating function (DGF), of a sequence is a common way of understanding and summing arithmetic functions in a meaningful way. A little known, or at least often forgotten about, way of expressing formulas for arithmetic functions and their summatory functions is to perform an integral transform that inverts the operation of forming the DGF of a sequence. This inversion is analogous to performing an inverse Z-transform to the generating function of a sequence to express formulas for the series coefficients of a given ordinary generating function.

References

↑ Shelly, D. J. M. (1911). "Una cuestión de la teoria de los numeros". Association Esp. Granada: 1–12. JFM 42.0209.02.
↑ Lava, Paolo Pietro; Balzarotti, Giorgio. La derivata aritmetica: Alla scoperta di un nuovo approccio alla teoria dei numeri.
↑ Scholes, John. "10th Putnam 1950".
↑ Barbeau, Edward (1961). "Remarks on an Arithmetic Derivative". Canadian Mathematical Bulletin . 4 (2): 117-122. doi: 10.4153/CMB-1961-013-0 .
↑ Barbeau, Edward (April 1973). "Problem". Canad. Math. Congress Notes. 5 (8): 6-7.
1 2 3 Ufnarovski, Victor; Ahlander, Bo (2003). "How to Differentiate a Number" (PDF). Journal of Integer Sequences. 6 (3).
↑ Krebs, Mike; Emmons, Caleb; Shaheen, Anthony (November 2009). "How to Differentiate an Integer Modulo n". The College Mathematics Journal. 40 (5): 345–353. doi:10.4169/074683409X475661. S2CID 122997343.
↑ Barbeau, E.J. (1961). Remarks on an arithmetic derivative. URL: https://www.cambridge.org/core/services/aop-cambridge-core/content/view/1FD7F09AD3972692FC97BB23A21D0BD8/S0008439500050773a.pdf/remarks_on_an_arithmetic_derivative.pdf
↑ Dahl, N., Olsson, J., Loiko, A. (2011). Investigations on the properties of the arithmetic derivative. On page 4. URL: https://arxiv.org/pdf/1108.4762.pdf

Barbeau, E. J. (1961). "Remarks on an arithmetic derivative". Canadian Mathematical Bulletin . 4 (2): 117–122. doi: 10.4153/CMB-1961-013-0 . Zbl 0101.03702.
Ufnarovski, Victor; Åhlander, Bo (2003). "How to Differentiate a Number". Journal of Integer Sequences . 6. Article 03.3.4. ISSN 1530-7638. Zbl 1142.11305.
Arithmetic Derivative , Planet Math , accessed 04:15, 9 April 2008 (UTC)
L. Westrick (2003). Investigations of the Number Derivative .
Peterson, I. Math Trek: Deriving the Structure of Numbers .
Stay, Michael (2005). "Generalized Number Derivatives". Journal of Integer Sequences . 8. Article 05.1.4. arXiv: math/0508364 . ISSN 1530-7638. Zbl 1065.05019.
Dahl N., Olsson J., Loiko A., Investigation of the properties of the arithmetic derivative .
Balzarotti, Giorgio; Lava, Paolo Pietro (2013). La derivata aritmetica. Alla scoperta di un nuovo approccio alla teoria dei numeri. Milan: Hoepli. ISBN 978-88-203-5864-8.
Sandor, Jozsef; Atanassov, Krassimir (2021). Arithmetic Functions, Section 3.5. Nova Science Publishers.

Koviˇc, Jurij (2012). "The Arithmetic Derivative and Antiderivative" (PDF). Journal of Integer Sequences. 15 (3.8).
Haukkanen, Pentti; Merikoski, Jorma K.; Mattila, Mika; Tossavainen, Timo (2017). "The arithmetic Jacobian matrix and determinant" (PDF). Journal of Integer Sequences . 20. Article 17.9.2. ISSN 1530-7638.
Haukkanen, Pentti; Merikoski, Jorma K.; Tossavainen, Timo (2016). "On Arithmetic Partial Differential Equations" (PDF). Journal of Integer Sequences . 19. ISSN 1530-7638.
Haukkanen, Pentti; Merikoski, Jorma K.; Tossavainen, Timo (2018). "The arithmetic derivative and Leibniz-additive functions". Notes on Number Theory and Discrete Mathematics. 24 (3): 68–76. arXiv: 1803.06849 . doi: 10.7546/nntdm.2018.24.3.68-76 . S2CID 119688466.
Haukkanen, Pentti (2019). "Generalized arithmetic subderivative". Notes on Number Theory and Discrete Mathematics. 25 (2): 1–7. doi: 10.7546/nntdm.2019.25.2.1-7 . S2CID 198468574.
Haukkanen, Pentti; Merikoski, Jorma K.; Tossavainen, Timo (2020). "Arithmetic Subderivatives: p-adic Discontinuity and Continuity". Journal of Integer Sequences . 23. Article 20.7.3. ISSN 1530-7638.
Haukkanen, Pentti; Merikoski, Jorma K.; Tossavainen, Timo (2020). "Asymptotics of partial sums of the Dirichlet series of the arithmetic derivative". Mathematical Communications. 25.
Merikoski, Jorma K.; Haukkanen, Pentti; Tossavainen, Timo (2019). "Arithmetic subderivatives and Leibniz-additive functions" (PDF). Annales Mathematicae et Informaticae. 50.
Merikoski, Jorma K.; Haukkanen, Pentti; Tossavainen, Timo (2021). "Complete additivity, complete multiplicativity, and Leibniz-additivity on rationals" (PDF). Integers. 21.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[notation-4] In this article we use Oliver Heaviside's notation $D (n)$ for the arithmetic derivative of $n$ . There are various other notations possible, such as $n'$ ; a full discussion is available here for general differential operators, of which the arithmetic derivative can be considered one. Heaviside's notation is used here because it highlights the fact that the arithmetic derivative is a function over the integers and yields itself better notation-wise to function iteration $D k$ for second and higher-order arithmetic derivatives.

[1] Shelly, D. J. M. (1911). "Una cuestión de la teoria de los numeros". Association Esp. Granada: 1–12. JFM 42.0209.02.

[2] Lava, Paolo Pietro; Balzarotti, Giorgio. La derivata aritmetica: Alla scoperta di un nuovo approccio alla teoria dei numeri.

[3] Scholes, John. "10th Putnam 1950".

[5] Barbeau, Edward (1961). "Remarks on an Arithmetic Derivative". Canadian Mathematical Bulletin . 4 (2): 117-122. doi: 10.4153/CMB-1961-013-0 .

[6] Barbeau, Edward (April 1973). "Problem". Canad. Math. Congress Notes. 5 (8): 6-7.

[jis2003-7] 1 2 3 Ufnarovski, Victor; Ahlander, Bo (2003). "How to Differentiate a Number" (PDF). Journal of Integer Sequences. 6 (3).

[8] Krebs, Mike; Emmons, Caleb; Shaheen, Anthony (November 2009). "How to Differentiate an Integer Modulo n". The College Mathematics Journal. 40 (5): 345–353. doi:10.4169/074683409X475661. S2CID 122997343.

[9] Barbeau, E.J. (1961). Remarks on an arithmetic derivative. URL: https://www.cambridge.org/core/services/aop-cambridge-core/content/view/1FD7F09AD3972692FC97BB23A21D0BD8/S0008439500050773a.pdf/remarks_on_an_arithmetic_derivative.pdf

[10] Dahl, N., Olsson, J., Loiko, A. (2011). Investigations on the properties of the arithmetic derivative. On page 4. URL: https://arxiv.org/pdf/1108.4762.pdf

[1]

[2]

[3]

[note 1]

[4]

[5]

[6]

[7]

[8]

[9]