probability that $e({\mathcal{I}},A_{i\ell})=uv$ is
$\frac{1}{|P|}=\frac{1}{N(N-1)}$.

We fix a sequence $e_{1},e_{2},\dots,e_{\lceil(1+\varepsilon)(\log\log
n)^{3}\rceil}\in P$ with the property that

$E(G)=\\{e_{1},\dots,e_{\lceil(1-\varepsilon)(\log\log
n)^{3}\rceil}\\}=\\{e_{1},\dots,e_{\lceil(1+\varepsilon)(\log\log
n)^{3}\rceil}\\}.$

Since $(1-\varepsilon)(\log\log n)^{3}n>N^{2}$, there are necessarily some
duplicate arcs, this will not be a problem. Then $H({\mathcal{I}},(A_{\ell
1},\dots,A_{\ell L_{\ell}}))=G$ is implied by the event
$\\{e({\mathcal{I}},A_{\ell i})=e_{i}\text{ for all $1\leq i\leq L_{i}$}\\}$.

For notational convenience, let us write

$E:=\\{H({\mathcal{I}},{\mathcal{I}}_{k}(J_{\ell}))=G\text{ for some
$1\leq\ell\leq M$ }\\}.$

It follows from the previous observations that if $Z$ denotes the number of
good indices, then the value of $Z$ is completely determined by the event
$F_{\tau,\underline{A},\underline{B}}$, and

$\begin{array}[]{rcl}{\mathbb{P}}\left(E|F_{\tau,\underline{A},\underline{B}}\right)&\geq&\displaystyle
1-\left(1-\left(\frac{1}{N^{2}}\right)^{(1+\varepsilon)(\log\log
n)^{3}}\right)^{Z}\\\\[8.61108pt] &\geq&\displaystyle
1-\exp\left[-Z\cdot\left(\frac{1}{N^{2}}\right)^{(1+\varepsilon)(\log\log
n)^{3}}\right]\\\\[12.91663pt] &=&\displaystyle 1-\exp\left[-Z\cdot
n^{o(1)}\right].\end{array}$

By Corollary 6.8 and Lemma 6.10 we have that

${\mathbb{P}}(Z<M/2)=e^{-n^{\Omega(1)}}.$

It follows that

$\begin{array}[]{rcl}{\mathbb{P}}(E)&\geq&\displaystyle\sum_{\tau,\underline{A},\underline{B}}{\mathbb{P}}\left(E|F_{\tau,\underline{A},\underline{B}}\right)\cdot{\mathbb{P}}(F_{\tau,\underline{A},\underline{B}})\\\
&\geq&\displaystyle 1-\exp[-M/2]-{\mathbb{P}}(Z<M/2)\\\
&=&1-e^{-n^{\Omega(1)}}.\end{array}$

This proves the statement of the lemma. ∎

###### Proof of Lemma 6.2.

Let $I_{1},\ldots,I_{N}$ be $\left\lceil n^{1/2k}\right\rceil$ intervals of
length $\lfloor n^{1-1/k}\cdot\left(\log\log n\right)^{3/k}\rfloor$. By
Corollary 6.8, with probability $1-e^{-\Omega(n^{1/2k})}$ at least $1$ of them
satisfies Conditions (i)-(iv) of Lemma 6.7, by relabeling if necessary, we can
assume that $I_{1}$ satisfies these conditions. We have
${\mathcal{I}}_{k}(I_{1})\gg\log\log n$ by Condition (i). By Lemma 6.9 we may
shrink $I_{1}$ by iteratively removing the maximum element until $\log\log
n<|{\mathcal{I}}_{k}(I_{1})|<2\log\log n$, ensuring that $I_{1}$ still
satisfies Conditions (ii)-(iv) of Lemma 6.7. In particular
$|I^{\prime}|>n^{4/7}$ for all $I^{\prime}\in{\mathcal{I}}_{k}(I_{1})$, and by
$|I_{1}|\leq n^{1-1/2k}$ we also have $I^{\prime}\leq n^{1-1/2k}$ for all
$I^{\prime}\in{\mathcal{I}}_{k}(I_{1})$.

By Lemma 6.11, for all directed graphs $G$ with
$V(G)={\mathcal{I}}_{k}(I_{1})$ there is an interval $J$ satisfying
$H({\mathcal{I}}_{k}(I_{1}),{\mathcal{I}}_{k}(J))=G$, with probability
$1-e^{-n^{\Omega(1)}}$. ∎

###### Proof of Lemma 6.3.

Let $I_{1},I_{2}$ be any two disjoint intervals such that
$0<|{\mathcal{I}}_{k}(I_{1})|<\log\log n<|{\mathcal{I}}_{k}(I_{2})|<2\log\log
n$, and such that $w_{k+1}(I_{1})=w_{k+1}(I_{2})=0$ and
$w_{k-1}(I^{\prime})>0$ for all
$I\in{\mathcal{I}}_{k}(I_{1})\cup{\mathcal{I}}_{k}(I_{2})$. Each of these
$I^{\prime}\in{\mathcal{I}}_{k}(I_{1})\cup{\mathcal{I}}_{k}(I_{2})$ has length
at most $\max\\{|I_{1}|,|I_{2}|\\}$. By Lemma 6.6 with
$\varepsilon=\frac{1}{2(k+1)}$

${\mathbb{P}}\left(w_{k+1}(I^{\prime})>0\text{ for all intervals
}I^{\prime}\text{ s.t. }|I^{\prime}|>n^{1-\frac{1}{2(k+1)}}\right)\geq
1-e^{-\Omega(n^{1/2})}.$ (154)

So with at least this probability, all $I_{1}$ and $I_{2}$ as described
satisfy $|I_{1}|,|I_{2}|\leq n^{1-\frac{1}{2(k+1)}}$. By
$w_{k-1}(I^{\prime})>0$ for all
$I^{\prime}\in{\mathcal{I}}_{k}(I_{1})\cup{\mathcal{I}}_{k}(I_{2})$ and Lemma
6.5 we have $|I^{\prime}|\geq n^{1-1000/{(k-1)}}$ for all such $I_{1},I_{2}$
and $I^{\prime}\in{\mathcal{I}}_{k}(I_{1})\cup{\mathcal{I}}_{k}(I_{2})$ with
probability $1-O(n^{-998})$. So for sufficiently large $k$ we have

$n^{\frac{1}{2}+\frac{1}{2(k+1)}}<n^{1-1000/(k-1)}\leq|I^{\prime}|<n^{1-\frac{1}{2(k+1)}}.$
(155)

The result then follows by
$|{\mathcal{I}}_{k}(I_{1})\cup{\mathcal{I}}_{k}(I_{2})|\leq 3\log\log n$ and
Lemma 6.11. ∎

##  7 Proof of Theorem 1.2 Part (ii)

Here we extend the case $q=1$ to $|1-q|<1/\log^{*}n$. We will make frequent
use of the sampling algorithm for a $\operatorname{Mallows}(n,q)$ distribution
detailed in Section 3.2.1. Recall also the definition of
$\operatorname{TruncGeo}(n,p)$ random variables whose probability mass
function is given in (11) and is valid in the range
$p\in(-\infty,0)\cup(0,1)$. In particular, $\operatorname{TruncGeo}(n,1-q)$
random variables are well defined for $q\in{\mathbb{R}}_{>0}\setminus\\{1\\}$.

###  7.1 Extending the $q=1$ case to $q=1\pm O(n^{-4})$

We first extend Proposition 6.1 to the following:

######  Proposition 7.1.

There exists a $\varphi\in{\operatorname{\mathsf{TOTO}}}$ such that for
$\Pi_{n}\sim\operatorname{Mallows}(n,q)$, all $n$ satisfying
$W^{(2)}(\log^{**}\log^{**}n-1)<\log\log n$ and all $c>0$ we have

${\mathbb{P}}(\Pi_{n}\models\varphi)=\begin{cases}1-O(cn^{-2})&\text{if
}\log^{**}\log^{**}n\text{ is even},\\\ O(cn^{-2})&\text{if
}\log^{**}\log^{**}n\text{ is odd}.\end{cases}$ (156)

for all sequences $q=q(n)$ satisfying $0\leq|1-q|\leq cn^{-4}$.

Proposition 6.1 will follow by showing that for $q=1-O(n^{-4})$, a
$\operatorname{Mallows}(n,q)$ distribution is in some sense very close to the
uniform distribution over $S_{n}$.

######  Lemma 7.2.

Let $q$ satisfy $0\neq|1-q|\leq cn^{-4}$ for some $c>0$. For $1\leq i\leq n$
let $Z_{i}\sim\operatorname{TruncGeo}(n-i+1,1-q)$ and
$X_{i}\sim\operatorname{Unif}([n-i+1])$ be independent. Then

$d_{\operatorname{TV}}(Z_{i},X_{i})\leq O(cn^{-3}),\quad\text{as }n\to\infty.$
(157)

###### Proof.

Let $m\coloneqq n-i+1$. By (9) we may write

$\displaystyle
d_{\operatorname{TV}}(Z_{i},X_{i})=\frac{1}{2}\sum\limits_{j=1}^{m}\left|\frac{(1-q)q^{j-1}}{1-q^{m}}-\frac{1}{m}\right|=\frac{1}{2}\sum\limits_{j=1}^{m}\frac{\left|m(1-q)q^{j-1}-(1-q^{m})\right|}{m|1-q^{m}|}.$
(158)

Define $\alpha\coloneqq 1-q$. We may bound the numerator in the summands of
(158) via

$\displaystyle\left|m(1-q)q^{j-1}-(1-q^{m})\right|$
$\displaystyle=\left|m\alpha(1-\alpha)^{j-1}-(1-(1-\alpha)^{m})\right|$ (159)
$\displaystyle=\left|m\alpha(1-j\alpha+O(j^{2}\alpha^{2}))-(1-(1-m\alpha+O(m^{2}\alpha^{2})))\right|$
(160) $\displaystyle=jm\alpha^{2}+O(m^{2}\alpha^{2})$ (161)
$\displaystyle=O(m^{2}\alpha^{2}).$ (162)

So the summands on the right–hand of (158) are all
${O(m\alpha^{2})}/{|1-q^{m}|}$. Now,

$\displaystyle\frac{O(m\alpha^{2})}{|1-(1-\alpha)^{m}|}$
$\displaystyle=\frac{O(m\alpha^{2})}{m\alpha+O(m^{2}\alpha^{2})}=\frac{O(\alpha)}{1+O(m\alpha)}=O(\alpha)\left(1+O(m\alpha)\right)=O(cn^{-4}).$
(163)

Thus $d_{\operatorname{TV}}(Z_{i},X_{i})=O(cmn^{-4})=O(cn^{-3})$. ∎

######  Lemma 7.3.

Let $q$ satisfy $|1-q|\leq cn^{-4}$ for some $c>0$. Let
$\Pi_{n}\sim\operatorname{Mallows}(n,q)$ and
$\Pi^{*}_{n}\sim\operatorname{Mallows}(n,1)$. There is a coupling of $\Pi_{n}$
and $\Pi^{*}_{n}$ such that
${\mathbb{P}}\left(\Pi_{n}\neq\Pi_{n}^{*}\right)=O(cn^{-2})$.

###### Proof.

If $q=1$, then $\Pi_{n}\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\Pi_{n}^{*}$ and the coupling may be achieved for instance
by sampling $\Pi_{n}$ and setting $\Pi^{*}_{n}=\Pi_{n}$. So we now assume that
$q\neq 1$.

