One of the first notion I was taught about subshifts is the topological entropy: intuitively, in a subshift \(X \subseteq \mathcal{A}^{\Z^d}\), the topological entropy counts the asymptotic growth rate of the number of patterns that appear in the configurations \(x \in X\). More formally, the topological entropy of \(X\) is defined as: \[ h(X) = \lim_{n \to +\infty} \frac{\log N_X(n)}{n^d},\] where \(N_X(n)\) is the number of patterns of size \(\llbracket 0,n \rrbracket^d\) that appear in \(X\).
The perceptive reader may notice that the topological entropy is defined as a limit, and wonder why it is well-defined. Assuming that $d=1$, the answer is straightforward: the function \(n \mapsto N_X(n)\) is submultiplicative (indeed, the map \(w \in \mathcal{A}^{n+m} \mapsto w|_{\llbracket 0,n-1 \rrbracket} \cdot w|_{\llbracket n,n+m-1 \rrbracket} \in \mathcal{A}^n \times \mathcal{A}^m\) is injective), and we conclude by the classical subadditive lemma:
Let \((a_n)_{n \in \N}\) be a subadditive sequence of real numbers (i.e. \(a_{n+m} \leq a_{n} + a_{m}\) for \(n,m \in \N\)). Then: \[ \frac{a_n}{n} \xrightarrow[n \to +\infty]{} \inf_{k \in \N} \frac{a_k}{k}.\]
(Here is its Wikipedia page). The classical proof (see here) is a very cool exercise: to prove that the limit superior is smaller than any \(a_k/k\), one uses the euclidean division of any \(n\) by \(k\) and applies subadditivity (so that \( a_{kq+r} \leq q\cdot a_k + a_r\)).
In higher dimension, the existence of topological entropy becomes messier. One could use the Ornstein-Weiss lemma to prove that the limit exists (and that, in fact, it is independent on the choice of the Følner sequence: taking the limit over any growing shape, instead of hypercubes, leads to the same value \(h(X)\)). Yet, in order to prove the existence of the topological entropy on \(\Z^d\) with basic combinatorics (without involving theorems whose statements include the words “amenable groups”), I always thought that I had, one way or another, to rely on the subadditive lemma above1.
Multivariate subadditive lemma
Let me provide some context for the rest of the story. One of my many passions in life is looking at entropies2: if you have a sequence that roughly behaves like \(2^{x \cdot n^2}\), I want to know what \(x\) is3 (and call it an entropy while I’m at it!). In particular, when working with Léo Paviet-Salomon and Pascal Vanier on extender entropies (my latest favorite entropy4), we had a rather inelegant way of proving their existence.
The article was submitted5, a state articles often evolve into once written. When the reviews came back this week, one reviewer had a very simple question: why did we not use a multivariate version of the subadditive lemma (e.g. [Capobianco, 2010])? Essentially, the statement is the following: for any multivariate function \( f : \N^d \to \R \) that is subadditive in each of its variables, the function \(f(x_1,\dots,x_d)/(x_1 \cdots x_d)\) admits a limit when the \(x_i\)’s grow to infinity, and this limit does not depend on the chosen sequence of hyperrectangles. The proof is essentially the same as the classical subadditive lemma: you apply the euclidean division on each variable, and then hope for the best.
So, why did we not use the perfect statement that we needed in our paper, with its perfectly natural proof? Well, it is because I had never heard about it before, that is why! In fact, here is my main take-home message: if you work on subshifts6, the subadditive lemma has a multivariate version and it is amazingly useful! 😁
Still learning
I only have one question left before wrapping up… How did I manage to never hear about this before?! It is quite something: I have been working on subshifts for years, I thought that by now I would have learned most of the basic folklore that you sometimes realize everybody knows (except you, of course, that is the point!). And yet, here I am, learning about this lemma many years after I think I should have first heard of it.
I am not even angry, nor frustrated: I am very thankful to the anonymous reviewer, and quite amazed that it still happens today. If I find a job and manage to keep doing math for the next forty-or-so years, will I still be discovering theorems older than me that would have been useful many years prior? This is a fascinating question!
Yet, being fascinated is all nice and fun but I have a thesis to write7. Antonin out!
- ↩
Which is a bit tricky, because we need to prove that the function \(\log N_X(n)/n^{d-1}\) is subadditive, i.e. the function \(N_X(n)^{1/n^{d-1}}\) is submultiplicative.
- ↩
Said no one ever! 😂
- ↩
(∗ Taking an old TV advertising voice 📺 ∗) You can learn all about it in Computability of extender sets in multidimensional subshifts arXiv:2401.07549! 🤡
- ↩
Actually, it has been submitted way too many times: but alas, such is the academic life!
- ↩
Given that I mostly share this website with mathematicians that are either actual or potential collaborators, this definitely has a quite high probability!
- ↩
Writing a thesis harder than I thought it would be, despite having some experience writing theses and papers. Maybe I should have started earlier (instead of developing my own LaTeX class over the summer). On the positive side, let me tell you: it looks amazing ✨!