verify_publication_controls.py

#!/usr/bin/env python3
"""Exact sign controls for the publication audit.

The calculations exercise the separability and supercenter formulas used in
the proof.  They are regression controls, not a proof of the global theorem.
Only Python's standard library is used.
"""

from fractions import Fraction
from itertools import product


def add_term(table, key, value):
    table[key] = table.get(key, Fraction(0)) + value
    if table[key] == 0:
        del table[key]


def matrix_left(tensor, k, ell):
    out = {}
    for (i, j, r, s), coefficient in tensor.items():
        if ell == i:
            add_term(out, (k, j, r, s), coefficient)
    return out


def matrix_right(tensor, k, ell):
    out = {}
    for (i, j, r, s), coefficient in tensor.items():
        if s == k:
            add_term(out, (i, j, r, ell), coefficient)
    return out


def matrix_product(tensor, dimension):
    out = {}
    for (i, j, r, s), coefficient in tensor.items():
        if j == r:
            add_term(out, (i, s), coefficient)
    return out


def check_matrix_separability():
    checks = 0
    for even_dimension in range(3):
        for odd_dimension in range(3):
            dimension = even_dimension + odd_dimension
            if dimension == 0:
                continue
            parities = [0] * even_dimension + [1] * odd_dimension
            for column in range(dimension):
                element = {
                    (i, column, column, i): Fraction(1)
                    for i in range(dimension)
                }
                assert matrix_product(element, dimension) == {
                    (i, i): Fraction(1) for i in range(dimension)
                }
                for i in range(dimension):
                    assert (
                        parities[i]
                        + parities[column]
                        + parities[column]
                        + parities[i]
                    ) % 2 == 0
                for k, ell in product(range(dimension), repeat=2):
                    assert matrix_left(element, k, ell) == matrix_right(
                        element, k, ell
                    )
                    checks += 1

    # The averaged Casimir is a second valid separability element.  Checking
    # it prevents a common hand-indexing error in the outer right action.
    dimension = 2
    casimir = {
        (i, j, j, i): Fraction(1, dimension)
        for i, j in product(range(dimension), repeat=2)
    }
    assert matrix_product(casimir, dimension) == {
        (i, i): Fraction(1) for i in range(dimension)
    }
    for k, ell in product(range(dimension), repeat=2):
        assert matrix_left(casimir, k, ell) == matrix_right(
            casimir, k, ell
        )
    return checks


def qmul(a, b):
    """Q(1) basis elements 0=1, 1=u, with u odd and u^2=1."""
    return (a + b) % 2


def check_queer_separability():
    e = {(0, 0): Fraction(1, 2), (1, 1): Fraction(1, 2)}
    product_value = {0: Fraction(0), 1: Fraction(0)}
    for (a, b), coefficient in e.items():
        product_value[qmul(a, b)] += coefficient
    assert product_value == {0: Fraction(1), 1: Fraction(0)}

    for generator in (0, 1):
        left = {}
        right = {}
        for (a, b), coefficient in e.items():
            add_term(left, (qmul(generator, a), b), coefficient)
            add_term(right, (a, qmul(b, generator)), coefficient)
        assert left == right
    return len(e)


def exterior_product(left, right, variables):
    if left & right:
        return 0, 0
    inversions = 0
    for i in range(variables):
        if left & (1 << i):
            inversions += sum(
                1 for j in range(i) if right & (1 << j)
            )
    return (-1 if inversions % 2 else 1), left | right


def tensor_basis_parity(item):
    q, exterior = item
    return (q + exterior.bit_count()) % 2


def tensor_multiply(a, b, variables):
    qa, ma = a
    qb, mb = b
    exterior_sign, mask = exterior_product(ma, mb, variables)
    if exterior_sign == 0:
        return 0, (0, 0)
    koszul = -1 if (ma.bit_count() * qb) % 2 else 1
    return exterior_sign * koszul, ((qa + qb) % 2, mask)


def rational_rank(rows):
    matrix = [list(map(Fraction, row)) for row in rows if any(row)]
    if not matrix:
        return 0
    columns = len(matrix[0])
    rank = 0
    for column in range(columns):
        pivot = next(
            (row for row in range(rank, len(matrix)) if matrix[row][column]),
            None,
        )
        if pivot is None:
            continue
        matrix[rank], matrix[pivot] = matrix[pivot], matrix[rank]
        scale = matrix[rank][column]
        matrix[rank] = [entry / scale for entry in matrix[rank]]
        for row in range(len(matrix)):
            if row == rank or matrix[row][column] == 0:
                continue
            scale = matrix[row][column]
            matrix[row] = [
                entry - scale * pivot_entry
                for entry, pivot_entry in zip(matrix[row], matrix[rank])
            ]
        rank += 1
    return rank


def supercenter_dimension(variables, parity):
    basis = [
        (q, mask)
        for q in range(2)
        for mask in range(1 << variables)
    ]
    candidates = [item for item in basis if tensor_basis_parity(item) == parity]
    rows = []
    for test in basis:
        for output in basis:
            row = []
            for candidate in candidates:
                left_sign, left_value = tensor_multiply(
                    candidate, test, variables
                )
                right_sign, right_value = tensor_multiply(
                    test, candidate, variables
                )
                super_sign = (
                    -1
                    if parity * tensor_basis_parity(test) % 2
                    else 1
                )
                row.append(
                    (left_sign if left_value == output else 0)
                    - super_sign
                    * (right_sign if right_value == output else 0)
                )
            rows.append(row)
    return len(candidates) - rational_rank(rows)


def check_queer_grassmann_supercenters():
    dimensions = []
    for variables in range(4):
        even = supercenter_dimension(variables, 0)
        odd = supercenter_dimension(variables, 1)
        expected_even = 1 if variables == 0 else 2 ** (variables - 1)
        expected_odd = 0 if variables == 0 else 2 ** (variables - 1)
        assert (even, odd) == (expected_even, expected_odd)
        dimensions.append((variables, even, odd))
    return dimensions


def main():
    matrix_checks = check_matrix_separability()
    queer_terms = check_queer_separability()
    center_dimensions = check_queer_grassmann_supercenters()
    print(f"matrix_bimodule_centrality_checks={matrix_checks}")
    print("averaged_matrix_casimir_verified=True")
    print(f"queer_separability_terms={queer_terms}")
    for variables, even, odd in center_dimensions:
        print(
            "Q1_tensor_Lambda"
            f"{variables}_supercenter_dimensions=({even}|{odd})"
        )
    print("ALL PUBLICATION CONTROLS PASSED")


if __name__ == "__main__":
    main()