"""Job #1868 (pursue route 71 rev 2). QUESTION (#986's next step): on the tile's own class at D = 15 (all cyclic words with T_7's gap multiset 6^3 12^8 18^2 30^2, total P_7 = 210), (A) for which k does the summed k-deck S_k separate the class up to the dihedral group, and does the reviewer's word-fold (q = 11) factor through S_k (equal S_k => equal folded S_k)? (B) do non-deck rotation-invariant summaries -- the cyclic k-deck of subsequences (Scott / Gabrys' object, all rotations) for k = 2, 3, 4 -- separate or factor? The positional window-sum family {(i, sum of window i)} is the word itself up to the circulant map and is not a compression; it is reported analytically, not tested. DEFINITIONS (as #986's job1861-checks.py, reused read-only for the fold convention): S(w, k) = sorted multiset of sums of k consecutive cyclic gaps; fold(word, q): positions from 0 by prefix sums, q lifts v + jP, delete lifts = 0 or -2 mod q, retain the gap word (length D' = (q-2) D); a word is folded from its CANONICAL rotation (lexicographically least). Dihedral class = the word's orbit under rotation and reversal (S_k is invariant on it, #986 (2)). PRE-REGISTERED (before the run). A1 the class has 90,090 necklaces (15!/(3! 8! 2! 2!) / 15 = 1,351,350 / 15; all primitive) in 45,045 + (self-symmetric) dihedral classes; A2 the duality S_{D-k}(W) = {P - s : s in S_k(W)} holds for every word and every k (so k and 15-k have the same buckets); A3 the spectrum: number of S_k buckets and number holding >= 2 dihedral classes, k = 1..14; A4 fold test per k: for up to 200 ambiguous buckets, one non-dihedral pair each, folded at q = 11; refutation = folded S_k differ (#986's criterion) and, stronger, folded words not dihedral-equivalent; A5 controls: #986's numbers at k = 2, 3, 4 (257/235, 2586/2197, 6538/4443 buckets / ambiguous) reproduced, fold(T_7) is a rotation of the true T_11 word, and the k = 2 pair (18,30,30,42,18,42,30)/(18,30,30,42,30,18,42) (length 7, from #986's broader domain) still refutes. B1 the cyclic k-deck for k = 2, 3, 4 (multiset of length-k subsequences over all 15 rotations, encoded on the 4-letter alphabet): buckets, ambiguous buckets, fold test as in A4. FALSIFIER of the route's closure branch: a k or a family with ambiguous buckets whose folded pairs ALWAYS agree; FALSIFIER of the route's negative branch: a k or family with NO ambiguous bucket (it separates the class). Stdout: ledger + JSON; stderr: progress. Runtime a few minutes; RAM < 2 GB.""" import json, sys, time, itertools, math import numpy as np from collections import Counter, defaultdict t0 = time.time(); log = sys.stderr; led = [] def check(tag, ok, detail): led.append(f"{'PASS' if ok else 'FAIL'} {tag} :: {detail}"); print(led[-1], file=log, flush=True) D, P, Q = 15, 210, 11 ALPHA = [6, 12, 18, 30]; COUNTS = {6: 3, 12: 8, 18: 2, 30: 2} def fold(word, q): P_ = sum(word); pos, x = [], 0 for g in word: pos.append(x); x += g keep = sorted(v + k * P_ for k in range(q) for v in pos if (v + k * P_) % q not in (0, (q - 2) % q)) n = len(keep); return [keep[i + 1] - keep[i] for i in range(n - 1)] + [q * P_ + keep[0] - keep[-1]] def S(w, k): n = len(w); return tuple(sorted(sum(w[(i + j) % n] for j in range(k)) for i in range(n))) def rots(w): return [tuple(w[i:] + w[:i]) for i in range(len(w))] def canon(w): return min(rots(list(w))) def dcanon(w): return min(min(rots(list(w))), min(rots(list(reversed(w))))) # ---- A1: enumerate necklaces (canonical rotations) of the multiset def perms(counts, n, prefix): if len(prefix) == n: yield tuple(prefix); return for a in ALPHA: if counts[a]: counts[a] -= 1; prefix.append(a) yield from perms(counts, n, prefix) prefix.pop(); counts[a] += 1 neck = [] for w in perms(dict(COUNTS), D, []): if w == canon(w): neck.append(w) N = len(neck); print(f'necklaces {N} ({time.time() - t0:.0f}s)', file=log, flush=True) W = np.array(neck, dtype=np.int32) dcl = {}; dclass = np.empty(N, dtype=np.int64) for i, w in enumerate(neck): c = dcanon(w); dclass[i] = dcl.setdefault(c, len(dcl)) ndih = len(dcl) check('A1_class_size', N == 90090, f'necklaces = {N}, dihedral classes = {ndih}') # ---- A2/A3: S_k spectrum by numpy WW = np.concatenate([W, W], axis=1); cs = np.concatenate([np.zeros((N, 1), np.int32), np.cumsum(WW, axis=1)], axis=1) def Sk_matrix(k): return np.sort(cs[:, k:k + D] - cs[:, :D], axis=1) # (N, D) sorted window sums spectrum = {}; buckets_by_k = {} dual_ok = True for k in range(1, D): M = Sk_matrix(k) keys, inv, cnt = np.unique(M, axis=0, return_inverse=True, return_counts=True) inv = inv.ravel() # ambiguous buckets: >= 2 distinct dihedral classes pairs = np.stack([inv, dclass], axis=1); up = np.unique(pairs, axis=0) per_bucket = np.bincount(up[:, 0], minlength=len(keys)) amb = np.flatnonzero(per_bucket >= 2) spectrum[k] = {'buckets': int(len(keys)), 'ambiguous_buckets': int(len(amb)), 'max_bucket': int(cnt.max()), 'necklaces_in_ambiguous': int(cnt[amb].sum()) if len(amb) else 0} buckets_by_k[k] = (inv, amb) if k <= D // 2: Md = Sk_matrix(D - k); dual_ok &= bool(np.array_equal(np.sort(P - M, axis=1), Md)) print(f'k={k}: buckets {len(keys)} ambiguous {len(amb)} ({time.time() - t0:.0f}s)', file=log, flush=True) check('A2_duality_S_D-k', dual_ok, 'S_{15-k}(W) = {210 - s : s in S_k(W)} for all words, k <= 7') check('A5_control_986_counts', spectrum[2]['buckets'] == 257 and spectrum[2]['ambiguous_buckets'] == 235 and spectrum[3]['buckets'] == 2586 and spectrum[3]['ambiguous_buckets'] == 2197 and spectrum[4]['buckets'] == 6538 and spectrum[4]['ambiguous_buckets'] == 4443, f"k=2 {spectrum[2]['buckets']}/{spectrum[2]['ambiguous_buckets']} k=3 {spectrum[3]['buckets']}/{spectrum[3]['ambiguous_buckets']} k=4 {spectrum[4]['buckets']}/{spectrum[4]['ambiguous_buckets']} (#986: 257/235, 2586/2197, 6538/4443)") sep = [k for k in range(1, D) if spectrum[k]['ambiguous_buckets'] == 0] check('A3_no_k_separates_the_class', len(sep) == 0, f'k with zero ambiguous buckets: {sep}; min ambiguous = {min(spectrum[k]["ambiguous_buckets"] for k in spectrum)} at k = {min(spectrum, key=lambda k: spectrum[k]["ambiguous_buckets"])}') # ---- A4: fold tests per k rng = np.random.default_rng(1868) def fold_tests(k, inv, amb, label, cap=200): if len(amb) == 0: return {'tested': 0} choose = amb if len(amb) <= cap else rng.choice(amb, cap, replace=False) tested = ref_S = ref_dih = 0; example = None for b in choose: idx = np.flatnonzero(inv == b) # one pair from two different dihedral classes cls = {} for i in idx: cls.setdefault(int(dclass[i]), int(i)) a, c = list(cls.values())[:2] fa, fc = fold(list(neck[a]), Q), fold(list(neck[c]), Q) tested += 1 if S(fa, k) != S(fc, k): ref_S += 1 if dcanon(fa) != dcanon(fc): ref_dih += 1 if example is None: example = {'w': list(neck[a]), 'u': list(neck[c])} return {'tested': tested, 'folded_S_k_differ': ref_S, 'folded_words_not_dihedral': ref_dih, 'example': example} foldres = {} for k in range(1, D): inv, amb = buckets_by_k[k]; foldres[k] = fold_tests(k, inv, amb, f'S_{k}') print(f'fold test k={k}: {foldres[k]} ({time.time() - t0:.0f}s)', file=log, flush=True) any_factor = [k for k in foldres if foldres[k]['tested'] and foldres[k]['folded_S_k_differ'] == 0] check('A4_fold_does_not_factor_through_any_S_k', len(any_factor) == 0, f'k where all tested pairs fold to equal S_k: {any_factor}; per k (tested, S_k differ, words not dihedral): ' + str({k: (v['tested'], v.get('folded_S_k_differ'), v.get('folded_words_not_dihedral')) for k, v in foldres.items()})) # A5 controls: true tile fold and #986's length-7 pair def tile(x): ps = [p for p in range(3, x + 1) if all(p % d for d in range(2, p))]; Px = 2 * math.prod(ps) r = [v for v in range(Px) if math.gcd(v, Px) == 1 and math.gcd(v + 2, Px) == 1] return r, [r[i + 1] - r[i] for i in range(len(r) - 1)] + [Px + r[0] - r[-1]] r7, w7 = tile(7); r11, w11 = tile(11) f7 = fold(w7, 11); ctrl_tile = dcanon(f7) == dcanon(w11) and Counter(w7) == COUNTS and canon(w7) in set(neck) pw, pu = [18, 30, 30, 42, 18, 42, 30], [18, 30, 30, 42, 30, 18, 42] ctrl_pair = S(pw, 1) == S(pu, 1) and S(pw, 2) == S(pu, 2) and S(pw, 3) == S(pu, 3) and S(fold(pw, 11), 2) != S(fold(pu, 11), 2) check('A5_control_true_fold_and_986_pair', ctrl_tile and ctrl_pair, f'fold(T_7) dihedral to T_11: {dcanon(f7) == dcanon(w11)}; T_7 word in class: {canon(w7) in set(neck)}; #986 pair refutes at k=2: {ctrl_pair}') # rotation dependence of the fold on synthetic words (frame control): is fold(rot(w)) always dihedral to fold(w)? rotdep = 0 for i in rng.choice(N, 300, replace=False): w = list(neck[i]); f0 = dcanon(fold(w, Q)) if any(dcanon(fold(list(r), Q)) != f0 for r in rots(w)[1:4]): rotdep += 1 check('A6_fold_frame_dependence_noted', True, f'{rotdep}/300 synthetic words whose fold changes (up to dihedral) under rotation of the start; the fold is applied to canonical rotations throughout, as in #986') # ---- B1: cyclic k-deck of subsequences, k = 2,3,4 (all rotations), encoded on the 4-letter alphabet letter = {6: 0, 12: 1, 18: 2, 30: 3}; V = np.vectorize(letter.get)(W) # (N, D) letters deck = {} for k in (2, 3, 4): combos = np.array(list(itertools.combinations(range(D), k)), dtype=np.int64) # (C, k) weights = (4 ** np.arange(k))[::-1] nb = 4 ** k; H = np.zeros((N, nb), dtype=np.int32) for s in range(D): Vr = np.roll(V, -s, axis=1) # rotation s codes = (Vr[:, combos] * weights).sum(axis=2) # (N, C) for i in range(0, N, 5000): blk = codes[i:i + 5000] H[i:i + 5000] += np.apply_along_axis(lambda row: np.bincount(row, minlength=nb), 1, blk).astype(np.int32) keys, inv, cnt = np.unique(H, axis=0, return_inverse=True, return_counts=True); inv = inv.ravel() pairs = np.stack([inv, dclass], axis=1); up = np.unique(pairs, axis=0); per_bucket = np.bincount(up[:, 0], minlength=len(keys)); amb = np.flatnonzero(per_bucket >= 2) ft = fold_tests(k, inv, amb, f'deck{k}') # for the deck family the natural closure test is: folded words dihedral-equal? and folded S_k equal deck[k] = {'buckets': int(len(keys)), 'ambiguous_buckets': int(len(amb)), 'max_bucket': int(cnt.max()), 'fold': ft} print(f'cyclic {k}-deck: buckets {len(keys)} ambiguous {len(amb)} fold {ft} ({time.time() - t0:.0f}s)', file=log, flush=True) deck_sep = [k for k in deck if deck[k]['ambiguous_buckets'] == 0] deck_factor = [k for k in deck if deck[k]['fold']['tested'] and deck[k]['fold']['folded_S_k_differ'] == 0] check('B1_cyclic_k_deck', True, f'separating k: {deck_sep}; factoring k: {deck_factor}; ' + str({k: (v['buckets'], v['ambiguous_buckets'], v['fold'].get('tested'), v['fold'].get('folded_S_k_differ'), v['fold'].get('folded_words_not_dihedral')) for k, v in deck.items()})) out = {'instrument': 'spectrum1868.py', 'job': 1868, 'D': D, 'P': P, 'q': Q, 'necklaces': N, 'dihedral_classes': ndih, 'spectrum': spectrum, 'fold_tests': foldres, 'cyclic_k_deck': deck, 'controls': {'tile_fold_ok': ctrl_tile, 'pair_986_ok': ctrl_pair, 'fold_rotation_dependent_words_of_300': rotdep}, 'ledger': led, 'secs': round(time.time() - t0, 1)} print('\n'.join(led)); print('VERDICT ' + json.dumps({'all_pass': all(l.startswith('PASS') for l in led), 'no_k_separates': len(sep) == 0, 'no_k_factors': len(any_factor) == 0, 'deck_separates': deck_sep, 'deck_factors': deck_factor, 'secs': out['secs']})) json.dump(out, open('spectrum1868.json', 'w'), indent=1)