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 , who defined it in his only mathematical publication. It was later studied by the Dutch mathematician Nicolaas Govert de Bruijn.
Definition The Dickman–de Bruijn function is a continuous function that satisfies the delay differential equation
with initial conditions for 0 ≤ u ≤ 1.
Properties Dickman proved that, when is fixed, we have
where is the number of y-smooth (or y-friable) integers below x. Equivalently, the number of -smooth numbers less than is about
Ramaswami later gave a rigorous proof that for fixed a, was asymptotic to , with the error bound
in big O notation.
Knuth gives a proof for a narrowed bound:
where γ is Euler's constant.
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
which is related to the estimate below.
The Golomb–Dickman constant has an alternate definition in terms of the Dickman–de Bruijn function.
Estimation A first approximation might be A better estimate is
where Ei is the exponential integral and ξ is the positive root of
A simple upper bound is
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 For each interval [n − 1, n] with n an integer, there is an analytic function such that . For 0 ≤ u ≤ 1, . For 1 ≤ u ≤ 2, . For 2 ≤ u ≤ 3,
with Li2 the dilogarithm. Other can be calculated using infinite series.
An alternate method is computing lower and upper bounds with the trapezoidal rule; 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. Values for u ≤ 7 can be usefully computed via numerical integration in ordinary double-precision floating-point. – Work describes algorithms that Kruppa had contributed to GMP-ECM and other factoring programs. Some chapters have been published elsewhere.
Extension Friedlander defines a two-dimensional analog of . This function is used to estimate a function similar to de Bruijn's, but counting the number of y-smooth integers with at most one prime factor greater than z. Then
This class of numbers may be encountered in the two-stage variant of P-1 factoring. However, Kruppa's estimate of the probability of finding a factor by P-1 does not make use of this result.
See also Buchstab function, a function used similarly to estimate the number of rough numbers, whose convergence to is controlled by the Dickman function Golomb–Dickman constant Poisson-Dirichlet distribution
References
Further reading