Existence of large sets of Kirkman triple systems of orders 375 and 399 (the two remaining prime-power exceptions below 400)

The existence of large sets of Kirkman triple systems (LKTS) — partitions of all triples of a $v$-element set into $v-2$ pairwise disjoint resolvable Steiner triple systems — is a classical open problem in combinatorial design theory. For the prime-power family of orders $v=q+2$ with $q\equiv 1\pmod 6$, Zheng, Chang and Zhou established LKTS($q+2$) for every prime power $q<400$ except possibly $q=373$ and $q=397$, i.e. orders 375 and 399. The problem of constructing an LKTS(375) and an LKTS(399), or proving nonexistence, remains open; settling both would complete the prime-power LKTS classification below 400.

Background

A Steiner triple system of order $v$, STS($v$), is a pair $(X,\mathcal{B})$ where $X$ is a $v$-element set and $\mathcal{B}$ is a collection of 3-element subsets (blocks) such that every unordered pair of points lies in exactly one block. An STS($v$) is called resolvable, or a Kirkman triple system KTS($v$), if its block set partitions into parallel classes, each being a set of blocks that partitions the point set. A KTS($v$) exists if and only if $v\equiv 3\pmod 6$; such $v$ are called admissible. Two STS($v$) on the same point set are disjoint if they share no block; a counting argument shows at most $v-2$ mutually disjoint STS($v$) can coexist, and $v-2$ of them necessarily partition all $\binom{v}{3}$ triples. Such a partition is called a large set, and a large set of Kirkman triple systems, LKTS($v$), is a partition of all triples of a $v$-set into $v-2$ pairwise disjoint KTS($v$). The LKTS existence problem was posed by Sylvester in connection with Kirkman's 1850 schoolgirl problem. The corresponding problem for large sets of unrestricted (not necessarily resolvable) Steiner triple systems was completely settled by the early 1990s, when Teirlinck completed Lu's determination of that spectrum; the resolvable analogue, by contrast, remains one of the best-known open problems in combinatorial design theory.

Known LKTS orders are sparse. Direct constructions — surveyed by Chang and Zhou in 2013, with later additions — give scattered orders such as 9, 15, 21, 33, 39, 51, 69, 75, 105, 129, 201, 273, 285, 309, 333 and 369, and, from the two 2016/2017 papers of Zheng, Chang and Zhou, the further orders 111, 123, 159, 183, 195, 231, 279, 291, 339 and 381. A prominent family has order $v=q+2$ where $q$ is a prime power with $q\equiv 1\pmod 6$, because finite-field difference methods apply. A difference family is a small collection of base blocks in a finite group whose elementwise differences cover each nonzero group element a prescribed number of times, so that its translates under the group rebuild a full design; a starter parallel class is a single parallel class whose orbit under multipliers — automorphisms obtained by multiplying by suitable elements of the multiplicative group of the finite field $\mathbb{F}_q$ — generates an entire resolvable system. For $q\equiv 1\pmod{24}$ the method rests on $(q-1,\{2,3\},1)$ difference families over a group of order $q-1$; for $q\equiv 13\pmod{24}$, the residue class of both exceptions, it rests instead on pairs of starter parallel classes on the point set $\mathbb{Z}_q\cup\{\infty_1,\infty_2\}$, developed under multipliers. Zheng, Chang and Zhou proved that an LKTS($q+2$) exists for every prime power $q\equiv 1\pmod 6$ with $q<400$, with exactly two possible exceptions: $q=373$ and $q=397$, that is, orders $v=375$ and $v=399$. Both exceptions are primes congruent to $13\pmod{24}$, the residue class in which the single-starter multiplier construction is inapplicable and a two-starter-parallel-class construction is required — an approach that succeeded for the smaller primes 109, 157, 181, 229 and 277 but was not carried through for 373 and 397.

No known recursive construction reaches these two orders. Denniston's tripling construction produces LKTS($3v$) from LKTS($v$) and thus needs an admissible cofactor $v$; but $375=3\cdot 5^3$ and $399=3\cdot 7\cdot 19$, whose cofactors 125 and 133 violate the admissibility condition $v\equiv 3\pmod 6$ (they are congruent to 5 and 1), so no tripling chain can produce either order. The same tripling form underlies constructions from RDSQS — Steiner quadruple systems (Steiner systems $S(3,4,v)$, designs whose blocks have size 4 and cover every triple of points exactly once) whose derived design at each point, formed by deleting that point from every block containing it, is resolvable — via the theorem that an RDSQS($v+1$) yields an LKTS($3v$). This route is blocked outright rather than merely unexplored: a resolvable derived design forces $v\equiv 3\pmod 6$, so an RDSQS can exist only in order $v+1\equiv 4\pmod 6$, whereas the required orders 126 and 134 are congruent to 0 and 2 modulo 6. The recursion of Wang and Shi produces LKTS($q^n+2$) only from a base LKTS($q+2$), and the 2026 construction of Wang produces LKTS($7q+2$) from an LKTS($q+2$) plus an auxiliary permutation structure on an abelian group; since 373 and 397 are primes not divisible by 7, neither 375 nor 399 has either form. Settling the last two prime-power exceptions below 400 is therefore expected to require further construction methods or dedicated computational searches.

