"""quadrinomial.py -- a four-term 0/1 polynomial that factors into two non-monomial factors carries a binomial factor, and off a line every factor vanishes on roots of unity. QUESTION. The torsion split asks whether a seed's negative factor can avoid every point of roots of unity. At size 3 the answer is decided on a line by Ljunggren's theorem (Math. Scand. 8 (1960) 65-70). What does a four-term 0/1 polynomial P look like when it factors over Z, in any number of variables, and can a non-collinear four-member seed be free? THE ARGUMENT (written before the engine). Let P = m_1 + m_2 + m_3 + m_4, monomials with exponent vectors e_1..e_4, and P = g h over Z with neither factor a monomial. (0) AFFINE DIMENSION. At dimension 3 the half-size law (halfsize.py) forbids a factorization, 4 < 2 * 3. So P lies on a line or in a plane, and the frame's unimodular map puts it in one or two variables. (1) THE PAIRING LEMMA. Four complex numbers of modulus 1 summing to 0 are two antipodal pairs. If z_1 + z_2 = 0 then z_3 + z_4 = 0. Otherwise s = z_1 + z_2 != 0, and the unordered pair of unit numbers with sum s is unique (the circle meets the perpendicular to s through s/2 in two points), so {z_3, z_4} = {-z_1, -z_2}. So at any root of P on the unit torus some pairing {i, j}, {k, l} has m_i / m_j = -1 = m_k / m_l there. (2) HAJOS'S BOUND. A nonzero root z of a T-term polynomial sum c_a x^(n_a) has multiplicity at most T - 1: at multiplicity T the operators (x d/dx)^r, r = 0..T - 1, all kill it, a Vandermonde system in the distinct n_a with the nonzero unknowns c_a z^(n_a). (3) MILLS'S THEOREM (Math. Scand. 57 (1985) 44-50, Theorem 2, read at source): for F = x^n + e_1 x^m + e_2 x^p + e_3, n > m > p > 0, e_i = +-1, the part B of F whose roots are no roots of unity is irreducible except for four forms, each with e_3 = -1. So an all-plus quadrinomial's non-cyclotomic part is 1 or irreducible. (4) THE LINE. P = 1 + x^a + x^b + x^c reducible has two non-unit factors, so by (3) a cyclotomic one, and a root of unity zeta with P(zeta) = 0. By (1) P = x^i (1 + x^s) + x^k (1 + x^t), s, t > 0, with zeta^s = zeta^t = -1, so s and t have one 2-adic valuation, and with d = gcd(s, t) both s/d and t/d are odd: 1 + x^d divides both halves. (5) THE PLANE. Choose coordinates in which neither g's nor h's support lies on a horizontal line. For K beyond the x-width of P's support, y -> x^K is injective on it and on g's and h's, so P_K = g_K h_K is an all-plus quadrinomial with two non-monomial factors, and by (3) one of them has only roots of unity for roots. One factor, say g, does so for infinitely many K. The degree of g_K past its lowest term grows with K, so by (2) g_K has unboundedly many distinct roots zeta, each a zero of P at the unit-torus point (zeta, zeta^K). For a pairing whose differences u = e_i - e_j and u' = e_k - e_l are not parallel, zeta^A = -1 = zeta^C with A = u . (1, K), C = u' . (1, K) makes zeta^(2 gcd(A, C)) = 1, and gcd(A, C) divides det(u, u') != 0: such a pairing holds at no more than 2 |det| roots, whatever K. So for large K some root sits on a pairing with parallel differences, u = s w and u' = t w along one primitive w, and omega = zeta^(w . (1, K)) has omega^s = omega^t = -1. As in (4): P = m_j (1 + w^s) + m_l (1 + w^t) with s/d and t/d odd, d = gcd(s, t). THE COFACTOR THEOREM: a four-term 0/1 polynomial that factors over Z into two non-monomial factors is divisible by 1 + u for a monomial u; in fact P = m (1 + W)(q_s'(W) + v q_t'(W)) with W = w^d, s' = s/d and t' = t/d odd, v = m_l / m_j and q_n(W) = 1 - W + ... + W^(n - 1). (6) THE SIZE-4 CLOSURE. Off a line v is independent of W. The factors of 1 + W and of c = gcd(q_s', q_t') are cyclotomic in W and vanish at roots of unity. If s' = t' the rest is 1 + v, likewise. If s' != t', R = a(W) + v b(W) with a = q_s'/c and b = q_t'/c coprime, squarefree, not both constant. Write v = x^i y^j, j >= 1, in coordinates with W = x^d. If a is not constant, R is Eisenstein in y at any prime of Q[x, 1/x] dividing a once (a has constant term 1, so x does not divide it); if a = 1, then y^-j R is Eisenstein in 1/y at a prime factor of b. R is primitive, so Z-irreducible, and at the torus point x = 1, y^j = -1, where W = 1 and v = -1, R = a(1) - b(1) = (1 - 1)/c(1) = 0, c(1) dividing q_s'(1) = 1. So EVERY Z-FACTOR OF A REDUCIBLE NON-COLLINEAR FOUR-TERM 0/1 POLYNOMIAL IS TORSION-ROOTED, and a four-member seed off a line is rooted. On a line v can be a power of W and the character is gone: 1 + x^3 + x^4 + x^5 = (1 + x)(1 - x + x^2 + x^4) is free. (7) TWO FREE SEEDS AT SIZE 6. {2, 3, 4, 8, 16, 24} has core (1 + x)[x (1 + x^2) + y (1 - x + x^2)], the bracket linear in y with coprime coefficients, so irreducible, and negative. At a torus point |y| = 1 forces |1 + x^2| = |1 - x + x^2| with |x| = 1, i.e. |2 cos theta| = |2 cos theta - 1|, so cos theta = 1/4 and x is a root of 2x^2 - x + 2, no algebraic integer, no root of unity. So the bracket meets no torsion point and the seed is free, mixed beside the rooted 1 + x, at size 6; its mirror {2, 3, 6, 12, 16, 24} likewise. DESIGN. Configurations are sets of exponent vectors, factored with sympy after collide.py's frame is applied by hand (min subtracted). CONTROL: (1 + x)(1 + y) reducible with a binomial factor; 1 + x + y irreducible; Mills's four forms at r = 1 each with two non-cyclotomic factors. PAIRING: every 4-tuple of 24th roots of unity summing to 0, each read for an antipodal pairing. PLANE: every 4-subset of [0, 4]^2 with least coordinates 0, non-collinear: reducible count; every reducible one read for the theorem's shape (a pairing along one primitive w with s/d, t/d odd) and a binomial Z-factor; every Z-factor searched for a zero at a pair of N-th roots of unity, N <= 24. RANK3: every 4-subset of [0, 2]^3 with least coordinates 0 at affine dimension 3: reducible count. LINE: every 1 + x^a + x^b + x^c, c <= 40: reducible count, shape and binomial factor, non-cyclotomic factors at most one, seeds by torsion class; 1 + x^3 + x^4 + x^5 among the free. FREE6: the two menus' cores factored; the bracket negative and irreducible; no zero at a pair of N-th roots, N <= 60. PREDICTIONS (fixed before the engine). P1 CONTROL: as named. P2 PAIRING: every vanishing tuple pairs antipodally. P3 PLANE: every reducible configuration has the shape and a binomial factor, and every Z-factor a torsion zero at N <= 24. P4 RANK3: 0 reducible. P5 LINE: every reducible quadrinomial has the shape and a binomial factor; at most one non-cyclotomic factor each; free seeds exist, 1 + x^3 + x^4 + x^5 among them. P6 FREE6: both cores (1 + x) times a negative irreducible bracket with no torsion zero at N <= 60. KILLS. P1 is the positive control: if it misses, nothing after it is read. A vanishing tuple without an antipodal pairing kills (1). A reducible configuration without the shape kills (4) or (5); a factor with no torsion zero off a line is read before it kills (6), since the search is bounded, and names the order it needs. A reducible rank-3 configuration kills (0). Two non-cyclotomic factors in a line quadrinomial contradicts the cited theorem. FINDINGS. Every prediction held and no kill fired. P1 (1 + x)(1 + y) has 2 factors, both binomials; 1 + x + y has 1; Mills's four forms at r = 1 have 2 non-cyclotomic factors each. P2 69 vanishing sums of four 24th roots of unity, the first root 1 and the other three an ordered triple, every one two antipodal pairs. P3 4,764 non-collinear configurations in [0, 4]^2, 296 reducible, 149 of them seeds; every reducible one has the shape and a binomial factor, and every factor a torsion zero, the largest order needed 8. P4 8,424 configurations of [0, 2]^3 at dimension 3, 0 reducible. P5 9,880 quadrinomials to degree 40, 4,306 reducible, every one with the shape and a binomial factor, at most one non-cyclotomic factor in any; seeds 366 rooted, 3,926 mixed, 0 free outright, 1 + x^3 + x^4 + x^5 among the free. None can be free outright: Mills gives every reducible one a cyclotomic factor. P6 {2, 3, 4, 8, 16, 24} factors as x0 + 1 times x0^3 + x0^2 x1 - x0 x1 + x0 + x1, and {2, 3, 6, 12, 16, 24} as x0 + 1 times x0^3 + x0^2 x1 - x0^2 + x0 + x1; each has one negative factor and no torsion zero at N <= 60: free, and mixed beside the rooted x0 + 1. Tiers: the cofactor theorem and the size-4 closure are theorems, proved above with Mills's theorem cited; the two free seeds at size 6 are a theorem by exhibit, proved by hand; the boxes are their falsification attempt, toy-scale. RUN RECORD. 9 of 9 checks, 11.4 s, peak commit 51 MB. The first run missed P1 at 8 of 9 on a transcription error in the control, Mills's second form typed with x^2 for x; corrected against the paper, every other print unchanged. An audit then restored MIXED to mean a free seed with any torsion-rooted factor; the line's split moved from 1,136 mixed and 2,790 free outright to 3,926 and 0. """ import cmath import os import sys import time from itertools import combinations, product from math import gcd os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") from sympy import Poly, symbols # noqa: E402 HERE = os.path.dirname(os.path.abspath(__file__)) sys.path.insert(0, HERE) from collide import menu_poly, vec, zfactors, negative # noqa: E402 CHECKS = [] X, Y, Z = symbols("x y z") 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) def poly(points, gens): return Poly.from_dict({p: 1 for p in points}, *gens) def factors(p): """Non-monomial Z-irreducible factors with multiplicity, normed.""" _, fl = p.factor_list() out = [] for q, e in fl: if len(q.terms()) < 2: continue if q.LC() < 0: q = -q out += [q] * e return out def dim(points): base = points[0] rows = [[a - b for a, b in zip(p, base)] for p in points[1:]] from sympy import Matrix return Matrix(rows).rank() def content(u): g = 0 for a in u: g = gcd(g, abs(a)) return g def shape(points): """The theorem's shape: a pairing {i, j}, {k, l} whose differences are s w and t w along one primitive w with s/d and t/d odd.""" for (i, j), (k, l) in (((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2))): u = [a - b for a, b in zip(points[i], points[j])] v = [a - b for a, b in zip(points[k], points[l])] s, t = content(u), content(v) wu = tuple(a // s for a in u) wv = tuple(a // t for a in v) if wu != wv and wu != tuple(-a for a in wv): continue d = gcd(s, t) if (s // d) % 2 and (t // d) % 2: return True return False def torsion_zero(q, top): """Least N <= top with q vanishing at a point of N-th roots of unity, else None (numerical, |q| < 1e-9).""" terms = q.terms() nv = len(terms[0][0]) for n in range(1, top + 1): roots = [cmath.exp(2j * cmath.pi * k / n) for k in range(n)] for pt in product(range(n), repeat=nv): val = 0 for e, c in terms: z = 1 for k, ex in zip(pt, e): z *= roots[(k * ex) % n] val += int(c) * z if abs(val) < 1e-9: return n return None def section_control(): section("CONTROL") a = factors(poly([(0, 0), (1, 0), (0, 1), (1, 1)], (X, Y))) b = factors(poly([(0, 0), (1, 0), (0, 1)], (X, Y))) print(f" (1 + x)(1 + y): {len(a)} factors; 1 + x + y: {len(b)}") mills = [Poly(X ** 8 + X ** 7 + X - 1, X), Poly(X ** 8 - X ** 7 - X - 1, X), Poly(X ** 8 + X ** 4 + X ** 2 - 1, X), Poly(X ** 8 - X ** 6 - X ** 4 - 1, X)] noncyc = [sum(1 for q in factors(m) if not q.is_cyclotomic) for m in mills] print(f" Mills's four forms at r = 1: non-cyclotomic factors " f"{noncyc}") control("P1 controls", len(a) == 2 and len(b) == 1 and all(len(q.terms()) == 2 for q in a) and noncyc == [2] * 4) def section_pairing(n=24): section(f"PAIRING -- vanishing sums of four {n}th roots of unity") roots = [cmath.exp(2j * cmath.pi * k / n) for k in range(n)] zero = bad = 0 for t in product(range(n), repeat=3): z = 1 + sum(roots[k] for k in t) if abs(z) > 1e-9: continue zero += 1 ks = (0,) + t if not any((ks[i] - ks[j]) % n == n // 2 and (ks[k] - ks[l]) % n == n // 2 for (i, j), (k, l) in (((0, 1), (2, 3)), ((0, 2), (1, 3)), ((0, 3), (1, 2)))): bad += 1 print(f" {zero} vanishing tuples with first root 1, {bad} unpaired") check("P2 every vanishing tuple pairs antipodally", zero and bad == 0) def section_plane(box=4, top=24): section(f"PLANE -- every 4-subset of [0, {box}]^2, least coordinates 0") grid = [(a, b) for a in range(box + 1) for b in range(box + 1)] configs = red = seeds = noshape = nobin = unrooted = 0 need = 0 for pts in combinations(grid, 4): if min(p[0] for p in pts) or min(p[1] for p in pts): continue if dim(list(pts)) != 2: continue configs += 1 fs = factors(poly(pts, (X, Y))) if len(fs) < 2: continue red += 1 seeds += any(any(c < 0 for c in q.coeffs()) for q in fs) if not shape(list(pts)): noshape += 1 print(f" NO SHAPE: {pts}") if not any(len(q.terms()) == 2 for q in fs): nobin += 1 for q in fs: n = torsion_zero(q, top) if n is None: unrooted += 1 print(f" NO TORSION ZERO <= {top}: {q.as_expr()} in {pts}") else: need = max(need, n) print(f" {configs} configurations, {red} reducible, {seeds} seeds; " f"without the shape {noshape}, without a binomial factor {nobin}," f" factors without a torsion zero {unrooted}; largest N needed " f"{need}") check("P3 every reducible one has the shape and a binomial factor", red and noshape == 0 and nobin == 0) check("P3 every factor has a torsion zero", unrooted == 0) def section_rank3(box=2): section(f"RANK3 -- every 4-subset of [0, {box}]^3 at dimension 3") grid = list(product(range(box + 1), repeat=3)) configs = red = 0 for pts in combinations(grid, 4): if any(min(p[i] for p in pts) for i in range(3)): continue if dim(list(pts)) != 3: continue configs += 1 red += len(factors(poly(pts, (X, Y, Z)))) > 1 print(f" {configs} configurations, {red} reducible") check("P4 dimension 3 is irreducible", configs and red == 0) def section_line(top=40): section(f"LINE -- 1 + x^a + x^b + x^c, c <= {top}") total = red = noshape = nobin = worst = 0 tally = {"rooted": 0, "mixed": 0, "outright": 0} free_names = set() for c in range(3, top + 1): for a, b in combinations(range(1, c), 2): total += 1 fs = factors(poly([(0,), (a,), (b,), (c,)], (X,))) if len(fs) < 2: continue red += 1 if not shape([(0,), (a,), (b,), (c,)]): noshape += 1 if not any(len(q.terms()) == 2 for q in fs): nobin += 1 worst = max(worst, sum(1 for q in fs if not q.is_cyclotomic)) neg = [q.is_cyclotomic for q in fs if any(k < 0 for k in q.coeffs())] if neg: if all(neg): tally["rooted"] += 1 else: rooted = any(q.is_cyclotomic for q in fs) tally["mixed" if rooted else "outright"] += 1 free_names.add((a, b, c)) print(f" {total} quadrinomials, {red} reducible; without the shape " f"{noshape}, without a binomial factor {nobin}; most " f"non-cyclotomic factors {worst}; seeds rooted {tally['rooted']}," f" mixed {tally['mixed']}, free outright {tally['outright']}") check("P5 every reducible one has the shape and a binomial factor", red and noshape == 0 and nobin == 0) check("P5 Mills: at most one non-cyclotomic factor", worst <= 1) check("P5 1 + x^3 + x^4 + x^5 is free", (3, 4, 5) in free_names) def section_free6(top=60): section("FREE6 -- two free seeds at size 6") ok = True for menu in ((2, 3, 4, 8, 16, 24), (2, 3, 6, 12, 16, 24)): fs = zfactors(menu_poly(menu)) neg = [f for f in fs if negative(f)] idx = [i for i, e in enumerate(zip(*[vec(m) for m in menu])) if any(e)] qs = [] for f in neg: d = {tuple(e[i] for i in idx): c for e, c in f.d.items()} lo = [min(e[k] for e in d) for k in range(len(idx))] qs.append(Poly.from_dict({tuple(a - b for a, b in zip(e, lo)): c for e, c in d.items()}, X, Y)) zero = [torsion_zero(q, top) for q in qs] print(f" {menu}: factors {[f.as_expr() for f in fs]}; negative " f"{len(neg)}, torsion zero at N <= {top}: {zero}") pos = [str(f.as_expr()) for f in fs if not negative(f)] ok &= (len(fs) == 2 and len(neg) == 1 and zero == [None] and pos == ["x0 + 1"]) check("P6 both free, no torsion zero found", ok) def main(): t0 = time.time() section_control() section_pairing() section_plane() section_rank3() section_line() section_free6() 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())