Transversals in quasirandom latin squares

1. Introduction

A transversal in an $n\times n$ latin square is a set of $n$ entries such that no two of them come from the same row or column or contain the same symbol.

Although there are examples of latin squares with no transversals (e.g., the multiplication table of $\mathbf{Z}/n\mathbf{Z}$ for $n$ even), it is widely believed that these are rare. For example, a famous conjecture of Ryser claims that an $n\times n$ latin square contains a transversal whenever $n$ is odd. In the same direction, Kwan [kwan] proved that a uniformly random $n\times n$ latin square has a transversal with probability $1-o(1)$ . Moreover, he showed that, with probability $1-o(1)$ , the number of transversals is $\bigl{(}(1-o(1))n/e^{2}\bigr{)}^{n}$ .

In this paper we improve Kwan’s result by finding the precise asymptotic of the number of transversals in a uniformly random latin square.

Theorem 1.1.

Let $\mathsf{L}$ be a uniformly random $n\times n$ latin square. Then $\mathsf{L}$ has $\bigl{(}e^{-1/2}+o(1)\bigr{)}n!^{2}/n^{n}$ transversals with probability $1-o(1)$ as $n\to\infty$ .

More generally, we find a (deterministic) quasirandomness condition for latin squares which is sufficient to guarantee this same asymptotic number of transversals.

Theorem 1.2.

There is a constant $\rho>0$ such that the following holds. Let $\mathsf{L}$ be an $n\times n$ latin square which is $\mathcal{A}$ -quasirandom with parameter $\rho$ . Then $\mathsf{L}$ has $\bigl{(}e^{-1/2}+o(1)\bigr{)}n!^{2}/n^{n}$ transversals.

The precise definition of “ $\mathcal{A}$ -quasirandom” is in terms of the spectral gap of some operator associated to $\mathsf{L}$ : see Definition 7.1\wrtusdrfdef:quasirandom. Despite the language, it is not actually obvious that a uniformly random $n\times n$ is quasirandom with high probability as $n\to\infty$ , and hence that Theorem 1.2\wrtusdrfthm:main-quasirandom implies Theorem 1.1\wrtusdrfthm:main-random. Indeed, it is incredibly delicate to prove any statistical properties of a uniform random latin square, for a number of reasons: the exact asymptotic count of $n\times n$ latin squares is not known; the latin square property is too rigid to make local changes; and no efficient way of sampling uniform random latin squares is known.

However, using a recent result of Kwan, Sah, Sawhney, and Simkin [KSSS] we are indeed able to establish that a random latin square is $\mathcal{A}$ -quasirandom with parameter $o(1)$ , with high probability, and we can thus prove Theorem 1.1\wrtusdrfthm:main-random as a consequence of Theorem 1.2\wrtusdrfthm:main-quasirandom.

Theorem 1.3.

Let $\mathsf{L}$ be a uniformly random $n\times n$ latin square. Then $\mathsf{L}$ is $\mathcal{A}$ -quasirandom with parameter $o(1)$ , with probability $1-o(1)$ as $n\to\infty$ .

Somewhat opposite to random latin squares are latin squares which are multiplication tables of finite groups. In [EMM] we proved that as long as the underlying group satisfies a necessary condition to have at least one transversal, we have the count as in Theorem 1.2\wrtusdrfthm:main-quasirandom with an extra factor equal to the size of the group’s abelianization. For some groups, this result is implied by Theorem 1.2\wrtusdrfthm:main-quasirandom and the following (easy) result.

Theorem 1.4.

Let $G$ be a group and let $\mathsf{L}_{G}$ be the multiplication table of $G$ . Then $\mathsf{L}_{G}$ is $\mathcal{A}$ -quasirandom with parameter $1/D$ , where $D$ is the minimal dimension of a nontrivial linear representation of $G$ .

This shows that the $\mathcal{A}$ -quasirandomness condition when restricted to group multiplication tables coincides with the usual notion of quasirandomness for groups due to Gowers [gowers]. Thus together Theorems 1.2 and 1.4\wrtusdrfthm:main-quasirandom,thm:quasirandom-groups-are-quasirandom recover the main result of [EMM] for sufficiently quasirandom groups.

There appears to be no single universal definition of a “quasirandom latin square”, in the same way that there is no single definition of a “quasirandom set of integers”. Instead there are various possible qualitatively inequivalent definitions, some more natural than others, and the correct choice depends on the problem at hand. For this reason we prefer to talk about a quasirandomness condition than about a “definition of quasirandomness”, and we do not claim that the condition in Definition 7.1\wrtusdrfdef:quasirandom is necessarily the correct one for other problems. In particular it is not directly related to the notion introduced in [MR4012871, MR4456029], since that depends on some additional structure (namely, an ordering on the set of symbols) to which our condition is oblivious. See Section 7\wrtusdrfsec:dense-minor for further remarks.

2. Outline

Our approach is analytical rather than combinatorial. Let $X$ , $Y$ , $Z$ be $n$ -element sets of rows, columns and symbols. We identify an $n\times n$ latin square $\mathsf{L}$ with a subset of $X\times Y\times Z$ satisfying the latin square property, i.e., every pair from $X\times Y$ , $Y\times Z$ and $Z\times X$ is in exactly one triple from $\mathsf{L}$ . We let $L^{2}(X),L^{2}(Y),L^{2}(Z)$ denote the spaces of complex-valued functions on $X$ , $Y$ , $Z$ (equipped with the standard hermitian inner product). The latin square tensor $\Lambda=\Lambda_{\mathsf{L}}$ is defined by

\Lambda(f,g,h):=\mathbf{E}_{(x,y,z)\in\mathsf{L}}f(x)g(y)h(z)

for $f\in L^{2}(X),g\in L^{2}(Y),h\in L^{2}(Z)$ .

We stress that the latin square tensor $\Lambda_{\mathsf{L}}$ depends on $\mathsf{L}$ , but we will always just write $\Lambda$ for brevity. We use the same notation for powers of $\mathsf{L}$ , in the following sense. If $\mathsf{L}_{1}$ and $\mathsf{L}_{2}$ are latin squares then $\mathsf{L}_{1}\times\mathsf{L}_{2}$ is also a latin square, where $\mathsf{L}_{1}\times\mathsf{L}_{2}$ is simply the cartesian product of $\mathsf{L}_{1}$ and $\mathsf{L}_{2}$ as subsets of $X_{1}\times Y_{1}\times Z_{1}$ and $X_{2}\times Y_{2}\times Z_{2}$ . Accordingly the powers $\mathsf{L}^{m}$ are latin squares of order $n^{m}$ for all $m\geqslant 0$ , and if $f\in L^{2}(X^{m}),g\in L^{2}(Y^{m}),h\in L^{2}(Z^{m})$ then we write

\Lambda(f,g,h):=\mathbf{E}_{(x,y,z)\in\mathsf{L}^{m}}f(x)g(y)h(z).

Of particular interest is the latin square $\mathsf{L}^{n}$ . We write $S$ (or sometimes $S_{X}$ to emphasize the domain, and similarly $S_{Y}$ and $S_{Z}$ ) for the subset $S\subseteq X^{n}$ of all bijections $[n]\to X$ . Then one can check that the number of transversals in $\mathsf{L}$ is

\Lambda(1_{S},1_{S},1_{S})\frac{n^{2n}}{n!}.

Our goal is therefore to show that

\Lambda(1_{S},1_{S},1_{S})=\bigl{(}e^{-1/2}+o(1)\bigr{)}{\left(\frac{n!}{n^{n}}\right)}^{3},

(2.1)

provided that $\mathsf{L}$ satisfies an appropriate quasirandomness condition.

We approach (2.1) principally by studying how $1_{S}$ deviates from its density $n!/n^{n}$ . We do this as follows. For any set $A\subseteq[m]$ , we may identify $L^{2}(X^{A})$ with the subspace of $L^{2}(X^{m})$ consisting of functions $X^{m}\to\mathbf{C}$ that factor as $X^{m}\to X^{A}\to\mathbf{C}$ ; i.e., functions $f(x_{1},\dots,x_{m})$ that only depend on $(x_{i}\colon i\in A)$ . These spaces are nested: if $A\subseteq B$ then $L^{2}(X^{A})\subseteq L^{2}(X^{B})$ . We write $Q_{A}$ for the orthogonal projection $L^{2}(X^{m})\to L^{2}(X^{A})$ and $P_{A}$ for the orthogonal projection

P_{A}:L^{2}(X^{m})\to L^{2}(X^{A})\cap\bigcap_{B\subsetneq A}L^{2}(X^{B})^{\perp}.

(2.2)

Here $L^{2}(X^{B})^{\perp}$ is the space of functions $f(x_{1},\dots,x_{m})$ orthogonal to functions depending only on $(x_{i}:i\in B)$ , i.e., such that $\mathbf{E}_{x_{i}:i\notin B}f(x_{1},\dots,x_{m})=0$ for any choice of $(x_{i}:i\in B)$ . Therefore the space on the right-hand side of (2.2) is the space of functions depending only on $(x_{i}:i\in A)$ and such that $\mathbf{E}_{x_{i}}f(x_{1},\dots,x_{m})=0$ for any $i\in A$ .

The operators $P_{A}$ , $Q_{A}$ are related via inclusion–exclusion rules:

	$\displaystyle Q_{A}$	$\displaystyle=\sum_{B\subseteq A}P_{B},$
	$\displaystyle P_{A}$	$\displaystyle=\sum_{B\subseteq A}(-1)^{\|A\setminus B\|}Q_{B}.$

Hence we have a kind of “Fourier expansion”

f=\sum_{A\subseteq[m]}P_{A}f,

for any function $f\in L^{2}(X^{m})$ (which is only truly a Fourier expansion if $n=2$ and $X^{m}$ is identified with $\mathbf{F}_{2}^{m}$ ). Applying this to $f=1_{S}\in L^{2}(X^{n})$ ,

1_{S}=\sum_{A\subseteq[n]}P_{A}1_{S}.

By the discussion above, $P_{A}1_{S}$ can be thought of as the component of $1_{S}$ which depends exactly on $(x_{i}:i\in A)$ (and is orthogonal to all functions depending only on variables in a strict subset of $A$ ). For example, $P_{\emptyset}1_{S}$ is equal to the density $n!/n^{n}$ .

The relevance of the $P_{A}$ projections is that any latin square tensor $\Lambda_{\mathsf{L}}$ is diagonal with respect to this decomposition: that is,

\Lambda(1_{S},1_{S},1_{S})=\sum_{A\subseteq[n]}\Lambda(P_{A}1_{S},P_{A}1_{S},P_{A}1_{S}).

(2.3)

This is a consequence of the following lemma.

Lemma 2.1.

Let $f\in L^{2}(X^{n}),g\in L^{2}(Y^{n}),h\in L^{2}(Z^{n})$ and $A,B,C\subseteq[n]$ . Then

\Lambda(P_{A}f,P_{B}g,P_{C}h)=0

unless $A=B=C$ .

Proof.

Assume it is not the case that $A=B=C$ . By symmetry we may assume $A\not\subseteq B$ , say $i\in A\setminus B$ . We may also assume $P_{A}f=f$ , $P_{B}g=g$ , $P_{C}h=h$ , by replacing $f,g,h$ with their images under $P_{A},P_{B},P_{C}$ , respectively. Now consider

\Lambda(f,g,h)=\mathbf{E}_{(x,y,z)\in\mathsf{L}^{n}}f(x)g(y)h(z).

In particular consider the average over the variables $(x_{i},y_{i},z_{i})\in\mathsf{L}$ . Since $i\notin B$ , there is no dependence on $y_{i}$ , so it is equivalent by the latin square property to average over all $(x_{i},z_{i})\in X\times Z$ . Since $\mathbf{E}_{x_{i}}f(x_{1},\dots,x_{m})=0$ , it follows that $\Lambda(f,g,h)=0$ . ∎

We now divide up the sum (2.3) according to the size $m$ of $A$ .

2.1. Major arcs

The terms in this decomposition where $A$ is very sparse (of size up to $cn^{1/2}$ ) form the major arcs.

Theorem 2.2.

There is a constant $c>0$ such that for $\log n<m\leqslant cn^{1/2}$ ,

\sum_{\begin{subarray}{c}A\subseteq[n]\\ |A|\leqslant m\end{subarray}}\Lambda(P_{A}1_{S},\>P_{A}1_{S},\>P_{A}1_{S})={\left(\frac{n!}{n^{n}}\right)}^{3}e^{-1/2}{\left(1+O(m^{2}/n)\right)}.

The proof is a mostly mechanical adaptation of [EMM, Section 4], which did not use group theory in an essential way.

2.2. Sparse minor arcs

The next range, the sparse minor arcs, concerns $A$ of size up to $cn$ for some small absolute constant $c$ .

Theorem 2.3.

There is a constant $c>0$ such that for $1\leqslant m\leqslant cn$ ,

\sum_{\begin{subarray}{c}A\subseteq[n]\\ |A|=m\end{subarray}}\Lambda(|P_{A}1_{S}|,|P_{A}1_{S}|,|P_{A}1_{S}|)\leqslant{\left(\frac{n!}{n^{n}}\right)}^{3}O(1)^{m+n/m}(m/n)^{m/8}.

Note $|\Lambda(P_{A}1_{S},P_{A}1_{S},P_{A}1_{S})|\leqslant\Lambda(|P_{A}1_{S}|,|P_{A}1_{S}|,|P_{A}1_{S}|)$ by the triangle inequality. The point is we have an exponential-in- $m$ gain over the main term provided

m\log(n/m)>C^{\prime}(m+n/m),

for some large enough $C^{\prime}>0$ . This would be satisfied as long as

C(n/\log n)^{1/2}<m<\epsilon n,

(2.4)

for some large enough $C>0$ and small enough $\epsilon>0$ .

We prove Theorem 2.3\wrtusdrfthm:sparse-minor by exhibiting a majorant for $|P_{A}1_{S}|$ and then using generating function methods.

2.3. Dense minor arcs

