# State of the art in the expected length of the Longest Increasing Subsequence of a random permutation

I have been reading about the topic motivated by a problem I read that asked for the first three digits of the sum of the LIS lengths in all permutations of length $n$. It is easy to see that we are really interested in the expected value of the LIS length in a random permutation of the first $n$ positive integers. A paper by Mike Phulsuksombati states $$l_n=2\sqrt{n}+cn^{1/6}+o(n^{1/6})$$ Where $c\approx-1.771088$ as a known asymptotic.

Questions: Is there a better asymptotic known? Is there a polynomial or logartihmic(in terms of $n$) time algorithm for finding $l_n$ or approximating it to a desired precision?

• I am not sure if there is anything better than Baik-Deift-Johansson's seminal result. If there indeed is, Dan Romik's fantastic book devoted to this and more would be the place to begin. – user61318 Oct 10 '15 at 21:32
• Dan Romik's book: The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, 2015. (Link to author page.) – Joseph O'Rourke Oct 11 '15 at 0:13
• @user61318 and JosephORourke Thanks for the reference to such an interesting, recent, free book! I will update the post after giving it a read, hopefully having an answer to both questions. – chubakueno Oct 11 '15 at 1:25
• Looking at the BDJ paper, I think one can likely make the little-o explicit (see (1.7), (1.8), and proof of 1.1 in Section 9), but I don't think it is sufficiently impressive looking to do so. But maybe I miss something. – kantelope Oct 11 '15 at 14:59

@chubakueono, as far as I know the answer to your questions are no and no. Pages 148-149 in my book have the state of the art (essentially the formula you wrote, along with some additional background) and the relevant references. However, in a broader sense much more is understood about the asymptotic formula for $l_n$ and where it comes from. The main important points as relates to your question are:
1. The asymptotic formula for $l_n$ is closely related to a more detailed distributional limit for the random variable $L(\sigma_n)$ defined as the maximal length of an increasing subsequence in a uniformly random permutation $\sigma_n$ of order $n$. The result, known as the Baik-Deift-Johansson theorem, says that for any $t\in\mathbb{R}$, $$\mathbb{P}\left( \frac{L(\sigma_n)-2\sqrt{n}}{n^{1/6}} \le t \right) \to F_2(t) \quad \textrm{as }n\to\infty,$$ where $F_2(t)$ is a certain probability distribution known as the Tracy-Widom distribution. $F_2(t)$ can be expressed explicitly as $$F_2(t) = \exp\left( -\int_x^\infty (x-t)q(x)^2\,dx \right),$$ where $q(x)$ is the unique solution to the Painleve II ODE $$y''(x)=2y(x)^3+xy(x)$$ with certain asymptotic boundary conditions.
2. The constant $c$ in the asymptotic formula for $l_n=\mathbb{E}(L(\sigma_n))$ is simply the expected value of this distribution, that is $$c = \int_{-\infty}^{\infty} x F_2'(x)\,dx.$$
3. Proving a rate of convergence estimate in the asymptotic formula for $l_n$ would be extremely interesting (and, I suspect, difficult) and is an open problem as far as I know.