Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For a self-map $\varphi:X\longrightarrow X$ of a space $X$, many important notions of entropy are defined through a limit of the form $$\lim_{n\rightarrow\infty}\frac{1}{n}\log a_n,$$ where in each case $a_n$ represents some appropriate quantity (see, for example, this answer to one of my previous questions.) Let $h(\varphi)$ denote a typical entropy that is defined by a limit as above and after Ian's example, assume that $h(\varphi)>0$. Does anyone know if limits of the form \begin{equation} \lim_{n\rightarrow\infty}\ \ \frac{a_n}{\exp(n\cdot h(\varphi))} \end{equation} have been studied anywhere? I will appreciate any possible information about such limits. For example, is there a known case where the limit exists? If so, what is the limit called? etc.

EDIT: As pointed out later by Ian, even if we assume $h(\varphi)>0$ this limit may not exist. I was curios to know if there were instances where the limit is known to exist. Or even better, can one characterize self-maps $\varphi$ for which the limit exists?

share|improve this question
Look at topological entropy. –  Steve Huntsman Jul 30 '11 at 6:01
@Steve: can you elaborate more? What about topological entropy? –  Mahdi Majidi-Zolbanin Jul 30 '11 at 14:46
I guess that the usual definition has the advantage of getting rid of many unrelevant information. So, if you have some precise case in mind, you should probably ask yourself if the limit you propose, assuming it exists, does depend only on the characteristics of your system that you really want it to translate or measure. –  Benoît Kloeckner Jul 30 '11 at 16:04

4 Answers 4

up vote 4 down vote accepted

The limit exists for the first two examples that come to mind, namely topological entropy on the full shift and on certain simple Markov shifts.

If $X \subset \Sigma_d^+ = \{1,2, \dots, d\}^{\mathbb{N}}$ and $\sigma$ is the shift map, then for the topological entropy the quantity $a_n$ denotes the number of words of length $n$ that appear in some sequence $x\in X$. If $X$ is the full shift, then $a_n = d^n$, the entropy is $h = \log d$, and we quickly see that $a_n / e^{nh} = 1$ for all $n$.

Slightly more interesting is when you have a Markov shift, say $X\subset \Sigma_2^+$ determined by the transition matrix $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$.

In this case it's not hard to show that the sequence $a_n$ is actually the Fibonacci sequence, and thus writing $\phi = \frac {1+\sqrt 5}2$ and $\psi = \frac { 1-\sqrt 5}2$, we have $$ a_n = \frac 1{\sqrt 5} (\phi^{n+2} - \psi^{n+2}). $$ Since $|\psi|<1$, this shows that the limit of $a_n / e^{nh}$ exists.

My guess is that a similar argument works for other Markov shifts and shows that the limit exists in those cases, based on obtaining a recurrence relation for $a_n$ and then an exact formula using standard tools for solving such sequences.

All that said, it's not immediately clear what the significance of the limit is, and I don't know of any name for it. For other interesting shifts, such as sofic shifts or shifts with specification, I'd be surprised if the limit always exists.

What is certainly quite important is to have conditions under which the ratio $a_n / e^{nh}$ is bounded away from $0$ and $\infty$. Such estimates are a significant part of arguments on the uniqueness of a measure of maximal entropy (and more generally uniqueness of equilibrium states), in particular the proof that such a measure satisfies a Gibbs property. For example, see Bowen's 1975 paper "Some systems with unique equilibrium states". (Dan Thompson and I also struggled with this not too long ago in Section 5.1 of this paper.)

It turns out that in the general setting, one of those bounds is immediate -- the sequence $a_n$ is submultiplicative, and so it's not hard to show that $a_n \geq e^{nh}$ for all $n$, whatever other properties the shift space has. Getting an upper bound on $a_n / e^{nh}$ is harder and requires some sort of specification property.

share|improve this answer
Hi Vaughn: this comment will be about two months late, but here is why I asked this question: in Noetherian local rings of positive characteristic, commutative algebraist used the Frobenius endomorphism and its iterations to define 'the Hilbert-Kunz Multiplicity' (HKM) which is a mysterious number, difficult to calculate, but a good measure of singularity of the ring. For example, HKM = 1 iff the ring is regular (modulo an assumption about the ring). The limit defining HKM can be interpreted like the limit in my question. However, no one in commutative algebra has looked at it like this, yet. –  Mahdi Majidi-Zolbanin Sep 28 '11 at 14:25

For the topological entropy of a subshift on finitely many symbols, I think that this limit will typically be infinite. Here is an example where this is the case.

