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 maps are special cases of subadditive functions. 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 maps are special cases of subadditive functions. A subadditive function is a function f : A → B {displaystyle fcolon A o B} , having a domain A and an ordered 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 ∀ x , y ≥ 0 {displaystyle forall x,ygeq 0} we have: A sequence { a n } , n ≥ 1 {displaystyle left{a_{n} ight},ngeq 1} , is called subadditive if it satisfies the inequality for all m and n. This is a special case of subadditive function, if a sequence is interpreted as a function on the set of natural numbers. A useful result pertaining to subadditive sequences is the following lemma due to Michael Fekete. The analogue of Fekete's lemma holds for superadditive sequences as well, that is: a n + m ≥ a n + a m . {displaystyle a_{n+m}geq a_{n}+a_{m}.} (The limit then may be positive infinity: consider the sequence a n = log ⁡ n ! {displaystyle a_{n}=log n!} .) There are extensions of Fekete's lemma that do not require the inequality (1) to hold for all m and n, but only for m and n such that 1 2 ≤ m n ≤ 2. {displaystyle {frac {1}{2}}leq {frac {m}{n}}leq 2.} Moreover, the condition a n + m ≤ a n + a m {displaystyle a_{n+m}leq a_{n}+a_{m}} may be weakened as follows: a n + m ≤ a n + a m + ϕ ( n + m ) {displaystyle a_{n+m}leq a_{n}+a_{m}+phi (n+m)} provided that ϕ {displaystyle phi } is an increasing function such that the integral ∫ ϕ ( t ) t − 2 d t {displaystyle int phi (t)t^{-2},dt} converges (near the infinity). 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.