Dickman function

From Wikipedia, the free encyclopedia

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] It was later studied by the Dutch mathematician Nicolaas Govert de Bruijn.^{[2] [3]}

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

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

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

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

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

where ${\displaystyle \Psi (x,y)}${\displaystyle \Psi (x,y)} is the number of y-smooth (or y-friable) integers below x. Equivalently, the number of ${\displaystyle B}${\displaystyle B}-smooth numbers less than ${\displaystyle N}${\displaystyle N} is about $${\displaystyle \Psi (N,B)\approx N\rho \left({\frac {\log N}{\log B}}\right).}$${\displaystyle \Psi (N,B)\approx N\rho \left({\frac {\log N}{\log B}}\right).}

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

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

in big O notation.^[4]

Knuth gives a proof for a narrowed bound:

${\displaystyle \Psi (x,x^{1/a})=x\rho (a)+(1-\gamma )\rho (a-1)(x/\log x)+O(x/{(\log x)}^{2})}${\displaystyle \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.^{[5] : 98}

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.^[5]

It can be shown that^[6]

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

which is related to the estimate ${\displaystyle \rho (u)\approx u^{-u}}${\displaystyle \rho (u)\approx u^{-u}} below.

The Golomb–Dickman constant has an alternate definition in terms of the Dickman–de Bruijn function.

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

${\displaystyle \rho (u)\sim {\frac {1}{\xi {\sqrt {2\pi u}}}}\cdot \exp(-u\xi +\operatorname {Ei} (\xi ))}${\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 .,円}${\displaystyle e^{\xi }-1=u\xi .,円}

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

${\displaystyle u}${\displaystyle u}	${\displaystyle \rho (u)}${\displaystyle \rho (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

For each interval [n − 1, n] with n an integer, there is an analytic function ${\displaystyle \rho _{n}}${\displaystyle \rho _{n}} such that ${\displaystyle \rho _{n}(u)=\rho (u)}${\displaystyle \rho _{n}(u)=\rho (u)}. For 0 ≤ u ≤ 1, ${\displaystyle \rho (u)=1}${\displaystyle \rho (u)=1}. For 1 ≤ u ≤ 2, ${\displaystyle \rho (u)=1-\log u}${\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}}.}${\displaystyle \rho (u)=1-(1-\log(u-1))\log(u)+\operatorname {Li} _{2}(1-u)+{\frac {\pi ^{2}}{12}}.}

with Li₂ the dilogarithm. Other ${\displaystyle \rho _{n}}${\displaystyle \rho _{n}} can be calculated using infinite series.^[8]

An alternate method is computing lower and upper bounds with the trapezoidal rule;^[7] 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] Values for u ≤ 7 can be usefully computed via numerical integration in ordinary double-precision floating-point.^{[5] : 99}

Friedlander defines a two-dimensional analog ${\displaystyle \sigma (u,v)}${\displaystyle \sigma (u,v)} of ${\displaystyle \rho (u)}${\displaystyle \rho (u)}.^[10] This function is used to estimate a function ${\displaystyle \Psi (x,y,z)}${\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).,円}${\displaystyle \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.^{[5] : 100}

• Buchstab function, a function used similarly to estimate the number of rough numbers, whose convergence to ${\displaystyle e^{-\gamma }}${\displaystyle e^{-\gamma }} is controlled by the Dickman function
• Golomb–Dickman constant
• Poisson-Dirichlet distribution

• Broadhurst, David (2010). "Dickman polylogarithms and their constants". arXiv:1004.0519 [math-ph].
• Soundararajan, Kannan (2012). "An asymptotic expansion related to the Dickman function". Ramanujan Journal . 29 (1–3): 25–30. arXiv:1005.3494 . doi:10.1007/s11139-011-9304-3. MR 2994087. S2CID 119564455.
• Weisstein, Eric W. "Dickman function". MathWorld .

Retrieved from "https://en.wikipedia.org/w/index.php?title=Dickman_function&oldid=1317101216"

Categories:

• Analytic number theory
• Special functions

Hidden categories:

• Articles with short description
• Short description matches Wikidata