• Images
• Videos
• Documents
• Books
• Articles

Definition

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

u ρ ′ ( u ) + ρ ( u − 1 ) = 0 {\displaystyle u\rho '(u)+\rho (u-1)=0\,}

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

Properties

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

Ψ ( x , x 1 / a ) ∼ x ρ ( a ) {\displaystyle \Psi (x,x^{1/a})\sim x\rho (a)\,}

where Ψ ( x , y ) {\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, Ψ ( x , x 1 / a ) {\displaystyle \Psi (x,x^{1/a})} was asymptotic to x ρ ( a ) {\displaystyle x\rho (a)} , with the error bound

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

in big O notation.⁵

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⁶

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

which is related to the estimate ρ ( u ) ≈ 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.

Estimation

A first approximation might be ρ ( u ) ≈ u − u . {\displaystyle \rho (u)\approx u^{-u}.\,} A better estimate is⁷

ρ ( u ) ∼ 1 ξ 2 π u ⋅ exp ⁡ ( − u ξ + Ei ⁡ ( ξ ) ) {\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

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

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

u {\displaystyle u}	ρ ( 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

Computation

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

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

with Li2 the dilogarithm. Other ρ n {\displaystyle \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.¹⁰

Extension

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

Ψ ( x , x 1 / a , x 1 / b ) ∼ x σ ( b , a ) . {\displaystyle \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 − γ {\displaystyle e^{-\gamma }} is controlled by the Dickman function
• Golomb–Dickman constant
• Poisson-Dirichlet distribution

Further reading

• 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.

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. Bibcode:1930ArMAF..22A..10D. /wiki/Arkiv_f%C3%B6r_Matematik,_Astronomi_och_Fysik ↩

2. Various (2012–2018). "nt.number theory - Reference request: Dickman, On the frequency of numbers containing prime factors". MathOverflow. Discussion: an unsuccessful search for a source of Dickman's paper, and suggestions on several others on the topic. https://mathoverflow.net/questions/89362/reference-request-dickman-on-the-frequency-of-numbers-containing-prime-factors ↩

3. de Bruijn, N. G. (1951). "On the number of positive integers ≤ x and free of prime factors > y" (PDF). Indagationes Mathematicae. 13: 50–60. http://alexandria.tue.nl/repository/freearticles/597499.pdf ↩

4. 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. http://alexandria.tue.nl/repository/freearticles/597534.pdf ↩

5. Ramaswami, V. (1949). "On the number of positive integers less than x {\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. https://www.ams.org/bull/1949-55-12/S0002-9904-1949-09337-0/S0002-9904-1949-09337-0.pdf ↩

6. 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. http://archive.numdam.org/article/JTNB_1993__5_2_411_0.pdf ↩

7. 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. https://doi.org/10.1090%2FS0025-5718-1969-0247789-3 ↩

8. Bach, Eric; Peralta, René (1996). "Asymptotic Semismoothness Probabilities" (PDF). Mathematics of Computation. 65 (216): 1701–1715. Bibcode:1996MaCom..65.1701B. doi:10.1090/S0025-5718-96-00775-2. http://cr.yp.to/bib/1996/bach-semismooth.pdf ↩

9. 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. https://doi.org/10.1090%2FS0025-5718-1969-0247789-3 ↩

10. 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. https://doi.org/10.1090%2FS0025-5718-1989-0969490-3 ↩

11. 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. /wiki/Doi_(identifier) ↩