9
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ 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. $\endgroup$
    – user35313
    Commented Oct 10, 2015 at 21:32
  • 5
    $\begingroup$ Dan Romik's book: The Surprising Mathematics of Longest Increasing Subsequences, Cambridge University Press, 2015. (Link to author page.) $\endgroup$
    – Joseph O'Rourke
    Commented Oct 11, 2015 at 0:13
  • $\begingroup$ @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. $\endgroup$
    – chubakueno
    Commented Oct 11, 2015 at 1:25
  • $\begingroup$ 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. $\endgroup$
    – kantelope
    Commented Oct 11, 2015 at 14:59

1 Answer 1

Reset to default
13
$\begingroup$

@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:

  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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .