Subadditivity

In mathematics, subadditivity is a property of a function that states, roughly, that evaluating the function for the sum of two elements of the domain always returns something less than or equal to the sum of the function's values at each element. There are numerous examples of subadditive functions in various areas of mathematics, particularly norms and square roots. Additive functions are special cases of subadditive functions.

A subadditive function is a function $f\; colon\; A\; o\; B$, having an domain $A$ and an ordered codomain $B$ that are both closed under addition, with the following property:::$forall\; x,\; y\; in\; A,\; f(x+y)leq\; f(x)+f(y)$.

An example is the square root function, having the non-negative real numbers as domain and codomain,since $forall\; x,\; y\; geq\; 0$ 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 Michael Fekete. [Fekete, M. "Uber die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit. ganzzahligen Koeffizienten." "Mathematische Zeitschrift" 17 (1923), pp. 228–249.]

:Lemma: For every subadditive sequence $\{left\; \{\; a\_n\; ight\; \_\{n=1\}^infty$, the limit $lim\_\{n\; o\; infty\}\; frac\{a\_n\}\{n\}$ exists and is equal to $inf\; frac\{a\_n\}\{n\}$. (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. [Michael J. Steele. "Probability theory and combinatorial optimization". SIAM, Philadelphia (1997). ISBN 0-89871-380-3.]

Economics

Subadditivity is an essential property of some particular cost functions. It is, generally, a necessary and sufficient condition for the verification of a natural monopoly. It implies that production from only one firm is socially less expensive (in terms of average costs) than production of a fraction of the original quantity by an equal number of firms.

Economies of scale are represented by subadditive average cost functions.

ee also

*Triangle inequality

References

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

External links