# Dickman function

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Dickman_function
> Markdown URL: https://mediated.wiki/source/Dickman_function.md
> Source: https://en.wikipedia.org/wiki/Dickman_function
> Source revision: 1317101216
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

In [analytic number theory](/source/Analytic_number_theory), the **Dickman function** or **Dickman–de Bruijn function** *ρ* is a [special function](/source/Special_function) used to estimate the proportion of [smooth numbers](/source/Smooth_number) up to a given bound. It was first studied by actuary [Karl Dickman](/source/Karl_Dickman), who defined it in his only mathematical publication.[1] It was later studied by the Dutch mathematician [Nicolaas Govert de Bruijn](/source/Nicolaas_Govert_de_Bruijn).[2][3]

## Definition

The Dickman–de Bruijn function \rho(u) is a [continuous function](/source/Continuous_function) that satisfies the [delay differential equation](/source/Delay_differential_equation)

- u\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](/source/Smooth_number) (or *y*-[friable](/source/Friable_number)) integers below *x*. Equivalently, the number of B-smooth numbers less than N is about

\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](/source/Error_bound)

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

in [big O notation](/source/Big_O_notation).[4]

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](/source/Euler's_constant).[5]: 98

## 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](/source/Pollard_P-1#How_to_choose_B?) and can be useful of its own right.[5]

It can be shown that[6]

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

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

The [Golomb–Dickman constant](/source/Golomb%E2%80%93Dickman_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[7]

- \rho(u)\sim \frac 1 {\xi\sqrt{2\pi u}} \cdot \exp(-u\xi+\operatorname{Ei}(\xi))

where Ei is the [exponential integral](/source/Exponential_integral) and *ξ* is the positive root of

- e^\xi-1=u\xi.\,

A simple upper bound is \rho(x)\le1/x!.

u \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](/source/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 Li2 the [dilogarithm](/source/Polylogarithm#Dilogarithm). Other \rho_n can be calculated using infinite series.[8]

An alternate method is computing lower and upper bounds with the [trapezoidal rule](/source/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

## 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).\,

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

## See also

- [Buchstab function](/source/Buchstab_function), a function used similarly to estimate the number of [rough numbers](/source/Rough_number), whose convergence to e^{-\gamma} is controlled by the Dickman function
- [Golomb–Dickman constant](/source/Golomb%E2%80%93Dickman_constant)
- [Poisson-Dirichlet distribution](/source/Poisson-Dirichlet_distribution)

## 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](/source/Arkiv_f%C3%B6r_Matematik,_Astronomi_och_Fysik)*. **22A** (10): 1–14. [Bibcode:1930ArMAF..22A..10D](https://ui.adsabs.harvard.edu/abs/1930ArMAF..22A..10D) Dickman's paper is difficult to access; for alternatives, see [nt.number theory - Reference request: Dickman, On the frequency of numbers containing prime factors](https://mathoverflow.net/questions/89362/reference-request-dickman-on-the-frequency-of-numbers-containing-prime-factors).

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

1. de Bruijn, N. G. (1966). ["On the number of positive integers ≤ *x* and free of prime factors > *y*, II"](http://alexandria.tue.nl/repository/freearticles/597534.pdf). *Indagationes Mathematicae*. **28**: 239–247.

1. Ramaswami, V. (1949). ["On the number of positive integers less than x and free of prime divisors greater than *x**c*"](https://www.ams.org/bull/1949-55-12/S0002-9904-1949-09337-0/S0002-9904-1949-09337-0.pdf). *Bulletin of the American Mathematical Society*. **55** (12): 1122–1127. [doi:10.1090/s0002-9904-1949-09337-0](https://doi.org/10.1090/s0002-9904-1949-09337-0). MR 0031958.

1. Kruppa, Alexander (2010). [*Speeding up Integer Multiplication and Factorization*](https://docnum.univ-lorraine.fr/public/SCD_T_2010_0054_KRUPPA.pdf) (PhD). Henri Poincaré University. – Work describes algorithms that Kruppa had contributed to GMP-ECM and other factoring programs. Some chapters have been published elsewhere.

1. Hildebrand, A. & Tenenbaum, G. (1993). ["Integers without large prime factors"](http://archive.numdam.org/article/JTNB_1993__5_2_411_0.pdf). *[Journal de théorie des nombres de Bordeaux](/source/Journal_de_th%C3%A9orie_des_nombres_de_Bordeaux)*. **5** (2): 411–484. [doi:10.5802/jtnb.101](https://doi.org/10.5802/jtnb.101)

1. van de Lune, J. & Wattel, E. (1969). "On the Numerical Solution of a Differential-Difference Equation Arising in Analytic Number Theory". *[Mathematics of Computation](/source/Mathematics_of_Computation)*. **23** (106): 417–421. [doi:10.1090/S0025-5718-1969-0247789-3](https://doi.org/10.1090/S0025-5718-1969-0247789-3)

1. Bach, Eric & Peralta, René (1996). ["Asymptotic Semismoothness Probabilities"](http://cr.yp.to/bib/1996/bach-semismooth.pdf). *Mathematics of Computation*. **65** (216): 1701–1715. [Bibcode:1996MaCom..65.1701B](https://ui.adsabs.harvard.edu/abs/1996MaCom..65.1701B). [doi:10.1090/S0025-5718-96-00775-2](https://doi.org/10.1090/S0025-5718-96-00775-2)

1. 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/S0025-5718-1989-0969490-3)

1. 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](https://doi.org/10.1112/plms/s3-33.3.565)

## Further reading

- Broadhurst, David (2010). "Dickman polylogarithms and their constants". [arXiv:1004.0519](https://arxiv.org/abs/1004.0519)
- Soundararajan, Kannan (2012). "An asymptotic expansion related to the Dickman function". *[Ramanujan Journal](/source/Ramanujan_Journal)*. **29** (1–3): 25–30. [arXiv:1005.3494](https://arxiv.org/abs/1005.3494). [doi:10.1007/s11139-011-9304-3](https://doi.org/10.1007/s11139-011-9304-3). MR 2994087. [S2CID 119564455](https://api.semanticscholar.org/CorpusID:119564455)

---
Adapted from the Wikipedia article [Dickman function](https://en.wikipedia.org/wiki/Dickman_function) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Dickman_function?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.