Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The following result, which I know under the name Fekete's lemma is quite often useful. It was, for example, used in this answer: Existence of a limit associated to an almost subadditive sequence.

If $(a_n)_{n=0}^\infty$ is a subadditive sequence of real numbers, i.e., $$(\forall m,n) a_{m+n} \le a_m + a_n,$$ then $$\lim\limits_{n\to\infty} \frac{a_n}n = \inf_n \frac{a_n}n.$$

Some references are given in Wikipedia article, the original Fekete's paper is available here. Basically the exponential version (for submultiplicative sequences) can be shown in a similar way as Satz II in this paper.

I was wondering, whether some analogous claim is true for functions. I.e. something like: Whenever $f:{(0,\infty)}\to{\mathbb R}$ fulfills $$(\forall x,y)f(x+y) \le f(x)+f(y)$$ (i.e., it is subadditive), then $$\lim\limits_{x\to\infty} \frac{f(x)}x = \inf_x \frac{f(x)}x.$$ (In particular, the above limit exists -- if we include the possibility $-\infty$.)

Clearly, this is not true without any additional assumptions on $f$. (E.g. if $f$ is any non-linear solution of Cauchy's equation, then $\liminf \frac{f(x)}x < \limsup \frac{f(x)}x$ and $f$ is both subadditive and superadditive. Probably even much simpler examples can be given.)

On the other hand, if $f$ is well-behaved, the above claim is true. If I assume that $f$ is bounded on intervals of the form $(0,x]$, then I can basically repeat the proof which is given for sequences here.

So my question is:

  • Under what assumptions on $f$ the above claim is true.

  • Can you give some references for this claim?

EDIT: I found a result which shows that measurability of $f$ is sufficient and added this result as an answer. I think this is sufficient for most applications and my guess is that there is not much space to improve this result. However, I will wait a little bit before accepting my own answer - just in case someone would like to add some interesting information or further useful references. I have accepted my own answer, but if you have some interesting information which you can add, I'll be very glad to learn about it.

share|improve this question
@t.b. I tried to look into the paper and the closest thing to me seemed to be the proof of Satz II, as I write in my question. Lemma 11.6. from van Lint-Wilson: A course in combinatorics, p. 103 also refers to this paper and is in the "exponential form", which might be an argument in favor of this. (That we should look for the "exponential form" in the paper.)\\ Polya and Szego write on p. 198: "For a special case see M. Fekete: Math. Z. Vol. 17, p. 233 (1939)." –  Martin Sleziak Oct 12 '11 at 13:45
Thanks! I forgot about the "special case" P-S mention and just found it, when I looked again, that's why I removed my earlier comment before you posted yours. Good to know. I agree that the argument from the proof Satz II is enough to prove the general lemma. –  t.b. Oct 12 '11 at 13:48
add comment

1 Answer

up vote 4 down vote accepted

If found the following $N$-dimensional result in the book An introduction to the theory of functional equations and inequalities By Marek Kuczma p.463:

Theorem 16.2.9. Let $f:\mathbb R^{N}\to\mathbb R$ be a measurable subadditive function. Then for every $x\in\mathbb R^N$ there exists the limit $$F(x)=\lim_{t\to\infty} \frac{f(tx)}t.$$ The function $F$ is finite, continuous in $\mathbb R^N$, positively homogeneous and subadditive.

I should also mention that in the proof of this theorem it is shown that $$\lim_{t\to\infty} \frac{f(tx)}t=\inf_{t>0}\frac{f(tx)}t.$$

This result is proven in Kuczma's book and he gives the following texts as further references:

  • E. Hille and R. S. Phillips, Functional analysis and semi-groups, American Mathematical Society Colloquium Publications, vol. 31, American Mathematical Society, Providence, R. I., 1957, rev. ed. Special case for $N=1$ is given in this book as Theorem 7.6.1. Here the assumptions are that $f$ is a real subadditive function defined on some interval $(a,\infty)$, $a\ge 0$.

  • R.A. Rosenbaum, Sub-additive functions, Duke Math. J. 17 (1950), 227–247.

I also stumbled upon the paper J.M. Hammersley: Generalization of the Fundamental Theorem on Subadditive Functions, where the author refers to this result as fundamental theorem on subadditive functions.

This shows that measurability of $f$ is sufficient for Fekete's lemma to hold.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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