Let $\Sigma_2= \{0,1\}^{\mathbb{N}}$ with the infinite product topology and let $T \colon \Sigma_2 \to \Sigma_2$ denote the shift transformation given by $T[(x_i)_{i=1}^\infty]:=(x_{i+1})_{i=1}^\infty$. The map $T$ is a continuous surjective transformation of the compact metrisable space $\Sigma_2$. Let us define a cylinder set of depth $n$ to be a set $Z \subseteq \Sigma_2$ having the form $$Z=\{(x_i) \in \Sigma_2 \colon x_j=z_j \text{ for all }j\text{ such that }1 \leq j \leq n\}$$ for some finite sequence of symbols $z_1,\ldots,z_n \in \{0,1\}$. If $K$ is a nonempty compact subset of $\Sigma_2$ such that $TK \subseteq K$, then the topological entropy of $T$ restricted to $K$ admits the following description: if for each $n \geq 1$ we let $a_n$ be the number of distinct cylinder sets of depth $n$ which have nonempty intersection with $K$, then $h_{top}(K) = \lim_{n \to \infty} \frac{1}{n} \log a_n$. This holds because the cylinder sets form the smallest-growing family of open covers in the sense of the usual definition of topological entropy on a compact space.

Now, let $K \subset \Sigma_2$ be a compact $T$-invariant set of Sturmian words with some specified irrational slope (for the definition and fundamental properties of Sturmian words see e.g. Wikipedia). Such sets exist and satisfy $a_n=n+1$ for all $n \geq 1$. In particular the restriction of the shift map $T$ to $K$ has topological entropy zero and $a_ne^{-nh}=n+1 \to \infty$.

More generally, a little further thought shows that $a_ne^{-nh} \to \infty$ for every nonempty compact minimal invariant subset of $\Sigma_2$ which has zero topological entropy and is not equal to a periodic orbit.

share|improve this answer
@Ian: You are right, when $h=0$ then the denominator is $1$ and if $a_n$ is not bounded, which obviously can happen as your example shows, then the limit will be infinite. Perhaps I should have added the assumption $h>0$ in my question. I am going to edit my question now and add this assumption. –  Mahdi Majidi-Zolbanin Jul 30 '11 at 18:01
It doesn't make any difference if we insist that the topological entropy is nonzero, since we can just take a product with the full shift on two symbols to get $a_n=(n+1)2^n$. –  Ian Morris Jul 30 '11 at 18:06
@Ian: I see! The limit may not always exist. –  Mahdi Majidi-Zolbanin Jul 30 '11 at 18:14

In the case of the geodesic flow acting on the unit tangent bundle of a compact negatively curved manifold, if $a_n$ is the number of closed geodesics of length at most $n$, and $h$ the topological entropy of the geodesic flow, Margulis proved that $a_n$ is equivalent to $\frac{e^{hn}}{hn}$.

The original article has only 2 pages, but his phd thesis was relatively recently published as a book.

share|improve this answer
Dear Barbara: can you provide the reference to Margulis' paper? –  Mahdi Majidi-Zolbanin Feb 4 '12 at 20:20

Let $\phi:\mathbb{P}^N\to\mathbb{P}^N$ be a rational map. The algebraic entropy of $\phi$ is the quantity $$h_{alg}(\phi) = \limsup_{n\to\infty} \frac{1}{n}\log \deg(\phi^n).$$

Suppose now that $\phi$ is defined over $\overline{\mathbb{Q}}$. Since you're using $h$ for entropy, I will let $w:\mathbb{P}^N(\overline{\mathbb{Q}})\to[0,\infty)$ denote the (absolute logarithmic) Weil height. The arithmetic entropy of $(\phi,P)$ is the quantity $$h_{arith}(\phi,P)=\limsup_{n\to\infty} \frac{1}{n}\log w(\phi^n(P)).$$ In the arithmetic setting, the quantity you're asking about is more-or-less what's called the canonical height. In particular, if we assume that $\phi$ is a morphism, then $h_{alg}(\phi)=\log(d)$, and $$\lim_{n\to\infty} \frac{w(\phi^n(P))}{\exp(nh_{alg}(\phi)} = \lim_{n\to\infty} \frac{w(\phi^n(P))}{d^n}$$ exists and is called the $\phi$-canonical height of $P$. (It's usually denoted $\hat{h}_\phi(P)$.) For the case of morphisms, this is all well known, see for example [2]. Algebraic entropy for rational maps is a subject of current research, see for example [1], and arithmetic entropy is defined (and studied for monomial maps) in [3].

  1. Degree-growth of monomial maps. Ergodic Theory Dynam. Systems, 27(5):1375--1397, 2007.
  2. Canonical heights on varieties with morphisms. Compositio Math., 89(2):163-205, 1993.
  3. http://arxiv.org/abs/1111.5664
share|improve this answer
Dear J. Silverman: Thank you for your response. What does the number $\hat{h}_{\phi}(P)$ measure? I know it vanishes at pre-periodic points, but what does a large value of $\hat{h}_{\phi}(P)$ mean, for example? Also, do the following limits have any meaning in arithmetic setting? (I don't know if they exist) $$\lim_{n\rightarrow\infty}\frac{\deg\phi^n}{\exp(n\cdot h_{\mathrm{alg}}(\phi))},\ \ \ \ \ \ \ \ \lim_{n\rightarrow\infty}\frac{w(\phi^n(P))}{\exp(n\cdot h_{\mathrm{arith}}(\phi,P))}.$$ –  Mahdi Majidi-Zolbanin Feb 5 '12 at 23:19

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.