A translational-symmetry barrier for C(16,5,3): every regular abelian action requires 80 blocks

Problem and result

A \((v,k,t)\) covering is a family \(\mathcal B\) of \(k\)-subsets of a \(v\)-set such that every \(t\)-subset is contained in at least one block. Its minimum size is \(C(v,k,t)\). LJCR v1.2, published 24 April 2026 from a database frozen in March 2026, records \[ 61\le C(16,5,3)\le 65. \] The lower endpoint is reproduced directly by the Schönheim recurrence [1], \[ \left\lceil\frac{16}{5}\left\lceil\frac{15}{4}\left\lceil\frac{14}{3}\right\rceil\right\rceil\right\rceil=61. \] The machine-readable LJCR history entry records size 65, contributor Rade Belic, and date 1997-08-06 [3]. LJCR is an authoritative versioned archival dataset, not by itself a peer-reviewed proof of worldwide priority. We independently extracted that witness from the covers.json key C(16,5,3), converted it to labels \(0,\ldots,15\), and verified 65 distinct blocks, no uncovered triple, and SHA-256 53d03ffea807a1b32d9bccb533cb57226761d4333ffb5323504c94dd3ca7fe7e for the newline-terminated block list. We make no claim that 65 is optimal without symmetry.

Let an abelian group \(G\) of order 16 act regularly on its own elements by translation. Write \(C_G(16,5,3)\) for the smallest size of a covering invariant under every translation in \(G\).

Theorem. For each abelian group \(G\) of order 16, \[ C_G(16,5,3)=80. \] Equivalently, the result holds for exactly the five invariant-factor types \[ C_{16},\quad C_8\times C_2,\quad C_4\times C_4,\quad C_4\times C_2^2,\quad C_2^4. \]

This is a restricted-family theorem, not a new unrestricted upper bound. Its content is a symmetry barrier: none of the regular abelian translation prescriptions can reach even 79 blocks, whereas LJCR v1.2 archives an unrestricted 65-block covering.

Relation to prior work and search scope

Gordon, Kuperberg, and Patashnik discuss cyclic development as one of several computational construction methods and report the earlier 68-block upper bound at this cell [2]. Kramer and Mesner provide the general orbit-incidence framework [4]. LJCR v1.2 supplies the later 65-block benchmark and its history, but does not record symmetry-restricted minima [3].

To the authors’ knowledge, searches completed 24 August 2026 of arXiv, the LJCR/Zenodo record and its source files, and exact-parameter web indexes found no prior source determining the minimum for the cyclic action or across all five regular abelian actions of order 16. Queries included C(16,5,3) cyclic, 16 5 3 covering design 80, translation-invariant C(16,5,3), and regular abelian covering design. This documented search supports a narrow novelty claim; it cannot prove a universal negative about unindexed literature.

Why only four-orbit exclusion is needed

For a 5-subset \(B\subseteq G\), let \(H\) be its stabilizer under translation. The restricted action of \(H\) on \(G\) is free, so every \(H\)-orbit has size \(|H|\). Since an \(H\)-invariant \(B\) is a union of such orbits, \(|H|\) divides \(|B|=5\). It also divides \(|G|=16\). Therefore \(|H|=1\), and every orbit of 5-subsets has size 16. The same argument with \(3\) in place of \(5\) shows that every triple orbit also has size 16.

Consequently there are \[ \binom{16}{5}/16=273 \] block orbits and \[ \binom{16}{3}/16=35 \] triple orbits. Any translation-invariant covering is a union of whole block orbits, hence its size is a multiple of 16. The elementary counting bound \(|\mathcal B|\binom 53\geq\binom{16}3\) gives \(|\mathcal B|\geq56\), so the only possible invariant size below 80 is 64, i.e. four block orbits. It remains only to exclude every four-orbit choice and then exhibit five-orbit covers.

Exhaustive lower certificate

For each group type, elements are tuples in lexicographic order, with the last coordinate varying fastest. Thus, for example, label \(2a+b\) denotes \((a,b)\in C_8\times C_2\), and label \(4a+2b+c\) denotes \((a,b,c)\in C_4\times C_2^2\). Addition is componentwise modulo the corresponding invariant factors. Explicitly, the permutation group is generated by the coordinate translations \(\tau_j(a_1,\ldots,a_j,\ldots,a_r)=(a_1,\ldots,a_j+1\pmod {n_j},\ldots,a_r)\) for the listed invariant factors \((n_1,\ldots,n_r)\).

The certificate uses the standard orbit-incidence reduction associated with Kramer and Mesner [4] and performs the following finite computation independently for each group.