Let $\Pi_{n}$ be generated by a sequence $Z_{1},\ldots,Z_{n}$ of independent
random variables with $Z_{i}\sim\operatorname{TruncGeo}(n-i+1,1-q)$ for
$i\in[n]$ (see Section 3.2.1). Let $\Pi_{n}^{*}$ be generated in the same
manner by a sequence $X_{1},\ldots,X_{n}$ of independent random variables
where $X_{i}\sim\operatorname{Unif}([n-i+1])$ for $i\in[n]$. By Lemma 7.2 and
3.4 we may couple $Z_{i}$ and $X_{i}$ for each $i$ such that

${\mathbb{P}}\left(Z_{i}\neq X_{i}\right)\leq O(cn^{-3}),\quad\text{as
}n\to\infty.$ (164)

This gives a coupling of $\Pi_{n}$ and $\Pi^{*}_{n}$. Now,
$\Pi_{n}=\Pi^{*}_{n}$ if and only if $Z_{i}=X_{i}$ for all $i\in[n]$, giving

${\mathbb{P}}\left(\Pi_{n}=\Pi^{*}_{n}\right)\geq 1-O\left(cn^{-2}\right).$
(165)

∎

###### Proof of Proposition 7.1.

Let $q$ satisfy $|1-q|\leq cn^{-4}$ for some $c>0$. Let
$\Pi_{n}\sim\operatorname{Mallows}(n,q)$ and
$\Pi_{n}^{*}\sim\operatorname{Mallows}(n,1)$ be coupled such that

${\mathbb{P}}\left(\Pi_{n}\neq\Pi_{n}^{*}\right)=O(cn^{-2}),$ (166)

This coupling exists by Lemma 7.3. Let $\varphi$ be the
$\operatorname{\mathsf{TOTO}}$ sentence from Proposition 6.1. Then $\Pi_{n}$
and $\Pi_{n}^{*}$ agree on $\varphi$ with probability $1-O(cn^{-2})$, giving
the desired result. ∎

###  7.2 Extending the $q=1\pm O(n^{-4})$ case to $q=1\pm O(1/n)$

The strategy of the current section is as follows. We will show that there is
a formula $\psi(y)$ such that for
$\Pi_{n}\sim\operatorname{Mallows}(n,1-O(n^{-1}))$, with probability
$1-\varepsilon$ there is a unique $j$ such that $\Pi_{n}\models\psi[j]$, and
where also $j=\Theta(n^{1/4})$, see Lemma 7.12. We can then restrict to the
permutation $\Pi_{j}\coloneqq\operatorname{rk}(\Pi_{n}(1),\ldots,\Pi_{n}(j))$
by Lemma 3.26. For such $q$ and $j$ we will then have the bound

$|1-q|=O(n^{-1})=O(j^{-4}),$ (167)

so we may subsequently apply Proposition 7.1 to conclude the proof. To find
this formula $\psi$ with the desired property, we first look for the value
$J_{1}$ which we define as the smallest $j$ such that there is an $i\in[n]$
with $\\{\Pi_{n}(i),\Pi_{n}(i)+1\\}\subseteq\Pi_{n}[[j]]$. For the current
range of $q$, $\Pi_{n}$ is still similar enough to a uniform permutation that
we roughly have

${\mathbb{E}}|\\{i:\\{\Pi_{n}(i),\Pi_{n}(i)+1\\}\subseteq\Pi_{n}[[j]]\\}|\approx
j\cdot j/n.$ (168)

Consequently we will be able to conclude that $J_{1}=\Theta(\sqrt{n})$ with
appropriately high probability. We then restrict to the permutation
$\operatorname{rk}(\Pi_{n}(1),\ldots,\Pi_{n}(J_{1}))$ and repeat this
procedure to find a $K_{1}$ satisfying $K_{1}=\Theta(n^{-1/4})$ again with at
least the right probability for our purposes. We now fill in all the details.

We first show that $q=1-O(1/n)$ is sufficiently close to $1$ that
$\operatorname{TruncGeo}(n,1-q)$ random variables behave somewhat like uniform
random variables. This is made explicit in the next lemma. Recall the
definition of the $\operatorname{TruncGeo}(n,p)$ distribution as given in
(11), valid for $p\in(-\infty,0)\cup(0,1)$.

######  Lemma 7.4.

Let $\alpha=\alpha(n)$ satisfy $|\alpha|\leq c/n$ for some constant $c>0$ and
$q=1-\alpha$. Then there exist $c_{U}=c_{U}(c)>0$ and $c_{L}=c_{L}(c)>0$ such
that for $0\leq i\leq 2n/3$, $J\subseteq[n-i]$ and $n\geq 4c$ we have

$c_{L}\frac{|J|}{n}\leq{\mathbb{P}}\left(\operatorname{TruncGeo}(n-i,1-q)\in
J\right)\leq c_{U}\frac{|J|}{n}.$ (169)

Before we prove Lemma 7.4, we need the following simple result.

######  Lemma 7.5.

If $0\leq x\leq 1/4$ then $1-x\geq e^{-2x}$.

###### Proof.

If $0\leq x\leq\frac{1}{4}$ then $\frac{1}{2}\leq 4^{-2x}\leq e^{-2x}$. So for
$0\leq x\leq\frac{1}{4}$ we have

$e^{-2x}=1-\int_{0}^{x}2e^{-2z}\mathrm{d}z\leq 1-\int_{0}^{x}\mathrm{d}z=1-x.$
(170)

∎

###### Proof of Lemma 7.4.

We consider first the case that $q<1$. Let $k\in J$, and define $m\coloneqq
n-i\geq n/3$. Let $Z_{i}\sim\operatorname{TruncGeo}(m,1-q)$ so that

${\mathbb{P}}\left(Z_{i}=k\right)=\frac{(1-q)q^{k-1}}{1-q^{m}}\quad\text{ for
}k=1,\ldots,m.$ (171)

By $0<q<1$ this is strictly decreasing in $k$. In particular, as $Z_{i}$ has
support $[m]$ we have $(1-q)/(1-q^{m})>1/m$. Thus

${\mathbb{P}}\left(Z_{i}=k\right)>\frac{q^{k-1}}{m}=\frac{(1-\alpha)^{k-1}}{m}.$
(172)

By $n\geq 4c$ we have $\alpha<\frac{1}{4}$. Lemma 7.5 thus gives
${\mathbb{P}}\left(Z_{i}=k\right)\geq{e^{-2k\alpha}}/{m}$. By $k\leq m\leq n$
and $\alpha\leq c/n$ this is at least $e^{-2c}/n$. Thus

${\mathbb{P}}\left(Z_{i}\in J\right)\geq e^{-2c}\frac{|J|}{n}.$ (173)

For the upper bound, note that $(1-\alpha)^{m}<e^{-m\alpha}\leq
e^{-n\alpha/3}$. Thus

$\displaystyle\frac{(1-q)q^{k-1}}{1-q^{m}}<\frac{\alpha
q^{k-1}}{1-e^{-n\alpha/3}}\leq\frac{\alpha}{1-e^{-n\alpha/3}}.$ (174)

To find an upper–bound for this expression, we define
$g(x)\coloneqq{x}/(1-e^{-nx/3})$. We have

$g^{\prime}(x)=\frac{1-e^{-nx/3}-\frac{nx}{3}e^{-nx/3}}{(1-e^{-nx/3})^{2}}=\frac{e^{-nx/3}\left(e^{nx/3}-1-\frac{nx}{3}\right)}{(1-e^{-nx/3})^{2}}$
(175)

By $e^{nx/3}>1+nx/3$ for all $x>0$, $g^{\prime}(x)$ is positive for all $x>0$.
So the maximum of the right–hand side of (174) over $0<\alpha\leq c/n$ is
attained at $c/n$. Therefore

${\mathbb{P}}\left(Z_{i}=k\right)\leq\frac{c}{1-e^{-c/3}}\,\frac{1}{n},$ (176)

and

${\mathbb{P}}\left(Z_{i}\in J\right)\leq\frac{c}{1-e^{-c/3}}\,\frac{|J|}{n}.$
(177)

We now consider the case $q>1$ implying $\alpha<0$. The probability mass
function in (171) is now strictly increasing in $q$, so that
$(1-q)/(1-q^{m})<1/m$ in this case. We thus have the bound

${\mathbb{P}}\left(Z_{i}=k\right)<\frac{(1+|\alpha|)^{k-1}}{m}\leq\frac{e^{k|\alpha|}}{m}.$
(178)

By $k|\alpha|\leq c$ and $m\geq n/3$ this is at most $3e^{c}/n$. Therefore

${\mathbb{P}}\left(Z_{i}\in J\right)\leq 3e^{c}\,\frac{|J|}{n}.$ (179)

For the lower bound, observe that by $(1+|\alpha|)^{m}\leq e^{m|\alpha|}$ we
have

${\mathbb{P}}\left(Z_{i}\in
J\right)\geq|J|\cdot\frac{q-1}{q^{m}-1}=|J|\cdot\frac{|\alpha|}{(1+|\alpha|)^{m}-1}\geq|J|\cdot\frac{|\alpha|}{e^{m|\alpha|}-1}.$
(180)

Let $h(x)\coloneqq x/(e^{mx}-1)$, then

$h^{\prime}(x)=\frac{e^{mx}-1-mxe^{mx}}{(e^{mx}-1)^{2}}=\frac{e^{mx}(1-mx-e^{-mx})}{(e^{mx}-1)^{2}}.$
(181)

As $1-mx<e^{-mx}$ for $x>0$, the above is negative for all $x>0$. So (180) is
minimized at $\alpha=c/n$ giving

${\mathbb{P}}\left(Z_{i}\in
J\right)\geq\frac{c}{e^{cm/n}-1}\,\frac{|J|}{n}\geq\frac{c}{e^{c}-1}\,\frac{|J|}{n}.$
(182)

∎

For $\Pi_{n}\in S_{n}$, recall the definition of $w_{k}(A)$ as given in (122).
We will be examining the quantity $w_{2}([j])$ for $j\in[n]$. For $\Pi_{n}\in
S_{n}$, $m\in[n-1]$ and $j\in{\mathbb{N}}$ we define

$\displaystyle A_{m}(j)$ $\displaystyle\coloneqq|\\{i\leq m:\Pi_{n}(i)\leq
j\\}|,$ (183) $\displaystyle Y_{m}(j)$
$\displaystyle\coloneqq\mathbf{1}_{\\{\Pi_{n}(m),\Pi_{n}(m+1)\leq j\\}}.$
(184)

When the permutation under consideration is ambiguous we will write
$w_{2}([j],\Pi_{n})$, $A_{m}(j,\Pi_{n})$ and $Y_{m}(j,\Pi_{n})$. We note that
$Y_{m}(j)=1$ _cannot_ be queried in $\operatorname{\mathsf{TOTO}}$, as we
cannot make comparisons of the form $\Pi(m)\leq j$. However, we do have

$\displaystyle w_{2}([j],\Pi_{n})$
$\displaystyle\,=\,|\\{i:\\{\Pi_{n}(i),\Pi_{n}(i)+1\\}\subseteq\Pi_{n}[[j]]\\}|$
(185)
$\displaystyle\,=\,|\\{m:\\{\Pi^{-1}_{n}(m),\Pi^{-1}_{n}(m+1)\\}\subseteq[j]\\}|$
(186) $\displaystyle\ \hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\ Y_{1}(j,\Pi_{n})+\ldots+Y_{n-1}(j,\Pi_{n}).$ (187)

