# Existence of a limit associated to an almost subadditive sequence

I want to prove that a sequence lives in a specific interval; I did prove that lives in a bigger interval, but not in the one I want.

Let $a_n$ a sequence such that for any n,m
$$a_n + a_m -1 < a_{n+m} < a_n + a_m +1$$ Prove that the sequence $(a_n) / n$ converges ( to $L$) and then prove that $$a_n \in \left(nL - 1,nL+1 \right)$$

I proved everything, but I proved that lies in $$\left( nL - 2,nL+2 \right)$$ I can´t bound it more.

-
Put $b_n = a_{n} + 1$ then $b_{n+m} \leq b_{n} + b_{m}$ and thus $$L = \lim_{n \to \infty} \frac{a_{n} + 1}{n} = \inf_{n} \frac{a_{n} + 1}{n}. \qquad \text{Moreover, } \frac{a_{n} + 1}{n} \geq L.$$ Similarly with $c_n = 1-a_n$ with $\dfrac{c_n}{n}$ converging to $-L$ and thus $$\frac{1-a_n}{n} \geq -L.$$ This is a classic from Pólya-Szegő, Exer. 98/99, by the way. (they attribute it to Fekete). – t.b. Aug 14 '11 at 20:20
Oh, sorry, I messed up the link. This one should work: it's Pólya-Szegő, Problems and theorems in analysis, Volume I: Series, integral calculus, theory of functions. It's part of the detailed statement that for a subbadditive sequence $d_{n + m} \leq d_{n} + d_{m}$ either there is a lower bound of $d_n/n$ and then $L \leq \frac{d_n}{n}$ and thus the limit equals the infimum or $\frac{d_n}{n}$ diverges properly to $-\infty$. The second case can't happen here because $c_n / n$ has $-L$ as lower bound. – t.b. Aug 14 '11 at 20:50
@Theo: Wikipedia has a reference (found on Subadditivity) to the paper of Fekete: Fekete, M. "Uber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit. ganzzahligen Koeffizienten." Mathematische Zeitschrift 17 (1923), pp. 228–249. – Asaf Karagila Aug 14 '11 at 20:56
@Asaf: Thanks (man, wanna challenge me with references?! :p) I know that paper, but after looking through it several times I found myself unable to find a compelling reason why exactly it is mentioned by PS... :) – t.b. Aug 14 '11 at 20:59
@Daniel: Please don't use subjective titles like "It's difficult", "it's hard", etc. – Arturo Magidin Aug 14 '11 at 22:55

There are two parts to the story here. Detailed arguments and variants can be found in Pólya-Szegő, Problems and theorems in analysis, Volume I: Series, integral calculus, theory of functions, page 198 and 199 (Exercises 98 and 99 of part I)

Suppose that the sequence $(x_n)_{n \in \mathbb{N}}$ of real numbers is subadditive: $x_{m+n} \leq x_m + x_n$. Consider $L = \inf\limits_{n \in \mathbb{N}} \frac{x_n}{n}$. Either $L = - \infty$ and $\dfrac{a_n}{n}$ diverges properly to $-\infty$, or $$\lim_{n \to \infty} \frac{x_n}{n} = \inf_{n \in \mathbb{N}} \frac{x_n}{n} = L,$$ and in particular the limit exists.

Let $L = \inf\limits_{n \in \mathbb{N}} \frac{x_n}{n}$. The case $L = - \infty$ is easy, so assume $L \gt -\infty$. For $\varepsilon \gt 0$ there is an $m$ such that $\frac{x_m}{m} \lt L + \varepsilon$. Writing $n = km + r$ with $0 \leq r \lt m$ we get $$L \leq \frac{x_{n}}{n} \leq \frac{k \cdot x_m + x_r}{km+r} \leq \frac{x_m}{m}+ \frac{x_r}{n} \leq \frac{x_m}{m} + \frac{C}{n}$$ with $C = \max{\{x_0,\ldots,x_{m-1}\}}.$ For $n \geq C/\varepsilon$ we thus have $\displaystyle L \leq \frac{x_n}{n} \leq \frac{x_m}{m} + \varepsilon \leq L+2\varepsilon$ and thus the limit exists and equals the infimum of the sequence.

The second part is:

Suppose the sequence $(a_n)_{n \in \mathbb{N}}$ satisfies $-1 + a_m + a_n \leq a_{m+n} \leq 1 + a_m + a_n$. Then the limit $L = \lim\limits_{n \to \infty}\frac{a_{n}}{n}$ exists and $L-1 \leq \frac{a_{n}}{n} \leq L+1$.

Note that the sequence $b_n = 1+a_n$ is subadditive: $b_{m+n} \leq b_m + b_n$ hence we can apply the first part to it and find that $$-\infty \leq L = \inf_{n \in \mathbb{N}} \frac{1+a_{n}}{n} = \lim_{n \to \infty} \frac{1+a_{n}}{n} \lt \infty.$$ Similarly, $c_n = 1-a_n$ is subadditive and hence $$- \infty \leq -L = \inf_{n \in \mathbb{N}} \frac{1-a_n}{n} = \lim_{n\to\infty}\frac{1-a_n}{n} \lt \infty.$$ Therefore $L$ is a real number and $L \leq \dfrac{1+a_n}{n}$ together with $-L \leq \dfrac{1-a_n}{n}$ yields the desired estimates $nL - 1 \leq a_n \leq nL+1$ where $L = \lim_{n\to\infty}\frac{a_n}{n}$ also follollows from the above.

These lemmas have many applications. An easy variant of this is that a submultiplicative sequence of non-negative numbers, that is $a_{n+m} \leq a_n a_m$ has the property that $a_{n}^{1/n}$ converges. This can be used for the spectral radius formula in functional analysis.

Recently, quasi-subadditive sequences have received quite a bit of attention in guise of quasi-morphisms with significant applications in group theory, dynamical systems, symplectic geometry, and so on.

A beautiful elementary application is Norbert A'Campo's model of real numbers via almost additive maps $\varphi: \mathbb{Z} \to \mathbb{Z}$ (he calls them slopes), that is functions $\varphi$ satisfying $$\sup\limits_{m,n \in \mathbb{Z}}{|\varphi(m+n) - \varphi(m) - \varphi(n)|} \lt \infty$$ modulo a simple equivalence relation. The basic idea here is that any real number $r$ yields such a map by setting $\phi(n) = \lfloor rn \rfloor$. The paper is highly recommended, as it contains quite a few ingenious constructions and interesting historical remarks.

-