Супераддитивность

В математике последовательность {a_n}, n ≥ 1, называется супераддитивной, если она удовлетворяет неравенству

${\displaystyle a_{n+m}\geq a_{n}+a_{m}}$

для любых m и n. Основная причина использования супераддитивных последовательностей вытекает из следующей леммы Майкла Фекете[1].

Лемма: (Фекете) Для любой супераддитивной последовательности {a_n}, n≥1, предел lim a_n /n существует и равен супремуму sup a_n /n. (Предел может быть положительной бесконечностью, например, для последовательности a_n=logn!).

Аналогично, функция f супераддитивна, если

${\displaystyle f(x+y)\geq f(x)+f(y)}$

для любых x и y из области определения f .

Например, ${\displaystyle f(x)=x^{2}}$ является супераддитивной функцией для неотрицательных действительных чисел, поскольку квадрат ${\displaystyle x+y}$ всегда больше или равен сумме квадратов ${\displaystyle x}$ и ${\displaystyle y}$ для любых неотрицательных действительных чисел ${\displaystyle x}$ и ${\displaystyle y}$ .

Аналог леммы Фекете верен и для субаддитивных функций. Существуют расширения леммы Фекете, которые не требуют, чтобы определение супераддитивности выполнялось для всех m и n. Есть также результаты, которые позволяют вывести скорость сходимости к пределу, существование которого утверждается в лемме Фекете, если присутствует какая-либо супераддитивность или субаддитивность. Хорошее изложение этой темы можно найти в Steele (1997)[2][3].

Термин «супераддитивный» также применяется к функциям из алгебры логики, где ${\displaystyle P(X\lor Y)\geq P(X)+P(Y)}$.

Если f — супераддитивная функция и 0 находится в её области определения, то f (0) ≤ 0. Чтобы убедиться в этом, возьмём неравенство: ${\displaystyle f(x)\leq f(x+y)-f(y)}$ . Следовательно ${\displaystyle f(0)\leq f(0+y)-f(y)=0.}$