"""reversal.py -- the Filaseta-Solan question read through the reversal: a 0/1 pentanomial whose non-cyclotomic part is reducible shares a non-cyclotomic factor with its reversal, so an exact gcd replaces factoring. QUESTION. f = 1 + x^q + x^p + x^m + x^n, 0 < q < p < m < n. M. Filaseta and I. Solan (An extension of a theorem of Ljunggren, Math. Scand. 84 (1999) 5-10, Theorem 1) prove that f with its irreducible reciprocal factors removed is 1 or irreducible, and leave open whether the same holds with only its cyclotomic factors removed; they state it "in the special case that n is exactly one of 2m, 2q, 2p, m + p, p + q, or m + q", the proof not printed, and report no computation. Is the non-cyclotomic part of f ever reducible? THE REDUCTION (written before the engine). Write f~ = x^n f(1/x) and G = gcd(f, f~) over Z. (1) f NOT RECIPROCAL. The non-cyclotomic part of f is reducible exactly when G has a non-cyclotomic irreducible factor. If f had no non-cyclotomic reciprocal irreducible factor, its non-cyclotomic part would be its non-reciprocal part, 1 or irreducible by Theorem 1; so some non-cyclotomic reciprocal w divides f, and w~ = +-w divides f~. Conversely let u | G be irreducible and not cyclotomic. If u is reciprocal, f = u v with v not reciprocal, so v has a non-reciprocal factor, which is not cyclotomic. If u is not reciprocal, u | f~ puts u~ in f beside u. Either way f has two non-cyclotomic factors. (2) f RECIPROCAL (n = 2p, m = n - q). G = f; the non-cyclotomic part is reducible exactly when f has at least two non-cyclotomic irreducible factors, with multiplicity: f is factored outright. (3) f -> f~ sends (q, p, m) to (n - m, n - p, n - q) and keeps the verdict, so one of each pair, the lexicographically smaller, is read. (4) THE SIX CASES ARE WHERE f - f~ CANCELS (by hand, after the run). A shared zero of f and f~ is a zero of f - f~ = x^q + x^p + x^m - x^(n-m) - x^(n-p) - x^(n-q). Setting one of {q, p, m} equal to one of {n - m, n - p, n - q}, over all nine pairs, gives n in {m + q, p + q, 2q, m + p, 2p, 2m}: exactly the six cases. Off them a shared zero is a zero of a six-term +-1 polynomial with no cancellation. Known beside it (E. Bombieri and U. Zannier, as Theorem 3 of M. Filaseta and A. Kalogirou, arXiv:2508.12242): a shared non-cyclotomic factor forces j . (q, p, m, n) = 0 for some nonzero integer j with |j| below a computable constant, so every NO lies on finitely many hyperplanes, none named. (5) THE SIX CASES, PROVED FOR NON-RECIPROCAL f (by hand, after the run). An off-diagonal equality cancels two pairs at once (q = n - m iff m = n - q, likewise p = n - m and q = n - p), leaving f - f~ a monomial times x^a - x^(n-a), a in {p, q, m}. A diagonal one (n = 2q, 2p or 2m) cancels one pair; with a < b the other two of {q, p, m} and d = n - a - b, the rest is x^a + x^b - x^(a+d) - x^(b+d) = x^a (1 + x^(b-a)) (1 - x^d), Laurent when d < 0. Either way every nonzero zero of f - f~ is a root of unity, unless f - f~ = 0, which is f reciprocal. So in the six cases G is cyclotomic for every non-reciprocal f, and (1) leaves its non-cyclotomic part 1 or irreducible (a theorem, given their Theorem 1). Two of the six values can be equal only as 2p = m + q (2q < p + q < m + q < m + p < 2m and p + q < 2p < m + p), and n = 2p = m + q is exactly f reciprocal. So if their "exactly one of" excludes an n equal to two of the values, (5) proves every case they stated; if it does not, the reciprocal f are the remainder, which (5) does not reach. SIX prints the check. DESIGN. Polynomials are python-flint's fmpz_poly; gcd and factor are exact over Z, a factor's cyclotomy is flint's is_cyclotomic. It is the one script here that needs python-flint (pip install python-flint). C1 POSITIVE: R h, R = x^2 - 3x + 1 (reciprocal, not cyclotomic), h = 1 + x + x^3: branch (1) reports R. R^2: branch (2) reports two non-cyclotomic factors. C2 NEGATIVE: 1 + x + x^3 + x^4 + x^7 = Phi_5 (1 - x^2 + x^3): G = Phi_5, not reported. R Phi_5, reciprocal with one non-cyclotomic factor: not reported. C3 CROSS: every pentanomial with n <= 30, unhalved, read by the gcd route and by flint's full factorization of f; the verdicts agree on every one, and the reducible count is pentanomial.py's P6 print (made with sympy). C4 COUNT: the halved enumeration expanded, 2 per non-reciprocal representative and 1 per reciprocal, totals C(N, 4). SCAN: n = 4..N, per decade of n the representatives, how many non-reciprocal ones have deg G > 0 (a reciprocal f has G = f), and survivors. Added after the run, on review: C5 two NOs planted in the scan's own loop, one per branch: at (1, 3, 4, 7) f becomes R f, at the reciprocal (1, 3, 5, 6) R^2 f, R = x^2 - 3x + 1, and a scan to 30 must find these two alone. SIX for n <= 40: f - f~ for every non-reciprocal f in the six cases has only cyclotomic factors besides x; C6, the control, finds f - f~ with a non-cyclotomic factor off the six cases; and an n equal to two of the six values occurs only at a reciprocal f. PREDICTIONS (fixed before the engine). C1-C4 as written; C3 reads 3,007 reducible of 27,405. SCAN: 0 survivors to N. A survivor is a NO to the question, printed with its factorization and its n read against the six cases. KILL. The line "survivors: s" over n = 4..N, both branches summed; s > 0 kills YES to degree N. C1 is read before the scan; if it misses, the scan is not read. RESOURCE. About 10 us per representative at degree 100. --rehearse runs N = 30; --top N sets the scan's top degree. FINDINGS (run at --top 180). Every check held: 7 of 7. C1 R h reports [x^2 - 3x + 1]; R^2 reports it twice. C2 1 + x + x^3 + x^4 + x^7: G = x^4 + x^3 + x^2 + x + 1, not reported; R Phi_5 not reported. C3 27405 pentanomials, 3007 reducible, the two routes agree on 27405. C4 42296805 against C(180, 4) = 42296805. SCAN 21,150,405 representatives over n = 4..180, 4,005 of them reciprocal (n/2 - 1 at each even n, consistent with C4); 2,076,390 non-reciprocal ones with deg G > 0, every such G cyclotomic: survivors: 0. GIVEN THEOREM 1, THE NON-CYCLOTOMIC PART OF EVERY 0/1 PENTANOMIAL OF DEGREE AT MOST 180 IS 1 OR IRREDUCIBLE. Per decade of n the share of non-reciprocal representatives with deg G > 0 runs from 9.4% (161..170) to 14.0% (4..10). At --rehearse after review: C5 finds its two plants alone; SIX reads 13680 non-reciprocal six-case f, 0 with a non-cyclotomic factor of f - f~, against 65186 of 77520 off them (C6); an n equal to two of the values at 190 reciprocal f and 0 others. Tier: rule (verified n <= 180, exhaustively, every verdict exact over Z), the non-reciprocal verdicts resting on Filaseta and Solan's Theorem 1, whose proof is printed; the reduction (1)-(3) and the six cases (5) for non-reciprocal f are theorems given that Theorem 1, (4) a property. RUN RECORD. --rehearse 7 of 7, 4.0 s. --top 100: 7 of 7, 27.1 s, peak 29 MB. --top 180: 7 of 7, 397.8 s, peak commit 173.5 MB under a memory guard, the estimate 7 minutes. The first draft inlined the gcd in the scan, outside the path C1 tests; both now read through read(). The per-decade rows were printed labelled "n <= b"; they count n in b - 9..b, and the label now says so. The question as frozen before the engine put RAM under 100 MB, flint's polys freed per step, yet the peak commit rose with N (13.2 MB at 30, 29 at 100, 173.5 at 180); the cause is not found. Review moved the loop into scan() for C5 and added SIX: --top 100 11 of 11, 40.3 s, peak 40.1 MB, its ten rows equal to the --top 180 run's first ten; then C5's second plant, read at --rehearse. """ import os import sys import time from math import comb os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") from flint import fmpz_poly # noqa: E402 CHECKS = [] REHEARSE = "--rehearse" in sys.argv TOP = 30 if REHEARSE else (int(sys.argv[sys.argv.index("--top") + 1]) if "--top" in sys.argv else 100) SIX = ("2m", "2p", "2q", "m+p", "m+q", "p+q") 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 penta(q, p, m, n): c = [0] * (n + 1) for e in (0, q, p, m, n): c[e] = 1 return fmpz_poly(c) def reverse(f): return fmpz_poly(list(reversed(f.coeffs()))) def noncyclotomic(f): """Non-cyclotomic irreducible factors of f, with multiplicity.""" _, fl = f.factor() return [g for g, e in fl for _ in range(e) if g.degree() > 0 and not g.is_cyclotomic()] def read(f): """(whether G = gcd(f, f~) is non-constant, the non-cyclotomic factors that make f's non-cyclotomic part reducible by (1) or (2), [] when it is 1 or irreducible). The scan and the controls both read through here.""" r = reverse(f) if r == f or r == -f: nc = noncyclotomic(f) return True, (nc if len(nc) >= 2 else []) g = f.gcd(r) if g.degree() == 0: return False, [] return True, noncyclotomic(g) def verdict(f): return read(f)[1] def direct(f): """The same verdict by factoring f alone.""" nc = noncyclotomic(f) return nc if len(nc) >= 2 else [] def six(q, p, m, n): vals = (2 * m, 2 * p, 2 * q, m + p, m + q, p + q) return [s for s, v in zip(SIX, vals) if v == n] def section_controls(): section("CONTROLS") R = fmpz_poly([1, -3, 1]) h = fmpz_poly([1, 1, 0, 1]) v = verdict(R * h) control("C1 R h: the gcd route reports R", v == [R], f"{v}") v = verdict(R * R) control("C1 R^2: the reciprocal branch reports two factors", v == [R, R], f"{v}") f = penta(1, 3, 4, 7) g = f.gcd(reverse(f)) control("C2 1 + x + x^3 + x^4 + x^7: G = Phi_5, not reported", g == fmpz_poly.cyclotomic(5) and verdict(f) == [], f"G = {g}") v = verdict(R * fmpz_poly.cyclotomic(5)) control("C2 R Phi_5: one non-cyclotomic factor, not reported", v == [], f"{v}") def section_cross(): section("CROSS -- every pentanomial with n <= 30, two routes") total = red = agree = 0 for n in range(4, 31): for q in range(1, n): for p in range(q + 1, n): for m in range(p + 1, n): f = penta(q, p, m, n) total += 1 _, fl = f.factor() red += sum(e for _, e in fl) > 1 agree += bool(verdict(f)) == bool(direct(f)) print(f" {total} pentanomials, {red} reducible, the two routes " f"agree on {agree}") control("C3 the routes agree on every one, 3,007 reducible of 27,405", total == 27405 and agree == total and red == 3007) def scan(top, plant=None, show=True): """Read one of each reversal pair with n <= top; at a tuple of the dict plant, f is replaced by its value times f, a planted NO.""" t0 = time.time() expanded, found = 0, [] row = [0, 0, 0] for n in range(4, top + 1): for q in range(1, n): for p in range(q + 1, n): for m in range(p + 1, n): rq, rp, rm = n - m, n - p, n - q if (q, p, m) > (rq, rp, rm): continue rec = (q, p, m) == (rq, rp, rm) expanded += 1 if rec else 2 row[0] += 1 f = penta(q, p, m, n) if plant and (q, p, m, n) in plant: f = plant[(q, p, m, n)] * f nonconstant, v = read(f) row[1] += nonconstant and not rec if v: found.append((q, p, m, n)) row[2] += 1 if show: print(f" SURVIVOR (q, p, m, n) = " f"{(q, p, m, n)} six cases " f"{six(q, p, m, n)}: {f.factor()}") if show and (n % 10 == 0 or n == top): print(f" n {max(4, n - 9):3d}..{n:3d}: {row[0]:8d} representatives, " f"{row[1]:7d} with deg G > 0, {row[2]} survivors, " f"{time.time() - t0:6.1f} s") row = [0, 0, 0] return expanded, found def section_scan(): section(f"SCAN -- n = 4..{TOP}, one of each reversal pair; the deg G > 0" " count is over non-reciprocal f") R = fmpz_poly([1, -3, 1]) plant = {(1, 3, 4, 7): R, (1, 3, 5, 6): R * R} _, found = scan(30, plant=plant, show=False) control("C5 NOs planted in the loop, one per branch, are its only " "survivors", sorted(found) == sorted(plant), f"{found}") expanded, found = scan(TOP) check("C4 the expanded count is C(N, 4)", expanded == comb(TOP, 4), f"{expanded} against {comb(TOP, 4)}") print(f" survivors: {len(found)}") check("SCAN no survivor", not found) def section_six(): section("SIX -- f - f~ over the six cases, n <= 40") x = fmpz_poly([0, 1]) counts = {True: [0, 0], False: [0, 0]} twice = {True: 0, False: 0} for n in range(4, 41): for q in range(1, n): for p in range(q + 1, n): for m in range(p + 1, n): f = penta(q, p, m, n) r = reverse(f) rec = r == f hits = len(six(q, p, m, n)) if hits >= 2: twice[rec] += 1 if rec: continue _, fl = (f - r).factor() bad = any(g.degree() > 0 and g != x and not g.is_cyclotomic() for g, _ in fl) counts[hits > 0][0] += 1 counts[hits > 0][1] += bad print(f" non-reciprocal, in the six cases: {counts[True][0]}, f - f~ " f"with a non-cyclotomic factor {counts[True][1]}; off them: " f"{counts[False][0]}, with one {counts[False][1]}") print(f" n equal to two of the six values: reciprocal {twice[True]}, " f"non-reciprocal {twice[False]}") control("C6 the test fires off the six cases", counts[False][1] > 0) check("SIX f - f~ has only cyclotomic factors in every six case", counts[True][1] == 0) check("SIX two of the six values meet only at the reciprocal f", twice[False] == 0 and twice[True] > 0) def main(): t0 = time.time() section_controls() section_cross() section_six() section_scan() print() print(f"{sum(CHECKS)} of {len(CHECKS)} checks, {time.time() - t0:.1f} s") return 0 if all(CHECKS) else 1 if __name__ == "__main__": sys.exit(main())