Dickman-de Bruijn function

From Wikipedia, the free encyclopedia

$u$	$ρ(u)$
1	1
2	3.0685282×10^-1
3	4.8608388×10^-2
4	4.9109256×10^-3
5	3.5472470×10^-4
6	1.9649696×10^-5
7	8.7456700×10^-7
8	3.2320693×10^-8
9	1.0162483×10^-9
10	2.7701718×10^-11

The Dickman-de Bruijn function $ρ(u)$ satisfies the delay differential equation

$u\rho'(u) + \rho(u-1) = 0\,$

with initial conditions $ρ(u) = 1$ for 0 ≤ $u$ ≤ 1. Dickman showed heuristically that

$\Psi(x, x^{1/a})\sim x\rho(a)\,$

where $Ψ(x, y)$ , the de Bruijn function, counts the number of y-smooth integers below x.

Ramaswami later gave a rigorous proof that $Ψ(x, x 1 / a)$ was asymptotic to $ρ(a)$ ,^[1] along with the error bound

$\Psi(x,x^{1/a})=x\rho(a)+\mathcal{O}(x/\log x)$

in Big O notation.

1 Estimation
2 Computation
3 Expansion
4 References
5 External links

[edit] Estimation

A first approximation might be $\rho(u)\approx u^{-u}.\,$ A better estimate is^[2]

$\rho(u)\sim\frac{1}{\xi\sqrt{2\pi x}}\cdot\exp(-x\xi+\operatorname{Ei}(\xi))$

where Ei is the exponential integral and ξ is the positive root of

$e^\xi-1=x\xi.\,$

A simple upper bound is $\rho(x)\le1/x!$

[edit] Computation

For each interval $[n - 1, n]$ with n an integer, there is an analytic function $ρ n$ such that $ρ n (u) = ρ(u)$ . For 0 ≤ $u$ ≤ 1, $ρ(u) = 1$ . For 1 ≤ $u$ ≤ 2, $ρ(u) = 1 - log u$ . For 2 ≤ $u$ ≤ 3,

$\rho(u) = 1-(1-\log(x-1))\log(x) + \operatorname{Li}_2(1 - x) + \frac{\pi^2}{12}$ .

with Li₂ the dilogarithm. Other $ρ n$ can be found with infinite series.^[3]

An alternate method is computing lower and upper bounds with the trapezoidal rule;^[2] 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.^[4]

[edit] Expansion

Bach and Peralta define a two-dimensional analog $σ(u, v)$ of $ρ(u)$ .^[3] This function is used to estimate a function $Ψ(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 x\sigma(b,a)\,$

[edit] References

^ V. Ramaswami, "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.
^ ^a ^b 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, no. 106 (1969), pp. 417–421.
^ ^a ^b Eric Bach and René Peralta, "Asymptotic Semismoothness Probabilities". Mathematics of Computation 65, no. 216 (1996), pp. 1701–1715.
^ George Marsaglia, Arif Zaman, and John C. W. Marsaglia, "Numerical Solution of Some Classical Differential-Difference Equations". Mathematics of Computation 53, no. 187 (1989), pp. 191–201.