"""Exact Fermat-plane incidence and integral quotient, for SageMath.

The union of two matching diagrams is a disjoint union of cycles. A connected
component contributes one affine kernel dimension precisely when all root-of-
unity constraints are consistent modulo 2*d. This is exact linear elimination
in a monomial system, not numerical rank. check_lattice.py checks it against
cyclotomic linear algebra independently.
"""
import numberdb.sage as numberdb
from sage.rings.integer_ring import ZZ
from sage.rings.rational_field import QQ
from sage.rings.finite_rings.finite_field_constructor import GF
from sage.matrix.constructor import matrix
from itertools import product
from sage.libs.pari import pari
from modular import integral_index_certificate

def selected_pairs():
    return [(2,d) for d in range(3,15)] + [(4,d) for d in range(3,6)]

def matchings(vertices):
    if not vertices:
        yield ()
        return
    u=vertices[0]
    for v in vertices[1:]:
        for tail in matchings(tuple(x for x in vertices[1:] if x!=v)):
            yield ((u,v),)+tail

def planes(n,d):
    return [tuple((u,v,1+2*c) for (u,v),c in zip(m,cs))
            for m in matchings(tuple(range(n+2)))
            for cs in product(range(d),repeat=n//2+1)]

def intersection_dimension(p,q,n,d):
    edges=[[] for _ in range(n+2)]
    for u,v,e in p+q:
        edges[u].append((v,-e));edges[v].append((u,e))
    potential={};kernel_dimension=0
    for root in range(n+2):
        if root in potential:continue
        potential[root]=0;todo=[root];consistent=True
        while todo:
            u=todo.pop()
            for v,e in edges[u]:
                t=(potential[u]+e)%(2*d)
                if v in potential:
                    if potential[v]!=t:consistent=False
                else:potential[v]=t;todo.append(v)
        kernel_dimension+=int(consistent)
    return kernel_dimension-1

def pairing(r,d):
    numerator=1-(1-d)**(r+1)
    assert numerator%d==0
    return ZZ(numerator//d)

def gram(n,d):
    ps=planes(n,d);N=len(ps);G=matrix(ZZ,N,N)
    for i,p in enumerate(ps):
        for j in range(i+1):
            v=pairing(intersection_dimension(p,ps[j],n,d),d)
            G[i,j]=v;G[j,i]=v
    return ps,G

def quotient(G):
    # A modular rank supplies candidate columns only. The exact factorization
    # below proves that these columns span the full rational row space.
    J=list(G.change_ring(GF(1000003)).pivots())
    print("modular pivots",len(J),flush=True)
    B=G.matrix_from_columns(J)
    # det of the principal full-rank minor is a proved multiple of the
    # row-lattice determinant. PARI modular HNF avoids coefficient swell.
    A=G.matrix_from_rows_and_columns(J,J)
    bound=abs(A.det(algorithm='flint'));assert bound!=0
    rev=list(reversed(range(len(J))))
    Hlow=pari(B.matrix_from_columns(rev).transpose()).mathnfmod(bound).sage().transpose()
    H=Hlow.matrix_from_rows_and_columns(rev,rev)
    assert H.nrows()==H.ncols()==len(J)
    print("HNF complete",flush=True)
    C=(B.change_ring(QQ)*H.change_ring(QQ).inverse()).change_ring(ZZ)
    print("coordinates complete",flush=True)
    integral_index_certificate(C,J)
    print("surjectivity complete",flush=True)
    A=G.matrix_from_rows_and_columns(J,J).change_ring(QQ)
    K=(H*A.inverse()*H.transpose()).change_ring(ZZ)
    print("quotient form complete",flush=True)
    assert K==K.transpose() and G==C*K*C.transpose()
    return J,H,C,K

def matrix_json(M):
    return [[int(x) for x in row] for row in M.rows()]
