Logical Limit Laws for Mallows Random Permutations

Abstract

A random permutation $\Pi_n$ of $\{1,\dots,n\}$ follows the $\text{Mallows}(n,q)$ distribution with parameter $q>0$ if ${\mathbb P} \left( \Pi_n = \pi \right)$ is proportional to $q^{\text{inv}(\pi)}$ for all $\pi$. Here $\text{inv}(\pi) := |\{ i<j : \pi(i)> \pi(j) \}|$ denotes the number of inversions of $\pi$. We consider properties of permutations that can be expressed by the sentences of two different logical languages. Namely, the theory of one bijection (TOOB), which describes permutations via a single binary relation, and the theory of two orders (TOTO), where we describe permutations by two total orders. We say that the convergence law holds with respect to one of these languages if, for every sentence $\phi$ in the language, the probability ${\mathbb P}(\Pi_n\text{ satisfies } \phi)$ converges to a limit as $n\to\infty$. If moreover that limit is $\in\{0,1\}$ for all sentences, then the zero-one law holds.

We will show that with respect to TOOB the $\text{Mallows}(n,q)$ distribution satisfies the zero-one law when $0<q<1$ is fixed, and for fixed $q>1$ the convergence law fails. (In the case when $q=1$ Compton [J. Combin. Theory Ser. A, 1989] has shown the convergence law holds but not the zero-one law.)

We will prove that with respect to TOTO the $\text{Mallows}(n,q)$ distribution satisfies the convergence law but not the zero-one law for any fixed $q\neq 1$, and that if $q=q(n)$ satisfies $1- 1/\log^*n < q < 1 + 1/\log^*n$ then $\text{Mallows}(n,q)$ fails the convergence law. Here $\log^*$ denotes the discrete inverse of the tower function.