Namespaces
Variants
Actions

Difference between revisions of "Dickman function"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (better)
m (tex done)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
The function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300901.png" /> defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300902.png" /> by the initial condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300903.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300904.png" /> and by the delay-differential equation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300905.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300906.png" />. Interest attaches to this function because of its connection to  "smooth"  numbers, i.e. numbers that are the product of many small prime numbers. Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300907.png" /> denote the number of positive integers less than or equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300908.png" /> and free of prime divisors greater than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d1300909.png" />. When <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009010.png" /> is much larger than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009011.png" />, it is a simple matter of inclusion-and-exclusion counting (cf. also [[Inclusion-exclusion formula|Inclusion-exclusion formula]]) to show that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009012.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009013.png" /> denotes a [[Prime number|prime number]]. But the error terms grow rapidly, and the  "main"  term gives the wrong answer in the ranges of greatest interest, including the case when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009014.png" /> is comparable to a fixed fractional power of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009015.png" />. For this case, K. Dickman found that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009016.png" />. If, in place of the restriction <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009017.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009018.png" /> one takes the condition <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009019.png" />, the resulting <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009020.png" /> is approximated by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009021.png" />, where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009022.png" /> is the Bukhstab function, defined by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009023.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009024.png" />, and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009025.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009026.png" />, where for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009027.png" /> the right-hand derivative has to be taken, [[#References|[a1]]]. Unlike <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009028.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009029.png" /> oscillates and tends to a positive limit, equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009030.png" />.
 
  
There are two combinatorial identities linking the Dickman function to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009031.png" />. Early work is based on the Bukhstab identity: With <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009032.png" /> denoting a prime number, for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009033.png" />,
+
The function $\rho(u)$ defined on $(0, \infty)$ by the initial condition $\rho(u) = 1$ for $0 < u \le 1$ and by the [[differential-delay equation]] $u \rho'(u) = -\rho(u-1)$ for $u > 1$. Interest attaches to this function because of its connection to "smooth" numbers, i.e. numbers that are the product of many small prime numbers. Let $\Psi(x,y)$ denote the number of positive integers less than or equal to $x$ and free of prime divisors greater than $y$. When $x$ is much larger than $y$, it is a simple matter of inclusion-and-exclusion counting (cf. also [[Inclusion-exclusion formula|Inclusion-exclusion formula]]) to show that $\Psi(x,y) \approx x \prod_{p \le y} (1-1/p)$, where $p$ denotes a [[Prime number|prime number]]. But the error terms grow rapidly, and the  "main" term gives the wrong answer in the ranges of greatest interest, including the case when $y$ is comparable to a fixed fractional power of $x$. For this case, K. Dickman found that $\lim_{x\to\infty} x^{-1} \Psi(x,x^{1/u}) = \rho(u)$. If, in place of the restriction $p \le y$ for $p|n$ one takes the condition $p > y$, the resulting $\Phi(x,y)$ is approximated by $x\omega(u)/\log y$, where $\omega(u)$ is the [[Buchstab function]], defined by $\omega(u) = 1/u$, $1\le u\le 2$, and $(u\omega(u))' = \omega(u-1)$, $u \ge 2$, where for $u=2$ the right-hand derivative has to be taken, [[#References|[a1]]]. Unlike $\rho$, $\omega$ oscillates and tends to a positive limit, equal to $e^{-\gamma}$.
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009034.png" /></td> </tr></table>
+
There are two combinatorial identities linking the Dickman function to $\Psi(x,y)$. Early work is based on the [[Buchstab identity]]: With $p$ denoting a prime number, for $y < z < x$,
  
The usual heuristic device of replacing a sum over prime numbers by an integral with  "prime density"  <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009035.png" /> and replacing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009036.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009037.png" /> leads to an identity which, when <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009038.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009039.png" />, simplifies to an integral equivalent to the definition of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009040.png" />. N.G. de Bruijn carried this idea to its limits in [[#References|[a2]]], but accuracy suffers when large and comparable estimated quantities must be subtracted. The more recent Hildebrand identity involves only additions and has the further advantage that the second input is the same <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009041.png" /> throughout:
+
$$
 +
\Psi(x,y) = \Psi(x,z) - \sum_{z< p\le y} \Psi\left(\frac xp, p \right).
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009042.png" /></td> </tr></table>
+
The usual heuristic device of replacing a sum over prime numbers by an integral with  "prime density" $1/\log t$ and replacing $\Psi(r,s)$ with $r\rho(\log r/\log s)$ leads to an identity which, when $y=x^{1/u}$ and $z=x^{1/(u-1)}$, simplifies to an integral equivalent to the definition of $\rho(u)$. N.G. de Bruijn carried this idea to its limits in [[#References|[a2]]], but accuracy suffers when large and comparable estimated quantities must be subtracted. The more recent Hildebrand identity involves only additions and has the further advantage that the second input is the same $y$ throughout:
  
Applications require estimates uniform in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009043.png" />; the best known estimate along these lines, due to A. Hildebrand and based on the identity above, is
+
$$
 +
\Psi(x,y) \log x = \int_1^x \Psi(t,y) \frac{dt}{t} + \sum_{\substack{p^m \le x \\ p\le y}} \Psi \left( \frac{x}{p^m}, y\right) \log p.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009044.png" /></td> </tr></table>
+
Applications require estimates uniform in $u$; the best known estimate along these lines, due to A. Hildebrand and based on the identity above, is
  
uniformly in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009045.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009046.png" />. There are similar results for algebraic integers, [[#References|[a3]]].
+
$$
 +
\Psi(x,y) = x \rho(u) \left( 1 + O_\epsilon \left( \frac{\log(u+1)}{\log y} \right)\right)
 +
$$
 +
 
 +
uniformly in $y\ge 2$ and $1\le u\le \exp(\log^{(3/5)-\epsilon} y)$. There are similar results for algebraic integers, [[#References|[a3]]].
  
 
There are also results concerning the number of smooth integers in an interval, and concerning the distribution of smooth integers into congruence classes [[#References|[a4]]], [[#References|[a5]]].
 
There are also results concerning the number of smooth integers in an interval, and concerning the distribution of smooth integers into congruence classes [[#References|[a4]]], [[#References|[a5]]].
  
The Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]) implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009047.png" /> [[#References|[a8]]].
+
The Riemann hypothesis (cf. [[Riemann hypotheses|Riemann hypotheses]]) implies $\Psi(y^u, y) = y^u \rho(u) \exp(O_\epsilon (\log(u+1)/\log y))$ [[#References|[a8]]].
  
The analytical properties of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009048.png" /> are reasonably well understood; calculus, analysis of the Laplace transform, and the saddle-point method are the key tools. The first extensive analysis is due to De Bruijn, and the function <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009049.png" /> is sometimes termed the Dickman–De Bruijn function. One has [[#References|[a10]]]:
+
The analytical properties of $\rho$ are reasonably well understood; calculus, analysis of the Laplace transform, and the saddle-point method are the key tools. The first extensive analysis is due to De Bruijn, and the function $\rho(u)$ is sometimes termed the Dickman–De Bruijn function. One has [[#References|[a10]]]:
  
a) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009050.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009051.png" /> (so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009052.png" /> is positive for all positive <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009053.png" />, and hence, from the definition, decreasing);
+
a) $u\rho(u) = \int_{u-1}^u \rho(v) \, dv$ for $u\ge 1$ (so that $\rho$ is positive for all positive $u$, and hence, from the definition, decreasing);
  
b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009054.png" /> is log-concave, that is, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009055.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009057.png" /> (K. Alladi);
+
b) $\rho(u)$ is log-concave, that is, $\rho(tu+(1-t)v) \ge \rho^t(u)\rho^{1-t}(v)$ for $u,v>0$ and $0\le t\le 1$ (K. Alladi);
  
 
c) The [[Laplace transform|Laplace transform]]
 
c) The [[Laplace transform|Laplace transform]]
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009058.png" /></td> </tr></table>
+
$$
 +
\mathcal{L} \rho(s) := \int_0^\infty e^{-su} \rho(u) \, du
 +
= \frac{1}{s} \exp \left[ -\int_s^\infty t^{-1} e^{-t} \, dt \right]
 +
= \exp [\gamma - \operatorname{Ein}(s)];
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009059.png" /></td> </tr></table>
+
d) $\rho(u) = \exp(-u(\log u + \log \log u - 1 + O(\log \log u/\log u)))$ as $u \to \infty$.
  
d) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009060.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009061.png" />.
+
The Dickman function is one of a parameterized family of related functions $\rho_\tau(u)$, [[#References|[a12]]], and a wider class of similar delay-differential equations has been studied in [[#References|[a7]]]. A quick and simple bit of Mathematica code suffices to calculate $\rho$ to reasonable accuracy in the interval $0<u<8$ using step-size $\epsilon = 10^{-4}$. This code calculates a table of values of $\rho$ at intervals of length $\epsilon$, working back recursively into $(0,2]$:
  
The Dickman function is one of a parameterized family of related functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009062.png" />, [[#References|[a12]]], and a wider class of similar delay-differential equations has been studied in [[#References|[a7]]]. A quick and simple bit of Mathematica code suffices to calculate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009063.png" /> to reasonable accuracy in the interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009064.png" /> using step-size <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009065.png" />. This code calculates a table of values of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009066.png" /> at intervals of length <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009067.png" />, working back recursively into <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009068.png" />:
+
  <table border="0" cellpadding="0" cellspacing="0" style="background-color:black;">  
 +
    <tr>
 +
      <td>
 +
        <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;">  
 +
          <tbody>
 +
            <tr>
 +
              <td colname="1" style="background-color:white;" colspan="1">$\rho[u_-,e_-]:=\rho[u,\epsilon]=$</td>
 +
            </tr>
 +
  <tr>
 +
    <td colname="1" style="background-color:white;" colspan="1">$\text{Module}[\{\square\},$</td>
 +
  </tr>
 +
  <tr>  
 +
    <td colname="1" style="background-color:white;" colspan="1"> $\text{If}[u\le 1, \text{Return}[1]];$</td>
 +
  </tr>
 +
  <tr>  
 +
    <td colname="1" style="background-color:white;" colspan="1"> $\text{If}[u\le 2, , \text{Return}[N[1-\text{Log}[u]]];$ </td>
 +
  </tr>
 +
  <tr>  
 +
    <td colname="1" style="background-color:white;" colspan="1"> $\rho[u-\epsilon, \epsilon] - (\epsilon/2)(\rho[u-1-\epsilon, \epsilon]/(u-\epsilon) + \rho[u-1, \epsilon]/u)$ </td>
 +
  </tr>
 +
  <tr>  
 +
    <td colname="1" style="background-color:white;" colspan="1"> $]$ </td>
 +
  </tr>
 +
          </tbody>
 +
        </table>
 +
      </td>
 +
    </tr>
 +
  </table>
  
<table border="0" cellpadding="0" cellspacing="0" style="background-color:black;"> <tr><td> <table border="0" cellspacing="1" cellpadding="4" style="background-color:black;"> <tbody> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009069.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009070.png" />,</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009071.png" />;</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009072.png" />;</td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009073.png" /></td> </tr> <tr> <td colname="1" style="background-color:white;" colspan="1"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009074.png" /></td> </tr> </tbody> </table>
+
====References====
 
+
<table>
</td></tr> </table>
+
<TR><TD valign="top">[a1]</TD> <TD valign="top">  N.G. de Bruijn,  "On the number of positive integers $\leq x$ and free prime factors $> y$. II" ''Indag. Math.'' , '''28'''  (1966)  pp. 239–247  ''Nederl. Akad. Wetensch. Proc. Ser. A'' , '''69'''  (1966)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  N.G. de Bruijn,  "On the number of uncancelled elements in the sieve of Eratosthenes" ''Indag. Math.'' , '''12'''  (1950)  pp. 247–256  ''Nederl. Akad. Wetensch. Proc.'' , '''53'''  (1950)  pp. 803–812</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Friedlander,  "On the number of ideals free from large prime divisors" ''J. Reine Angew. Math.'' , '''255'''  (1972)  pp. 1–7</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Friedlander,  A. Granville,  "Integers without large prime factors, in short intervals" ''Philos. Trans. Royal Soc.'' , '''345'''  (1993)  pp. 339–348</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Granville,  "On integers, without large prime factors, in arithmetic progressions II" ''Philos. Trans. Royal Soc.'' , '''345'''  (1993)  pp. 349–362</TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top">  A. Hildebrand,  G. Tenenbaum,  "Integers without large prime factors" ''J. Théor. Nombres Bordeaux'' , '''5''' :  2  (1993)  pp. 411–484</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Hildebrand,  G. Tenenbaum,  "On a class of differential-difference equations arising in number theory" ''J. Anal. Math.'' , '''61'''  (1993)  pp. 145–179</TD></TR>
 +
<TR><TD valign="top">[a8]</TD> <TD valign="top">  A. Hildebrand,  "Integers free of large prime factors and the Riemann hypothesis" ''Mathematika'' , '''31''' :  2  (1985)  pp. 258–271</TD></TR>
 +
<TR><TD valign="top">[a9]</TD> <TD valign="top">  S. Hunter,  J. Sorenson,  "Approximating the number of integers free of large prime factors" ''Math. Comput.'' , '''66''' :  220  (1997)  pp. 1729–1741</TD></TR>
 +
<TR><TD valign="top">[a10]</TD> <TD valign="top">  P. Moree,  "Psixyology and Diophantine equations" ''Diss. Univ. Leiden''  (1993)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  E. Saias,  "Sur le nombre des entiers sans grand facteur premier" ''J. Number Theory'' , '''32''' : 1  (1989)  pp. 78–99</TD></TR>
 +
<TR><TD valign="top">[a12]</TD> <TD valign="top">  F.S. Wheeler,  "Two differential-difference equations arising in number theory"  ''Trans. Amer. Math. Soc.'' , '''318''' : 2  (1990)  pp. 491–523</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  D.S. Mitrinović,  J. Sandor,  B. Crstici,  "Handbook of number theory" , Kluwer Acad. Publ.  (1996)  pp. Sect. IV.21</TD></TR>
 +
<TR><TD valign="top">[a14]</TD> <TD valign="top"> K. Dickman,  "On the frequency of numbers containing prime factors of a certain relative magnitude"  ''Ark. Mat., Astron. och Fysik'' , '''22A''' :  10  (1930)  pp. 1–14</TD></TR></table>
  
====References====
+
{{TEX|done}}
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  N.G. de Bruijn,  "On the number of positive integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009075.png" /> and free prime factors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/d/d130/d130090/d13009076.png" />. II"  ''Indag. Math.'' , '''28'''  (1966)  pp. 239–247  ''Nederl. Akad. Wetensch. Proc. Ser. A'' , '''69'''  (1966)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  N.G. de Bruijn,  "On the number of uncancelled elements in the sieve of Eratosthenes"  ''Indag. Math.'' , '''12'''  (1950)  pp. 247–256  ''Nederl. Akad. Wetensch. Proc.'' , '''53'''  (1950)  pp. 803–812</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  J. Friedlander,  "On the number of ideals free from large prime divisors"  ''J. Reine Angew. Math.'' , '''255'''  (1972)  pp. 1–7</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Friedlander,  A. Granville,  "Integers without large prime factors, in short intervals"  ''Philos. Trans. Royal Soc.'' , '''345'''  (1993)  pp. 339–348</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  A. Granville,  "On integers, without large prime factors, in arithmetic progressions II"  ''Philos. Trans. Royal Soc.'' , '''345'''  (1993)  pp. 349–362</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  A. Hildebrand,  G. Tenenbaum,  "Integers without large prime factors"  ''J. Théor. Nombres Bordeaux'' , '''5''' :  2  (1993)  pp. 411–484</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  A. Hildebrand,  G. Tenenbaum,  "On a class of differential-difference equations arising in number theory"  ''J. Anal. Math.'' , '''61'''  (1993)  pp. 145–179</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  A. Hildebrand,  "Integers free of large prime factors and the Riemann hypothesis"  ''Mathematika'' , '''31''' :  2  (1985)  pp. 258–271</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  S. Hunter,  J. Sorenson,  "Approximating the number of integers free of large prime factors"  ''Math. Comput.'' , '''66''' :  220  (1997)  pp. 1729–1741</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  P. Moree,  "Psixyology and Diophantine equations"  ''Diss. Univ. Leiden''  (1993)</TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top">  E. Saias,  "Sur le nombre des entiers sans grand facteur premier"  ''J. Number Theory'' , '''32''' :  1  (1989)  pp. 78–99</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top">  F.S. Wheeler,  "Two differential-difference equations arising in number theory"  ''Trans. Amer. Math. Soc.'' , '''318''' :  2  (1990)  pp. 491–523</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top">  D.S. Mitrinović,  J. Sandor,  B. Crstici,  "Handbook of number theory" , Kluwer Acad. Publ.  (1996)  pp. Sect. IV.21</TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top">  K. Dickman,  "On the frequency of numbers containing prime factors of a certain relative magnitude"  ''Ark. Mat., Astron. och Fysik'' , '''22A''' :  10  (1930)  pp. 1–14</TD></TR></table>
 

Latest revision as of 05:11, 15 February 2024

The function $\rho(u)$ defined on $(0, \infty)$ by the initial condition $\rho(u) = 1$ for $0 < u \le 1$ and by the differential-delay equation $u \rho'(u) = -\rho(u-1)$ for $u > 1$. Interest attaches to this function because of its connection to "smooth" numbers, i.e. numbers that are the product of many small prime numbers. Let $\Psi(x,y)$ denote the number of positive integers less than or equal to $x$ and free of prime divisors greater than $y$. When $x$ is much larger than $y$, it is a simple matter of inclusion-and-exclusion counting (cf. also Inclusion-exclusion formula) to show that $\Psi(x,y) \approx x \prod_{p \le y} (1-1/p)$, where $p$ denotes a prime number. But the error terms grow rapidly, and the "main" term gives the wrong answer in the ranges of greatest interest, including the case when $y$ is comparable to a fixed fractional power of $x$. For this case, K. Dickman found that $\lim_{x\to\infty} x^{-1} \Psi(x,x^{1/u}) = \rho(u)$. If, in place of the restriction $p \le y$ for $p|n$ one takes the condition $p > y$, the resulting $\Phi(x,y)$ is approximated by $x\omega(u)/\log y$, where $\omega(u)$ is the Buchstab function, defined by $\omega(u) = 1/u$, $1\le u\le 2$, and $(u\omega(u))' = \omega(u-1)$, $u \ge 2$, where for $u=2$ the right-hand derivative has to be taken, [a1]. Unlike $\rho$, $\omega$ oscillates and tends to a positive limit, equal to $e^{-\gamma}$.

There are two combinatorial identities linking the Dickman function to $\Psi(x,y)$. Early work is based on the Buchstab identity: With $p$ denoting a prime number, for $y < z < x$,

$$ \Psi(x,y) = \Psi(x,z) - \sum_{z< p\le y} \Psi\left(\frac xp, p \right). $$

The usual heuristic device of replacing a sum over prime numbers by an integral with "prime density" $1/\log t$ and replacing $\Psi(r,s)$ with $r\rho(\log r/\log s)$ leads to an identity which, when $y=x^{1/u}$ and $z=x^{1/(u-1)}$, simplifies to an integral equivalent to the definition of $\rho(u)$. N.G. de Bruijn carried this idea to its limits in [a2], but accuracy suffers when large and comparable estimated quantities must be subtracted. The more recent Hildebrand identity involves only additions and has the further advantage that the second input is the same $y$ throughout:

$$ \Psi(x,y) \log x = \int_1^x \Psi(t,y) \frac{dt}{t} + \sum_{\substack{p^m \le x \\ p\le y}} \Psi \left( \frac{x}{p^m}, y\right) \log p. $$

Applications require estimates uniform in $u$; the best known estimate along these lines, due to A. Hildebrand and based on the identity above, is

$$ \Psi(x,y) = x \rho(u) \left( 1 + O_\epsilon \left( \frac{\log(u+1)}{\log y} \right)\right) $$

uniformly in $y\ge 2$ and $1\le u\le \exp(\log^{(3/5)-\epsilon} y)$. There are similar results for algebraic integers, [a3].

There are also results concerning the number of smooth integers in an interval, and concerning the distribution of smooth integers into congruence classes [a4], [a5].

The Riemann hypothesis (cf. Riemann hypotheses) implies $\Psi(y^u, y) = y^u \rho(u) \exp(O_\epsilon (\log(u+1)/\log y))$ [a8].

The analytical properties of $\rho$ are reasonably well understood; calculus, analysis of the Laplace transform, and the saddle-point method are the key tools. The first extensive analysis is due to De Bruijn, and the function $\rho(u)$ is sometimes termed the Dickman–De Bruijn function. One has [a10]:

a) $u\rho(u) = \int_{u-1}^u \rho(v) \, dv$ for $u\ge 1$ (so that $\rho$ is positive for all positive $u$, and hence, from the definition, decreasing);

b) $\rho(u)$ is log-concave, that is, $\rho(tu+(1-t)v) \ge \rho^t(u)\rho^{1-t}(v)$ for $u,v>0$ and $0\le t\le 1$ (K. Alladi);

c) The Laplace transform

$$ \mathcal{L} \rho(s) := \int_0^\infty e^{-su} \rho(u) \, du = \frac{1}{s} \exp \left[ -\int_s^\infty t^{-1} e^{-t} \, dt \right] = \exp [\gamma - \operatorname{Ein}(s)]; $$

d) $\rho(u) = \exp(-u(\log u + \log \log u - 1 + O(\log \log u/\log u)))$ as $u \to \infty$.

The Dickman function is one of a parameterized family of related functions $\rho_\tau(u)$, [a12], and a wider class of similar delay-differential equations has been studied in [a7]. A quick and simple bit of Mathematica code suffices to calculate $\rho$ to reasonable accuracy in the interval $0<u<8$ using step-size $\epsilon = 10^{-4}$. This code calculates a table of values of $\rho$ at intervals of length $\epsilon$, working back recursively into $(0,2]$:

<tbody> </tbody>
$\rho[u_-,e_-]:=\rho[u,\epsilon]=$
$\text{Module}[\{\square\},$
$\text{If}[u\le 1, \text{Return}[1]];$
$\text{If}[u\le 2, , \text{Return}[N[1-\text{Log}[u]]];$
$\rho[u-\epsilon, \epsilon] - (\epsilon/2)(\rho[u-1-\epsilon, \epsilon]/(u-\epsilon) + \rho[u-1, \epsilon]/u)$
$]$

References

[a1] N.G. de Bruijn, "On the number of positive integers $\leq x$ and free prime factors $> y$. II" Indag. Math. , 28 (1966) pp. 239–247 Nederl. Akad. Wetensch. Proc. Ser. A , 69 (1966)
[a2] N.G. de Bruijn, "On the number of uncancelled elements in the sieve of Eratosthenes" Indag. Math. , 12 (1950) pp. 247–256 Nederl. Akad. Wetensch. Proc. , 53 (1950) pp. 803–812
[a3] J. Friedlander, "On the number of ideals free from large prime divisors" J. Reine Angew. Math. , 255 (1972) pp. 1–7
[a4] J. Friedlander, A. Granville, "Integers without large prime factors, in short intervals" Philos. Trans. Royal Soc. , 345 (1993) pp. 339–348
[a5] A. Granville, "On integers, without large prime factors, in arithmetic progressions II" Philos. Trans. Royal Soc. , 345 (1993) pp. 349–362
[a6] A. Hildebrand, G. Tenenbaum, "Integers without large prime factors" J. Théor. Nombres Bordeaux , 5 : 2 (1993) pp. 411–484
[a7] A. Hildebrand, G. Tenenbaum, "On a class of differential-difference equations arising in number theory" J. Anal. Math. , 61 (1993) pp. 145–179
[a8] A. Hildebrand, "Integers free of large prime factors and the Riemann hypothesis" Mathematika , 31 : 2 (1985) pp. 258–271
[a9] S. Hunter, J. Sorenson, "Approximating the number of integers free of large prime factors" Math. Comput. , 66 : 220 (1997) pp. 1729–1741
[a10] P. Moree, "Psixyology and Diophantine equations" Diss. Univ. Leiden (1993)
[a11] E. Saias, "Sur le nombre des entiers sans grand facteur premier" J. Number Theory , 32 : 1 (1989) pp. 78–99
[a12] F.S. Wheeler, "Two differential-difference equations arising in number theory" Trans. Amer. Math. Soc. , 318 : 2 (1990) pp. 491–523
[a13] D.S. Mitrinović, J. Sandor, B. Crstici, "Handbook of number theory" , Kluwer Acad. Publ. (1996) pp. Sect. IV.21
[a14] K. Dickman, "On the frequency of numbers containing prime factors of a certain relative magnitude" Ark. Mat., Astron. och Fysik , 22A : 10 (1930) pp. 1–14
How to Cite This Entry:
Dickman function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Dickman_function&oldid=39999
This article was adapted from an original article by D. Hensley (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article