Intransitive Dice — minimizing the face count

Last updated: 2026-07-24

What this repo is about

A set of dice is n-player intransitive if, for every coalition of n−1 dice, some other die beats all of them (an (n−1)-paradoxical tournament). The fewest dice needed for 2, 3, 4, 5, 6, 7 players are 1, 3, 7, 19, 67, 331, 1163 (OEIS A362137).

Those dice can be built from the Paley tournament P(p) (p ≡ 3 mod 4 prime; die i beats die j iff (i − j) mod p is a quadratic residue), which is k-paradoxical for large enough p. The standard way to realize P(p) with dice is as the majority of F linear orders ("voters"): each die gets one face per order, offset so faces from different orders occupy disjoint value ranges, and then

bias(i, j) = Σ_t sign( order_t[i] − order_t[j] )

so die i beats die j exactly when a majority of the F orders rank i above j. Each die ends up with F faces.

The question this repo studies: how small can F be? F = faces per die is the quantity we minimize. The published realization (Bozóki 2014) uses F = p(p−1)/2 (e.g. 171 for p = 19); everything here does dramatically better, and for a few small primes we prove the exact minimum.

The recurring conjecture is that the minimum face count is the least odd number ≥ (p+1)/4.

Where things are

README.md / README_Chinese.md   ← this overview (EN / 中文)
FACE_COUNTS.md                   ← THE MAIN RESULT: per-prime best face counts + all constructions
RESEARCH_LOG.md                  ← chronological research log / session handoff (local, gitignored)
classification_by_prime.tsv      ← the face-count table as a spreadsheet-friendly TSV
LICENSE

gen_unified.py                   ← main generator: chain / Construction 6 / annealing "reduce"

best_results/                    ← the record dice sets, one file per order (see naming below)
  paley_<order>_<faces>.txt        one die per line, space-separated face values
  paley_0331_143.aut.txt           automorphism certificate for the P(331) domination proof

sat/                             ← SAT-based minimizer (smallest F for small p) + hybrids
  sat_paley_sb.py, sat_solve.py    rank encoding + column-permutation symmetry breaking
  hybrid.py, hybrid_bin.py         residual-SAT hybrid (bilevel head + SAT tail) for mid-size p
  README.md                        details + solver notes

bilevel/                         ← decomposition constructions (best for large p)
  bilevel_balanced.py, bilevel_lemma3.py, bilevel_naive.py   Erdős–Moser style bilevel cover
  multilevel.py                    transitive-subtournament decomposition — CURRENT large-p record
  gen_dice.py, verify.py, README.md

verify_script/                   ← independent verifiers
  verify_dice_set.py               enumerates every coalition (exact, for small p)
  verify_6player_domination.py     domination-number proof + automorphism certificate (large p)

visualization/                   ← self-contained HTML visualizations (open directly in a browser)
  multilevel_p19.html              the multi-level construction on P(19), layer by layer

old_work/                        ← superseded originals, kept for reference
  gen_intransitive_dice.py         the first 171-face-per-die 4-player generator
  gen_9face_4player.py             early annealing experiment
9face_4player.txt                ← example output (4-player, 9 faces)

best_results/ filenames are paley_<order>_<faces>.txt with the order zero-padded to 4 digits (paley_0019_5.txt, paley_0331_143.txt) so the directory sorts by prime.

The constructions (and which wins where)

Full details and the per-prime table are in FACE_COUNTS.md. In brief:

Method	Faces	Best for	Where
Construction 6 (Bednay–Bozóki)	p	universal fallback, any p ≡ 3 mod 4	gen_unified.py (default)
Chain	(p−1)/2	p ≡ 7 mod 8	gen_unified.py --chain
newbednay − 2 voters	(p−1)/2	p ≡ 3 mod 8 (except Heegner 67, 163)	sibling repo bb_direct.py + reduction
SAT	conjectured min ≈ (p+1)/4	small p (≤ ~103); proves minimality for p = 11	sat/
residual-SAT hybrid	between the above	mid-size p (e.g. 83→31, 103→45)	sat/hybrid.py
bilevel	Θ(p / log p)	large p crossover (523, 743, 991)	bilevel/bilevel_*.py
multi-level	current large-p record	331→143, 1163→393	bilevel/multilevel.py

Highlights: P(11) = 5 is proven minimal (d = 3, 4 UNSAT). P(67) = 17, P(19) = 5, P(59) = 15, etc. match the (p+1)/4 conjecture. The multi-level construction generalizes bilevel: instead of a bipartite A→B cover (which wastes the arcs inside A and inside B), it packs each layer with vertex-disjoint transitive subtournaments, covering all C(s,2) internal arcs of a size-s block at the same 2-voter cost — this set the current records for P(331) and P(1163).

Quickstart

Generate and verify a set for a given prime or player count:

# auto-pick the smallest prime with the fewest faces
python gen_unified.py --players 4                 # 23 dice × 11 faces (chain, p=23)
python gen_unified.py --players 3                 # 7 dice × 3 faces

# explicit prime
python gen_unified.py 19                          # Construction 6: 19 dice × 19 faces
python gen_unified.py 19 --reduce                 # anneal for the fewest faces (reaches 9; SAT proves 5)
python gen_unified.py 7  --chain                  # chain (needs p ≡ 7 mod 8)

Reproduce a large-p record with the multi-level construction:

cd bilevel
python multilevel.py 331 40 --save                # → best_results/paley_0331_143.txt (143 faces)
python multilevel.py 1163 40 --save               # → 393 faces

Search for the minimum face count on a small prime with SAT (see sat/README.md):

cd sat
python sat_paley_sb.py 19                          # finds 5 faces for P(19)

Verifying a dice set

For small p, enumerate every coalition directly:

python verify_script/verify_dice_set.py 5 <dice_file>
# VALID 5-player intransitive dice set. (checks all C(p, 4) coalitions)

For large p the C(p, n−1) enumeration is infeasible (C(331,5) ≈ 3.3×10⁹), so verify the equivalent domination-number condition — a set is a valid n-player set iff its dominance tournament has domination number ≥ n (no dominating set of size n−1) — with an O(n²)-checked automorphism certificate that makes the proof both fast and rigorous:

python verify_script/verify_6player_domination.py \
    best_results/paley_0331_143.txt best_results/paley_0331_143.aut.txt

Relation to the literature

The Paley tournament P(p) is k-paradoxical for large p (Graham & Spencer, A constructive solution to a tournament problem, Canad. Math. Bull. 14, 1971). Bozóki (Nontransitive dice sets realizing the Paley tournaments, Miskolc Math. Notes 15, 2014) gives an explicit set with p(p−1)/2 faces and equal face-sums. Bednay & Bozóki, Constructions for nontransitive dice sets (Proc. 8th Japanese–Hungarian Symposium, 2013), push below that. The constructions here use far fewer faces (at the cost of unequal sums and smaller winning margins); minimality is claimed only where the SAT lower bound matches (currently p = 11).