Namespaces
Variants
Actions

Difference between revisions of "User:Richard Pinch/sandbox-6"

From Encyclopedia of Mathematics
Jump to: navigation, search
(New draft: Asymptotics of arithmetic functions)
(simplify, add on rates of growth)
Line 6: Line 6:
 
''asymptotics of number-theoretical functions''
 
''asymptotics of number-theoretical functions''
  
Approximate representations of arithmetic functions (functions defined for all natural number values of the argument) by means of comparatively simple expressions with arbitrary small error terms. More precisely, for an arithmetic function $f(x)$ there exists an asymptotic if one has an asymptotic indentity
+
Approximate representations of arithmetic functions (functions defined for all natural number values of the argument) by means of comparatively simple expressions with arbitrary small error terms.  
  
$$f(x)=\phi(x)+R(x),$$
+
An initial question is to ask for a function with the same rate of growth as the given function.  Given an arithmetic function $f(x)$ we say that $f$ has rate of growth, or is asymptotic to, a given function $\phi$ if
 +
$$
 +
\lim_{x\to\infty}\frac{f(x)}{\phi(x)}=1 \ .
 +
$$
 +
A short notation is: $f(x)\sim\phi(x)$ (cf. [[Asymptotic formula]]).
  
where $\phi(x)$ is the approximating function, and $R(x)$ is the error term, about which one knows in general only that
+
Examples:
 +
* The [[Prime number theorem]]: $\pi(x)$, the number of primes less than $x$ is asymptotic to $\frac{x}{\log x}$.
  
$$\lim_{x\to\infty}\frac{R(x)}{\phi(x)}=0.$$
+
More precisely, for an arithmetic function $f(x)$ there exists an asymptotic if one has an asymptotic identity
 +
$$
 +
f(x)=\phi(x)+R(x)\,,
 +
$$
 +
where $\phi(x)$ is the approximating function or main term, and $R(x)$ is the error term, about which one knows in general only that
 +
$$
 +
\lim_{x\to\infty}\frac{R(x)}{\phi(x)}=0 \ .
 +
$$
 +
A short notation is: $f(x)=\phi(x)+o(\phi(x))$ or $f(x) = (1+o(1))\phi(x)$.
  
A short notation is: $f(x)=\phi(x)+o(\phi(x))$ or $f(x)\sim\phi(x)$ (cf. [[Asymptotic formula|Asymptotic formula]]).
+
Examples:
 +
* The [[Prime number theorem]] in a more precise form: $\pi(x) = (1+o(1)) \mathop{Li}(x)$ where $\mathop{Li}$ is the [[logarithmic integral]] function.
  
 
Finding asymptotics of arithmetic functions is one of the most important problems in analytic number theory. This is explained by the fact that most arithmetic functions with interesting arithmetical properties display extreme irregularity in their changes as the argument increases. If one considers instead of an arithmetic function $f(x)$ its average value $(\sum_{n\leq x}f(n))/x$ ($n$ a natural number), then the  "irregularity"  of $f(x)$ is smoothed out. Hence, a typical problem for an arithmetic function is that of obtaining an asymptotic for its average value function. For example, the average value of the function $\tau(n)$, giving the [[number of divisors]] of $n$, is equal to
 
Finding asymptotics of arithmetic functions is one of the most important problems in analytic number theory. This is explained by the fact that most arithmetic functions with interesting arithmetical properties display extreme irregularity in their changes as the argument increases. If one considers instead of an arithmetic function $f(x)$ its average value $(\sum_{n\leq x}f(n))/x$ ($n$ a natural number), then the  "irregularity"  of $f(x)$ is smoothed out. Hence, a typical problem for an arithmetic function is that of obtaining an asymptotic for its average value function. For example, the average value of the function $\tau(n)$, giving the [[number of divisors]] of $n$, is equal to
Line 25: Line 39:
 
Asymptotics of arithmetic functions play an important a role in additive problems (cf. [[Additive number theory|Additive number theory]]). For many of them there is no known direct proof of the existence of decompositions of a number into terms of a given form. However, as soon as one has an asymptotic for the number of decompositions of the type one is looking for, one can deduce that the required decomposition exists for all sufficiently large numbers $n$.
 
