\documentclass[reqno, final,a4paper]{amsart}

\usepackage{color}
\usepackage[colorlinks=true,allcolors=blue
%,backref=page
]{hyperref}
\usepackage{amsmath, amssymb, amsthm,bbm}
\usepackage{mathrsfs}
%\usepackage[foot]{amsaddr}
\usepackage{mathtools}
\usepackage{cases}
\usepackage[noabbrev,capitalize,nameinlink]{cleveref}
\crefname{equation}{}{}
\usepackage{textalpha}
\usepackage{fullpage}
\usepackage[noadjust]{cite}
\usepackage[table]{xcolor}
\usepackage{graphics}
\usepackage{pifont}
\usepackage{tikz}
\usepackage[T1]{fontenc}
\usetikzlibrary{arrows.meta}
\newcommand{\cmark}{\text{\ding{51}}}
\newcommand{\xmark}{\text{\ding{55}}}
\usepackage{environ}
\usepackage{url}
\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
\usepackage[noend]{algpseudocode}
\usepackage[labelfont=bf]{caption}
\usepackage{framed}
\usepackage[framemethod=tikz]{mdframed}
\usepackage{pgfplots}
\usepgfplotslibrary{groupplots}
\usepackage{appendix}
\usepackage{graphicx}
\usepackage[textsize=tiny]{todonotes}


