User:Richard Pinch/sandbox-6

Complexity function

of a word $w$

The complexity function of a word $w$ (finite, infinite or bi-infinite) over a finite alphabet $A$ is the function $p_w(n)$ that counts the number of distinct factors (substrings of consecutive symbols) of length $n$ in $w$. More generally, the complexity function of a language, a set of finite words over an alphabet, counts the number of distinct words of given length.

For a string $u$ of length at least $n$ over an alphabet of size $k$ we clearly have $$ 1 \le p_u(n) \le k^n$ $$ the bounds being achieved by the constant word and a disjunctive word (for example, the Champernowne word) respectively. For infinite words $u$, we have $p_u(n)$ bounded if $u$ is ultimately periodic (a finite, possibly empty, sequence followed by a finite cycle). Conversely, if $p_u(n) \le n$ for some $n$, then $u$ is ultimately periodic.

An aperiodic sequence is one which is not ultimately periodic. An aperiodic sequence has strictly increasing complexity function (this is the Morse–Hedlund theorem), so $p_u(n) \ge n+1$.

A set$S$ of finite binary words is balanced if for each $n$ the subset $S_n$ of words of length $n$ has the property that the Hamming weight of the words in $S_n$ takes at most two distinct values. A balanced sequence is one for which the set of factors is balanced. A balanced sequence has complexity function $p(n) \le n+1$.

A Sturmian word over a binary alphabet is one with complexity function $p(n) = n+1$ A sequence is Sturmian if and only if it is balanced and aperiodic. An example is the Fibonacci word. More generally, a Sturmian word over an alphaber of size $k$ is one with complexity $p(n) = n+k-1$. An Arnoux-Rauzy word over a ternary alphabet has complexity $2n+1$: an example is the Tribonacci word.

Let $L$ be a language over an alphabet and define the function $P_L(n)$ of a positive integer $n$ to be the number of different words of length $n$ in $L$ The complexity function of a word is thus the complexity function of the language consisting of the factors of that word.

The complexity function of a language is less constrained than that of a word. For example, it may be bounded but not eventually constant: the complexity function of the regular language $a(bb)^*a$ takes values 3 and 4 on odd and even $n \ge 2$ respectively. There is an analogue of the Morse–Hedlund theorem: if the complexity of $L$ satisfies $p_L(n) \le n$ for some $n$, then $p_L$ is bounded and there is a finite language $F$ such that $$ L \subseteq \{ x y^k z : x,y,z \in F,\ k \in \mathbb{N} \} \ . $$ A polynomial or sparse language is one for which the complexity function $p(n)$ is bounded by a fixed power of $n$. An exponential language is one for which there exists $k>1$ such that there are infinitely many $n$ for which $p(n) > k^n$. Words exist with complexity functions having growth intermediate between polynomial and exponential; however, a regular language is either polynomial or exponential.

The topological entropy of an infinite sequence $u$ is defined by $$ H_{\mathrm{top}}(u) = \lim_{n \rightarrow \infty} \frac{\log p_u(n)}{n \log k} \ . $$

The limit exists as the logarithm of the complexity function is a subadditive function: indeed, $p(m+n) \le p(m) \cdot p(n)$. Every real number between 0 and 1 occurs as the topological entropy of some sequence, which may be taken to be a uniformly recurrent word or even uniquely ergodic.

For $x$ a real number and $b$ an integer $\ge 2$ then the complexity function of $x$ base $b$ is the complexity function $p_{x,b}(n)$ of the sequence of digits of $x$ written in base $b$. If $x$ is an irrational number then $p_{x,b}(n) \ge n+1$; if x is rational then $p_{x,b}(n) \le C$ for some constant $C$ depending on $x$ and $b$. It is conjectured that for algebraic irrational $x$ the complexity is $b^n$ (which would follow if all such numbers were normal) but all that is known in this case is that $p_{x,b}(n)$ grows faster than any linear function of $n$.

The abelian complexity function $p^{\text{ab}}(n)$ similarly counts the number of occurrences of distinct factors of given length $n$, where now we identify factors that differ only by a permutation of the positions. Clearly $p^{\text{ab}}(n) \le p(n)$. The abelian complexity of a Sturmian sequence satisfies $p^{\text{ab}}(n) = 2$.

References

• Allouche, Jean-Paul; Shallit, Jeffrey (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015.
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). Combinatorics on words. Christoffel words and repetitions in words. CRM Monograph Series. 27. Providence, RI: American * Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043.
• Berthé, Valérie; Rigo, Michel, eds. (2010). Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. 135. Cambridge: Cambridge University Press. ISBN 978-0-521-51597-9. Zbl 1197.68006.
• Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. 193. Cambridge: Cambridge University Press. ISBN 978-0-521-11169-0. Zbl pre06066616.
• Cassaigne, Julien; Nicolas, François (2010). "Factor complexity". In Berthé, Valérie; Rigo, Michel. Combinatorics, automata, and number theory. Encyclopedia of Mathematics and its Applications. 135. Cambridge: Cambridge University Press. pp. 163–247. ISBN 978-0-521-51597-9. Zbl 1216.68204.
• Lothaire, M. (2011). Algebraic combinatorics on words. Encyclopedia of Mathematics and Its Applications. 90. With preface by Jean Berstel and Dominique Perrin (Reprint of the 2002 hardback ed.). Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183.
• Pytheas Fogg, N. (2002). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015.

Density of a sequence

Other definitions

Let $A$ be a set of natural numbers and $\Lambda = (\lambda_n)$ a sequence of weights. The density of $A$ with respect to $\Lambda$ is the limit, if it exists $$ d_\Lambda(A) = \lim_{x \rightarrow \infty} \frac{\sum_{n \le x,\,n \in A} \lambda_n}{\sum_{n \le x} \lambda_n} \ . $$ The upper and lower densities $\bar d_\Lambda$,${\underline d}_\Lambda$ are the corresponding upper and lower limits, if they exist.

The natural or asymptotic density is the density with respect to the constant weight $\lambda_n = 1$ for all $n$.

The logarithmic density is the density with respect to weights $\lambda_n = \frac{1}{n}$.

A sequence has analytic density if and only if it has logarithmic density and if so then they are equal.

References

• Tenenbaum, Gérald, "Introduction to analytic and probabilistic number theory." Cambridge Studies in Advanced Mathematics 46 Cambridge University Press (1995) ISBN 0-521-41261-7 Zbl 0831.11001

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:

• 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 $$ \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 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 $\phi(n)$, the Euler totient function of $n$, is $ \frac{6}{\pi^2} n$;
• The average order of $r(n)$, the number of ways of expressing $n$ as a sum of two squares, is $\pi$;
• The Prime Number Theorem is equivalent to the statement that the von Mangoldt function $\Lambda(n)$ has average order 1.

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:

• The Hardy–Ramanujan theorem: the normal order of $\omega(n)$, the number of distinct prime factors of $n$, is $\log\log n$;
• The normal order of $\log d(n))$, where $d(n)$ is the number of divisors function of $n$, is $\log 2 \log\log n$.

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