Back to Graphenium

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.

Repository: lambda-alpha-labs/MUB-6 Lean v4.34.0-rc2 Showcase commit: 5ea55e8 Pipeline time: ~60 seconds
48 exact F6 vectors
90 exact S6 vectors
16 F6 bases found
0 MUB pairs between them

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,6 MUB 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 sorry and no native_decide.
  • The C exhaustive search independently confirms exactly 48 Bjorck biunimodular sequences. make verify runs 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

Exact vector and graph counts for F6 and Tao S6
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

  1. The U9 table had two sign errors. The two entries involving omega^2 beta and omega^2 beta-bar had the wrong i sqrt(15) sign. With the uncorrected table the seed vectors do not have unit-modulus entries.
  2. 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 matrix P S6 is Hadamard-equivalent to S6; any of the 60 equivalent working row orders gives the same obstruction.
  3. 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 <= 2 and 0 <= k < 12. The exhaustive C search included in the repository reports exactly 48 solutions.
Exact arithmetic the two coordinate systems
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.

Lean 4 / build Mathlib-free core
$ 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.

Graphenium Datalog graphenium/mub_cliques.dl
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 F6 result
$ 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.

Graphenium index metrics for the MUB-6 repository
Metric Value
AST symbols 91 nodes
Structural boundaries 172 edges
Communities 6
Import resolution 16 / 16 (100%)
Ambiguous edges 0
Trust check PASS
gm check trust gate
$ 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.

Terminal end to end
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 verify on 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