Asymptotics of arithmetic functions play an important a role in additive problems (cf. [[Additive number theory|Additive number theory]]). For many of them there is no known direct proof of the existence of decompositions of a number into terms of a given form. However, as soon as one has an asymptotic for the number of decompositions of the type one is looking for, one can deduce that the required decomposition exists for all sufficiently large numbers $n$.
  
==Average order of an arithmetic function==
+
The ''average order'' and ''normal order'' of arithemetic functions refer to some simpler or better-understood function which have comparable asymptotic behaviour.  It is conventional to assume that the approximating function $g$ is [[Continuous function|continuous]] and [[Monotone function|monotone]].
Some simpler or better-understood function which takes the same values "on average" as an [[arithmetic function]].
+
 
 +
 
 +
The ''average order'' of an arithmetic function is a function which has the same average.
  
 
Let $f$, $g$ be functions on the [[natural number]]s.  We say that $f$ has average order $g$ if the [[asymptotic equality]]
 
Let $f$, $g$ be functions on the [[natural number]]s.  We say that $f$ has average order $g$ if the [[asymptotic equality]]
Line 34: Line 50:
 
holds as $x$ tends to infinity.
 
holds as $x$ tends to infinity.
  
It is conventional to assume that the approximating function $g$ is [[Continuous function|continuous]] and [[Monotone function|monotone]].
 
  
===Examples===
+
Examples:
 
* The average order of $d(n)$, the [[number of divisors]] of $n$, is $\log n$;
 
* The average order of $d(n)$, the [[number of divisors]] of $n$, is $\log n$;
 
* The average order of $\sigma(n)$, the [[sum of divisors]] of $n$, is $ \frac{\pi^2}{6} n$;
 
* The average order of $\sigma(n)$, the [[sum of divisors]] of $n$, is $ \frac{\pi^2}{6} n$;
Line 43: Line 58:
 
* The [[Prime number theorem|Prime Number Theorem]] is equivalent to the statement that the [[Mangoldt function|von Mangoldt function]] $\Lambda(n)$ has average order 1.
 
* The [[Prime number theorem|Prime Number Theorem]] is equivalent to the statement that the [[Mangoldt function|von Mangoldt function]] $\Lambda(n)$ has average order 1.
  
===References===
 
* G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. ISBN 0-19-921986-5
 
* Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics '''46'''. Cambridge University Press. ISBN 0-521-41261-7
 
  
  
==Normal order of an arithmetic function==
+
The ''normal order'' of an arithmetic function is a function which "usually" takes the same or closely approximate values.
A function, perhaps simpler or better-understood, which "usually" takes the same or closely approximate values as a given [[arithmetic function]].
 
 
 
  
 
Let $f$ be a function on the [[natural number]]s.  We say that the ''normal order'' of $f$ is $g$ if for every $\epsilon > 0$, the inequalities
 
Let $f$ be a function on the [[natural number]]s.  We say that the ''normal order'' of $f$ is $g$ if for every $\epsilon > 0$, the inequalities
Line 58: Line 68:
 
hold for ''[[almost all]]'' $n$: that is, the proportion of $n < x$ for which this does not hold tends to 0 as $x$ tends to infinity.
 
hold for ''[[almost all]]'' $n$: that is, the proportion of $n < x$ for which this does not hold tends to 0 as $x$ tends to infinity.
  
It is conventional to assume that the approximating function $g$ is [[Continuous function|continuous]] and [[Monotone function|monotone]].
+
Examples:
 
 
===Examples===
 
 
* The [[Hardy–Ramanujan theorem]]: the normal order of $\omega(n)$, the number of distinct [[prime factor]]s of $n$, is $\log\log n$;
 
* The [[Hardy–Ramanujan theorem]]: the normal order of $\omega(n)$, the number of distinct [[prime factor]]s of $n$, is $\log\log n$;
 
* The normal order of $\log d(n))$, where $d(n)$  is the [[number of divisors|number of divisors function]] of $n$, is $\log 2 \log\log n$.
 
* The normal order of $\log d(n))$, where $d(n)$  is the [[number of divisors|number of divisors function]] of $n$, is $\log 2 \log\log n$.
Line 66: Line 74:
 
===References===
 
===References===
 
* G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92
 
* G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92
* G.H. Hardy; E.M. Wright; An Introduction to the Theory of Numbers, Oxford University Press (2008), pp. 473. ISBN 0-19-921986-5
+
* G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. ISBN 0-19-921986-5  
* Gérald Tenenbaum; Introduction to Analytic and Probabilistic Number Theory, ser. Cambridge studies in advanced mathematics '''46''' , Cambridge University Press (1995), pp. 299-324. ISBN 0-521-41261-7
+
* Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics '''46'''. Cambridge University Press. ISBN 0-521-41261-7

