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]

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.

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 (or y-friable) 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

\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:

\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

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

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

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

u\rho(u)
11
23.0685282×10-1
34.8608388×10-2
44.9109256×10-3
53.5472470×10-4
61.9649696×10-5
78.7456700×10-7
83.2320693×10-8
91.0162483×10-9
102.7701718×10-11

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 Li2 the dilogarithm. Other \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

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

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 Dickman's paper is difficult to access; for alternatives, see nt.number theory - Reference request: Dickman, On the frequency of numbers containing prime factors.
  2. ^ de Bruijn, N. G. (1951). "On the number of positive integers ≤ x and free of prime factors > y". Indagationes Mathematicae. 13: 50–60.
  3. ^ de Bruijn, N. G. (1966). "On the number of positive integers ≤ x and free of prime factors > y, II". Indagationes Mathematicae. 28: 239–247.
  4. ^ Ramaswami, V. (1949). "On the number of positive integers less than x and free of prime divisors greater than xc". Bulletin of the American Mathematical Society. 55 (12): 1122–1127. doi:10.1090/s0002-9904-1949-09337-0. MR 0031958.
  5. ^ Kruppa, Alexander (2010). Speeding up Integer Multiplication and Factorization (PhD). Henri Poincaré University. – Work describes algorithms that Kruppa had contributed to GMP-ECM and other factoring programs. Some chapters have been published elsewhere.
  6. ^ Hildebrand, A. & Tenenbaum, G. (1993). "Integers without large prime factors". Journal de théorie des nombres de Bordeaux. 5 (2): 411–484. doi:10.5802/jtnb.101
  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
  8. ^ Bach, Eric & Peralta, René (1996). "Asymptotic Semismoothness Probabilities". Mathematics of Computation. 65 (216): 1701–1715. Bibcode:1996MaCom..65.1701B. doi:10.1090/S0025-5718-96-00775-2
  9. ^ 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
  10. ^ 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

Further reading