Regarding sub-additive sequences and Fekete's lemma

Question

A non-negative sequence $\{a_n\}$ is sub-additive if $a_{m+n}\leq a_m + a_n.$ Fekete's lemma says that for any non-negative sub-additive sequence:

$$\lim_{n\to\infty} \frac{a_n}{n} = \inf_{n} \frac{a_n}{n}.$$

Of course, one way to show this would be to show that $\frac{a_n}{n}$ is non-increasing, but I have seen no proof of Fekete's lemma like this, so I suspect this is not true. Can you give me an example of a non-negative sub-additive sequence $\{a_n\}$ for which $\frac{a_n}{n}$ is not non-increasing? Thanks!

Answer 1

Here is another "natural" example. Fix an integer $b \ge 2$ and let $s_b(n)$ denote, for each $n \in \mathbf N^+$, the sum of the $b$-digits of $n$. Then $s_b$ is subadditive: This comes, e.g., from the first of the identities mentioned here, together with the fact that also the fractional part is subadditive, which in turn is a consequence of the following: $$ \forall x, y \in \mathbf R: \{x\} + \{y\} = \{x+y\} + \lfloor \{x\} + \{y\} \rfloor. $$ Now observe that, for all $n \in \mathbf N^+$, $$ \frac{s_b(b^n)}{b^n} = \frac{1}{b^n} < \frac{2}{b^n+1} = \frac{s_b(b^n + 1)}{b^n + 1}. $$ Therefore, the sequence $\mathbf N^+ \to \mathbf R: n \mapsto s_b(n)/n$ is not [eventually] non-increasing.

Answer 2

Here's an example from nature, but for superadditive sequences. Fekete's Lemma for superadditive sequences says $$\lim_{n\to\infty} \frac{a_n}{n} = \sup_{n} \frac{a_n}{n}.$$

For a CW complex $X$, we can look at the Lusternik-Schnirelmann category of the skeleta $X_n$ as $n$ varies (actually, the relative category $\mathrm{cat}_X(X_n)$), and define a sequence $$ \sigma_X (k) = \inf\{ n \mid \mathrm{cat}_X(X_n) \geq k \}. $$ It can be proved that this sequence is always superadditive, and it contains lots of good information about the space $X$, so it is nice to determine -- or estimate -- the sequence if possible.

One big challenge to people studying L-S category is to determine the category of the symplectic groups $Sp(n)$. It has been shown that for $n\geq 3$, the sequence $\sigma_{Sp(n)}$ begins $(0,3,7,10,18,21,\ldots)$. The ratios are $$ 3 < {7\over 2} > {10\over 3} < {18\over 4} > {21\over 5} $$