Editing Subadditivity (section)

===Combinatorics on words===
A factorial [[Formal language|language]] <math>L</math> is one where if a [[String (computer science)|word]] is in <math>L</math>, then all [[Substring|factors]] of that word are also in <math>L</math>.   In [[combinatorics on words]], a common problem is to determine the number <math>A(n)</math> of length-<math>n</math> words in a factorial language.  Clearly <math>A(m+n) \leq A(m)A(n)</math>, so <math>\log A(n)</math> is subadditive, and hence Fekete's lemma can be used to estimate the growth of <math>A(n)</math>.<ref name=shur>{{cite journal|last=Shur|first=Arseny|title=Growth properties of power-free languages|journal=Computer Science Review|date=2012|volume=6|issue=5–6|pages=187–208|doi=10.1016/j.cosrev.2012.09.001}}</ref>

For every <math>k \geq 1</math>, sample two strings of length <math>n</math> uniformly at random on the alphabet <math>1, 2, ..., k</math>. The expected length of the [[longest common subsequence]] is a ''super''-additive function of <math>n</math>, and thus there exists a number <math>\gamma_k \geq 0</math>, such that the expected length grows as <math>\sim \gamma_k n</math>. By checking the case with <math>n=1</math>, we easily have <math>\frac 1k < \gamma_k \leq 1</math>. The exact value of even <math>\gamma_2</math>, however, is only known to be between 0.788 and 0.827.<ref>{{Cite journal |last=Lueker |first=George S. |date=May 2009 |title=Improved bounds on the average length of longest common subsequences |url=https://dl.acm.org/doi/10.1145/1516512.1516519 |journal=Journal of the ACM |language=en |volume=56 |issue=3 |pages=1–38 |doi=10.1145/1516512.1516519 |s2cid=7232681 |issn=0004-5411|url-access=subscription }}</ref>