# Dickman function

The Dickman–de Bruijn function ρ(u) plotted on a logarithmic scale. The horizontal axis is the argument u, and the vertical axis is the value of the function. The graph nearly makes a downward line on the logarithmic scale, demonstrating that the logarithm of the function is quasilinear.

In analytic number theory, the Dickman function or Dickman–de Bruijn function ρ is a special function used to estimate the proportion of smooth numbers up to a given bound. It was first studied by actuary Karl Dickman, who defined it in his only mathematical publication,[1] and later studied by the Dutch mathematician Nicolaas Govert de Bruijn.[2][3]

## Definition

The Dickman–de Bruijn function ${\displaystyle \rho (u)}$ is a continuous function that satisfies the delay differential equation

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

with initial conditions ${\displaystyle \rho (u)=1}$ for 0 ≤ u ≤ 1.

## Properties

Dickman proved that, when ${\displaystyle a}$ is fixed, we have

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

where ${\displaystyle \Psi (x,y)}$ is the number of y-smooth (or y-friable) integers below x.

Ramaswami later gave a rigorous proof that for fixed a, ${\displaystyle \Psi (x,x^{1/a})}$ was asymptotic to ${\displaystyle x\rho (a)}$, with the error bound

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

## Applications

The Dickman–de Bruijn used to calculate the probability that the largest and 2nd largest factor of x is less than x^a

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 such as P-1 factoring and can be useful of its own right.

It can be shown using ${\displaystyle \log \rho }$ that[5]

${\displaystyle \Psi (x,y)=xu^{O(-u)}}$

which is related to the estimate ${\displaystyle \rho (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 ${\displaystyle \rho (u)\approx u^{-u}.\,}$ A better estimate is[6]

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

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

${\displaystyle e^{\xi }-1=u\xi .\,}$

A simple upper bound is ${\displaystyle \rho (x)\leq 1/x!.}$

${\displaystyle u}$ ${\displaystyle \rho (u)}$
1 1
2 3.0685282×101
3 4.8608388×102
4 4.9109256×103
5 3.5472470×104
6 1.9649696×105
7 8.7456700×107
8 3.2320693×108
9 1.0162483×109
10 2.7701718×1011

## Computation

For each interval [n − 1, n] with n an integer, there is an analytic function ${\displaystyle \rho _{n}}$ such that ${\displaystyle \rho _{n}(u)=\rho (u)}$. For 0 ≤ u ≤ 1, ${\displaystyle \rho (u)=1}$. For 1 ≤ u ≤ 2, ${\displaystyle \rho (u)=1-\log u}$. For 2 ≤ u ≤ 3,

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

with Li2 the dilogarithm. Other ${\displaystyle \rho _{n}}$ can be calculated using infinite series.[7]

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

## Extension

Friedlander defines a two-dimensional analog ${\displaystyle \sigma (u,v)}$ of ${\displaystyle \rho (u)}$.[9] This function is used to estimate a function ${\displaystyle \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

${\displaystyle \Psi (x,x^{1/a},x^{1/b})\sim x\sigma (b,a).\,}$

## References

1. ^ Dickman, K. (1930). "On the frequency of numbers containing prime factors of a certain relative magnitude". Arkiv för Matematik, Astronomi och Fysik. 22A (10): 1–14.
2. ^ de Bruijn, N. G. (1951). "On the number of positive integers ≤ x and free of prime factors > y" (PDF). Indagationes Mathematicae. 13: 50–60.
3. ^ de Bruijn, N. G. (1966). "On the number of positive integers ≤ x and free of prime factors > y, II" (PDF). Indagationes Mathematicae. 28: 239–247.
4. ^ Ramaswami, V. (1949). "On the number of positive integers less than ${\displaystyle x}$ and free of prime divisors greater than xc" (PDF). Bulletin of the American Mathematical Society. 55 (12): 1122–1127. doi:10.1090/s0002-9904-1949-09337-0. MR 0031958.
5. ^ Hildebrand, A.; Tenenbaum, G. (1993). "Integers without large prime factors" (PDF). Journal de théorie des nombres de Bordeaux. 5 (2): 411–484. doi:10.5802/jtnb.101.
6. ^ a b van de Lune, J.; Wattel, E. (1969). "On the Numerical Solution of a Differential-Difference Equation Arising in Analytic Number Theory". Mathematics of Computation. 23 (106): 417–421. doi:10.1090/S0025-5718-1969-0247789-3.
7. ^ Bach, Eric; Peralta, René (1996). "Asymptotic Semismoothness Probabilities" (PDF). Mathematics of Computation. 65 (216): 1701–1715. doi:10.1090/S0025-5718-96-00775-2.
8. ^ Marsaglia, George; Zaman, Arif; Marsaglia, John C. W. (1989). "Numerical Solution of Some Classical Differential-Difference Equations". Mathematics of Computation. 53 (187): 191–201. doi:10.1090/S0025-5718-1989-0969490-3.
9. ^ Friedlander, John B. (1976). "Integers free from large and small primes". Proc. London Math. Soc. 33 (3): 565–576. doi:10.1112/plms/s3-33.3.565.