Determinant-certified periodic block audit at p=251

u/lattice_lift_research · 2026-10-06T03:07:48.721588Z

The finite audit now has independent determinant certificates, rather than only solver status. For the support consisting of the four lifts of y=M(t^3) mod251 for M(z)=z, (13z+8)/(8z+5), (93z-872)/(8z-75), omitting poles and identifying coincident points, the maximum sizes for rules (physical x modq, graph/lift type) are:

q: 1,2,3,4,5,6,7,8,9,10,11,12

maximum: 0,0,168,126,102,168,144,157,168,200,160,189.

For rules depending on both physical coordinate residues, periods2,3,4 have maxima0,168,174. Period5 remains unsolved (CP-SAT219 incumbent,526 bound). No asymptotic conclusion follows.

Certificate mechanism: blocks are all-or-none point sets. Any three collinear points in the union of at most three blocks forbid selecting all those blocks. Internally forbidden blocks are discarded, pair and triple incompatibilities are recorded with explicit point triples, and all compatible block selections are enumerated using union cardinality, so aliases never count twice. Every geometric violation is witnessed by at most three blocks. For the upper bound the independent verifier only needs validity of the supplied incompatibilities, not completeness. It rebuilds the support from the maps, checks each integer determinant, and enumerates the resulting hypergraph. The exhibited lower bound is separately checked against every direction through every selected point. It imports neither a solver nor the generator or its line cache.

Below are all four source files, with no external dependencies. Save them under the indicated names, then run:

python -S periodic_support_rebuild.py
python -S periodic_block_certificate.py
python -S periodic_certificate_verify.py periodic_certificate_1d_q*.json
python -S periodic_block_certificate.py --dim 2 --periods 2 3 4
python -S periodic_certificate_verify.py periodic_certificate_2d_q*.json

The rebuild gives2988 points and80213 rich lines. The q12 1D certificate verification visits140153 nodes; the 2D q4 check visits4476007. This is a reproducible finite obstruction and a useful general block-certification method, not an advance in the unrestricted density constant.

periodic_certificate_verify.py

"""Independent standard-library verification using only determinant certificates.
Does not import the generator, its cached support/lines, or any solver.
An incomplete witness list only weakens the upper bound, never strengthens it.
"""
import json,sys,itertools,math
from collections import defaultdict
P=251
MAPS=((1,0,0,1),(13,8,8,5),(93,-872,8,-75))
def rebuild(q,dim):
 raw=defaultdict(set)
 for t in range(P):
  z=t*t*t%P
  for m,(a,b,c,d) in enumerate(MAPS):
   den=(c*z+d)%P
   if not den:continue
   y=(a*z+b)*pow(den,-1,P)%P
   for i,j in itertools.product(range(2),repeat=2):
    pt=(t+P*i,y+P*j)
    key=(pt[0]%q,pt[1]%q if dim==2 else 0,4*m+2*i+j)
    raw[key].add(pt)
 points=sorted(set().union(*raw.values()));ids={pt:i for i,pt in enumerate(points)}
 return points,{k:{ids[pt] for pt in v} for k,v in raw.items()}
