Subadditive function
Encyclopedia
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 function
s are special cases of subadditive functions.
, 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 number
s as domain and codomain,
since
we have:
A sequence
, is called subadditive if it satisfies the inequality
for all m and n.
due to Michael Fekete.
The analogue of Fekete's lemma holds for superadditive functions as well, that is:
(The limit then may be positive infinity: consider the sequence 
.)
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.
If f is a subadditive function, and if 0 is in its domain, then f(0) ≥ 0. To see this, take the inequality at the top.
. Hence 
A concave function
with f(0) = 0 is also subadditive.
To see this, one first observes that
.
A properly weighted sum of this bound for
and 
shows that f is subadditive.
The negative of a subadditive function is superadditive.
. 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.
In general, the price of goods (as a function of quantity) must be subadditive. Otherwise, if the sum of the cost of two items is cheaper than the cost of the bundle of two of them together, then nobody would ever buy the bundle, effectively causing the price of the bundle to "become" the sum of the prices of the two separate items.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, 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
Norm (mathematics)
In linear algebra, functional analysis and related areas of mathematics, a norm is a function that assigns a strictly positive length or size to all vectors in a vector space, other than the zero vector...
and square roots. Additive function
Additive function
In mathematics the term additive function has two different definitions, depending on the specific field of application.In algebra an additive function is a function that preserves the addition operation:for any two elements x and y in the domain. For example, any linear map is additive...
s are special cases of subadditive functions.
Definitions
A subadditive function is a functionFunction (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
, having a domain A and an ordered codomainCodomain
In mathematics, the codomain or target set of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation...
B that are both closed
Closure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under addition, with the following property:
-
.
An example is the square root
Square root
In mathematics, a square root of a number x is a number r such that r2 = x, or, in other words, a number r whose square is x...
function, having the non-negative real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s as domain and codomain,
since
we have:
A sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
, is called subadditive if it satisfies the inequality
for all m and n.
Properties
A useful result pertaining to subadditive sequences is the following lemmaLemma (mathematics)
In mathematics, a lemma is a proven proposition which is used as a stepping stone to a larger result rather than as a statement in-and-of itself...
due to Michael Fekete.
- Fekete's Subadditive Lemma: For every subadditive sequence
, the limitLimit of a sequenceThe limit of a sequence is, intuitively, the unique number or point L such that the terms of the sequence become arbitrarily close to L for "large" values of n...
exists and is equal to 
. (The limit may be 
.)
The analogue of Fekete's lemma holds for superadditive functions as well, that is:
(The limit then may be positive infinity: consider the sequence .)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.
If f is a subadditive function, and if 0 is in its domain, then f(0) ≥ 0. To see this, take the inequality at the top.
. Hence A concave function
Concave function
In mathematics, a concave function is the negative of a convex function. A concave function is also synonymously called concave downwards, concave down, convex upwards, convex cap or upper convex.-Definition:...
with f(0) = 0 is also subadditive.To see this, one first observes that
.A properly weighted sum of this bound for
and shows that f is subadditive.The negative of a subadditive function is superadditive.
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 monopolyNatural monopoly
A monopoly describes a situation where all sales in a market are undertaken by a single firm. A natural monopoly by contrast is a condition on the cost-technology of an industry whereby it is most efficient for production to be concentrated in a single form...
. 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
Economies of scale
Economies of scale, in microeconomics, refers to the cost advantages that an enterprise obtains due to expansion. There are factors that cause a producer’s average cost per unit to fall as the scale of output is increased. "Economies of scale" is a long run concept and refers to reductions in unit...
are represented by subadditive average cost
Average cost
In economics, average cost or unit cost is equal to total cost divided by the number of goods produced . It is also equal to the sum of average variable costs plus average fixed costs...
functions.
In general, the price of goods (as a function of quantity) must be subadditive. Otherwise, if the sum of the cost of two items is cheaper than the cost of the bundle of two of them together, then nobody would ever buy the bundle, effectively causing the price of the bundle to "become" the sum of the prices of the two separate items.