SUBADDITIVITY

(Redirected from Subadditive)

In mathematics, a 'subadditive function' is a function $f\; colon\; A\; o\; B$, having a domain $A$ and a codomain $B$ that are both closed under addition, with the following property:
::.
An example is the square root function, having the non-negative real numbers as domain and codomain,
since we have:
::$sqrt\{x+y\}leq\; sqrt\{x\}+sqrt\{y\}.$
A sequence $left\; \{\; a\_n$
ight }, n geq 1, is called 'subadditive' if it satisfies the inequality
::$(1)\; qquad\; a\_\{n+m\}leq\; a\_n+a\_m$
for all $m$ and $n$. The major reason for use of subadditive sequences is the following lemma due to M. Fekete.
:'Lemma:' For every subadditive sequence $\{left\; \{\; a\_n$
ight }}_{n=1}^infty, the limit exists and is equal to . (The limit may be $-infty$.)
The analogue of Fekete's lemma holds for superadditive functions as well, that is:
$a\_\{n+m\}geq\; a\_n\; +\; a\_m.$ (The limit then may be positive infinity: consider the sequence $a\_n\; =\; log\; n!$.)
There are extensions of Fekete's lemma that do not require equation (1) to hold for all $m$ and $n$. There are also results that allow one to deduce the rate of convergence to the limit whose existence is stated in Fekete's lemma if some kind of both superadditivity and subadditivity is present.

Contents

See also

References

Note

See also

★ Triangle inequality

References

★ Problems and theorems in analysis, volume 1, György Pólya and Gábor Szegö., , , Springer-Verlag, New York, 1976, ISBN 0-387-05672-6

★ Probability theory and combinatorial optimization, Michael J. Steele, , , SIAM, Philadelphia, 1997, ISBN 0-89871-380-3

Note

★ A good exposition of this topic may be found in Steele's ''Probability theory and combinatorial optimization'' given in the references.