Finally we have the dense range, where $m\geqslant cn$ . Here we use quasirandomness. To be precise we define a certain Markov chain on $X\times Y$ , with adjacency operator $\mathcal{A}$ , and we consider $\mathsf{L}$ to be $\mathcal{A}$ -quasirandom with parameter $\rho$ if $\mathcal{A}$ has a spectral gap at least $1-\rho$ , i.e., if the spectral radius of $\mathcal{A}-\mathcal{U}$ is at most $\rho$ , where $\mathcal{U}$ is the projection to constants (the uniform distribution). See Definition 7.1\wrtusdrfdef:quasirandom.

Theorem 2.4.

For every $\epsilon>0$ there is $\rho>0$ such that if $\mathsf{L}$ is $\mathcal{A}$ -quasirandom with parameter $\rho$ , then

\sum_{\begin{subarray}{c}A\subseteq[n]\\ |A|\geqslant\epsilon n\end{subarray}}|\Lambda(P_{A}1_{S},P_{A}1_{S},P_{A}1_{S})|\leqslant{\left(\frac{n!}{n^{n}}\right)}^{3}10^{-n}.

2.4. Quasirandomness

It remains (for Theorems 1.1 and 1.4\wrtusdrfthm:main-random,thm:quasirandom-groups-are-quasirandom) to demonstrate that the latin squares in scope are quasirandom in this sense. If $\mathsf{L}$ is the multiplication table of a group $G$ we compute the entire spectrum of $\mathcal{A}$ and find $\rho=1/D$ where $D$ is the minimal dimension of a nontrivial representation of $G$ , which shows that our notion of quasirandomness is equivalent to the usual one due to Gowers [gowers] in the case of groups. For genuinely random latin squares we use recent work of Kwan, Sah, Sawhney, and Simkin [KSSS] to show that $\operatorname{tr}\mathcal{A}^{6}=1+o(1)$ with high probability, and this implies that $\rho=o(1)$ .

2.5. Proof of Theorem 1.2\wrtusdrfthm:main-quasirandom

Putting Theorems 2.2, 2.3 and 2.4\wrtusdrfthm:major-arcs,thm:sparse-minor,thm:dense-minor together it is straightforward to deduce Theorem 1.2\wrtusdrfthm:main-quasirandom.

Proof of Theorem 1.2\wrtusdrfthm:main-quasirandom.

Let $C$ and $\epsilon$ be as in (2.4) and $M:=C(n/\log n)^{1/2}$ . Theorems 2.2, 2.3 and 2.4 give us that for some $c>0$

	$\displaystyle\Lambda(1_{S},1_{S},1_{S})$	$\displaystyle=\bigl{(}e^{-1/2}+O(M^{2}/n)\bigr{)}\,{\left(\frac{n!}{n^{n}}\right)}^{3}$
		$\displaystyle\qquad+\sum_{M<m\leqslant\epsilon n}O(e^{-cm})\,{\left(\frac{n!}{n^{n}}\right)}^{3}$
		$\displaystyle\qquad+10^{-n}{\left(\frac{n!}{n^{n}}\right)}^{3},$

as long as $\mathsf{L}$ is $\mathcal{A}$ -quasirandom with parameter $\rho$ for small enough $\rho$ (depending on $\epsilon$ ). The choice of $M$ implies (2.1) and hence Theorem 1.2\wrtusdrfthm:main-quasirandom. ∎

2.6. Layout of the paper

To prove Theorems 2.2, 2.3 and 2.4\wrtusdrfthm:major-arcs,thm:sparse-minor,thm:dense-minor we need some background material on partition systems (Section 3\wrtusdrfsec:partitions) and on the primitive “Fourier analysis” of coordinate projections $Q_{A}$ , $P_{A}$ discussed above (Section 4\wrtusdrfsec:fourier). This builds on similar material from [EMM].

Then, Sections 5, 6 and 7\wrtusdrfsec:major-arcs,sec:true-sparse-minor,sec:dense-minor give the proofs of the three key theorems above. Finally, Section 8\wrtusdrfsec:quasirandomness proves the quasirandomness properties from Section 2.4\wrtusdrfsub:outline-quasi.

3. Partitions and partition systems

3.1. Partitions

Most of our language relating to the partition lattice is standard.

(1)

If $A$ is a set, $\Pi_{A}$ is the set of all partitions of $A$ . If $A=[m]$ we will conserve brackets by writing simply $\Pi_{m}$ .
(2)

$\Pi_{A}^{(k)}$ is the set of partitions all of whose cells have size at most $k$ .
(3)

If $A\subseteq B$ then any partition of $A$ is identified with a partition of $B$ by adding singletons $\bigl{\{}\{b\}\colon b\in B\setminus A\bigr{\}}$ . With this convention, $\Pi_{A}\subseteq\Pi_{B}$ .
(4)

The support $\operatorname{supp}\pi$ of a partition $\pi\in\Pi_{A}$ is the union of the nonsingleton cells of $\pi$ . It is the smallest set $B\subseteq A$ such that $\pi\in\Pi_{B}$ .
(5)

$\Pi^{\prime}_{A}$ is the set of $\pi\in\Pi_{A}$ with $\operatorname{supp}\pi=A$ .
(6)

If $\pi,\pi^{\prime}\in\Pi_{A}$ , $\pi\leqslant\pi^{\prime}$ means that $\pi$ is a refinement of $\pi^{\prime}$ (i.e., every cell of $\pi^{\prime}$ is a union of cells of $\pi$ ). Synonymously, $\pi^{\prime}$ is a coarsening of $\pi$ .
(7)

The meet $\pi\wedge\pi^{\prime}$ is the coarsest partition refining both $\pi$ and $\pi^{\prime}$ ; the join $\pi\vee\pi^{\prime}$ is the finest partition coarsening both $\pi$ and $\pi^{\prime}$ .
(8)

The partition $\{\{a\}:a\in A\}$ is the discrete partition; the partition $\{A\}$ is the indiscrete partition.
(9)

The rank of a partition $\pi\in\Pi_{A}$ is $\operatorname{rank}(\pi)=|A|-|\pi|$ ; equivalently it is the greatest $r$ such that there are partitions $\pi_{0}<\pi_{1}<\cdots<\pi_{r}=\pi$ . (Note that $\operatorname{rank}(\pi)$ is meaningful without specifying $A$ , unlike $|\pi|$ ; i.e., it is invariant under adding or removing singletons.)
(10)

The Möbius function $\mu$ at $\pi\in\Pi_{A}$ is given by $\mu(\pi)=(-1)^{\operatorname{rank}(\pi)}\prod_{p\in\pi}(|p|-1)!$ .
(11)

A function $f:A\to X$ is $\pi$ -measurable if $f$ is constant on the cells of $\pi$ . A subset $S\subseteq A$ is called $\pi$ -measurable if $1_{S}$ is $\pi$ -measurable.
(12)

If $\pi\in\Pi_{A}$ , $c_{\pi}\in L^{2}(X^{A})$ is the indicator of $\pi$ -measurability (i.e., $c_{\pi}(f)$ is $1$ if $f$ is $\pi$ -measurable, and $0$ otherwise).

The exponential formula for partitions states

\sum_{m\geqslant 0}\frac{1}{m!}\sum_{\pi\in\Pi_{m}}\prod_{p\in\pi}x_{|p|}=\exp{\left(\sum_{k\geqslant 1}\frac{1}{k!}x_{k}\right)}.

(3.1)

Here $x_{1},x_{2},\dots$ are formal variables. We will apply (3.1) several times in Section 6\wrtusdrfsec:true-sparse-minor.

3.2. Partition systems

In Sections 5 and 6\wrtusdrfsec:major-arcs,sec:true-sparse-minor it will be essential to have good bounds on the quantity $\Lambda(c_{\pi_{1}},c_{\pi_{2}},c_{\pi_{3}})$ for $A\subseteq[n]$ and various choices $\pi_{1},\pi_{2},\pi_{3}\in\Pi_{A}$ . This motivates the following definitions.

(1)

A partition triple on a set $A$ is a triple $\mathfrak{P}=(\pi_{1},\pi_{2},\pi_{3})\in\Pi_{A}^{3}$ .
(2)

We call $\mathfrak{P}$ a partition system if $\operatorname{supp}\pi_{1}=\operatorname{supp}\pi_{2}=\operatorname{supp}\pi_{3}$ .
(3)

The support of $\mathfrak{P}$ is $\operatorname{supp}\mathfrak{P}=\operatorname{supp}\pi_{1}\cup\operatorname{supp}\pi_{2}\cup\operatorname{supp}\pi_{3}$ .

Definition 3.1 (Combinatorial rank).

Let $\mathfrak{P}=(\pi_{1},\pi_{2},\pi_{3})\in\Pi_{A}^{3}$ be a partition triple. We write $S\subseteq\mathfrak{P}$ to mean that $S\subseteq\pi_{1}\sqcup\pi_{2}\sqcup\pi_{3}$ , i.e., $S$ is a collection of cells labelled 1, 2, or 3. A subset $S\subseteq\mathfrak{P}$ is closed (with respect to $\mathfrak{P}$ ) if whenever $p_{i}\in\pi_{i}$ for $i=1,2,3$ and $p_{1}\cap p_{2}\cap p_{3}\neq\emptyset$ , if two of $p_{1},p_{2},p_{3}$ are in $S$ then so is the third. The closure $\langle S\rangle$ of $S$ is the intersection of all closed sets containing $S$ . The combinatorial rank of $\mathfrak{P}=(\pi_{1},\pi_{2},\pi_{3})$ is defined as

\operatorname{crank}(\mathfrak{P})=2|A|-\min\left\{|S|:S\subseteq\mathfrak{P},\langle S\rangle=\mathfrak{P}\right\}.

The motivation for combinatorial rank is the following bound.

Lemma 3.2.

For a set $A$ , partitions $\pi_{1},\pi_{2},\pi_{3}\in\Pi_{A}$ , and latin square $\mathsf{L}\subseteq X\times Y\times Z$ ,

0\leqslant\Lambda(c_{\pi_{1}},c_{\pi_{2}},c_{\pi_{3}})\leqslant n^{-\operatorname{crank}(\pi_{1},\pi_{2},\pi_{3})}.

The idea of the proof is the same as for the related result [EMM, Lemma 4.6].

Proof.

The $\Lambda$ value is, by definition, $n^{-2|A|}$ times the number of triples of functions

f_{1}\colon A\to X,\qquad f_{2}\colon A\to Y,\qquad f_{3}\colon A\to Z

such that $f_{i}$ is $\pi_{i}$ -measurable for $i=1,2,3$ and such that $(f_{1}(a),f_{2}(a),f_{3}(a))\in\mathsf{L}$ for all $a\in A$ . Note we can think of $f_{i}$ as a function on the cells of $\pi_{i}$ , since it is $\pi_{i}$ -measurable.

We claim that, given $S\subseteq\mathfrak{P}$ with $\langle S\rangle=\mathfrak{P}$ , the triple $(f_{1},f_{2},f_{3})$ is determined by the values of $f_{i}$ on cells in $S$ . Hence the number of such triples is at most $n^{|S|}$ , giving the result.

Indeed, suppose $f^{\prime}_{1},f^{\prime}_{2},f^{\prime}_{3}$ is another triple of measurable functions with the same restriction to $S$ . Let $W\subseteq\mathfrak{P}$ be the set of all cells $p_{i}\in\pi_{i}$ such that $f_{i}|_{p_{i}}=f^{\prime}_{i}|_{p_{i}}$ . By hypothesis $W\supseteq S$ . If $p_{i}\in\pi_{i}$ for $i=1,2,3$ , $a\in p_{1}\cap p_{2}\cap p_{3}$ , and two of $p_{1},p_{2},p_{3}$ are in $W$ , then so is the third, as the triples $(f_{1}(a),f_{2}(a),f_{3}(a)),(f^{\prime}_{1}(a),f^{\prime}_{2}(a),f^{\prime}_{3}(a))\in\mathsf{L}$ agree at two coordinates and so are equal by the latin square property. Hence $W$ is a closed set, so $W\supseteq\langle S\rangle=\mathfrak{P}$ and $f_{i}=f^{\prime}_{i}$ , as required. ∎

This reduces the problem of bounding $\Lambda(c_{\pi_{1}},c_{\pi_{2}},c_{\pi_{3}})$ from above to the problem of bounding $\operatorname{crank}(\pi_{1},\pi_{2},\pi_{3})$ from below. In [EMM] we did this using two slightly weaker notions of rank, called triple rank and lower rank, defined respectively as

	$\displaystyle\operatorname{trank}(\mathfrak{P})$	$\displaystyle=\max_{\sigma\in S_{3}}\bigl{(}\operatorname{rank}(\pi_{\sigma(1)})+\operatorname{rank}(\pi_{\sigma(2)}\vee\pi_{\sigma(3)})\bigr{)}$
	$\displaystyle\operatorname{lrank}(\mathfrak{P})$	$\displaystyle=\bigl{(}\operatorname{rank}(\pi_{1})+\operatorname{rank}(\pi_{2})+\operatorname{rank}(\pi_{3})+\operatorname{rank}(\pi_{1}\vee\pi_{2}\vee\pi_{3})\bigr{)}/2.$

Lemma 3.3.

$\operatorname{crank}(\mathfrak{P})\geqslant\operatorname{trank}(\mathfrak{P})\geqslant\operatorname{lrank}(\mathfrak{P})$ .

Proof.

For the first inequality, let $S\subseteq\mathfrak{P}$ contain all of $\pi_{1}$ and one cell of $\pi_{2}$ from each cell of $\pi_{2}\vee\pi_{3}$ . Then $|S|=|\pi_{1}|+|\pi_{2}\vee\pi_{3}|$ and $\langle S\rangle=\mathfrak{P}$ , so $\operatorname{crank}(\mathfrak{P})\geqslant\operatorname{rank}(\pi_{1})+\operatorname{rank}(\pi_{2}\vee\pi_{3})$ , and equally for other permutations of 1, 2, 3. The second inequality was proved in [EMM, Lemma 4.8], and in any case will not be used in this paper. ∎

