A crash course in subadditivity, part 1

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 $(S, \cdot)$ be a semigroup. A function $f : S \to \mathbb{R}$ is subadditive if:

$f(x \cdot y) \leq f(x) + f(y)$ for every $x, y \in S$ (1)

$\Diamond$

If $S$ is a group, with an identity element $e$ and a multiplicative inverse $x^{-1}$ for every element $x$ , then (1) is equivalent to:

$f(x) \geq f(y) - f(x^{-1} \cdot y)$ for every $x, y \in S$

Usually, we will have $S$ be one of the sets $\mathbb{Z}$ and $\mathbb{R}$ of integers and reals, respectively, or one of the sets $\mathbb{Z}_{+}$ and $\mathbb{R}_{+}$ 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 $H : \mathbb{R} \to \mathbb{R}$ defined by $H(x)=1$ if $x \geq 0$ and $H(x)=0$ if $x<0$ . This function is subadditive, because if $x$ and $y$ 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 $U \subseteq S$ and let $f : S \to \mathbb{R}$ be defined by $f(x)=1$ if $x \in U$ and $f(x)=2$ if $x \not \in U$ . Then $f$ 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 $S=\mathbb{R}$ and $U=\mathbb{Q}$ this shows that a subadditive function can be discontinuous at every point.
Let $A$ be a finite nonempty set and let $A^\ast$ be the free monoid on $A$ , that is, the set of words on $A$ with concatenation as the binary operation and the empty word $\lambda$ as the identity element. The length of a word is a subadditive (actually, additive) function on $A^\ast$ .

If $S$ is a subsemigroup of either $\mathbb{R}$ or $\mathbb{Z}$ , a useful trick is that $f(x)$ is subadditive on $-S$ if and only if $f(-x)$ is subadditive on $S$ . This, for example, allows to “dualize” proofs on $\mathbb{R}_{+}$ to make them work on $\mathbb{R}_{-}$ , the additive semigroup of negative reals.

Fekete’s lemma. Let $f : S \to \mathbb{R}$ be a subadditive function.

If $S=\mathbb{R}_{+}$ or $S=\mathbb{Z}_{+}$ , then $\ell_{+} = \lim_{x \to +\infty} f(x)/x = \inf_{x > 0} f(x)/x$ .
Dually, if $S=\mathbb{R}_{-}$ or $S=\mathbb{Z}_{-}$ , then $\ell_{-} = \lim_{x \to -\infty} f(x)/x = \sup_{x < 0} f(x)/x$ .
Finally, if $S=\mathbb{R}$ or $S=\mathbb{Z}$ , then $\ell_{-} \leq \ell_{+}$ , and both are finite.

Note that $\ell_{+}$ cannot be $+\infty$ , but can be $-\infty$ : for example, $f(x) = -x^2$ is subadditive on $\mathbb{R}_{+}$ and $\lim_{x \to +\infty} f(x)/x = -\infty$ . Dually, $\ell_{-}$ cannot be $-\infty$ , but can be $+\infty$ . Note that $f(x)/x$ itself needs not be subadditive: for example, $f(x)=-x$ is subadditive on $\mathbb{R}_{+}$ , but $f(x)/x=-1$ is not.

Proof of point 1 with $S = \mathbb{Z}_{+}$ : Fix a positive integer $t$ . Every positive integer $x$ large enough can be written in the form $x = qt + r$ with $q$ positive integer and (attention!) $1 \leq r \leq t$ . By subadditivity,

$\dfrac{f(x)}{x} \leq \dfrac{f(qt) + f(r)}{x} \leq \dfrac{q}{x} f(t) + \dfrac{f(r)}{x}$ .

But by construction, $\lim_{x \to \infty} q/x = 1/t$ : since there are no more than $r$ possible values for $f(r)$ , by taking the upper limits we get

$\limsup_{x \to +\infty} \dfrac{f(x)}{x} \leq \dfrac{f(t)}{t}$ .

This holds for every positive integer $t$ , so we can conclude:

$\limsup_{x \to \infty} \dfrac{f(x)}{x} \leq \inf_{x > 0} \dfrac{f(x)}{x} \leq \liminf_{x \to \infty} \dfrac{f(x)}{x}$ .

