Dickman-de Bruijn function

In analytic number theory, Dickman's function is a special function used to estimate the proportion of smooth numbers up to a given bound.

Dickman's function is named after actuary Karl Dickman, who defined it in his only mathematical publication. [K. Dickman, "On the frequency of numbers containing prime factors of a certain relative magnitude", "Arkiv för Matematik, Astronomi och Fysik" 22A:10 (1930), pp. 1–14.] Its properties were later studied by the Dutch mathematician Nicolaas Govert de Bruijn; [N.G. de Bruijn, " [http://alexandria.tue.nl/repository/freearticles/597499.pdf On the number of positive integers ≤ "x" and free of prime factors > "y"] ", "Indagationes Mathematicae" 13 (1951), pp. 50-60.] [N.G. de Bruijn, [http://alexandria.tue.nl/repository/freearticles/597534.pdf On the number of positive integers ≤ "x" and free of prime factors > "y", II"] , "Indagationes Mathematicae" 28 (1966), pp. 239–247] , so some sourcesfact|date=August 2008 call it the Dickman-de Bruijn function.

Definition

The Dickman-de Bruijn function $ho(u)$ is a continuous function that satisfies the delay differential equation:$u\; ho\text{'}(u)\; +\; ho(u-1)\; =\; 0,$with initial conditions $ho(u)\; =\; 1$ for 0 ≤ $u$ ≤ 1. Dickman showed heuristically that:$Psi(x,\; x^\{1/a\})sim\; x\; ho(a),$where $Psi(x,y)$ is the number of "y"-smooth integers below "x".

V. Ramaswami of Andhra University later gave a rigorous proof that $Psi(x,x^\{1/a\})$ was asymptotic to $ho(a)$, [V. Ramaswami, " [http://www.ams.org/bull/1949-55-12/S0002-9904-1949-09337-0/S0002-9904-1949-09337-0.pdf On the number of positive integers less than $x$ and free of prime divisors greater than $x^c$] ". "Bulletin of the American Mathematical Society" 55 (1949), pp. 1122–1127.] along with the error bound:$Psi(x,x^\{1/a\})=x\; ho(a)+mathcal\{O\}(x/log\; x)$in big O notation.

Applications

The main purpose of the Dickman-de Bruijn function is to estimate the frequency of smooth numbers at a given size. This can be used to optimize various number-theoretical algorithms, and can be useful of its own right.

It can be shown using $log\; ho$ that [A. Hildebrand and G. Tenenbaum, " [http://archive.numdam.org/article/JTNB_1993__5_2_411_0.pdf Integers without large prime factors] ", "Journal de théorie des nombres de Bordeaux", 5:2 (1993), pp. 411-484.] :$Psi(x,y)=xu^\{O(-u)\}$which is related to the estimate $ho(u)approx\; u^\{-u\}$ below.

The Golomb–Dickman constant has an alternate definition in terms of the Dickman-de Bruijn function.

Estimation

A first approximation might be $ho(u)approx\; u^\{-u\}.,$ A better estimate is:$ho(u)simfrac\{1\}\{xisqrt\{2pi\; xcdotexp(-xxi+operatorname\{Ei\}(xi))$where Ei is the exponential integral and ξ is the positive root of:$e^xi-1=xxi.,$

A simple upper bound is $ho(x)le1/x!.$

Computation

For each interval $[n-1,\; n]$ with "n" an integer, there is an analytic function $ho\_n$ such that $ho\_n(u)=\; ho(u)$. For 0 ≤ $u$ ≤ 1, $ho(u)\; =\; 1$. For 1 ≤ $u$ ≤ 2, $ho(u)\; =\; 1-log\; u$. For 2 ≤ $u$ ≤ 3,:$ho(u)\; =\; 1-(1-log(u-1))log(u)\; +\; operatorname\{Li\}\_2(1\; -\; u)\; +\; frac\{pi^2\}\{12\}$.with Li₂ the dilogarithm. Other $ho\_n$ can be calculated using infinite series.Eric Bach and René Peralta, " [http://cr.yp.to/bib/1996/bach-semismooth.pdf Asymptotic Semismoothness Probabilities] ". "Mathematics of Computation" 65:216 (1996), pp. 1701–1715.]

An alternate method is computing lower and upper bounds with the trapezoidal rule;J. van de Lune and E. Wattel, "On the Numerical Solution of a Differential-Difference Equation Arising in Analytic Number Theory". "Mathematics of Computation" 23:106 (1969), pp. 417–421.] a mesh of progressively finer sizes allows for arbitrary accuracy. For high precision calculations (hundreds of digits), a recursive series expansion about the midpoints of the intervals is superior. [George Marsaglia, Arif Zaman, and John C. W. Marsaglia, "Numerical Solution of Some Classical Differential-Difference Equations". "Mathematics of Computation" 53:187 (1989), pp. 191–201.]

Extension

Bach and Peralta define a two-dimensional analog $sigma(u,v)$ of $ho(u)$. This function is used to estimate a function $Psi(x,y,z)$ similar to de Bruijn's, but counting the number of "y"-smooth integers with at most one prime factor greater than "z". Then:$Psi(x,x^\{1/a\},x^\{1/b\})sim\; xsigma(b,a).,$

References

External links

*