6
$\begingroup$

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!

$\endgroup$
8
  • 2
    $\begingroup$ How about $a_n=1$ if $n$ is odd, and $a_n=0$ if $n$ is even. $\endgroup$
    – Lucia
    Apr 9, 2014 at 1:01
  • $\begingroup$ @Lucia I think one wants $a_n$ to be increasing. $\endgroup$ Apr 9, 2014 at 1:36
  • $\begingroup$ Thanks Lucia for the example. I believe you can make it increasing by adding your sequence to the sequence $b_n = 2n$ to get $c_n = 2n+ 1_{\mathrm{$n$ is odd}}$. $\endgroup$
    – Hedonist
    Apr 9, 2014 at 3:23
  • $\begingroup$ What does ''not non-increasing" mean? $\endgroup$
    – Lucia
    Apr 9, 2014 at 3:31
  • $\begingroup$ Lucia: By "not non-increasing", I meant "not monotonically decreasing or constant". $\endgroup$
    – Hedonist
    Apr 9, 2014 at 17:01

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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} $$

$\endgroup$
2
  • 1
    $\begingroup$ Are the ratios $\sigma_{X}(k)/k$ eventually non-increasing for $X = {\rm Sp}(n)$ or whatever? $\endgroup$ Apr 9, 2014 at 12:47
  • $\begingroup$ I don't know! The long term behavior of the sequence is unknown. I'd love to know, for example, what that limit is. $\endgroup$
    – Jeff Strom
    Apr 9, 2014 at 13:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.