strictly de-creasing function

Dickman-de Bruijn function

In analytic number theory, Dickman's function is a special function used to estimate the proportion of smooth numbers up to a given bound.

Dickman's function is named after actuary Karl Dickman, who defined it in his only mathematical publication. Its properties were later studied by the Dutch mathematician Nicolaas Govert de Bruijn;, so some sources call it the Dickman-de Bruijn function.

Definition

The Dickman-de Bruijn function rho(u) is a continuous function that satisfies the delay differential equation
urho'(u) + rho(u-1) = 0,
with initial conditions rho(u) = 1 for 0 ≤ u ≤ 1. Dickman showed heuristically that
Psi(x, x^{1/a})sim xrho(a),
where Psi(x,y) is the number of y-smooth integers below x.

V. Ramaswami of Andhra University later gave a rigorous proof that Psi(x,x^{1/a}) was asymptotic to rho(a), along with the error bound

Psi(x,x^{1/a})=xrho(a)+mathcal{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, and can be useful of its own right.

It can be shown using logrho that

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
rho(u)simfrac{1}{xisqrt{2pi x}}cdotexp(-xxi+operatorname{Ei}(xi))
where Ei is the exponential integral and ξ is the positive root of
e^xi-1=xxi.,

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

u rho(u)
1 1
2 3.0685282
3 4.8608388
4 4.9109256
5 3.5472470
6 1.9649696
7 8.7456700
8 3.2320693
9 1.0162483
10 2.7701718

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.

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

Bach and Peralta define a two-dimensional analog sigma(u,v) of rho(u). 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 xsigma(b,a).,

References

External links

Search another word or see strictly de-creasing functionon Dictionary | Thesaurus |Spanish
Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature