|
|
|
Viewing Version
6
of
'superadditivity'
|
[ view 'superadditivity'
|
back to history
]
| Title of object: |
superadditivity |
| Canonical Name: |
Superadditivity |
| Type: |
Definition |
| Created on: |
2003-08-19 01:50:21 |
| Modified on: |
2004-01-25 01:00:12 |
| Classification: |
msc:39B62 |
| Synonyms: |
superadditivity=superadditive |
Revision comment (for changes between this and next version):
Preamble:
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amsthm}
\newtheorem*{lemma}{Lemma}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
\makeatletter
\@ifundefined{bibname}{}{\renewcommand{\bibname}{References}}
\makeatother |
Content:
A sequence $\{a_n\}_{n=1}^\infty$ is called \emph{superadditive} if
it satisfies the inequality
\begin{equation}\label{eqn:seq}
a_{n+m}\geq a_n+a_m\qquad\text{for all $n$ and $m$}.
\end{equation}
The major reason for use of superadditive sequences is the following
lemma due to Fekete.
\begin{lemma}[\cite{cite:polya_szegoi}]
For every superadditive sequence $\{a_n\}_{n=1}^\infty$ the limit
$\lim a_n/n$ exists and equal to $\sup a_n/n$.
\end{lemma}
Similarly, a function $f(x)$ is \emph{superadditive} if
\begin{equation*}
f(x+y)\geq f(x)+f(y)\qquad\text{for all $x$ and $y$}.
\end{equation*}
The analogue of Fekete lemma holds for superadditive functions as
well.
There are extensions of Fekete lemma that do not require \eqref{eqn:seq} 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 lemma if some kind of both super- and subadditivity is present. A good exposition of this topic may be found in \cite{cite:steele_azuma}.
\begin{thebibliography}{1}
\bibitem{cite:polya_szegoi}
Gy{\"o}rgy Polya and G{\'a}bor Szeg{\"o}.
\newblock {\em Problems and theorems in analysis}, volume~1.
\newblock 1976.
\newblock \PMlinkexternal{Zbl 0338.00001}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0338.00001}.
\bibitem{cite:steele_azuma}
Michael~J. Steele.
\newblock {\em Probability theory and combinatorial optimization}, volume~69 of
{\em CBMS-NSF Regional Conference Series in Applied Mathematics}.
\newblock SIAM, 1997.
\newblock \PMlinkexternal{Zbl 0916.90233}{http://www.emis.de/cgi-bin/zmen/ZMATH/en/quick.html?type=html&an=0916.90233}.
\end{thebibliography} |
|
|
|
|
|
