In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, subadditivity is a property of a function that states, roughly, that evaluating the function for the sum of two
elements of the
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
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
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
.
Additive map
In algebra, an additive map, Z-linear map or additive function is a function f that preserves the addition operation:
f(x + y) = f(x) + f(y)
for every pair of elements x and y in the domain of f. For example, any linear map is additive. When the ...
s are special cases of subadditive functions.
Definitions
A subadditive function is a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
, having a
domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
**Domain of definition of a partial function
**Natural domain of a partial function
**Domain of holomorphy of a function
* Do ...
''A'' and an
ordered codomain
In mathematics, the codomain or set of destination 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 . The term range is sometimes ambiguously used to refer to either th ...
''B'' that are both
closed under addition, with the following property:
An example is the
square root
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
...
function, having the
non-negative
In mathematics, the sign of a real number is its property of being either positive, negative, or zero. Depending on local conventions, zero may be considered as being neither positive nor negative (having no sign or a unique third sign), or it ...
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s as domain and codomain,
since
we have:
A
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
, is called subadditive if it satisfies the
inequality
Inequality may refer to:
Economics
* Attention inequality, unequal distribution of attention across users, groups of people, issues in etc. in attention economy
* Economic inequality, difference in economic well-being between population groups
* ...
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.
Note that while a concave sequence is subadditive, the converse is false. For example, randomly assign
with values in
, then the sequence is subadditive but not concave.
Properties
Sequences
A useful result pertaining to subadditive sequences is the following
lemma due to
Michael Fekete
Michael (Mihály) Fekete ( he, מיכאל פקטה; 19 July 1886 – 13 May 1957) was a Hungarian- Israeli mathematician.
Biography
Fekete was born in 1886 in Zenta, Austria-Hungary (today Senta, Serbia). He received his PhD in 1909 from ...
.
The analogue of Fekete's lemma holds for superadditive sequences 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 the inequality
to hold for all ''m'' and ''n'', but only for ''m'' and ''n'' such that
Moreover, the condition
may be weakened as follows:
provided that
is an increasing function such that the integral
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 In mathematics, a function f is superadditive if
f(x+y) \geq f(x) + f(y)
for all x and y in the domain of f.
Similarly, a sequence \left\, n \geq 1, is called superadditive if it satisfies the inequality
a_ \geq a_n + a_m
for all m and n.
The t ...
and subadditivity is present.
Besides, analogues of Fekete's lemma have been proved for subadditive real maps (with additional assumptions) from finite subsets of an amenable group
,
and further, of a cancellative left-amenable semigroup.
Functions
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