Dickman function

Image:Mplwp Dickman function log.svg.]]

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,{{cite journal |first=K. |last=Dickman |title=On the frequency of numbers containing prime factors of a certain relative magnitude |journal=Arkiv för Matematik, Astronomi och Fysik |volume=22A |issue=10 |year=1930 |pages=1–14 |bibcode=1930ArMAF..22A..10D }} which is not easily available,{{Cite web |title=nt.number theory - Reference request: Dickman, On the frequency of numbers containing prime factors |author=Various |website=MathOverflow |date=2012–2018 |url= https://mathoverflow.net/questions/89362/reference-request-dickman-on-the-frequency-of-numbers-containing-prime-factors}} Discussion: an unsuccessful search for a source of Dickman's paper, and suggestions on several others on the topic. and later studied by the Dutch mathematician Nicolaas Govert de Bruijn.{{cite journal |first=N. G. |last=de Bruijn |url=http://alexandria.tue.nl/repository/freearticles/597499.pdf |title=On the number of positive integers ≤ x and free of prime factors > y |journal=Indagationes Mathematicae |volume=13 |year=1951 |pages=50–60 }}{{cite journal |first=N. G. |last=de Bruijn |url=http://alexandria.tue.nl/repository/freearticles/597534.pdf |title=On the number of positive integers ≤ x and free of prime factors > y, II |journal=Indagationes Mathematicae |volume=28 |year=1966 |pages=239–247 }}

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.

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.{{cite journal |first=V. |last=Ramaswami |url=https://www.ams.org/bull/1949-55-12/S0002-9904-1949-09337-0/S0002-9904-1949-09337-0.pdf |title=On the number of positive integers less than $x$ and free of prime divisors greater than x^c |journal=Bulletin of the American Mathematical Society |volume=55 |issue=12 |year=1949 |pages=1122–1127 |doi= 10.1090/s0002-9904-1949-09337-0 | mr=0031958|doi-access=free }}

Applications

Image:Dickman_prob_factor_size.svg

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{{cite journal |first1=A. |last1=Hildebrand |first2=G. |last2=Tenenbaum |url=http://archive.numdam.org/article/JTNB_1993__5_2_411_0.pdf |title=Integers without large prime factors |journal=Journal de théorie des nombres de Bordeaux |volume=5 |issue=2 |year=1993 |pages=411–484 |doi=10.5802/jtnb.101|doi-access=free }}

: $\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)\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!.$

class="wikitable" style="float:right"
$u$ ! $\rho(u)$
1 \| 1
2 \| 3.0685282{{e
1}}
3 \| 4.8608388{{e
2}}
4 \| 4.9109256{{e
3}}
5 \| 3.5472470{{e
4}}
6 \| 1.9649696{{e
5}}
7 \| 8.7456700{{e
7}}
8 \| 3.2320693{{e
8}}
9 \| 1.0162483{{e
9}}
10 \| 2.7701718{{e
11}}

class="wikitable" style="float:right"

u

! $\rho(u)$

1

| 1

2

| 3.0685282{{e

1}}

3

| 4.8608388{{e

2}}

4

| 4.9109256{{e

3}}

5

| 3.5472470{{e

4}}

6

| 1.9649696{{e

5}}

7

| 8.7456700{{e

7}}

8

| 3.2320693{{e

8}}

9

| 1.0162483{{e

9}}

10

| 2.7701718{{e

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 Li₂ the dilogarithm. Other $\rho_n$ can be calculated using infinite series.{{cite journal |first1=Eric |last1=Bach |first2=René |last2=Peralta |url=http://cr.yp.to/bib/1996/bach-semismooth.pdf |title=Asymptotic Semismoothness Probabilities |journal=Mathematics of Computation |volume=65 |issue=216 |pages=1701–1715 |year=1996 |doi=10.1090/S0025-5718-96-00775-2 |bibcode=1996MaCom..65.1701B |doi-access=free }}

An alternate method is computing lower and upper bounds with the trapezoidal rule;{{cite journal |first1=J. |last1=van de Lune |first2=E. |last2=Wattel |title=On the Numerical Solution of a Differential-Difference Equation Arising in Analytic Number Theory |journal=Mathematics of Computation |volume=23 |issue=106 |year=1969 |pages=417–421 |doi=10.1090/S0025-5718-1969-0247789-3 |doi-access=free }} 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.{{cite journal |first1=George |last1=Marsaglia |first2=Arif |last2=Zaman |first3=John C. W. |last3=Marsaglia |title=Numerical Solution of Some Classical Differential-Difference Equations |journal=Mathematics of Computation |volume=53 |issue=187 |year=1989 |pages=191–201 |doi=10.1090/S0025-5718-1989-0969490-3 |doi-access=free }}

Extension

Friedlander defines a two-dimensional analog $\sigma(u,v)$ of $\rho(u)$ .{{cite journal |first=John B. |last=Friedlander |title=Integers free from large and small primes |journal=Proc. London Math. Soc. |volume=33 |issue=3 |pages=565–576 |year=1976 |doi=10.1112/plms/s3-33.3.565 }} 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).\,$