Case study / Lean 4 / Datalog / Quantum information
Mapping the exact algebraic graph of Mutually Unbiased Bases in dimension six
We built a three-layer, CI-verified Graphenium showcase for the dimension-six MUB
problem: exact coordinates, an embedded Datalog clique checker, and a Mathlib-free
Lean 4 certificate with zero sorrys.
TL;DR
The short version
- The Fourier pair {I6, F6} has exactly 48 vectors unbiased to both. They form 16 orthonormal bases, and no two of those bases are mutually unbiased.
- Tao's spectral matrix S6 has exactly 90 vectors unbiased to both. No two of those 90 vectors are orthogonal, so the pair cannot even be extended to a third basis.
-
The S6 orthogonality graph is computed in exact integer arithmetic in
Z[sqrt(5), i*sqrt(3), i*sqrt(15)], scaled by 8. The F6 graph is computed in double precision with a certified separation margin. -
Graphenium's embedded Datalog engine finds the 16 F6 bases and checks
every
K6,6MUB pair. No Souffle installation is required. -
The Mathlib-free Lean core checks 8,100 exact inner products, the 16
base certificates, and the absence of an F6 MUB pair, with no
sorryand nonative_decide. -
The C exhaustive search independently confirms exactly 48 Bjorck
biunimodular sequences.
make verifyruns Python, C, Graphenium, and Lean in sequence in CI. - The honest boundary: the completeness of the 48-vector and 90-vector sets is the published input. The showcase verifies the exact coordinates, the graph construction, the clique enumeration, and the combinatorial obstruction.
1 / The setup
The mathematical bottleneck
In quantum mechanics, two measurement bases are mutually unbiased if
measuring a state in one basis leaves no information about the other. In dimension
d, the maximum number of pairwise MUBs is d + 1 when
d is a prime power. Dimension six (d = 2 x 3) is the smallest
open case.
To rule out a fourth MUB for a pair such as {I6, F6}, you must find every vector unbiased to the pair, group the vectors into orthogonal 6-cliques (third bases), and then prove that no two of those cliques are completely joined in the MUB relation. The same reduction applies to Tao's {I6, S6} pair, where the obstruction is even stronger: there is not even an orthogonal pair among the 90 candidates.
2 / The exact data
Two finite obstructions
| Data set | Vectors | Orthogonal pairs | MUB pairs | 6-cliques | MUB pairs between bases |
|---|---|---|---|---|---|
F6 | 48 | 300 | 144 | 16 | 0 |
Tao S6 | 90 | 0 | 1125 | 0 | 0 |
For F6, every vector is exactly unbiased to I6 and F6.
The graph is computed in double precision with a certified margin: every non-edge is at
least 0.4307... away from both thresholds 0 and 6,
and every edge is within 9.8e-15 of its threshold.
For S6, the orthogonality graph is computed in exact integer arithmetic and is empty. A third basis would require six mutually orthogonal vectors from the 90-vector set, so the pair cannot be extended.
Three corrections that made the data exact
- The U9 table had two sign errors. The two entries involving
omega^2 betaandomega^2 beta-barhad the wrongi sqrt(15)sign. With the uncorrected table the seed vectors do not have unit-modulus entries. - The S6 representative must be row-permuted. The supplied 90 seeds are
unbiased to the row permutation
P = (0,1,2,5,4,3)of the standard S6 representative. The matrixP S6is Hadamard-equivalent to S6; any of the 60 equivalent working row orders gives the same obstruction. - The F6 vectors are not in the original r± alphabet. That alphabet
produces only 12 of the 48 vectors. The complete set is the Bjorck biunimodular set over
{d^m zeta^k}with-2 <= m <= 2and0 <= k < 12. The exhaustive C search included in the repository reports exactly 48 solutions.
S6: exact integer arithmetic in Z[sqrt(5), i*sqrt(3), i*sqrt(15)]
U9 = {1, omega, omega^2} x {1, beta, beta-bar}
beta = (1 + i*sqrt(15)) / 4
F6: Bjorck biunimodular alphabet
d = (1 - sqrt(3))/2 + i*sqrt(sqrt(3)/2)
zeta = exp(2*pi*i/12)
non-edge margin 0.4307... / edge error 9.8e-15 3 / The Lean certificate
Finite graph checks in the kernel
The core Lean build is deliberately Mathlib-free. Algebra.lean checks,
by pure kernel decide, that all 90 S6 vectors have unit entries, that all
540 inner products with S6 have squared modulus exactly 6 after scaling, and that no
two of the 90 S6 vectors are orthogonal. That last check is an 8,100-fold kernel
computation, not a mask lookup.
MasterProof.lean then checks the graph certificates: the S6 orthogonality
mask cross-check is identically zero, the 16 F6 bases are six-element cliques with
distinct vertices, and no two of those bases are completely joined in the MUB relation.
The compiled core depends only on propext (and Quot.sound
where needed), not on sorryAx and not on
Lean.ofReduceBool from native_decide.
$ cd lean4 && lake build
✔ [2/6] Built MUB6.Certificates
✔ [3/6] Built MUB6.Algebra
✔ [4/6] Built MUB6.MasterProof
✔ [5/6] Built MUB6
Build completed successfully (6 jobs). Eisenstein.lean is separate. It uses Mathlib for
nlinarith, interval_cases, and norm_num, and
proves the arithmetic lemma a^2 - a*b + b^2 != 6 together with the finite
residue check in ZMod 4.
4 / The topological graph
Orchestrating the obstruction with embedded Datalog
Asking an agent to find cliques in a dense 90-node graph by reading raw files is a context-collapse problem. The showcase instead compiles the adjacency facts into a small Graphenium graph and lets the engine enumerate the combinatorial structure.
Graphenium's EDB exposes calls, imports, and
contains. The bridge maps orthogonality to calls, mutual
unbiasedness to imports, and the canonical order i < j
to contains. Interleaving the order atoms with the adjacency atoms keeps
every partial clique in increasing vertex order, so the join stays small.
clique6(A, B, C, D, E, F) :-
calls(A, B, _), calls(A, C, _), calls(B, C, _),
contains(A, B, _), contains(B, C, _),
calls(A, D, _), calls(B, D, _), calls(C, D, _),
contains(C, D, _),
calls(A, E, _), calls(B, E, _), calls(C, E, _), calls(D, E, _),
contains(D, E, _),
calls(A, F, _), calls(B, F, _), calls(C, F, _), calls(D, F, _), calls(E, F, _),
contains(E, F, _).
mub_clique_pair(A, B, C, D, E, F, G, H, I, J, K, L) :-
clique6(A, B, C, D, E, F),
clique6(G, H, I, J, K, L),
contains(A, G, _),
imports(A, G, _), imports(A, H, _), imports(A, I, _), imports(A, J, _), imports(A, K, _), imports(A, L, _),
imports(B, G, _), imports(B, H, _), imports(B, I, _), imports(B, J, _), imports(B, K, _), imports(B, L, _),
imports(C, G, _), imports(C, H, _), imports(C, I, _), imports(C, J, _), imports(C, K, _), imports(C, L, _),
imports(D, G, _), imports(D, H, _), imports(D, I, _), imports(D, J, _), imports(D, K, _), imports(D, L, _),
imports(E, G, _), imports(E, H, _), imports(E, I, _), imports(E, J, _), imports(E, K, _), imports(E, L, _),
imports(F, G, _), imports(F, H, _), imports(F, I, _), imports(F, J, _), imports(F, K, _), imports(F, L, _).
?- clique6(A, B, C, D, E, F),
mub_clique_pair(A, B, C, D, E, F, G, H, I, J, K, L). $ gm query "" --datalog "$(cat graphenium/mub_cliques.dl)" \
--graph graphenium-out/f6_graph.json
## Results for `clique6`
| # | Values |
| 1 | "v0", "v2", "v4", "v6", "v8", "v10" |
| 2 | "v0", "v7", "v12", "v27", "v36", "v43" |
...
| 16 | "v37", "v39", "v41", "v43", "v45", "v47" |
No Souffle binary is required. The generated graph and log files use relative paths,
and graphenium/verify_embedded.sh asserts that no developer-machine
absolute paths leak into the artifacts.
5 / Indexing the showcase
The showcase indexes itself cleanly
Running Graphenium on the MUB-6 repository itself gives a small, clean structural index. It covers the Python generator, the C search tool, the Graphenium bridge and Datalog program, the Lean core, and the CI wiring.
| Metric | Value |
|---|---|
| AST symbols | 91 nodes |
| Structural boundaries | 172 edges |
| Communities | 6 |
| Import resolution | 16 / 16 (100%) |
| Ambiguous edges | 0 |
| Trust check | PASS |
$ make verify
[MUB-6] F6: 16 bases, 0 MUB pairs between bases
[MUB-6] S6: 0 bases, 0 orthogonal pairs, 0 MUB pairs
[MUB-6] path sanitation check passed
Build completed successfully (6 jobs).
All MUB-6 verification layers passed. 6 / Reproduce
One command, four layers
The repository's Makefile runs the Python generator, the exhaustive C
search, Graphenium's embedded Datalog verification, and the Lean core build in
sequence. The GitHub Actions workflow runs the same command on a fresh Ubuntu runner.
git clone https://github.com/lambda-alpha-labs/MUB-6
cd MUB-6
make verify
# Individual layers
python3 python/generate_facts.py
make c-search
make datalog
make lean
The Datalog layer needs gm on PATH; set
GM=/path/to/gm to override it. The Lean layer uses the pinned
lean-toolchain and is Mathlib-free by default.
7 / What this demonstrates
Exact algebra, graph topology, and kernel checks
- Exact arithmetic is practical. The S6 layer uses exact integer
arithmetic in
Z[sqrt(5), i*sqrt(3), i*sqrt(15)], scaled by 8, not a floating-point approximation. - Finite graph certificates can be kernel-checked. Lean verifies the
combinatorial obstruction without
native_decide. - Graphenium's embedded Datalog is real. The clique program runs in
gm, not an external dependency, and the bridge keeps generated artifacts portable. - CI can check the whole stack. Python, C, Graphenium, and Lean all
run from one
make verifyon a fresh Ubuntu runner.
From algebraic coordinates to a kernel certificate
Run the exact MUB-6 showcase end to end.
Clone the repository, run make verify, and watch the Python generator,
C exhaustive search, Graphenium Datalog layer, and Lean 4 core build in sequence.
Prefer email? hello@graphenium.dev