Difference between revisions of "Dickman-de Bruijn function"

From Number
Jump to: navigation, search
(Definition)
 
Line 14: Line 14:
 
* <math>\rho(u) = 1 - \log u</math> for <math>u \in [1,2]</math>.
 
* <math>\rho(u) = 1 - \log u</math> for <math>u \in [1,2]</math>.
 
* <math>\rho</math> is (strictly) decreasing for <math>u \in [1,\infty)</math>, i.e., <math>\rho'(u) < 0</math> for <math>u \in (1, \infty)</math>.
 
* <math>\rho</math> is (strictly) decreasing for <math>u \in [1,\infty)</math>, i.e., <math>\rho'(u) < 0</math> for <math>u \in (1, \infty)</math>.
* <math>\rho</math> is once differentiable on <math>(1,\infty)</math>. More generally, $\rho</math> is <math>n</math> times differentiable everywhere except at the points <math>\{ 1,2,\dots, n \}</math>.
+
* <math>\rho</math> is once differentiable on <math>(1,\infty)</math>. More generally, <math>\rho</math> is <math>n</math> times differentiable everywhere except at the points <math>\{ 1,2,\dots, n \}</math>.
 
* <math>\rho</math> is infinitely differentiable except at integers.
 
* <math>\rho</math> is infinitely differentiable except at integers.
 
* <math>\lim_{u \to \infty} \rho(u) = 0</math>.
 
* <math>\lim_{u \to \infty} \rho(u) = 0</math>.
  
 
It turns out that the density of numbers with no prime divisor greater than the <math>x^{th}</math> root is given by <math>\rho(x)</math>. Formally, consider, for any <math>N</math>, the fraction of natural numbers <math>n \le N</math> such that all prime divisors of <math>n</math> are at most <math>N^{1/x}</math>. Then, as <math>N \to \infty</math>, this fraction tends to <math>\rho(x)</math>. Thus, this function is crucial to understand the behavior of the [[largest prime divisor]] function and it is important in obtaining [[smooth number|smoothness bounds]].
 
It turns out that the density of numbers with no prime divisor greater than the <math>x^{th}</math> root is given by <math>\rho(x)</math>. Formally, consider, for any <math>N</math>, the fraction of natural numbers <math>n \le N</math> such that all prime divisors of <math>n</math> are at most <math>N^{1/x}</math>. Then, as <math>N \to \infty</math>, this fraction tends to <math>\rho(x)</math>. Thus, this function is crucial to understand the behavior of the [[largest prime divisor]] function and it is important in obtaining [[smooth number|smoothness bounds]].

Latest revision as of 02:40, 9 February 2010

History

The function was first introduced by Dickman with a heuristic argument relating it to smoothness. de Bruijn explored many properties of this function, and Ramaswami gave a formal proof of its relation to the size of the largest prime divisor.

Definition

This function, called Dickman's function or the Dickman-de Bruijn function, is defined as the function satisfying the delay differential equation:

subject to the initial condition for . The function satisfies the following properties:

  • for .
  • for .
  • is (strictly) decreasing for , i.e., for .
  • is once differentiable on . More generally, is times differentiable everywhere except at the points .
  • is infinitely differentiable except at integers.
  • .

It turns out that the density of numbers with no prime divisor greater than the root is given by . Formally, consider, for any , the fraction of natural numbers such that all prime divisors of are at most . Then, as , this fraction tends to . Thus, this function is crucial to understand the behavior of the largest prime divisor function and it is important in obtaining smoothness bounds.