"""pentanomial.py -- five terms: a seed with a factor cyclotomic in a monomial carries it negative, a free seed can be mixed, and a seed free of every negative torsion zero is a question about one variable. QUESTION. The torsion split (rooted.py) calls a seed FREE when some negative factor of its core vanishes at no point of roots of unity, MIXED when a free seed's core also carries a torsion-rooted factor, and FREE OUTRIGHT when no factor of its core is torsion-rooted. Sizes 3 and 4 are never free outright (rooted.py, quadrinomial.py), so size 5 is the first place it can occur. Off a line, can a size-5 seed be free at all, what shape must it have, and is its freedom outright a new question or the line's? THE ARGUMENT (written before the engine). P is a 0/1 core with five terms. By the half-size law (halfsize.py) a factorization needs Newton dimension at most 2, so P lies on a line or in a plane. (1) FIVE IS PRIME. P(1, 1) = 5 is the product of its factors' values, so one factor has value +-5 and every other +-1. A non-monomial factor with no negative coefficient has value at least 2, so at most ONE factor is nonnegative, and a reducible core is a seed. (2) THE ROW LEMMA. Let P, off a line, have a factor Phi_n(w) with w a primitive monomial. In coordinates with w = x (a unimodular map) Phi_n(x) divides P exactly when it divides every row P_j(x), the terms of P with y-exponent j. A one-term row never vanishes at a root of unity and P has at least two rows, so the rows have sizes 2 and 3. A binomial row x^a (1 + x^s) vanishing at a primitive n-th root zeta makes zeta^s = -1, so n is even. A trinomial row makes three unit numbers sum to 0, which forces an equilateral triangle (|1 + z| = 1 with |z| = 1 puts z at a primitive cube root), so the two ratios are the primitive cube roots and 3 | n. So 6 | n, n is no prime power, Phi_n(1) = 1, and Phi_n, with constant and leading coefficient 1, has a negative coefficient. EVERY FACTOR OF A NON-COLLINEAR FIVE-TERM CORE THAT IS CYCLOTOMIC IN A MONOMIAL IS NEGATIVE AND TORSION-ROOTED, of order divisible by 6, and the rows in its direction have sizes 2 and 3. (3) SIZE 5 CAN BE MIXED. P = 1 + x^3 + y (1 + x^4 + x^8), rows 1 + x^3 = Phi_2 Phi_6 and 1 + x^4 + x^8 = Phi_3 Phi_6 Phi_12, is Phi_6(x) times R = (1 + x) + y Phi_3(x) Phi_12(x), which is linear in y with coprime coefficients, so irreducible, and negative. At a torus point |y| = 1 needs |1 + x| = |Phi_3(x) Phi_12(x)| with x = e^(i theta); with t = 2 + 2 cos theta, |1 + x|^2 = t, |Phi_3|^2 = (t - 1)^2 and |Phi_12|^2 = (t^2 - 4t + 1)^2, so t is a root of S = (t - 1)^2 (t^2 - 4t + 1)^2 - t. At a root of unity x, t is a totally real algebraic integer, and an irreducible S with a non-real root has no totally real root. So R has no torsion zero and the menu {2, 16, 6, 96, 1536}, core P, is a free seed, mixed beside Phi_6. (4) MANN'S BOUND. In a minimal vanishing sum of t roots of unity (no proper subsum vanishes) every ratio is a root of unity of squarefree order with every prime factor at most t (H. B. Mann, Mathematika 12 (1965) 107-117). The argument, for the record: put the roots in mu_N with one of them 1 and p | N. If p^2 | N, the powers 1..rho^(p-1) of a primitive N-th root rho are a basis of Q(rho) over Q(rho^p), so each coset of mu_(N/p) sums to 0 and minimality leaves one coset: N drops to N/p. If p || N, the only relation among a primitive p-th root's powers over Q(zeta_(N/p)) is their sum, so the p coset sums are equal; zero forces one coset as before, and nonzero needs all p cosets filled, p <= t. At t = 5 every ratio in a minimal part is a 30th root of unity, and a vanishing five-term sum is minimal or a pair beside a triple. (5) THE DETERMINANT BOUND. At a zero (zeta, zeta^K) of P, zeta a root of unity, write A_u = u . (1, K) for a difference u of two exponent vectors of P. Within a minimal part zeta^(30 A_u) = 1 for each of its differences. If two of the constrained differences u, u' are not parallel, zeta^(30 g) = 1 with g = gcd(A_u, A_u'), and g divides u'_2 A_u - u_2 A_u' = det(u, u'): so zeta is one of at most 30 |det(u, u')| roots, however large K is. Otherwise every constrained difference lies along one primitive w: the pair and the triple each sit on a line parallel to w, the rows of (2) in that direction, and omega = zeta^(w . (1, K)) is a common root of the binomial row B(W) and the trinomial row T(W). Then gcd(B, T) is a non-constant product of cyclotomic polynomials and gcd(B, T)(w) divides P. So IF P HAS NO FACTOR CYCLOTOMIC IN A MONOMIAL, THE ROOTS OF UNITY zeta WITH P(zeta, zeta^K) = 0 NUMBER AT MOST 30 SUM |det(u, u')| OVER NON-PARALLEL PAIRS, FOR EVERY K. (6) THE SIZE-5 REDUCTION. Let P be a size-5 seed off a line none of whose NEGATIVE factors has a torsion zero. By (2) P has no factor cyclotomic in a monomial. Choose coordinates in which no factor's support lies on a horizontal line; for K past the x-width of P, y -> x^K is injective on P's support and on each factor's, so P_K = P(x, x^K) is a 0/1 pentanomial and every factor stays non-monomial. A negative factor's image has no cyclotomic factor, at any K. With two negative factors the non-cyclotomic part of P_K is reducible. Otherwise P = G H with G nonnegative by (1). G_K has G's t terms and degree span at least K minus a constant, and a nonzero root of a t-term polynomial has multiplicity at most t - 1 (quadrinomial.py, Hajos's bound), so if G_K had only roots of unity for roots it would have at least (K - c)/(t - 1) distinct ones, each a zero of P at (zeta, zeta^K), against (5). So for all large K, G_K has a non-cyclotomic factor beside H_K, and P_K's non-cyclotomic part is reducible. A FREE-OUTRIGHT size-5 seed needs none of this: it has no torsion zero at all, so P_K has no cyclotomic factor and is reducible. Conversely a reducible 0/1 pentanomial with no cyclotomic factor is itself a free-outright seed on a line, by (1). SO A FREE-OUTRIGHT SEED OF SIZE 5 EXISTS IN SOME NUMBER OF VARIABLES EXACTLY WHEN SOME 0/1 PENTANOMIAL IN ONE VARIABLE IS REDUCIBLE WITH NO CYCLOTOMIC FACTOR, and a seed off a line free of every negative torsion zero exists only when some 0/1 pentanomial's non-cyclotomic part is reducible, a NO to the question Filaseta and Solan left open (Math. Scand. 84 (1999) 5-10, read at source); on a line 1 + x + x^3 + x^4 + x^7 = Phi_5 (1 - x^2 + x^3) is such a seed with no NO in it. Their Theorem 1, that such a pentanomial with its irreducible RECIPROCAL factors removed is 1 or irreducible, puts a non-cyclotomic reciprocal factor in any such example. DESIGN. Polynomials are sympy's; a factor is cyclotomic by sympy's own test. CONTROL: P of (3) factors as Phi_6(x) times R; 1 + x + x^2 + y is irreducible; 1 + x + x^3 + x^4 + x^7 = Phi_5(x) (1 - x^2 + x^3), a mixed seed on the line. The rotated exhibit (x -> x y) has a factor cyclotomic in x y, and its zeros (zeta, zeta^K) number 2(K + 1), growing with K: the positive control for (5)'s count. MANN: every multiset of five N-th roots of unity with one of them 1, N = 60 and 84, summing to 0: the minimal ones have every ratio a 30th root of unity; every pair part is antipodal and every triple part equilateral. EXHIBIT: S irreducible over Z with a non-real root; R irreducible and negative; no zero of R at a pair of N-th roots, N <= 60. BOX: every 5-subset of [0, 8]^2 with least coordinates 0, not collinear, through the Gao-Lauder polygon filter (a lattice polygon is a Minkowski sum of two polygons, neither a point (S. Gao and A. G. B. Lauder, Decomposition of polytopes and polynomials, Discrete Comput. Geom. 26 (2001) 89-104), exactly when some 0 <= l'_i <= l_i, neither all 0 nor all l_i, has sum l'_i v_i = 0 over its primitive edge directions v_i of lattice length l_i), one per orbit of the square's eight symmetries, factored. Per seed: a factor cyclotomic in a primitive monomial, the rows in its direction, its order and sign; the other factors' torsion zeros decided (below); the split rooted / mixed, free outright read as a seed with no factor cyclotomic in a monomial. THE TORSION TEST for a factor R = A(x) + v B(x), v a monomial with positive y-exponent in coordinates where the cyclotomic factor is Phi_n(x): R has a torsion zero exactly when some root of unity omega has B(omega) != 0 and -A(omega)/B(omega) a root of unity, since v then takes that value at a torsion point. Such an omega is a root of A(x) A(1/x) - B(x) B(1/x), and in Q(omega) of order m the ratio is a root of unity only if its 2m-th power is 1: the candidates exact, the power read numerically at each, within 10^-7. Where A(x) A(1/x) - B(x) B(1/x) vanishes identically every omega is a candidate and the bracket is left unresolved. BOUND: for every orbit representative that is irreducible, take every 997th, the zeros (zeta, zeta^K) with zeta of order at most 400, at K = 20, 40, 60, against 30 sum |det(u, u')|. LINE: every 1 + x^a + x^b + x^c + x^n, n <= 30: the non-cyclotomic part 1 or irreducible; the non-reciprocal part 1 or irreducible (Filaseta-Solan Theorem 1); seeds rooted / mixed / free outright. SPECIALIZE: every seed of the box at K = 9..12, each a 0/1 pentanomial, its non-cyclotomic part 1 or irreducible. PREDICTIONS (fixed before the engine). P1 CONTROL: as named; the rotated exhibit's count 2(K + 1) at each K. P2 MANN: every minimal part's ratios in mu_30; pairs antipodal, triples equilateral. P3 EXHIBIT: S irreducible with a non-real root; R irreducible, negative, no torsion zero at N <= 60. P4 BOX: every seed has a factor cyclotomic in a primitive monomial, of order divisible by 6 and negative, with rows of sizes 2 and 3 in its direction; free outright 0; the split carried from the legacy census of the same box, 130 seeds, 33 mixed and 97 rooted, a TRANSPLANT of a print made with a different instrument. P5 BOUND: no count above its bound, and no representative's count rising from K = 20 to K = 60. P6 LINE: every non-cyclotomic part 1 or irreducible; every non-reciprocal part 1 or irreducible; free outright 0. P7 SPECIALIZE: every image five terms with coefficients 1; every non-cyclotomic part 1 or irreducible. KILLS. P1 is the positive control: if it misses, nothing after it is read. A minimal five-term sum with a ratio outside mu_30 contradicts (4) and is first read as an instrument error. A seed whose factor cyclotomic in a monomial is positive, or whose rows in its direction are not 2 and 3, kills (2). A count above its bound kills (5). A reducible non-cyclotomic part at P6 or P7 is a Filaseta-Solan example: a finding, named with its factorization. A seed with no factor cyclotomic in a monomial is not a kill; it is where a free-outright seed would sit, and it is printed with its factors [ruled on audit: it fails P4's check that every seed carries one, a prediction missed, not a kill]. RESOURCE. The box's 25.6 million subsets are cut to its cores by the first point's column; the filter and the factoring are the cost, estimated 5 to 8 minutes, under 300 MB. --rehearse runs the box [0, 5]^2 and the line to n = 16. FINDINGS. Every kill held; one clause of P5 missed and is reported. P1 The exhibit factors as x^2 - x + 1 times x^6 y + x^5 y - x^3 y + x y + x + y + 1; 1 + x + x^2 + y is irreducible; 1 + x + x^3 + x^4 + x^7 is x^3 - x^2 + 1 times Phi_5. The rotated exhibit's zeros at K = 20, 40, 60 number 42, 82, 122, which is 2(K + 1). P2 N = 60: 50 vanishing sums, 1 minimal (the pentagon), 49 a pair beside a triple; N = 84: 69, none minimal, 69 split. No ratio of a minimal sum outside mu_30; every pair antipodal, every triple equilateral. P3 S = t^6 - 10t^5 + 35t^4 - 52t^3 + 35t^2 - 11t + 1 is irreducible with 4 real roots of 6; R is irreducible and negative, no torsion zero at N <= 60. The exhibit is free, and mixed. P4 5,263,020 cores, 5,262,736 non-collinear, 1,228,232 through the filter, 154,643 orbit representatives, 130 reducible, every one a seed. Every seed has a factor cyclotomic in a primitive monomial, of order divisible by 6, negative, with rows of sizes 2 and 3 in its direction. Seeds: 97 rooted, 33 mixed, as the transplant said, and none free outright, none lacking a factor cyclotomic in a monomial. P5 155 representatives; the most zeros at K = 20, 40, 60 are 8, 8, 8, none above its bound. The frozen clause "no count rising" MISSED at 6 representatives: the count is bounded but moves with K, since which roots satisfy zeta^(30 A_u) = 1 turns on K's residues (three representatives read 0, 0, 2). The theorem claims the bound only, and the reading was narrowed to it after the miss; the least bound over the sample is 4500 against a most of 8. P6 27,405 pentanomials to n = 30, 3,007 reducible; non-cyclotomic part reducible at 0, non-reciprocal part reducible at 0; seeds 169 rooted, 2,838 mixed, 0 free outright. P7 520 (seed, K) pairs, every image a 0/1 pentanomial of degree at most 104; non-cyclotomic part 1 at 2, irreducible at the other 518, reducible at 0. Tiers: the row lemma and the size-5 reduction are theorems, proved above with Mann's bound's argument written out and Filaseta and Solan cited only for the question they left open; size 5 being mixed is a theorem by exhibit; the box and line counts are observation, and the line's is a toy-scale reading of an open question, YES wherever it reached. RUN RECORD. 13 of 13 checks, 229.3 s, peak commit 120 MB under a memory guard; every negative bracket the test read decided free. The rehearsal first read 9 of 12. The engine took the first nonzero difference, not its primitive part, as the monomial w, so x^2 - x + 1 was read in x^2 and matched to Phi_2: fixed, 14 of 14 box seeds then read the row lemma. The Mann check demanded a minimal sum at N = 84, which has no fifth roots: the check's own algebra, fixed to demand one exactly when 5 | N. The third was the P5 miss above. """ import cmath import os import sys import time from fractions import Fraction from itertools import combinations, combinations_with_replacement from math import gcd os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") from sympy import Poly, cyclotomic_poly, real_roots, symbols # noqa: E402 CHECKS = [] X, Y, T = symbols("x y t") REHEARSE = "--rehearse" in sys.argv 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): return Poly.from_dict({p: 1 for p in points}, X, Y) def factors(p): """Non-monomial Z-irreducible factors with multiplicity, leading coefficient made positive.""" _, 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 negative(q): return any(c < 0 for c in q.coeffs()) def cross(u, v): return u[0] * v[1] - u[1] * v[0] def collinear(pts): p0 = pts[0] u = (pts[1][0] - p0[0], pts[1][1] - p0[1]) return all(cross(u, (p[0] - p0[0], p[1] - p0[1])) == 0 for p in pts[2:]) def hull(pts): """Vertices of the convex hull, counterclockwise, no collinear ones.""" ps = sorted(set(pts)) lo, hi = [], [] for p in ps: while len(lo) >= 2 and cross((lo[-1][0] - lo[-2][0], lo[-1][1] - lo[-2][1]), (p[0] - lo[-2][0], p[1] - lo[-2][1])) <= 0: lo.pop() lo.append(p) for p in reversed(ps): while len(hi) >= 2 and cross((hi[-1][0] - hi[-2][0], hi[-1][1] - hi[-2][1]), (p[0] - hi[-2][0], p[1] - hi[-2][1])) <= 0: hi.pop() hi.append(p) return lo[:-1] + hi[:-1] def decomposable(pts): """Gao-Lauder: the hull is a sum of two lattice polygons, neither a point.""" h = hull(pts) edges = [] for i in range(len(h)): a, b = h[i], h[(i + 1) % len(h)] dx, dy = b[0] - a[0], b[1] - a[1] g = gcd(abs(dx), abs(dy)) edges.append((dx // g, dy // g, g)) states = {(0, 0, False, False)} for vx, vy, g in edges: states = {(sx + j * vx, sy + j * vy, u or j > 0, left or j < g) for sx, sy, u, left in states for j in range(g + 1)} return (0, 0, True, True) in states SYMS = [lambda a, b: (a, b), lambda a, b: (b, a), lambda a, b: (-a, b), lambda a, b: (a, -b), lambda a, b: (-a, -b), lambda a, b: (-b, a), lambda a, b: (b, -a), lambda a, b: (-b, -a)] def canonical(pts): best = None for s in SYMS: q = [s(a, b) for a, b in pts] mx, my = min(a for a, _ in q), min(b for _, b in q) key = tuple(sorted((a - mx, b - my) for a, b in q)) if best is None or key < best: best = key return best def adapt(w): """A unimodular matrix sending the primitive vector w to (1, 0).""" p, q = w # extended gcd: a p + b q = 1 a0, a1, b0, b1, r0, r1 = 1, 0, 0, 1, p, q while r1: k = r0 // r1 a0, a1, b0, b1, r0, r1 = a1, a0 - k * a1, b1, b0 - k * b1, r1, r0 - k * r1 if r0 < 0: a0, b0 = -a0, -b0 return ((a0, b0), (-q, p)) def apply(m, pts): return [(m[0][0] * a + m[0][1] * b, m[1][0] * a + m[1][1] * b) for a, b in pts] def monomial_cyclotomic(q): """(w, n) when q is Phi_n(w) for a primitive monomial w, else None.""" pts = [e for e, _ in q.terms()] if len(pts) < 2 or not collinear(pts): return None p0 = min(pts) u = [(a - p0[0], b - p0[1]) for a, b in pts] a, b = next(d for d in u if d != (0, 0)) g = gcd(abs(a), abs(b)) w = (a // g, b // g) if w[0] < 0 or (w[0] == 0 and w[1] < 0): w = (-w[0], -w[1]) coeff = {} for (e, c) in q.terms(): d = (e[0] - p0[0], e[1] - p0[1]) k = d[0] // w[0] if w[0] else d[1] // w[1] coeff[(k,)] = int(c) lo = min(k for (k,) in coeff) uni = Poly.from_dict({(k - lo,): c for (k,), c in coeff.items()}, X) if uni.LC() < 0: uni = -uni if not uni.is_cyclotomic: return None for n in range(1, 400): if Poly(cyclotomic_poly(n, X), X) == uni: return w, n return None def rows_along(pts, w): m = adapt(w) q = apply(m, pts) rows = {} for a, b in q: rows.setdefault(b, []).append(a) return m, rows def torsion_free_bracket(pts, w): """Test on R = F / (its part cyclotomic in w): with F's two rows along w, A = row0 / G and B = row1 / G, G their gcd. Returns (free, reason).""" m, rows = rows_along(pts, w) if len(rows) != 2: return None, "rows" (_, r0), (_, r1) = sorted(rows.items()) def row(r): lo = min(r) return Poly.from_dict({(a - lo,): 1 for a in r}, X) a, b = row(r0), row(r1) g = a.gcd(b) a, b = a.quo(g), b.quo(g) da, db = a.degree(), b.degree() arev = Poly.from_dict({(da - k,): c for (k,), c in a.terms()}, X) brev = Poly.from_dict({(db - k,): c for (k,), c in b.terms()}, X) d = (a * arev * Poly(X ** db, X) - b * brev * Poly(X ** da, X)) if d.is_zero: return None, "identical moduli" for f, _ in d.factor_list()[1]: if f.degree() < 1 or not f.is_cyclotomic: continue n = next(k for k in range(1, 2000) if Poly(cyclotomic_poly(k, X), X) == (f if f.LC() > 0 else -f)) for k in range(n): if gcd(k, n) != 1: continue om = cmath.exp(2j * cmath.pi * k / n) bv = b.eval(om) if abs(bv) < 1e-9: continue r = -a.eval(om) / bv if abs(r ** (2 * n) - 1) < 1e-7: return False, f"zero at order {n}" return True, "no omega" def torsion_zero(q, top): terms = q.terms() for n in range(1, top + 1): roots = [cmath.exp(2j * cmath.pi * k / n) for k in range(n)] for i in range(n): for j in range(n): v = sum(int(c) * roots[(i * e[0] + j * e[1]) % n] for e, c in terms) if abs(v) < 1e-9: return n return None def section_control(): section("CONTROL") p = poly([(0, 0), (3, 0), (0, 1), (4, 1), (8, 1)]) fs = factors(p) phi6 = Poly(X ** 2 - X + 1, X, Y) r = Poly((1 + X) + Y * (1 + X + X ** 2) * (X ** 4 - X ** 2 + 1), X, Y) ok_ex = sorted(fs, key=lambda q: q.total_degree()) == [phi6, r] irr = len(factors(Poly(1 + X + X ** 2 + Y, X, Y))) == 1 line = Poly(1 + X + X ** 3 + X ** 4 + X ** 7, X) lf = factors(line) ok_line = (sorted(q.degree() for q in lf) == [3, 4] and sum(q.is_cyclotomic for q in lf) == 1 and any(negative(q) and not q.is_cyclotomic for q in lf)) print(f" exhibit: {[q.as_expr() for q in fs]}") print(f" 1 + x + x^2 + y irreducible: {irr}; 1 + x + x^3 + x^4 + x^7:" f" {[q.as_expr() for q in lf]}") rot = [(a, a + b) for a, b in [(0, 0), (3, 0), (0, 1), (4, 1), (8, 1)]] counts = [zeros_on(rot, K, 400) for K in (20, 40, 60)] print(f" rotated exhibit, zeros (zeta, zeta^K) at K = 20, 40, 60: " f"{counts}") control("P1 controls", ok_ex and irr and ok_line and counts == [2 * (K + 1) for K in (20, 40, 60)]) def section_mann(): section("MANN -- vanishing sums of five roots of unity") ok = True for n in (60, 84): roots = [cmath.exp(2j * cmath.pi * k / n) for k in range(n)] vanish = minimal = bad = split = badsplit = 0 for rest in combinations_with_replacement(range(n), 4): ks = (0,) + rest if abs(sum(roots[k] for k in ks)) > 1e-9: continue vanish += 1 parts = [c for r in (2, 3) for c in combinations(range(5), r) if abs(sum(roots[ks[i]] for i in c)) < 1e-9] if not parts: minimal += 1 if any((ks[i] - ks[j]) * 30 % n for i in range(5) for j in range(5)): bad += 1 continue split += 1 for c in parts: if len(c) == 2: badsplit += (ks[c[0]] - ks[c[1]]) % n != n // 2 else: d = sorted((ks[i] - ks[c[0]]) % n for i in c) badsplit += d != [0, n // 3, 2 * n // 3] print(f" N = {n}: {vanish} vanishing, {minimal} minimal ({bad} " f"with a ratio outside mu_30), {split} split ({badsplit} " f"parts neither antipodal nor equilateral)") ok &= (vanish > 0 and (minimal > 0) == (n % 5 == 0) and bad == 0 and badsplit == 0) check("P2 Mann's bound at five terms", ok) def section_exhibit(): section("EXHIBIT -- the mixed seed {2, 16, 6, 96, 1536}") s = Poly((T - 1) ** 2 * (T ** 2 - 4 * T + 1) ** 2 - T, T) sf = s.factor_list()[1] nreal = len(real_roots(s)) r = Poly((1 + X) + Y * (1 + X + X ** 2) * (X ** 4 - X ** 2 + 1), X, Y) rirr = len(factors(r)) == 1 z = torsion_zero(r, 60) print(f" S = {s.as_expr()}; factors {len(sf)}, real roots {nreal} of " f"{s.degree()}; R irreducible {rirr}, negative {negative(r)}, " f"torsion zero at N <= 60: {z}") check("P3 the exhibit is free", len(sf) == 1 and sf[0][1] == 1 and nreal < s.degree() and rirr and negative(r) and z is None) def enumerate_box(box): grid = [(a, b) for a in range(box + 1) for b in range(box + 1)] col0 = [i for i, p in enumerate(grid) if p[0] == 0] cores = noncol = passed = 0 reps = set() for i0 in col0: p0 = grid[i0] for rest in combinations(range(i0 + 1, len(grid)), 4): pts = [p0] + [grid[i] for i in rest] if min(b for _, b in pts): continue cores += 1 if collinear(pts): continue noncol += 1 if not decomposable(pts): continue passed += 1 reps.add(canonical(pts)) return cores, noncol, passed, sorted(reps) BOX = {} def section_box(): box = 5 if REHEARSE else 8 section(f"BOX -- every non-collinear five-term core in [0, {box}]^2") t0 = time.time() cores, noncol, passed, reps = enumerate_box(box) t1 = time.time() print(f" {cores} cores, {noncol} non-collinear, {passed} through the" f" filter, {len(reps)} orbit representatives [{t1 - t0:.1f} s]") seeds, irred = [], [] nonseed = 0 for pts in reps: fs = factors(poly(pts)) if len(fs) < 2: irred.append(pts) continue if not any(negative(q) for q in fs): nonseed += 1 seeds.append((pts, fs)) print(f" {len(seeds)} reducible, {nonseed} with no negative factor " f"[{time.time() - t1:.1f} s]") split = {"rooted": 0, "mixed": 0} noshape = badfactor = unresolved = 0 reasons = {} for pts, fs in seeds: cyc = [(q, monomial_cyclotomic(q)) for q in fs] cyc = [(q, wn) for q, wn in cyc if wn] if not cyc: noshape += 1 print(f" NO FACTOR CYCLOTOMIC IN A MONOMIAL: {pts} " f"{[q.as_expr() for q in fs]}") continue for q, (w, n) in cyc: _, rows = rows_along(list(pts), w) sizes = sorted(len(r) for r in rows.values()) if sizes != [2, 3] or n % 6 or not negative(q): badfactor += 1 print(f" ROW LEMMA FAILS: {pts} {q.as_expr()} n={n} " f"rows {sizes}") others = [q for q in fs if not monomial_cyclotomic(q)] negs = [q for q in others if negative(q)] if not negs: split["rooted"] += 1 continue free, why = torsion_free_bracket(list(pts), cyc[0][1][0]) why = why if free is None else ("free" if free else "zero found") reasons[why] = reasons.get(why, 0) + 1 if free is None or len(others) > 1: unresolved += 1 print(f" UNRESOLVED: {pts} {[q.as_expr() for q in fs]}") continue split["mixed" if free else "rooted"] += 1 BOX.update(box=box, seeds=seeds, irred=irred) print(f" seeds: rooted {split['rooted']}, mixed {split['mixed']}; " f"without a factor cyclotomic in a monomial, the only way to be " f"free outright, {noshape}; row lemma failures {badfactor}; " f"unresolved {unresolved}; torsion test outcomes {reasons}") check("P4 every reducible core is a seed", seeds and nonseed == 0) check("P4 every seed has a factor cyclotomic in a monomial, so none is " "free outright", noshape == 0) check("P4 the row lemma: rows 2 and 3, order divisible by 6, negative", badfactor == 0) check("P4 every negative bracket decided", unresolved == 0) if box == 8: check("P4 the split (transplant: 130 / 33 mixed / 97 rooted)", (len(seeds), split["mixed"], split["rooted"]) == (130, 33, 97)) FRACS = {} def zeros_on(pts, K, top): """Roots of unity zeta of order <= top with sum zeta^(a + K b) = 0.""" if top not in FRACS: FRACS[top] = [(k, n) for n in range(1, top + 1) for k in range(n) if gcd(k, n) == 1] count = 0 exps = [a + K * b for a, b in pts] for k, n in FRACS[top]: v = sum(cmath.exp(2j * cmath.pi * ((k * e) % n) / n) for e in exps) if abs(v) < 1e-9: count += 1 return count def det_bound(pts): diffs = [(p[0] - q[0], p[1] - q[1]) for p, q in combinations(pts, 2)] return 30 * sum(abs(cross(u, v)) for u, v in combinations(diffs, 2) if cross(u, v)) def section_bound(): section("BOUND -- zeros (zeta, zeta^K) of irreducible pentanomials") sample = BOX["irred"][::997] over = rising = 0 worst, rises = [0, 0, 0], [] for pts in sample: c = [zeros_on(list(pts), K, 400) for K in (20, 40, 60)] b = det_bound(pts) over += any(x > b for x in c) rising += c[2] > c[0] if c[2] > c[0]: rises.append(c) worst = [max(w, x) for w, x in zip(worst, c)] print(f" {len(sample)} representatives; most zeros at K = 20, 40, 60: " f"{worst}; above the bound {over}; rising {rising}: {rises}") least = min(det_bound(pts) for pts in sample) print(f" the least bound over the sample: {least}") check("P5 no count above its bound (the frozen kill of (5))", sample and over == 0) def section_line(): top = 16 if REHEARSE else 30 section(f"LINE -- 1 + x^a + x^b + x^c + x^n, n <= {top}") total = red = badcyc = badrec = 0 split = {"rooted": 0, "mixed": 0, "outright": 0} for n in range(4, top + 1): for a, b, c in combinations(range(1, n), 3): total += 1 fs = factors(Poly(1 + X ** a + X ** b + X ** c + X ** n, X)) if len(fs) < 2: continue red += 1 noncyc = [q for q in fs if not q.is_cyclotomic] if len(noncyc) > 1: badcyc += 1 print(f" FILASETA-SOLAN WITNESS: {(a, b, c, n)} " f"{[q.as_expr() for q in fs]}") nonrec = [q for q in fs if Poly(list(reversed(q.all_coeffs())), X) not in (q, -q)] badrec += len(nonrec) > 1 negs = [q for q in fs if negative(q)] if all(q.is_cyclotomic for q in negs): split["rooted"] += 1 elif any(q.is_cyclotomic for q in fs): split["mixed"] += 1 else: split["outright"] += 1 print(f" {total} pentanomials, {red} reducible; non-cyclotomic part " f"reducible {badcyc}; non-reciprocal part reducible {badrec}; " f"seeds rooted {split['rooted']}, mixed {split['mixed']}, free " f"outright {split['outright']}") check("P6 the non-cyclotomic part is 1 or irreducible", red and badcyc == 0) check("P6 Filaseta-Solan Theorem 1 holds", badrec == 0) check("P6 free outright 0", split["outright"] == 0) def section_specialize(): box = BOX["box"] section(f"SPECIALIZE -- every seed of the box at K = {box + 1}..{box + 4}") pairs = shape = bad = one = 0 top = 0 for pts, _ in BOX["seeds"]: for K in range(box + 1, box + 5): pairs += 1 terms = {} for a, b in pts: terms[(a + K * b,)] = terms.get((a + K * b,), 0) + 1 p = Poly.from_dict(terms, X) top = max(top, p.degree()) shape += len(terms) == 5 and set(terms.values()) == {1} noncyc = [q for q in factors(p) if not q.is_cyclotomic] one += not noncyc if len(noncyc) > 1: bad += 1 print(f" FILASETA-SOLAN WITNESS: {pts} K={K}") print(f" {pairs} (seed, K) pairs, {shape} five-term 0/1 images, " f"degree at most {top}; non-cyclotomic part 1 at {one}, " f"reducible at {bad}") check("P7 every non-cyclotomic part 1 or irreducible", bad == 0) def main(): t0 = time.time() section_control() section_mann() section_exhibit() section_box() section_bound() section_line() section_specialize() 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())