Dickman function

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] which is not easily available,^[2] and later studied by the Dutch mathematician Nicolaas Govert de Bruijn.^[3]^[4]

Definition

The Dickman–de Bruijn function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(u)} is a continuous function that satisfies the delay differential equation

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u\rho'(u) + \rho(u-1) = 0\,}

with initial conditions Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(u) = 1} for 0 ≤ u ≤ 1.

Properties

Dickman proved that, when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a } is fixed, we have

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

where $\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, $\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.^[5]

Applications

The Dickman–de Bruijn used to calculate the probability that the largest and 2nd largest factor of x is less than x^a

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^[6]

\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^[7]

\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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e^\xi-1=u\xi.\,}

A simple upper bound is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(x)\le1/x!.}

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u}	Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(u)}
1	1
2	3.0685282×10⁻¹
3	4.8608388×10⁻²
4	4.9109256×10⁻³
5	3.5472470×10⁻⁴
6	1.9649696×10⁻⁵
7	8.7456700×10⁻⁷
8	3.2320693×10⁻⁸
9	1.0162483×10⁻⁹
10	2.7701718×10⁻¹¹

Computation

For each interval [n − 1, n] with n an integer, there is an analytic function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_n} such that Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho_n(u)=\rho(u)} . For 0 ≤ u ≤ 1, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(u) = 1} . For 1 ≤ u ≤ 2, $\rho (u)=1-\log u$ . For 2 ≤ u ≤ 3,

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(u) = 1-(1-\log(u-1))\log(u) + \operatorname{Li}_2(1 - u) + \frac{\pi^2}{12}. }

with Li₂ the dilogarithm. Other Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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]

Extension

Friedlander defines a two-dimensional analog Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma(u,v)} of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \rho(u)} .^[10] This function is used to estimate a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \Psi(x,x^{1/a},x^{1/b})\sim x\sigma(b,a).\,}

References

^ 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.
^ 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.
^ de Bruijn, N. G. (1951). "On the number of positive integers ≤ x and free of prime factors > y" (PDF). Indagationes Mathematicae. 13: 50–60.
^ 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.
^ Ramaswami, V. (1949). "On the number of positive integers less than $x$ and free of prime divisors greater than x^c" (PDF). Bulletin of the American Mathematical Society. 55 (12): 1122–1127. doi:10.1090/s0002-9904-1949-09337-0. MR 0031958.
^ 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.
^ ^7.0 ^7.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. 23 (106): 417–421. doi:10.1090/S0025-5718-1969-0247789-3.
^ 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.
^ 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.
^ 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.