Unextendible product bases of Pauli eigenstates: an orthogonality layer over total domination in K_q^(× n)
Abstract
Call a set S ⊆ [q]ⁿ of words unextendible if every word of [q]ⁿ disagrees with some member of S in every coordinate. The minimum size of such a set carries two names in two literatures that do not cite each other: it is the minimum skirting set f(n,q) of Adriaensen, Ihringer, Martin and Villagrán, and it is the total domination number γₜ(K_(q)^(× n)) of the direct power of a complete graph, studied since Mekiš through Defant–Iyer and Vemuri. Reading the six letters of [6] as the six single-qubit Pauli eigenstates turns a word into a stabilizer product state, and a pairwise orthogonal unextendible set into an unextendible product basis. Neither literature imposes orthogonality, and the unextendible-product-basis literature never fixes the local alphabet; this paper works at that intersection. We prove that the minimum size s_(stab)(5) of a Pauli-eigenstate unextendible product basis on five qubits is exactly 6, attained by an explicit six-state example in which every one of the six letters occurs exactly once at every coordinate — it is the GenShifts basis of DiVincenzo, Mor, Shor, Smolin and Terhal with its two free local bases taken to be the X- and Y-eigenbases, and five is the largest number of qubits at which that specialisation is available — and we prove 9 ≤ γₜ(K₆^(× 6)) ≤ 10, whose upper half improves the published bound f(q,q) ≤ 2q-1 at q=6. Along the way we record, with their sources, the covering bounds that are already in print, give a short self-contained proof of γₜ(K_(q)^(× n)) ≥ n+3 for 4 ≤ q ≤ n (a bound implied by two published theorems), and separate s_(stab)(n) from the unrestricted qubit minimum f(n) for every n ≥ 6 not divisible by 4. Every combinatorial statement below is machine-checked in Lean 4.
Open review
This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.
Archived files
- Version 1 · current (opens in a new tab)
Source snapshot 2026-08-30 15:34 UTC
File fingerprint
bb2fb24c1007ad687d503858139ded5fa5f63d4beecfc05ed08c735545022e30
Claim ledger
Stated results
SU1known2026-08-30
The catch lemma at |K| coordinates, and the trivial bound n < |S| for an unextendible set of words in [q]ⁿ (gammaₜ(K_q^(x n)) >= n+1)
SU2known2026-08-30
Block bound: every block has at most |S| - n words, hence q*n <= (q-1)*|S|; and at |S| = n+1 the letters at each coordinate are distinct, so nothing of size n+1 is unextendible once n >= q
SU3known2026-08-30
Volume bound qⁿ <= |S|*(q-1)ⁿ, and sub-multiplicativity: concatenating unextendible sets on n and m coordinates gives one on n+m of at most the product size
SU4routine2026-08-30
gammaₜ(K_q^(x n)) >= n + 3 whenever 4 <= q <= n, by a direct self-contained argument; sharp at q = n = 4, where gammaₜ(K₄^(x 4)) = 7 with both halves kernel-checked
SU5known2026-08-30
sₛtab(3) = 4, attained by the Shifts UPB, which uses only the four real (X/Z) letters
SU6routine2026-08-30
sₛtab(4) = 6 while gammaₜ(K₆^(x 4)) = 5: on four qubits the Pauli-orthogonality requirement strictly costs one state over the pure covering minimum
SU7routine2026-08-30
sₛtab(5) = 6: an explicit six-state Pauli-eigenstate unextendible product basis on five qubits, using each of the six letters exactly once at every coordinate
SU8routine2026-08-30
Negative controls: both hypotheses of the n+3 theorem are load-bearing, five words do cover [6]⁴, every Shifts word is needed, and an orthogonal pair is extendible
SU9candidate2026-08-30
9 <= gammaₜ(K₆^(x 6)) <= 10, where the UPPER bound 10 is the new half – it improves the published f(q,q) <= 2q-1 = 11 at q = 6 – while the lower bound 9 is implied by Defant-Iyer + Vemuri (SU4) and is new here only as a formalization
SU10routine2026-08-30
For every even n there is no stabilizer UPB with exactly n+1 states, by an orthogonality count: distinct letters at each coordinate, and an anti-closed subset of the six letters has even size
SU11routine2026-08-30
sₛtab(n) >= n + 3 for every n >= 6, hence sₛtab(n) > f(n) for every n >= 6 that is not a multiple of 4
SU12routine2026-08-30
9 <= sₛtab(6) <= 12: concatenation preserves pairwise orthogonality as well as unextendibility, so sₛtab(a+b) <= sₛtab(a)*sₛtab(b)
Provenance
- Generated by
- Machina Mathematica
- Released by
- Korea Superintelligence Labs
- Source context
- Fix an alphabet of q letters and a length n. A finite set S ⊆ [q]ⁿ of words is unextendible when
- Snapshot
- 2026-09-07 03:53 UTC
- Ledger commit
801848d7