Dickman function explained

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] which is not easily available,^[2] and later studied by the Dutch mathematician Nicolaas Govert de Bruijn.^{[3] [4]}

Definition

The Dickman–de Bruijn function

\rho(u) is a continuous function that satisfies the delay differential equationu\rho'(u) + \rho(u -1 ) = 0

with initial conditions

\rho(u) = 1 for 0 ≤ u ≤ 1.

Properties

Dickman proved that, when

a is fixed, we have\Psi(x, x ^{1/a} )\sim x\rho(a)

where

\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,

\Psi(x,x ^{1/a} ) was asymptotic to x \rho(a) , with the error bound\Psi(x,x ^{1/a} ) = x\rho(a) + O(x/ log x)

in big O notation.^[5]

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

It can be shown that^[6]

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

which is related to the estimate

\rho(u) ≈ 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

\rho(u) ≈ u ^{-u} . A better estimate is\rho(u)\sim (1)/(\xi\sqrt{ 2 \pi u) } \cdot \exp(-u\xi+\operatorname(\xi))

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

e ^{\xi-1=u\xi.}

A simple upper bound is

\rho(x)\le 1 /x!.

u	\rho(u)
1	1
2	3.0685282
3	4.8608388
4	4.9109256
5	3.5472470
6	1.9649696
7	8.7456700
8	3.2320693
9	1.0162483
10	2.7701718

Computation

\rho _{n} such that \rho _{n(u)=\rho(u)} . For 0 ≤ u ≤ 1, \rho(u) = 1 . For 1 ≤ u ≤ 2, \rho(u) = 1-log u . For 2 ≤ u ≤ 3,\rho(u) = 1- ( 1-log (u -1 )) log (u) + \operatorname{Li} _{2(1} - u) + (\pi ^{2})/(12) .

with Li₂ the dilogarithm. Other

\rho _{n} can be calculated using infinite series.^[7]

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

Extension

Friedlander defines a two-dimensional analog

\sigma(u,v) of \rho(u) .^[10] 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 x\sigma(b,a).

See also

• Buchstab function, a function used similarly to estimate the number of rough numbers, whose convergence to

e ^{-\gamma} is controlled by the Dickman function

• Golomb–Dickman constant

References

1. K. . Dickman . On the frequency of numbers containing prime factors of a certain relative magnitude . . 22A . 10 . 1930 . 1–14 . 1930ArMAF..22A..10D .
2. Web site: nt.number theory - Reference request: Dickman, On the frequency of numbers containing prime factors . Various . MathOverflow . 2012–2018 . Discussion: an unsuccessful search for a source of Dickman's paper, and suggestions on several others on the topic.
3. N. G. . de Bruijn . On the number of positive integers ≤ x and free of prime factors > y . Indagationes Mathematicae . 13 . 1951 . 50–60 .
4. N. G. . de Bruijn . On the number of positive integers ≤ x and free of prime factors > y, II . Indagationes Mathematicae . 28 . 1966 . 239–247 .
5. 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 . 12 . 1949 . 1122–1127 . 10.1090/s0002-9904-1949-09337-0 . 0031958. free .
6. A. . Hildebrand . G. . Tenenbaum . Integers without large prime factors . . 5 . 2 . 1993 . 411–484 . 10.5802/jtnb.101. free .
7. Eric . Bach . René . Peralta . Asymptotic Semismoothness Probabilities . Mathematics of Computation . 65 . 216 . 1701–1715 . 1996 . 10.1090/S0025-5718-96-00775-2 . 1996MaCom..65.1701B . free .
8. J. . van de Lune . E. . Wattel . On the Numerical Solution of a Differential-Difference Equation Arising in Analytic Number Theory . . 23 . 106 . 1969 . 417–421 . 10.1090/S0025-5718-1969-0247789-3 . free .
9. George . Marsaglia . Arif . Zaman . John C. W. . Marsaglia . Numerical Solution of Some Classical Differential-Difference Equations . Mathematics of Computation . 53 . 187 . 1989 . 191–201 . 10.1090/S0025-5718-1989-0969490-3 . free .
10. John B. . Friedlander . Integers free from large and small primes . Proc. London Math. Soc. . 33 . 3 . 565–576 . 1976 . 10.1112/plms/s3-33.3.565 .

Further reading

• David. Broadhurst. Dickman polylogarithms and their constants. 1004.0519. 2010. math-ph.
• Kannan. Soundararajan. An asymptotic expansion related to the Dickman function. 1005.3494. 2012. Ramanujan Journal. 29. 1–3. 10.1007/s11139-011-9304-3. 2994087. 25–30. 119564455.