For continuity with [EMM], we define the complexity of a partition system $\mathfrak{P}$ to be

\operatorname{cx}(\mathfrak{P})=\operatorname{trank}(\mathfrak{P})-|\operatorname{supp}\mathfrak{P}|.

The complexity of a partition system is nonnegative, and it is zero if and only if $\mathfrak{P}=(\pi,\pi,\pi)$ for some matching $\pi$ , i.e., a partition of $A=\operatorname{supp}\pi$ into $|A|/2$ pairs.

3.3. Combinatorial rank of matching systems

In this subsection we compute $\operatorname{crank}(\pi_{1},\pi_{2},\pi_{3})$ for all $(\pi_{1},\pi_{2},\pi_{3})\in\Pi^{(2)}_{A}$ , i.e., partition triples such that all cells of $\pi_{1},\pi_{2},\pi_{3}$ have size at most 2. Where it applies, this is a significant improvement on what Lemma 3.3\wrtusdrflem:crank¿=trank gives us.

Lemma 3.4.

Let $\pi_{1},\pi_{2},\pi_{3}\in\Pi_{A}^{(2)}$ . Suppose there are precisely $k$ cells $p\in\pi_{1}\vee\pi_{2}\vee\pi_{3}$ such that $\pi_{i}|_{p}$ has full support (i.e., is a matching) for each $i\in[3]$ . Then

\operatorname{crank}(\pi_{1},\pi_{2},\pi_{3})=\operatorname{rank}(\pi_{1})+\operatorname{rank}(\pi_{2})+\operatorname{rank}(\pi_{3})-k.

Proof.

Since all terms are additive across cells of $\pi_{1}\vee\pi_{2}\vee\pi_{3}$ , we may assume $\pi_{1}\vee\pi_{2}\vee\pi_{3}$ is indiscrete. In particular $k\in\{0,1\}$ , and $k=0$ if and only if one of $\pi_{1},\pi_{2},\pi_{3}$ has a singleton.

Case $k=1$ : In this case $\pi_{1},\pi_{2},\pi_{3}$ are matchings, so

\operatorname{rank}(\pi_{1})=\operatorname{rank}(\pi_{2})=\operatorname{rank}(\pi_{3})=|A|/2,

and we must show

\operatorname{crank}(\pi_{1},\pi_{2},\pi_{3})=3|A|/2-1.

Let $\mathcal{G}$ be the multigraph whose vertex set is $A$ and with edges given by the cells of $\pi_{1},\pi_{2},\pi_{3}$ (which are all 2-cells). Clearly $\mathcal{G}$ is $3$ -regular, with $|A|$ vertices and $3|A|/2$ edges. Since $\pi_{1}\vee\pi_{2}\vee\pi_{3}$ is indiscrete, $\mathcal{G}$ is connected.

According to Definition 3.1\wrtusdrfdef:crank, we want to infect as few edges as possible in such a way that, if two infected edges incident at a vertex always spread infection to the third edge, then infection spreads to all edges. Note that for this to happen, it is necessary and sufficient to infect at least one edge in each cycle, since the edges that are uninfected at the end of the process form a subgraph with no vertex of degree $1$ . Hence, equivalently, we want to delete as few edges as possible to get a forest.

Since $\mathcal{G}$ has $3|A|/2$ edges and any forest has at most $|A|-1$ edges, we must delete at least $|A|/2+1$ edges. Conversely, given any connected 3-regular multigraph, we can delete edges until we have a (simple) tree. Hence the minimal number of generators is precisely $|A|/2+1$ , so $\operatorname{crank}(\pi_{1},\pi_{2},\pi_{3})=2|A|-(|A|/2+1)=3|A|/2-1$ , as claimed.

Case $k=0$ : In this case at least one of $\pi_{1},\pi_{2},\pi_{3}$ has a singleton, and we must show that

\operatorname{crank}(\pi_{1},\pi_{2},\pi_{3})=\operatorname{rank}(\pi_{1})+\operatorname{rank}(\pi_{2})+\operatorname{rank}(\pi_{3}).

We define a graph $\mathcal{G}$ as in the previous case but additionally for every singleton $\{v\}\in\pi_{1}\sqcup\pi_{2}\sqcup\pi_{3}$ we add an edge $\{v,*\}$ , where $*$ is a special additional vertex at which infection does not spread. Since $\pi_{1}\vee\pi_{2}\vee\pi_{3}$ is indiscrete, $\mathcal{G}\setminus*$ is connected. Since there is at least one singleton, $\mathcal{G}$ is connected. Again we want to delete as few edges as possible to get a forest. The number of vertices in $\mathcal{G}$ is $|A|+1$ and the number of edges is $|\pi_{1}|+|\pi_{2}|+|\pi_{3}|$ , so the number of edges we must delete is precisely $|\pi_{1}|+|\pi_{2}|+|\pi_{3}|-|A|.$ Hence

\operatorname{crank}(\pi_{1},\pi_{2},\pi_{3})=3|A|-|\pi_{1}|-|\pi_{2}|-|\pi_{3}|=\operatorname{rank}(\pi_{1})+\operatorname{rank}(\pi_{2})+\operatorname{rank}(\pi_{3}),

as claimed. ∎

4. The “Fourier” expansion of $1_{S}$

Recall from Section 2\wrtusdrfsec:outline that $Q_{A}$ denotes the orthogonal projection $L^{2}(X^{m})\to L^{2}(X^{A})$ and $P_{A}$ denotes the orthogonal projection

P_{A}:L^{2}(X^{m})\to L^{2}(X^{A})\cap\bigcap_{B\subsetneq A}L^{2}(X^{B})^{\perp},

and these operators are related via inclusion–exclusion rules:

	$\displaystyle Q_{A}$	$\displaystyle=\sum_{B\subseteq A}P_{B},$
	$\displaystyle P_{A}$	$\displaystyle=\sum_{B\subseteq A}(-1)^{\|A\setminus B\|}Q_{B}.$		(4.1)

In this section we study the terms in the expansion

1_{S}=\sum_{A\subseteq[n]}P_{A}1_{S}.

To express some of the results it is convenient to use the linear map $U:\mathbf{C}[z]\to\mathbf{C}$ defined by

U(z^{k})=\begin{cases}n^{k}/(n)_{k}&:k\leqslant n,\\ 0&:k>n.\end{cases}

Here $(n)_{k}=n(n-1)\cdots(n-k+1)$ .

4.1. Formulas for $P_{A}1_{S}$

Let $S_{A}\subseteq X^{A}$ denote the set of injections $A\to X$ . Thus if $|A|=m$ , $|S_{A}|=(n)_{m}$ .

Lemma 4.1.

If $A\subseteq[n]$ and $|A|=m$ ,

Q_{A}1_{S}=\frac{n!}{n^{n}}\frac{n^{m}}{(n)_{m}}1_{S_{A}}.

Proof.

A function $f\colon A\to X$ can be extended to a bijection $[n]\to X$ in $(n-m)!$ ways if $f$ is injective and $0$ ways otherwise, and by definition $Q_{A}1_{S}(f)$ is the number of such extensions normalized by $1/n^{n-m}$ . ∎

Lemma 4.2 ([EMM, Lemma 4.3]).

1_{S_{A}}=\sum_{\pi\in\Pi_{A}}\mu(\pi)c_{\pi}.

Lemma 4.3.

If $A\subseteq[n]$ and $|A|=m$ then

P_{A}1_{S}=\frac{n!}{n^{n}}\frac{n^{m}}{(n)_{m}}\sum_{\pi\in\Pi^{\prime}_{A}}\mu(\pi)P_{A}c_{\pi}.

Proof.

Combining the previous two lemmas,

P_{A}1_{S}=P_{A}Q_{A}1_{S}=\frac{n!}{n^{n}}\frac{n^{m}}{(n)_{m}}\sum_{\pi\in\Pi_{A}}\mu(\pi)P_{A}c_{\pi}.

Since $c_{\pi}\in L^{2}(X^{\operatorname{supp}\pi})$ , only the terms with $\operatorname{supp}\pi=A$ survive. ∎

We can use $U$ to give another formula for $P_{A}1_{S}$ . If $x\in X^{A}$ (i.e., $x:A\to X$ ), the kernel $\ker x\in\Pi_{A}$ of $x$ is the level set partition

\ker x=\bigl{\{}x^{-1}(t):t\in X,x^{-1}(t)\neq\emptyset\bigr{\}}.

Note that

c_{\pi}(x)=1\iff x~{}\text{is $\pi$-measurable}\iff\pi\leqslant\ker x.

Lemma 4.4.

Let $A\subseteq[n]$ , $|A|=m$ . For $x\in X^{n}$ , let $\pi=\ker(x|_{A})\in\Pi_{A}$ . Then

P_{A}1_{S}(x)=(-1)^{\operatorname{rank}(\pi)}\frac{n!}{n^{n}}U\prod_{p\in\pi}(|p|z-1).

Proof.

From (4.1) and Lemma 4.1\wrtusdrflem:Q_AS_B we have

P_{A}1_{S}=\frac{n!}{n^{n}}\sum_{B\subseteq A}(-1)^{|A\setminus B|}\frac{n^{|B|}}{(n)_{|B|}}1_{S_{B}}.

Now, the sets $B$ such that $x|_{B}$ is injective are precisely those which intersect each cell of $\pi$ in at most one point. Hence

	$\displaystyle P_{A}1_{S}(x)$	$\displaystyle=\frac{n!}{n^{n}}U\sum_{B\subseteq A}(-1)^{\|A\setminus B\|}z^{\|B\|}1_{S_{B}}(x)$
		$\displaystyle=\frac{n!}{n^{n}}(-1)^{\|A\|-\|\pi\|}U\prod_{p\in\pi}(\|p\|z-1).\qed$

4.2. Sparseval

The word sparseval is our playful term for the computation of $\|P_{A}f\|_{2}^{2}$ for any $A\subseteq[n]$ . This is possible by inclusion–exclusion and orthogonality: since

\|Q_{A}f\|_{2}^{2}=\sum_{B\subseteq A}\|P_{B}f\|_{2}^{2},

it follows that

\|P_{A}f\|_{2}^{2}=\sum_{B\subseteq A}(-1)^{|A\setminus B|}\|Q_{B}f\|_{2}^{2}.

(4.2)

Lemma 4.5.

If $A\subseteq[n]$ and $|A|=m$ ,

\|P_{A}1_{S}\|_{2}^{2}={\left(\frac{n!}{n^{n}}\right)}^{2}U\bigl{(}(z-1)^{m}\bigr{)}.

Proof.

Note that $\|1_{S_{B}}\|_{2}^{2}=(n)_{|B|}/n^{|B|}$ for every $B\subseteq A$ . Hence, from (4.2) and Lemma 4.1\wrtusdrflem:Q_AS_B,

\|P_{A}1_{S}\|_{2}^{2}{\left(\frac{n!}{n^{n}}\right)}^{-2}=\sum_{B\subseteq A}(-1)^{|A\setminus B|}\frac{n^{|B|}}{(n)_{|B|}}=U\bigl{(}(z-1)^{m}\bigr{)}.

∎

Proposition 4.6.

Assume $0\leqslant m\leqslant n$ and let $t=m/n$ . Then

0\leqslant U\bigl{(}(z-1)^{m}\bigr{)}\ll\binom{n}{m}^{-1}e^{s(t)n},

where

s(t)=t^{1/2}-t\log t^{1/2}-(1-t)\log(1+t^{1/2}).

In particular

U\bigl{(}(z-1)^{m}\bigr{)}\leqslant e^{O(m)}(m/n)^{m/2}.

Sketch.

The inequality $U\bigl{(}(z-1)^{m}\bigr{)}\geqslant 0$ follows from the previous lemma. For the main claim, by expanding we have

U\bigl{(}(z-1)^{m}\bigr{)}=\frac{1}{n!}\sum_{k=0}^{m}\binom{m}{k}(-1)^{m-k}n^{k}(n-k)!,

and this can be identified as $\binom{n}{m}^{-1}$ times the coefficient of $X^{m}$ in $e^{nX}/(1+X)^{n-m+1}$ . The stated bound follows by taking a contour integral (chosen in the spirit of the saddle-point method) to extract the coefficient. For details see [EMM-cyclic, bound for the sum in (5.4)]. Extra care is needed for $t$ near 1, but we omit the details because we will not use the claim for $t>1/2$ . The second bound follows by Stirling’s formula. ∎

The following corollary will not be used but is included for interest.

Corollary 4.7.

The sign of $P_{A}1_{S}(x)$ is $(-1)^{\operatorname{rank}(\ker x|_{A})}$ .

Proof.

Let $\pi=\ker(x|_{A})$ . By Lemma 4.4\wrtusdrfprop:PA1S-sparseval-like-expression it suffices to prove that

U\prod_{p\in\pi}(|p|z-1)>0.

There are nonnegative integers $r_{\omega}\geqslant 0$ such that

\prod_{p\in\pi}(|p|z-1)=\prod_{p\in\pi}\bigl{(}|p|(z-1)+(|p|-1)\bigr{)}=\sum_{\omega\subseteq\pi}r_{\omega}(z-1)^{|\omega|}.

Hence the claim follows from $U\bigl{(}(z-1)^{m}\bigr{)}\geqslant 0$ . ∎

5. Major arcs

The goal in this section is to prove Theorem 2.2. Define

	$\displaystyle\mathfrak{S}_{m}=\sum_{2k\leqslant m}\frac{(-1)^{k}}{2^{k}k!},$
	$\displaystyle M_{m}=\sum_{\begin{subarray}{c}A\subseteq[n]\\ \|A\|\leqslant m\end{subarray}}\Lambda(P_{A}1_{S},P_{A}1_{S},P_{A}1_{S}).$

Our aim is to prove that, for $m\leqslant cn^{1/2}$ ,

