Dickman-de Bruijn function: Difference between revisions

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 $ρ : [0, \infty) \to R$ satisfying the delay differential equation:

$u ρ^{'} (u) + ρ (u - 1) = 0$

subject to the initial condition $ρ (u) = 1$ for $u \in [0, 1]$ . The function satisfies the following properties:

$ρ (u) = 1$ for $u \in [0, 1]$ .
$ρ (u) = 1 - \log u$ for $u \in [1, 2]$ .
$ρ$ is (strictly) decreasing for $u \in [1, \infty)$ , i.e., $ρ^{'} (u) < 0$ for $u \in (1, \infty)$ .
$ρ$ is once differentiable on $(1, \infty)$ . More generally, $ρ$ is $n$ times differentiable everywhere except at the points ${1, 2, \dots, n}$ .
$ρ$ is infinitely differentiable except at integers.
$lim_{u \to \infty} ρ (u) = 0$ .

It turns out that the density of numbers with no prime divisor greater than the $x^{t h}$ root is given by $ρ (x)$ . Formally, consider, for any $N$ , the fraction of natural numbers $n \leq N$ such that all prime divisors of $n$ are at most $N^{1 / x}$ . Then, as $N \to \infty$ , this fraction tends to $ρ (x)$ . Thus, this function is crucial to understand the behavior of the largest prime divisor function and it is important in obtaining smoothness bounds.

@@ Line 1: / Line 1: @@
+==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==
@@ Line 10: / Line 14: @@
 * <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 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>\lim_{u \to \infty) \rho(u) = 0</math>.
+* <math>\lim_{u \to \infty} \rho(u) = 0</math>.
-==Related facts==
-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>.
+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]].