Show that the inversion permutation, i

Definitions and mathematical statement

For a prime $p$, let $\iota_p$ be the permutation of $\{1,\ldots,p-1\}$ defined by multiplicative inversion modulo $p$: $\iota_p(a)$ is the unique representative in this set satisfying $a\,\iota_p(a)\equiv1\pmod p$. Its longest increasing subsequence length is \[ L(p)=\max\{\ell:\exists\,1\le a_1<\cdots<a_\ell<p, \ \iota_p(a_1)<\cdots<\iota_p(a_\ell)\}. \] Determine the growth and finer asymptotic behavior of $L(p)$ as $p\to\infty$ through primes. In particular, the question seeks whether Propp's conjectured asymptotic formula \[ L(p)=(2+o(1))\sqrt p \] holds, or equivalently whether $L(p)/\sqrt p\to2$ through primes. The constant is suggested by comparison with uniformly random permutations, but is conjectural for these inversion permutations.

All comparisons use the ordinary integer representatives $1,\ldots,p-1$; there is no cyclic ordering of residues in the definition. Zero is omitted because it is not invertible. This is a deterministic sequence of permutations indexed by primes, so probabilistic behavior of uniform random permutations does not by itself provide an asymptotic formula for $L(p)$. Upper and lower estimates should hold over the stated sequence of primes, or explicitly identify any exceptional subsequence. The selected indices need not be consecutive, and the question concerns the maximal length, rather than the number of increasing subsequences of a given length.

Short English statement

Determine the asymptotic length of the longest increasing subsequence of the inversion permutation modulo a prime.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100035 (AMR-030-0035), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Permutations, source-order bullet 35. Original source indexed by AMR-030-0035. https://people.math.sc.edu/cooper/combprob.html.
• S3 Miller, project on longest increasing subsequences of modular-inversion permutations, inspired by Propp’s question. https://web.williams.edu/Mathematics/sjmiller/public_html/book/projects/modp/modp.htm.