Revision as of 06:33, 11 September 2016

Asymptotics of arithmetic functions

asymptotics of number-theoretical functions

Approximate representations of arithmetic functions (functions defined for all natural number values of the argument) by means of comparatively simple expressions with arbitrary small error terms.

An initial question is to ask for a function with the same rate of growth as the given function. Given an arithmetic function $f(x)$ we say that $f$ has rate of growth, or is asymptotic to, a given function $\phi$ if $$ \lim_{x\to\infty}\frac{f(x)}{\phi(x)}=1 \ . $$ A short notation is: $f(x)\sim\phi(x)$ (cf. Asymptotic formula).

Examples:

  • The Prime number theorem: $\pi(x)$, the number of primes less than $x$ is asymptotic to $\frac{x}{\log x}$.

More precisely, for an arithmetic function $f(x)$ there exists an asymptotic if one has an asymptotic identity $$ f(x)=\phi(x)+R(x)\,, $$ where $\phi(x)$ is the approximating function or main term, and $R(x)$ is the error term, about which one knows in general only that $$ \lim_{x\to\infty}\frac{R(x)}{\phi(x)}=0 \ . $$ A short notation is: $f(x)=\phi(x)+o(\phi(x))$ or $f(x) = (1+o(1))\phi(x)$.

Examples:

Finding asymptotics of arithmetic functions is one of the most important problems in analytic number theory. This is explained by the fact that most arithmetic functions with interesting arithmetical properties display extreme irregularity in their changes as the argument increases. If one considers instead of an arithmetic function $f(x)$ its average value $(\sum_{n\leq x}f(n))/x$ ($n$ a natural number), then the "irregularity" of $f(x)$ is smoothed out. Hence, a typical problem for an arithmetic function is that of obtaining an asymptotic for its average value function. For example, the average value of the function $\tau(n)$, giving the number of divisors of $n$, is equal to $$ \frac1n\sum_{m\leq n}\tau(m)\sim\ln n. $$ (cf. Divisor_problems#Dirichlet's_divisor_problem). The problem that arises here, of the best possible bound for the error term in the asymptotic identity, is still unsolved (1984) for many functions, in particular for the function $\tau(x)$ (cf. Analytic number theory).

Asymptotics of arithmetic functions play an important a role in additive problems (cf. Additive number theory). For many of them there is no known direct proof of the existence of decompositions of a number into terms of a given form. However, as soon as one has an asymptotic for the number of decompositions of the type one is looking for, one can deduce that the required decomposition exists for all sufficiently large numbers $n$.

The average order and normal order of arithemetic functions refer to some simpler or better-understood function which have comparable asymptotic behaviour. It is conventional to assume that the approximating function $g$ is continuous and monotone.


The average order of an arithmetic function is a function which has the same average.

Let $f$, $g$ be functions on the natural numbers. We say that $f$ has average order $g$ if the asymptotic equality $$ \sum_{n \le x} f(n) \sim \sum_{n \le x} g(n) $$ holds as $x$ tends to infinity.


Examples:


The normal order of an arithmetic function is a function which "usually" takes the same or closely approximate values.

Let $f$ be a function on the natural numbers. We say that the normal order of $f$ is $g$ if for every $\epsilon > 0$, the inequalities $$ (1-\epsilon) g(n) \le f(n) \le (1+\epsilon) g(n) $$ hold for almost all $n$: that is, the proportion of $n < x$ for which this does not hold tends to 0 as $x$ tends to infinity.

Examples:

References

  • G.H. Hardy; S. Ramanujan; The normal number of prime factors of a number, Quart. J. Math., 48 (1917), pp. 76–92
  • G.H. Hardy; E.M. Wright (2008). An Introduction to the Theory of Numbers (6th ed.). Oxford University Press. ISBN 0-19-921986-5
  • Gérald Tenenbaum (1995). Introduction to Analytic and Probabilistic Number Theory. Cambridge studies in advanced mathematics 46. Cambridge University Press. ISBN 0-521-41261-7
How to Cite This Entry:
Richard Pinch/sandbox-6. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Richard_Pinch/sandbox-6&oldid=39081