Dickman function
Mathematical function
≈ 3 min read
Names in other languages
- FrançaisFonction de Dickman
- SvenskaDickmans funktion
- EnglishDickman function
- РусскийФункция Дикмана
- 中文Dickman函數
- 简体中文Dickman函數
- 繁體中文Dickman函式
- 한국어딕맨 함수
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
. 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 \rho(u) is a continuous function that satisfies the delay differential equation u\rho'(u) + \rho(u-1) = 0\, with initial conditions \rho(u) = 1 for 0 ≤ u ≤ 1. \Psi(N,B) \approx N \rho\left(\frac{\log N}{\log B}\right). 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.
Knuth gives a proof for a narrowed bound: \Psi(x,x^{1/a})=x\rho(a)+(1-\gamma)\rho(a-1)(x/\log x)+O(x/{(\log x)}^2) 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 \Psi(x,y)=xu^{O(-u)} which is related to the estimate \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 \rho(u)\approx u^{-u}.\, A better estimate is \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 e^\xi-1=u\xi.\, A simple upper bound is \rho(x)\le1/x!.
Computation
For each interval [n − 1, n] with n an integer, there is an analytic function \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) + \frac{\pi^2}{12}. with Li 2 the dilogarithm. Other \rho_n 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.
Extension
Friedlander defines a two-dimensional analog \sigma(u,v) of \rho(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 x\sigma(b,a).\, 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 e^{-\gamma} is controlled by the Dickman function Golomb–Dickman constant Poisson-Dirichlet distribution
Text derived from https://en.wikipedia.org/w/index.php?oldid=1372858535 under CC BY-SA 4.0; modifications have been made.