WorksMathematics
The constant Steiner kernel is not optimal at large girth
Abstract
In the paper "nonlinear lower-tail large deviations at criticality", we bound the number of order- 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 , for large , are 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.
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).
Introduction
A Steiner triple system (STS) of order is a collection of triples from such that every pair of points lies in exactly one triple; it has triples. For , an Erdős -configuration is a set of triples spanning only points, such that every subset of of its triples with spans at least points. (For 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 girth at least if it contains no Erdős -configuration with . We write for the set of isomorphism classes of Erdős -configurations.
Glock, Kühn, Lo and Osthus [2] conjectured an asymptotic formula for the number of STS of order with girth at least , and Kwan, Sah, Sawhney and Simkin [4] proved the corresponding lower bound. In [3 Theorem 1.17], we proved the matching upper bound for . Our proof reduces the count to a variational problem over “profiles” of triples, and then shows [3 Lemma 8.10] that the uniform profile is optimal. In [3 Remark 1.19] we report that for large 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 [3], we suspect that this provides evidence that the conjecture is false.
Theorem statement
A Steiner kernel on a probability space is a symmetric measurable function such that, for almost every , we have ; we call this the pair constraint.
For a Steiner kernel , we define the entropy cost
This quantity is nonnegative because , and it vanishes only for the constant kernel . Also, for a -graph , define the homomorphism density
and let be the automorphism group of . For , let
and define the girth- functional
At the constant kernel, this functional equals
the predicted number of forbidden configurations per triple in a uniformly random STS. For the only forbidden configuration is the Pasch configuration, so . In [3 Lemma 8.10] we prove the inequality for kernels on finite uniform spaces, even without the pair constraint (only is needed). For general the analogous statement would be
that is, the constant kernel would minimise . It does not.
Theorem 1.1. There is a symmetric measurable function with on a probability space, with zero pair marginals, for all , such that for all sufficiently large the Steiner kernel
satisfies .
To comment on the connection to the Glock–Kühn–Lo–Osthus conjecture: we would conjecture that for a random order- Steiner triple system ,
If this conjecture were true, then Theorem 1.1 would contradict the conjectured formula in [2] for the number of STS with girth at least . It would be a very significant undertaking to actually prove this conjecture (in addition to the ideas in [3], presumably one would need some version of the techniques in [4] or [1]), but we nonetheless view Theorem 1.1 as strong evidence that the Glock–Kühn–Lo–Osthus conjecture is false.
To prove Theorem 1.1, the approach is to consider a slight perturbation . This perturbation costs about in entropy, whereas the configuration terms only respond at order . What changes with is the number of configuration terms, which grows like . We look for a sub-configuration that has negative density in some admissible direction , 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 is tiny.
§ 2 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 grid and one other. § 3 builds 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. § 4 proves Theorem 1.1 assuming that grids are abundant inside Erdős configurations, and § 5 proves this by completing a grid at random.
What a perturbation of the constant kernel sees
Let be symmetric with zero pair marginals. Then is a Steiner kernel for . To compare with , expand each density by multiplying out :
where is the density of the 3-graph formed by the edges in (vertices of covered by no edge of simply integrate to 1).
The pair constraint now does most of the work. If some vertex lies in exactly one edge , then integrating over first replaces by its pair marginal, which is zero, so . Call leafless if every vertex covered by lies in at least two edges of . Only leafless sets contribute to (3): 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 lay in only one edge , then the other edges would span at most vertices, contrary to the definition. So contributes . Proper subsets are far more restricted, because the definition of forces them to be sparse while leaflessness forces them to be dense.
Lemma 2.1. Let , and let be nonempty and leafless. Then . If , then covers exactly nine vertices, each lying in exactly two edges of , and is isomorphic either to the grid or to the configuration dual to the triangular prism.
Here the grid has the nine cells of a array as its vertices, and its three rows and three columns as its edges. The configuration is described in the proof.
Proof. Let , and let be the number of vertices covered by . A single edge has leaves, so , and then the definition of gives . Since each covered vertex lies in at least two of the edges, . Together these give , so ; and if both inequalities are equalities, so and every vertex lies in exactly two edges of .
Such an is determined by a graph. Let be the graph whose vertices are the six edges of , with one edge for each vertex of , joining the two edges of that contain it. Each edge of has three vertices, so is 3-regular; it has no loops, and no parallel edges because two edges of share at most one vertex. Conversely, is recovered from : its vertices are the edges of , and its edges are the stars of the vertices of . There are exactly two simple 3-regular graphs on six vertices, and the triangular prism. If with parts and , then the vertices of are the nine edges , and its edges are the stars of the and of the . These are the rows and columns of a array, so . The prism gives the other configuration, which we call . □
Summing (3) over configurations, consists of the entropy term together with one term for each () and each nonempty leafless . By Theorem 2.1 these terms come in three kinds:
whole configurations with at most six edges, a fixed finite family contributing independently of ;
proper six-edge subsets, which are copies of or of and contribute or each;
sets with at least seven edges.
The entropy term is of order , with a constant independent of . The six-edge terms are therefore the first ones whose total coefficient grows with , since the numbers of copies of and grow with the number of configurations. This tells us what to ask of :
(U1) is symmetric, , and has zero pair marginals;
(U2) ;
(U3) .
Condition (U3) spares us from comparing the number of copies of with the number of copies of . Under (U1)–(U3), the six-edge terms add up to , where
and denotes the number of copies of in . We will see that , like , is . The grid terms then beat the entropy cost as soon as , i.e. for somewhat larger than . They also beat the terms with at least seven edges, whose total weight is at most and which are each , provided for a suitable constant . The choice lies comfortably inside this window.
An admissible direction with negative grid density
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 positive; this is the failure of positivity mentioned in [3 Remark 1.19].
Theorem 3.1 (Sidorenko). There are a probability space and a bounded symmetric measurable function with .
For a proof, see [5 Proposition 1.5]. Dividing by , we may assume . Nothing else about will matter: it may be nonzero when two of its arguments coincide, and its pair marginals may be arbitrary.
Such a is not yet an admissible direction. Nothing forces its pair marginals to vanish, and without that is not a Steiner kernel, and the expansion of § 2 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 on for a probability space , set
Integrating over the third argument factorises, so has zero pair marginals as soon as does, whatever is; and for every 3-graph . Thus (U2) and (U3) become conditions on : we need , to keep the sign of , and .
Both and are 2-regular: each vertex lies in exactly two edges. This makes the most obvious choice useless. On , the kernel has zero pair marginals, but in each colour of a 2-regular appears twice, so : this cannot tell from . And does have to be switched off: we know nothing about , and if it were positive, copies of would contribute with the wrong sign.
It turns out that three colours suffice. On with the uniform measure, let and
Its pair marginals vanish because . 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 into a count of 2-colourings.
Lemma 3.2. Let be a connected linear 3-graph in which every vertex lies in exactly two edges, and let be the graph defined in the proof of Theorem 2.1. Then if is bipartite, and otherwise.
Proof. Write with , and expand the product over the edges of as a sum over choices of or for each edge:
where and denote the two edges containing . Averaging over gives 1 if and 0 otherwise; as , the condition is . So is times the number of taking opposite values on any two edges that share a vertex, which is the number of proper 2-colourings of . A connected graph has two of them if it is bipartite, and none otherwise. □
The grid’s graph is , which is bipartite, so ; the prism contains triangles, so . Collecting what we have, satisfies (U1)–(U3):
Proposition 3.3. Let be as in Theorem 3.1 with , let with the product of and the uniform measure, and let be as above. Then is symmetric, , has zero pair marginals, and
Proof. is symmetric because and are, and because and . The rest follows from and Theorem 3.2. □
Proof of Theorem 1.1, given that grids are abundant
Let be as in Theorem 3.3, and write . The bookkeeping of § 2 gives, for and , the exact identity
where is the sum of over all with and all leafless with . Indeed, is the sum of over nonempty leafless . The sets with give the second term. By Theorem 2.1, proper leafless sets have at least six edges, and those with exactly six are copies of , each contributing , or of , contributing nothing. Everything else has at least seven edges.
Every term except the grid term is small:
Since , we have for . As , this gives
As , every is at most 1. The second term in (4) is therefore at most in absolute value, where is an absolute constant. We never need to know its sign.
A configuration with edges has fewer than edge subsets, so .
Hence
Everything now depends on how large is compared with .
Lemma 4.1. As ,
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 . 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 .
Proof of Theorem 1.1, assuming Theorem 4.1. Take in (5). Then
The middle term exceeds the other two by a factor , so for all sufficiently large . □
As anticipated in § 2, the exponent has no special role: the same computation works for with any .
Grids are abundant: proof of Lemma 4.1
Both bounds are statements about labelled configurations. By the orbit–stabiliser theorem, an Erdős -configuration has labelled copies on the vertex set . Hence
where is the number of Erdős -configurations on , and ranges over them.
Upper bound
Upper bound. An Erdős -configuration on is a set of triples from , so
Since , (6) gives , and summing over gives .
Lower bound: completing a grid at random
Lower bound: completing a grid at random. Fix , and a copy of on nine of the vertices in . By (6), , where is the number of Erdős -configurations on that contain the fixed grid. So we need : up to a factor , 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 -configuration every vertex lies in at least two edges (as we saw in § 2), and the degrees sum to . So if all degrees are 2 or 3, exactly six vertices have degree 2. We build configurations of this kind using the so-called configuration model (see e.g. [6]). Besides the nine grid vertices, we let six vertices have degree 2, and the remaining have degree 3; each grid vertex also gets degree 3, i.e. one incidence besides its two grid lines. Represent the missing incidences by stubs: one at each grid vertex, two at each degree-2 vertex and three at each other vertex, so
in total. Add new edges with three stubs each, again stubs in total, and match vertex stubs to edge stubs by a uniformly random bijection. Call the resulting multi-hypergraph . Every Erdős configuration on which contains the fixed grid and has the prescribed degrees arises from exactly
bijections: the new edges can be labelled in ways, and the stubs at each new edge and at each vertex can be ordered arbitrarily. Therefore
and by Stirling’s formula the fraction is . So the lower bound in Theorem 4.1 follows from the next proposition. (Any bound of the form would do, but the natural proof gives a constant.)
Proposition 5.1. as .
The multi-hypergraph is an Erdős -configuration if and only if
is linear, and
no set of edges with spans at most vertices.
(Linearity rules out repeated vertices in an edge and repeated edges, and it is the case of the definition; spans all 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 . Condition (ii) is global, but it fails only with probability .
Linearity
Linearity. Think of through its incidence graph: the bipartite multigraph with the vertices of on one side, the edges of on the other, and one link for each incidence. 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 .
The remaining short cycles are formed by stubs alone, and all but fifteen vertices have three stubs. Let and 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 stub pairs is present with probability for bounded , where . Since almost every vertex has three stubs,
The method of moments upgrades this to a Poisson limit. For fixed and , the factorial moment counts ordered tuples of distinct 2-cycles and distinct 4-cycles that are all present. Tuples of pairwise disjoint cycles contribute , 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 ways and each link costs a factor in probability, these tuples contribute . Hence converges in distribution to a pair of independent Poisson random variables with means 2 and 4, and
No dense edge sets
No dense edge sets. Call a set of edges of bad if and spans at most vertices. We show that the expected number of bad sets is , handling sets with at most edges directly and larger ones through their complements. In both cases a bad set forces all stubs of some new edges into a prescribed set of roughly stubs, at a cost of order , while the sets involved can be chosen in about ways. The remaining bounded powers of are controlled by the condition and by the fact that the grid is itself sparse.
Small sets. Suppose is bad and . Let be the set of grid lines in , say rows and columns, in total, and let the other edges of be new. Choose a set of exactly vertices containing every vertex of . Then contains the vertices covered by , and all stubs of the new edges in are matched to stubs at vertices of .
The grid is sparse in the same sense as an Erdős configuration: one grid line covers 3 vertices, and grid lines cover (one checks the few cases). Consequently ; more precisely if (as ), if , and if . Moreover, the number of vertices of not forced by is , where if , if , and if .
Now fix and . The new edges of can be chosen in at most ways and the rest of in at most ways, and the stubs land among the at most stubs at with probability at most . For bounded this gives , and in all three cases.
Large sets. Suppose is bad and , and let be its complement, with . Since spans at most vertices, at least vertices lie in no edge of , so all their edges are in . Choose a set of exactly such vertices. Let contain grid lines ( rows and columns) and new edges. A grid vertex can belong to only if both grid lines through it are in , so contains at most grid vertices. If contains grid vertices and vertices of degree , then the vertices of carry stubs, all of which must be matched to the stubs of the new edges in . In particular .
Fix the grid lines in , and , and . The new edges of can be chosen in at most ways and in ways, and the stub condition has probability . For bounded this gives , which is because .
Summing over $r. The estimates above are for fixed ; it remains to show that large contribute little. In both cases the bound for a given is at most , with an absolute implied constant. To see this, write . In both cases (otherwise the probability is zero) and differ from $3r$ by at most , so and ; moreover for and large, and the second binomial coefficient in each count is at most , because its lower index differs from by a bounded amount and .
Heuristically, choosing edges and about vertices is worth , while forcing stubs into a set of about stubs costs . With , the standard estimates and make this precise:
using . So the bound for each is at most for an absolute constant . For this is at most , and for it is at most . Choosing , the terms with add up to , while the finitely many contribute by the fixed- estimates. Since there are boundedly many choices of the grid lines involved and of and , the expected number of bad sets is .
Proof of Theorem 5.1. By the two estimates, .
This completes the proof of Theorem 4.1, and with it the proof of Theorem 1.1.
References
Institute of Science and Technology Austria (ISTA).
Email address: [email protected]
Department of Mathematics, University of Chicago.
Email address: [email protected]
References
- [1]M. Delcourt and L. Postle, Proof of the high girth existence conjecture via refined absorption, arXiv preprint arXiv:2402.17856 (2024).arxiv.org/abs/2402.17856
- [2]S. Glock, D. Kühn, A. Lo, and D. Osthus, On a conjecture of Erdős on locally sparse Steiner triple systems, Combinatorica 40 (2020), no. 3, 363–403.DOI
- [3]M. Kwan and H. T. Pham, Nonlinear lower-tail deviations at criticality, arXiv preprint arXiv:2610.10233 (2026).arxiv.org/abs/2610.10233
- [4]M. Kwan, A. Sah, M. Sawhney, and M. Simkin, High-girth Steiner triple systems, Ann. of Math. (2) 200 (2024), no. 3, 1059–1156.arxiv.org/abs/2201.04554
- [5]A. Sidorenko, On positive hypergraphs, European J. Combin. 106 (2022), Paper No. 103574, 5.
- [6]N. C. Wormald, Models of random regular graphs, Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239–298.