M_{m}=\bigl{(}\mathfrak{S}_{m}+O(m^{2}/n)\bigr{)}{\left(\frac{n!}{n^{n}}\right)}^{3}.

(5.1)

In particular this implies Theorem 2.2\wrtusdrfthm:major-arcs.

5.1. The quantities $\gamma$ and $\gamma_{0}$

From Lemma 4.3\wrtusdrflem:P_A-on-1_S it is clear that to estimate $\Lambda(P_{A}1_{S},P_{A}1_{S},P_{A}1_{S})$ it suffices to estimate $\Lambda(P_{A}c_{\pi_{1}},P_{A}c_{\pi_{2}},P_{A}c_{\pi_{3}})$ for every partition system $\mathfrak{P}=(\pi_{1},\pi_{2},\pi_{3})$ with support $A$ and aggregate the results with the appropriate weighting. For continuity with [EMM, Section 4], we define the normalized quantities

\gamma_{0}(\mathfrak{P})=n^{\operatorname{trank}(\mathfrak{P})}\Lambda(c_{\pi_{1}},c_{\pi_{2}},c_{\pi_{3}})

and

\gamma(\mathfrak{P})=n^{\operatorname{trank}(\mathfrak{P})}\Lambda(P_{A}c_{\pi_{1}},P_{A}c_{\pi_{2}},P_{A}c_{\pi_{3}})

for any partition triple $\mathfrak{P}=(\pi_{1},\pi_{2},\pi_{3})$ . Note that

0\leqslant\gamma_{0}(\mathfrak{P})\leqslant 1

by Lemmas 3.2 and 3.3\wrtusdrflem:crank-bound,lem:crank¿=trank. Since $c_{\pi}\in L^{2}(X^{\operatorname{supp}\pi})$ , $\gamma(\mathfrak{P})=0$ unless $\mathfrak{P}$ is a partition system.

Lemma 5.1.

Let $\mathfrak{P}$ be a partition system with support $\operatorname{supp}\mathfrak{P}=A$ of size $m$ , and suppose $m^{\prime}$ points of $A$ are contained in cells $\pi_{1}\vee\pi_{2}\vee\pi_{3}$ of size at least $3$ . Then

|\gamma(\mathfrak{P})|\leqslant 2^{m^{\prime}}.

Sketch.

The idea is that

	$\displaystyle\Lambda(P_{A}c_{\pi_{1}},P_{A}c_{\pi_{2}},P_{A}c_{\pi_{3}})$	$\displaystyle=\Lambda(c_{\pi_{1}},c_{\pi_{2}},P_{A}c_{\pi_{3}})$
		$\displaystyle=\sum_{B\subseteq A}(-1)^{\|A\setminus B\|}\Lambda(c_{\pi_{1}},c_{\pi_{2}},Q_{B}c_{\pi_{3}})$
		$\displaystyle=\sum_{B\subseteq A}(-1)^{\|A\setminus B\|}\Lambda(Q_{B}c_{\pi_{1}},Q_{B}c_{\pi_{2}},Q_{B}c_{\pi_{3}}),$

and

Q_{B}c_{\pi}=n^{-\operatorname{rank}(\pi)+\operatorname{rank}(\pi|_{B})}c_{\pi|_{B}},

where

\pi|_{B}=\{p\cap B:p\in\pi,p\cap B\neq\emptyset\}.

Let $\mathfrak{P}|_{B}=(\pi_{1}|_{B},\pi_{2}|_{B},\pi_{3}|_{B})$ . Then, normalizing,

\gamma(\mathfrak{P})=\sum_{B\subseteq A}(-1)^{|A\setminus B|}\gamma_{0}(\mathfrak{P}|_{B})n^{-t(\mathfrak{P},B)},

where

t(\mathfrak{P},B)=\operatorname{trank}(\mathfrak{P}|_{B})-\operatorname{trank}(\mathfrak{P})+\sum_{i=1}^{3}\bigl{(}\operatorname{rank}(\pi_{i})-\operatorname{rank}(\pi_{i}|_{B})\bigr{)}.

In [EMM, Section 4] we showed $t(\mathfrak{P},B)\geqslant 0$ . Since $\gamma_{0}(\mathfrak{P}|_{B})\in[0,1]$ for all $B$ this shows $|\gamma(\mathfrak{P})|\leqslant 2^{m}$ . The stronger bound with $m^{\prime}$ in place of $m$ follows by separating off the doubleton cells of $\pi_{1}\vee\pi_{2}\vee\pi_{3}$ . See [EMM, Section 4] for details. ∎

5.2. The $M_{m}(z)$ series

For a partition triple $\mathfrak{P}=(\pi_{1},\pi_{2},\pi_{3})$ we use the shorthand

\mu(\mathfrak{P})=\mu(\pi_{1})\,\mu(\pi_{2})\,\mu(\pi_{3}).

From Lemma 4.3 we have

M_{m}={\left(\frac{n!}{n^{n}}\right)}^{3}\sum_{|\operatorname{supp}\mathfrak{P}|\leqslant m}{\left(\frac{n^{|\operatorname{supp}\mathfrak{P}|}}{(n)_{|\operatorname{supp}\mathfrak{P}|}}\right)}^{3}\mu(\mathfrak{P})\gamma(\mathfrak{P})n^{-\operatorname{trank}(\mathfrak{P})},

where the sum is over all partition systems on $[n]$ . For $z\in\mathbf{C}$ define

M_{m}(z)={\left(\frac{n!}{n^{n}}\right)}^{3}\sum_{|\operatorname{supp}\mathfrak{P}|\leqslant m}{\left(\frac{n^{|\operatorname{supp}\mathfrak{P}|}}{(n)_{|\operatorname{supp}\mathfrak{P}|}}\right)}^{3}\mu(\mathfrak{P})\gamma(\mathfrak{P})n^{-|\operatorname{supp}\mathfrak{P}|}z^{\operatorname{cx}(\mathfrak{P})}.

As we have mentioned, $\operatorname{cx}(\mathfrak{P})\geqslant 0$ for any partition system $\mathfrak{P}$ , so $M_{m}(z)$ is a polynomial such that $M_{m}=M_{m}(1/n)$ . By bounding $M_{m}(z)$ and using some complex analysis we will show $M_{m}(1/n)\approx M_{m}(0)$ , and then we will directly estimate $M_{m}(0)$ .

Proposition 5.2.

There is a constant $c>0$ such that, for $|z|^{1/2}\leqslant c/m$ , we have

|M_{m}(z)|\ll{\left(\frac{n^{m}}{(n)_{m}}\right)}^{2}{\left(\frac{n!}{n^{n}}\right)}^{3}.

Proof.

By the definition of $M_{m}(z)$ , the triangle inequality, and Lemma 5.1\wrtusdrflem:trivial-gamma-bound, the quantity $|M_{m}(z)|/{\left(\frac{n!}{n^{n}}\right)}^{3}$ is bounded by

\sum_{|A|\leqslant m}n^{-|A|}{\left(\frac{n^{|A|}}{(n)_{|A|}}\right)}^{3}\sum_{\operatorname{supp}\mathfrak{P}=A}2^{m^{\prime}(\mathfrak{P})}|\mu(\mathfrak{P})|\ |z|^{\operatorname{cx}(\mathfrak{P})},

where $m^{\prime}(\mathfrak{P})$ is the number of points of $\operatorname{supp}\mathfrak{P}$ contained in cells of $\pi_{1}\vee\pi_{2}\vee\pi_{3}$ of size at least 3. This exact sum was analyzed in [EMM, Section 4.4], and we showed that it is $O(n^{m}/(n)_{m})^{2}$ provided $|z|^{1/2}<c/m$ . The proposition follows. ∎

Corollary 5.3.

There is a constant $c>0$ such that, for $m<cn^{1/2}$ ,

|M_{m}-M_{m}(0)|\ll(m^{2}/n){\left(\frac{n!}{n^{n}}\right)}^{3}.

Proof.

By the residue theorem,

M_{m}(u)-M_{m}(0)=\frac{1}{2\pi i}\oint_{|z|=R}\frac{M_{m}(z)u}{(z-u)z}\,dz

as long as $|u|<R$ . Hence

\left|M_{m}(u)-M_{m}(0)\right|\leqslant\max_{|z|=R}|M_{m}(z)|\frac{|u|/R}{1-|u|/R}.

Take $u=1/n$ and $R=c^{2}/m^{2}$ , where $c$ is as in the previous proposition. Then as long as $1/n<c^{2}/m^{2}$ , i.e., $m<cn^{1/2}$ , we get

|M_{m}-M_{m}(0)|\ll(1+n^{-1/2})^{2m}{\left(\frac{n^{m}}{(n)_{m}}\right)}^{2}{\left(\frac{n!}{n^{n}}\right)}^{3}\frac{m^{2}/n}{1-m^{2}/(c^{2}n)}.

Hence as long as say $m<(c/2)n^{1/2}$ we get the claimed bound. ∎

5.3. The constant term $M_{m}(0)$

By definition,

M_{m}(0)={\left(\frac{n!}{n^{n}}\right)}^{3}\sum_{\begin{subarray}{c}|\operatorname{supp}\mathfrak{P}|\leqslant m\\ \operatorname{cx}(\mathfrak{P})=0\end{subarray}}{\left(\frac{n^{|\operatorname{supp}\mathfrak{P}|}}{(n)_{|\operatorname{supp}\mathfrak{P}|}}\right)}^{3}\mu(\mathfrak{P})\gamma(\mathfrak{P})n^{-|\operatorname{supp}\mathfrak{P}|}.

As remarked, $\operatorname{cx}(\mathfrak{P})=0$ if and only if $\mathfrak{P}=(\pi,\pi,\pi)$ for some matching $\pi$ . In this case, if say $|\operatorname{supp}\mathfrak{P}|=2k$ ,

	$\displaystyle\frac{n^{\|\operatorname{supp}\mathfrak{P}\|}}{(n)_{\|\operatorname{supp}\mathfrak{P}\|}}=\frac{n^{2k}}{(n)_{2k}}=1+O(k^{2}/n),$
	$\displaystyle\mu(\mathfrak{P})=\mu(\pi)^{3}=(-1)^{k},$
	$\displaystyle\gamma(\mathfrak{P})=(1-1/n)^{k}.$

The last identity holds by a direct calculation analogous to [EMM, Lemma 4.10]. The number of matchings $\pi$ in $[n]$ of support size $2k$ is

\frac{(n)_{2k}}{2^{k}k!}=\frac{n^{2k}}{2^{k}k!}\bigl{(}1+O(k^{2}/n)\bigr{)}.

Thus

	$\displaystyle M_{m}(0)$	$\displaystyle={\left(\frac{n!}{n^{n}}\right)}^{3}\sum_{k=0}^{\left\lfloor{m/2}\right\rfloor}\frac{n^{2k}}{2^{k}k!}(-1)^{k}n^{-2k}\bigl{(}1+O(k^{2}/n)\bigr{)}$
		$\displaystyle={\left(\frac{n!}{n^{n}}\right)}^{3}\bigl{(}\mathfrak{S}_{m}+O(1/n)\bigr{)}.$

By combining with Corollary 5.3 we have

M_{m}={\left(\frac{n!}{n^{n}}\right)}^{3}\bigl{(}\mathfrak{S}_{m}+O(m^{2}/n)\bigr{)}

provided $m<cn^{1/2}$ . This finishes the proof of (5.1).

6. Sparse minor arcs

To prove Theorem 2.3\wrtusdrfthm:sparse-minor we need a bound on $\Lambda(|P_{A}1_{S}|,|P_{A}1_{S}|,|P_{A}1_{S}|)$ for larger $|A|$ . Note that in any latin square $\mathsf{L}^{\prime}\subseteq(X^{\prime},Y^{\prime},Z^{\prime})$ ,

	$\displaystyle\|\Lambda(f,g,h)\|$	$\displaystyle=\lvert\mathbf{E}_{(x,y,z)\in\mathsf{L}^{\prime}}f(x)g(y)h(z)\rvert$
		$\displaystyle\leqslant\mathbf{E}_{x\in X^{\prime}}\|f(x)\|\left\lvert\mathbf{E}_{y,z\colon(x,y,z)\in\mathsf{L}^{\prime}}g(y)h(z)\right\rvert\leqslant\\|f\\|_{1}\\|g\\|_{2}\\|h\\|_{2}$		(6.1)

using the latin square property and Cauchy–Schwarz, and similarly permuting $f,g,h$ . One approach to Theorem 2.3\wrtusdrfthm:sparse-minor might be to find upper bounds on $|P_{A}1_{S}(x)|$ , pointwise or in $L^{1}$ , and simply apply (6.1). However, by itself this approach is too crude, even assuming optimal upper bounds.

Another idea is to seek a majorant for $|P_{A}1_{S}|$ of the form

|P_{A}1_{S}|\leqslant\sum_{\pi\in\Pi_{A}}t_{\pi}c_{\pi}

(6.2)

for some coefficients $t_{\pi}\geqslant 0$ . Then

\Lambda(|P_{A}1_{S}|,|P_{A}1_{S}|,|P_{A}1_{S}|)\leqslant\sum_{\pi_{1},\pi_{2},\pi_{3}\in\Pi_{A}}t_{\pi_{1}}t_{\pi_{2}}t_{\pi_{3}}\Lambda(c_{\pi_{1}},c_{\pi_{2}},c_{\pi_{3}})

and Lemma 3.2\wrtusdrflem:crank-bound, together with generating function techniques, gives a way to control the right-hand side. This bound is particularly effective if $\pi_{i}\in\Pi_{A}^{(2)}$ , given Lemma 3.4\wrtusdrfclaim:cool-crank-value.

Again this approach does not succeed by itself. Our final argument works by decomposing $|P_{A}1_{S}|$ into two pieces and combining the two techniques discussed above.

6.1. A majorant for $|P_{A}1_{S}|$

Throughout this section let $C>0$ be some large enough constant, $A\subseteq[n]$ and $|A|=m\leqslant n/C$ . Additionally, we let

\delta:=(Cm/n)^{1/2}.

