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?
 A: @user61318 and @JosephORourke, thanks for the advertisement for my book.
@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:


*

*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.

*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. $$

*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.
