# P2562: Covering every five-set with eight-sets on sixteen points

- ID: `P2562`
- Reference: `covering-design-16-8-5`
- Page: https://theoremdb.org/statements/P2562
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(C(16,8,5)\) be the smallest size of a family \(\mathcal B\subseteq\binom{[16]}{8}\) such that every five-element subset of \([16]\) lies in some \(B\in\mathcal B\). Determine \(C(16,8,5)\).

### Remarks

- **Remark.** This is the classical covering-design number with 16 points, block size 8, and covered-subset size 5.
- **Remark.** Blocks are distinct; relabeling the 16 points preserves feasibility.

### What counts as a solution

- Give a cover and a matching lower-bound certificate establishing the exact value.

## Status

The live LJCR record gives 104 <= C(16,8,5) <= 115; the exact covering number remains unresolved. [2](#reference-2) [3](#reference-3) [4](#reference-4)

## Work

### Evidence for the current status

**Claim 1 (The current table interval is 104 through 115).** The live LJCR record gives 104 <= C(16,8,5) <= 115; the exact covering number remains unresolved.

A \((16,8,5)\) covering is a family of 8-subsets of a 16-point set such that every 5-subset lies in at least one block. The covering number \(C(16,8,5)\) is the smallest possible family size.

The La Jolla Covering Repository page accessed on 2026-07-24 reports
\[
104\le C(16,8,5)\le115.
\]
It credits the displayed 115-block cover to Alessandro Jurcovich and labels the lower-bound method `Schonheim`. The companion replay verifies every block and all \(\binom{16}{5}=4368\) coverage requirements. The lower-bound record spells out the recursive calculation. Together they certify the interval. They leave an eleven-block gap, so the candidate's request for a single exact value is still open.

### Background and intake notes

The published interval is 104 <= C(16,8,5) <= 115. A simple lexicographic greedy rule independently gives a verified 118-block cover, which provides a reproducible baseline for stronger searches.

- Original intake status: The La Jolla Covering Repository currently records 104 <= C(16,8,5) <= 115; the exact value is unresolved there.
- The repository entry at https://ljcr.dmgordon.org/cover/show_cover.php?k=8&t=5&v=16 supplies a 115-block cover and attributes the lower bound 104 to the Schonheim bound.
- An exact solver could combine isomorph rejection, fractional-cover bounds, and branch certificates indexed by the first uncovered five-set.

- Recorded example: The greedy baseline covers 56 new five-sets with each of its first 30 blocks and finishes after 118 blocks.

### Other known results

- **Computation 1** (reproduced): Exhaustive enumeration confirms that the published family contains every 5-subset in at least one of its 115 distinct 8-blocks. [2](#reference-2)
- **Proposition 1** (supported): Schonheim's inequality, seeded by C(13,5,2)=10, gives C(16,8,5) >= 104. [1](#reference-1)

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python decodes the archived block list, checks its shape, enumerates every 5-subset, and verifies the coverage and lower-bound arithmetic. [2](#reference-2)

### Computational notes

- All 12870 eight-subsets and 4368 five-subsets were represented as exact bitsets. The lexicographic greedy rule selected 118 distinct blocks, and an independent union check verified coverage of all 4368 five-subsets. Each of the final eight choices covered 8 new five-subsets. The repository's displayed 115 blocks were also parsed as subsets of [16] and checked to cover every five-subset.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `covering-design-16-8-5`, 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. <a id="reference-1"></a>Daniel M. Gordon, La Jolla Covering Repository, C(13,5,2) record (checked 26 July 2026). C(13,5,2) record: exact value 10 and lower-bound attribution https://ljcr.dmgordon.org/cover/show_cover.php?k=5&t=2&v=13
   - website; reference source; web version checked 2026-08-01; checked 2026-07-24
   - Source use: citation_only
   - Records C(13,5,2)=10, the seed value used in the recursive lower-bound calculation.
2. <a id="reference-2"></a>Daniel M. Gordon, La Jolla Covering Repository, C(16,8,5) record and 115-block covering credited to Alessandro Jurcovich (checked 26 July 2026). C(16,8,5) bounds and the complete 115-block family credited to Alessandro Jurcovich https://ljcr.dmgordon.org/cover/show_cover.php?k=8&t=5&v=16
   - Also cited at Live C(16,8,5) bound and 115-block family
   - Also cited at Complete 115-block list credited to Alessandro Jurcovich; independently replayed in cd1685-artifact-exhaustive-cover
   - Also cited at Inline CPython standard-library replay of the complete LJCR block list, executed 2026-07-24
   - dataset; dataset source; dataset snapshot checked 2026-08-01; checked 2026-07-24
   - Source use: citation_only
   - Supplies Jurcovich's 115 blocks and records the current interval 104 through 115 for C(16,8,5).
   - Source named by the research packet.
3. <a id="reference-3"></a>Johanan Schönheim, On Coverings, Pacific Journal of Mathematics 14(4) (1964), 1405-1411. The recursive covering inequality on pp. 1405-1407 https://msp.org/pjm/1964/14-4/pjm-v14-n4-p29-s.pdf
   - journal_article; primary source; version of record; checked 2026-07-24
   - Source use: citation_only
   - Provides the recursive covering inequality used to derive the lower bound 104.
4. <a id="reference-4"></a>Daniel Gordon, Greg Kuperberg, and Oren Patashnik, New constructions for covering designs, arXiv:math/9502238v1 (1995). Daniel Gordon, Greg Kuperberg, and Oren Patashnik, New constructions for covering designs, Journal of Combinatorial Designs 3(4) (1995), 269-284; definition and small-parameter tables https://arxiv.org/abs/math/9502238
   - preprint; reference source; arXiv:math/9502238v1; checked 2026-07-24
   - Source use: citation_only
   - Gives the standard covering-design framework and small-parameter construction context used in the status audit.