Although we will always have this specific value of $\delta$ in mind, most of the results in this section only rely on $\delta\leqslant 1$ . The next proposition gives a useful bound for $|P_{A}1_{S}|$ . For $\delta:=(Cm/n)^{1/2}$ , $r\geqslant 1$ , and $\pi$ a partition define

	$\displaystyle\sigma_{r}^{(\delta)}$	$\displaystyle=\begin{cases}\delta&:r=1,\\ r-1&:r>1,\end{cases}$
	$\displaystyle\sigma_{\pi}^{(\delta)}$	$\displaystyle=\prod_{p\in\pi}\sigma_{\|p\|}^{(\delta)}.$

Proposition 6.1.

We have

|P_{A}1_{S}(x)|\leqslant\frac{n!}{n^{n}}e^{\delta m}\sigma_{\ker x}^{(\delta)}\qquad(x\in X^{A}).

Proof.

From Lemma 4.4\wrtusdrfprop:PA1S-sparseval-like-expression,

P_{A}1_{S}(x)=(-1)^{\operatorname{rank}(\pi)}\frac{n!}{n^{n}}U\phi,

where $\pi=\ker x$ and

	$\displaystyle\phi$	$\displaystyle=\prod_{p\in\pi}(\|p\|z-1)=\sum_{\omega\subseteq\pi}r_{\omega}(z-1)^{\|\omega\|},$
	$\displaystyle r_{\omega}$	$\displaystyle=\prod_{p\in\pi\setminus\omega}(\|p\|-1)\prod_{p\in\omega}\|p\|.$

From Proposition 4.6\wrtusdrfprop:umbral-sparseval and crude estimates (Stirling’s formula), for $0\leqslant d\leqslant m$ ,

U\bigl{(}(z-1)^{d}\bigr{)}\leqslant(Cd/n)^{d/2}\leqslant(Cm/n)^{d/2}=\delta^{d}

provided $C$ is large enough. Then

	$\displaystyle U\phi$	$\displaystyle\leqslant\sum_{\omega\subseteq\pi}r_{\omega}\delta^{\|\omega\|}$
		$\displaystyle=\prod_{p\in\pi}(\|p\|-1+\|p\|\delta)$
		$\displaystyle=\sigma_{\pi}^{(\delta)}\prod_{p\in\pi:\|p\|>1}{\left(1+\frac{\|p\|}{\|p\|-1}\delta\right)}$
		$\displaystyle\leqslant\sigma_{\pi}^{(\delta)}{\left(1+2\delta\right)}^{m/2}$
		$\displaystyle\leqslant\sigma_{\pi}^{(\delta)}e^{\delta m}$

as required. ∎

In light of the proposition, to find majorants for $|P_{A}1_{S}|$ of the form (6.2) it suffices to find analogous bounds for $\sigma_{\pi}^{(\delta)}$ . Recall that $\Pi_{A}^{(k)}$ is the set of all $\pi\in\Pi_{A}$ having no part of size greater than $k$ . Let $r_{k}(\pi)$ be the number of $k$ -cells in $\pi$ and let $r_{3+}(\pi)=\sum_{k\geqslant 3}r_{k}(\pi)$ .

Lemma 6.2.

Let $\pi$ be a partition.

(1)

$\sigma_{\pi}^{(\delta)}\leqslant\sum\Bigl{\{}\sigma_{\pi^{\prime}}^{(\delta)}:\pi^{\prime}\leqslant\pi,\pi^{\prime}\in\Pi^{(3)}\Bigr{\}}.$

(2)

\sigma_{\pi}^{(\delta)}\leqslant\sum\Bigl{\{}\sigma_{\pi^{\prime}}^{(\delta)}:\pi^{\prime}\leqslant\pi,\pi^{\prime}\in\Pi^{(4)},r_{3+}(\pi^{\prime})=r_{3+}(\pi)\Bigr{\}}.

(3)

\sigma_{\pi}^{(\delta)}\leqslant\delta^{-r_{3+}(\pi)}\sum\Bigl{\{}\sigma_{\pi^{\prime}}^{(\delta)}:\pi^{\prime}\leqslant\pi,\pi^{\prime}\in\Pi^{(2)}\Bigr{\}}.

Proof.

Consider the first inequality. Both sides are multiplicative across cells of $\pi$ , so we may assume $\pi$ is a single cell, say of size $r$ . The inequality is trivial for $r\leqslant 3$ (since $\sigma_{\pi}^{(\delta)}$ is one of the summands on the right-hand side), so we may assume $r\geqslant 4$ . Then it suffices to check

r-1\leqslant\sum_{\begin{subarray}{c}2a+3b=r\end{subarray}}\frac{r!}{2!^{a}a!3!^{b}b!}2^{b}.

This is a calculation for $r\leqslant 10$ (say) and an uninteresting exercise for $r>10$ .

Now consider the second inequality. This time, the right-hand side is not itself multiplicative over cells of $\pi$ , but if we replace the condition $r_{3+}(\pi^{\prime})=r_{3+}(\pi)$ by the stronger one

\forall p\in\pi,\ |p|\geqslant 3:\ \text{there is exactly one }p^{\prime}\in\pi^{\prime}\text{ with }p^{\prime}\subseteq p\text{ and }|p^{\prime}|\geqslant 3

then it becomes so, and it suffices to prove the corresponding stronger inequality. Now we may again assume that $\pi$ is an $r$ -cell, and we may assume $r\geqslant 5$ . Then we must check

r-1\leqslant\sum_{\begin{subarray}{c}2a+3b+4c=r\\ b+c=1\end{subarray}}\frac{r!}{2!^{a}a!3!^{b}b!4!^{c}c!}2^{b}3^{c}.

Again we omit further details.

Now consider the third inequality. Again it suffices to consider the case of an $r$ -cell, and we may assume $r\geqslant 3$ . Then the assertion is

r-1\leqslant\delta^{-1}\sum_{a+2b=r}\frac{r!}{a!2!^{b}b!}\delta^{a}.

Since $\delta\leqslant 1$ , it suffices to check

r-1\leqslant\sum_{\begin{subarray}{c}a+2b=r\\ a\leqslant 1\end{subarray}}\frac{r!}{a!2!^{b}b!},

which is again essentially a calculation. ∎

Lemma 6.3.

Let $x\in X^{A}$ . Then

|P_{A}1_{S_{A}}(x)|\leqslant\frac{n!}{n^{n}}e^{\delta m}\sum_{\pi\in\Pi_{A}^{(3)}}\sigma_{\pi}^{(\delta)}c_{\pi}(x).

Proof.

By Proposition 6.1\wrtusdrfprop:PA1S-physical-bound,

|P_{A}1_{S_{A}}(x)|\leqslant\frac{n!}{n^{n}}e^{\delta m}\sigma_{\ker x}^{(\delta)}.

By Lemma 6.2(1),

\sigma_{\ker x}^{(\delta)}\leqslant\sum\Bigl{\{}\sigma_{\pi}^{(\delta)}:\pi\leqslant\ker x,\pi\in\Pi_{A}^{(3)}\Bigr{\}}=\sum_{\pi\in\Pi_{A}^{(3)}}\sigma_{\pi}^{(\delta)}c_{\pi}(x).\qed

6.2. A splitting of $|P_{A}1_{S}|$

We can use the bound on $|P_{A}1_{S}|$ given in the previous section to bound the $L^{1}$ norm of $P_{A}1_{S}$ , but the bound would not be strong enough for what we need. To go further, we break up $R:=|P_{A}1_{S}|$ into two parts, a part whose $L^{1}$ norm we can control better, and a part we can analyze separately. Fix $\epsilon\geqslant 0$ and let

\Pi^{\sharp}=\{\pi\in\Pi_{A}:r_{3+}(\pi)<\epsilon m\}.

Let $\Pi^{\flat}=\Pi_{A}\setminus\Pi^{\sharp}$ . Define

	$\displaystyle R^{\sharp}(x)$	$\displaystyle=1_{\Pi^{\sharp}}(\ker x)R(x),$
	$\displaystyle R^{\flat}(x)$	$\displaystyle=1_{\Pi^{\flat}}(\ker x)R(x).$

Clearly $R=R^{\sharp}+R^{\flat}$ .

Lemma 6.4.

We have

	$\displaystyle R^{\flat}$	$\displaystyle\leqslant\frac{n!}{n^{n}}e^{\delta m}\sum_{\pi\in\Pi^{\flat}\cap\Pi^{(4)}}\sigma_{\pi}^{(\delta)}c_{\pi},$
	$\displaystyle R^{\sharp}$	$\displaystyle\leqslant\frac{n!}{n^{n}}e^{\delta m}\sum_{\pi\in\Pi^{\sharp}\cap\Pi^{(4)}}\sigma_{\pi}^{(\delta)}c_{\pi},$
	$\displaystyle R^{\sharp}$	$\displaystyle\leqslant\frac{n!}{n^{n}}e^{\delta m}\delta^{-\epsilon m}\sum_{\pi\in\Pi^{(2)}}\sigma_{\pi}^{(\delta)}c_{\pi}.$

Proof.

By Proposition 6.1\wrtusdrfprop:PA1S-physical-bound,

R(x)\leqslant\frac{n!}{n^{n}}e^{\delta m}\sigma_{\ker x}^{(\delta)}.

Suppose $\ker x\in\Pi^{\flat}$ . Then by Lemma 6.2(2),

\sigma_{\ker x}\leqslant\sum\{\sigma_{\pi}:\pi\leqslant\ker x,\pi\in\Pi^{(4)},r_{3+}(\pi)\geqslant\epsilon m\}.

This proves the bound on $R^{\flat}$ . The first bound on $R^{\sharp}$ is proved identically. The second is proved in the same way using instead Lemma 6.2(3). ∎

Corollary 6.5.

We have

\|R^{\flat}\|_{1}\ll\frac{n!}{n^{n}}e^{O(m)}(m/n)^{(1+\epsilon)m/2}.

Proof.

Using the previous lemma, $\delta\leqslant 1$ and $\|c_{\pi}\|_{1}=n^{-\operatorname{rank}(\pi)}$ ,

\|R^{\flat}\|_{1}\leqslant\frac{n!}{n^{n}}e^{m}\sum_{\pi\in\Pi^{\flat}\cap\Pi^{(4)}}\sigma_{\pi}^{(\delta)}n^{-\operatorname{rank}(\pi)}.

Let

\alpha_{r}(x,w)=\sum_{\pi\in\Pi_{r}^{(4)}}\sigma_{\pi}^{(\delta)}x^{\operatorname{rank}(\pi)}w^{r_{3+}(\pi)}.

Then, for real $w\geqslant 1$ ,

\sum_{\pi\in\Pi^{\flat}\cap\Pi^{(4)}}\sigma_{\pi}^{(\delta)}n^{-\operatorname{rank}(\pi)}\leqslant w^{-\epsilon m}\alpha_{m}(1/n,w).

Using the exponential formula (3.1) with $x_{k}=\sigma_{k}^{(\delta)}x^{k-1}y^{k}$ for $k=1,2$ , $x_{k}=\sigma_{k}^{(\delta)}wx^{k-1}y^{k}$ for $k=3,4$ , and $x_{k}=0$ for $k\geqslant 5$ , we obtain

\sum_{r\geqslant 0}\frac{1}{r!}\alpha_{r}(x,w)y^{r}=\exp(\delta y+xy^{2}/2+wx^{2}y^{3}/3+wx^{3}y^{4}/8).

Hence for real $y>0$ ,

w^{-\epsilon m}\alpha_{m}(x,w)\leqslant\frac{m!}{w^{\epsilon m}y^{m}}\exp(\delta y+xy^{2}/2+wx^{2}y^{3}/3+wx^{3}y^{4}/8).

Putting $x=1/n$ , $y=(mn)^{1/2}$ , and $w=(n/m)^{1/2}$ , we get

w^{-\epsilon m}\alpha_{m}(1/n,w)\leqslant\frac{m!}{(n/m)^{\epsilon m/2}(mn)^{m/2}}e^{O(m)}.

This proves what we want. ∎

Corollary 6.6.

We have

\Lambda(R,R,R)\leqslant\Lambda(R^{\sharp},R^{\sharp},R^{\sharp})+{\left(\frac{n!}{n^{n}}\right)}^{3}O(1)^{m}(m/n)^{(1+\epsilon/2)m}.

Proof.

We have $\|R^{\sharp}\|_{2}\leqslant\|R\|_{2}$ since $0\leqslant R^{\sharp}\leqslant R$ pointwise. Hence, from (6.1),

	$\displaystyle\Lambda(R,R,R)$	$\displaystyle=\Lambda(R^{\flat},R,R)+\Lambda(R^{\sharp},R^{\flat},R)+\Lambda(R^{\sharp},R^{\sharp},R^{\flat})+\Lambda(R^{\sharp},R^{\sharp},R^{\sharp})$
		$\displaystyle\leqslant\Lambda(R^{\sharp},R^{\sharp},R^{\sharp})+3\\|R\\|_{2}^{2}\\|R^{\flat}\\|_{1}.$

From sparseval (Lemma 4.5\wrtusdrflem:L2-to-sparseval and Proposition 4.6\wrtusdrfprop:umbral-sparseval),

\|R\|_{2}^{2}\ll{\left(\frac{n!}{n^{n}}\right)}^{2}e^{O(m)}(m/n)^{m/2}.

Combining with Corollary 6.5\wrtusdrfcor:rflat-l1-bound gives the bound. ∎

6.3. The contribution from $R^{\sharp}$

Finally we must bound $\Lambda(R^{\sharp},R^{\sharp},R^{\sharp})$ . From Lemma 6.4,

R^{\sharp}\leqslant\frac{n!}{n^{n}}e^{\delta m}\delta^{-\epsilon m}Q\leqslant\frac{n!}{n^{n}}e^{O(m)}(m/n)^{-\epsilon m/2}Q,

(6.3)

where

Q=\sum_{\pi\in\Pi^{(2)}}\sigma_{\pi}^{(\delta)}c_{\pi}.