Here we used the fact that $\Pi_{n}^{-1}\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\Pi_{n}$ if $\Pi_{n}\sim\operatorname{Mallows}(n,q)$, by
(22).

For the following proofs we will make use of the sampling algorithm for
$\Pi_{n}\sim\operatorname{Mallows}(n,q)$ using a sequence $Z_{1},\ldots,Z_{n}$
of independent random variables with
$Z_{i}\sim\operatorname{TruncGeo}(n-i+1,1-q)$, see Section 3.2.1. In this
procedure, during step $i$ we select $\Pi_{n}(i)$ as the $Z_{i}$-th smallest
number in the set $[n]\setminus\\{\Pi_{n}(1),\ldots,\Pi_{n}(i-1)\\}$. In
particular, when determining $\Pi_{n}(i)$ we have $\Pi_{n}(i)\leq j$ only if
$Z_{i}\leq j$. Moreover, if $A_{m}<j/3$ and $Z_{m}\leq j/2$ then certainly
$\Pi_{n}(m)\leq j$. We will put these facts to work in the proofs of the
following lemmas.

######  Lemma 7.6.

Let $\alpha=\alpha(n)$ satisfy $|\alpha|\leq c/n$ for some constant $c>0$. Let
$q=1-\alpha$, $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ and $1\leq j\leq n$.
Then, with $c_{U}$ as in Lemma 7.4, we have

$\displaystyle{\mathbb{E}}Y_{i}(j,\Pi_{n})$ $\displaystyle\leq
c_{U}^{2}\frac{j^{2}}{n^{2}}\qquad\text{ for }i\in[n-1].$ (188)

###### Proof.

If $Z_{i}>j$, then certainly $\Pi_{n}(i)>j$. Thus, for $i<n$ we have

${\mathbb{E}}Y_{i}={\mathbb{P}}\left(Y_{i}=1\right)\leq{\mathbb{P}}\left(Z_{i}\leq
j\right){\mathbb{P}}\left(Z_{i+1}\leq j\right).$ (189)

For $i<2n/3-1$, by Lemma 7.4 this is at most $c_{U}^{2}j^{2}/n^{2}$.

Now consider the case $i\geq 2n/3$. Recall that we defined the reversal
permutation $r_{n}\in S_{n}$ by $r_{n}:i\to n-i+1$. Let
$\Pi_{n}^{\prime}\coloneqq r_{n}\circ\Pi_{n}\circ r_{n}$ and
$i^{\prime}\coloneqq r_{n}(i)\leq n/3+1$. We observe that

$\displaystyle{\mathbb{P}}\left(\Pi_{n}(i),\Pi_{n}(i+1)\leq j\right)$
$\displaystyle={\mathbb{P}}\left(\Pi_{n}\circ r_{n}(i^{\prime}),\Pi_{n}\circ
r_{n}(i^{\prime}-1)\leq j\right)$ (190)
$\displaystyle={\mathbb{P}}\left(r_{n}\circ\Pi_{n}\circ
r_{n}(i^{\prime}),r_{n}\circ\Pi_{n}\circ r_{n}(i^{\prime}-1)\geq
r_{n}(j)\right).$ (191)

As $r_{n}\circ\Pi_{n}\circ r_{n}\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\Pi_{n}$, $\eqref{eq:P_i__}$ equals
${\mathbb{P}}\left(\Pi_{n}(i^{\prime}),\Pi_{n}(i^{\prime}-1)\geq
r_{n}(j)\right)$. Similarly to before, we have $\Pi_{n}(i^{\prime})\geq n-j+1$
only if $Z_{i^{\prime}}\geq n-i^{\prime}+1-j$. So for $i\geq 2n/3$ we have

$\displaystyle{\mathbb{P}}\left(Y_{i}=1\right)$
$\displaystyle\leq{\mathbb{P}}\left(Z_{i^{\prime}}\geq
n-i^{\prime}+1-j\right){\mathbb{P}}\left(Z_{i^{\prime}-1}\geq
n-i^{\prime}+2-j\right).$ (192)

By Lemma 7.4 we again conclude that ${\mathbb{P}}\left(Y_{i}=1\right)\leq
c_{U}^{2}j^{2}/n^{2}$. ∎

######  Corollary 7.7.

Let $\alpha=\alpha(n)$ satisfy $|\alpha|\leq c/n$ for some constant $c>0$. Let
$q=1-\alpha$, $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ and $1\leq j\leq n$.
Then, with $c_{U}$ as in Lemma 7.4, we have

$\displaystyle{\mathbb{E}}w_{2}([j],\Pi_{n})$ $\displaystyle\leq
c_{U}^{2}\frac{j^{2}}{n}.$ (193)

######  Lemma 7.8.

Let $\alpha=\alpha(n)$ satisfy $|\alpha|\leq c/n$ for some constant $c>0$ and
$q=1-\alpha$. Let $\Pi_{n}\sim\operatorname{Mallows}(n,q)$. Then there exist
$\gamma=\gamma(c)>0$ and $K=K(c)>0$ such that for every $n$ and every $1\leq
j\leq n$

${\mathbb{P}}\left(A_{m}(j,\Pi_{n})<\frac{j}{3}\text{ for all }m<\gamma
n\right)\geq 1-e^{-Kj}.$ (194)

###### Proof.

Let $m=\left\lceil\gamma n\right\rceil$ for $\gamma=\gamma(c)>0$ to be
determined. Let $Z_{1},\ldots,Z_{n}$ be independent random variables
generating $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ with
$Z_{i}\sim\operatorname{TruncGeo}(n-i+1,1-q)$. If less than $j/3$ of the
$Z_{1},\ldots,Z_{m}$ are at most $j$ then indeed $A_{m}<j/3$. Letting
$c_{L}=c_{L}(c)$ and $c_{U}=c_{U}(c)$ be as in Lemma 7.4 we have for $i\leq m$
that

$c_{L}\frac{j}{n}\leq{\mathbb{P}}\left(Z_{i}\leq j\right)\leq
c_{U}\frac{j}{n},$ (195)

provided that $\gamma<2/3$. Let $X_{m}$ be the the number of $Z_{i}$ with
$i\leq m$ such that $Z_{i}\leq j$, so that $A_{m}\leq X_{m}$. Then

$\mu_{m}\coloneqq{\mathbb{E}}X_{m}\geq c_{L}m\frac{j}{n}\geq c_{L}\gamma j,$
(196)

and

$\mu_{m}\leq c_{U}m\frac{j}{n}<c_{U}(\gamma n+1)\frac{j}{n}.$ (197)

By Chernoff’s inequality (Theorem 3.1) with $\varepsilon=1/2$ we have

${\mathbb{P}}\left(X_{m}\geq\frac{3}{2}c_{U}(\gamma
n+1)\frac{j}{n}\right)\leq{\mathbb{P}}\left(X_{m}\geq\frac{3}{2}\mu_{m}\right)\leq\exp\left\\{-\frac{\mu_{m}}{12}\right\\}\leq\exp\left\\{-\frac{c_{L}\gamma
j}{12}\right\\}.$ (198)

Suppose that $n\geq 6c_{U}$ and set
$\gamma=\frac{1}{12c_{U}}\leq\frac{1}{6c_{U}}-\frac{1}{n}$. Then

$\frac{3}{2}c_{u}(\gamma
n+1)\frac{j}{n}\leq\frac{3}{2}c_{U}\left(\frac{n}{6c_{U}}\right)\frac{j}{n}<\frac{j}{3}.$
(199)

Using this $\gamma$ in the right–hand side of (198) we then obtain

${\mathbb{P}}\left(A_{m}\geq\frac{j}{3}\right)\leq{\mathbb{P}}\left(X_{m}\geq\frac{j}{3}\right)\leq\exp\left\\{-\frac{c_{L}j}{144c_{U}}\right\\}.$
(200)

We also have $A_{1}\leq A_{2}\leq\ldots\leq A_{m}$, so the result follows. We
are left with the case $n<6c_{U}$, but then $\gamma n<1$ so that there is in
fact no $m<\gamma n$ if $n<6c_{U}$ in which case the result is vacuously true.
∎

(a) For the permutation $\Pi$ depicted we have $J_{1}(\Pi)=5$. Indeed the set
$W_{2}([5])=\\{i:\\{\Pi(i),\Pi(i)+1\\}\subseteq\Pi[[5]]\\}$ contains exactly
$i=5$ (depicted by red lines) and $i=2$ (depicted by dashed lines), whereas
$W_{2}([4])$ is empty.

(b) The permutation $\Pi_{J_{1}}=\operatorname{rk}(\Pi(1),\ldots,\Pi(5))$. We
have $K_{1}(\Pi)=J_{1}(\Pi_{J_{1}})=3$ as witnessed by the red lines.

Figure 7.1:  An illustration of $J_{1}$ and $K_{1}$

Recall that we have defined

$w_{2}([j],\Pi_{n})\textbf{}\,=\,|\\{i:\\{\Pi_{n}(i),\Pi_{n}(i)+1\\}\subseteq\Pi_{n}[[j]]\\}|.$
(201)

For a permutation $\pi$ and $M\in{\mathbb{N}}$ we define the function

$J_{1}(\pi)=\inf\\{j:w_{2}([j],\pi)\geq 1\\},$ (202)

where we agree as usual that the infimum of the empty set equals $\infty$. We
also define

$K_{1}=J_{1}\left(\Pi_{J_{1}(\Pi_{n})}\right),$ (203)