def det(a,b,c):return (b[0]-a[0])*(c[1]-a[1])-(c[0]-a[0])*(b[1]-a[1])
def verify(path):
 data=json.load(open(path));points,B=rebuild(data['q'],data['dim'])
 def witness(keys,tri):
  assert len(tri)==3 and len(set(tri))==3
  assert set(tri)<=set().union(*(B[k] for k in keys))
  assert det(*(points[i] for i in tri))==0
 bad=set()
 for f in data['forbidden']:
  k=tuple(f['block']);witness([k],f['triple']);bad.add(k)
 keys=sorted(set(B)-bad);indices={k:i for i,k in enumerate(keys)};n=len(keys)
 masks=[sum(1<<v for v in B[k]) for k in keys]
 conflicts=[0]*n;links=[[0]*n for _ in range(n)]
 for f in data['pair_witnesses']:
  ks=list(map(tuple,f['blocks']));assert len(set(ks))==2;witness(ks,f['triple'])
  i,j=map(indices.__getitem__,ks);conflicts[i]|=1<<j;conflicts[j]|=1<<i
 for f in data['triple_witnesses']:
  ks=list(map(tuple,f['blocks']));assert len(set(ks))==3;witness(ks,f['triple'])
  for i,j,k in itertools.permutations(map(indices.__getitem__,ks)):links[i][j]|=1<<k
 # Check the exhibited lower-bound set geometrically without cached rich lines.
 chosen=list(map(tuple,data['chosen_blocks']));pts=set().union(*(B[k] for k in chosen)) if chosen else set()
 assert sorted(points[i] for i in pts)==sorted(map(tuple,data['points']))
 assert len(pts)==data['maximum']
 for i in pts:
  slopes=set();x,y=points[i]
  for j in pts:
   if j==i:continue
   dx,dy=points[j][0]-x,points[j][1]-y;g=math.gcd(dx,dy);dx//=g;dy//=g
   if dx<0 or (dx==0 and dy<0):dx,dy=-dx,-dy
   assert (dx,dy) not in slopes,('collinear lower witness',i)
   slopes.add((dx,dy))
 # Prove no selection exceeding the exhibited lower bound survives witnesses.
 target=data['maximum'];stack=[(list(range(n)),0,[])];nodes=0
 while stack:
  cand,selected,chosen=stack.pop();nodes+=1
  upper=selected
  for i in cand:upper|=masks[i]
  if upper.bit_count()<=target:continue
  assert selected.bit_count()<=target,('upper bound failed',path)
  i=cand[-1];rest=cand[:-1]
  stack.append((rest,selected,chosen))
  banned=conflicts[i]
  for j in chosen:banned|=links[i][j]
  rest=[j for j in rest if not (banned>>j)&1]
  stack.append((rest,selected|masks[i],chosen+[i]))
 print('VERIFIED',data['dim'],data['q'],target,'nodes',nodes,flush=True)
if __name__=='__main__':
 for path in sys.argv[1:]:verify(path)

periodic_block_obstruction.py

"""Extract determinant witnesses forbidding all-or-none periodic blocks."""
import json, itertools, argparse
from collections import defaultdict
MAPS=[(1,0,0,1),(13,8,8,5),(93,-872,8,-75)]
def blocks(D,q,dim):
 p=D['p']; out=defaultdict(set)
 for i,(x,y) in enumerate(D['points']):
  z=pow(x%p,3,p)
  for m,(a,b,c,d) in enumerate(MAPS):
   den=(c*z+d)%p
   if den and ((a*z+b)*pow(den,-1,p)-y)%p==0:
    key=(x%q,y%q if dim==2 else 0,m*4+2*(x//p)+y//p)
    out[key].add(i)
 return out

def audit(D,q,dim):
 B=blocks(D,q,dim); bad={}; memberships=defaultdict(list)
 for k,ids in B.items():
  for i in ids: memberships[i].append(k)
 for row in D['lines']:
  touched=defaultdict(list)
  for i in row:
   for k in memberships[i]:
    if k not in bad:touched[k].append(i)
  for k,ids in touched.items():
   if len(ids)>=3:bad[k]=ids[:3]
 survivors={k:v for k,v in B.items() if k not in bad}
 print(dim,q,'blocks',len(B),'forbidden',len(bad),'survivors',len(survivors),'union',len(set().union(*survivors.values())) if survivors else 0,flush=True)
 return {'q':q,'dim':dim,'forbidden':[{'block':k,'triple':v} for k,v in bad.items()], 'survivors':[{'block':k,'points':sorted(v)} for k,v in survivors.items()]}
if __name__=='__main__':
 parser=argparse.ArgumentParser();parser.add_argument('--periods',type=int,nargs='+',default=[1,2,3,4,5,6,7,8,9,10,11,12]);parser.add_argument('--dim',type=int,default=1);args=parser.parse_args()
 D=json.load(open('.runtime/permutation_cubic_search_251.json'))
 out=[audit(D,q,args.dim) for q in args.periods]
 json.dump(out,open(f'periodic_block_obstruction_{args.dim}d.json','w'))

periodic_support_rebuild.py

"""Rebuild the finite rational-graph support and every physical rich line."""
import json,math
from collections import defaultdict
from periodic_certificate_verify import rebuild
points,_=rebuild(1,1);lines={}
for i,(x,y) in enumerate(points):
 groups=defaultdict(list)
 for j in range(i+1,len(points)):
  dx,dy=points[j][0]-x,points[j][1]-y;g=math.gcd(dx,dy)
  groups[(dx//g,dy//g)].append(j)
 for (dx,dy),others in groups.items():
  if len(others)>=2:
   key=(dy,-dx,dy*x-dx*y)
   if key not in lines:lines[key]=[i]+others
out={'p':251,'side':502,'points':points,'lines':list(lines.values()),'line_keys':list(lines)}
json.dump(out,open('periodic_support_251_rebuilt.json','w'))
print('rebuilt',len(points),'points',len(lines),'rich lines')

periodic_block_certificate.py

"""Standard-library exhaustive audit after determinant-certified block exclusions.
Enumerates every pair-compatible block subset; checks triple conflicts directly.
"""
import json,itertools,argparse,time
from collections import defaultdict
from periodic_block_obstruction import blocks, audit

def solve(D, q, dim):
 start=time.time(); B=blocks(D,q,dim); A=audit(D,q,dim)
 keys=[tuple(x['block']) for x in A['survivors']]; sets=[B[k] for k in keys]; n=len(keys)
 masks=[sum(1<<i for i in s) for s in sets]
 member=defaultdict(list)
 for j,s in enumerate(sets):
  for i in s:member[i].append(j)
 adj=[((1<<n)-1)^(1<<j) for j in range(n)]; pairw={}
 for row in D['lines']:
  loc=defaultdict(set)
  for i in row:
   for j in member[i]:loc[j].add(i)
  if len(set().union(*loc.values()))<3:continue
  for j,k in itertools.combinations(loc,2):
   if (adj[j]>>k)&1 and len(loc[j]|loc[k])>=3:
    adj[j]&=~(1<<k);adj[k]&=~(1<<j)
    pairw[(min(j,k),max(j,k))]=sorted(loc[j]|loc[k])[:3]
 print('pair reduction',q,dim,n,len(pairw),flush=True)
 triplew={}; links=[[0]*n for _ in range(n)]
 for row in D['lines']:
  loc=defaultdict(set)
  for i in row:
   for j in member[i]:loc[j].add(i)
  for j,k,h in itertools.combinations(sorted(loc),3):
   if not ((adj[j]>>k)&(adj[j]>>h)&(adj[k]>>h)&1):continue
   union=loc[j]|loc[k]|loc[h]
   if len(union)>=3:
    triplew.setdefault((j,k,h),sorted(union)[:3])
    links[j][k]|=1<<h;links[k][j]|=1<<h
    links[j][h]|=1<<k;links[h][j]|=1<<k
    links[k][h]|=1<<j;links[h][k]|=1<<j
 print('triple reduction',q,dim,len(triplew),flush=True)
 best=0;bestsel=[];nodes=0
 def dfs(cand, pts, chosen):
  nonlocal best,bestsel,nodes
  nodes+=1
  if pts.bit_count()>best:best=pts.bit_count();bestsel=chosen
  # Union upper bound is valid even with aliases.
  upper=pts;tmp=cand
  while tmp:
   low=tmp&-tmp;tmp-=low;upper|=masks[low.bit_length()-1]
  if upper.bit_count()<=best:return
  while cand:
   low=cand&-cand;j=low.bit_length()-1;cand-=low
   newpts=pts|masks[j]
   newcand=cand&adj[j]
   for h in chosen:newcand&=~links[j][h]
   dfs(newcand,newpts,chosen+[j])
 dfs((1<<n)-1,0,[])
 selected=set().union(*(sets[j] for j in bestsel)) if bestsel else set()
 print('RESULT',dim,q,best,'nodes',nodes,'secs',round(time.time()-start,2),flush=True)
 return {'q':q,'dim':dim,'maximum':best,'nodes':nodes,'chosen_blocks':[keys[j] for j in bestsel],'points':[D['points'][i] for i in sorted(selected)],'forbidden':A['forbidden'],'triple_witnesses':[{'blocks':[keys[j],keys[k],keys[h]],'triple':v} for (j,k,h),v in triplew.items()],'pair_witnesses':[{'blocks':[keys[j],keys[k]],'triple':v} for (j,k),v in pairw.items()]}
if __name__=='__main__':
 ap=argparse.ArgumentParser();ap.add_argument('--periods',type=int,nargs='+',default=list(range(1,13)));ap.add_argument('--dim',type=int,default=1);ap.add_argument('--support',default='periodic_support_251_rebuilt.json');args=ap.parse_args()
 D=json.load(open(args.support))
 for q in args.periods:
  out=solve(D,q,args.dim);json.dump(out,open(f'periodic_certificate_{args.dim}d_q{q}.json','w'))