Hence it suffices to bound $\Lambda(Q,Q,Q)$ . The key ingredient for this is the knowledge of the exact value of combinatorial rank for $\pi_{1},\pi_{2},\pi_{3}\in\Pi^{(2)}$ (Lemma 3.4\wrtusdrfclaim:cool-crank-value).

Lemma 6.7.

\Lambda(Q,Q,Q)\leqslant(m/n)^{3m/2}e^{O(m+n/m)}.

Proof.

Let $\mathcal{M}_{A}\subseteq\Pi_{A}^{(2)}$ be the set of matchings (partitions all of whose cells have size 2). For $\pi_{1},\pi_{2},\pi_{3}\in\Pi^{(2)}_{A}$ , let $k(\pi_{1},\pi_{2},\pi_{2})$ be the number of cells $p\in\pi_{1}\vee\pi_{2}\vee\pi_{3}$ such that $\pi_{i}|_{p}\in\mathcal{M}_{p}$ for each $i\in[3]$ . Then, from Lemma 3.2\wrtusdrflem:crank-bound and Lemma 3.4\wrtusdrfclaim:cool-crank-value,

\Lambda(c_{\pi_{1}},c_{\pi_{2}},c_{\pi_{3}})\leqslant n^{k(\pi_{1},\pi_{2},\pi_{3})-\operatorname{rank}(\pi_{1})-\operatorname{rank}(\pi_{2})-\operatorname{rank}(\pi_{3})}.

Hence

	$\displaystyle\Lambda(Q,Q,Q)$	$\displaystyle=\sum_{\pi_{1},\pi_{2},\pi_{3}\in\Pi^{(2)}_{A}}\sigma_{\pi_{1}}^{(\delta)}\sigma_{\pi_{2}}^{(\delta)}\sigma_{\pi_{3}}^{(\delta)}\Lambda(c_{\pi_{1}},c_{\pi_{2}},c_{\pi_{3}})$
		$\displaystyle\leqslant\sum_{\pi_{1},\pi_{2},\pi_{3}\in\Pi^{(2)}_{A}}\sigma_{\pi_{1}}^{(\delta)}\sigma_{\pi_{2}}^{(\delta)}\sigma_{\pi_{3}}^{(\delta)}n^{k(\pi_{1},\pi_{2},\pi_{3})-\operatorname{rank}(\pi_{1})-\operatorname{rank}(\pi_{2})-\operatorname{rank}(\pi_{3})}$
		$\displaystyle=\sum_{\pi\in\Pi_{A}}\prod_{p\in\pi}\sum_{\begin{subarray}{c}\pi_{1},\pi_{2},\pi_{3}\in\Pi^{(2)}_{p}\\ \pi_{1}\vee\pi_{2}\vee\pi_{3}=\{p\}\end{subarray}}n^{k(\pi_{1},\pi_{2},\pi_{3})}\prod_{i\in[3]}\sigma_{\pi_{i}}^{(\delta)}n^{-{\operatorname{rank}(\pi_{i})}}.$

In the last sum above, since $\pi_{1}\vee\pi_{2}\vee\pi_{3}=\{p\}$ , $k(\pi_{1},\pi_{2},\pi_{3})$ is $0$ or $1$ according to whether $\pi_{1},\pi_{2},\pi_{3}\in\mathcal{M}_{p}$ . Splitting the sum according to these cases,

	$\displaystyle\Lambda(Q,Q,Q)$	$\displaystyle\leqslant\sum_{\pi\in\Pi_{A}}\prod_{p\in\pi}\bigg{(}\sum_{\begin{subarray}{c}\pi_{1},\pi_{2},\pi_{3}\in\Pi^{(2)}_{p}\\ \pi_{1}\vee\pi_{2}\vee\pi_{3}=\{p\}\end{subarray}}\prod_{i\in[3]}\sigma_{\pi_{i}}^{(\delta)}n^{-{\operatorname{rank}(\pi_{i})}}$
		$\displaystyle\qquad+\sum_{\begin{subarray}{c}\pi_{1},\pi_{2},\pi_{3}\in\mathcal{M}_{p}\\ \pi_{1}\vee\pi_{2}\vee\pi_{3}=\{p\}\end{subarray}}n\prod_{i\in[3]}\sigma_{\pi_{i}}^{(\delta)}n^{-{\operatorname{rank}(\pi_{i})}}\bigg{)}.$

In the second sum we will ignore the constraint $\pi_{1}\vee\pi_{2}\vee\pi_{3}=\{p\}$ ; in the first sum we will use only $\operatorname{rank}(\pi_{1})+\operatorname{rank}(\pi_{2})+\operatorname{rank}(\pi_{3})\geqslant\operatorname{rank}(\pi_{1}\vee\pi_{2}\vee\pi_{3})=|p|-1$ .

Fix parameters $w_{r}\geqslant 1$ for all $r\geqslant 1$ . Define

	$\displaystyle\alpha_{r}(x)$	$\displaystyle=\sum_{\pi\in\Pi_{r}^{(2)}}\sigma_{\pi}^{(\delta)}x^{\operatorname{rank}(\pi)},$
	$\displaystyle\alpha_{r}^{\prime}(x)$	$\displaystyle=\sum_{\pi\in\mathcal{M}_{r}}\sigma_{\pi}^{(\delta)}x^{\operatorname{rank}(\pi)}=\|\mathcal{M}_{r}\|x^{r/2},$
	$\displaystyle\beta_{r}(x)$	$\displaystyle=\sum_{\pi\in\Pi_{r}}\prod_{p\in\pi}{\left(w_{\|p\|}^{-(\|p\|-1)}\alpha_{\|p\|}(w_{\|p\|}x)^{3}+x^{-1}\alpha^{\prime}_{\|p\|}(x)^{3}\right)}.$

Then, by the discussion above,

\Lambda(Q,Q,Q)\leqslant\beta_{m}(1/n).

Three applications of the exponential formula (3.1) give

$\displaystyle\sum_{r\geqslant 0}\frac{y^{r}}{r!}\alpha_{r}(x)$	$\displaystyle=\exp(\delta y+xy^{2}/2),$	(6.4)
$\displaystyle\sum_{r\geqslant 0}\frac{y^{r}}{r!}\alpha_{r}^{\prime}(x)$	$\displaystyle=\exp(xy^{2}/2),$	(6.5)
$\displaystyle\sum_{r\geqslant 0}\frac{y^{r}}{r!}\beta_{r}(x)$	$\displaystyle=\exp{\left(\sum_{r\geqslant 1}\frac{y^{r}w_{r}^{-r+1}\alpha_{r}(w_{r}x)^{3}}{r!}+\sum_{r\geqslant 2~{}\text{even}}\frac{y^{r}x^{-1}\alpha_{r}^{\prime}(x)^{3}}{r!}\right)}.$	(6.6)

From (6.4), for real $y>0$ ,

\alpha_{r}(x)\leqslant\frac{r!}{y^{r}}\exp(\delta y+xy^{2}/2).

Replacing $x$ with $w_{r}x$ , putting $w_{r}=\delta^{2}/(xr)$ (we will ensure later that $w_{r}\geqslant 1$ for $1\leqslant r\leqslant m$ ) and $y=r/\delta$ gives

w_{r}^{-r+1}\alpha_{r}(w_{r}x)^{3}\leqslant e^{O(r)}r^{r}\delta^{r+2}x^{r-1}.

From (6.5) with $y=(r/x)^{1/2}$ we have

\alpha^{\prime}_{r}(x)\leqslant\frac{r!}{y^{r}}\exp(xy^{2}/2)\asymp r^{1/2}(rx/e)^{r/2}

(alternatively, this follows directly from $\alpha^{\prime}_{r}(x)=|\mathcal{M}_{r}|x^{r/2}$ ). Hence, from (6.6) for $x,y>0$ ,

\beta_{m}(x)\leqslant\frac{m!}{y^{m}}\exp b(x,y),

(6.7)

where $b$ is the truncated sum

	$\displaystyle b(x,y)$	$\displaystyle=\sum_{r=1}^{m}\frac{y^{r}w_{r}^{-r+1}\alpha_{r}(w_{r}x)^{3}}{r!}+\sum_{r=2}^{m}\frac{y^{r}x^{-1}\alpha_{r}^{\prime}(x)^{3}}{r!}$
		$\displaystyle\ll\sum_{r=1}^{m}e^{O(r)}\delta^{r+2}x^{r-1}y^{r}+\sum_{r=2}^{m}r^{O(1)}(e^{-1/2}r^{1/2}x^{3/2}y)^{r}x^{-1}.$

Inserting $x=1/n$ and $\delta=(Cm/n)^{1/2}$ ,

b(1/n,y)\ll\sum_{r=1}^{m}O(m^{1/2}y/n^{3/2})^{r}m+\sum_{r=2}^{m}r^{O(1)}(e^{-1/2}r^{1/2}y/n^{3/2})^{r}n.

Note that $w_{r}=Cm/r$ , and this is indeed at least 1 for $r\leqslant m$ since we may assume $C\geqslant 1$ . Finally, let $y=cn^{3/2}/m^{1/2}$ for a sufficiently small constant $c>0$ . Then

b(1/n,y)\ll m+n/m.

Hence, from (6.7),

\Lambda(Q,Q,Q)\leqslant\beta_{m}(1/n)\leqslant\frac{m!}{y^{m}}\exp b(1/n,y)\ll(m/n)^{3m/2}e^{O(m+n/m)},

as claimed. ∎

Putting the last few results together, we have the following theorem, which clearly implies Theorem 2.3\wrtusdrfthm:sparse-minor.

Theorem 6.8.

We have

\Lambda(|P_{A}1_{S}|,|P_{A}1_{S}|,|P_{A}1_{S}||)\leqslant{\left(\frac{n!}{n^{n}}\right)}^{3}(m/n)^{9m/8}e^{O(m+n/m)}.

Proof.

From Corollary 6.6,

\Lambda(R,R,R)\leqslant\Lambda(R^{\sharp},R^{\sharp},R^{\sharp})+{\left(\frac{n!}{n^{n}}\right)}^{3}e^{O(m)}(m/n)^{(1+\epsilon/2)m}.

By (6.3) and the previous lemma the main term is

	$\displaystyle\Lambda(R^{\sharp},R^{\sharp},R^{\sharp})$	$\displaystyle\leqslant{\left(\frac{n!}{n^{n}}\right)}^{3}e^{O(m)}(m/n)^{-3\epsilon m/2}\Lambda(Q,Q,Q)$
		$\displaystyle\leqslant{\left(\frac{n!}{n^{n}}\right)}^{3}(m/n)^{(1-\epsilon)3m/2}e^{O(m+n/m)}.$

Set $\epsilon=1/4$ . ∎

7. Dense minor arcs

Figure 1. A transition

(x,y)\mapsto(x^{\prime},y^{\prime})

in the Markov chain

Define a Markov chain on $X\times Y$ as follows. If the current state is $(x,y)$ , pick uniformly at random $z\in Z$ . The next state is $(x^{\prime},y^{\prime})$ , where $x^{\prime}$ and $y^{\prime}$ are the unique solutions to

(x,y^{\prime},z),(x^{\prime},y,z)\in\mathsf{L}

(see Figure 1\wrtusdrffig:markov-chain). Let $\mathcal{A}$ be the transition operator for this Markov chain:

\mathcal{A}(f)(x,y)=\frac{1}{n}\sum_{(x,y^{\prime},z),(x^{\prime},y,z)\in\mathsf{L}}f(x^{\prime},y^{\prime}).

The Markov chain is reversible with uniform stationary distribution, so $\mathcal{A}$ is self-adjoint and has the constant function on $X\times Y$ as a $1$ -eigenvector. Let $\mathcal{U}$ be the projection to constants:

\mathcal{U}(f)(x,y)=\frac{1}{n^{2}}\sum_{x^{\prime},y^{\prime}}f(x^{\prime},y^{\prime}).

Definition 7.1.

We say $\mathsf{L}$ is $\mathcal{A}$ -quasirandom with parameter $\rho$ if $\mathcal{A}-\mathcal{U}$ has spectral radius at most $\rho$ .

In particular, $\rho<1$ if and only if the Markov chain is connected, and in general $\rho$ measures the rate of mixing.

Remark 7.2.

For a finite set $T$ , let $L^{2}(T)_{0}$ denote the subspace $\bigl{\{}f\in L^{2}(T)\colon\mathbf{E}f=0\bigr{\}}$ . Then equivalently, $\mathsf{L}$ is $\mathcal{A}$ -quasirandom with parameter $\rho$ if the restriction $\mathcal{A}|_{L^{2}(X\times Y)_{0}}$ has spectral radius at most $\rho$ .

All our applications of quasirandomness go through the following lemma.

Lemma 7.3.

Assume $\mathsf{L}$ is $\mathcal{A}$ -quasirandom with parameter $\rho$ and¹¹1Note that the $m=1$ case of (7.1) does not obviously imply the general case: the operator-type norm for trilinear forms does not behave well under taking tensor powers. let $m\geqslant 1$ . Then

|\Lambda(f,g,h)|\leqslant\rho^{m/2}\|f\|_{2}\|g\|_{2}\|h\|_{2}

(7.1)

for all $f\in L^{2}(X)_{0}^{\otimes m}$ , $g\in L^{2}(Y)_{0}^{\otimes m}$ , $h\in L^{2}(Z)_{0}^{\otimes m}$ .

Remark 7.4.

Identifying $L^{2}(X)^{\otimes m}$ with $L^{2}(X^{m})$ in the usual way, $L^{2}(X)_{0}^{\otimes m}$ is identified with the subspace $\operatorname{im}P_{[m]}\subseteq L^{2}(X^{m})$ ; see (2.2).

Proof of Lemma 7.3\wrtusdrflem:quasi-use.