%\usepackage[shortlabels]{enumitem}
\usepackage{cancel}
\crefformat{enumi}{#2#1#3}
\crefrangeformat{enumi}{#3#1#4 to~#5#2#6}
\crefmultiformat{enumi}{#2#1#3}
{ and~#2#1#3}{, #2#1#3}{ and~#2#1#3}
\allowdisplaybreaks
\usepackage{paralist}
\usepackage[shortcuts]{extdash}

% \left(\right) should behave the same as ()
\let\originalleft\left
\let\originalright\right
\renewcommand{\left}{\mathopen{}\mathclose\bgroup\originalleft}
\renewcommand{\right}{\aftergroup\egroup\originalright}

\let\originalbig\big
\renewcommand{\big}{\mathopen{}\mathclose\originalbig}


\newcommand*{\claimproofname}{Proof of claim}
\newenvironment{claimproof}[1][\claimproofname]{\begin{proof}[#1]\renewcommand*{\qedsymbol}{\(\blacksquare\)}}{\end{proof}}


\crefname{equation}{}{} %remove ``Equation''
\newcommand{\creflastconjunction}{, and\nobreakspace} %Oxford comma
\AtBeginEnvironment{appendices}{\crefalias{section}{appendix}} %appendices

%\usepackage[color]{showkeys} %add in 'final' into parameter to remove showkeys
%\renewcommand\showkeyslabelformat[1]{\scalebox{.8}{\normalfont\footnotesize\ttfamily#1}\hspace{-.5em}}
% showkeys font
\colorlet{refkey}{orange!20}
\colorlet{labelkey}{blue!30}

\crefname{algocf}{Algorithm}{Algorithms}

% ------   Theorem Styles -------
\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}[theorem]{Claim}
\crefname{claim}{Claim}{Claims}
%\crefname{theorem}{Theorem}{Theorems}

\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem*{question*}{Question}
\newtheorem{fact}[theorem]{Fact}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem*{definition*}{Definition}
\newtheorem*{theorem*}{Theorem}
\newtheorem{example}[theorem]{Example}
\newtheorem{setup}[theorem]{Setup}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem*{remark*}{Remark}
\newtheorem*{notation}{Notation}

% ----- Delimiters ----
\newcommand{\abs}[1]{\left\lvert#1\right\rvert}
\newcommand{\norm}[1]{\left\lVert#1\right\rVert}
\newcommand{\snorm}[1]{\lVert#1\rVert}
\newcommand{\bnorm}[1]{\bigg\lVert#1\bigg\rVert}
\newcommand{\ang}[1]{\left\langle #1 \right\rangle}
\newcommand{\sang}[1]{\langle #1 \rangle}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\paren}[1]{\left( #1 \right)}
\newcommand{\sqb}[1]{\left[ #1 \right]}
\newcommand{\set}[1]{\left\{ #1 \right\}}
\newcommand{\setcond}[2]{\left\{ #1 \;\middle\vert\; #2 \right\}}
\newcommand{\cond}[2]{\left( #1 \;\middle\vert\; #2 \right)}
\newcommand{\sqcond}[2]{\left[ #1 \;\middle\vert\; #2 \right]}
\newcommand{\one}{\mathbbm{1}}

\newcommand{\mb}{\mathbb}
\newcommand{\mbf}{\mathbf}
\newcommand{\mbm}{\mathbbm}
\newcommand{\mc}{\mathcal}
\newcommand{\mf}{\mathfrak}
\newcommand{\mr}{\mathrm}
\newcommand{\msc}{\mathscr}
\newcommand{\ol}{\overline}
\newcommand{\on}{\operatorname}
\newcommand{\tsc}{\textsc}
\newcommand{\wh}{\widehat}
\newcommand{\wt}{\widetilde}
\newcommand{\edit}[1]{{\color{red}#1}}
\newcommand{\assign}{\leftarrow}
\newcommand{\Alg}{\mathcal{A}}
\newcommand{\bN}{\mathbb{N}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\Zt}{\widetilde{Z}}

\newcommand{\cE}{\mathcal{E}}
\newcommand{\eps}{\varepsilon}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\dd}{\,\mathrm{d}}
\DeclareMathOperator{\Aut}{Aut}

\renewcommand{\Pr}{\mb P}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\su}{\subseteq}

\global\long\def\mk#1{\textcolor{red}{\textbf{[MK comments:} #1\textbf{]}}}
\global\long\def\hp#1{\textcolor{magenta}{\textbf{[HP comments:} #1\textbf{]}}}
\global\long\def\ls#1{\textcolor{blue}{\textbf{[LS comments:} #1\textbf{]}}}
\global\long\def\zh#1{\textcolor{orange}{\textbf{[ZH comments:} #1\textbf{]}}}
\newcommand{\hide}[1]{}

\allowdisplaybreaks

\title{The constant Steiner kernel is not optimal at large girth}

\author[Kwan]{Matthew Kwan}

\address{Institute of Science and Technology Austria (ISTA).}
\email{matthew.kwan@ist.ac.at}

\author[Pham]{Huy Tuan Pham}

\address{Department of Mathematics, University of Chicago.}
\email{htpham@uchicago.edu}

\thanks{
Matthew Kwan was supported by ERC Starting Grant ``RANDSTRUCT'' No.\ 101076777. Huy Tuan Pham was supported by a Clay Research Fellowship, a Sloan Research Fellowship and NSF Career grant DMS-2543870. %Part of this work was done when Pham was visiting the Institute for Advanced Study and supported by the Bell System Fellowship. 
}

\begin{document}

\maketitle
\begin{abstract}
In the paper ``nonlinear lower-tail large deviations at criticality'', we bound the number of order-$n$ Steiner triple systems with no Pasch configuration. In doing so, we show that a certain variational problem is minimised by a constant kernel. Using ChatGPT 6 Pro, we also discovered that the analogous variational problems for Steiner triple systems of girth at least $g$, for large $g$, are \emph{not} minimised by the constant kernel, and we included a brief remark to this effect. In this note (not intended for publication), we present the details of this proof.
\end{abstract}
\maketitle
\noindent\textbf{Note: }This proof was discovered with ChatGPT 6 Pro, and we are not attempting to claim any kind of credit for it; this note only exists to share information that may be of interest to the community. Much of the text in this note was produced by ChatGPT 6 Pro and Claude Opus 5.5 (at maximum effort).
\section{Introduction}
A \emph{Steiner triple system} (STS) of order $n$ is a collection of triples from $[n]$ such that every pair of points lies in exactly one triple; it has ${\binom n2}/3$ triples. For $k\ge 4$, an \emph{Erdős $k$-configuration} is a set of $k$ triples spanning only $k+2$ points, such that every subset of $s$ of its triples with $2\le s<k$ spans at least $s+3$ points. (For $s=2$ this says that two triples share at most one point, as they must in an STS.) The smallest one is the Pasch configuration, four triples on six points. Erdős configurations play a role for triple systems similar to that of cycles for graphs, and an STS has \emph{girth at least $g$} if it contains no Erdős $k$-configuration with $4\le k<g$. We write $\mc E_k$ for the set of isomorphism classes of Erdős $k$-configurations.

Glock, Kühn, Lo and Osthus~\cite{GKLO20} conjectured an asymptotic formula for the number of STS of order $n$ with girth at least $g$, and Kwan, Sah, Sawhney and Simkin~\cite{KSSS24} proved the corresponding lower bound. In~\cite[Theorem~1.17]{KP}, we proved the matching upper bound for $g=5$. Our proof reduces the count to a variational problem over ``profiles'' of triples, and then shows~\cite[Lemma~8.10]{KP} that the uniform profile is optimal. In~\cite[Remark~1.19]{KP} we report that for large $g$ the uniform profile is not optimal for the corresponding variational problems, so that our method, in this form, gives upper bounds weaker than conjectured. This note proves a precise version of that statement. As remarked in \cite{KP}, we suspect that this provides evidence that the conjecture is false. 

\subsection{Theorem statement}
% An STS on $[n]$ can be encoded by a function on triples of points: with the uniform probability measure $\mu$ on $[n]$, let $W(x,y,z)=n$ if $\{x,y,z\}$ is a triple of the system, and $W(x,y,z)=0$ otherwise. The factor $n$ is chosen so that
% \[
% \int W(x,y,z)\dd\mu(z)=1\qquad\text{for distinct }x,y,
% \]
% because $\{x,y\}$ lies in exactly one triple. Abstracting this,
A \emph{Steiner kernel} on a probability space $(\Omega,\mu)$ is a symmetric measurable function $W\colon\Omega^3\to[0,\infty)$ such that, for almost every $(x,y)\in\Omega^2$, we have $\int W(x,y,z)\dd\mu(z)=1$; we call this the \emph{pair constraint}. %The constant kernel $W\equiv1$ describes triples spread as evenly as possible.

For a Steiner kernel $W$, we define the entropy cost
\[
D(W)=\int_{\Omega^3}W\log W\dd\mu^3.
\]
This quantity is nonnegative because $\int W=1$, and it vanishes only for the constant kernel $W\equiv1$. 
%and %Two quantities are attached to a kernel. F
Also, for a $3$-graph $F$, define the \emph{homomorphism density}
\[
t_F(W)=\int_{\Omega^{V(F)}}\prod_{e\in E(F)}W(x_e)\dd\mu^{V(F)}(x).
\]
and let $\Aut(F)$ be the automorphism group of $F$.
%(where $x_e=(x_u,x_v,x_w)$ for $e=\{u,v,w\}$) measures how often $W$ contains $F$.
For $F\in\cE_k$, let
\[
a_F=\frac{6}{|\Aut(F)|}.
\]
%chosen so that $a_F\,t_F(W)$ is the number of copies of $F$ per triple that the profile $W$ predicts. %To see this for the constant kernel, pretend that the $n^2/6$ triples of an STS form a random set in which each of the $\binom n3$ possible triples is present with probability about $1/n$. A placement of $F$ on $k+2$ given points is then present with probability about $n^{-k}$, and there are about $n^{k+2}/|\Aut(F)|$ placements, so we expect about $n^2/|\Aut(F)|=a_F\cdot n^2/6$ copies of $F$, i.e.\ $a_F$ per triple. (For the Pasch configuration $|\Aut(F)|=24$, giving the heuristic count $n^2/24$ of~\cite[Remark~1.18]{KP}.)
and define the girth-$g$ functional
\begin{equation}\label{eq:Ig}
I_g(W)=D(W)+\sum_{4\le k<g}\ \sum_{F\in\cE_k}a_F\,t_F(W).
\end{equation}
%It is the entropy cost of moving to the profile $W$, plus the predicted number of forbidden configurations per triple at that profile.
At the constant kernel, this functional equals
\[
C_g:=I_g(1)=\sum_{4\le k<g}\ \sum_{F\in\cE_k}a_F,
\]
the predicted number of forbidden configurations per triple in a uniformly random STS.

For $g=5$ the only forbidden configuration is the Pasch configuration, so $C_5=1/4$. In \cite[Lemma~8.10]{KP} we prove the inequality $I_5(W)\ge1/4$ for kernels on finite uniform spaces, even without the pair constraint (only $\int W=1$ is needed). %This is what makes their bound sharp: a random STS is anti-Pasch with probability $\exp(-n^2/24+o(n^2))=\exp(-C_5\cdot n^2/6+o(n^2))$.
For general $g$ the analogous statement would be
\begin{equation}\label{eq:conj}
I_g(W)\ge C_g\qquad\text{for every Steiner kernel }W,
\end{equation}
that is, the constant kernel would minimise $I_g$. It does not.

\begin{theorem}\label{thm:main}
There is a symmetric measurable function $U$ with $|U|\le1$ on a probability space, with zero pair marginals, $\int U(x,y,z)\dd\mu(z)=0$ for all $x,y$, such that for all sufficiently large $g$ the Steiner kernel
\[
W_g=1+g^{-g/5}\,U
\]
satisfies $I_g(W_g)<C_g$.
\end{theorem}

To comment on the connection to the Glock--K\"uhn--Lo--Osthus conjecture: we would conjecture that for a random order-$n$ Steiner triple system $S$,
\[\log \Pr[S\text{ has girth at least }g]=-\frac{\binom n2}3\cdot \min_W I_g(W)+o(n^2).\]
If this conjecture were true, then \cref{thm:main} would contradict the conjectured formula in \cite{GKLO20} for the number of STS with girth at least $g$. It would be a very significant undertaking to actually prove this conjecture (in addition to the ideas in \cite{KP}, presumably one would need some version of the techniques in \cite{KSSS24} or \cite{DP24}), but we nonetheless view \cref{thm:main} as  strong evidence that the Glock--K\"uhn--Lo--Osthus conjecture is false.

%The kernels $W_g$ are strictly positive and converge uniformly to $1$; nothing about them is singular. They satisfy the pair constraint exactly, so \eqref{eq:conj} also fails over any larger class of kernels, for instance if the pair constraint is relaxed to $\int W=1$. The proof is asymptotic and does not identify the smallest girth for which \eqref{eq:conj} fails. %\Cref{sec:scope} discusses what \cref{thm:main} does and does not say about counting Steiner triple systems.

To prove \cref{thm:main}, the approach is to consider a slight perturbation  $1+\eps U$. This perturbation costs about $\eps^2$ in entropy, whereas the configuration terms only respond at order $\eps^4$. What changes with $g$ is the number of configuration terms, which grows like $g^g$. We look for a sub-configuration that has negative density in some admissible direction $U$, and that is contained in so many Erdős configurations that the resulting negative terms add up to more than the entropy cost, even though $\eps$ is tiny.
% \subsection*{Where the counterexample comes from}
% Why should anything beat the constant kernel, which is optimal for $g=5$? For each fixed $g$ it is in fact a strict local minimiser: perturbing it to $1+\eps U$ costs about $\eps^2$ in entropy, whereas the configuration terms only respond at order $\eps^4$. What changes with $g$ is the number of configuration terms, which grows like $g^g$. We look for a sub-configuration that has negative density in some admissible direction $U$, and that is contained in so many Erdős configurations that the resulting negative terms add up to more than the entropy cost, even though $\eps$ is tiny.

\Cref{sec:expansion} shows that the pair constraint severely limits which sub-configurations can play this role: the first ones whose contributions get multiplied by the number of configurations have six edges, and there are only two of them, the $3\times3$ grid and one other. \Cref{sec:lift} builds $U$ from a theorem of Sidorenko, which provides a signed kernel with negative grid density, together with a three-colour lift that enforces the pair constraint and switches the other six-edge configuration off. \Cref{sec:proof} proves \cref{thm:main} assuming that grids are abundant inside Erdős configurations, and \cref{sec:counting} proves this by completing a grid at random.

\section{What a perturbation of the constant kernel sees}\label{sec:expansion}

Let $U\colon\Omega^3\to[-1,1]$ be symmetric with zero pair marginals. Then $W=1+\eps U$ is a Steiner kernel for $0\le\eps\le1$. To compare $I_g(1+\eps U)$ with $C_g$, expand each density by multiplying out $\prod_e(1+\eps U(x_e))$:
\begin{equation}\label{eq:expand}
t_F(1+\eps U)=\sum_{A\subseteq E(F)}\eps^{|A|}\,t_A(U),
\end{equation}
where $t_A(U)$ is the density of the $3$-graph formed by the edges in $A$ (vertices of $F$ covered by no edge of $A$ simply integrate to $1$).

The pair constraint now does most of the work. If some vertex $v$ lies in exactly one edge $e\in A$, then integrating over $x_v$ first replaces $U(x_e)$ by its pair marginal, which is zero, so $t_A(U)=0$. Call $A$ \emph{leafless} if every vertex covered by $A$ lies in at least two edges of $A$. Only leafless sets contribute to \eqref{eq:expand}: the empty set contributes $1$, and single edges contribute nothing.

Which leafless edge sets does an Erdős configuration contain? The whole configuration is one. Indeed, if a vertex of $F\in\cE_k$ lay in only one edge $e$, then the other $k-1$ edges would span at most $k+1$ vertices, contrary to the definition. So $A=E(F)$ contributes $\eps^k\,t_F(U)$. Proper subsets are far more restricted, because the definition of $\cE_k$ forces them to be sparse while leaflessness forces them to be dense.

\begin{lemma}\label{lem:six}
Let $F\in\cE_k$, and let $A\subsetneq E(F)$ be nonempty and leafless. Then $|A|\ge6$. If $|A|=6$, then $A$ covers exactly nine vertices, each lying in exactly two edges of $A$, and $A$ is isomorphic either to the $3\times3$ grid $G$ or to the configuration $P$ dual to the triangular prism.
\end{lemma}

Here the \emph{grid} $G$ has the nine cells of a $3\times3$ array as its vertices, and its three rows and three columns as its edges. The configuration $P$ is described in the proof.

\begin{proof}
Let $j=|A|$, and let $v$ be the number of vertices covered by $A$. A single edge has leaves, so $j\ge2$, and then the definition of $\cE_k$ gives $v\ge j+3$. Since each covered vertex lies in at least two of the $j$ edges, $3j\ge2v$. Together these give $3j\ge2j+6$, so $j\ge6$; and if $j=6$ both inequalities are equalities, so $v=9$ and every vertex lies in exactly two edges of $A$.

Such an $A$ is determined by a graph. Let $A^*$ be the graph whose vertices are the six edges of $A$, with one edge for each vertex of $A$, joining the two edges of $A$ that contain it. Each edge of $A$ has three vertices, so $A^*$ is $3$-regular; it has no loops, and no parallel edges because two edges of $F$ share at most one vertex. Conversely, $A$ is recovered from $A^*$: its vertices are the edges of $A^*$, and its edges are the stars of the vertices of $A^*$. There are exactly two simple $3$-regular graphs on six vertices, $K_{3,3}$ and the triangular prism. If $A^*=K_{3,3}$ with parts $\{r_1,r_2,r_3\}$ and $\{c_1,c_2,c_3\}$, then the vertices of $A$ are the nine edges $r_ic_j$, and its edges are the stars of the $r_i$ and of the $c_j$. These are the rows and columns of a $3\times3$ array, so $A\cong G$. The prism gives the other configuration, which we call $P$.
\end{proof}

Summing \eqref{eq:expand} over configurations, $I_g(1+\eps U)-C_g$ consists of the entropy term $D(1+\eps U)$ together with one term $a_F\,\eps^{|A|}\,t_A(U)$ for each $F\in\cE_k$ ($4\le k<g$) and each nonempty leafless $A\subseteq E(F)$. By \cref{lem:six} these terms come in three kinds:
\begin{itemize}
\item whole configurations with at most six edges, a fixed finite family contributing $O(\eps^4)$ independently of $g$;
\item proper six-edge subsets, which are copies of $G$ or of $P$ and contribute $\eps^6\,t_G(U)$ or $\eps^6\,t_P(U)$ each;
\item sets with at least seven edges.
\end{itemize}
The entropy term is of order $\eps^2$, with a constant independent of $g$. The six-edge terms are therefore the first ones whose total coefficient grows with $g$, since the numbers of copies of $G$ and $P$ grow with the number of configurations. This %is where a counterexample has to come from, and it
tells us what to ask of $U$:
\begin{enumerate}
\item[(U1)] $U$ is symmetric, $|U|\le1$, and $U$ has zero pair marginals;
\item[(U2)] $t_G(U)<0$;
\item[(U3)] $t_P(U)=0$.
\end{enumerate}
Condition (U3) spares us from comparing the number of copies of $P$ with the number of copies of $G$. Under (U1)--(U3), the six-edge terms add up to $-|t_G(U)|\,b_g\,\eps^6$, where
\[
b_g=\sum_{4\le k<g}\ \sum_{F\in\cE_k}a_F\,N_G(F),
\]
and $N_G(F)$ denotes the number of copies of $G$ in $F$. We will see that $b_g$, like $C_g$, is $g^{(1+o(1))g}$. The grid terms then beat the entropy cost as soon as $b_g\eps^4\to\infty$, i.e.\ for $\eps$ somewhat larger than $g^{-g/4}$. They also beat the terms with at least seven edges, whose total weight is at most $2^gC_g$ and which are each $O(\eps^7)$, provided $\eps\le e^{-Cg}$ for a suitable constant $C$. The choice $\eps=g^{-g/5}$ lies comfortably inside this window.

\section{An admissible direction with negative grid density}\label{sec:lift}

Condition (U2) asks for a direction in which the grid has negative density, and this is provided by a theorem of Sidorenko. In his terminology it says that the grid is not \emph{positive}; this is the failure of positivity mentioned in~\cite[Remark~1.19]{KP}.

\begin{theorem}[Sidorenko]\label{thm:sid}
There are a probability space $(\Omega_0,\mu_0)$ and a bounded symmetric measurable function $V\colon\Omega_0^3\to\mathbb{R}$ with $t_G(V)<0$.
\end{theorem}

For a proof, see~\cite[Proposition~1.5]{Sid22}. Dividing $V$ by $\|V\|_\infty$, we may assume $|V|\le1$. Nothing else about $V$ will matter: it may be nonzero when two of its arguments coincide, and its pair marginals may be arbitrary.

Such a $V$ is not yet an admissible direction. Nothing forces its pair marginals to vanish, and without that $1+\eps V$ is not a Steiner kernel, and the expansion of \cref{sec:expansion} would no longer discard edge sets with leaves. We repair this by tensoring with a kernel whose pair marginals do vanish. Given a symmetric function $K$ on $\Lambda^3$ for a probability space $(\Lambda,\nu)$, set
\[
U\big((x,\alpha),(y,\beta),(z,\gamma)\big)=V(x,y,z)\,K(\alpha,\beta,\gamma)\qquad\text{on }(\Omega_0\times\Lambda)^3.
\]
Integrating over the third argument factorises, so $U$ has zero pair marginals as soon as $K$ does, whatever $V$ is; and $t_A(U)=t_A(V)\,t_A(K)$ for every $3$-graph $A$. Thus (U2) and (U3) become conditions on $K$: we need $t_G(K)>0$, to keep the sign of $t_G(V)$, and $t_P(K)=0$.

Both $G$ and $P$ are $2$-regular: each vertex lies in exactly two edges. This makes the most obvious choice useless. On $\Lambda=\Z/2\Z$, the kernel $K(\alpha,\beta,\gamma)=(-1)^{\alpha+\beta+\gamma}$ has zero pair marginals, but in $\prod_{e\in A}K(x_e)$ each colour of a $2$-regular $A$ appears twice, so $t_A(K)=1$: this $K$ cannot tell $G$ from $P$. And $P$ does have to be switched off: we know nothing about $t_P(V)$, and if it were positive, copies of $P$ would contribute with the wrong sign.

It turns out that three colours suffice. On $\Lambda=\Z/3\Z$ with the uniform measure, let $\omega=e^{2\pi i/3}$ and
\[
K(\alpha,\beta,\gamma)=\operatorname{Re}\omega^{\alpha+\beta+\gamma}=
\begin{cases}1&\text{if }\alpha+\beta+\gamma\equiv0\pmod3,\\[2pt] -\frac12&\text{otherwise}.\end{cases}
\]
Its pair marginals vanish because $\sum_{\gamma}\omega^{\alpha+\beta+\gamma}=0$. The point of a cube root of unity is that the two edges at a vertex can only cancel each other's characters if they carry conjugate ones, and this turns $t_A(K)$ into a count of $2$-colourings.

\begin{lemma}\label{lem:colour}
Let $A$ be a connected linear $3$-graph in which every vertex lies in exactly two edges, and let $A^*$ be the graph defined in the proof of \cref{lem:six}. Then $t_A(K)=2^{1-|A|}$ if $A^*$ is bipartite, and $t_A(K)=0$ otherwise.
\end{lemma}

\begin{proof}
Write $K=\frac12(\chi+\bar\chi)$ with $\chi(\alpha,\beta,\gamma)=\omega^{\alpha+\beta+\gamma}$, and expand the product over the edges of $A$ as a sum over choices $\sigma\in\{\pm1\}^A$ of $\chi$ or $\bar\chi$ for each edge:
\[
\prod_{e\in A}K(x_e)=2^{-|A|}\sum_{\sigma}\ \prod_{e\in A}\omega^{\sigma_e\sum_{v\in e}x_v}=2^{-|A|}\sum_{\sigma}\ \prod_{v}\omega^{(\sigma_e+\sigma_{e'})x_v},
\]
where $e$ and $e'$ denote the two edges containing $v$. Averaging over $x_v\in\Z/3\Z$ gives $1$ if $\sigma_e+\sigma_{e'}\equiv0\pmod3$ and $0$ otherwise; as $\sigma_e+\sigma_{e'}\in\{-2,0,2\}$, the condition is $\sigma_e=-\sigma_{e'}$. So $t_A(K)$ is $2^{-|A|}$ times the number of $\sigma$ taking opposite values on any two edges that share a vertex, which is the number of proper $2$-colourings of $A^*$. A connected graph has two of them if it is bipartite, and none otherwise.
\end{proof}

The grid's graph $G^*$ is $K_{3,3}$, which is bipartite, so $t_G(K)=2^{-5}$; the prism contains triangles, so $t_P(K)=0$. Collecting what we have, $U$ satisfies (U1)--(U3):

\begin{proposition}\label{prop:U}
Let $V$ be as in \cref{thm:sid} with $|V|\le1$, let $\Omega=\Omega_0\times\Z/3\Z$ with the product of $\mu_0$ and the uniform measure, and let $U=V\otimes K$ be as above. Then $U$ is symmetric, $|U|\le1$, $U$ has zero pair marginals, and
\[
t_G(U)=\frac{t_G(V)}{32}<0,\qquad t_P(U)=0.
\]
\end{proposition}

\begin{proof}
$U$ is symmetric because $V$ and $K$ are, and $|U|\le1$ because $|V|\le1$ and $|K|\le1$. The rest follows from $t_A(U)=t_A(V)\,t_A(K)$ and \cref{lem:colour}.
\end{proof}

\section{Proof of \texorpdfstring{\cref{thm:main}}{Theorem 1.1}, given that grids are abundant}\label{sec:proof}

Let $U$ be as in \cref{prop:U}, and write $a=-t_G(U)>0$. The bookkeeping of \cref{sec:expansion} gives, for $g\ge7$ and $0\le\eps\le1$, the exact identity
\begin{equation}\label{eq:identity}
I_g(1+\eps U)-C_g=D(1+\eps U)+\sum_{k=4}^{6}\ \sum_{F\in\cE_k}a_F\,\eps^k\,t_F(U)-a\,b_g\,\eps^6+R_g(\eps),
\end{equation}
where $R_g(\eps)$ is the sum of $a_F\,\eps^{|A|}\,t_A(U)$ over all $F\in\cE_k$ with $4\le k<g$ and all leafless $A\subseteq E(F)$ with $|A|\ge7$. Indeed, $t_F(1+\eps U)-1$ is the sum of $\eps^{|A|}\,t_A(U)$ over nonempty leafless $A\subseteq E(F)$. The sets $A=E(F)$ with $k\le6$ give the second term. By \cref{lem:six}, proper leafless sets have at least six edges, and those with exactly six are copies of $G$, each contributing $\eps^6\,t_G(U)$, or of $P$, contributing nothing. Everything else has at least seven edges.

Every term except the grid term is small:
\begin{itemize}
\item Since $\log(1+u)\le u$, we have $(1+u)\log(1+u)-u\le u^2$ for $u\ge-1$. As $\int\eps U=0$, this gives
\[
D(1+\eps U)=\int\big[(1+\eps U)\log(1+\eps U)-\eps U\big]\le\eps^2\int U^2\le\eps^2.
\]
\item As $|U|\le1$, every $|t_A(U)|$ is at most $1$. The second term in \eqref{eq:identity} is therefore at most $C_7\,\eps^4$ in absolute value, where $C_7=\sum_{k=4}^{6}\sum_{F\in\cE_k}a_F$ is an absolute constant. We never need to know its sign.
\item A configuration with $k<g$ edges has fewer than $2^g$ edge subsets, so $|R_g(\eps)|\le2^gC_g\,\eps^7$.
\end{itemize}
Hence
\begin{equation}\label{eq:threeterms}
I_g(1+\eps U)-C_g\le(1+C_7)\,\eps^2-a\,b_g\,\eps^6+2^gC_g\,\eps^7.
\end{equation}
Everything now depends on how large $b_g$ is compared with $C_g$.

\begin{lemma}\label{lem:counting}
As $g\to\infty$,
\[
C_g\le\exp\big(g\log g+O(g)\big)\qquad\text{and}\qquad b_g\ge\exp\big(g\log g-O(g)\big).
\]
\end{lemma}

The upper bound is a crude count of all possible configurations. The lower bound says that the weighted number of pairs (Erdős configuration, grid inside it) is as large as the weighted number of configurations, up to a factor $e^{O(g)}$. This does not require grids to be typical: heuristically, only a polynomially small proportion of Erdős configurations contain a grid. But polynomial, and even exponential, losses are invisible on the scale $g\log g$.

\begin{proof}[Proof of \cref{thm:main}, assuming \cref{lem:counting}]
Take $\eps=g^{-g/5}=\exp(-\frac15g\log g)$ in \eqref{eq:threeterms}. Then
\begin{align*}
(1+C_7)\,\eps^2&=\exp\big(-\tfrac25g\log g+O(1)\big),\\
a\,b_g\,\eps^6&\ge\exp\big(-\tfrac15g\log g-O(g)\big),\\
2^gC_g\,\eps^7&\le\exp\big(-\tfrac25g\log g+O(g)\big).
\end{align*}
The middle term exceeds the other two by a factor $\exp(\frac15g\log g-O(g))\to\infty$, so $I_g(1+\eps U)<C_g$ for all sufficiently large $g$.
\end{proof}

As anticipated in \cref{sec:expansion}, the exponent $\frac15$ has no special role: the same computation works for $\eps=g^{-\theta g}$ with any $\theta\in(0,\frac14)$.

\section{Grids are abundant: proof of \texorpdfstring{\cref{lem:counting}}{Lemma 4.1}}\label{sec:counting}

Both bounds are statements about labelled configurations. By the orbit--stabiliser theorem, an Erdős $k$-configuration $F$ has $(k+2)!/|\Aut(F)|$ labelled copies on the vertex set $[k+2]$. Hence
\begin{equation}\label{eq:labelled}
\sum_{F\in\cE_k}a_F=\frac{6\,L_k}{(k+2)!}\qquad\text{and}\qquad\sum_{F\in\cE_k}a_F\,N_G(F)=\frac{6}{(k+2)!}\sum_{F'}N_G(F'),
\end{equation}
where $L_k$ is the number of Erdős $k$-configurations on $[k+2]$, and $F'$ ranges over them.

\subsection*{Upper bound}
An Erdős $k$-configuration on $[k+2]$ is a set of $k$ triples from $[k+2]$, so
\[
L_k\le\binom{\binom{k+2}{3}}{k}\le\frac{(k+2)^{3k}}{k!}=\exp\big(2k\log k+O(k)\big).
\]
Since $(k+2)!=\exp(k\log k+O(k))$, \eqref{eq:labelled} gives $\sum_{F\in\cE_k}a_F\le\exp(k\log k+O(k))$, and summing over $k<g$ gives $C_g\le\exp(g\log g+O(g))$.

\subsection*{Lower bound: completing a grid at random}
Fix $k=g-1$, and a copy of $G$ on nine of the vertices in $[k+2]$. By \eqref{eq:labelled}, $b_g\ge6L_k^G/(k+2)!$, where $L_k^G$ is the number of Erdős $k$-configurations on $[k+2]$ that contain the fixed grid. So we need $L_k^G\ge\exp(2k\log k-O(k))$: up to a factor $e^{O(k)}$, as many configurations through a fixed grid as the upper bound allows for all configurations. We obtain them by completing the grid at random.

What should a completion look like? In an Erdős $k$-configuration every vertex lies in at least two edges (as we saw in \cref{sec:expansion}), and the degrees sum to $3k=2(k+2)+(k-4)$. So if all degrees are $2$ or $3$, exactly six vertices have degree $2$. We build configurations of this kind using the so-called \emph{configuration model} (see e.g.\ \cite{Wor99}). Besides the nine grid vertices, we let six vertices have degree $2$, and the remaining $k-13$ have degree $3$; each grid vertex also gets degree $3$, i.e.\ one incidence besides its two grid lines. Represent the missing incidences by \emph{stubs}: one at each grid vertex, two at each degree-$2$ vertex and three at each other vertex, so
\[
M=9+12+3(k-13)=3k-18
\]
in total. Add $k-6$ new edges with three stubs each, again $M$ stubs in total, and match vertex stubs to edge stubs by a uniformly random bijection. Call the resulting multi-hypergraph $F$.

Every Erdős configuration on $[k+2]$ which contains the fixed grid and has the prescribed degrees arises from exactly
\[
(k-6)!\cdot(3!)^{k-6}\cdot(2!)^6\cdot(3!)^{k-13}
\]
bijections: the new edges can be labelled in $(k-6)!$ ways, and the stubs at each new edge and at each vertex can be ordered arbitrarily. Therefore
\[
L_k^G\ge\Pr[F\in\cE_k]\cdot\frac{(3k-18)!}{(k-6)!\,2^6\,6^{2k-19}},
\]
and by Stirling's formula the fraction is $\exp(3k\log k-k\log k+O(k))=\exp(2k\log k+O(k))$. So the lower bound in \cref{lem:counting} follows from the next proposition. (Any bound of the form $\Pr[F\in\cE_k]\ge e^{-O(k)}$ would do, but the natural proof gives a constant.)

\begin{proposition}\label{prop:completion}
$\Pr[F\in\cE_k]\to e^{-6}$ as $k\to\infty$.
\end{proposition}

The multi-hypergraph $F$ is an Erdős $k$-configuration if and only if
\begin{enumerate}
\item[(i)] $F$ is linear, and
\item[(ii)] no set $S$ of edges with $3\le|S|\le k-1$ spans at most $|S|+2$ vertices.
\end{enumerate}
(Linearity rules out repeated vertices in an edge and repeated edges, and it is the case $|S|=2$ of the definition; $F$ spans all $k+2$ vertices because each has degree at least $2$.) Condition (i) is local, and it fails with probability bounded away from zero: it is the source of the constant $e^{-6}$. Condition (ii) is global, but it fails only with probability $O(1/k)$.

\subsection*{Linearity}
Think of $F$ through its incidence graph: the bipartite multigraph with the vertices of $F$ on one side, the edges of $F$ on the other, and one link for each incidence. $F$ is linear exactly when this graph has no cycle of length $2$ (a vertex matched twice to the same edge) and no cycle of length $4$ (two edges sharing two vertices).

Short cycles meeting the grid are rare. The grid itself has none. A grid vertex has a single stub, so it lies on no $2$-cycle, and a $4$-cycle through it must consist of a grid line and a new edge containing two vertices of that line. There are $18$ pairs of vertices on a common grid line, and the stubs of a given pair go to the same new edge with probability $O(1/k)$.

The remaining short cycles are formed by stubs alone, and all but fifteen vertices have three stubs. Let $X$ and $Y$ be the numbers of $2$-cycles and $4$-cycles formed by stub pairs. A $2$-cycle is specified by a vertex, a new edge, and two stub pairs between them; a $4$-cycle by two vertices, two new edges, and four stub pairs forming the cycle. A given set of $t$ stub pairs is present with probability $1/(M)_t=(1+O(1/k))(3k)^{-t}$ for bounded $t$, where $(M)_t=M(M-1)\cdots(M-t+1)$. Since almost every vertex has three stubs,
\[
\mathbb{E}X=(1+O(1/k))\,k\cdot k\cdot\frac{3\cdot3\cdot2}{(3k)^2}\to2,\qquad
\mathbb{E}Y=(1+O(1/k))\binom k2^2\frac{(3\cdot2)^4}{(3k)^4}\to4.
\]
The method of moments upgrades this to a Poisson limit. For fixed $i$ and $j$, the factorial moment $\mathbb{E}[(X)_i(Y)_j]$ counts ordered tuples of $i$ distinct $2$-cycles and $j$ distinct $4$-cycles that are all present. Tuples of pairwise disjoint cycles contribute $2^i4^j+o(1)$, by the computation above. In every other tuple, the union of the cycles has a component containing two distinct cycles, and so has more links than nodes. Since each node can be chosen in $O(k)$ ways and each link costs a factor $O(1/k)$ in probability, these tuples contribute $O(1/k)$. Hence $(X,Y)$ converges in distribution to a pair of independent Poisson random variables with means $2$ and $4$, and
\[
\Pr[F\text{ is linear}]=\Pr[X=Y=0]+O(1/k)\to e^{-2}e^{-4}=e^{-6}.
\]

\subsection*{No dense edge sets}
Call a set $S$ of edges of $F$ \emph{bad} if $3\le|S|\le k-1$ and $S$ spans at most $|S|+2$ vertices. We show that the expected number of bad sets is $O(1/k)$, handling sets with at most $k/2$ edges directly and larger ones through their complements. In both cases a bad set forces all stubs of some $r$ new edges into a prescribed set of roughly $3r$ stubs, at a cost of order $k^{-3r}$, while the sets involved can be chosen in about $k^{2r}$ ways. The remaining bounded powers of $k$ are controlled by the condition $|S|\ge3$ and by the fact that the grid is itself sparse.

\emph{Small sets.} Suppose $S$ is bad and $s=|S|\le k/2$. Let $A$ be the set of grid lines in $S$, say $p$ rows and $q$ columns, $h=p+q$ in total, and let the other $r=s-h$ edges of $S$ be new. Choose a set $Y$ of exactly $s+2$ vertices containing every vertex of $S$. Then $Y$ contains the $3h-pq$ vertices covered by $A$, and all $3r$ stubs of the new edges in $S$ are matched to stubs at vertices of $Y$.

The grid is sparse in the same sense as an Erdős configuration: one grid line covers $3$ vertices, and $h\ge2$ grid lines cover $3h-pq\ge h+3$ (one checks the few cases). Consequently $r\ge1$; more precisely $r\ge3$ if $h=0$ (as $s\ge3$), $r\ge2$ if $h=1$, and $r\ge1$ if $h\ge2$. Moreover, the number of vertices of $Y$ not forced by $A$ is $s+2-(3h-pq)=r+c$, where $c=2$ if $h=0$, $c=0$ if $h=1$, and $c\le-1$ if $h\ge2$.

Now fix $A$ and $r$. The new edges of $S$ can be chosen in at most $\binom kr$ ways and the rest of $Y$ in at most $\binom{k+2}{r+c}$ ways, and the $3r$ stubs land among the at most $3(s+2)$ stubs at $Y$ with probability at most $(3s+6)_{3r}/(M)_{3r}$. For bounded $r$ this gives $O(k^r\cdot k^{r+c}\cdot k^{-3r})=O(k^{c-r})$, and $c-r\le-1$ in all three cases.

\emph{Large sets.} Suppose $S$ is bad and $|S|>k/2$, and let $T$ be its complement, with $m=|T|<k/2$. Since $S$ spans at most $|S|+2=k+2-m$ vertices, at least $m$ vertices lie in no edge of $S$, so all their edges are in $T$. Choose a set $Z$ of exactly $m$ such vertices. Let $T$ contain $h=p+q$ grid lines ($p$ rows and $q$ columns) and $r=m-h$ new edges. A grid vertex can belong to $Z$ only if both grid lines through it are in $T$, so $Z$ contains at most $pq\le2h$ grid vertices. If $Z$ contains $j$ grid vertices and $d$ vertices of degree $2$, then the vertices of $Z$ carry $3m-2j-d$ stubs, all of which must be matched to the $3r$ stubs of the new edges in $T$. In particular $r\ge1$.

Fix the grid lines in $T$, and $j$, $d$ and $r$. The new edges of $T$ can be chosen in at most $\binom kr$ ways and $Z$ in $O(\binom k{m-j-d})$ ways, and the stub condition has probability $(3r)_{3m-2j-d}/(M)_{3m-2j-d}$. For bounded $r$ this gives $O(k^{r+(m-j-d)-(3m-2j-d)})=O(k^{j-2h-r})$, which is $O(k^{-r})=O(k^{-1})$ because $j\le2h$.

\emph{Summing over $r$.} The estimates above are for fixed $r$; it remains to show that large $r$ contribute little. In both cases the bound for a given $r\le k/2$ is at most $k^{O(1)}\binom kr^2\big/\binom{3k}{3r}$, with an absolute implied constant. To see this, write $(y)_x/(M)_x=\binom yx\big/\binom Mx$. In both cases $x\le y$ (otherwise the probability is zero) and $x,y$ differ from $3r$ by at most $24$, so $\binom yx\le(3k)^{24}$ and $\binom Mx\ge M^{-24}\binom M{3r}$; moreover $\binom M{3r}\ge3^{-18}\binom{3k}{3r}$ for $r\le k/2$ and $k$ large, and the second binomial coefficient in each count is at most $k^{O(1)}\binom kr$, because its lower index differs from $r$ by a bounded amount and $r\le k/2$.

Heuristically, choosing $r$ edges and about $r$ vertices is worth $\binom kr^2$, while forcing $3r$ stubs into a set of about $3r$ stubs costs $1/\binom{3k}{3r}$. With $\eta(x)=-x\log x-(1-x)\log(1-x)$, the standard estimates $\binom kr\le e^{k\eta(r/k)}$ and $\binom{3k}{3r}\ge e^{3k\eta(r/k)}/(3k+1)$ make this precise:
\[
\binom kr^2\Big/\binom{3k}{3r}\le(3k+1)\,e^{-k\eta(r/k)}\le(3k+1)\Big(\frac rk\Big)^r,
\]
using $\eta(x)\ge x\log(1/x)$. So the bound for each $r\le k/2$ is at most $k^{c_0}(r/k)^r$ for an absolute constant $c_0$. For $r_0\le r\le\sqrt k$ this is at most $k^{c_0-r/2}$, and for $\sqrt k\le r\le k/2$ it is at most $k^{c_0}2^{-\sqrt k}$. Choosing $r_0\ge2c_0+4$, the terms with $r\ge r_0$ add up to $O(k^{-2})$, while the finitely many $r<r_0$ contribute $O(1/k)$ by the fixed-$r$ estimates. Since there are boundedly many choices of the grid lines involved and of $j$ and $d$, the expected number of bad sets is $O(1/k)$.

\begin{proof}[Proof of \cref{prop:completion}]
By the two estimates, $\Pr[F\in\cE_k]=\Pr[F\text{ is linear}]-O(1/k)\to e^{-6}$.
\end{proof}

This completes the proof of \cref{lem:counting}, and with it the proof of \cref{thm:main}.

% \section{What \texorpdfstring{\cref{thm:main}}{Theorem 1.1} does and does not show}\label{sec:scope}

% \subsection*{The size of the effect}
% The kernel $W_g$ is at distance $g^{-g/5}$ from the constant kernel, and by \eqref{eq:identity} it lowers $I_g$ by $\exp(-\frac15g\log g\pm O(g))$. An effect of this size is invisible to numerical exploration at moderate $g$, and the argument gives no explicit girth at which \eqref{eq:conj} first fails.

% For each fixed $g$, on the other hand, the constant kernel is a strict local minimiser, as the following remark shows. There is no contradiction: the neighbourhood in which it is minimal shrinks superexponentially in $g$, and $W_g$ lies outside it.

% \begin{remark}\label{rem:local}
% Fix $g\ge5$, and let $W=1+\Phi$ be a Steiner kernel with $0<\|\Phi\|_\infty\le\delta$, where $\delta^2<(2^{g+2}C_g)^{-1}$. Then $I_g(W)>C_g$.

% Indeed, $\delta<1$ because $C_g\ge C_5=\frac14$, and $(1+u)\log(1+u)-u\ge u^2/(2(1+\delta))\ge u^2/4$ for $|u|\le\delta$, since the second derivative of the left side is $1/(1+u)$; as $\int\Phi=0$, this gives $D(W)\ge\|\Phi\|_2^2/4$. The configuration terms are $a_F\,t_A(\Phi)$ for leafless $A\subseteq E(F)$, and in a linear $3$-graph a leafless set has at least four edges (two edges span five vertices, three span at least six). Pick two edges $e,f\in A$. They share at most one vertex, so the Cauchy--Schwarz inequality gives $\int|\Phi(x_e)\Phi(x_f)|\le\|\Phi\|_2^2$, and bounding the other factors by $\delta$ gives $|t_A(\Phi)|\le\delta^{|A|-2}\|\Phi\|_2^2\le\delta^2\|\Phi\|_2^2$. Summing, $|I_g(W)-C_g-D(W)|\le2^gC_g\,\delta^2\|\Phi\|_2^2<\|\Phi\|_2^2/4$.
% \end{remark}

% Combined with \cref{lem:counting}, the remark shows that the constant kernel is minimal among Steiner kernels within $L^\infty$-distance $\exp(-\frac12g\log g-O(g))$ of it, while \cref{thm:main} shows that it is not minimal within distance $g^{-g/5}$.

% \subsection*{Counting Steiner triple systems}
% \Cref{thm:main} is a statement about the functional $I_g$. It shows that the infimum of $I_g$ is strictly below $C_g$, the value at the constant kernel, which is the value corresponding to the conjecture of Glock, Kühn, Lo and Osthus. So an upper bound on the number of STS of girth at least $g$ obtained by minimising $I_g$ is strictly weaker than conjectured. It does not disprove the conjecture, since a weak upper bound says nothing about the true count. To disprove it, one would have to show that Steiner triple systems of girth at least $g$ can actually follow a non-uniform profile such as $W_g$, at the rate that $I_g(W_g)$ suggests. That is a lower bound, which the variational method does not provide. Kwan and Pham regard the observation as strong evidence that the conjecture is false~\cite[Remark~1.19]{KP}, and suggest~\cite[Section~1.5]{KP} that a non-regular generalisation of conflict-free hypergraph matchings, together with absorption, might lead to a disproof.


\begin{thebibliography}{1}

\bibitem{DP24}
M.~Delcourt and L.~Postle, \emph{Proof of the high girth existence conjecture via refined absorption}, arXiv preprint arXiv:2402.17856 (2024).

\bibitem{GKLO20}
S.~Glock, D.~K\"{u}hn, A.~Lo, and D.~Osthus, \emph{On a conjecture of {E}rd{\H{o}}s on locally sparse {S}teiner triple systems}, Combinatorica \textbf{40} (2020), no.~3, 363--403.

\bibitem{KP}
M.~Kwan and H.~T. Pham, \emph{Nonlinear lower-tail large deviations at criticality}, arXiv preprint arXiv:2610.10233 (2026).

\bibitem{KSSS24}
M.~Kwan, A.~Sah, M.~Sawhney, and M.~Simkin, \emph{High-girth {S}teiner triple systems}, Ann. of Math. (2) \textbf{200} (2024), no.~3, 1059--1156.

\bibitem{Sid22}
A.~Sidorenko, \emph{On positive hypergraphs}, European J. Combin. \textbf{106} (2022), Paper No. 103574, 5.

\bibitem{Wor99}
N.~C. Wormald, \emph{Models of random regular graphs}, Surveys in combinatorics, 1999 ({C}anterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp.~239--298.

\end{thebibliography}
\end{document}