$\Box$

A key ingredient of the proof is that $f$ is bounded on $\{1, \ldots, t\}$ . The argument can be modified to work on $\mathbb{R}_{+}$ , but requires that $f$ be bounded in every closed and bounded interval of the form $[1,t+1)$ : this is actually true if $f$ 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 $\mathbb{R}_{+}$ or $\mathbb{Z}_{+}$ can go to $+\infty$ for $x \to +\infty$ at most linearly. On the other hand, an everywhere negative subadditive function defined on positive reals or positive integers can go to $-\infty$ for $x \to +\infty$ arbitrarily fast. Indeed, the following holds:

Lemma 1. Let $S$ be either $\mathbb{R}_{+}$ or $\mathbb{Z}_{+}$ and let $f, g : S \to \mathbb{R}$ . If $f$ is negative and subadditive and $g$ is positive and nondecreasing, then $f(x)g(x)$ is subadditive (and negative).

Proof: If $a<0$ and $0 < b \leq c$ , then $ac \leq ab$ . Then the following chain of inequalities hold:

$f(x+y) g(x+y) \leq \left( f(x) + f(y) \right) g(x+y) \leq f(x) g(x) + f(y) g(y)$ .

$\Box$

Hence, if $f(x) = -x$ and $g(x)$ is positive and nondecreasing, then $f(x)g(x)$ is subadditive and $|f(x)g(x)| = \Omega(g(x))$ .

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 $A$ be a finite nonempty set. A subset $X$ of the set $A^\mathbb{Z}$ of bi-infinite words is a (one-dimensional) subshift if there exists a set of forbidden words $\mathcal{F} \subseteq A^\ast$ such that the following holds: for every $x \in A^\mathbb{Z}$ , it is $x \in X$ if and only if for no $i \in \mathbb{Z}$ and $n \in \mathbb{Z}_{+}$ it is $x_i \ldots x_{i+n-1} \in \mathcal{F}$ . The set $\mathcal{L}(X)$ of the words over $A$ which appear in elements of $X$ is called the language of the subshift $X$ . $\Diamond$

Examples of subshifts are:

The full shift $X = A^\mathbb{Z}$ . In this case, $\mathcal{F} = \emptyset$ .
The golden mean shift on the binary alphabet, where $\mathcal{F} = \{ 11 \}$ .

Let $X$ be a subshift on $A$ and let $u$ and $v$ be words on $A$ of length $m$ and $n$ , respectively. If $uv$ is an allowed word for $X$ , then so must be $u$ and $v$ : that is, there cannot be more allowed words of length $m+n$ than juxtapositions of an allowed word of length $m$ and an allowed word of length $n$ . Switching to logarithms, we see that

$f(n) = \log |\mathcal{L}(X) \cap A^n|$

is a subadditive function of the positive integer variable $n$ : Fekete’s lemma then tells us that

$h(X) = \lim_{n \to \infty} \dfrac{\log |\mathcal{L}(X) \cap A^n|}{n}$ (2)

exists. The quantity (2) is called the entropy of the subshift $X$ , and is a measure of the quantity of information it can convey.

(As a funny note, the use of the uncapitalized letter $h$ 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 $H$ used by Ludwig Boltzmann… which, however, was a capitalized $\eta$ .)

Definition 3. A one-dimensional cellular automaton is a triple $\mathcal{A} = \langle Q, r, \delta \rangle$ where $Q$ is a finite nonempty set of states, $r$ is a nonnegative integer radius, and $\delta : Q^{2r+1} \to Q$ is a local update rule. $\Diamond$

A cellular automaton $\mathcal{A} = \langle Q, r, \delta \rangle$ induces a global transition function $G : Q^\mathbb{Z} \to Q^\mathbb{Z}$ by synchronous update:

$G(x)_i = \delta(x_{i-r} \ldots x_{i+r})$ for every $i \in \mathbb{Z}$ (3)

If $G$ is the global transition function of a cellular automaton with set of states $Q$ , then $G \left( Q^\mathbb{Z} \right)$ 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.

Bibliography:

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.

Theory Lunch

Institute of Cybernetics, Tallinn

A crash course in subadditivity, part 1

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply