back to table · edit · history · where entries came from · files · download
3562 bytes, as of the version from 2026-11-16 04:25 (current). Recorded here, not run.
"""Exact low-memory lattice checks, using Sage finite-ring matrix operations.
Local Smith exponents are found by invertible-block Schur complements modulo
prime powers. This is used because the native large integer Smith step exceeds
the builder memory cap. Unit blocks are inverted by checked Newton lifting.
"""
import numberdb.sage as numberdb
import sage.rings.polynomial.laurent_polynomial_ring
from sage.rings.integer_ring import ZZ
from sage.rings.finite_rings.integer_mod_ring import Zmod
from sage.rings.finite_rings.finite_field_constructor import GF
from sage.matrix.constructor import matrix
import math
def integral_index_certificate(C,rows):
r=C.ncols();minor=abs(C.matrix_from_rows(rows).det(algorithm='flint'))
assert minor!=0
factors=list(minor.factor(proof=True))
assert math.prod(int(p)**int(e) for p,e in factors)==minor
cert=[]
for p,e in factors:
rank=C.change_ring(GF(p)).rank();assert rank==r
cert.append({'prime':str(p),'exponent':int(e),'rank_mod_prime':int(rank)})
return {'maximal_minor_rows':rows,'maximal_minor_determinant':str(minor),'prime_rank_certificates':cert,'row_lattice_index':1}
def local_smith(K,p,precision=8):
r=K.nrows();R=Zmod(ZZ(p)**precision);M=K.change_ring(R)
exponents=[];stages=[];level=0
while M.nrows():
if level>=precision:raise ArithmeticError('insufficient prime-power precision')
F=GF(p);Mf=M.change_ring(F);J=list(Mf.pivots());t=len(J)
stages.append({'exponent':level,'unit_rank':t,'remaining_dimension':M.nrows()})
exponents.extend([level]*t)
if t:
I=list(Mf.matrix_from_columns(J).transpose().pivots())
other_i=[i for i in range(M.nrows()) if i not in I]
other_j=[j for j in range(M.ncols()) if j not in J]
A=M.matrix_from_rows_and_columns(I,J)
Ai0=Mf.matrix_from_rows_and_columns(I,J).inverse()
X=matrix(R,t,t,[int(x) for x in Ai0.list()]);unit=matrix(R,t,t,1)
correct=1
while correct<precision-level:
X=X*(2*unit-A*X);correct*=2
assert A*X==unit and X*A==unit
if t==M.nrows():break
B=M.matrix_from_rows_and_columns(I,other_j)
C=M.matrix_from_rows_and_columns(other_i,J)
D=M.matrix_from_rows_and_columns(other_i,other_j)
S=D-C*X*B
else:S=M
ints=[int(x) for x in S.list()]
assert all(x%p==0 for x in ints)
level+=1
if level>=precision:raise ArithmeticError('unresolved Smith exponents at current precision')
R=Zmod(ZZ(p)**(precision-level))
M=matrix(R,S.nrows(),S.ncols(),[x//p for x in ints])
assert len(exponents)==r
return exponents,stages
def smith_factors(K,determinant=None):
determinant=K.det(algorithm='flint') if determinant is None else ZZ(determinant)
assert determinant!=0
factorization=list(abs(determinant).factor(proof=True));factors=[ZZ(1)]*K.nrows();proof=[]
assert math.prod(int(p)**int(e) for p,e in factorization)==abs(determinant)
for p,e in factorization:
precision=8
while True:
try:vals,stages=local_smith(K,int(p),precision);break
except ArithmeticError:precision*=2
assert sum(vals)==e
factors=[s*ZZ(p)**v for s,v in zip(factors,vals)]
proof.append({'prime':str(p),'determinant_valuation':int(e),'precision':precision,'exponents':vals,'stages':stages})
assert math.prod(factors)==abs(determinant)
return [int(x) for x in factors],proof