where
$\Pi_{J_{1}(\Pi_{n})}=\operatorname{rk}(\Pi_{n}(1),\ldots,\Pi_{n}(J_{1}(\Pi_{n}))$.
See Figure 7.1 for an illustration of these definitions. We should note that
$K_{1}$ is technically not always defined, indeed $J_{1}(\Pi_{n})$ may exceed
$n$. However, if $\pi\in S_{n}$ with $n\geq 2$ then $w_{2}([1],\pi)=0$ and
$w_{2}([n],\pi)\geq 1$ so that $J_{1}(\pi)\in\\{2,\ldots,n\\}$ and $K_{1}$ is
finite for all such $\pi$.

######  Lemma 7.9.

Let $\alpha=\alpha(n)$ satisfy $|\alpha|\leq c/n$ for some constant $c>0$. Let
$q=1-\alpha$, $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ and $1\leq j\leq n$.
Then for every $\varepsilon>0$ there exist $0<b_{1}<b_{2}$, depending on
$\varepsilon$ and $c$, such that

${\mathbb{P}}\left(b_{1}\sqrt{n}\leq J_{1}(\Pi_{n})\leq
b_{2}\sqrt{n}\right)>1-\varepsilon,$ (204)

provided that $n\geq n_{0}$ for some $n_{0}$ depending on $\varepsilon$ and
$c$.

###### Proof.

Corollary 7.7 says that ${\mathbb{E}}w_{2}([j],\Pi_{n})\leq c_{U}^{2}j^{2}/n$.
Setting $b_{1}=\sqrt{{\varepsilon}/{2c_{U}^{2}}}$, Markov’s inequality yields

${\mathbb{P}}\left(J_{1}(\Pi_{n})\leq\left\lfloor
b_{1}\sqrt{n}\right\rfloor\right)={\mathbb{P}}\left(w_{2}([\left\lfloor
b_{1}\sqrt{n}\right\rfloor],\Pi_{n})\geq
1\right)\leq\frac{c_{U}^{2}(\left\lfloor
b_{1}\sqrt{n}\right\rfloor)^{2}}{n}\leq\frac{\varepsilon}{2}.$ (205)

For the other bound we will again use the fact that $w_{2}([j],\Pi_{n})\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444ptY_{1}(j,\Pi_{n})+\ldots+Y_{n-1}(j,\Pi_{n})$. We claim that
if $A_{m}<j/3$ and $Z_{m},Z_{m+1}\leq j/2$, then
$Y_{m}(j,\Pi_{n})=\mathbf{1}_{\\{\Pi_{n}(m),\Pi_{n}(m+1)\leq j\\}}=1$. To see
this, note that $A_{m}<j/3$ means that

$\left|[j]\setminus\\{\Pi_{n}(1),\ldots,\Pi_{n}(m)\\}\right|\geq\left\lceil\frac{2j}{3}\right\rceil.$
(206)

In this case, if $Z_{m}\leq j/2$ then
$\Pi_{n}(m)\leq\lfloor\frac{j}{3}\rfloor+\lfloor\frac{j}{2}\rfloor<j$ and if
additionally $Z_{m+1}\leq\frac{j}{2}$ then
$\Pi_{n}(m+1)\leq\lfloor\frac{j}{3}\rfloor+\lfloor\frac{j}{2}\rfloor+1\leq j$.

So let $X_{i}$ be the indicator random variable for the event
$\\{Z_{i},Z_{i+1}\leq\frac{j}{2}\\}$. If $A_{m}\leq j/3$ holds then
$Y_{1}+\ldots+Y_{m}\geq X_{1}+\ldots+X_{m}$. Let $m\coloneqq\left\lfloor\gamma
n\right\rfloor-1$ with $\gamma=\gamma(c)$ as in Lemma 7.8. Let $E$ be the set
of even numbers in $[m]$ and $O$ be the set of odd numbers in $[m]$. For $n$
large enough, depending on $c$, we have $m/3<|E|,|O|<2m/3$. Moreover, the
$X_{i}$ for $i\in E$ are mutually independent, as are the $X_{i}$ for $i\in
O$. By Lemma 7.4 we also have

$\mu_{E}\coloneqq{\mathbb{E}}\left(\sum_{i\in
E}X_{i}\right)\geq|E|c_{L}^{2}\frac{j^{2}}{4n^{2}}\geq
mc_{L}^{2}\frac{j^{2}}{12n^{2}},$ (207)

and the same bound for $\mu_{O}\coloneqq{\mathbb{E}}\left(\sum_{i\in
O}X_{i}\right)$. By Chernoff’s bound (Theorem 3.1 with
$\varepsilon=\frac{1}{2}$) we have

${\mathbb{P}}\left(\sum_{i\in E}X_{i}\leq
mc_{L}^{2}\frac{j^{2}}{24n^{2}}\right)\leq{\mathbb{P}}\left(\sum_{i\in
E}X_{i}\leq\frac{\mu_{E}}{2}\right)\leq\exp\left(-\frac{\mu_{E}}{8}\right)\leq\exp\left(-mc_{L}^{2}\frac{j^{2}}{96n^{2}}\right).$
(208)

We have the same bound replacing $E$ by $O$ in the sums in (208), as we only
used the bounds on $|E|$ and the mutual independence of $X_{i}$ for $i\in E$.
Let $b_{2}$ be for the moment undetermined and set $j=\left\lfloor
b_{2}\sqrt{n}\right\rfloor$. Then

$\frac{mj^{2}}{n^{2}}\geq\frac{(\gamma
n-1)(b_{2}\sqrt{n}-1)^{2}}{n^{2}}=(1+o(1))\frac{\gamma
b_{2}^{2}n^{2}}{n^{2}}.$ (209)

So we can select $b_{2}$ so large that $mc_{L}^{2}\frac{j^{2}}{24n^{2}}>1$ and
such that the right–hand side of (208) is less than $\varepsilon/8$. By
$[m]=E\uplus O$ we have

$\displaystyle{\mathbb{P}}\left(w_{2}([\left\lfloor
b_{2}\sqrt{n}\right\rfloor],\Pi_{n})\leq 1\,|\,A_{m}\leq\frac{j}{3}\right)$
$\displaystyle\leq{\mathbb{P}}\left(\sum_{i\in[m]}X_{i}\leq
1\,|\,A_{m}\leq\frac{j}{3}\right)\leq\frac{\varepsilon}{4\,{\mathbb{P}}\left(A_{m}\leq\frac{j}{3}\right)}.$
(210)

By Lemma 7.8 and our choice of $m$ we have

${\mathbb{P}}\left(w_{2}([\left\lfloor
b_{2}\sqrt{n}\right\rfloor],\Pi_{n})\leq
1\right)\leq\frac{\varepsilon}{4}+e^{-Kj}=\frac{\varepsilon}{4}+e^{-K\left\lfloor
b_{2}\sqrt{n}\right\rfloor},$ (211)

where $K=K(c)$. For $n$ large enough, depending on $\varepsilon$ and $c$, this
is at most $\varepsilon/2$. We note that ${\mathbb{P}}\left(J_{1}>\left\lfloor
b_{2}\sqrt{n}\right\rfloor\right)$ only if $w_{2}([\left\lfloor
b_{2}\sqrt{n}\right\rfloor],\Pi_{n})=0$, giving the desired bound. ∎

We now have an appropriate probabilistic bound on $J_{1}$ that we wist to
extend to $K_{1}$. However, we cannot simply examine the permutation
$\Pi_{J_{1}}$, as exposing the value of $J_{1}$ imposes some constraints on
$\Pi_{J_{1}}$ so that the latter is no longer necessarily distributed as a
Mallows permutation. The next lemma will show that $J_{1}(\Pi_{x})$ is
monotonically increasing in $x$. Now, without exposing $J_{1}$ we have
$J_{1}(\Pi_{\left\lfloor b_{1}\sqrt{n}\right\rfloor})=\Theta(n^{-1/4})$ and
$J_{1}(\Pi_{\left\lceil b_{2}\sqrt{n}\right\rceil})=\Theta(n^{-1/4})$ with
probability at least $1-2\varepsilon$. By the mentioned monotonicity of
$J_{1}(\Pi_{x})$ we can thus sandwich $K_{1}$ within these bounds with
probability at least $1-3\varepsilon$ by the previous lemma. The next two
lemmas provide all details.

######  Lemma 7.10.

For every $n\geq 3$, $2\leq k\leq n-1$ and every $\pi\in S_{n}$ we have

$J_{1}(\pi_{k})\leq J_{1}(\pi_{k+1}),$ (212)

where $\pi_{k}=\operatorname{rk}(\pi(1),\ldots,\pi(k))$ and
$\pi_{k+1}=\operatorname{rk}(\pi(1),\ldots,\pi(k+1))$.

###### Proof.

As $J_{1}(\pi_{k})\leq k$, we need only consider the case
$J_{1}(\pi_{k+1})=a<k$. Then $w_{2}([a],\pi_{k+1})\geq 1$ so there is some
$i\in[k+1]$ such that $\pi_{k+1}(i)$ and $\pi_{k+1}(i)+1$ are both contained
in $\pi_{k+1}[[a]]$. This implies that $i\in[a]\subseteq[k-1]$ and
$\pi_{k+1}(i)+1=\pi_{k+1}(a_{0})$ for some $a_{0}\in[a]$, which in turn
implies
$\mathbf{1}_{\\{\pi(k+1)<\pi(i)\\}}=\mathbf{1}_{\\{\pi(k+1)<\pi(a_{0})\\}}$.
Thus

$\displaystyle\pi_{k}(i)+1=\pi_{k+1}(i)+1-\mathbf{1}_{\\{\pi(k+1)<\pi(i)\\}}=\pi_{k+1}(a_{0})-\mathbf{1}_{\\{\pi(k+1)<\pi(a_{0})\\}}=\pi_{k}(a_{0}).$
(213)

Thus $\pi_{k}(i)\in\pi_{k}[[a]]$ and
$\pi_{k}(i)+1=\pi_{k}(a_{0})\in\pi_{k}[[a]]$. So $J_{1}(\pi_{k})\leq a$. ∎

######  Lemma 7.11.

Let $\alpha=\alpha(n)$ satisfy $|\alpha|\leq c/n$ for some constant $c>0$. Let
$q=1-\alpha$ and $\Pi_{n}\sim\operatorname{Mallows}(n,q)$. Then for every
$\varepsilon>0$ there exist positive constants $b_{1}^{\prime},b_{2}^{\prime}$
such that

${\mathbb{P}}\left(b_{1}^{\prime}n^{1/4}\leq K_{1}(\Pi_{n})\leq
b_{2}^{\prime}n^{1/4}\right)>1-\varepsilon,$ (214)

provided that $n\geq n_{0}$ for some $n_{0}$ depending on $\varepsilon$ and
$c$.

###### Proof.

By Lemma 7.9 there exists $0<b_{1}<b_{2}$ depending on $\varepsilon$ and $c$
such that

${\mathbb{P}}\left(b_{1}\sqrt{n}\leq J_{1}(\Pi_{n})\leq
b_{2}\sqrt{n}\right)\geq 1-\frac{\varepsilon}{3}.$ (215)

Denote the event above by $E$. Define $k_{1}=\left\lfloor
b_{1}\sqrt{n}\right\rfloor$, $k_{2}=\left\lceil b_{2}\sqrt{n}\right\rceil$ and
$\Pi_{k_{1}}=\operatorname{rk}(\Pi_{n}(1),\ldots,\Pi_{n}(k_{1}))$ and
similarly $\Pi_{k_{2}}$. Conditional on $E$, by $k_{1}\leq k_{2}$ and Lemma
7.10 we have

$J_{1}(\Pi_{k_{1}})\leq K_{1}(\Pi_{n})\leq J_{1}(\Pi_{k_{2}}).$ (216)

By Lemma 3.10 we have $\Pi_{k_{1}}\sim\operatorname{Mallows}(k_{1},q)$ where

$|1-q|\leq\frac{c}{n}\leq\frac{cb_{1}}{k_{1}^{2}}.$ (217)

Similarly $\Pi_{k_{2}}\sim\operatorname{Mallows}(k_{2},q)$ with $|1-q|\leq
cb_{2}/k_{2}^{2}$. Lemma 7.9 says that there are
$b_{1}^{\prime\prime},b_{2}^{\prime\prime}$ depending on $\varepsilon$ and $c$
(and on $b_{1}$ and $b_{2}$ which themselves depend on $\varepsilon$ and $c$)
such that

$\displaystyle{\mathbb{P}}\left(b_{1}^{\prime\prime}\sqrt{k_{1}}\leq
J_{1}(\Pi_{k_{1}})\right)$ $\displaystyle\geq 1-\frac{\varepsilon}{3},$ (218)
$\displaystyle{\mathbb{P}}\left(b_{2}^{\prime\prime}\sqrt{k_{2}}\geq
J_{1}(\Pi_{k_{2}})\right)$ $\displaystyle\geq 1-\frac{\varepsilon}{3},$ (219)

provided that $k_{1}$ and $k_{2}$ both exceed some lower bound depending on
$\varepsilon$ and $c$. These bounds together with (216) and
${\mathbb{P}}\left(E\right)>1-\varepsilon/3$ give

${\mathbb{P}}\left(b_{1}^{\prime\prime}\sqrt{b_{1}}n^{1/4}\leq
K_{1}(\Pi_{n})\leq b_{2}^{\prime\prime}\sqrt{b_{2}}n^{1/4}\right)\geq
1-\varepsilon.$ (220)

∎

######  Lemma 7.12.

There exists a $\operatorname{\mathsf{TOTO}}$ formula $\psi$ such that the
following holds: Let $\alpha=\alpha(n)$ satisfy $|\alpha|\leq c/n$ for some
constant $c>0$, and $\Pi_{n}\sim\operatorname{Mallows}(n,1-\alpha)$. Then for
every $\varepsilon>0$ there exist positive constants
$b_{1}^{\prime},b_{2}^{\prime}$ such that with probability at least
$1-\varepsilon$, there is a unique $j$ such that $\Pi_{n}\models\psi[j]$, and
this unique $j$ satisfies the bounds

$b_{1}^{\prime}n^{1/4}\leq j\leq b_{2}^{\prime}n^{1/4},$ (221)

provided that $n\geq n_{0}$ for some $n_{0}$ depending on $\varepsilon$ and
$c$.

###### Proof.

We have already found a formula that determines whether $i\in
W_{2}([j],\Pi_{n})$ in (123), call this formula $\zeta(i,j)$. Then
${J}_{1}=j_{1}\in[n]$ if and only if $\Pi_{n}\models\xi[j_{1}]$ where

$\xi(x)\coloneqq\exists z(\zeta(z,x))\wedge\forall
w\left(w<_{1}x\rightarrow\neg\exists z\left(\zeta(z,w)\right)\right).$ (222)

We now define the formula

$\psi(x)\coloneqq\exists
z\left(\xi(z)\wedge(x\leq_{1}z)\wedge\xi^{\leq}(z,x)\right),$ (223)

where $\xi^{\leq}$ is the relativization of $\xi$, see Lemma 3.24. By Lemma
3.26, $K_{1}=j\in[n]$ if and only if $\Pi_{n}\models\psi[j]$, and such a
unique $j$ always exists (as long as $n\geq 2$). By Lemma 7.11 there are
$b_{1}^{\prime},b_{2}^{\prime}$ depending on $\varepsilon$ and $c$ such that
this $j$ also satisfies (221) with probability at least $1-\varepsilon$. ∎

######  Proposition 7.13.

Let $\alpha=\alpha(n)$ satisfy $|\alpha|\leq c/n$ for some constant $c>0$. Let
$q=1-\alpha$ and $\Pi_{n}\sim\operatorname{Mallows}(n,q)$. Then there is a
sentence $\omega\in\operatorname{\mathsf{TOTO}}$ such that for all $n$
satisfying $W^{(2)}(\log^{**}\log^{**}n-1)<\log^{*}n$ we have

${\mathbb{P}}(\Pi_{n}\models\omega)=\begin{cases}>\frac{9}{10}-O(n^{-1/4})&\text{if
}\log^{**}\log^{**}n\text{ is even},\\\ <\frac{1}{10}+O(n^{-1/4})&\text{if
}\log^{**}\log^{**}n\text{ is odd},\end{cases}$ (224)

where the implicit constants in the $O(n^{-1/4})$ terms depend on $c$.

###### Proof.

Let $\psi$ be as in Lemma 7.12 and let $\varphi$ be the sentence provided by
Proposition 7.1. We define the sentence

$\omega\coloneqq\exists z\left(\psi(z)\wedge\varphi^{\leq}(z)\right),$ (225)

where $\varphi^{\leq}$ is the relativization of $\varphi$ as in Lemma 3.24.

Set $\varepsilon=\frac{1}{10}$. Let $0<b_{1}^{\prime}<b_{2}^{\prime}$, both
depending on $c$, be as in Lemma 7.12. Let $E$ be the event that there is a
unique $j$ such that $\Pi_{n}\models\psi[j]$ and that this unique $j$
satisfies (221). We have ${\mathbb{P}}\left(E\right)>\frac{9}{10}$ by Lemma
7.12. Letting $\Pi_{j}=\operatorname{rk}(\Pi_{n}(1),\ldots,\Pi_{n}(j))$ if $E$
holds, we have by Lemma 3.26 that

$\displaystyle{\mathbb{P}}\left(\Pi_{n}\models\omega\right)$
$\displaystyle\geq\frac{9}{10}\cdot{\mathbb{P}}\left(\Pi_{j}\models\varphi\,|\,E\right),$
(226) $\displaystyle{\mathbb{P}}\left(\Pi_{n}\not\models\omega\right)$
$\displaystyle\geq\frac{9}{10}\cdot{\mathbb{P}}\left(\Pi_{j}\not\models\varphi\,|\,E\right).$
(227)

We will first show that conditional on $E$, the condition
$W^{(2)}(\log^{**}\log^{**}n-1)<\log^{*}n$ implies that
$\log^{**}\log^{**}n=\log^{**}\log^{**}j$ and
$W^{(2)}(\log^{**}\log^{**}j-1)<\log\log j$, at least for $n$ larger than some
lower bound depending on $b_{1}^{\prime}$ and $b_{2}^{\prime}$. Note that
$W^{(2)}(\log^{**}\log^{**}n-1)<\log^{*}n$ implies

$\log^{**}\log^{**}n-1<\log^{**}\log^{**}\log^{*}n\leq\log^{**}\log^{**}n.$
(228)

This forces the second inequality to be an equality. If $n\geq j\geq
b_{1}^{\prime}n^{1/4}>\log^{*}n$, then conditional on $E$ we indeed have that
$\log^{**}\log^{**}j=\log^{**}\log^{**}n$. For $n$ exceeding some lower bound
depending on $b^{\prime}_{1}$, we also have $\log^{*}n<\log\log
b_{1}^{\prime}n^{1/4}$, so that in this case the event $E$ implies

$W^{(2)}(\log^{**}\log^{**}n-1)=W^{(2)}(\log^{**}\log^{**}j-1)<\log^{*}n<\log\log
b_{1}^{\prime}n^{1/4}\leq\log\log j.$ (229)

Consider then the case $\log^{**}\log^{**}n$ even and let
$\ell\coloneqq\left\lceil b_{1}^{\prime}n^{1/4}\right\rceil$ and
$u\coloneqq\left\lfloor b_{2}^{\prime}n^{1/4}\right\rfloor$. For every
$\ell\leq m\leq u$ we have
$\Pi_{m}\coloneqq\operatorname{rk}(\Pi_{n}(1),\ldots,\Pi_{n}(m))\sim\operatorname{Mallows}(m,q)$,
where

$|1-q|\leq\frac{c}{n}\leq\frac{cb_{2}^{\prime 4}}{m^{4}}.$ (230)

Thus, Proposition 7.1 yields

${\mathbb{P}}\left(\Pi_{j}\models\varphi\,|\,E\right)\geq{\mathbb{P}}\left(\bigwedge\limits_{m=\ell}^{u}\Pi_{m}\models\varphi\right)\geq
1-\sum\limits_{m=\ell}^{u}{\mathbb{P}}\left(\Pi_{m}\not\models\varphi\right)\geq
1-u\,O(cb_{2}^{\prime 4}\ell^{-2}).$ (231)

We conclude that

${\mathbb{P}}\left(\Pi_{n}\models\omega\right)\geq\frac{9}{10}-O(n^{-1/4}).$
(232)

We consider now the case $\log^{**}\log^{**}n$ odd. Again, conditioning on
$E$, we are in the second case of Proposition 7.1 for $n$ large enough. We
again have
${\mathbb{P}}\left(\Pi_{n}\not\models\omega\right)\geq\frac{9}{10}\,{\mathbb{P}}\left(\Pi_{j}\not\models\varphi\,|\,E\right)$.
The same calculations as in (231) show that in this case
${\mathbb{P}}\left(\Pi_{n}\not\models\omega\right)>\frac{9}{10}-O(n^{-1/4})$.
∎

###  7.3 Lifting to $|1-q|<1/\log^{*}n$

In the section we finalize the proof of Theorem 1.2 Part (ii) by extending the
results of the previous sections to
$1-\frac{1}{\log^{*}n}<q<1+\frac{1}{\log^{*}n}$. We will proceed as follows:
We partition the interval $(1-\frac{1}{\log^{*}n},1+\frac{1}{\log^{*}n})$ into
the parts

${\mathcal{D}}_{1}\coloneqq\left(1-\frac{1}{\log^{*}n},1-\frac{c}{n}\right),\
\ {\mathcal{D}}_{2}\coloneqq\left[1-\frac{c}{n},1+\frac{c}{n}\right],\ \
{\mathcal{D}}_{3}\coloneqq\left(1+\frac{c}{n},1+\frac{1}{\log^{*}n}\right).$
(233)

With foresight we set $c=50$. We will find $\operatorname{\mathsf{TOTO}}$
sentences $\rho,\xi_{1}$ and $\xi_{2}$ and disjoint infinite sets
$A^{-},A^{+}\subsetneq{\mathbb{N}}$ such that all bounds in Table 1 hold.
Before we show the existence of such sentences with the desired properties, we
show how they imply Theorem 1.2 Part (ii).

|  | $1-\frac{1}{\log^{*}n}<q<1-\frac{50}{n}$ | $|1-q|\leq\frac{50}{n}$ | $1+\frac{50}{n}<q<1+\frac{1}{\log^{*}n}$
---|---|---|---|---
$n>50$ | ${\mathbb{P}}(\Pi_{n}\models\rho)$ | $\leq 0.1$ |  | $\geq 0.9$
$n\in A^{+}$ | ${\mathbb{P}}(\Pi_{n}\models\xi_{1})$ | $\geq 0.8$ | $\geq 0.8$ |
${\mathbb{P}}(\Pi_{n}\models\xi_{2})$ |  | $\geq 0.8$ | $\geq 0.8$
$n\in A^{-}$ | ${\mathbb{P}}(\Pi_{n}\models\xi_{1})$ | $\leq 0.2$ | $\leq 0.2$ |
${\mathbb{P}}(\Pi_{n}\models\xi_{2})$ |  | $\leq 0.2$ | $\leq 0.2$
Table 1:  We find $\operatorname{\mathsf{TOTO}}$ sentences $\rho,\xi_{1}$ and
$\xi_{2}$ and two disjoint infinite set $A^{-},A^{+}\subsetneq{\mathbb{N}}$
such that the probability that $\Pi_{n}\sim\operatorname{Mallows}(n,q)$
satisfies each of the sentences is as shown.

###### Proof of Theorem 1.2 Part (ii).

We may assume that $A^{-}$ and $A^{+}$ contain only numbers exceeding $50$, so
that the bounds on ${\mathbb{P}}\left(\Pi_{n}\models\rho\right)$ in Table 1
hold for all $n\in A^{-}\uplus A^{+}$. Let

$\varphi\coloneqq\left(\rho\rightarrow\xi_{2}\right)\wedge((\neg\rho)\rightarrow\xi_{1}).$
(234)

As $\Pi_{n}$ satisfies exactly one of $\rho$ and $\neg\rho$, any of the three
events

$E_{1}\coloneqq\\{\Pi_{n}\models(\neg\rho)\wedge\xi_{1}\\},\quad
E_{2}\coloneqq\\{\Pi_{n}\models(\xi_{1}\wedge\xi_{2})\\}\quad\text{or}\quad
E_{3}\coloneqq\\{\Pi_{n}\models\rho\wedge\xi_{2}\\}$ (235)

imply that $\Pi_{n}\models\varphi$. For $n\in A^{+}$, by the bounds in Table 1
we have that

$\displaystyle\text{if }\quad
q\in{\mathcal{D}}_{1}\quad\text{then}\quad{\mathbb{P}}\left(E_{1}\right)$
$\displaystyle\geq 1-0.1-0.2=0.7,$ (236) $\displaystyle\text{if }\quad
q\in{\mathcal{D}}_{2}\quad\text{then}\quad{\mathbb{P}}\left(E_{2}\right)$
$\displaystyle\geq 1-0.2-0.2=0.6,$ (237) $\displaystyle\text{if }\quad
q\in{\mathcal{D}}_{3}\quad\text{then}\quad{\mathbb{P}}\left(E_{3}\right)$
$\displaystyle\geq 1-0.1-0.2=0.7.$ (238)

In general, for $n\in A^{+}$ and
$q\in(1-\frac{1}{\log^{*}n},1+\frac{1}{\log^{*}n})={\mathcal{D}}_{1}\uplus{\mathcal{D}}_{2}\uplus{\mathcal{D}}_{3}$
we have ${\mathbb{P}}\left(\Pi_{n}\models\varphi\right)\geq 0.6$.

We now consider $n\in A^{-}$. Note that the three events

$F_{1}\coloneqq\\{\Pi_{n}\not\models\rho\wedge\Pi_{n}\not\models\xi_{1}\\},\quad
F_{2}\coloneqq\\{\Pi_{n}\not\models(\xi_{1}\vee\xi_{2})\\}\quad\text{and}\quad
F_{3}\coloneqq\\{\Pi_{n}\models\rho\wedge\Pi_{n}\not\models\xi_{2}\\}$ (239)

now each imply that $\Pi_{n}\not\models\varphi$. For $n\in A^{-}$ the bounds
in Table 1 now give that

$\displaystyle\text{if }\quad
q\in{\mathcal{D}}_{1}\quad\text{then}\quad{\mathbb{P}}\left(F_{1}\right)$
$\displaystyle\geq 1-0.1-0.2=0.7,$ (240) $\displaystyle\text{if }\quad
q\in{\mathcal{D}}_{2}\quad\text{then}\quad{\mathbb{P}}\left(F_{2}\right)$
$\displaystyle\geq 1-0.2-0.2=0.6,$ (241) $\displaystyle\text{if }\quad
q\in{\mathcal{D}}_{3}\quad\text{then}\quad{\mathbb{P}}\left(F_{3}\right)$
$\displaystyle\geq 1-0.1-0.2=0.7.$ (242)

So for $n\in A^{-}$ and $q\in(1-1/\log^{*}n,1+1/\log^{*}n)$ we have
${\mathbb{P}}\left(\Pi_{n}\not\models\varphi\right)\geq 0.6$.

As both $A^{-}$ and $A^{+}$ have infinite cardinality, we conclude that
${\mathbb{P}}\left(\Pi_{n}\models\varphi\right)$ does not have a limit as
$n\to\infty$ for any sequence $q=q(n)$ satisfying
$1-1/\log^{*}n<q<1+1/\log^{*}n$. ∎

So it remains to find $\rho,\xi_{1},\xi_{2},A^{-}$ and $A^{+}$ and prove the
bounds in Table 1. We start by defining the $\operatorname{\mathsf{TOTO}}$
sentence $\rho$ as

$\rho=\exists xy\left(\neg\exists
w(\mathsf{succ}_{1}(w,x)\vee\mathsf{succ}_{1}(y,w))\wedge(y<_{2}x)\right).$
(243)

If $n\geq 1$, then there always exist unique $x$ and $y$ such that
$\neg\exists w(\mathsf{succ}_{1}(w,x)\vee\mathsf{succ}_{1}(y,w))$, namely
$x=1$ and $y=n$ the largest element in $[n]$. Then $\Pi_{n}\models\rho$
precisely when $\Pi_{n}(1)>\Pi_{n}(n)$.

######  Lemma 7.14.

Let $\Pi_{n}\sim\operatorname{Mallows}(n,q)$. For every $n>50$ we have

$\displaystyle{\mathbb{P}}\left(\Pi_{n}\not\models\rho\right)$
$\displaystyle\geq 0.9\qquad\text{ if }q<1-\frac{50}{n},$ (244)
$\displaystyle{\mathbb{P}}\left(\Pi_{n}\models\rho\right)$ $\displaystyle\geq
0.9\qquad\text{ if }q>1+\frac{50}{n}.$ (245)

###### Proof.

Recall once more the definition of $\operatorname{TruncGeo}(n,p)$ random
variables as in (11), valid for $p\in(-\infty,0)\cup(0,1)$.

We first consider the case $q>1+50/n$. Recall that we defined the mapping
$r_{n}:[n]\to[n]$ by $r_{n}:i\to n-i+1$. By $r_{n}(1)=n$ we may estimate

${\mathbb{P}}\left(\Pi_{n}(n)\geq\frac{n}{3}+1\right)={\mathbb{P}}\left((r_{n}\circ\Pi_{n}\circ
r_{n})(1)\leq
n-\frac{n}{3}\right)={\mathbb{P}}\left(\Pi_{n}(1)\leq\frac{2n}{3}\right),$
(246)

where we used the fact that $r_{n}\circ\Pi_{n}\circ r_{n}\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\Pi_{n}$. Using this estimate we have

${\mathbb{P}}\left(\Pi_{n}\models\rho\right)\geq{\mathbb{P}}\left(\Pi_{n}(1)>\frac{2n}{3}\text{
and }\Pi_{n}(n)<\frac{n}{3}+1\right)\geq
1-2\cdot{\mathbb{P}}\left(\Pi_{n}(1)\leq\frac{2n}{3}\right).$ (247)

The value $\Pi_{n}(1)$ follows a $\operatorname{TruncGeo}(n,1-q)$
distribution, so that

$\displaystyle{\mathbb{P}}\left(\Pi_{n}\models\rho\right)$
$\displaystyle>1-2\cdot\frac{q-1}{q^{n}-1}\sum\limits_{i=0}^{\left\lfloor
2n/3\right\rfloor}q^{i}$ (248) $\displaystyle=1-2\cdot\frac{q^{\left\lfloor
2n/3\right\rfloor+1}-1}{q^{n}-1}$ (249)
$\displaystyle>1-2\cdot\frac{q^{3n/4}-1}{q^{n}-1}.$ (250)

The last inequality holds as $n>50$ implies that $\left\lfloor
2n/3\right\rfloor+1<3n/4$. Now, for all $1<x<y$ it holds that
$\frac{x-1}{y-1}<\frac{x}{y}$, so that $1<q<q^{n}$ implies

${\mathbb{P}}\left(\Pi_{n}\models\rho\right)>1-2q^{-n/4}>1-2\left(1+\frac{50}{n}\right)^{-n/4}.$
(251)

By $n>50$, the latter quantity is at least $1-2\cdot 2^{-n/4}>1-2\cdot
2^{-12.5}>0.9$.

Now suppose that $q<1-50/n$ and that $n>50$. Then

$\frac{1}{q}>\frac{1}{1-\frac{50}{n}}=\sum_{i\geq
0}\left(\frac{50}{n}\right)^{i}>1+\frac{50}{n}.$ (252)

Recalling that for $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ we have
$r_{n}\circ\Pi_{n}\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\operatorname{Mallows}(n,1/q)$ gives

${\mathbb{P}}\left(\Pi_{n}\not\models\rho\right)={\mathbb{P}}\left(r_{n}\circ\Pi_{n}\models\rho\right)>0.9.$
(253)

∎

We now build up a collection of results that will allow us to find $\xi_{1}$
and $\xi_{2}$ with the desired properties. For the next few lemmas we will
consider $c=100$ instead of $50$ to simplify some of the manipulations later
on.

######  Lemma 7.15.

Let $q=q(n)$ be such that $1-100/n\leq q\leq 1+100/n$. Then there exists an
absolute constant $c_{1}>0$ such that for
$\Pi_{n}\sim\operatorname{Mallows}(n,q)$ and $n\geq 400$ we have

${\mathbb{P}}\left(c_{1}n\leq\Pi_{n}^{-1}(1)\right)>0.99.$ (254)

###### Proof.

If $q=1$, then $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ is uniformly
distributed over $S_{n}$. Then $\Pi_{n}^{-1}(1)$ is uniformly distributed over
$[n]$ and such $c_{1}$ clearly exists.

So let $q\neq 1$. As before, we note that $\Pi_{n}^{-1}\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\Pi_{n}$ so that also $\Pi_{n}^{-1}(1)\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\Pi_{n}(1)\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444ptZ_{1}$ where ${Z_{1}\sim\operatorname{TruncGeo}(n,1-q)}$.
By Lemma 7.4 there is a $c_{U}>0$ such that for $n\geq 400$ we have

${\mathbb{P}}\left(Z_{1}<c_{1}n\right)\leq c_{U}\frac{\left\lfloor
c_{1}n\right\rfloor}{n}.$ (255)

For $c_{1}$ small enough this is less than $0.01$. ∎

######  Lemma 7.16.

There exist constants $0<c_{1}<c_{2}$ and $n_{0}$ such that for $n\geq n_{0}$
and any sequence $q=q(n)$ satisfying $1-1/\log^{*}n<q<1-100/n$, the random
permutation $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ satisfies

$\displaystyle{\mathbb{P}}\left(\frac{c_{1}}{1-q}\leq\Pi_{n}^{-1}(1)\leq\frac{c_{2}}{1-q}\right)>0.99.$
(256)

###### Proof.

We again have $\Pi_{n}^{-1}(1)\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444ptZ_{1}$ where ${Z_{1}\sim\operatorname{TruncGeo}(n,1-q)}$.
Therefore the inequalities $q<1-100/n<e^{-100/n}<1$ imply that

${\mathbb{P}}\left(\Pi_{n}^{-1}(1)<\frac{c_{1}}{1-q}\right)\leq\frac{1-q}{1-q^{n}}\sum\limits_{i=1}^{\left\lfloor\frac{c_{1}}{1-q}\right\rfloor}q^{i-1}<\frac{c_{1}}{1-q^{n}}<\frac{c_{1}}{1-e^{-100}}.$
(257)

Clearly the above is less than $0.005$ for $c_{1}$ small enough.

For the remaining bound, Markov’s inequality gives

${\mathbb{P}}\left(\Pi^{-1}(1)>\frac{c_{2}}{1-q}\right)={\mathbb{P}}\left(\Pi^{-1}(1)-1>\frac{c_{2}-1+q}{1-q}\right)\leq\frac{(1-q){\mathbb{E}}(\Pi_{n}^{-1}(1)-1)}{c_{2}-1+q}.$
(258)

Theorem 3.15 implies that
${\mathbb{E}}(\Pi^{-1}_{n}(1)-1)\leq\min(\frac{2q}{1-q},n-1)\leq\frac{2}{1-q}$.
So

${\mathbb{P}}\left(\Pi^{-1}(1)>\frac{c_{2}}{1-q}\right)\leq\frac{2}{c_{2}-1+q}<\frac{2}{c_{2}-\frac{1}{\log^{*}n}}.$
(259)

For $n$ and $c_{2}$ large enough the above is less than $0.005$, finishing the
proof. ∎

We now combine the previous two lemmas into a form that will be convenient for
us.

######  Lemma 7.17.

There exist absolute constants $n_{1},c_{1},c_{2}$ and a
$\operatorname{\mathsf{TOTO}}$ formula $\lambda(y)$ with one free variable $y$
such that the following holds: For $1-1/\log^{*}n<q<1+100/n$ and
$\Pi_{n}\sim\operatorname{Mallows}(n,q)$, if $n\geq n_{1}$, then

  1. (i)

$\Pi_{n}\models\lambda[x]$ if and only if $\Pi_{n}(x+1)=1$;

  2. (ii)

${\mathbb{P}}\left(\left\\{\exists x\text{ s.t. }\Pi_{n}(x+1)=1\text{ and
}x\geq c_{1}\log^{*}n\text{ and }|1-q|\leq\frac{c_{2}}{x}\right\\}\right)\geq
0.99.$ (260)

###### Proof.

Let $\lambda(y)$ be the formula

$\lambda(y)\coloneqq\exists z\ (\mathsf{succ}_{1}(y,z)\wedge\neg\exists w\
(w<_{2}z)).$ (261)

Then $\Pi_{n}\models\lambda[N]$ if and only if the successor under $<_{1}$ of
$N$ is the smallest number under the ordering $<_{2}$, that is, if and only if
$\Pi_{n}(N+1)=1$. So let $N=\Pi^{-1}_{n}(1)-1$.

We consider two cases. First suppose that $1-100/n\leq q\leq 1+100/n$. By
Lemma 7.15 there is a $c_{1}$ such that for $n$ large enough we have $N\geq
c_{1}n-1>c_{1}\log^{*}n$ with probability at least $0.99$. Moreover, by $N\leq
n$ we have $|1-q|\leq 100/n\leq 100/N$. This finishes the first case.

Suppose then that $1-1/\log^{*}n<q<1-100/n$. By Lemma 7.16 there are absolute
$c_{1},c_{2}$ such that with probability at least $0.99$ we have

$\frac{c_{1}}{1-q}\leq N+1\leq\frac{c_{2}}{1-q}.$ (262)

The first inequality gives $N\geq\frac{c_{1}}{1-q}-1>c_{1}\log^{*}n-1$. For
$n$ large enough (depending on the absolute constant $c_{1}$) this is at
least, say, $\frac{c_{1}}{2}\log^{*}n$. The second inequality gives $0<1-q\leq
c_{2}/N$. This finishes the second case as well. ∎

We will need the following algebraic lemma before we can turn to the existence
of $\xi_{1},\xi_{2}$ as advertised at the start of this section. Recall the
definitions of $W(\cdot)$ and $T(\cdot)$ from Section 3.4.

######  Lemma 7.18.

Let $c_{1}$ be as given in Lemma 7.17. Then there exists an $m\in{\mathbb{N}}$
such that the following holds: Let $t\geq m$, set $n\coloneqq W^{(2)}(t)$ and
let $N$ satisfy $c_{1}\log^{*}n\leq N\leq n$. Then

$W^{(2)}(\log^{**}\log^{**}N-1)<\log^{*}N,$ (263)

and

$\log^{**}\log^{**}N=t.$ (264)

###### Proof.

First, let $m>3$ so that by Lemma 3.29 the inequality

$T^{(3)}\circ W^{(2)}(t-1)<W^{(2)}(t)$ (265)

holds for all $t\geq m$. We may also select $m$ so large that for all $t\geq
m$

$c_{1}\,T^{(2)}\circ W^{(2)}(t-1)>T\circ W^{(2)}(t-1).$ (266)

We claim that any $m$ satisfying these two conditions is as desired. To see
this, let $t\geq m$, $n=W^{(2)}(t)$ and $c_{1}\log^{*}n\leq N\leq n$. The
inequalities (266) and (265) imply that

$N\geq c_{1}\log^{*}W^{(2)}(t)>c_{1}\log^{*}(T^{(3)}\circ W^{(2)}(t-1))>T\circ
W^{(2)}(t-1).$ (267)

Thus

$\displaystyle\log^{**}\log^{**}N$ $\displaystyle\geq\log^{**}\log^{**}(T\circ
W^{(2)}(t-1))>t-1.$ (268)

As we trivially have $\log^{**}\log^{**}N\leq\log^{**}\log^{**}n=t$, we
conclude that $\log^{**}\log^{**}N=t$. Moreover, (267) also implies that

$\displaystyle\log^{*}N>W^{(2)}(t-1)=W^{(2)}(\log^{**}\log^{**}N-1).$ (269)

∎

For what follows, we let $S_{0}$ be the set containing only the empty
permutation; that is, the $\operatorname{\mathsf{TOTO}}$ structure with empty
domain. We let $\operatorname{Mallows}(0,q)$ be the degenerate distribution
with support $S_{0}$.

######  Lemma 7.19.

Let $0<q\leq 1$ and $\Pi_{n}\sim\operatorname{Mallows}(n,q)$. If
$N:=\Pi_{n}^{-1}(1)-1$ and
$\Pi_{N}:=\operatorname{rk}(\Pi_{n}(1),\dots,\Pi_{n}(N))$, then

$\Pi_{N}\hskip
0.86108pt\raisebox{-0.43057pt}{$=$}\raisebox{4.30554pt}{{$\scriptstyle
d$}}\hskip 3.44444pt\operatorname{Mallows}(N,q),$ (270)

(I.e., we generate a Mallows distribution with $n$ random.)

###### Proof.

Let $0\leq m<n$ and $\pi\in S_{m}$, we will determine the distribution of
$\Pi_{N}$ conditional on $N=m$. If $m=0$, then we trivially have
$\Pi_{m}\sim\operatorname{Mallows}(m,q)$, so we may consider $m\geq 1$. We
have for each $\pi\in S_{m}$

${\mathbb{P}}\left(\Pi_{m}=\pi\,|\,N=m\right)=\frac{{\mathbb{P}}\left(\Pi_{m}=\pi\text{
and }N=m\right)}{{\mathbb{P}}\left(N=m\right)}$ (271)

If $N=m$, then $\Pi(m+1)=1$. So the two events $\\{\Pi_{m}=\pi\\}$ and
$\\{N=m\\}$ imply that $(i,m)$ is an inversion of $\Pi_{m+1}$ for every $i\leq
m$. That is, conditioning on these two events we have
$\operatorname{inv}(\Pi_{m+1})=\operatorname{inv}(\pi)+m$. We obtain that

${\mathbb{P}}\left(\Pi_{m}=\pi\,|\,N=m\right)=\frac{q^{\operatorname{inv}(\pi)}}{F(m,q)},$
(272)

for some function $F(m,q)$. In fact, summing the above over all $\pi\in S_{m}$
gives one, so that $F(m,q)$ necessarily equals $\sum_{\pi\in
S_{m}}q^{\operatorname{inv}(\pi)}$. ∎

We are now ready to show the existence of $\xi_{1}$ satisfying the bounds in
Table 1.

######  Lemma 7.20.

There exists a sentence $\xi_{1}\in\operatorname{\mathsf{TOTO}}$ and two
infinite disjoint sets $A^{+},A^{-}\subseteq{\mathbb{N}}_{>100}$ such that for

$1-\frac{1}{\log^{*}n}\leq q<1+\frac{100}{n}$ (273)

and $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ we have

$\displaystyle{\mathbb{P}}\left(\Pi_{n}\models\xi_{1}\right)$
$\displaystyle>0.8,\quad\text{if }\ n\in A^{+},$ (274)
$\displaystyle{\mathbb{P}}\left(\Pi_{n}\models\xi_{1}\right)$
$\displaystyle<0.2,\quad\text{if }\ n\in A^{-}.$ (275)

###### Proof.

Let $n_{1},c_{1},c_{2}$ and $\lambda(y)$ be as provided by Lemma 7.17, and let
the event $E$ be as in (260). Let $m$ be as given in Lemma 7.18. Without loss
of generality, we may assume that $m$ is so large that $W^{(2)}(m)>n_{1}$.
Define the $\operatorname{\mathsf{TOTO}}$ sentence $\xi_{1}$ as

$\xi_{1}=\exists z(\lambda(z)\wedge\omega^{\leq}(z)),$ (276)

where $\omega$ is the sentence $\omega(c_{1})$ as given in Proposition 7.13
(using the absolute constant $c_{1}$), and $\omega^{\leq}$ is its
relativization as in Lemma 3.24. Then by Lemma 3.26

${\mathbb{P}}\left(\Pi_{n}\models\xi_{1}\,|\,E\right)={\mathbb{P}}\left(\Pi_{N}\models\omega\,|\,E\right).$
(277)

Let $t\geq m$ be even and set $n=W^{(2)}(t)$. Then for all $c_{1}\log^{*}n\leq
N<n$ we have by Lemma 7.18 that $N$ satisfies the conditions of the first case
in Proposition 7.13, so that Lemma 7.19 yields

${\mathbb{P}}\left(\Pi_{N}\models\omega\,|\,E\right)>\frac{9}{10}-O\left((\log^{*}n)^{-1/4}\right).$
(278)

For $n$ large enough (i.e., $t$ large enough), this is at least $0.81$. As
${\mathbb{P}}\left(E\right)>0.99$ we have that
${\mathbb{P}}\left(\Pi_{n}\models\xi_{1}\right)>0.8$.

Completely analogously, when $t$ is odd, then
${\mathbb{P}}\left(\Pi_{N}\models\omega\,|\,E\right)<0.19$. Using
${\mathbb{P}}\left(E\right)>0.99$ we again conclude that there are also
infinitely many $n=W^{(2)}(t)$ with $t$ now odd, such that
${\mathbb{P}}\left(\Pi_{n}\models\xi_{1}\right)<0.2$. ∎

######  Remark 7.21.

As alluded to earlier, Lemma 7.20 is slightly stronger than needed: we only
require the bounds for the smaller domain
${\mathbb{P}}\left(\Pi_{n}\models\xi_{1}\right)$ for $1-1/\log^{*}n<q<1+50/n$.

The last lemma of this section gives the existence of $\xi_{2}$ with the
desired specifications, finishing the proof of Theorem 1.2 Part (ii).

######  Lemma 7.22.

Let $A^{-}$ and $A^{+}$ be as in Lemma 7.20. There exists a
$\operatorname{\mathsf{TOTO}}$ sentence $\xi_{2}$ such that for

$1-\frac{50}{n}\leq q<1+\frac{1}{\log^{*}n}$ (279)

and $\Pi_{n}\sim\operatorname{Mallows}(n,q)$ we have

$\displaystyle{\mathbb{P}}\left(\Pi_{n}\models\xi_{2}\right)$
$\displaystyle>0.8,\quad\text{if }\ n\in A^{+},$ (280)
$\displaystyle{\mathbb{P}}\left(\Pi_{n}\models\xi_{2}\right)$
$\displaystyle<0.2,\quad\text{if }\ n\in A^{-}.$ (281)

###### Proof.

Let $\xi_{2}\coloneqq\xi_{1}^{\operatorname{reverse}}$, where $\xi_{1}$ is as
provided by Lemma 7.20. Let $1-\frac{50}{n}\leq q<1+\frac{1}{\log^{*}n}$. Then

$\frac{1}{q}\leq\frac{1}{1-\frac{50}{n}}=1+\frac{50}{n-50}.$ (282)

If $n\geq 100$ then this is at most $1+100/n$, as is simple to verify.
Moreover,

$\frac{1}{q}>\frac{1}{1+\frac{1}{\log^{*}n}}=1-\frac{1}{\log^{*}n+1}>1-\frac{1}{\log^{*}n}.$
(283)

Recall from Lemma 7.20 that $A^{-}$ and $A^{+}$ are subsets of
${\mathbb{N}}_{>100}$. By Lemma 3.27 and Lemma 7.20 we have for
$\Pi_{n}\sim\operatorname{Mallows}(n,q)$ that

${\mathbb{P}}\left(\Pi_{n}\models\xi_{2}\right)={\mathbb{P}}\left(r_{n}\circ\Pi_{n}\models\xi_{1}\right)=\begin{cases}>0.8&\text{if
}n\in A^{+},\\\ <0.2&\text{if }n\in A^{-}.\\\ \end{cases}$ (284)

∎

### Acknowledgements

We thank Valentin Féray, Tomasz Łuczak, Marc Noy and Joel Spencer for helpful
discussions and pointers to the literature.

## References

  * [1] L. Addario-Berry and B. Corsini.  The height of Mallows trees.  Ann. Probab., 49(5):2220–2271, 2021.
  * [2] M. Albert, M. Bouvel, and V. Féray.  Two first-order logics of permutations.  J. Combin. Theory Ser. A, 171:105–158, 46, 2020.
  * [3] M. Albert, M. Bouvel, V. Féray, and M. Noy.  Convergence law for $231$-avoiding permutations.  arXiv preprint arXiv:2210.05537, 2022.
  * [4] M. H. Albert and A. M. Frieze.  Random graph orders.  Order, 6(1):19–30, 1989.
  * [5] O. Angel, A. E. Holroyd, T. Hutchcroft, and A. Levy.  Mallows permutations as stable matchings.  Canad. J. Math., 73(6):1531–1555, 2021.
  * [6] R. Arratia and S. Tavaré.  The cycle structure of random permutations.  Ann. Probab., 20(3):1567–1591, 1992.
  * [7] R. Basu and N. Bhatnagar.  Limit theorems for longest monotone subsequences in random Mallows permutations.  Ann. Inst. Henri Poincaré Probab. Stat., 53(4):1934–1951, 2017\.
  * [8] I. Benjamini, N. Berger, C. Hoffman, and E. Mossel.  Mixing times of the biased card shuffling and the asymmetric exclusion process.  Trans. Amer. Math. Soc., 357(8):3013–3029, 2005.
  * [9] N. Bhatnagar and R. Peled.  Lengths of monotone subsequences in a Mallows permutation.  Probab. Theory Related Fields, 161(3-4):719–780, 2015.
  * [10] B. Bollobás and P. Winkler.  The longest chain among random points in euclidean space.  Proceedings of the American Mathematical Society, 103(2):347–353, 1988.
  * [11] A. Borodin, P. Diaconis, and J. Fulman.  On adding a list of numbers (and other one-dependent determinantal processes).  Bull. Amer. Math. Soc. (N.S.), 47(4):639–670, 2010.
  * [12] S. Braunfeld and M. Kukla.  Logical limit laws for layered permutations and related structures.  arXiv preprint arXiv:2111.06307, 2021.
  * [13] M. Braverman and E. Mossel.  Sorting from noisy information.  Preprint, available from http://arxiv.org/abs/0910.1191, 2009.
  * [14] G. Brightwell.  Models of random partial orders, volume 187.  Cambridge University Press Cambridge, 1993.
  * [15] G. Brightwell and M. Luczak.  The mathematics of causal sets.  In Recent Trends in Combinatorics, pages 339–365. Springer, 2016\.
  * [16] H. Crane and S. DeSalvo.  Pattern avoidance for random permutations.  Discrete Math. Theor. Comput. Sci., 19(2):Paper No. 13, 24, 2017\.
  * [17] H. Crane, S. DeSalvo, and S. Elizalde.  The probability of avoiding consecutive patterns in the Mallows distribution.  Random Structures Algorithms, 53(3):417–447, 2018.
  * [18] P. Diaconis and A. Ram.  Analysis of systematic scan Metropolis algorithms using Iwahori-Hecke algebra techniques.  volume 48, pages 157–190. 2000.  Dedicated to William Fulton on the occasion of his 60th birthday.
  * [19] R. Douc, E. Moulines, P. Priouret, and P. Soulier.  Markov chains.  Springer Series in Operations Research and Financial Engineering. Springer, Cham, 2018.
  * [20] J. Enright, K. Meeks, W. Pettersson, and J. Sylvester.  Tangled paths: A random graph model from Mallows permutations.  arXiv preprint arXiv:2108.04786, 2021.
  * [21] C. Even-Zohar and C. Leng.  Counting small permutation patterns.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2288–2302. SIAM, 2021.
  * [22] X. Fang, H. L. Gan, S. Holmes, H. Huang, E. Peköz, A. Röllin, and W. Tang.  Arcsine laws for random walks generated from random permutations with applications to genomics.  J. Appl. Probab., 58(4):851–867, 2021.
  * [23] J. Foy and A. R. Woods.  Probabilities of sentences about two linear orderings.  In Feasible mathematics (Ithaca, NY, 1989), volume 9 of Progr. Comput. Sci. Appl. Logic, pages 181–193. Birkhäuser Boston, Boston, MA, 1990.
  * [24] A. Gladkich and R. Peled.  On the cycle structure of Mallows permutations.  Ann. Probab., 46(2):1114–1169, 2018.
  * [25] A. Gnedin and G. Olshanski.  $q$-exchangeability via quasi-invariance.  Ann. Probab., 38(6):2103–2135, 2010.
  * [26] A. Gnedin and G. Olshanski.  The two-sided infinite extension of the Mallows model for random permutations.  Adv. in Appl. Math., 48(5):615–639, 2012.
  * [27] W. Gontcharoff.  Sur la distribution des cycles dans les permutations.  C. R. (Doklady) Acad. Sci. URSS (N.S.), 35:267–269, 1942.
  * [28] R. L. Goodstein.  Transfinite ordinals in recursive number theory.  J. Symbolic Logic, 12:123–129, 1947.
  * [29] G. R. Grimmett and D. R. Stirzaker.  Probability and random processes.  Oxford University Press, New York, third edition, 2001.
  * [30] S. Haber and M. Krivelevich.  The logic of random regular graphs.  Journal of combinatorics, 1(4):389–440, 2010.
  * [31] J. He.  A central limit theorem for descents of a Mallows permutation and its inverse.  Ann. Inst. Henri Poincaré Probab. Stat., 58(2):667–694, 2022\.
  * [32] J. He, T. Müller, and T. W. Verstraaten.  Cycles in Mallows random permutations.  Preprint, available from https://arxiv.org/abs/2201.11610, 2022\.
  * [33] P. Heinig, T. Müller, M. Noy, and A. Taraz.  Logical limit laws for minor-closed classes of graphs.  Journal of Combinatorial Theory, Series B, 130:158–206, 2018.
  * [34] W. Hodges.  A shorter model theory.  Cambridge University Press, Cambridge, 1997.
  * [35] A. E. Holroyd, T. Hutchcroft, and A. Levy.  Mallows permutations and finite dependence.  Ann. Probab., 48(1):343–379, 2020.
  * [36] N. Immerman.  Descriptive complexity.  Graduate Texts in Computer Science. Springer-Verlag, New York, 1999.
  * [37] S. Janson, T. Łuczak, and A. Rucinski.  Random graphs.  Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000.
  * [38] K. Jin.  The length of the longest common subsequence of two independent Mallows permutations.  Ann. Appl. Probab., 29(3):1311–1355, 2019.
  * [39] D. E. Knuth.  Mathematics and computer science: Coping with finiteness.  Science, 194(4271):1235–1242, 1976.
  * [40] V. F. Kolchin.  A problem of the allocation of particles in cells and cycles of random permutations.  Theory of Probability & Its Applications, 16(1):74–90, 1971.
  * [41] V. Koponen.  Random graphs with bounded maximum degree: asymptotic structure and a logical limit law.  Discrete Mathematics & Theoretical Computer Science, 14, 2012.
  * [42] D. Král’ and O. Pikhurko.  Quasirandom permutations are characterized by 4-point densities.  Geometric and Functional Analysis, 23(2):570–579, 2013.
  * [43] D. A. Levin and Y. Peres.  Markov chains and mixing times, volume 107.  American Mathematical Soc., 2017.
  * [44] L. Libkin.  Elements of finite model theory.  Texts in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 2004.
  * [45] J. F. Lynch.  Convergence laws for random words.  Australas. J. Combin., 7:145–156, 1993.
  * [46] J. A. Makowsky.  Algorithmic uses of the Feferman-Vaught theorem.  Ann. Pure Appl. Logic, 126(1-3):159–213, 2004.
  * [47] C. L. Mallows.  Non-null ranking models. I.  Biometrika, 44:114–130, 1957.
  * [48] Y. Malyshkin and M. Zhukovskii.  Logical convergence laws via stochastic approximation and markov processes.  arXiv preprint arXiv:2210.13437, 2022.
  * [49] C. Mueller and S. Starr.  The length of the longest increasing subsequence of a random Mallows permutation.  J. Theoret. Probab., 26(2):514–540, 2013.
  * [50] T. Müller and M. Noy.  The first order convergence law fails for random perfect graphs.  Random Structures & Algorithms, 53(4):717–727, 2018.
  * [51] J. R. Norris.  Markov chains. Cambridge series in statistical and probabilistic mathematics. Cambridge University Press, 1998.
  * [52] A. Panconesi and A. Srinivasan.  Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds.  SIAM J. Comput., 26(2):350–368, 1997.
  * [53] R. G. Pinsky.  Permutations avoiding a pattern of length three under Mallows distributions.  Random Structures Algorithms, 58(4):676–690, 2021.
  * [54] J. Pitman and W. Tang.  Regenerative random permutations of integers.  Ann. Probab., 47(3):1378–1416, 2019.
  * [55] M. Podder and J. H. Spencer.  First order probabilities for galton–watson trees.  In A journey through discrete mathematics, pages 711–734. Springer, 2017.
  * [56] W. Rautenberg.  A concise introduction to mathematical logic.  Universitext. Springer, New York, second edition, 2006.  With a foreword by Lev Beklemishev.
  * [57] S. Shelah and J. H. Spencer.  Zero-one laws for sparse random graphs.  J. Amer. Math. Soc., 1(1):97–115, 1988.
  * [58] J. H. Spencer.  Nonconvergence in the theory of random orders.  Order, 7(4):341–348, 1990.
  * [59] J. H. Spencer.  The strange logic of random graphs, volume 22 of Algorithms and Combinatorics.  Springer-Verlag, Berlin, 2001.
  * [60] R. P. Stanley.  Enumerative combinatorics. Volume 1, volume 49 of Cambridge Studies in Advanced Mathematics.  Cambridge University Press, Cambridge, second edition, 2012.
  * [61] S. Starr.  Thermodynamic limit for the Mallows model on $S_{n}$.  J. Math. Phys., 50(9):095208, 15, 2009.
  * [62] S. Starr and M. Walters.  Phase uniqueness for the Mallows measure on permutations.  J. Math. Phys., 59(6):063301, 28, 2018.
  * [63] W. Tang.  Mallows ranking models: maximum likelihood estimate and regeneration.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6125–6134. PMLR, 2019.
  * [64] P. Winkler.  Random orders.  Order, 1(4):317–331, 1985.
  * [65] T. Yanagimoto.  On measures of association and a related problem.  Annals of the Institute of Statistical Mathematics, 22(1):57–63, 1970.