Subadditivity

Subadditivity is a property of a function or sequence that expresses a diminishing combination cost or value. Formally, a function f defined on the nonnegative reals (or a similar additive domain) is subadditive if, for all x,y in the domain, f(x + y) ≤ f(x) + f(y). A sequence {a_n} is subadditive if a_{m+n} ≤ a_m + a_n for all m,n. When f(0) = 0, these conditions are most commonly studied.

Key results and extensions include Fekete’s lemma, which says that for any subadditive sequence a_n, the limit lim_{n→∞} a_n / n exists and equals inf_n a_n / n. This provides a well-defined asymptotic per-unit value. In probability and ergodic theory, Kingman’s subadditive ergodic theorem extends the idea to stochastic processes, giving almost sure and L1 limits for normalized sums under suitable conditions.

Examples include f(x) = sqrt(x) on [0, ∞), which satisfies sqrt(x+y) ≤ sqrt(x) + sqrt(y). In information theory, entropy is subadditive in the sense that H(X,Y) ≤ H(X) + H(Y). In economics and operations research, cost functions with C(m+n) ≤ C(m) + C(n) exhibit economies of scale, reflecting that producing together can be cheaper than producing separately.

Subadditivity often implies that average values f(n)/n stabilize and that long-run behavior is tractable. It is a fundamental concept across analysis, probability, information theory, and optimization, guiding both theory and applications.