1. Enumerate all \(\binom{16}{5}=4368\) blocks and canonicalize each under the 16 translations, obtaining 273 block orbits.
2. Enumerate and canonicalize all \(\binom{16}{3}=560\) triples, obtaining 35 triple orbits.
3. Represent each block orbit by a 35-bit mask: bit \(q\) is set exactly when at least one translated block contains a member of triple orbit \(q\). Translation equivariance then implies that it contains every member of that triple orbit. Hence a union of block orbits covers all 560 triples if and only if the OR of its masks has all 35 bits set.
4. Loop over every \(0\le i<j<k<\ell<273\), OR the four masks, and count set bits.

The loop count returned in every case is \[ \binom{273}{4}=226{,}387{,}980, \] which is also checked against the closed form. The maximum number of the 35 triple orbits covered by four block orbits is:

No four-orbit union covers all 35 triple orbits. Because every block orbit has size 16, this proves \(C_G(16,5,3)\ge80\) for all five groups. This is a computer-assisted proof by direct enumeration of all four-element subsets of a 273-element list; it does not depend on a branch-and-bound solver or an unproved optimality status. The supplied verifier uses 64-bit masks. Numba [5] only compiles the four nested loops; an independent standard-library reimplementation reproduced every maximum, tie count, witness histogram, and hash.

Five-orbit witnesses

The reverse inequality follows from the following base blocks. For each row, translate each of the five displayed blocks by all 16 elements of the stated group. Every orbit has size 16, so each recipe yields 80 distinct blocks.

A direct sweep over all 560 triples gives zero uncovered triples in every row. The coverage histograms (multiplicity: number of triples) and hashes of the expanded, lexicographically sorted, newline-terminated block lists are:

Each histogram sums to 560 triples and has weighted sum 800, as required by 80 blocks containing \(\binom53=10\) triples each.

Interpretation and limitations

Cyclic development is among the classical computational construction methods used in covering-design work [2], and prescribing automorphisms is a standard way to reduce covering searches. At \((16,5,3)\), however, regular translation symmetry is not merely unhelpful: for every abelian group structure on the point set it forces at least 80 blocks. Because \(C(16,5,3)\le65\), the exact restricted optimum 80 is at least 15 blocks above the unknown unrestricted optimum; it is exactly 15 blocks, or \(15/65\approx23.1\%\), above the independently verified LJCR v1.2 benchmark.

This points the search in a falsifiable direction. A construction improving 65 cannot be invariant under a regular abelian subgroup. Any regular abelian subgroup of \(S_{16}\) is permutation-isomorphic, after relabeling the points, to the left-regular action of one of the five groups above, so the classification applies. Searches that hard-code cyclic, elementary-abelian, or any other abelian translation development can therefore be excluded before optimization. The theorem does not exclude nonabelian regular groups, nonregular automorphism groups, or designs with trivial automorphism group; it does not determine the unrestricted value of \(C(16,5,3)\). Those are deliberate boundaries, not extrapolations.

Reproducibility

The supplementary certificate is verify_abelian_80.py (SHA-256 042ed421431b0402ef907c8bd511663142937ba33295b63d255cccaf813342d4). It was run under Python 3.10 with NumPy 2.2.6 and Numba 0.61.2. It reconstructs the five group actions and all subset orbits from first principles, exhausts the four-orbit choices, expands every witness, recomputes all 560 coverage multiplicities, and writes c1653-abelian-exhaustive-certificate.json. No external covering table is consumed by the proof. The LJCR archive is used only to contextualize and independently check the unrestricted 65-block benchmark.

References

[1] J. Schönheim, “On coverings,” Pacific Journal of Mathematics 14 (1964), 1405–1411. https://doi.org/10.2140/pjm.1964.14.1405

[2] D. M. Gordon, G. Kuperberg, and O. Patashnik, “New constructions for covering designs,” Journal of Combinatorial Designs 3 (1995), 269–284. https://doi.org/10.1002/jcd.3180030404

[3] D. Gordon, La Jolla Coverings Repository, version 1.2, Zenodo; published 24 April 2026, accessed 24 August 2026. https://doi.org/10.5281/zenodo.19735294

[4] E. S. Kramer and D. M. Mesner, “t-designs on hypergraphs,” Discrete Mathematics 15 (1976), 263–296. https://doi.org/10.1016/0012-365X(76)90030-3

[5] S. K. Lam, A. Pitrou, and S. Seibert, “Numba: a LLVM-based Python JIT compiler,” LLVM-HPC (2015), 1–6. https://doi.org/10.1145/2833157.2833162