back to table · edit · history · where entries came from · files · download
3515 bytes, as of the version from 2026-11-16 04:25 (current). Recorded here, not run.
"""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()]