Today, the 1st of March 2018, I gave what ended up being the first of a series of Theory Lunch talks about subadditive functions. The idea is to give an introduction to the subject, following Hille’s and Lind and Marcus’s textbooks, and stating an important theorem by the Hungarian mathematician Mihály Fekete; then, discuss some extensions to the case of many variables and their implications in the theory of cellular automata, referring to two of my papers from 2008, one of them with Tommaso Toffoli and Patrizia Mentrasti.
Let’s start from the beginning:
Definition 1. Let be a semigroup. A function is subadditive if:
for every (1)
If is a group, with an identity element and a multiplicative inverse for every element , then (1) is equivalent to:
Usually, we will have be one of the sets and of integers and reals, respectively, or one of the sets and of positive integers and positive reals, respectively. All these sets will be considered as semigroups with respect to addition.
Examples of subadditive functions are:
- The Heaviside function defined by if and if . This function is subadditive, because if and are both negative, then the left-hand side of (1) is 0, and if one of them is nonnegative, then the right-hand side is either 1 or 2.
- Let and let be defined by if and if . Then is subadditive, because the left-hand side of (1) is either 1 or 2, and the right-hand side is either 2, 3, or 4. For and this shows that a subadditive function can be discontinuous at every point.
- Let be a finite nonempty set and let be the free monoid on , that is, the set of words on with concatenation as the binary operation and the empty word as the identity element. The length of a word is a subadditive (actually, additive) function on .
If is a subsemigroup of either or , a useful trick is that is subadditive on if and only if is subadditive on . This, for example, allows to “dualize” proofs on to make them work on , the additive semigroup of negative reals.
Fekete’s lemma. Let be a subadditive function.
- If or , then .
- Dually, if or , then .
- Finally, if or , then , and both are finite.
Note that cannot be , but can be : for example, is subadditive on and . Dually, cannot be , but can be . Note that itself needs not be subadditive: for example, is subadditive on , but is not.
Proof of point 1 with : Fix a positive integer . Every positive integer large enough can be written in the form with positive integer and (attention!) . By subadditivity,
But by construction, : since there are no more than possible values for , by taking the upper limits we get
This holds for every positive integer , so we can conclude:
A key ingredient of the proof is that is bounded on . The argument can be modified to work on , but requires that be bounded in every closed and bounded interval of the form : this is actually true if is subadditive, but proving this fact would go beyond the scope of our talks.
An immediate consequence of Fekete’s lemma is that, as it was intuitively true from the definition, a subadditive function defined on or can go to for at most linearly. On the other hand, an everywhere negative subadditive function defined on positive reals or positive integers can go to for arbitrarily fast. Indeed, the following holds:
Lemma 1. Let be either or and let . If is negative and subadditive and is positive and nondecreasing, then is subadditive (and negative).
Proof: If and , then . Then the following chain of inequalities hold:
Hence, if and is positive and nondecreasing, then is subadditive and .
To see an application of Fekete’s lemma in the context of the theory of dynamical system, we introduce the notions of subshift and of cellular automaton. We will first do so in dimension 1, then expand to arbitrary dimension in later talks.
Definition 2. Let be a finite nonempty set. A subset of the set of bi-infinite words is a (one-dimensional) subshift if there exists a set of forbidden words such that the following holds: for every , it is if and only if for no and it is . The set of the words over which appear in elements of is called the language of the subshift .
Examples of subshifts are:
- The full shift . In this case, .
- The golden mean shift on the binary alphabet, where .
Let be a subshift on and let and be words on of length and , respectively. If is an allowed word for , then so must be and : that is, there cannot be more allowed words of length than juxtapositions of an allowed word of length and an allowed word of length . Switching to logarithms, we see that
is a subadditive function of the positive integer variable : Fekete’s lemma then tells us that
exists. The quantity (2) is called the entropy of the subshift , and is a measure of the quantity of information it can convey.
(As a funny note, the use of the uncapitalized letter to indicate entropy apparently originates from Claude Shannon, after John von Neumann suggested that he called “entropy” a similar information-theoretical quantity. Shannon decided to uncapitalize the letter used by Ludwig Boltzmann… which, however, was a capitalized .)
Definition 3. A one-dimensional cellular automaton is a triple where is a finite nonempty set of states, is a nonnegative integer radius, and is a local update rule.
A cellular automaton induces a global transition function by synchronous update:
for every (3)
If is the global transition function of a cellular automaton with set of states , then is a subshift. Not every subshift can be obtained this way: those that can, belong to the special class of sofic shifts, a term suggested by Benjamin Weiss coming from the Hebrew word for “finite”.
In the upcoming talk (or talks) we will examine the case of several variables, and correspondingly, subshifts and cellular automata in higher dimension. In particular, we will discuss a generalization of Fekete’s lemma to arbitrarily many positive integer variables.
- Silvio Capobianco. Multidimensional cellular automata and generalization of Fekete’s lemma. Discrete Mathematics and Theoretical Computer Science 10 (2008), 95–104.
- Einar Hille. Functional Analysis and Semigroups. American Mathematical Society, 1948.
- Douglas Lind and Brian Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press 1995.
- Tommaso Toffoli, Silvio Capobianco, and Patrizia Mentrasti. When—and how—can a cellular automaton be rewritten as a lattice gas? Theoretical Computer Science 403 (2008), 71–88.