"""faces.py -- where on the Newton polytope two factorizations of one menu product part, and what a face reads there. QUESTION. collide.py defines the DESCENT DIMENSION delta of two factorizations of a product over N: the least dimension of a face of the product's Newton polytope on which the multisets of initial forms, each divided by its monomial gcd, differ, at least 1 in the menu frame. How low does delta sit through ten terms, where the classification by number of terms is complete? Do two factorizations of one product exist that no proper face separates? Which pairs of menus have a product factoring two ways when one of them is a seed with a two-factor core, and can the test be read off one product without factoring the whole? And when two factorizations have the SHARED SHAPE, one factor p common to a block on each side, {p n, q} against {p, n q}, exactly which faces separate them? THE ARGUMENT (written before the engine). (A) EDGE DESCENT THROUGH TEN TERMS. A product's term counts multiply (collide.py, the term-count law), so non-uniqueness needs a composite count; van de Woestijne's classification makes 4, 8 and 9 unique, leaving 6 and 10. At 6 the one shape X^a (1 + X^b + ... + X^(5b)) spends one of its two exponents on a translation, so read through Lemma 3.10 in several variables its exponent vectors are alpha + i beta: a segment, delta <= 1. The three sporadic ten-term shapes likewise carry one free exponent and a translation, so they sit on segments. The two ten-term families F1 (1 + X^(3b))(1 + X^a + X^b + X^(a+b) + X^(a+2b)) = (1 + X^b)(1 + X^a + X^(a+2b) + X^(3b) + X^(a+4b)), F2 (1 + X^(3b))(1 + X^a + X^b + X^(a+b) + X^(2b)) = (1 + X^b)(1 + X^a + X^(2b) + X^(a+3b) + X^(4b)), with a and b read as independent vectors, carry two weights w with = 0. The engine minimizes w.e, so < 0 keeps the a-terms and > 0 drops them. Writing v = X^b, F1 keeping them and F2 dropping them read {1 + v^3, 1 + v + v^2} against {1 + v, 1 + v^2 + v^4}: they differ on a face spanned by b alone, so delta = 1. (The other weight reads {1 + v^3, 1 + v} on both sides in both families and does not separate.) So any two factorizations of a product of at most ten terms, counted with multiplicity as the classification counts them, have delta = 1, and delta = 2 needs twelve, eleven being prime. (B) THE SIGN SCAN. Let a seed's core have exactly two Z-irreducible factors, n with a negative coefficient and p nonnegative, and a partner's core be one Z-irreducible q, nonnegative since it is a 0/1 polynomial. The product's Z-factors are {n, p, q} up to monomials. Of the five partitions, {n, p, q} and {n, p q} leave n alone and fail; {n p q} splits as (n p) q and is not atomic; {n p, q} always stands; {n q, p} stands iff n q has no negative coefficient. So the product factors two ways iff n q >= 0 and q != p, where the two survivors coincide. A two-factor core with BOTH factors negative is unique against any such partner: every partition but {n1 n2, q} leaves a negative block. (C) THE FACE LAW. On two factorizations of the shared shape, write P, N, Q for the initial forms of p, n, q at a weight w, each divided by its monomial gcd. Initial forms multiply, and so does that division: the least exponent of each variable in a product is the sum of the least exponents. Blocks both sides hold contribute the same form to both and cancel. So the face reads {P N, Q} against {P, N Q}, forms equal to 1 dropped. If they agree, P N equals P or N Q, so N = 1 or P = Q by cancellation in a domain; conversely either gives equality. In the frame a monomial initial form gamma x^v of n has gamma = 1: a generic refinement of w picks a vertex of the menu product, of coefficient 1 as every menu's vertices are, so each nonnegative integer block has coefficient 1 there, p n among them, whose coefficient is gamma times p's. So N = 1 means in_w(n) is a monomial. Hence A FACE SEPARATES IFF in_w(n) IS NOT A MONOMIAL AND P != Q. At product dimension 2, with vertices never separating, delta = 1 exactly when some edge normal of Newt(n) is an edge normal of Newt(p) or Newt(q) along which P != Q. The clause P != Q is the ACCIDENT's: with p = 1 + t, n = 1 - t + t^2 and q = (1 + t) + y (1 + t + t^2) + y^2 (1 + t), both edges of the product parallel to n read in_w(q) = p, so no proper face separates and delta = 2, although n's edge is parallel to p's. (D) THE LINE SHAPE. Take p = 1 + t, n univariate in t, and q = sum over j of y^j q_j. Then n has non-monomial initial forms only at w = (0, 1) and (0, -1), where p reads itself and q its lowest and highest layer. So delta = 2 exactly when both outermost layers of q are monomial multiples of p. (E) TWELVE IS EMPTY IN THE LINE SHAPE. Let two such factorizations have delta = 2, B = p n, and q not divisible by 1 + t. Counted with multiplicity, |F| = |B| |q| for F = B q. B(-1) = 0 makes |B| even. The outermost layers are multiples of 1 + t, so some middle layer r has r(-1) != 0, and n r >= 0 (n q = sum y^j n q_j) rules out a monomial r, n carrying a negative coefficient. So |q| >= 2 + 2 + 2 and |F| >= 12, with equality only at |B| = 2 and one two-term middle layer. |B| = 2 makes B = 1 + t^k, k odd, k >= 3, n = 1 - t + t^2 - ... + t^(k-1); r = t^c (1 + t^m) gives n r / t^c the coefficient -1 + [m = 1] at t, so m = 1 and r is a multiple of 1 + t, contradicting its choice. No line-shape product factoring two ways at delta = 2 with q not divisible by 1 + t has twelve terms, at any degree and any layer count. (F) SIXTEEN IS EMPTY TOO (added after the runs above, with its own check P7). With |q| >= 6 and |B| even, |F| = 16 forces |B| = 2 and |q| = 8, so B = 1 + t^k and n as in (E). A multiple of 1 + t has an even number of terms with multiplicity, so the outer layers hold at least 4 and the middle layers an even number, at most 4; none is a monomial, and a two-term one is a multiple of 1 + t by (E), so the layer r with r(-1) != 0 has four terms. With c now the least exponent of r, the coefficient at t in n r / t^c is -1 + [1 in X], X the exponents of r / t^c, so X = {0, 1, a, b} with 1 < a < b and n r / t^c = 1 + t^k + t^a n + t^b n. The -1 of t^a n at a + 1 is covered only by t^k or by b = a + 1, and b = a + 1 makes r = (1 + t)(1 + t^a); so k = a + 1. At k = 3 the -1 of t^b n at b + 1 is covered only at b = 3, again a multiple. At k >= 5 the -1 of t^a n at k + 2 needs b = k (a multiple) or b = k + 2, which leaves a -1 at 2k. No line-shape product factoring two ways at delta = 2 has sixteen terms either, q not divisible by 1 + t, among q whose middle layers are 0/1, so among every 0/1 F, since q <= F = q + t^k q coefficient by coefficient. A layer with a coefficient above 1, F not 0/1, is not ruled out, and P7 searches 0/1 layers only. DESIGN. collide.py supplies the counter (Z-factors, atomic factorizations over N) and the exact face engine for products of Newton dimension at most 2. Sections: CONTROL: the six-term identity (1 + x)(1 + x^2 + x^4) = (1 + x + x^2) (1 + x^3) counted and graded; the escape of collide.py graded. EDGE: F1 and F2 at three independent vector choices and one parallel choice, and the three sporadic shapes lifted by X -> x0 x1^2 beside a monomial x1^3; every pair of atomic factorizations graded. WITNESS: {4,6} x {3,4,8,9,18,24} against {2,4} x {6,8,9,24,27,36}; the counter, the Z-factors, the polygon's faces enumerated, delta, and the edge normals of Newt(n) against those of Newt(p), Newt(q). SCAN: seeds with a two-factor core -- every size-2 seed of {2..64}, {2,8,32}, every size-4 seed of {2..20} with such a core, and the witness's seed -- against every menu of sizes 2 to 6 in {2..14} whose core is one Z-irreducible; the scan's verdict against the counter's at every pair. LAW: at every face of every scan product factoring two ways of Newt dimension at most 2, of the witness, of the escape, of the fourteen-term specimen {2,16} x {2,4,6,12,18,24,36} = {2,4} x {2,6,16,18,24,96,144}, and of every LINE object below: separation against the law, and delta against the delta the law predicts. LINE: p = 1 + t (t the prime 2, y the prime 3); every 0/1 univariate B of degree <= 5 with constant term 1, B(-1) = 0 and a negative coefficient in n = B/(1 + t); layers the nonzero 0/1 univariates r of degree <= 5 with n r >= 0 and B r 0/1; q of two layers, or of three with the middle one possibly zero, least t-exponent 0, some layer nonzero at t = -1. Kept when the counter returns exactly the two factorizations {B, q} and {p, n q}; deduplicated on F. SIXTEEN: for k odd in 3..41, every 0/1 layer with least exponent 0 and exponents to 60 of two terms (a control), and of four terms with r(-1) != 0, tested for n r >= 0; the layers (1 + t)(1 + t^a), a = 2..29, a second control. PREDICTIONS (fixed before the engine). P1 CONTROL: the six-term identity has 2 atomic factorizations, Newt dimension 1, delta 1; the escape has delta 1 at dimension 2. P2 EDGE: every family instance is 0/1 with ten terms and at least two atomic factorizations; every pair of them reads delta 1; the independent choices have dimension 2, the parallel one and every sporadic lift dimension 1. P3 WITNESS: both menu products agree; 12 terms, 0/1; exactly 2 atomic factorizations; Z-factors x0 + x1, x0 + 1 and a five-term n with a negative coefficient and a two-dimensional polygon; product dimension 2; delta 2; no edge normal of Newt(n) is an edge normal of Newt(p) or Newt(q). P4 SCAN: the scan and the counter agree at every pair; both verdicts occur; the clause q = p decides at least one pair ({2,16} against {2,4}); the witness pair is among the non-unique. P5 LAW: the law and separation agree at every face read, in both directions; the law's delta equals the engine's at every object; the fourteen-term specimen reads delta 2 with two faces where in_w(n) is not a monomial and P = Q, the escape delta 1 with one. P6 LINE: at least one delta = 2 object; delta = 2 exactly when both outermost layers are monomial multiples of 1 + t, at every object; no delta = 2 object has twelve terms. P7 SIXTEEN (fixed before its own section ran): no four-term 0/1 layer r with least exponent 0 and r(-1) != 0 has n r >= 0, for k odd in 3..41 and exponents to 60; controls: a two-term layer passes only at 1 + t, and the layers (1 + t)(1 + t^a) pass [ruled on audit: checked at all 560 (k, a), a = 2..29 at each odd k]. KILLS. A delta other than 1 in EDGE kills (A). A scan verdict against the counter kills (B). A face where the law and separation disagree kills (C), which is proved, so it is read as an engine fault first. A delta = 2 object at twelve terms in LINE kills (E), a passing layer in P7 kills (F); a disagreement with the closed reading kills (D). A witness with delta below 2, or with a third factorization, retracts the witness. P1 is the positive control: if it misses, nothing after it is read. FINDINGS. Every prediction held and no kill fired. P1 the six-term identity reads 2 atomic factorizations, Newt dimension 1, delta 1; the escape reads delta 1 at dimension 2. P2 F1 and F2 at a, b = (0,1), (1,0); (1,1), (0,1); (3,1), (1,2) are 0/1 with ten terms, two factorizations, dimension 2, delta 1; at the parallel choice (1,0), (2,0) and at the three sporadic lifts, dimension 1 and delta 1. P3 {4,6} x {3,4,8,9,18,24} = {2,4} x {6,8,9,24,27,36}; the core has 12 terms, all 1, and exactly 2 atomic factorizations; Z-factors x0 + x1, x0 + 1 and n = x0^2 x1 + x0^2 - x0 x1 + x1^2 + x1, five terms of rank 2; the polygon's 16 proper faces (8 vertices, 8 edges) separate nowhere, delta 2 at dimension 2. The normals where an initial form is not a monomial: n (1,0), (-1,0), (1,2), (-1,-2); p (0,1), (0,-1); q (1,1), (-1,-1); disjoint. P4 20 two-factor seeds (none with both factors negative, so the sibling clause is proved and not exercised) against 4049 menus of {2..14} with an irreducible core: 80980 pairs, 80568 unique and 412 factoring two ways, 106 decided by q = p, 0 disagreements; the witness pair among the 412. P5 the 412 give 404 distinct products: 207 of Newt dimension at most 2 read face by face, 197 past it left unread by the engine, every one of the 197 with a menu product that is not 0/1 (among them {2,3,6,16} x {2,3,4,5,10}), while the 78 with a 0/1 menu product all sit at dimension at most 2; with the witness, the two specimens and the 924 line products factoring two ways, no face disagrees with the law and no delta differs from the law's. The escape reads delta 1 with one accident face; the fourteen-term specimen, whose menu products agree, delta 2 with two. P6 the line box holds 5 admissible B and 924 products factoring two ways (64 candidates dropped by the counter); delta 2 at 86, 52 of 14 terms and 34 of 18, none of 12; the closed reading holds at all 924. P7 a two-term layer passes only at m = 1, all 560 of the (k, a) pairs pass with r = (1 + t)(1 + t^a), and of the 21,170 four-term layers with r(-1) != 0, tried at each of the 20 values of k (423,400 pairs), none passes: (F) stands. RUN RECORD. python faces.py: 10 of 10 checks, 59.5 s, peak commit 69.0 MB (8 of 8 before P7). The first run passed 8 of 8 with a vacuous witness check: the normals of a segment were read off the face engine, which lists only a segment's two vertices, so p and q reported none and "disjoint" held by emptiness. A segment's two normals are now computed from its direction; the disjointness holds on the real sets. The frame split of the scan's products factoring two ways was added after the second run. """ import os import sys import time from itertools import combinations from math import gcd os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") from collide import ( # noqa: E402 GENS, Dp, all_atomic_lists, descent, dkey, dmul, face_multisets, face_weights, menu_factors, negative, nonneg, prod, rank, zdir, zfactors) CHECKS = [] R = len(GENS) D_LINE = 5 def check(name, ok, detail=""): CHECKS.append(bool(ok)) tag = "ok " if ok else "FAIL" print(f" [{tag}] {name}" + (f" ({detail})" if detail else "")) def control(name, ok, detail=""): check(name, ok, detail) if not ok: print(" control failed: run stopped") raise SystemExit(1) def section(title): print() print(title) # ------------------------------------------------------------ polynomials def ev(*e): """An exponent vector with the given leading entries.""" return tuple(list(e) + [0] * (R - len(e))) def mono(*e): return Dp({ev(*e): 1}) def dp(pairs): """A Dp from {(i, j): c} over the first two variables.""" return Dp({ev(i, j): c for (i, j), c in pairs.items()}) def uni(exps, var=0): """A 0/1 polynomial in one variable from its exponents.""" return Dp({ev(*([0] * var + [k])): 1 for k in exps}) def sub(x_exp, shift, exps): """A 0/1 polynomial in X = x^x_exp from its exponents in X, times the monomial x^shift; vectors of two entries.""" return Dp({ev(shift[0] + k * x_exp[0], shift[1] + k * x_exp[1]): 1 for k in exps}) def add(*ps): out = {} for p in ps: for e, c in p.d.items(): out[e] = out.get(e, 0) + c return Dp(out) def terms(p): return len(p.d) def zero_one(p): return all(c == 1 for c in p.d.values()) def prim_init(f, w): """The initial form of f at the weight w (minimizing), divided by its monomial gcd, as a frozenset of (exponent, coefficient).""" vals = {e: sum(a * b for a, b in zip(w, e)) for e in f.d} lo = min(vals.values()) init = [(e, c) for e, c in f.d.items() if vals[e] == lo] base = [min(e[i] for e, _ in init) for i in range(R)] return frozenset((tuple(a - b for a, b in zip(e, base)), c) for e, c in init) def is_mono(f, w): return len(prim_init(f, w)) == 1 def face_read(p, n, q): """Every face of the shared-shape factorizations {p n, q} / {p, n q}: (face dimension, separates, law, accident). The accident is a face where in_w(n) is not a monomial and p, q have the same initial form at w after division by monomial gcd (prim_init).""" side_a, side_b = [p * n, q], [p, n * q] points = list((p * n * q).d) dim, faces = face_weights(points) out = [] for fdim, w in faces: sep = face_multisets(side_a, w) != face_multisets(side_b, w) live = not is_mono(n, w) same = prim_init(p, w) == prim_init(q, w) out.append((fdim, sep, live and not same, live and same)) return dim, out def law_delta(dim, reads): fired = [fdim for fdim, _, law, _ in reads if law] return min(fired) if fired else dim def shared_delta(p, n, q): return descent([p * n, q], [p, n * q]) def edge_normals(f): """The primitive normals w of Newt(f), f in the first two variables, at which in_w(f) is not a monomial: a polygon's edge normals, or the two normals of a segment.""" pts = [e for e in f.d] if rank(pts) == 1: d = next(tuple(a - b for a, b in zip(e, pts[0])) for e in pts if e != pts[0]) g = gcd(d[0], d[1]) return {(-d[1] // g, d[0] // g), (d[1] // g, -d[0] // g)} out = set() for fdim, w in face_weights(pts)[1]: if fdim == 1: g = gcd(w[0], w[1]) out.add((w[0] // g, w[1] // g)) return out # ------------------------------------------------------------ sections def section_control(): section("CONTROL: the six-term identity and the escape") lhs = [uni((0, 1)), uni((0, 2, 4))] facts = all_atomic_lists(zfactors(prod(lhs))) pts = list(prod(lhs).d) d6 = descent(facts[0], facts[1]) if len(facts) == 2 else (-1, -1) print(f" (1+x)(1+x^2+x^4): {len(facts)} atomic factorizations, " f"(delta, dimension) {d6}, Newt dimension {rank(pts)}") p, n = uni((0, 1)), dp({(0, 0): 1, (1, 0): -1, (2, 0): 1}) q = add(uni((0, 1)), dp({(0, 1): 1, (1, 1): 1, (2, 1): 1})) de = shared_delta(p, n, q) print(f" the escape (1+t^3)((1+t) + y(1+t+t^2)): (delta, dim) {de}") control("P1 control: 2 factorizations at delta 1, escape delta 1", len(facts) == 2 and d6 == (1, 1) and de == (1, 2)) def section_edge(): section("EDGE: the ten-term classification graded") rows = [] for a, b, want in (((0, 1), (1, 0), 2), ((1, 1), (0, 1), 2), ((3, 1), (1, 2), 2), ((1, 0), (2, 0), 1)): A = lambda k, a=a, b=b: (k[0] * a[0] + k[1] * b[0], # noqa: E731 k[0] * a[1] + k[1] * b[1]) # exponents written as (coefficient of a, coefficient of b) f1 = [[(0, 0), (0, 3)], [(0, 0), (1, 0), (0, 1), (1, 1), (1, 2)]] f2 = [[(0, 0), (0, 3)], [(0, 0), (1, 0), (0, 1), (1, 1), (0, 2)]] for name, fam in (("F1", f1), ("F2", f2)): blocks = [Dp({ev(*A(k)): 1 for k in blk}) for blk in fam] rows.append((f"{name} a={a} b={b}", prod(blocks), want)) sporadic = { "S1": [(0, 1), (0, 2, 4, 6, 8)], "S2": [(0, 1), (0, 4, 6, 8, 12)], "S3": [(0, 3), (0, 2, 4, 6, 8)], } for name, (u, v) in sporadic.items(): blocks = [sub((1, 2), (0, 3), u), sub((1, 2), (0, 0), v)] rows.append((f"{name} X=x0 x1^2", prod(blocks), 1)) ok = True for name, whole, want in rows: facts = all_atomic_lists(zfactors(whole)) dim = rank(list(whole.d)) deltas = sorted({descent(f, g)[0] for f, g in combinations(facts, 2)}) good = zero_one(whole) and terms(whole) == 10 and len(facts) >= 2 good = good and deltas == [1] and dim == want ok = ok and good print(f" {name:26s} terms {terms(whole)}, factorizations " f"{len(facts)}, dimension {dim}, deltas {deltas}") check("P2 every ten-term collision reads delta 1 at its dimension", ok) WITNESS = ((4, 6), (3, 4, 8, 9, 18, 24), (2, 4), (6, 8, 9, 24, 27, 36)) def section_witness(): section("WITNESS: a twelve-term collision no proper face separates") a, b, c, d = WITNESS same = dmul(zdir(a), zdir(b)) == dmul(zdir(c), zdir(d)) fs = menu_factors(a) + menu_factors(b) whole = prod(fs) facts = all_atomic_lists(fs) print(f" {a} x {b} = {c} x {d}: {same}; core terms {terms(whole)}" f", 0/1 {zero_one(whole)}, atomic factorizations {len(facts)}") for f in fs: print(f" Z-factor {f.as_expr()}") n = next(f for f in fs if negative(f)) rest = [f for f in fs if not negative(f)] q = menu_factors(a)[0] p = next(f for f in rest if f != q) dim, reads = face_read(p, n, q) delta = shared_delta(p, n, q) nn, pn, qn = edge_normals(n), edge_normals(p), edge_normals(q) print(f" p = {p.as_expr()}, q = {q.as_expr()}, n has " f"{terms(n)} terms and rank {rank(list(n.d))}") print(f" faces {len(reads)} (vertices " f"{sum(1 for r in reads if r[0] == 0)}, edges " f"{sum(1 for r in reads if r[0] == 1)}), separating " f"{sum(1 for r in reads if r[1])}; (delta, dim) {delta}") print(f" edge normals: n {sorted(nn)}, p {sorted(pn)}, " f"q {sorted(qn)}") check("P3 the witness: two factorizations, delta 2, no shared normal", same and terms(whole) == 12 and zero_one(whole) and len(facts) == 2 and len(fs) == 3 and terms(n) == 5 and rank(list(n.d)) == 2 and delta == (2, 2) and not (nn & (pn | qn))) return p, n, q def two_factor_seeds(): out = [] for m in combinations(range(2, 65), 2): out.append(m) out.append((2, 8, 32)) out += list(combinations(range(2, 21), 4)) out.append(WITNESS[1]) seeds, sibling = [], [] for m in out: if len(m) == 2 and not negative_quick(m): continue fs = menu_factors(m) if len(fs) != 2: continue neg = [f for f in fs if negative(f)] if len(neg) == 1: seeds.append(m) elif len(neg) == 2: sibling.append(m) return seeds, sibling def negative_quick(m): """A size-2 menu is a seed iff its d has an odd prime factor (collide.py); used only to skip factoring the rest.""" from collide import size2_criterion return size2_criterion(m) def section_scan(): section("SCAN: two-factor seeds against irreducible cores") t0 = time.time() seeds, sibling = two_factor_seeds() partners = [m for s in range(2, 7) for m in combinations(range(2, 15), s) if len(menu_factors(m)) == 1] print(f" {len(seeds)} two-factor seeds, {len(sibling)} with both " f"factors negative, {len(partners)} partners " f"[{time.time() - t0:.1f} s]") bad, verdicts, by_clause, found = 0, [0, 0], 0, [] for s in seeds: fs = menu_factors(s) n = next(f for f in fs if negative(f)) p = next(f for f in fs if not negative(f)) for m in partners: q = menu_factors(m)[0] scan = nonneg(n * q) and q != p if nonneg(n * q) and q == p: by_clause += 1 count = len(all_atomic_lists([n, p, q])) bad += scan != (count == 2) verdicts[scan] += 1 if scan: found.append((s, m, p, n, q)) for s in sibling: fs = menu_factors(s) for m in partners: bad += len(all_atomic_lists(fs + menu_factors(m))) != 1 print(f" pairs {sum(verdicts)}: unique {verdicts[0]}, two ways " f"{verdicts[1]}; decided by q = p {by_clause}; disagreements " f"{bad} [{time.time() - t0:.1f} s]") hit = any(s == WITNESS[1] and m == WITNESS[0] for s, m, *_ in found) check("P4 the scan agrees with the counter at every pair", bad == 0 and min(verdicts) > 0 and by_clause > 0 and hit) return found def law_over(objects, label): """Read every face of every (p, n, q); return disagreements, the delta mismatches and the objects read.""" bad = mism = read = skipped = 0 for p, n, q in objects: if rank(list((p * n * q).d)) > 2: skipped += 1 continue dim, reads = face_read(p, n, q) read += 1 bad += sum(1 for _, sep, law, _ in reads if sep != law) mism += law_delta(dim, reads) != shared_delta(p, n, q)[0] print(f" {label}: objects read {read}, skipped at dimension > 2 " f"{skipped}, face disagreements {bad}, delta mismatches {mism}") return bad, mism, read def section_law(found, witness): section("LAW: every face against the face law") seen, objs, high, split = set(), [], None, {} for s, m, p, n, q in found: whole = dmul(zdir(s), zdir(m)) key = dkey(whole) if key not in seen: seen.add(key) objs.append((p, n, q)) past = rank(list((p * n * q).d)) > 2 frame = set(whole.values()) == {1} split[past, frame] = split.get((past, frame), 0) + 1 if high is None and past: high = (s, m, frame) print(f" (past dimension 2, menu product 0/1): count " f"{dict(sorted(split.items()))}") print(f" first past dimension 2, and whether 0/1: {high}") b1, m1, r1 = law_over(objs, "scan collisions") b2, m2, r2 = law_over([witness], "the witness") p, n = uni((0, 1)), dp({(0, 0): 1, (1, 0): -1, (2, 0): 1}) esc = add(uni((0, 1)), dp({(0, 1): 1, (1, 1): 1, (2, 1): 1})) q14 = add(esc, dp({(0, 2): 1, (1, 2): 1})) same = dmul(zdir((2, 16)), zdir((2, 4, 6, 12, 18, 24, 36))) == dmul( zdir((2, 4)), zdir((2, 6, 16, 18, 24, 96, 144))) out = [] for name, q in (("escape", esc), ("fourteen", q14)): dim, reads = face_read(p, n, q) acc = sum(1 for r in reads if r[3]) delta = shared_delta(p, n, q) facts = len(all_atomic_lists(zfactors(p * n * q))) out.append((delta[0], acc, facts)) print(f" {name}: terms {terms(p * n * q)}, factorizations " f"{facts}, (delta, dim) {delta}, accident faces {acc}") b3, m3, r3 = law_over([(p, n, esc), (p, n, q14)], "the two specimens") core = prod(menu_factors((2, 16)) + menu_factors((2, 4, 6, 12, 18, 24, 36))) print(f" the fourteen-term specimen's menu core is p n q: " f"{core == p * n * q14}") check("P5 the law agrees with separation at every face read", b1 + b2 + b3 == 0 and m1 + m2 + m3 == 0 and r1 > 0 and (r2, r3) == (1, 2)) check("P5 the fourteen-term specimen: delta 2 through two accidents", same and core == p * n * q14 and out == [(1, 1, 2), (2, 2, 2)]) def line_objects(): D = D_LINE p = uni((0, 1)) bs = [] for mask in range(1, 1 << (D + 1), 2): ex = [k for k in range(D + 1) if mask >> k & 1] if len(ex) < 2 or sum((-1) ** k for k in ex) != 0: continue B = uni(ex) n = Dp({}) rem = dict(B.d) for k in range(max(ex), 0, -1): c = rem.get(ev(k), 0) if c: n.d[ev(k - 1)] = c rem[ev(k - 1)] = rem.get(ev(k - 1), 0) - c rem[ev(k)] = 0 assert all(v == 0 for v in rem.values()) if negative(n): bs.append((B, n)) out, seen, dropped = [], set(), 0 for B, n in bs: layers = [] for mask in range(1, 1 << (D + 1)): r = uni([k for k in range(D + 1) if mask >> k & 1]) if nonneg(n * r) and zero_one(B * r): layers.append(mask) cands = [(a, b) for a in layers for b in layers] cands += [(a, m, b) for a in layers for m in [0] + layers for b in layers] for c in cands: if min((mk & -mk).bit_length() for mk in c if mk) != 1: continue if all(sum((-1) ** k for k in range(D + 1) if mk >> k & 1) == 0 for mk in c): continue q = Dp({ev(k, j): 1 for j, mk in enumerate(c) for k in range(D + 1) if mk >> k & 1}) F = B * q key = frozenset(F.d) if key in seen: continue seen.add(key) facts = all_atomic_lists(zfactors(F)) want = {frozenset([B, q]), frozenset([p, n * q])} got = {frozenset(f) for f in facts} if got != want: dropped += 1 continue out.append((p, n, q, c, terms(F))) return bs, out, dropped def section_line(): section(f"LINE: p = 1 + t, n univariate, degrees at most {D_LINE}") t0 = time.time() bs, objs, dropped = line_objects() closed_bad, twelve, spectrum = 0, 0, {} for p_, n, q, c, T in objs: delta = shared_delta(p_, n, q)[0] outer = [c[0], c[-1]] mult = all(mk & (mk >> 1) and bin(mk).count("1") == 2 and mk == (mk & -mk) * 3 for mk in outer) closed_bad += (delta == 2) != mult if delta == 2: spectrum[T] = spectrum.get(T, 0) + 1 twelve += T == 12 print(f" admissible B {len(bs)}, collisions {len(objs)}, " f"candidates dropped by the counter {dropped} " f"[{time.time() - t0:.1f} s]") print(f" delta 2 by term count {dict(sorted(spectrum.items()))}; " f"closed-reading disagreements {closed_bad}") b, m, r = law_over([(p_, n, q) for p_, n, q, _, _ in objs], "line collisions") check("P6 the closed reading holds and twelve is empty", sum(spectrum.values()) > 0 and closed_bad == 0 and twelve == 0) check("P5 the law agrees at every face of every line collision", b == 0 and m == 0 and r == len(objs) > 0) def layer_ok(k, exps): """n r >= 0 for n = (1 + t^k)/(1 + t) and r the 0/1 layer on exps.""" c = [0] * (k + max(exps)) for e in exps: for i in range(k): c[e + i] += (-1) ** i return min(c) >= 0 def section_sixteen(): section("SIXTEEN: the four-term middle layer of (F), k odd 3..41, " "exponents to 60") ks = range(3, 42, 2) two = sorted({m for k in ks for m in range(1, 61) if layer_ok(k, (0, m))}) mult = sum(layer_ok(k, (0, 1, a, a + 1)) for k in ks for a in range(2, 30)) tested, passing = 0, 0 for k in ks: for rest in combinations(range(1, 61), 3): exps = (0,) + rest if sum((-1) ** e for e in exps) == 0: continue tested += 1 passing += layer_ok(k, exps) print(f" two-term layers passing at m = {two}; (1 + t)(1 + t^a) " f"passing at {mult} (k, a); four-term layers with r(-1) != 0 " f"tested {tested}, passing {passing}") check("P7 the controls: two-term only at 1 + t, every " "(1 + t)(1 + t^a) passes", two == [1] and mult == len(ks) * 28) check("P7 no four-term layer with r(-1) != 0 passes", passing == 0) def main(): t0 = time.time() section_control() section_edge() witness = section_witness() found = section_scan() section_law(found, witness) section_line() section_sixteen() print() n, ok = len(CHECKS), sum(CHECKS) print(f"{ok} of {n} checks pass [{time.time() - t0:.1f} s]") return 0 if ok == n else 1 if __name__ == "__main__": sys.exit(main())