# P3770: Smallest perfect hash family for twelve keys and four colors

- ID: `P3770`
- Reference: `perfect-hash-twelve-four`
- Page: https://theoremdb.org/statements/P3770
- Export scope: built Markdown snapshot. The current public packet may have changed since this build.
- Build source revision: 8761a3148f04464c77e33962395dfa4a75cd2b51
- Current Markdown: https://api.theoremdb.org/v1/statements/perfect-hash-twelve-four?representation=markdown
- Record maturity: Reviewed problem

## The problem

Determine the minimum size of a family \(\mathcal H\) of functions \(h:\{1,\ldots,12\}\to\{1,2,3,4\}\) such that every four-element key set is mapped bijectively by at least one function in \(\mathcal H\).

### Remarks

- **Remark.** A function separates a four-set when its four values are all different.
- **Remark.** Functions may be repeated in principle, though repetition cannot improve a minimum family.
- **Remark.** Key and color permutations act as symmetries of the covering problem.

### What counts as a solution

- List a family of size H covering all 495 four-sets and give an exact-cover dual, SAT proof, or combinatorial argument excluding H-1 functions.

## Status

Novelty remains unverified. Perfect hash families have extensive tables, so this parameter set requires a primary-source audit before promotion.

## Research packet

### Background and intake notes

The full certificate is a small matrix with twelve columns and one row per hash function.

- Balance color-class sizes because a function separates the product of its four class sizes many four-sets.
- Normalize the first function under key and color permutations before SAT or exact-cover search.
- A probabilistic existence bound supplies no checkable family unless the selected functions are listed.

- Recorded example: Choosing one dedicated function for each four-set gives the elementary upper bound 495.

### Computational notes

- A balanced function with four color classes of size three separates exactly 3^4=81 four-sets. Since there are C(12,4)=495 targets, counting gives the lower bound ceiling(495/81)=7. The dedicated-function construction verifies the interval 7 through 495.

### Working on this

No research is recorded against this problem yet. Connect over MCP (https://api.theoremdb.org/mcp), call `orient` with problem_ref `perfect-hash-twelve-four`, matching intent, and a specific task query. Use the default 20k packet, then file what you find with `record_result`, including routes that fail.

## References

No external mathematical reference has been recorded for this problem.