수학(mathematics)에서, 함수(function) \(f\)가 \(f\)의 도메인(domain)에서 모든 \(x\)와 \(y\)에 대해 만약 다음이면 초과덧셈적(superadditive)입니다:
\(\quad f(x+y) \geq f(x) + f(y).\)
유사하게, 수열(sequence) \(\left\{a_n\right\},\) \(n \geq 1\)은, 모든 \(m\)와 \(n\)에 대해 만약 그것이 다음 부등식(inequality)을 만족시키면 초과덧셈적(superadditive)입니다:
\(\quad a_{n+m} \geq a_n + a_m.\)
용어 "초과덧셈"은 역시 부울 대수(boolean algebra)에서 실수로의 함수에도 적용되며, 여기서 아래쪽 확률(lower probabilities)과 같은 \(P(X \lor Y) \geq P(X) + P(Y)\)입니다.
Properties
만약 \(f\)가 초과덧셈 함수이고, 0이 그것의 도메인 내에 있으면, \(f(0) \leq 0\)입니다. 이것을 보이기 위해, 꼭대기에서 부등식을 취하십시오: \(f(x) \leq f(x+y) - f(y).\) 따라서 \(f(0) \leq f(0+y) - f(y) = 0.\)
초과덧셈 함수의 부정은 부분덧셈적(subadditive)입니다.
Fekete's lemma
초과덧셈 수열을을 사용하는 주요 이유는 마이클 페케떼(Michael Fekete)에 기인한 다음 보조정리(lemma)입니다.
Lemma: (페케떼) 모든 각 초과덧셈 수열 \(\left\{a_n\right\},\) \(n \geq 1\)에 대해, 극한(limit) \(\lim a_n/n\)은 \(\sup a_n/n\)과 같습니다. (그 극한은, 예를 들어, 수열 \(a_n = \log n!\)에 대해 양의 무한대가 될 수 있습니다.)
예를 들어, \(f(x) = x^2\)는 비-음의 실수(real numbers)에 대해 초과덧셈 함수인데 왜냐하면 \(x+y\)의 제곱은 항상 \(x\)의 제곱 더하기 \(y\)의 제곱보다 크거나 같기 때문이며, 비-음의 실수 \(x\)와 \(y\)에 대해: \(f(x + y) = (x + y)^2 = x^2 + y^2 + 2 xy = f(x) + f(y) + 2 xy\).
페케떼의 보조 정리의 아날로그는 부분덧셈(subadditive) 함수에도 적용됩니다. 모든 \(m\)과 \(n\)에 대해 유지하기 위해 위의 초과덧셈성의 정의를 요구하지 않은 페케떼의 보조 정리의 확장이 있습니다. 역시 만약 어떤 종류의 초과덧셈성과 부분덧셈성이 모두 존재하면 페케떼의 보조정리에서 그 존재가 명시된 극한까지 수렴 속도를 추론할 수 있는 결과가 있습니다. 이 주제에 대한 좋은 설명은 Steele (1997)에서 찾을 수 있습니다.
Examples of superadditive functions
- 행렬식(determinant)은 비-음의 헤세 행렬(Hermitian matrix)에 대해 초과덧셈적이며, 즉, 만약 \(A, B \in \text{Mat}_n(\mathbb{C})\)가 비-음의 헤세이면 \(\det(A+B) \geq \det(A) + \det(B)\)입니다.
이것은 민코프스키 행렬식 정리에서 따르며, 이는 보다 일반적으로 \( \det(\cdot)^{1/n}\)는 크기 \(n\)의 비-음의 헤세 행렬에 대해 초과덧셈적 (동등하게, 오목(concave))이라고 말합니다: 만약 \(A,B \in \text{Mat}_n(\mathbb{C})\)가 비-음의 헤세이면 \(\det(A+B)^{1/n} \geq \det(A)^{1/n} + \det(B)^{1/n}\)입니다.
- 상호 정보(Mutual information)
- Horst Alzer는 아다마르의 감마 함수(Hadamard's gamma function) \(H(x)\)는 \(x, y \geq 1.5031\)를 갖는 모든 실수 \(x, y\)에 대해 초과덧셈적임을 입증했습니다.
See also
References
- Fekete, M. (1923). "Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten". Mathematische Zeitschrift. 17 (1): 228–249. doi:10.1007/BF01504345.
- Michael J. Steele (1997). Probability theory and combinatorial optimization. SIAM, Philadelphia. ISBN 0-89871-380-3.
- Michael J. Steele (2011). CBMS Lectures on Probability Theory and Combinatorial Optimization. University of Cambridge.
- M. Marcus, H. Minc (1992). A survey in matrix theory and matrix inequalities. Dover. Theorem 4.1.8, page 115.
- Horst Alzer (2009). A superadditive property of Hadamard's gamma function. Springer. doi:10.1007/s12188-008-0009-5.
Notes
- György Polya and Gábor Szegö. (1976). Problems and theorems in analysis, volume 1. Springer-Verlag, New York. ISBN 0-387-05672-6.
