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

- ID: `P2632`
- Reference: `cyclic-315-packing-31`
- Page: https://theoremdb.org/statements/P2632
- Record maturity: Reviewed problem with recorded work

## 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.

### Context

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

### Definitions

- **Definition (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 (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.

### What counts as a solution

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

## Status

Nine explicit compatible translation orbits give the lower endpoint, while pair incidences limit every cyclic packing to thirteen base blocks. [4](#reference-4)

## Work

### Evidence for the current status

**Computation 1 (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.

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.

### Background and intake notes

- Original intake status: Status remains unverified. Cyclic packing tables may contain this parameter set.
- Normalize every base block by its lexicographically least translate containing 0. Treat each valid orbit as a 310-column exact-cover row over triples.
- Trap: a base block with a short orbit or an internal repeated triple orbit has a different coverage count. At prime 31, verify the 310 distinct triples rather than assuming it.

- Recorded example: 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}.

### Other known results

- **Theorem 1** (established): 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. [4](#reference-4)
- **Computation 2** (reproduced): Exhaustive development confirms that the nine orbits contain 279 distinct blocks and 2,790 distinct triples. [3](#reference-3)

### Prior approaches

- **Route 1** (inconclusive): 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. [3](#reference-3) [4](#reference-4) [2](#reference-2) [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python develops the construction, checks every triple, enumerates the complete orbit-level search space, and replays the upper bound. [2](#reference-2)

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `cyclic-315-packing-31`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1 entry has incomplete source metadata. Each affected row names the fields that still need editorial review.

1. <a id="reference-1"></a>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 https://doi.org/10.1002/1520-6610(2000)8:6%3C426::AID-JCD5%3E3.0.CO;2-4
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - For Largest cyclic 3-(31,5,1) packing: cyclic difference packing literature; pairwise condition differs
   - cyclic difference packing literature; pairwise condition differs
2. <a id="reference-2"></a>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 https://doi.org/10.1016/S0012-365X(03)00266-8
   - Also 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
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - 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
3. <a id="reference-3"></a>F. R. K. Chung, J. A. Salehi, and V. K. Wei, Optical orthogonal codes: design, analysis and applications https://doi.org/10.1109/18.30982
   - scholarly_publication; reference source
   - Source metadata incomplete: exact locator.
   - Source use: citation_only
   - foundational cyclic-shift correlation formulation
   - Source named by the research packet.
4. <a id="reference-4"></a>Robert F. Bailey and Andrea C. Burgess, Generalized packing designs 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 https://doi.org/10.1016/j.disc.2011.11.039
   - scholarly_publication; reference source
   - Source use: citation_only
   - ordinary packing definition and Johnson-Schonheim bound