Problem Statement

Determine whether a large set of Kirkman triple systems of order 375 exists, and whether one of order 399 exists.

Concretely, for each $v\in\{375,399\}$: does there exist a partition of all $\binom{v}{3}$ triples of a $v$-element set into $v-2$ pairwise disjoint Kirkman triple systems of order $v$? For $v=375$ this means 373 disjoint KTS(375), each with 23,375 blocks resolved into 187 parallel classes of 125 blocks, together covering all 8,718,875 triples; for $v=399$ it means 397 disjoint KTS(399), each with 26,467 blocks resolved into 199 parallel classes of 133 blocks, covering all 10,507,399 triples.

For each of the two orders the question is settled either by an explicit construction or by a proof that no such large set exists. The two orders together form one classification objective: settling both completes the theorem of Zheng, Chang and Zhou that an LKTS($q+2$) exists for every prime power $q\equiv 1\pmod 6$ with $q<400$, closing the last two exceptions of the prime-power-size classification below 400.

References

1. Hao Zheng, Yanxun Chang, Junling Zhou, Large sets of Kirkman triple systems of prime power sizes, Designs, Codes and Cryptography 85(3):411-423 (2017; online December 2016), DOI: 10.1007/s10623-016-0315-3, https://doi.org/10.1007/s10623-016-0315-3.
2. Hao Zheng, Yanxun Chang, Junling Zhou, Direct constructions of large sets of Kirkman triple systems, Designs, Codes and Cryptography 83:23-32 (2017; online March 2016), DOI: 10.1007/s10623-016-0197-4, https://doi.org/10.1007/s10623-016-0197-4.
3. Yanxun Chang, Junling Zhou, Large sets of Kirkman triple systems and related designs, Journal of Combinatorial Theory, Series A 120:649-670 (2013), DOI: 10.1016/j.jcta.2012.12.001, https://doi.org/10.1016/j.jcta.2012.12.001.
4. Yan Liu, Jianguo Lei, More results on large sets of Kirkman triple systems, Designs, Codes and Cryptography 91:2677-2686 (2023), DOI: 10.1007/s10623-023-01221-9, https://doi.org/10.1007/s10623-023-01221-9 (preprint arXiv:2210.06214, https://arxiv.org/abs/2210.06214).
5. Juanjuan Xu, Lijun Ji, Large sets of Kirkman triple systems of orders $2^{2n+1}+1$, Discrete Mathematics 344:112373 (2021), DOI: 10.1016/j.disc.2021.112373, https://doi.org/10.1016/j.disc.2021.112373.
6. Yuli Tan, Junling Zhou, Steiner quadruple systems with minimum colorable derived designs: constructions and applications, Designs, Codes and Cryptography 93:4117-4140 (2025), DOI: 10.1007/s10623-025-01677-x, https://doi.org/10.1007/s10623-025-01677-x (preprint arXiv:2503.11934, https://arxiv.org/abs/2503.11934).
7. Chen Wang, A new recursive construction for large sets of Kirkman triple systems, preprint, July 2026, arXiv:2607.21521, https://arxiv.org/abs/2607.21521.
8. Chen Wang, Cong Shi, Large sets of Kirkman triple systems with order $q^n+2$, Discrete Mathematics 340:1042-1045 (2017), DOI: 10.1016/j.disc.2016.11.008, https://doi.org/10.1016/j.disc.2016.11.008 (preprint arXiv:1307.3019, https://arxiv.org/abs/1307.3019).
9. R. H. F. Denniston, Further cases of double resolvability, Journal of Combinatorial Theory, Series A 26:298-303 (1979), DOI: 10.1016/0097-3165(79)90106-7, https://doi.org/10.1016/0097-3165(79)90106-7.
10. Luc Teirlinck, A completion of Lu's determination of the spectrum for large sets of disjoint Steiner triple systems, Journal of Combinatorial Theory, Series A 57:302-305 (1991), DOI: 10.1016/0097-3165(91)90053-J, https://doi.org/10.1016/0097-3165(91)90053-J.