By Cauchy–Schwarz,

	$\displaystyle\|\Lambda(f,g,h)\|$	$\displaystyle=\left\|\mathbf{E}_{(x,y,z)\in\mathsf{L}^{m}}f(x)g(y)h(z)\right\|$
		$\displaystyle\leqslant{\left(\mathbf{E}_{z}\left\|\mathbf{E}_{x,y:(x,y,z)\in\mathsf{L}^{m}}f(x)g(y)\right\|^{2}\right)}^{1/2}\\|h\\|_{2}$
		$\displaystyle={\left(\mathbf{E}_{z,x,y,x^{\prime},y^{\prime}:(x,y,z),(x^{\prime},y^{\prime},z)\in\mathsf{L}^{m}}f(x)g(y){\bar{f}}(x^{\prime}){\bar{g}}(y^{\prime})\right)}^{1/2}\\|h\\|_{2}$
		$\displaystyle=\langle\mathcal{A}^{\otimes m}(f\otimes\bar{g}),f\otimes\bar{g}\rangle^{1/2}\\|h\\|_{2}.$

Note $\|f\otimes\bar{g}\|_{2}=\|f\|_{2}\|g\|_{2}$ , and that $f\otimes\overline{g}\in L^{2}(X\times Y)_{0}^{\otimes m}$ . Since $\mathcal{A}|_{L^{2}(X\times Y)_{0}}$ has spectral radius at most $\rho$ , the tensor power $\mathcal{A}^{\otimes m}|_{L^{2}(X\times Y)_{0}^{\otimes m}}$ has spectral radius (and hence operator norm) at most $\rho^{m}$ , so the last expression above is bounded by $\rho^{m/2}\|f\|_{2}\|g\|_{2}\|h\|_{2}$ . ∎

Remark 7.5.

As stated in the introduction, while Definition 7.1\wrtusdrfdef:quasirandom has some nice properties (e.g., the spectral radius of $\mathcal{A}-\mathcal{U}$ can be computed efficiently), it is chosen for mainly practical rather than philosophical reasons, and there are similar but qualitatively inequivalent conditions that would work equally well.

One notable criticism of this definition is that latin squares associated to Steiner triple systems (i.e., where $X=Y=Z$ and $\mathsf{L}$ contains the diagonal $\{(x,x,x)\colon x\in X\}$ and is invariant under the $S_{3}$ -action on triples) always fail to be $\mathcal{A}$ -quasirandom with parameter $\rho<1$ (since the diagonal $\{(x,x):x\in X\}$ of $X\times X$ is a closed set for the Markov chain). On the other hand, a random Steiner triple system is far from having algebraic structure and presumably satisfies (7.1) for $\rho=o(1)$ with high probability as $n\to\infty$ .

One point of view is that (7.1) itself is the more natural quasirandomness condition (but harder to verify), and Definition 7.1\wrtusdrfdef:quasirandom is a convenient sufficient condition.

Proof of Theorem 2.4\wrtusdrfthm:dense-minor.

Let $A\subseteq[n]$ and $|A|=m$ . By Lemmas 7.3 and 7.2\wrtusdrflem:quasi-use,rem:l20,

|\Lambda(P_{A}1_{S},P_{A}1_{S},P_{A}1_{S})|\leqslant\rho^{m/2}\|P_{A}1_{S}\|_{2}^{3}\leqslant\rho^{m/2}\|1_{S}\|_{2}^{3}=\rho^{m/2}{\left(\frac{n!}{n^{n}}\right)}^{3}.

Hence, for $\rho\leqslant 1$ ,

\sum_{|A|\geqslant m}|\Lambda(P_{A}1_{S},P_{A}1_{S},P_{A}1_{S})|\leqslant 2^{n}\rho^{m/2}{\left(\frac{n!}{n^{n}}\right)}^{3}.

Taking $m=\epsilon n$ and $\rho$ so that $2\rho^{\epsilon/2}\leqslant 1/10$ , the result follows. ∎

8. Quasirandomness

In this section we will verify that two natural classes of latin squares are $\mathcal{A}$ -quasirandom with parameter $o(1)$ :

•

multiplication tables of quasirandom groups;
•

uniformly random $n\times n$ latin squares, with high probability as $n\to\infty$ .

In the case of a group we can compute the whole spectrum of $\mathcal{A}$ using representation theory. In the case of a random latin square we will use the bound

1+\rho^{6}\leqslant\operatorname{tr}\mathcal{A}^{6}

which holds because the spectrum of $\mathcal{A}$ is real and $6$ is even. By interpreting $n^{6}\operatorname{tr}\mathcal{A}^{6}$ as counting certain kinds of configuration in $\mathsf{L}$ (and using a recent result of [KSSS]) we will show that $\operatorname{tr}\mathcal{A}^{6}=1+o(1)$ with high probability, which implies that $\rho=o(1)$ . (Using the same method one can show that $\operatorname{tr}\mathcal{A}^{4}=3+o(1)$ with high probability, so $6$ is the smallest even integer that we can use for this argument.)

8.1. Quasirandom groups

The following proposition shows that our quasirandomness condition generalizes the definition of a quasirandom group (see [gowers]), implying Theorem 1.4.

Proposition 8.1.

Suppose $\mathsf{L}$ is the multiplication table of a group $G$ . Then the spectrum of $\mathcal{A}$ consists of $d^{3}(d+1)/2$ copies of $1/d$ and $d^{3}(d-1)/2$ copies of $-1/d$ for every $d$ -dimensional irreducible representation of $G$ , and $n^{2}-\sum_{\chi\in\operatorname{Irr}(G)}\chi(1)^{4}$ zeros. In particular $\rho=1/D$ where $D$ is the minimal dimension of a nontrivial representation of $G$ .

Proof.

Here $X=Y=Z=G$ and $\mathsf{L}=\{(x,y,z)\in G^{3}:xy=z\}$ , so $L^{2}(X\times Y)=L^{2}(G\times G)$ and $\mathcal{A}$ is the operator defined by

\mathcal{A}(f)(x,y)=\frac{1}{n}\sum_{z\in G}f(zy^{-1},x^{-1}z).

By representation theory, $L^{2}(G)$ has an orthogonal basis consisting of the functions of the form $x\mapsto\langle\rho(x)e_{i},e_{j}\rangle$ , where $\rho\colon G\to U(V)$ is an irreducible unitary representation of $G$ and $e_{1},\dots,e_{\dim V}$ is an orthonormal basis of $V$ .

It follows that $L^{2}(G\times G)\cong L^{2}(G)\otimes L^{2}(G)$ has an orthogonal basis consisting of functions of the form

f_{\rho,\rho^{\prime},i,j,k,\ell}(x,y)=\bigl{\langle}\rho(x)e_{i},e_{j}\bigr{\rangle}\bigl{\langle}e^{\prime}_{\ell},\rho^{\prime}(y)e^{\prime}_{k}\bigr{\rangle}

where $\rho\colon G\to U(V)$ and $\rho^{\prime}\colon G\to U(V^{\prime})$ are two irreducible unitary representations of $G$ and $1\leqslant i,j\leqslant\dim V$ , $1\leqslant k,\ell\leqslant\dim V^{\prime}$ .

To find $\mathcal{A}(f_{\rho,\rho^{\prime},i,j,k,\ell})$ we recall the Schur orthogonality relation for matrix coefficients, which states that for irreducible $V$ , $V^{\prime}$ as above, $a,b\in V$ and $a^{\prime},b^{\prime}\in V^{\prime}$ ,

\frac{1}{n}\sum_{z\in G}\langle\rho(z)a,b\rangle\langle b^{\prime},\rho^{\prime}(z)a^{\prime}\rangle=\begin{cases}0&\colon(\rho,V)\ncong(\rho^{\prime},V^{\prime})\\ \frac{1}{\dim V}\langle a,a^{\prime}\rangle\langle b^{\prime},b\rangle&\colon(\rho,V)=(\rho^{\prime},V^{\prime}),\end{cases}

and thereby compute

	$\displaystyle\mathcal{A}(f_{\rho,\rho^{\prime},i,j,k,\ell})(x,y)$	$\displaystyle=\frac{1}{n}\sum_{z\in G}\bigl{\langle}\rho(z)\rho(y^{-1})e_{i},e_{j}\bigr{\rangle}\bigl{\langle}\rho(x)e^{\prime}_{\ell},\rho(z)e^{\prime}_{k}\bigr{\rangle}$
		$\displaystyle=\begin{cases}0&\colon(\rho,V)\ncong(\rho^{\prime},V^{\prime})\\ \frac{1}{\dim V}\bigl{\langle}\rho(x)e_{\ell},e_{j}\bigr{\rangle}\bigl{\langle}e_{i},\rho(y)e_{k}\bigr{\rangle}&\colon(\rho,V)=(\rho^{\prime},V^{\prime})\end{cases}$
		$\displaystyle=\begin{cases}0&\colon(\rho,V)\ncong(\rho^{\prime},V^{\prime})\\ \frac{1}{\dim V}f_{\rho,\rho,\ell,j,k,i}(x,y)&\colon(\rho,V)=(\rho^{\prime},V^{\prime}).\end{cases}$

In the case $\rho\neq\rho^{\prime}$ we get an eigenfunction with eigenvalue $0$ . When $\rho=\rho^{\prime}$ and $i=\ell$ we get a $(1/\dim V)$ -eigenfunction. Finally when $\rho=\rho^{\prime}$ and $i\neq\ell$ , the functions

f_{\rho,\rho,i,j,k,\ell}\pm f_{\rho,\rho,\ell,j,k,i}

are eigenfunctions of $\mathcal{A}$ with eigenvalues $\pm 1/\dim V$ respectively.

Altogether we have $d^{3}+d^{3}(d-1)/2=d^{3}(d+1)/2$ copies of $1/d$ and $d^{3}(d-1)/2$ copies of $-1/d$ , and the rest $0$ , as claimed.

∎

8.2. Random latin squares

We will use a recent result of Kwan, Sah, Sawhney, and Simkin [KSSS] on configuration counts in random latin squares. A triple system is a 3-uniform 3-partite hypergraph $\mathsf{H}\subseteq X_{\mathsf{H}}\times Y_{\mathsf{H}}\times Z_{\mathsf{H}}$ with vertex classes $X_{\mathsf{H}},Y_{\mathsf{H}},Z_{\mathsf{H}}$ . The number of vertices is $v=|X_{\mathsf{H}}|+|Y_{\mathsf{H}}|+|Z_{\mathsf{H}}|$ and the number of triples (hyperedges) is $e=|\mathsf{H}|$ . We say $\mathsf{H}$ is latin if every pair of vertices is in at most one triple. (A latin square of order $n$ is then a latin triple system with 3 classes of $n$ vertices and $n^{2}$ triples.)

Let $\mathsf{H}$ be a fixed triple system. A copy of $\mathsf{H}$ in a triple system $\mathsf{L}$ is a triple of injective maps

X_{\mathsf{H}}\to X_{\mathsf{L}},\qquad Y_{\mathsf{H}}\to Y_{\mathsf{L}},\qquad Z_{\mathsf{H}}\to Z_{\mathsf{L}}

which maps triples to triples. Let $N_{\mathsf{H}}(\mathsf{L})$ denote the number of copies of $\mathsf{H}$ in $\mathsf{L}$ .

Let $\mathsf{B}_{n}$ denote the random triple system $\mathsf{B}_{n}\subseteq[n]\times[n]\times[n]$ in which each possible triple is present independently with probability $1/n$ . Note that $\mathbf{E}[N_{\mathsf{H}}(\mathsf{B}_{n})]=(1-o(1))n^{v-e}$ (when $\mathsf{H}$ is fixed and $n$ is large). We say $\mathsf{H}$ is $\alpha$ -stable if $\alpha\geqslant v-e$ and

\mathbf{E}[N_{\mathsf{H}}(\mathsf{B}_{n})\mid\mathsf{Q}\subseteq\mathsf{B}_{n}]-\mathbf{E}[N_{\mathsf{H}}(\mathsf{B}_{n})]=o(n^{\alpha})

for any latin triple system $\mathsf{Q}\subseteq[n]\times[n]\times[n]$ with at most $n(\log n)^{3}$ triples.

Theorem 8.2 ([KSSS, Theorem 7.2]).

Fix an $\alpha$ -stable latin triple system $\mathsf{H}$ with $v$ vertices and $e$ triples. Let $\mathsf{L}$ be a uniformly random latin square. Then

N_{\mathsf{H}}(\mathsf{L})\leqslant n^{v-e}+o(n^{\alpha})

with high probability as $n\to\infty$ .

In order to use this theorem effectively we need a computable form of stability. Let $\mathsf{H}$ be a latin triple system. A subset of the vertices $S\subseteq X_{\mathsf{H}}\cup Y_{\mathsf{H}}\cup Z_{\mathsf{H}}$ is called closed if whenever two vertices of a triple of $\mathsf{H}$ is in $S$ , so is the third. The closure $\langle S\rangle_{\mathsf{H}}$ of a subset $S$ if the smallest closed set containing it. If $\mathsf{F}\subseteq\mathsf{H}$ let $X_{\mathsf{F}},Y_{\mathsf{F}},Z_{\mathsf{F}}$ denote the vertices incident with at least one member of $\mathsf{F}$ , and let $v(\mathsf{F})=|X_{\mathsf{F}}|+|Y_{\mathsf{F}}|+|Z_{\mathsf{F}}|$ and $e(\mathsf{F})=|\mathsf{F}|$ . We say $\mathsf{F}\subseteq\mathsf{H}$ generates $\mathsf{H}$ if

\langle X_{\mathsf{F}}\cup Y_{\mathsf{F}}\cup Z_{\mathsf{F}}\rangle_{\mathsf{H}}=X_{\mathsf{H}}\cup Y_{\mathsf{H}}\cup Z_{\mathsf{H}}.

Let

d(\mathsf{H})=\min\{e(\mathsf{F}):\mathsf{F}~{}\text{generates}~{}\mathsf{H}\}.

For example, if $\mathsf{H}_{1}$ is the latin triple system shown in Figure 2\wrtusdrffig:trAdj6, one generating set consists of both triples containing $z_{1}$ , one triple containing $z_{3}$ , and one triple containing $z_{5}$ , and there is no smaller generating set, so $d(\mathsf{H}_{1})=4$ .

