[#P2632] Largest cyclic 3-(31,5,1) packing

A neutral schematic of the objects and relations in the statement.

Problem. A base block is a five-element subset \(B\subseteq\mathbb Z/31\mathbb Z\), with translation orbit \(\{B+t:t\in\mathbb Z/31\mathbb Z\}\). Choose one representative from each selected orbit so that no three-element subset of \(\mathbb Z/31\mathbb Z\) occurs in more than one translated block. Determine the maximum possible number of selected base blocks.

1Context

This is a translation-invariant packing problem for five-subsets of a cyclic group, with triples as the capacity-one resources.

2Definitions

Definition 1 (base block and translation orbit). A base block is a five-element subset \(B\subseteq\mathbb Z/31\mathbb Z\), and its orbit is \(\{B+t:t\in\mathbb Z/31\mathbb Z\}\).

Definition 2 (cyclic \(3\text{-}(31,5,1)\) packing). A cyclic \(3\text{-}(31,5,1)\) packing is a collection of translation orbits in which no three-subset occurs in more than one translated block.

3What counts as a solution

Give the maximum set of base blocks and verify all translated triples, together with a complete upper-bound certificate.

1Status

Current status (The certified interval is 9 through 13 base blocks). Nine explicit compatible translation orbits give the lower endpoint, while pair incidences limit every cyclic packing to thirteen base blocks.^[1]

1Records

Record	Kind	Assessment
	Result	Reproduced
claim · Computation 1 Nine explicit compatible translation orbits give the lower endpoint, while pair incidences limit every cyclic packing to thirteen base blocks.^[1] Relevance to this problem For Largest cyclic 3-(31,5,1) packing, record cyclic315-claim-certified-interval-9-13 (“The certified interval is 9 through 13 base blocks”) records a bound, answer, status fact, or structural consequence. The record states: Nine explicit compatible translation orbits give the lower endpoint, while pair incidences limit every cyclic packing to thirteen base blocks. Evidence ReproducedA computation someone reran from the artifact on this page. Record state open Scope translation orbits of 5-subsets of Z_31 in which each 3-subset occurs in at most one developed block Sources Reference 1 Details Let \(M\) be the maximum number of base blocks. The checked construction in this record proves \(M\geq9\). A pair-incidence argument proves \(M\leq13\), improving the raw triple-counting bound of 14. Thus \[ \boxed{9\leq M\leq13}. \] The exact value remains unresolved by the evidence retained here. The cyclic packing is equivalently a one-dimensional optical orthogonal code of length 31, weight 5, and auto- and cross-correlation at most 2. The literature audit found the general OOC correspondence and Johnson bound, but no primary-source table or construction settling this exact parameter. Open full record →
	Result	Established
claim · Theorem 1 Every pair lies in at most nine developed blocks, which caps an unrestricted packing at 418 blocks and a full-orbit cyclic packing at thirteen base blocks.^[1] Relevance to this problem For Largest cyclic 3-(31,5,1) packing, record cyclic315-claim-pair-incidence-upper-13 (“Pair incidences give an upper bound of thirteen”) records a bound, answer, status fact, or structural consequence. The record states: Every pair lies in at most nine developed blocks, which caps an unrestricted packing at 418 blocks and a full-orbit cyclic packing at thirteen base blocks. Evidence EstablishedA complete argument is recorded and has been reviewed. Scope every cyclic 3-(31,5,1) packing consisting of full translation orbits Sources Reference 1 Argument Fix a pair of points. Exactly 29 triples contain it. A developed 5-block containing the pair uses the three triples obtained by adjoining one of its other points. Distinct packing blocks use disjoint triples, so the pair belongs to at most \(\lfloor29/3\rfloor=9\) blocks. If the developed packing has \(B\) blocks, counting pair-block incidences gives \[ 10B=B\binom52\leq9\binom{31}{2}=4185, \] hence \(B\leq418\). Every translation orbit of a 5-subset has length 31: a nonzero translation generates the prime-order group, and an invariant subset would have size 0 or 31. A cyclic packing with \(M\) base blocks therefore has \(B=31M\). It follows that \[ M\leq\left\lfloor\frac{418}{31}\right\rfloor=13. \] This is the relevant Johnson-style bound with the orbit divisibility condition imposed. Related: Computation 1 Open full record →
	Result	Reproduced
claim · Computation 2 Exhaustive development confirms that the nine orbits contain 279 distinct blocks and 2,790 distinct triples.^[2] Relevance to this problem For Largest cyclic 3-(31,5,1) packing, record cyclic315-claim-nine-orbit-packing (“Nine base blocks form a cyclic 3-packing”) records a bound, answer, status fact, or structural consequence. The record states: Exhaustive development confirms that the nine orbits contain 279 distinct blocks and 2,790 distinct triples. Evidence ReproducedA computation someone reran from the artifact on this page. Record state established Scope all 279 translates and all 2,790 triples developed from the nine displayed base blocks in Z_31 Sources Reference 2 Details The base blocks are \[ \begin{aligned} &\{0,3,9,12,24\},\ \{0,2,6,8,15\},\ \{0,1,15,27,29\},\\ &\{0,1,9,18,20\},\ \{0,3,6,14,19\},\ \{0,3,7,13,27\},\\ &\{0,1,2,7,24\},\ \{0,1,5,13,26\},\ \{0,1,4,21,22\}. \end{aligned} \] Develop each block by every translation in \(\mathbb Z_{31}\). Each orbit has length 31, and the resulting 279 blocks are distinct. Exhaustive enumeration of the ten triples in every developed block produces 2,790 distinct triples, each with multiplicity one. This proves the packing condition and the lower bound \(M\geq9\). The canonical newline-delimited base-block list has SHA-256 digest `2323141aa6883f95a8b8ee5b300cc4b8a57f7437d08a43054de576c99e30228f`. Related: Computation 1 Open full record →
	Trace	Inconclusive
attempt · Route 1 The checked sources establish the general framework and upper-bound method, while a capped feasibility run produced no reusable certificate for sizes ten through thirteen.^[2][1][3][4] Relevance to this problem For Largest cyclic 3-(31,5,1) packing, record cyclic315-attempt-literature-and-exact-search-audit (“Literature and exact-search audit leaves four cases”) documents a concrete method, search boundary, or failed route. The record states: The checked sources establish the general framework and upper-bound method, while a capped feasibility run produced no reusable certificate for sizes ten through thirteen. Evidence InconclusiveThe recorded search or audit ended without settling the question. Scope primary sources and a capped orbit-level feasibility search checked on 2026-07-25 Sources Reference 2, Reference 1, Reference 3, Reference 4 What happened The primary-source audit covered the original optical orthogonal code framework of Chung, Salehi, and Wei; the ordinary packing definition and Johnson-Schonheim bound summarized by Bailey and Burgess; and Chu and Colbourn's exact-search formulation for small cyclic OOCs. Related cyclic difference-packing and cyclic group-divisible-packing papers concern different strengths or block sizes. No checked source stated \(\Phi(31,5,2)\) or printed a construction with ten or more codewords. A complete orbit generator found 145 translation classes of triples and 4,761 internally valid translation classes of 5-subsets. The maximum is therefore a 0-1 set-packing problem with 145 at-most-one constraints. A 120-second Z3 feasibility attempt at size 13 did not finish and yielded no proof object. This timing result carries no mathematical weight. A useful continuation would encode target sizes 13, 12, 11, and 10 with a proof-producing pseudo-Boolean or SAT solver, retain a DRAT/LRAT-style unsatisfiability certificate when available, and replay any satisfying base-block list with the artifact in this record. Related: Computation 1 Open full record →
	Artifact	Reproduced
artifact · Artifact 1 Standard-library Python develops the construction, checks every triple, enumerates the complete orbit-level search space, and replays the upper bound.^[3] Relevance to this problem For Largest cyclic 3-(31,5,1) packing, record cyclic315-artifact-exact-verifier (“Exact difference and orbit verifier”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python develops the construction, checks every triple, enumerates the complete orbit-level search space, and replays the upper bound. Evidence ReproducedA computation someone reran from the artifact on this page. Record state available Scope the displayed packing, all cyclic 3- and 5-subset orbits on Z_31, and the pair-incidence arithmetic Sources Reference 3 Entry point `join source_lines with newline and run with python3` Runtime CPython 3, standard library only Details The program uses exact integer and set arithmetic. It develops all nine base blocks, rejects any duplicate developed block or triple, and canonicalizes translation orbits by trying every point as the translate sent to zero. It also enumerates all 5,481 translation orbits of 5-subsets. Exactly 4,761 are internally admissible because their ten triples lie in ten distinct triple orbits. These are the columns of the finite set-packing formulation over 145 triple orbits. The enumeration scopes a future exact search. It does not certify infeasibility for ten through thirteen base blocks. The pair-incidence proof supplies the certified upper endpoint. The seven-line output has SHA-256 digest `027dcba8ec13682f044b6c7ee8eb1e609f5e5ac537dee552a17d0e18a2f427f2`. Related: Computation 2 · Theorem 1 Open full record →
No records match these filters.

Notes and companion materialContext, examples, and computations

Original intake status. UNKNOWN as of 2026-07-25. Nine explicit compatible translation orbits give the lower endpoint, while pair incidences limit every cyclic packing to thirteen base blocks. The checked sources do not settle the full acceptance condition.

The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: Nine explicit compatible translation orbits give the lower endpoint, while pair incidences limit every cyclic packing to thirteen base blocks.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.

Recorded example 1. Nine compatible base blocks found in one run were {0,3,9,12,24}, {0,2,6,8,15}, {0,1,15,27,29}, {0,1,9,18,20}, {0,3,6,14,19}, {0,3,7,13,27}, {0,1,2,7,24}, {0,1,5,13,26}, and {0,1,4,21,22}.

Computational notes

There are 4495 triples. Each full block orbit covers 31 times 10=310 triples, so at most 14 base blocks are possible. Three thousand seeded random orbit-greedy runs found the displayed compatible nine-block packing, which covers 2790 distinct triples.

How the 5 records connectTyped relations and evidence flow

ProblemLargest cyclic 3-(31,5,1) packing

Computation 1The certified interval is 9 through 13 base blocksin this packetReproduced
Computation 2Nine base blocks form a cyclic 3-packingsupportsReproduced
Artifact 1Exact difference and orbit verifierverifiesReproduced
Theorem 1Pair incidences give an upper bound of thirteensupportsEstablished
Route 1Literature and exact-search audit leaves four casescontextualizesInconclusive

2See also

Orders of ternary row-orthogonal matrices with a full rowdesign theory
Components of the Pasch-switch graph on STS(15) classesdesign theory
Hadamard matrix conjecturedesign theory

How to cite

TheoremDB contributors, “Largest cyclic 3-(31,5,1) packing,” TheoremDB research memory, snapshot of July 25, 2026. https://theoremdb.org/statements/cyclic-315-packing-31

This page as plain text: cyclic-315-packing-31.md

This problem includes 5 records joined by 5 typed links, sourced from doi.org^[2], current as of July 25, 2026.

1References

Robert F. Bailey and Andrea C. Burgess, Generalized packing designs. Robert F. Bailey and Andrea C. Burgess, Generalized packing designs, Discrete Mathematics 313 (2013), 1167-1190, Definition 1.1.1 and Proposition 1.1.4; parameter-specific construction and upper-bound replay in this fixture; The general Johnson-Schonheim packing bound is stated as Proposition 1.1.4 by Bailey and Burgess; the pair-incidence specialization and orbit divisibility step are proved here; F. R. K. Chung, J. A. Salehi, and V. K. Wei, Optical orthogonal codes: design, analysis and applications, IEEE Transactions on Information Theory 35 (1989), 595-604; literature audit and capped computation on 2026-07-25. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The certified interval is 9 through 13 base blocks. Nine explicit compatible translation orbits give the lower endpoint, while pair incidences limit every cyclic packing to thirteen base blocks. Pair incidences give an upper bound of thirteen. Every pair lies in at most nine developed blocks, which caps an unrestricted packing at 418 blocks and a full-orbit cyclic packing at thirteen base blocks. ordinary packing definition and Johnson-Schonheim boundAlso cited at The general Johnson-Schonheim packing bound is stated as Proposition 1.1.4 by Bailey and Burgess; the pair-incidence specialization and orbit divisibility step are proved here.ordinary packing definition and Johnson-Schonheim bound
Packet source. F. R. K. Chung, J. A. Salehi, and V. K. Wei, Optical orthogonal codes: design, analysis and applications. Construction recorded in the TheoremDB candidate and independently replayed in cyclic315-artifact-exact-verifier; OOC formulation follows Chung, Salehi, and Wei, IEEE Transactions on Information Theory 35 (1989), 595-604; F. R. K. Chung, J. A. Salehi, and V. K. Wei, Optical orthogonal codes: design, analysis and applications, IEEE Transactions on Information Theory 35 (1989), 595-604; literature audit and capped computation on 2026-07-25. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.Nine base blocks form a cyclic 3-packing. Exhaustive development confirms that the nine orbits contain 279 distinct blocks and 2,790 distinct triples. Literature and exact-search audit leaves four cases. The checked sources establish the general framework and upper-bound method, while a capped feasibility run produced no reusable certificate for sizes ten through thirteen. foundational cyclic-shift correlation formulationfoundational cyclic-shift correlation formulationSource named by the research packet.
Wensong Chu and Charles J. Colbourn, “Optimal (n,4,2)-OOC of small orders”. Discrete Mathematics 279(1-3) (2004), 163-172. DOI 10.1016/S0012-365X(03)00266-8. Inline CPython verifier; the set-theoretic cyclic-shift formulation follows Wensong Chu and Charles J. Colbourn, Optimal (n,4,2)-OOC of small orders, Discrete Mathematics 279 (2004), Definitions 1.1-1.3; F. R. K. Chung, J. A. Salehi, and V. K. Wei, Optical orthogonal codes: design, analysis and applications, IEEE Transactions on Information Theory 35 (1989), 595-604; literature audit and capped computation on 2026-07-25. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.Exact difference and orbit verifier. Standard-library Python develops the construction, checks every triple, enumerates the complete orbit-level search space, and replays the upper bound. set formulation and algorithmic treatment of small cyclic OOCs; weight differsAlso cited at Inline CPython verifier; the set-theoretic cyclic-shift formulation follows Wensong Chu and Charles J. Colbourn, Optimal (n,4,2)-OOC of small orders, Discrete Mathematics 279 (2004), Definitions 1.1-1.3.For Largest cyclic 3-(31,5,1) packing: Standard-library Python develops the construction, checks every triple, enumerates the complete orbit-level search space, and replays the upper bound.set formulation and algorithmic treatment of small cyclic OOCs; weight differs
Christopher N. Swanson, “Planar cyclic difference packings”. Journal of Combinatorial Designs 8(6) (2000), 426-434. DOI 10.1002/1520-6610(2000)8:6<426::AID-JCD5>3.0.CO;2-4. F. R. K. Chung, J. A. Salehi, and V. K. Wei, Optical orthogonal codes: design, analysis and applications, IEEE Transactions on Information Theory 35 (1989), 595-604; literature audit and capped computation on 2026-07-25. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.cyclic difference packing literature; pairwise condition differsFor Largest cyclic 3-(31,5,1) packing: cyclic difference packing literature; pairwise condition differs

CC0 cyclic packing target with an orbit-level incumbent.

[#P2632] Largest cyclic 3-(31,5,1) packing

1Context

2Definitions

3What counts as a solution

1Status

1Records

Computational notes

2See also

1Lean verification

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Report a problem

1Context

2Definitions

3What counts as a solution

1Status

1Records

Computational notes

2See also

1References

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance