- 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] and later studied by the Dutch mathematician Nicolaas Govert de Bruijn.[2][3]
Contents
Definition
The Dickman-de Bruijn function ρ(u) is a continuous function that satisfies the delay differential equation
with initial conditions ρ(u) = 1 for 0 ≤ u ≤ 1. Dickman showed heuristically that
where Ψ(x,y) is the number of y-smooth integers below x.
V. Ramaswami of Andhra University later gave a rigorous proof that Ψ(x,x1 / a) was asymptotic to xρ(a), with the error bound
- Ψ(x,x1 / a) = xρ(a) + O(x / log x)
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, and can be useful of its own right.
It can be shown using log ρ that[5]
- Ψ(x,y) = xuO( − u)
which is related to the estimate below.
The Golomb–Dickman constant has an alternate definition in terms of the Dickman–de Bruijn function.
Estimation
A first approximation might be A better estimate is[6]
where Ei is the exponential integral and ξ is the positive root of
A simple upper bound is
u ρ(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 such that ρn(u) = ρ(u). For 0 ≤ u ≤ 1, ρ(u) = 1. For 1 ≤ u ≤ 2, ρ(u) = 1 − log u. For 2 ≤ u ≤ 3,
- .
with Li2 the dilogarithm. Other ρn can be calculated using infinite series.[7]
An alternate method is computing lower and upper bounds with the trapezoidal rule;[6] 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.[8]
Extension
Bach and Peralta define a two-dimensional analog σ(u,v) of ρ(u).[7] This function is used to estimate a function Ψ(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
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.
- ^ de Bruijn, N. G. (1951). "On the number of positive integers ≤ x and free of prime factors > y". Indagationes Mathematicae 13: 50–60. http://alexandria.tue.nl/repository/freearticles/597499.pdf.
- ^ de Bruijn, N. G. (1966). "On the number of positive integers ≤ x and free of prime factors > y, II". Indagationes Mathematicae 28: 239–247. http://alexandria.tue.nl/repository/freearticles/597534.pdf.
- ^ 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: 1122–1127. http://www.ams.org/bull/1949-55-12/S0002-9904-1949-09337-0/S0002-9904-1949-09337-0.pdf.
- ^ Hildebrand, A.; Tenenbaum, G. (1993). "Integers without large prime factors". Journal de théorie des nombres de Bordeaux 5 (2): 411–484. http://archive.numdam.org/article/JTNB_1993__5_2_411_0.pdf.
- ^ a b 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.
- ^ a b Bach, Eric; Peralta, René (1996). "Asymptotic Semismoothness Probabilities". Mathematics of Computation 65 (216): 1701–1715. doi:10.1090/S0025-5718-96-00775-2. http://cr.yp.to/bib/1996/bach-semismooth.pdf.
- ^ 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.
External links
- Broadhurst, David (2010). "Dickman polylogarithms and their constants". arXiv:1004.0519.
- Soundararajan, K. (2010). "An asymptotic expansion related to the Dickman function". arXiv:1005.3494.
- Weisstein, Eric W., "Dickman function" from MathWorld.
Categories:
Wikimedia Foundation. 2010.