Lemma 8.3.

Let $\mathsf{H}$ be a latin triple system with $v$ vertices and $e$ triples. Then $\mathsf{H}$ is $\alpha$ -stable provided $\alpha\geqslant v-e$ and

\alpha>v-e+\max_{\emptyset\neq\mathsf{F}\subseteq\mathsf{H}}\bigl{(}d(\mathsf{F})-v(\mathsf{F})+e(\mathsf{F})\bigr{)}.

Remark 8.4.

A much simpler model problem is the following: given a fixed graph $H$ and a random graph $G_{n,p}$ , does $G$ contain $n^{v(H)}p^{e(H)}(1+o(1))$ copies of $H$ (i.e., close to the expected number) with high probability? The answer might be no if $H$ contains a subgraph $H^{\prime}$ with much greater density than $H$ in some sense: indeed, if $n^{v(H^{\prime})}p^{e(H^{\prime})}=o(1)$ then with high probability $G(n,p)$ contains zero copies of $H^{\prime}$ , and hence of $H$ . However, this is essentially all that can go wrong. The condition for $\alpha$ -stability in the lemma captures a similar intuition.

Remark 8.5.

Given a triple system $\mathsf{H}\subseteq X_{\mathsf{H}}\times Y_{\mathsf{H}}\times Z_{\mathsf{H}}$ , one can construct a partition triple $\mathfrak{P}=(\pi_{1},\pi_{2},\pi_{3})\in\Pi_{\mathsf{H}}^{3}$ in the sense of Section 3.1 (i.e., the ground set has size $e(\mathsf{H})$ ) where two triples $(x,y,z),(x^{\prime},y^{\prime},z^{\prime})\in\mathsf{H}$ lie in the same cell of $\pi_{1}$ if and only if $x=x^{\prime}$ , and similarly for $\pi_{2}$ and $y=y^{\prime}$ , and $\pi_{3}$ and $z=z^{\prime}$ .

The construction can be reversed (up to the issue of repeated edges). In other words, triple systems and partition triples are more-or-less the same objects. Under this analogy, the notion of closure here coincides with that in Definition 3.1, and $\operatorname{crank}(\mathfrak{P})=2e(\mathsf{H})-d(\mathsf{H})$ .

Although using both languages is strictly speaking redundant, it is useful to keep the two notions separate, partly for minor technical reasons, but mainly because using partition systems follows our previous work in [EMM-cyclic, EMM] while using triple systems follows [KSSS].

Proof of Lemma 8.3\wrtusdrflem:stability-lemma.

(Cf. [KSSS, p. 15]) Let $\mathsf{Q}\subseteq[n]^{3}$ be a latin triple system with at most $n^{1+o(1)}$ triples. For a copy of $\mathsf{H}$ in $\mathsf{B}_{n}$ , say one of its triples is forced if it appears in $\mathsf{Q}$ . The difference

\mathbf{E}[N_{\mathsf{H}}(\mathsf{B}_{n})\mid\mathsf{Q}\subseteq\mathsf{B}_{n}]-\mathbf{E}[N_{\mathsf{H}}(\mathsf{B}_{n})]

(8.1)

arises from copies of $\mathsf{H}$ with at least one forced triple. Let $\mathsf{F}\subseteq\mathsf{H}$ be a nonempty subsystem and consider copies of $\mathsf{H}$ whose forced triples are precisely the images of those in $\mathsf{F}$ . Let $\mathsf{F}_{0}\subseteq\mathsf{F}$ be a generating subsystem of size $d(\mathsf{F})$ . Because $\mathsf{Q}$ satisfies the latin property, any copy of $\mathsf{F}$ in $\mathsf{Q}$ is determined by the image of $\mathsf{F}_{0}$ . Therefore the number of copies of $\mathsf{F}$ in $\mathsf{Q}$ is at most $|\mathsf{Q}|^{|\mathsf{F}_{0}|}$ . There are $v-v(\mathsf{F})$ vertices of $\mathsf{H}$ outside $\mathsf{F}$ , each with $n$ possible images in $[n]^{3}$ , and the image of each of the $e-e(\mathsf{F})$ triples outside $\mathsf{F}$ has probability $1/n$ (independently) of being present in $\mathsf{B}_{n}$ . Hence the contribution to (8.1) from $\mathsf{F}$ is bounded by

|\mathsf{Q}|^{|\mathsf{F}_{0}|}n^{v-v(\mathsf{F})}(1/n)^{e-e(\mathsf{F})}=n^{v-e+d(\mathsf{F})-v(\mathsf{F})+e(\mathsf{F})+o(1)}.

This is $o(n^{\alpha})$ provided the stated condition is satisfied. ∎

Figure 2. The chain

(x_{0},y_{0}),\dots,(x_{6},y_{6})

and the latin triple system

\mathsf{H}_{1}

defined by identifying

x_{0}

with

x_{6}

and

y_{0}

with

y_{6}

Now we can show that random latin squares are $\mathcal{A}$ -quasirandom with parameter $o(1)$ with high probability (Theorem 1.3\wrtusdrfthm:random-implies-quasirandom). This follows from the following proposition and the bound $1+\rho^{6}\leqslant\operatorname{tr}\mathcal{A}^{6}$ .

Proposition 8.6.

For a uniformly random latin square $\mathsf{L}$ ,

\operatorname{tr}\mathcal{A}^{6}=1+o(1)

with high probability as $n\to\infty$ .

Proof (computer-assisted).

For $(x_{0},y_{0})\in X\times Y$ , let $(x_{i},y_{i})$ denote the iterates of $(x_{0},y_{0})$ under the Markov chain defining $\mathcal{A}$ . Then

\operatorname{tr}\mathcal{A}^{6}=\sum_{x_{0},y_{0}}\mathbf{P}\bigl{(}(x_{6},y_{6})=(x_{0},y_{0})\bigr{)}=N/n^{6},

where $N$ is the number of configurations in $\mathsf{L}$ of the form shown in Figure 2\wrtusdrffig:trAdj6 with $x_{0}=x_{6}$ and $y_{0}=y_{6}$ . We do not assume the other vertices are distinct.

Let $\mathsf{H}_{1}$ be the latin triple system depicted in Figure 2\wrtusdrffig:trAdj6 and let $\mathsf{H}_{2},\dots,\mathsf{H}_{k}$ (where $k$ is bounded) be all the degenerations obtainable by identifying some (like-colored) vertices and identifying triangles as necessary to preserve the latin property.

Formally, we consider all triples of partitions $(\pi_{X},\pi_{Y},\pi_{Z})$ where $\pi_{X}\in\Pi_{X_{\mathsf{H}_{1}}}$ , $\pi_{Y}\in\Pi_{Y_{\mathsf{H}_{1}}}$ , $\pi_{Z}\in\Pi_{Z_{\mathsf{H}_{1}}}$ satisfying the following closure property: if $(x,y,z)$ and $(x^{\prime},y^{\prime},z^{\prime})$ are two triples of $\mathsf{H}_{1}$ and two of the pairs $(x,x^{\prime})$ , $(y,y^{\prime})$ , $(z,z^{\prime})$ are in the same cell of $\pi_{X}$ , $\pi_{Y}$ , $\pi_{Z}$ respectively then so is the third. Number such triples of partitions $1,\dots,k$ , where $1$ corresponds to three copies of the discrete partition. Then $\mathsf{H}_{i}$ denotes the quotient hypergraph of $\mathsf{H}_{1}$ with respect to partition $i$ .

Let $N_{i}=N_{\mathsf{H}_{i}}(\mathsf{L})$ . Then $N=N_{1}+\cdots+N_{k}$ . Let $v_{i}=v(\mathsf{H}_{i})$ and $e_{i}=e(\mathsf{H}_{i})$ . Then $v_{1}-e_{1}=18-12=6$ . Now the proposition follows from Theorem 8.2\wrtusdrfthm:KSSS, Lemma 8.3\wrtusdrflem:stability-lemma, and the following two claims:

(1)

$v_{i}-e_{i}\leqslant 5$ for each $i>1$ ,
(2)

$v_{i}-e_{i}+\max_{\emptyset\neq\mathsf{F}\subseteq\mathsf{H}}\bigl{(}d(\mathsf{F})-v(\mathsf{F})+e(\mathsf{F})\bigr{)}\leqslant 5$ for each $i\geqslant 1$ .

Indeed, provided (1) and (2) hold, Lemma 8.3\wrtusdrflem:stability-lemma shows that $\mathsf{H}_{i}$ is $6$ -stable for each $i\geqslant 1$ , so Theorem 8.2\wrtusdrfthm:KSSS implies that $N_{i}\leqslant n^{v_{i}-e_{i}}+o(n^{6})$ with high probability for each $i$ , so $N\leqslant(1+o(1))n^{6}$ with high probability.

Both claims can be verified by exhaustive search. We find $\mathsf{H}_{2},\dots,\mathsf{H}_{k}$ by starting with $\mathsf{H}_{1}$ and iteratively identifying pairs of vertices, using breadth-first search. Thus we verify (1). Now for each $\mathsf{H}_{i}$ we check all subsystems $\mathsf{F}\subseteq\mathsf{H}_{i}$ and compute $d(\mathsf{F})$ by checking all $\mathsf{F}_{0}\subseteq\mathsf{F}$ , and thus we verify (2).

It turns out $k=1206$ , and there are $154$ distinct isomorphism classes among the degenerations $\mathsf{H}_{i}$ . The quantity in (2) turns out to be at most 4 in all cases except $\mathsf{H}_{1}$ , for which it is $5$ . There are just eight degenerations $\mathsf{H}_{i}$ (up to isomorphism) for which $v_{i}-e_{i}=5$ . Of these, four are just $\mathsf{H}_{1}$ with a single pair of vertices identified (so $v_{i}=17$ and $e_{i}=12$ ). The other four cases are shown in Figure 3\wrtusdrffig:degenerations. These cases are therefore the dominant contributors to the error term. ∎

(a)

v=16

,

e=11

(b)

v=15

,

e=10

(c)

v=11

,

e=6

(d)

v=11

,

e=6

Figure 3. Degenerations of

\mathsf{H}_{1}

with

v_{i}-e_{i}=5

and

e_{i}<12

. Some triangles are shown flat.

	$\displaystyle\|\Lambda(f,g,h)\|$	$\displaystyle=\left\|\mathbf{E}_{(x,y,z)\in\mathsf{L}^{m}}f(x)g(y)h(z)\right\|$
		$\displaystyle\leqslant{\left(\mathbf{E}_{z}\left\|\mathbf{E}_{x,y:(x,y,z)\in\mathsf{L}^{m}}f(x)g(y)\right\|^{2}\right)}^{1/2}\\|h\\|_{2}$
		$\displaystyle={\left(\mathbf{E}_{z,x,y,x^{\prime},y^{\prime}:(x,y,z),(x^{\prime},y^{\prime},z)\in\mathsf{L}^{m}}f(x)g(y){\bar{f}}(x^{\prime}){\bar{g}}(y^{\prime})\right)}^{1/2}\\|h\\|_{2}$
		$\displaystyle=\langle\mathcal{A}^{\otimes m}(f\otimes\bar{g}),f\otimes\bar{g}\rangle^{1/2}\\|h\\|_{2}.$

Transversals in quasirandom latin squares

Abstract.

1. Introduction

Theorem 1.1.

Theorem 1.2.

Theorem 1.3.

Theorem 1.4.

2. Outline

Lemma 2.1.

Proof.

2.1. Major arcs

Theorem 2.2.

2.2. Sparse minor arcs

Theorem 2.3.

2.3. Dense minor arcs

Theorem 2.4.

2.4. Quasirandomness

2.5. Proof of Theorem 1.2\wrtusdrfthm:main-quasirandom

Proof of Theorem 1.2\wrtusdrfthm:main-quasirandom.

2.6. Layout of the paper

3. Partitions and partition systems

3.1. Partitions

3.2. Partition systems

Definition 3.1 (Combinatorial rank).

Lemma 3.2.

Proof.

Lemma 3.3.

Proof.

3.3. Combinatorial rank of matching systems

Lemma 3.4.

Proof.

4. The “Fourier” expansion of 1S1_{S}

4.1. Formulas for PA​1SP_{A}1_{S}

Lemma 4.1.

Proof.

Lemma 4.2 ([EMM, Lemma 4.3]).

Lemma 4.3.

Proof.

Lemma 4.4.

Proof.

4.2. Sparseval

Lemma 4.5.

Proof.

Proposition 4.6.

Sketch.

Corollary 4.7.

Proof.

5. Major arcs

5.1. The quantities γ\gamma and γ0\gamma_{0}

Lemma 5.1.

Sketch.

5.2. The Mm​(z)M_{m}(z) series

Proposition 5.2.

Proof.

Corollary 5.3.

Proof.

5.3. The constant term Mm​(0)M_{m}(0)

6. Sparse minor arcs

6.1. A majorant for |PA​1S||P_{A}1_{S}|

Proposition 6.1.

Proof.

Lemma 6.2.

Proof.

Lemma 6.3.

Proof.

6.2. A splitting of |PA​1S||P_{A}1_{S}|

Lemma 6.4.

Proof.

Corollary 6.5.

Proof.

Corollary 6.6.

Proof.

6.3. The contribution from R♯R^{\sharp}

Lemma 6.7.

Proof.

Theorem 6.8.

Proof.

7. Dense minor arcs

Definition 7.1.

Remark 7.2.

4. The “Fourier” expansion of $1_{S}$

4.1. Formulas for $P_{A}1_{S}$

5.1. The quantities $\gamma$ and $\gamma_{0}$

5.2. The $M_{m}(z)$ series

5.3. The constant term $M_{m}(0)$

6.1. A majorant for $|P_{A}1_{S}|$

6.2. A splitting of $|P_{A}1_{S}|$

6.3. The contribution from $R^{\sharp}$