Editing Subadditivity (section)

===Sequences===
{{Anchor|Fekete's Subadditive Lemma}}A useful result pertaining to subadditive sequences is the following [[lemma (mathematics)|lemma]] due to [[Michael Fekete]].<ref>{{cite journal |last=Fekete |first=M. |title=Über die Verteilung der Wurzeln bei gewissen algebraischen Gleichungen mit ganzzahligen Koeffizienten |journal=Mathematische Zeitschrift |volume=17 |issue=1 |year=1923 |pages=228–249 |doi=10.1007/BF01504345 |s2cid=186223729 }}</ref>

{{math theorem|name=Fekete's Subadditive Lemma|math_statement= For every subadditive sequence <math>{\left \{ a_n \right \}}_{n=1}^\infty</math>, the [[Limit of a sequence|limit]] <math>\displaystyle \lim_{n \to \infty} \frac{a_n}{n}</math> is equal to the [[Infimum and supremum|infimum]] <math>\inf \frac{a_n}{n}</math>.  (The limit may be <math>-\infty</math>.)}}

{{Math proof|proof= 
Let <math>s^* := \inf_n \frac{a_n}n</math>.

By definition, <math>\liminf_n \frac{a_n}n \geq s^*</math>. So it suffices to show <math>\limsup_n \frac{a_n}n \leq s^*</math>.

If not, then there exists a subsequence <math>(a_{n_k})_k</math>, and an <math>\epsilon > 0</math>, such that <math>\frac{a_{n_k}}{n_k} > s^* + \epsilon</math> for all <math>k</math>. 

Since <math>s^* := \inf_n \frac{a_n}n</math>, there exists an <math>a_m</math> such that <math>\frac{a_m}m < s^* + \epsilon</math>.

By [[pigeonhole principle#infinite sets|infinitary pigeonhole principle]], there exists a sub-subsequence of <math>(a_{n_k})_k</math>, whose indices all belong to the same [[modular arithmetic|residue class]] modulo <math>m</math>, and so they advance by multiples of <math>m</math>. This sequence, continued for long enough, would be forced by subadditivity to dip below the <math>s^* + \epsilon</math> slope line, a contradiction.  

In more detail, by subadditivity, we have

<math display="inline">\begin{aligned} a_{n_2} &\leq a_{n_1} + a_m (n_2-n_1)/m \\ a_{n_3} &\leq a_{n_2} + a_m (n_3-n_2)/m \leq a_{n_1} + a_m (n_3-n_1)/m \\ \cdots & \cdots\\ a_{n_k} &\leq a_{n_1} + a_m (n_k-n_1)/m \end{aligned}</math>

which implies <math>\limsup_k a_{n_k}/n_k \leq a_m/m < s^* + \epsilon</math>, a contradiction.
}}

The analogue of Fekete's lemma holds for superadditive sequences as well, that is:
<math>a_{n+m}\geq a_n + a_m.</math>  (The limit then may be positive infinity: consider the sequence <math>a_n = \log n!</math>.)

There are extensions of Fekete's lemma that do not require the inequality <math>a_{n+m}\le a_n + a_m</math> to hold for all ''m'' and ''n'', but only for ''m'' and ''n'' such that <math display="inline">\frac 1 2 \le \frac m n \le 2.</math> 

{{Math proof|proof= 

Continue the proof as before, until we have just used the infinite pigeonhole principle.  

Consider the sequence <math>a_m, a_{2m}, a_{3m}, ...</math>. Since <math>2m/m = 2</math>, we have <math>a_{2m} \leq 2a_m</math>. Similarly, we have <math>a_{3m} \leq a_{2m}+a_m \leq 3a_m</math>, etc.  

By the assumption, for any <math>s, t \in \N</math>, we can use subadditivity on them if   

<math display="block">\ln(s+t) \in [\ln(1.5 s), \ln (3s)] = \ln s + [\ln 1.5, \ln 3]</math>

If we were dealing with continuous variables, then we can use subadditivity to go from <math>a_{n_k}</math> to <math>a_{n_k} + [\ln 1.5, \ln 3]</math>, then to <math>a_{n_k} + \ln 1.5 + [\ln 1.5, \ln 3]</math>, and so on, which covers the entire interval <math>a_{n_k} + [\ln 1.5, +\infty)</math>.  

Though we don't have continuous variables, we can still cover enough integers to complete the proof. Let <math>n_k</math> be large enough, such that   

<math display="block">\ln (2) > \ln(1.5) + \ln \left(\frac{1.5 n_k + m}{1.5 n_k}\right) </math>
then let <math>n'</math> be the smallest number in the intersection <math>(n_k + m\Z) \cap (\ln n_k + [\ln(1.5), \ln (3)])</math>. By the assumption on <math>n_k</math>, it's easy to see (draw a picture) that the intervals <math>\ln n_k + [\ln(1.5), \ln (3)]</math> and <math>\ln n' + [\ln(1.5), \ln (3)]</math> touch in the middle. Thus, by repeating this process, we cover the entirety of <math>(n_k + m\Z) \cap (\ln n_k + [\ln(1.5), \infty])</math>.  

With that, all <math>a_{n_k}, a_{n_{k+1}}, ...</math> are forced down as in the previous proof. }}

Moreover, the condition <math>a_{n+m}\le a_n + a_m</math> may be weakened as follows: <math>a_{n+m}\le a_n + a_m + \phi(n+m)</math> provided that <math>\phi</math> is an increasing function such that the integral <math display="inline">\int \phi(t) t^{-2} \, dt</math> converges (near the infinity).<ref>{{cite journal |last1=de Bruijn |first1=N.G. |last2=Erdös |first2=P. |title=Some linear and some quadratic recursion formulas. II |journal=Nederl. Akad. Wetensch. Proc. Ser. A |volume=55 |year=1952 |pages=152–163|doi=10.1016/S1385-7258(52)50021-0 }} (The same as ''Indagationes Math.'' '''14'''.) See also Steele 1997, Theorem 1.9.2.</ref>

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 [[superadditive|superadditivity]] and subadditivity is present.<ref>Michael J. Steele. "Probability theory and combinatorial optimization". SIAM, Philadelphia (1997). {{isbn|0-89871-380-3}}.</ref><ref>{{cite video|author=Michael J. Steele|title=CBMS Lectures on Probability Theory and Combinatorial Optimization|publisher=University of Cambridge|year=2011|url=http://sms.cam.ac.uk/collection/1189351}}</ref>

Besides, analogues of Fekete's lemma have been proved for subadditive real maps (with additional assumptions) from finite subsets of an amenable group <ref>{{Cite journal| doi = 10.1007/BF02810577 | doi-access=free | issn = 0021-2172| volume = 115| issue = 1| pages = 1–24| last1 = Lindenstrauss| first1 = Elon| authorlink1=Elon Lindenstrauss | last2 = Weiss| first2 = Benjamin| authorlink2=Benjamin Weiss| title = Mean topological dimension| journal = [[Israel Journal of Mathematics]]| year = 2000| citeseerx = 10.1.1.30.3552}} Theorem 6.1</ref>
<ref>{{Cite journal| doi = 10.1007/BF02790325| doi-access=free | issn = 0021-7670| volume = 48| issue = 1| pages = 1–141| last1 = Ornstein| first1 = Donald S.|authorlink1=Donald Samuel Ornstein| last2 = Weiss| first2 = Benjamin| authorlink2=Benjamin Weiss| title = Entropy and isomorphism theorems for actions of amenable groups| journal = [[Journal d'Analyse Mathématique]]| year = 1987}}</ref>
,<ref>{{Cite journal| doi = 10.1023/A:1009841100168| issn = 1385-0172| volume = 2| issue = 4| pages = 323–415| last = Gromov| first = Misha| title = Topological Invariants of Dynamical Systems and Spaces of Holomorphic Maps: I| journal = Mathematical Physics, Analysis and Geometry| year = 1999| bibcode = 1999MPAG....2..323G| s2cid = 117100302}}</ref>
and further, of a cancellative left-amenable semigroup.<ref>{{Cite journal | arxiv = 1209.6179| last1 = Ceccherini-Silberstein| first1 = Tullio| title = An analogue of Fekete's lemma for subadditive functions on cancellative amenable semigroups| journal = [[Journal d'Analyse Mathématique]]| volume = 124| pages = 59–81| last2 = Krieger| first2 = Fabrice| last3 = Coornaert| first3 = Michel| year = 2014| doi = 10.1007/s11854-014-0027-4 | doi-access=free}} Theorem 1.1</ref>