editors: nobody
HADAMARD MATRICES OF ORDER SIX AND MUTUALLY UNBIASED BASES
==========================================================
Two exact theorems
ABSTRACT
--------
We prove two theorems about complex Hadamard matrices of size 6x6.
(1) Fourier vanishing. Every 6x6 complex Hadamard matrix that is not
equivalent to Tao's cubic example T (via row/column permutation
and rescaling of individual rows and columns) has
g_H(pi alpha) = 0
at every coordinate permutation pi of alpha = (1,1,1,-1,-1,-1).
(2) No complete family. In C^6 there do not exist seven mutually
unbiased bases. Combined with Weiner's completion theorem this
gives the upper bound N(6) <= 5.
Both proofs are finite and exact: every identity used is verified
with integer or rational arithmetic. The full verifier is described
in Section 9.
The central object of both theorems is the character sum
g_H(a) = (1/6) * sum_{k=0}^5 prod_{i=0}^5 H(i,k)^(a_i),
defined for balanced integer vectors a with sum a_i = 0.
1. HADAMARD MATRICES
====================
A complex Hadamard matrix of order d is a dxd matrix H whose entries
all lie on the unit circle in C (|H(i,j)| = 1) and whose columns are
mutually orthogonal:
H* H = dI.
Throughout d = 6.
Example (order 2): H = [[ 1, 1], [ 1, -1]].
Example (order 3, from the cube root omega = exp(2 pi i / 3)):
T_3 = [[1, 1, 1 ],
[1, w, w^2 ],
[1, w^2, w ]]
Fix omega = exp(2 pi i / 3). The cubic matrix T of order 6 is the
6x6 matrix T = (omega^(t_ij)) whose integer exponents t_ij are
t_ij = 0 if i = 0 or j = 0 or i = j,
t_ij = 1 if i, j in {1,2,3,4,5} and i - j = +/- 1 (mod 5),
t_ij = -1 otherwise.
Explicitly, with w = omega:
col 0 col 1 col 2 col 3 col 4 col 5
+-------------------------------------------
row 0| 1 1 1 1 1 1
row 1| 1 1 w w^2 w^2 w
row 2| 1 w 1 w w^2 w^2
row 3| 1 w^2 w 1 w w^2
row 4| 1 w^2 w^2 w 1 w
row 5| 1 w w^2 w^2 w 1
The five noninitial rows (and columns) form a cycle 1-2-3-4-5-1 with
+1 exponents on cycle edges and -1 on non-edges. Direct checking
gives T T* = 6I and also T^{circ 2} (T^{circ 2})* = 6I: the
entrywise square of T is conj(T), and conj(T) is again Hadamard
because it has the same rows in the same order.
Two Hadamard matrices H, H' are equivalent if one may be obtained
from the other by
(a) permuting rows,
(b) permuting columns,
(c) multiplying each row by a unit complex number,
(d) multiplying each column by a unit complex number.
2. MUTUALLY UNBIASED BASES
==========================
Two orthonormal bases b_0,...,b_{d-1} and c_0,...,c_{d-1} of C^d
are mutually unbiased (MUB) if every inner product has the same small
modulus:
|<b_i, c_j>|^2 = 1/d for all i, j.
A pairwise-MUB family in C^d has at most d + 1 members. For
prime-power d a complete family of d + 1 exists (Wootters-Fields,
1989). Weiner's completion theorem (2013) says any family of m < d+1
MUBs extends to a complete one. So finding the maximum size N(d)
reduces to the question: does a complete family exist?
For d = 6, Theorem 2 says: no complete family, hence N(6) <= 5. A
companion paper reaches N(6) = 3 by a longer computer-aided argument;
we establish only the clean upper bound N(6) <= 5.
Fix a reference basis B_r. Every other basis B_s in the family gives
a dxd transition matrix
H_rs(i, k) = sqrt(d) * <b_{r,i}, b_{s,k}>.
Unbiasedness gives |sqrt(d) * <inner product>| = 1, so H_rs has
entries on the unit circle. Orthonormality of B_r and B_s gives
orthogonal rows and orthogonal columns. So H_rs is Hadamard. Also
H_sr = H_rs^* (conjugating inner products swaps the two bases).
3. NOTATION AND CHARACTER SUMS
==============================
Fix a 6x6 Hadamard matrix H.
Coordinates: e_0, ..., e_5 is the standard basis of C^6.
Charge: an integer vector a = (a_0, ..., a_5) in Z^6 with sum a_i = 0.
Order: ord(a) = sum of the positive entries of a.
Character sum:
g_H(a) = (1/6) * sum_{k=0}^5 prod_{i=0}^5 H(i,k)^(a_i).
Exponents: entries have modulus 1, so H(i,k)^m is defined for any
integer m: the usual power for m >= 0, and conj(H(i,k))^{|m|} for
m < 0.
Special charge: alpha = (1, 1, 1, -1, -1, -1).
Difference charges: D = {e_i - e_j : i != j}.
Five elementary facts about g_H, each from the definition:
(1) g_H(0) = 1. (Empty product = 1; averaging 1.)
(2) |g_H(a)| <= 1. (Average of six unit-modulus complex numbers.)
(3) g_H(-a) = conj(g_H(a)). (Conjugating the whole expression.)
(4) Column phases do not affect g_H. Replacing column k by
exp(i theta_k) * column k multiplies the k-th term by
exp(i theta_k * sum_i a_i) = 1. This is why the charge must be
balanced.
(5) Row phases multiply g_H by a unit. Replacing row i by
u_i * row i (|u_i| = 1) multiplies g_H(a) by
u^a = prod_i u_i^(a_i). Hence |g_H| is invariant under row
phases.
(6) For i != j, g_H(e_i - e_j) = 0. Indeed
g_H(e_i - e_j) = (1/6) sum_k H(i,k) * conj(H(j,k))
= (1/6) (row i) . conj(row j)
= delta_ij.
Coordinate permutations: for a permutation pi of {0,...,5}, write
(pi a)_i = a_{pi(i)}. The statement g_H(pi alpha) = 0 for all pi is
equivalent to saying g_{H^pi}(alpha) = 0 for all pi, where H^pi is H
with its rows permuted by pi.
4. THE DICHOTOMY FOR A SINGLE HADAMARD MATRIX
=============================================
Fix a 6x6 Hadamard matrix H. Write H^pi for the row permutation
H^pi(i, k) = H(pi(i), k). We will prove:
DICHOTOMY. At least one of the following holds:
(M) g_{H^pi}(alpha) = 0 for every coordinate permutation pi.
(C) the entrywise square H^{circ 2} is a Hadamard matrix.
Case (M) is the assertion of Theorem 1 in its positive form. Case (C)
leads (in Section 5) to the cubic exceptional case. The proof of the
dichotomy uses only orthogonality and unimodularity of H.
The strategy is the standard "sum of nonnegative terms equals zero"
argument. We build one auxiliary function L_H of H whose weighted
average squared modulus plus another nonnegative term evaluates,
exactly, to zero. Each summand is then individually zero, which
forces the dichotomy.
4.1 INJECTIVE MOMENTS
---------------------
An exponent matrix of size p x q (with p, q <= 6) is an integer
matrix A = (A_uv) whose row sums and column sums all vanish.
Its injective moment:
m_H(A) = E[ Re( prod_{u=0}^{p-1} prod_{v=0}^{q-1}
K( rho(u), kappa(v) )^{A_uv} ) ],
where the expectation is over three independent uniform choices:
- K is H (prob 1/2) or H^T (prob 1/2);
- rho: {0,...,p-1} -> {0,...,5} is a uniform injection;
- kappa: {0,...,q-1} -> {0,...,5} is a uniform injection.
The transpose H^T is also Hadamard, since H H^* = 6I transposed
gives H^T (H^T)^* = 6I.
For the empty exponent matrix, m_H(varnothing) = 1.
Basic properties, all from the definitions:
|m_H(A)| <= 1 (average of unit modulus complex numbers)
m_H(A) is unchanged by:
- row permutation of A,
- column permutation of A,
- global negation A -> -A,
- transposition A -> A^T,
- deleting any zero row or zero column.
The four symmetries follow from: renaming rho / kappa, conjugating the
whole product, swapping rho with kappa and H with H^T respectively.
A zero row or column contributes a factor of 1 and can be deleted.
4.2 CONTRACTING AN ORDER-ONE ROW
--------------------------------
Let A be a balanced exponent matrix with p rows and q <= 6 columns.
Suppose row i of A has order 1: that is, row i is +1 in one column
(v_+) and -1 in another column (v_-), and zero elsewhere.
The contracted matrix A_{i -> l} (for l != i) is formed by:
- adding row i to row l;
- deleting row i.
It still has zero row and column sums, so it is again an exponent
matrix, this time with p-1 rows.
CONTRACTION LEMMA. Under the above setup:
if p <= 6: (7 - p) * m_H(A) = - sum_{l != i} m_H( A_{i->l} );
if p = 7: 0 = sum_{l != i} m_H( A_{i->l} ).
Proof. Fix K, kappa, and the row assignments of every row except i.
Let M be the product of those rows' factors. Row i's factor is
K(t, kappa(v_+)) * conj(K(t, kappa(v_-))) for the sampled row index t.
Summing over t:
sum_t K(t, kappa(v_+)) * conj(K(t, kappa(v_-))) = 0
by column orthogonality (columns kappa(v_+) and kappa(v_-) are
distinct because kappa is injective). So M times this sum is zero.
For p <= 6, there are 7 - p labels not yet used for row i, so summing
over these and averaging gives a factor (7 - p) times the conditional
mean of M. Averaging over K and kappa and taking real parts gives the
p <= 6 relation. For p = 7, all six other rows already use all six
labels; no averaging is needed and we get the p = 7 relation.
Repeatedly applying this lemma contracts any moment with both
dimensions at most six into a rational linear combination of the
empty moment and moments whose nonzero rows and columns all have
order at least 2. Each contraction reduces the total row count, so
the procedure terminates.
4.3 EQUALITY-PATTERN EXPANSION
------------------------------
Define the pair average over orientations and row permutations:
<F(H~)>_H = (1 / (2 * 6!)) *
sum_{K in {H, H^T}} sum_{pi in S_6} F(K^pi).
Column permutations do not appear because g is invariant under them.
EQUALITY-PATTERN LEMMA. Let a_1, ..., a_n be balanced charges with
sum_{j=1}^n a_j = 0. Form the n-column matrix A = [a_1 | ... | a_n].
For each set partition S of {1,...,n} with at most six blocks, form
A_S by replacing each block's columns with their sum. Then
< Re( prod_j g_H~(a_j) ) >_H
= sum_{S : |S| <= 6} (6)_{|S|} / 6^n * m_H(A_S),
where (6)_k = 6 * 5 * ... * (6 - k + 1) is the falling factorial.
Proof. Expand the product as an average over n independent uniformly
sampled columns of the underlying matrix. Group the resulting 6^n
terms by which sample positions land in the same column (an equality
pattern, i.e. a set partition). For a specified partition with k
blocks, the block labels take (6)_k distinct injective values, each
with weight 6^{-n}. On that set, the exponents of positions in the
same block add. Summing gives m_H(A_S).
Simple example (n = 2, charges a and -a):
< |g_H~(a)|^2 >_H = 1/6 + 5/6 * m_H([a | -a]).
The "1/6" is the partition into 1 block (A_S is a single zero column,
giving m_H = 1); the "5/6" comes from the partition into 2 blocks.
4.4 THE AUXILIARY FUNCTION L_H
------------------------------
Let
w = (-3, -2, 0, 1, 2, 2),
a_1 = (-1, -1, 0, 0, 1, 1),
a_2 = (-2, 0, 0, 0, 1, 1),
a_3 = (-1, -1, 0, 1, 0, 1),
a_4 = (-1, -1, 0, 1, 1, 0).
All are balanced. Each w - a_j is balanced too. Define
L_H = - g_H(w) + 2 g_H(a_1) g_H(w - a_1)
+ 1 g_H(a_2) g_H(w - a_2)
+ 1 g_H(a_3) g_H(w - a_3)
+ 1 g_H(a_4) g_H(w - a_4).
Every term on the right has total charge w (the a_j's cancel against
w - a_j).
The two probe charges:
q_cross = ( 2, 0, 0, -2, 0, 0) = 2(e_0 - e_3),
q_same = ( 2, -2, 0, 0, 0, 0) = 2(e_0 - e_1).
Both are balanced with order two. The names refer to how they
interact with alpha: q_cross has its +1 entry among the first three
positions of alpha and its -1 among the last three, whereas q_same
puts both entries in the same triple. Section 4.6 exploits this.
4.5 THE EXACT SPRINGBOARD IDENTITY
----------------------------------
CERTIFICATE PROPOSITION. For every 6x6 Hadamard matrix H and every
q in { q_cross, q_same }:
3 < |L_H~|^2 >_H + < |g_H~(alpha) g_H~(q)|^2 >_H = 0.
Both averages are over H~ drawn uniformly from {H, H^T} and then over
a uniform row permutation. Both terms are averages of nonnegative
real quantities.
The proof is an exact algebraic computation, carried out with
rational coefficients only:
Step 1. Expand both absolute squares. Each monomial becomes a
product of at most four character sums. Apply the
equality-pattern lemma to reduce each piece to a linear
combination of injective moments.
Step 2. Apply the contraction lemma repeatedly to zero out
every order-one row and column. All resulting moments
have every nonzero row and column of order at least 2.
Step 3. Use the seven-row homogeneous case of the contraction
lemma (the p = 7 relation, specific to a Hadamard matrix
of order six) to write additional relations among the
six-row moments.
Step 4. Verify in exact arithmetic that the resulting linear
combination is identically zero, for each value of q.
The full finite computation is described in Section 9.
4.6 FROM THE IDENTITY TO THE DICHOTOMY
--------------------------------------
Both terms in the certificate are averages of nonnegative real
quantities. Their sum is zero, so every summand is zero for every
choice of H~ in {H, H^T} and every choice of row permutation. That
is, for every coordinate permutation pi:
g_{H^pi}( alpha ) * g_{H^pi}( q_cross ) = 0,
g_{H^pi}( alpha ) * g_{H^pi}( q_same ) = 0.
Suppose (M) fails, i.e. g_{H^{pi0}}(alpha) != 0 for some pi0. Fix
one such pi0. Write I_+ = { pi0(0), pi0(1), pi0(2) } (the three
rows of H carrying alpha's +1 positions) and I_- = { pi0(3), pi0(4),
pi0(5) } (the three rows carrying alpha's -1 positions).
Claim: any other permutation pi with pi({0,1,2}) = I_+ and
pi({3,4,5}) = I_- has g_{H^pi}(alpha) = g_{H^{pi0}}(alpha) != 0.
(Because rearranging rows within I_+ leaves the product
H(pi(0),k) H(pi(1),k) H(pi(2),k) unchanged: three +1 contributions
to the same k-column.) Hence g_{H^pi}(q_cross) = g_{H^pi}(q_same)
= 0.
Now let i, j be any two distinct row labels of H.
Case i, j both in I_+. Choose pi with pi(0) = i, pi(1) = j.
Then g_{H^pi}(q_same) = (1/6) sum_k H(i,k)^2 conj(H(j,k))^2 =
g_H(2(e_i - e_j)). Vanishing gives g_H(2(e_i - e_j)) = 0.
Case i, j both in I_-. Same trick using q_same; the sign is
absorbed using g_H(-a) = conj(g_H(a)).
Case i in I_+, j in I_-. Choose pi with pi(0) = i and pi(3) = j.
Then g_{H^pi}(q_cross) = g_H(2(e_i - e_j)). Same conclusion.
Case i in I_-, j in I_+. Use q_cross with the opposite charge,
then conjugate.
So for all i != j:
g_H( 2(e_i - e_j) ) = 0.
Now g_H( 2(e_i - e_j) ) = (1/6) sum_k H(i,k)^2 conj(H(j,k))^2.
Setting N = H^{circ 2} (entrywise square), this says
(1/6) * (row i of N) . conj(row j of N) = 0 for i != j.
So N N^* = 6 I. For a square matrix N, NN^* = 6I implies N^*N = 6I
automatically (both follow from N / sqrt(6) being unitary). So the
columns of N also have squared norm 6 and are orthogonal. Since the
entries of N are squares of unit modulus complex numbers, N is
Hadamard. This is case (C).
5. CLASSIFYING THE CUBIC ALTERNATIVE
====================================
Now assume both H and H^{circ 2} are Hadamard matrices. We show that H
must be equivalent to the cubic matrix T. This proves a conjecture of
Phangara and also confirms the Matolcsi-Ruzsa-Weiner Fourier-vanishing
conjecture in the exceptional cubic case.
PROPOSITION 5.1 (Cubic classification). Suppose H is a 6x6 Hadamard
matrix and H^{circ 2} is also Hadamard. Then H is equivalent (by
row/column permutations and row/column phase multiplications) to T,
and every entry of a dephased H is a cube root of unity.
Dephasing means multiplying rows and columns by phases so that the
first row and the first column are all ones. Every Hadamard matrix
can be dephased, and the operations preserve both Hadamard conditions.
5.1 ROW RATIOS FACTOR AS CUBES OF A QUADRATIC IN z^3
----------------------------------------------------
Fix two distinct rows r and r' of H. Define
v_k = H(r, k) / H(r', k) (k = 0, ..., 5).
The v_k are six unit complex numbers. Orthogonality of rows r and r'
of H gives
sum_k H(r,k) conj(H(r',k)) = 0,
equivalently sum_k v_k = 0 (dividing by |H(r',k)| = 1).
Orthogonality of the same two rows of H^{circ 2} (whose rows are the
entrywise squares of the rows of H) gives
sum_k v_k^2 = 0.
Let e_1, ..., e_6 be the elementary symmetric polynomials in
v_0, ..., v_5, so that prod_k (z - v_k) = z^6 - e_1 z^5 + e_2 z^4
- e_3 z^3 + e_4 z^2 - e_5 z + e_6. Newton's identities convert
p_1 = p_2 = 0 into e_1 = e_2 = 0. Since every v_k has modulus 1, the
coefficients satisfy the reciprocal-symmetry relation
e_{6-k} = e_6 * conj(e_k), hence e_4 = e_5 = 0 too. The polynomial
reduces to a quadratic in z^3:
prod_k (z - v_k) = z^6 - e_3 z^3 + e_6.
As a quadratic in w = z^3 it factors as (w - r_+)(w - r_-), so
{z^3 : z = v_k} is the union of two cyclic triples {a, a omega, a omega^2}
(possibly with repeated a). Therefore
the cube v_k^3 takes at most two distinct values among the six k.
The same argument applied to column ratios (using column orthogonality
of H and of H^{circ 2}) gives the same conclusion for column ratios.
5.2 DEPHASED ROWS OF H^{circ 3} ARE 1'S OR 3-AND-3
--------------------------------------------------
Dephase H. Both Hadamard conditions persist.
By Section 5.1, for any pair (r, r') of distinct rows, the row ratio
v_k = H(r,k)/H(r',k) is a union of two rotated cube-root triples
T_1 = {a, a*omega, a*omega^2} and T_2 = {b, b*omega, b*omega^2}
(each value appearing exactly once in v). Applying this to the fixed
pair (r, r' = 0) after dephasing: v_k = H(r,k) (since H(0,k) = 1),
and H(r,0) = 1 means 1 lies in T_1 union T_2. Relabel so a = 1 (or
b = 1); WLOG a = 1. Then T_1 = {1, omega, omega^2}.
So the six values of H(r,k) are 1, omega, omega^2 (each once) and
b, b*omega, b*omega^2 (each once, some unit b). Cubing entrywise:
H^{circ 3}(r, k) = 1 for the three columns in T_1, and
H^{circ 3}(r, k) = b^3 for the three columns in T_2.
If b = 1, then b^3 = 1 and the whole row of H^{circ 3} is 1.
Otherwise b^3 != 1 and the row of H^{circ 3} is three 1's and three
b^3's. So
every row of H^{circ 3} is either constant 1 or has exactly
three 1's and three entries equal to some x != 1.
Call the three positions with the value x != 1 the support of a
nonconstant row of H^{circ 3}. This support is a 3-element subset of
{0, ..., 5}. Since H(r, 0) = 1 (dephased), column 0 is in T_1, i.e.
the value at column 0 is 1 and therefore not in the support. So the
support lies in {1, ..., 5}.
5.3 ALL NONCONSTANT ROWS SHARE ONE SUPPORT
------------------------------------------
Suppose two nonconstant rows have different supports S and U, with
respective values x != 1 and y != 1. Because |S| = |U| = 3 and both
lie in the five noninitial columns, |S cap U| = k with k in {1, 2}.
The cubed row ratio (of the two rows of H) evaluated at each of the
six coordinates takes the following four values with the following
multiplicities (checking on S∖U, U∖S, S cap U, and the common
complement of S union U in {1,...,5}):
value multiplicity
1 k
x 3 - k
y^{-1} 3 - k
x y^{-1} k
All four multiplicities are positive. But by Section 5.1 the cubed
row ratio can take at most two distinct values. So two of the four
values coincide.
Forcing 1, x, y^{-1} all into a two-element set gives x = y^{-1}.
Forcing x y^{-1} = x^2 to coincide with 1 or x gives x = y = -1. But
then the four multiplicities are 2k and 6 - 2k, which cannot both be
3 (contradicting the 3 + 3 structure forced by Section 5.2).
Contradiction.
So all nonconstant rows share the same 3-element support. The same
argument with rows and columns interchanged shows all nonconstant
columns share a common 3-element support.
5.4 THE 3x3 BLOCK STRUCTURE AND ITS RULING-OUT
----------------------------------------------
If H^{circ 3} is all ones, every entry of H is a cube root of unity
and we skip to Section 5.5.
Otherwise, let S be the common support, consisting of three columns.
Exactly three rows are nonconstant (by the analogous common-support
statement for columns). Comparing their non-one values in any one
column of S shows that three rows have the same non-one value x.
Rearranging these two classes of rows and two classes of columns, the
entrywise cube has the block form
H^{circ 3} = [[ J_3 J_3 ],
[ J_3 x J_3 ]],
where J_3 is the all-ones 3x3 matrix and x != 1.
Restrict every row of H to the three columns of the x J_3 block. Each
restriction has squared norm 3 (since |H(i,j)| = 1). For a row i in
one class and a row j in the other, their ratio cubes to x or x^{-1}
on those three columns, and to 1 on the other three columns (by the
common-support property). The two counter-rotating triples of cube
roots in the ratio are therefore separated by this column split.
Their sums are zero, so the restrictions of rows from opposite
classes are mutually orthogonal.
Each class spans a subspace of dimension at least two on the three
columns. To see this: suppose one class spanned a line. Its three
restrictions have squared norm 3 each, so any pairwise inner product
has modulus 3. Orthogonality of the full rows forces their
complementary (three-column) restrictions likewise to have modulus-3
inner products. Equality in Cauchy-Schwarz then makes these
complementary restrictions proportional. The three full rows would
then live in a space of dimension at most two, contradicting their
orthogonality. So both classes span subspaces of dimension at least
two.
Two mutually orthogonal subspaces of C^3 cannot both have dimension
at least two. Contradiction. Therefore the 3x3 block structure cannot
occur, and combined with the all-ones case:
after dephasing, every entry of H is a cube root of unity.
5.5 THE PLUS PATTERN IS A FIVE-CYCLE
------------------------------------
In each noninitial row of the dephased H, the entries are cube roots
of unity. Orthogonality to the initial all-ones row gives one more
"1" than either w or w^2, so 2 each of 1, omega, omega^2. The
positions of the extra 1 in each noninitial row form a matching; by
relabelling columns we can place them on the diagonal. The other
four entries per row contain 2 omegas and 2 omega^2's:
H(i, j) in { omega, omega^2 } for i != j, i, j in {1, ..., 5}.
Write H(i,j) = omega^{s_ij} with s_ij in {+1, -1}. Each row i has
two +1's and two -1's among the four off-diagonal entries.
For two distinct noninitial rows i and j, their ratio contains each
cube root exactly twice (by Section 5.1). At column 0 they agree
(both = 1) and at columns i and j they disagree (one is omega,
the other omega^2 by the diagonal matching arrangement). Among the
remaining three columns they agree in exactly one. Summing exponents,
this forces
prod_{k not in {0, i, j}} s_ik * s_jk = 1,
and combined with the per-row relation prod_{k != i} s_ik = 1
(two +1's and two -1's) one deduces s_ij = s_ji. So the graph on
{1, ..., 5} with an edge (i,j) iff s_ij = +1 is a simple undirected
graph where each vertex has degree two. Such a graph on five vertices
is a disjoint union of cycles; the only way to have all degrees two
with total edge count 5 is a single five-cycle (since 3 + 3 + ... can
only sum to 5 as 5).
Rearranging noninitial rows and columns to match this five-cycle
gives exactly the matrix T from Section 1. This completes the
classification.
5.6 FOURIER VANISHING
---------------------
Theorem 1 follows directly from the dichotomy and Proposition 5.1:
PROOF OF THEOREM 1. Let H be any 6x6 Hadamard matrix. If some
permutation pi has g_{H^pi}(alpha) != 0, the dichotomy (Section 4)
forces H^{circ 2} to be Hadamard. Proposition 5.1 then makes H
equivalent to T. So if H is NOT equivalent to T, every permutation
has g_{H^pi}(alpha) = 0.
6. CHARACTER IDENTITIES OF A COMPLETE FAMILY
============================================
Assume now the exact opposite of Theorem 2: a complete set of seven
mutually unbiased bases B_1, ..., B_7 in C^6.
Choose a reference index r. Every other basis B_s (s != r) corresponds
to a Hadamard matrix
H_s(i, k) = sqrt(6) * <b_{r,i}, b_{s,k}> (s != r).
Write g_s(a) = g_{H_s}(a). The following identities are consequences
of mutual unbiasedness plus family completeness. They are what makes
the complete-family problem tractable.
BASIC LEMMA. For a complete family of seven MUBs, the character sums
satisfy:
(A) g_s(d) = 0 for every d in D. (Row orthogonality of H_s; already
elementary.)
(B) For every charge a of order two, sum_{s != r} g_s(a) = 0.
Intuition. The seven bases together form a complex
projective 2-design. The corresponding projector identity
(Zauner 1999; Klappenecker-Roetteler 2005) is
Tr(X Y) = sum_{s=1}^7 sum_{k=0}^5 Tr(X P_{s,k}) Tr(Y P_{s,k})
for all trace-zero X, Y, where P_{s,k} = b_{s,k} b_{s,k}^*.
Applying this with X, Y chosen off-diagonal in the reference
basis and each with one nontrivial entry: the reference-basis sum
is zero (X and Y traceless and diagonal in that basis give
Tr(X P_{r,k}) = 0). Each external basis contributes g_s(a) / 6,
and multiplying by 6 gives (B).
(C) For balanced charges a, b and any coordinate index i:
sum_{j=0}^5 g_s(a + e_i - e_j) g_s(b - e_i + e_j) = g_s(a+b).
This is a column-orthogonality relation on one matrix: expand
both g_s sums as averages over columns x and y, and note that
sum_{j=0}^5 (x/y)^{e_i-e_j}-type terms collapse to 6 delta_{x=y}.
(D) For distinct external bases s != t:
sum_{d in D} g_s(a + d) g_t(b - d) = 0.
This is a mutual-unbiasedness statement. For a fixed coupling,
each column x of H_s and column y of H_t have |<x,y>|^2 = 1/6,
equivalently |sum_i x_i / y_i|^2 = 6. Expanding the square:
sum_{d in D} (x/y)^d = |sum_i x_i / y_i|^2 - 6 = 0.
Multiplying by the appropriate factors of g_s(a) g_t(b) gives (D).
These identities hold for every H_s in a complete family. They are
the character-level form of the completeness constraints, and they
are the raw material for the cubic obstruction of Section 7 and the
positive-forms certificate of Section 8.
7. CUBIC MATRICES CANNOT SIT INSIDE SEVEN MUBS
=============================================
Fix a complete set of seven MUBs and let T be the cubic matrix from
Section 1. We show:
PROPOSITION 7.1. In a complete set of seven MUBs in C^6, no
transition matrix can have H_rs^{circ 2} Hadamard. In particular, no
H_rs can be equivalent to T.
The proof is a long exact computation using the character-sum
identities (A)-(D) of Section 6. It rules out the exceptional cubic
case for the family problem; Theorem 1 alone only rules T out for the
individual-matrix problem.
Suppose T does occur as some transition. By row/column permutation
and phase multiplications (which preserve mutual unbiasedness) we may
arrange the reference basis and its partner so that T is exactly the
transition matrix. Write G(b) = g_T(b). Pick one matrix per "other"
partner basis and average their character sums:
f(b) = (1/5) * sum_{s=1}^5 g_{K_s}(b),
where K_1, ..., K_5 are the five other transition matrices from the
reference basis. Then three facts hold:
(7.1a) Order one: f(b) = 0 and G(b) = 0 for ord(b) = 1.
(Both vanish by row orthogonality.)
(7.1b) Order two: f(b) = -(1/5) G(b) for ord(b) = 2.
(By identity (B): sum_{s != r} g_s(b) = 0 when ord(b) = 2.
Combined with G(b) = g_T(b), this is 5 f(b) + G(b) = 0.)
(7.1c) Cross: sum_{d in D} f(a+d) * conj( G(c+d) ) = 0
for any balanced a, c.
(Identity (D) applied with s = the T-index, averaged over
the five other t-indices, with f coming from the 1/5-weighted
average.)
Define the permutation-orbit average
S(b) = (1/6!) sum_{pi in S_6} Re( f(pi b) * conj( G(pi b) ) ).
Here pi runs over all coordinate permutations of {0,...,5}. Because
f(-b) = conj(f(b)) and G(-b) = conj(G(b)), S is the same if we
average over the orbit under signed coordinate permutations.
POSITIVITY. Let z be a uniformly random column of a uniformly random
K_s (s = 1..5). Then E(z^b) = f(b) for the resulting random variable
z^b = prod_i z_i^{b_i}. Consider
E[ | sum_i z_i^3 |^2 ]
= sum_{i,j} E[ z_i^3 conj(z_j^3) ]
= 6 + sum_{d in D} f(3 d)
= 6 + 30 * S( 3(e_5 - e_0) ).
The equality "= 6 + 30 S" uses that the signed permutation orbit of
3(e_5 - e_0) is exactly { 3 d : d in D } (six points) and the orbit
average is symmetric; summing over orbit representatives and using
the normalizing 1/6! gives the factor 30.
Since E|...|^2 >= 0, we must have
S( 3(e_5 - e_0) ) >= -1/5.
On the other hand, identities (7.1a)-(7.1c) will force this same
number to be -4/5. Contradiction. That is the strategy; the actual
computation is Section 7.2 below.
7.1 SYMMETRY OF THE CUBIC MATRIX
--------------------------------
For T from Section 1:
LEMMA 7.2. Every permutation of the rows of T can be completed to a
symmetry of T by column permutations, row/column phase factors, and
complex conjugation. Consequently |G(b)| is constant on every orbit of
balanced charges under coordinate permutations and negation.
Sketch of proof. A symmetry is a factorization T ~ (D_1 P_1) T (P_2 D_2)
or its complex conjugate, with P_i permutations and D_i diagonal
unitaries. Normalize the output row 0 to all ones; then the all-one
output row and column determine all the row and column phases up to
a common rescaling, which we fix by normalizing row 0's phase.
There are 36 choices of initial row/column, 2 choices of conjugation,
and 10 orders of the other rows that (together with the matching
column orders) make the plus-sign pattern a five-cycle. So 36 * 2 *
10 = 720 = 6! symmetry operations.
Distinctness: work with exponents modulo 3, and write t_j for column
j of the exponent matrix. A symmetry fixing the row order acts on
the set X = {t_0, ..., t_5} as X -> sX + u with s in {+1, -1} and u
in X. Counting shows the only such symmetry is the identity after
phase normalization. The 720 operations are therefore distinct
row-permutation classes; since there are 720 row permutations, they
exhaust them.
For a balanced charge, column phases cancel in g, while row phases
multiply g by a unit. Conjugation conjugates g. So |G| is constant on
orbits under the symmetry group described above.
7.2 EXPLICIT COEFFICIENT COMPUTATION
------------------------------------
Only charges of order at most three are needed. Up to coordinate
permutation and negation, there are exactly eleven of them:
w_0 .. w_10 =
(-3, 0, 0, 0, 0, 3) (order 3, up to sign)
(-3, 0, 0, 0, 1, 2) (order 3, up to sign)
(-3, 0, 0, 1, 1, 1) (order 3, up to sign)
(-2,-1, 0, 0, 1, 2) (order 3)
(-2,-1, 0, 1, 1, 1) (order 3)
(-2, 0, 0, 0, 0, 2) (order 2, up to sign)
(-2, 0, 0, 0, 1, 1) (order 2)
(-1,-1,-1, 1, 1, 1) (order 3)
(-1,-1, 0, 0, 1, 1) (order 2)
(-1, 0, 0, 0, 0, 1) (order 1, up to sign)
( 0, 0, 0, 0, 0, 0) (order 0)
For each representative, both G(w_j) and a certain weighted
cross-coefficient R(w_j) (built from all cross identities with
(a, c) ranging over simultaneous permutations of (w_5, w_5) or
(w_8, w_8), see below) are rational combinations of cube roots of
unity with small denominators. Write
6 G(w_j) = N_0 + N_1 omega + N_2 omega^2 (N_i in Z)
72 R(w_j) = U_0 + U_1 omega + U_2 omega^2 (U_i in Z)
Then the integer triples are:
j w_j (N_0, N_1, N_2) (U_0, U_1, U_2)
-- ----------------------------- --------------- ----------------
0 (-3, 0, 0, 0, 0, 3) (6, 0, 0) (0, 0, 0)
1 (-3, 0, 0, 0, 1, 2) (2, 2, 2) (0, 0, 0)
2 (-3, 0, 0, 1, 1, 1) (3, 0, 3) (0, 0, 0)
3 (-2,-1, 0, 0, 1, 2) (4, 1, 1) (60, 42, 42)
4 (-2,-1, 0, 1, 1, 1) (2, 2, 2) (144,144, 144)
5 (-2, 0, 0, 0, 0, 2) (2, 2, 2) (0, 0, 0)
6 (-2, 0, 0, 0, 1, 1) (3, 3, 0) (180,180, 72)
7 (-1,-1,-1, 1, 1, 1) (3, 3, 0) (540,540, 216)
8 (-1,-1, 0, 0, 1, 1) (4, 1, 1) (480,336, 336)
9 (-1, 0, 0, 0, 0, 1) (2, 2, 2) (576,576, 576)
10 ( 0, 0, 0, 0, 0, 0) (6, 0, 0) (0, 0, 0)
Each row can be summed using 1 + omega + omega^2 = 0. Rewriting
R(w_j) / G(w_j) after cancellation gives (on the orbit of each w_j):
on orbit of w_3: R = (1/2) G
on orbit of w_6: R = 3 G
on orbit of w_7: R = 9 G
on orbit of w_8: R = 4 G
on all other orbits: R = 0
Orbit sizes (under signed coordinate permutations acting on w_j):
|orbit(w_3)| = 360, |orbit(w_6)| = 120, |orbit(w_7)| = 20,
|orbit(w_8)| = 90.
Let S_j = S(w_j) denote the orbit average. Then:
(i) WEIGHTED CROSS (from summing (7.1c) over symmetric choices,
using the R multipliers and dividing by 180):
S_3 + 2 S_6 + S_7 + 2 S_8 = 0.
(ii) Rows j in {1, 4, 5, 9} have multiplier R = 0, and by the
orbit symmetry this forces S_j = 0 for those j.
(iii) Rows j in {6, 8}: |G(w_j)|^2 = (3^2 + 3^2)/36 = 1/4. Then
(7.1b) together with the definition of S_j gives
S_6 = S_8 = -1/20.
(iv) Take a = c = w_5 in (7.1c) and average over coordinate
permutations. Same for a = c = w_8. The 30 charges w_j + D
(adding each e_i - e_j to w_j) distribute among the orbit
classes (0, 1, 3, 4, 6, 7, 8, 9) with these integer counts:
w_5 + D : 0:1, 1:8, 3:12, 4:0, 6:8, 7:0, 8:0, 9:1
w_8 + D : 0:0, 1:0, 3: 4, 4:8, 6:4, 7:2, 8:8, 9:4
Averaging over permutations sends each w_j + d to its orbit
average. Substituting the known values S_1 = S_4 = S_9 = 0 and
S_6 = S_8 = -1/20 gives the linear system
S_0 + 12 S_3 = 2/5,
4 S_3 + 2 S_7 = 3/5.
(v) Solve the system. From (i) plus S_6 = S_8 = -1/20:
S_3 + S_7 = 1/5. [A]
Subtract twice [A] from 4 S_3 + 2 S_7 = 3/5:
2 S_3 = 1/5, S_3 = 1/10, S_7 = 1/10.
Then back-substitute into S_0 + 12 S_3 = 2/5:
S_0 = 2/5 - 12/10 = -4/5.
(vi) Plug into positivity:
E[ | sum_i z_i^3 |^2 ] = 6 + 30 S_0 = 6 - 24 = -18 < 0.
Contradiction. This proves Proposition 7.1.
8. SIX POSITIVE FORMS THAT RULE OUT SEVEN MUBS
==============================================
By Proposition 5.1 and Theorem 1, every transition matrix in a
(fictional) complete family would have to satisfy case (M):
g_{H_{rs}}(pi alpha) = 0 for every coordinate permutation pi,
for every ordered pair of distinct bases r != s.
We now build a single positive-definite quadratic form on the
collection of character sums whose exact average is negative. That
contradicts positivity and proves Theorem 2.
8.1 SAMPLING AND PAIRED FUNCTIONS
---------------------------------
Assume seven MUBs exist. Choose:
- reference index r uniform on {1, ..., 7};
- uniform coordinate permutation sigma of {0, ..., 5};
- uniform bijection pi from {1, ..., 6} to {1, ..., 7}∖{r}.
The reduced transition matrices are
H_s(i, k) = sqrt(6) * <b_{r,sigma(i)}, b_{pi(s),k}> (s = 1..6)
with g_s = g_{H_s}. For labels s = (s_1, ..., s_n) and balanced
charges a = (a_1, ..., a_n) with sum a_j = 0, define
M( s ; a ) = E[ Re( prod_{j=1}^n g_{s_j}(a_j) ) ]
where E is over (r, sigma, pi). Equal labels denote the same matrix.
Also define the ordered-pair average
m(A) = (1/42) sum_{r != s} m_{H_rs}(A),
where m_{H_rs} is the real injective moment of Section 4.1.
Bounds:
|m(A)| <= 1 (unit-modulus monomials)
|M(s ; a)| <= 1 (each g is an average of six unit-modulus
complex numbers)
8.2 SHARED-COLUMN FUNCTIONS
---------------------------
Choose one additional random column z = (z_0, ..., z_5) uniformly
from H_0. For a balanced charge a, define
F_0(a) = g_0(a) * z^{-a}
F_1(a) = ( (1/5) * sum_{s=1}^5 g_s(a) ) * z^{-a}.
Here z^{-a} = prod_i z_i^{-a_i}. Both F_0 and F_1 are random complex
functions on the probability space defined so far.
GRAM-ENTRY LEMMA. For balanced charges a, v, and b = (a, -v, v - a):
if (s,t) = (0,0), (0,1), or (1,0):
Re E[ F_s(a) * conj(F_t(v)) ] = M( (s,t,0) ; b )
if (s,t) = (1,1):
Re E[ F_1(a) * conj(F_1(v)) ]
= (1/5) M( (1,1,0) ; b ) + (4/5) M( (1,2,0) ; b ).
The "0" in a triple denotes a fresh external basis label, not tied to
H_0. The "2" in (1,2,0) is an auxiliary label used to distinguish the
two factors of F_1 that come from distinct bases.
Proof. Condition on all matrices and average over z. Orthogonality of
the columns of H_0 gives
E_z [ z^{v - a} ] = g_0( v - a ).
Case (s,t) = (0,0). F_0(a) conj(F_0(v)) = g_0(a) g_0(-v) z^{v-a}.
Averaging over z, the resulting three-factor product has charges
(a, -v, v-a) on three factors, all with the label 0 (the same
matrix H_0). So the moment is exactly M((0,0,0); b).
Case (s,t) = (0,1). F_0(a) conj(F_1(v)) is (1/5) sum_s g_0(a) g_s(-v)
z^{v-a}. Averaging over z, the resulting three-factor product has
labels (0, s, 0) with s uniform on {1,...,5}. By label symmetry (I),
every s contributes the same M((0,1,0); b), so the average is
M((0,1,0); b). Case (1,0) is identical.
Case (s,t) = (1,1). F_1(a) conj(F_1(v)) is (1/25) sum_{s,t}
g_s(a) g_t(-v) z^{v-a}. Averaging over z, the resulting three-factor
product has labels (s, t, 0) and there are 25 ordered pairs. Diagonal
(s=t): 5 of them, each contributing M((1,1,0); b) by label symmetry.
Off-diagonal (s!=t): 20 of them, each contributing M((1,2,0); b) by
label symmetry. So the average is (5/25) M((1,1,0); b) plus
(20/25) M((1,2,0); b).
8.3 REDUCTION RULES FOR MIXED MOMENTS
-------------------------------------
Under assumption (M) on all transitions, the mixed moments M satisfy:
(I) SYMMETRY. Common coordinate permutation of all a_j; simultaneous
sign flip a_j -> -a_j; reordering of factors and their labels;
injective renaming of used labels; removal of zero charge factors
(g_s(0) = 1); removal of coordinates on which every charge is
zero. All preserve M as a mixed moment.
(II) VANISHING. M(s ; a) = 0 if any factor has ord(a_j) = 1 or is a
coordinate permutation of alpha. (First part: (A). Second part:
assumption (M).)
(III) SINGLETON CONTRACTION. Suppose a_j has order two and its label
s_j occurs only once among the factors. Let l = |S| be the number
of distinct labels used. Then
M(s ; a) = -(1/(7-l)) sum_{t in S∖{s_j}}
M( s[ s_j -> t ] ; a ),
where s[s_j -> t] means: replace that one label s_j by t.
Proof sketch: Fix the row permutation and the bases assigned to
the l-1 other used labels. There are 7 - l available bases for the
singleton label. Identity (B) says: sum over these available
bases of g_v(a_j) = - sum over used non-singleton bases of
g_v(a_j). Multiplying by the other factors and averaging gives
the formula.
(IV) SINGLE-LABEL PARTITIONS. If all labels are equal to s, then
M((s,...,s); a) decomposes exactly into pair moments m(A) with
rational coefficients:
M((s,...,s); a)
= sum_{P : set partition of {1,...,n}, |P| <= 6}
(6)_{|P|} / 6^n * m( A_P ),
where A_P is formed by replacing each block's columns by their
sum, and (6)_k is the falling factorial. (Same equality-pattern
machinery as Section 4.3, using that m is already an
ordered-pair average.)
(V) MIXED IDENTITIES. For balanced a, b, c with a + b + c = 0:
sum_{j=0}^5 M((s,s,u); (a + e_i - e_j, b - e_i + e_j, c))
= M((s,u); (a+b, c)), [same]
sum_{d in D} M((s,t,u); (a+d, b-d, c)) = 0, if s != t. [diff]
These are the character identities (C) and (D) from Section 6.
(In (same), if a + b = 0 the right side reduces to M((s,u); (0, c))
which by (I) is just M((u); c) or 1 if c = 0.)
8.4 THE SIX POSITIVE FORMS
--------------------------
For lambda a partition of 6, arrange the positions 1, ..., 5 in
left-justified rows of lengths lambda_1, lambda_2, ... (position 0
sits at top-left). Let R_lambda and C_lambda be the groups of
row-internal and column-internal permutations, both fixing position 0.
The six partitions used are:
lambda m e_lambda
(1,1,1,2) 5 14
(1,1,3) 21 13
(1,2,2) 11 13
(1,4) 27 14
(2,3) 22 14
(5) 12 15
For each lambda we provide:
- a list ws_lambda = ((t_0, v_0), ..., (t_{m-1}, v_{m-1})) of m
pairs, each t_i in {0,1} and v_i a balanced charge;
- a symmetric positive-definite integer matrix Z_lambda of size
m x m, stored via its strictly lower triangular half in row
order (so the encoding a_lambda has length m(m+1)/2).
The Young functions are the finite linear combinations
(Y_lambda)_i = sum_{p in R_lambda, q in C_lambda}
sgn(q) * F_{t_i}( (P_p P_q v_i) ),
where P_x is coordinate permutation on charges. Each Y_lambda is a
list of m complex functions of the probability space.
THEOREM 8.1 (Mixed-moment certificate).
Q := 5 * sum_lambda 10^{15 - e_lambda}
* E( Y_lambda^* Z_lambda Y_lambda )
= c_0 + sum_{K != empty} c_K * mu_K
with the rational values
c_0 = -613302797399911 / 6480,
sum_K |c_K| = 179721388988719 / 6480,
so that
Q <= c_0 + sum_K |c_K| = -2007321335237 / 30 < 0.
Here mu_K runs over the moment coordinates retained after all
reductions of Section 8.3, and every |mu_K| <= 1.
EVERYTHING IN Q IS NONNEGATIVE BY CONSTRUCTION. For a fixed evaluation
of the probability space, each Y_lambda = x + i y is a complex vector
with real x, y. For a real symmetric positive-definite Z_lambda:
Y^* Z Y = x^T Z x + y^T Z y >= 0.
So each E(Y_lambda^* Z_lambda Y_lambda) is nonnegative, and each
10^{15} - e_lambda multiplier is a positive power of 10, so Q >= 0.
Theorem 8.1 computes Q to be strictly negative. Contradiction. So
seven MUBs in C^6 do not exist; Theorem 2 is proved.
What remains is the exact finite statement "Q <= -2007321335237/30".
It reduces to three rational computations:
(a) each Z_lambda is positive definite;
(b) the mixed-moment substitutions from Section 8.3 are exact
rational identities;
(c) the residual coefficients c_0 and c_K have the stated
values in Theorem 8.1 (in particular their absolute sum).
All three are verified by the exact verifier of Section 9.
8.5 WHY THIS CERTIFIES A NEGATIVE BOUND
---------------------------------------
In the moment coordinates,
Q = c_0 + sum_{K != empty} c_K * mu_K.
Every mu_K is a mixed moment (or a reduce-to-pair-moment), and by
the bounds in Section 8.1, |mu_K| <= 1. Then
Q = c_0 + sum c_K mu_K
<= c_0 + sum |c_K| * |mu_K|
<= c_0 + sum |c_K|
= -2007321335237/30
< 0.
So Q is strictly negative. This contradicts Q >= 0 from the positive
definiteness of Z_lambda. Note c_0 is itself a large negative number
(about -9.5e10) and the residual coefficient sum is about +2.8e10;
their sum is still about -6.7e10 (i.e. -2007321335237/30). So no
assignment of mu_K with |mu_K| <= 1 can rescue positivity.
9. EXACT VERIFICATION
=====================
Both certificates (the pair certificate of Section 4.5 and the mixed
certificate of Theorem 8.1) rest on finitely many exact rational
identities. The verifier is a single standard-library Python program.
From the paper directory it runs with
python3 verification/run.py
and prints exactly three lines:
rank table: 8871 909 897
rank table: 46041 3429 2767
-613302797399911/6480 179721388988719/6480 5000000000000000
The first two lines are (nonzero equations, moment coordinates,
independent witness rows) for the pair and mixed systems. The third
gives c_0, sum |c_K|, and the normalization 5*10^15 for Theorem 8.1.
9.1 EXACT LINEAR SUBSTITUTIONS
------------------------------
Both certificates express some moments in terms of others using a
finite system of rational linear equations.
Suppose W is an r x N integer matrix of moment equations (after
clearing denominators), and we want a rational matrix P satisfying
P_{*,J} = 0, P_{F,F} = I, W P = 0,
where J is a chosen pivot set of r columns and F = {1,...,N} ∖ J is
the complementary free set.
EXACT SUBSTITUTION LEMMA. If the r x r submatrix W_J is invertible (it
suffices that it be invertible modulo one prime), then P exists and
every real vector m satisfying W m = 0 also satisfies m = P m.
Consequently the rows of P are valid exact substitution rules that
only use equations from W.
Proof. Write W = ( W_J | W_F ) in the order (J, F). Set P = [[0,
P_{J,F}], [0, I]]. Then W P = W_J P_{J,F} + W_F = 0, so P_{J,F} =
-W_J^{-1} W_F. For any solution m, m_J = P_{J,F} m_F and m_F = m_F,
i.e. m = P m.
The verifier finds P as follows:
1. Modular elimination over Z/p for several large primes
identifies candidate pivot columns J (columns that stay
independent modulo each prime).
2. Retain exactly those integer equations from W that gave
pivots (each supplies one row). Call this retained set W'.
3. Over W', back-substitute (ascending pivot order) to solve
each pivot column in terms of free columns.
4. Chinese-remainder the modular coefficient solutions; recover
candidate rational P values.
5. Substitute every P rule into each retained integer row of W'
and verify that every integer coefficient vanishes after
clearing denominators.
Only step 5 matters for correctness. Steps 1-4 merely find candidates.
A prime that happens to conceal a true equation simply leaves that
equation unused; it cannot make the certificate unsound.
9.2 PAIR CERTIFICATE
--------------------
The pair system collects every instance of the homogeneous seven-row
contraction (Section 4.2, p = 7 case)
sum_{l=1}^6 U_0( A_{i -> l} ) = 0
where A ranges over integer matrices with these properties:
- size 7 x q with q in {2, 3, 4};
- zero row sums and zero column sums;
- 7 positive integer row orders r_0 <= ... <= r_6 summing to
k in {7, 8, 9, 10, 11}, each r_i <= floor(k/2); first row
order 1 (forced: sum of seven ints >= 2 with sum <= 11 fails);
- q positive integer column orders c_0 <= ... <= c_{q-1}
summing to the same k, each c_j in [2, floor(k/2)];
- no two matrices are equal up to canonical symmetry (row/col
permutation, negation, transposition).
"U_0(A_{i->l})" is the recursively contracted expression: any
remaining order-one row or column is repeatedly contracted using the
p <= 6 formula, terminating when all nonzero orders are >= 2.
Table size:
nonzero equations: 8871
moment coordinates: 909
independent witness rows: 897
With these substitutions, the pair certificate identity of Section
4.5 reduces to zero. Exact rational arithmetic confirms.
9.3 MIXED CERTIFICATE
---------------------
The mixed system collects every instance of the mixed identities (V)
of Section 8.3, together with (III) singleton contractions and (IV)
single-label partitions. Concretely the program:
- enumerates triples (a,b,c) of balanced charges with a+b+c=0
and 0 <= ord(c) <= ord(b) <= ord(a) <= 5, total order <= 11;
- for each, forms five mixed-moment equations (one per equality
pattern of the three labels), each expanded via evmix;
- adds instances of same-matrix and different-matrix identities
(both shifts) with total order <= 11;
- adds the pair-system equations embedded in single-label
moments.
Table size:
nonzero equations: 46041
moment coordinates: 3429
independent witness rows: 2767
The six positive forms of Section 8.4 are constructed from explicit
Young-symmetrizer data. Their combined expansion Q is a rational
linear combination of the moment coordinates. Substituting all
reductions and combining coefficients gives exactly
c_0 = -613302797399911 / 6480,
sum_{K != empty} |c_K| = 179721388988719 / 6480,
c_0 + sum_K |c_K| = -2007321335237 / 30 < 0.
Positive definiteness of each Z_lambda is certified by exact Schur
complement: write B = [[C, u], [u^T, p]] and replace B by C - u u^T
/ p. Repeat until empty. Positive pivots at every step imply positive
definiteness of the original. Every pivot in every Z_lambda satisfies
p > 40000 (a strict rational inequality), across 98 pivots total.
9.4 WHAT THE CHECK DOES AND DOES NOT REQUIRE
--------------------------------------------
The verifier needs no floating-point tolerance and no assumed
numerical accuracy. Every equality it asserts is an equality of
rational numbers derived from the finite integer inputs (the lists
ws_lambda and integer matrices Z_lambda). The only place "modular"
reasoning enters is in candidate-finding; the final exact check in
step 5 of Section 9.1 is unconditional.
Independence of the chosen equations matters not: any true subset of
the moment relations suffices. The verifier checks that a specific
finite set gives enough reduction, and then checks the resulting
identity exactly.