"""rays.py -- whether a signed pentanomial's survivors can fill a plane: the shared factor of a 5-term Laurent polynomial in two variables and its reversal. QUESTION. A SURVIVOR is a signed f = 1 + s1 x^q + s2 x^p + s3 x^m + s4 x^n, e = (q, p, m, n) ADMISSIBLE (0 < q < p < m < n), not +-reciprocal, with a non-cyclotomic factor in gcd(f, f~). With G(x1..x4) = 1 + sum s_i x_i and H = x1 x2 x3 x4 G(1/x), f = G(x^e) and H(x^e) = x^(q + p + m) f~ (x^n f(1/x) = f~), so a survivor is exactly an e at which G(x^e) and H(x^e) share a non-cyclotomic factor. THEOREM 3 OF FILASETA AND KALOGIROU (arXiv:2508.12242, Bombieri and Zannier, 1998), as printed: for k >= 2, n1 < ... < nk positive and G, H in Z[x1..xk] relatively prime in Q[x1..xk], if G(x^n1, ..., x^nk) and H(x^n1, ..., x^nk) share a non-cyclotomic irreducible factor then j . n = 0 for some j in Z^k, not all 0, with sum |j_i| <= C(G, H), a computable constant depending only on G and H (also E. Bombieri, D. Masser and U. Zannier, IMRN 2007, Theorem 1.6, not read here; their structure theorem may hold the reduction). Its proof is not printed there. The condition it reaches is exactly the survivor condition, and its constant is effective. THE REDUCTION (by hand). Restrict to a hyperplane j . e = 0, e = M t, t in Z^3, M's columns a basis of its lattice: G_M(y) = G(y^M) = 1 + sum s_i y^(r_i), r_i the rows of M, H_M ~ G_M(1/y), and f_e = G_M(x^t). A sublattice on which two of 0, r_1..r_4 coincide lies in e_i = e_j or e_i = 0 and holds no admissible e, so G_M has 5 terms. THE CHAMBERS: Theorem 3 wants 0 < t_1 < t_2 < t_3. The planes t_i = 0 and t_i = +-t_j cut Z^3 into finitely many open chambers, each fixing the signs of the t_i and the order of the |t_i|; in each, a permutation and an inversion of the y_i, times a monomial, gives a polynomial pair whose exponents are positive and increasing, the specialization changing by a power of x, which no survivor's factor is (f(0) = 1). The walls are rank-2 sublattices, recursed on in turn. Either G_M and G_M(1/y) share a factor of measure > 1 (CASE A), or their gcd E has measure 1, so is a product of monomials and extended cyclotomic polynomials Phi_m(y^v) (D. W. Boyd, Kronecker's theorem and Lehmer's problem for polynomials in several variables, J. Number Theory 13 (1981) 116-121), every irreducible factor of E(x^t) is cyclotomic or x, and a survivor's shared factor divides both coprime cofactors at x^t: Theorem 3 again, a hyperplane in t. The recursion ends at rank 1, where the admissible half of a line Z v holds survivors at every point or at none (f_(tv)(x) = f_v(x^t), and gcd(a(x^t), b(x^t)) = gcd(a, b)(x^t)): a ray. At rank k the rows r_i span R^k, so G_M's support has affine rank k. A CASE A sublattice of rank 3 restricts to rank 2: Lawton's theorem (W. M. Lawton, J. Number Theory 16 (1983) 356-362: M(Q(x^r)) -> M(Q) as q(r) -> oo, q(r) the least height, max |s_i|, of a nonzero s with s . r = 0), applied to D and to D(y^N) with q(N s) >= min(q(N), q(s)/|N|), gives M(D(y^N)) -> M(D) as q(N) -> oo, q(N) the least height of a nonzero s with N^T s = 0, |N| the largest column sum of |N|'s entries. The kernel of N^T is Z s0, s0 primitive, q(N) = |s0|, and s0 of any height occurs (N a basis of the integer vectors orthogonal to s0); once q(N) passes Lawton's threshold and exceeds every |r_i - r_j| and |r_i + r_j - r_k - r_l| (i = j and k = l allowed), N^T is injective on the points and on their pairwise sums, so G_M(y^N) has 5 terms, support of affine rank 2 (N^T is onto), and a shared factor of measure > 1, and a central symmetry of it, r_i + r_pi(i) mapped to one point, lifts to G_M. Then (R2) makes every CASE A G_M +-reciprocal, and every f on its sublattice with it: no survivor. Here (R2) is the bivariate statement: (R2) every 5-term +-1 Laurent polynomial G in two variables, its support affinely of rank 2, that shares a factor of measure > 1 with G(1/y) is +-reciprocal (G(1/y) = +-monomial G). So Theorem 3 and (R2) put the survivors on finitely many rays, and make "three rays" a finite computation with the constants C. (R2) is proved below. THE PROOF OF (R2) (by hand). G as in (R2), D irreducible of measure > 1 dividing G and G* (G(1/y) times a monomial; D* likewise), P its Newton polygon. SEGMENT. D's Newton polytope is not a segment: else D = mono phi(y^w), w primitive, phi not cyclotomic, and each coset of Z w meeting the support carries a component of G divisible by phi, so of 3 terms at least (a binomial's roots are roots of unity); rank 2 puts the support in at least two cosets, 6 terms. TWO LAYERS. The support does not lie on two parallel lines: write G = g0(z) + t^h g1(z) along them. D involves t (else D divides g0 and g1, each then of measure > 1 and 3 terms) and z (else D is a segment), so its zero curve dominates z, where G = G(1/y) = 0 gives g0(z) g0(1/z) = g1(z) g1(1/z) identically, so |g0| = |g1| on the circle and, by Jensen's formula in t, M(G) = M(g0) = M(g1) >= M(D) > 1: each layer has 3 terms at least, 6 in all. PARALLELOGRAM. N(G) has at most 5 edges. If D ~ D*, P is centrally symmetric; if not, D* divides G too and D D* does, so P + (-P) is a Minkowski summand of N(G). Either way each edge normal of P and of -P is one of N(G)'s; that set is closed under negation, so of even size at most 5: four, +-n1 and +-n2, and no three of them span the plane positively, so P uses all four: a parallelogram, its sides along primitive u and v. 2-1-2. Cut the plane into lines along u. G's face at either normal to u is D's face there, an edge of P and so not a monomial, times a nonzero face: each outer line holds 2 terms at least, and by TWO LAYERS a third line holds one, so the lines carry 2, 1 and 2. Likewise along v. With a and b the linear forms constant along u and along v (together injective on Z^2), the support sits in a 3 x 3 grid of a-values 0 < alpha < A and b-values 0 < beta < B, 2, 1, 2 points to a row and to a column: the X (the four corners and the center cell), or a SKEW pattern, the middle row's point in an outer column, such as (0, 0), (0, B), (alpha, 0), (A, beta), (A, B). MIDLINE. With z along u and t across, G = g0(z) + c z^r t^alpha + g2(z) t^A, g0 and g2 binomials. D's top face in t divides g2, so has measure 1, and Jensen's formula in t makes the integral of the sum of log+ |t_i(z)| over D(z, .)'s roots log M(D) > 0: the z with a root off the circle have positive measure and, the roots moving continuously, hold an arc, shrunk off the zeros of g0 and g2. There a root t0 = rho w, |w| = 1, rho != 1, has G(z, t0) = 0, and G*(z, t0) = 0 conjugated is G(z, 1/conj(t0)) = 0. With a = g0(z), X = c z^r w^alpha, Y = g2(z) w^A: a + X rho^alpha + Y rho^A = 0 = a + X rho^-alpha + Y rho^-A, a real system of determinant rho^(alpha - A) - rho^(A - alpha) != 0, so X/a and Y/a are real and R = X^A Y^-alpha a^(alpha - A) = c^A z^(rA) g2^-alpha g0^(alpha - A), w cancelled, is real on the arc: R(z) = R(1/z) identically. A +-1 binomial with exponents i, j has g(1/z) = +-z^-(i + j) g(z), so this is a monomial identity, 2 r A = (A - alpha)(i0 + j0) + alpha (i2 + j2): the middle term lies on the segment joining the midpoints of the two outer pairs. Each outer pair holds two b-values, so that point's b lies strictly inside (0, B), and a SKEW pattern's middle point does not: the support is the X, its corners p1, p2, p3, p4 with p1 + p4 = p2 + p3, and MIDLINE along u and along v puts its fifth point m at the center (p1 + p4)/2. THE X. Align G* = y^(p1 + p4) G(1/y), c_i the coefficient at p_i, c0 at m, and e = c1 c4: D divides H = G - e G*, which vanishes at p1 and p4. If c3 = e c2, H = (1 - e) c0 y^m, a monomial unless e = 1, G = G*. If c3 = -e c2, H = 2 c2 (y^p2 - e y^p3) + (1 - e) c0 y^m is not 0 and lies on the diagonal p2 p3, a segment, of which P is no summand. So G is +-reciprocal: (R2) holds. DESIGN. Every 5-point set S in the box [0, B]^2 touching both axes (one per translate), affinely of rank 2, with the 16 sign vectors fixing the first point's coefficient at +1; G* = y^(B, B) G(1/y). The gcd of G and G* over Z[y, z] (flint), factored; a factor is FLAGGED when its Newton polytope has dimension 2, or dimension 1 with a non-cyclotomic phi. G is +-RECIPROCAL when G* is +-G after translation. C1 detector plants, off the 5-term family: (1 + y + z)(y z + y + z)(1 + 2y), not +-reciprocal, a 2-dimensional shared factor; and (1 + y - y^3)(y^3 + y^2 - 1)(1 + z), a 1-dimensional non-cyclotomic one; each flagged twice (D and its reversal both divide), and 1 + 2y + z, sharing nothing, not. C2 the +-reciprocal family is seen: the set {(1,0), (2,0), (1,1), (0,2), (1,2)} (the hyperplane n = 2p = m + q, t = (a, b) -> (a, b, 2b - a, 2b), shifted) with coefficients (1, s1, s2, s1, 1), so G = G* at every sign, is counted +-reciprocal, and its gcd is G. C3 the lemmas as a check, over every flagged G, +-reciprocal or not: with a segment factor (SEGMENT says 0), on two parallel lines (TWO LAYERS says 0). C4 the proof's later steps as a check, over every G with a flagged 2-dimensional factor: its P not a parallelogram; the support not the X with m at its center. And MIDLINE's algebra, at 8 points z = exp(2 pi i (k + sqrt 2 - 1)/8) of the circle, never a root of unity, so g0(z) and g2(z) are not 0: each root t0 of G(z, .) in t (z along a side of P) with |t0| > 1 + 1e-6 whose 1/conj(t0) is also a root, R(z) computed, the pairs counted and the largest |Im R|/|R| printed. A pair count of 0 reads nothing. Every G it reads is +-reciprocal (the box holds no other flagged G), so C4 checks the steps' algebra, never a contrary case. PREDICTIONS, frozen before the engine. P1 B = 4: no flagged G that is not +-reciprocal. P2 the +-reciprocal G are flagged unless G is a product of cyclotomic polynomials in monomials. P3 C3 prints 0 and 0. P4 C4 prints 0 and 0, pairs > 0, and the largest |Im R|/|R| below 1e-9 (the third count, not on three lines along P's side, was added with the code). KILL. "flagged, not +-reciprocal: h" over the box B = 4: h >= 1 kills (R2) as a theorem to seek; the example then names a candidate plane of survivors, to be read at its generic member. FINDINGS. C1 ['2d', '2d'], ['1d', '1d'], [] (D and its reversal both divide each plant); C2 each of the four sign choices +-reciprocal, gcd G. B = 4: "26486 sets of rank 2 (4 collinear skipped), 423776 signed G"; "+-reciprocal G: 248, with a flagged factor 248"; "flagged with a segment factor: 0; flagged on two parallel lines: 0"; "flagged, not +-reciprocal: 0": P1, P2, P3 held, the kill misses. --box 6: "582480 sets of rank 2 (60 collinear skipped), 9319680 signed G"; "+-reciprocal G: 1056, with a flagged factor 1056"; the lemma prints 0 and 0; "flagged, not +-reciprocal: 0". So (R2) holds for every support in [0, 6]^2 (a rule over that box), and every +-reciprocal G there carries a factor of measure > 1. C4 at --box 6: "P not a parallelogram: 0; the support not the centered X: 0; not on three lines along P's side: 0"; "MIDLINE: 6956 root pairs, largest |Im R|/|R| 3.99e-14" (B = 4: 920 pairs, 4.13e-15): P4 held. RUN RECORD. --rehearse first failed C1: the wanted set held one flag per plant, forgetting that D and D* both divide it; the detector was right. Then 3 of 3, B = 2, 0.0 s. B = 4: 3 of 3, 8.8 s, peak commit 12.4 MB; the lemma prints were then widened to every flagged G. --box 6: 3 of 3, 197.4 s, 12.6 MB. With recip() returning False in a scratch copy, C2 stops the run; with the controls also skipped, the kill fires, "flagged, not +-reciprocal: 248". C4 first sampled z = exp(2 pi i (k + 1/3)/8), each a root of unity, and failed at --box 6, "largest |Im R|/|R| 9.85e-01" (and at B = 4, 5.80e-01): at k = 1 the g0 and g2 of y^6 z^4 + y^6 z^3 + y^3 z^2 + z + 1 both vanish, outside MIDLINE's arc, and the roots were noise; moved to k + sqrt 2 - 1. Then 4 of 4: B = 4, 9.1 s; --box 6, 205.0 s, peak commit 21.2 MB. With R's exponent of Y as 1 - alpha in a scratch copy, --rehearse prints "MIDLINE: 40 root pairs, largest |Im R|/|R| 9.87e-01" and C4 fails. C3 then made a check: B = 4, 5 of 5, 13.1 s; with layers() returning True in a scratch copy, "flagged on two parallel lines: 248" and C3 fails. --box 6 at 4 of 4 before it: 208.0 s, peak commit 21.3 MB. RESOURCE. 26,490 of the C(25, 5) five-sets (those touching both axes) times 16 signs, a bivariate gcd each, at B = 4 (8.8 s); --box 6 about 20 times that; --rehearse B = 2. """ import os import sys import time from itertools import combinations, product from math import gcd os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") import flint # noqa: E402 import numpy as np # noqa: E402 CHECKS = [] TWO_D = [] # (G, its 2-dimensional flagged factors), filled by the box SQ2 = 2 ** 0.5 REHEARSE = "--rehearse" in sys.argv B = 2 if REHEARSE else (int(sys.argv[sys.argv.index("--box") + 1]) if "--box" in sys.argv else 4) CTX = flint.fmpz_mpoly_ctx.get(("y", "z"), "lex") 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 poly(terms): """terms {(a, b): c} -> fmpz_mpoly, shifted so both minima are 0.""" a0 = min(a for a, _ in terms) b0 = min(b for _, b in terms) return CTX.from_dict({(a - a0, b - b0): c for (a, b), c in terms.items()}) def terms_of(P): return {tuple(int(x) for x in e): int(c) for e, c in P.to_dict().items()} def star(P): """y^(top) P(1/y), shifted: the reversal.""" t = terms_of(P) return poly({(-a, -b): c for (a, b), c in t.items()}) def rank(points): p0 = points[0] vs = [(a - p0[0], b - p0[1]) for a, b in points[1:]] return 2 if any(u[0] * v[1] - u[1] * v[0] for u in vs for v in vs) else ( 1 if any(v != (0, 0) for v in vs) else 0) def flagged(D): """D irreducible: dimension 2, or 1 with a non-cyclotomic phi.""" t = terms_of(D) pts = sorted(t) r = rank(pts) if r == 2: return "2d" if r == 0: return None lo, hi = pts[0], pts[-1] dx, dy = hi[0] - lo[0], hi[1] - lo[1] g = gcd(dx, dy) w = (dx // g, dy // g) k = {((a - lo[0]) // w[0] if w[0] else (b - lo[1]) // w[1]): c for (a, b), c in t.items()} phi = flint.fmpz_poly([k.get(i, 0) for i in range(max(k) + 1)]) return None if phi.is_cyclotomic() else "1d" def recip(P): S = star(P) return S == P or S == -P def shared(P): """The flagged irreducible factors of gcd(P, P*).""" g = P.gcd(star(P)) if g.total_degree() <= 0: return g, [] _, fl = g.factor() return g, [(D, flagged(D)) for D, _ in fl if flagged(D)] def layers(points): """The support lies on two parallel lines.""" for i, j in combinations(range(5), 2): u = (points[j][0] - points[i][0], points[j][1] - points[i][1]) vals = {u[0] * p[1] - u[1] * p[0] for p in points} if len(vals) == 2: return True return False def section_controls(): print("CONTROLS") y, z = CTX.gens() p1 = (1 + y + z) * (y * z + y + z) * (1 + 2 * y) p2 = (1 + y - y ** 3) * (y ** 3 + y ** 2 - 1) * (1 + z) p3 = 1 + 2 * y + z f1 = [k for _, k in shared(p1)[1]] f2 = [k for _, k in shared(p2)[1]] f3 = [k for _, k in shared(p3)[1]] control("C1 the detector: a 2-dimensional plant, a 1-dimensional " "non-cyclotomic plant, and a coprime pair", f1 == ["2d", "2d"] and f2 == ["1d", "1d"] and not f3 and not recip(p1), f"{f1}, {f2}, {f3}") found = [] for s1, s2 in product((1, -1), repeat=2): P = poly({(1, 0): 1, (2, 0): s1, (1, 1): s2, (0, 2): s1, (1, 2): 1}) g, fl = shared(P) found.append((recip(P), g == P or g == -P, [k for _, k in fl])) control("C2 the +-reciprocal plane n = 2p = m + q: each sign choice " "+-reciprocal, the gcd G itself", all(a and b for a, b, _ in found), f"{found}") def section_box(): print(f"BOX -- every signed 5-set in [0, {B}]^2 touching both axes") t0 = time.time() cells = [(a, b) for a in range(B + 1) for b in range(B + 1)] sets = rk1 = 0 rec, recflag, bad, seg, two = 0, 0, [], 0, 0 for S in combinations(cells, 5): if min(a for a, _ in S) or min(b for _, b in S): continue if rank(list(S)) < 2: rk1 += 1 continue sets += 1 lay = layers(list(S)) for sg in product((1, -1), repeat=4): P = poly(dict(zip(S, (1,) + sg))) g, fl = shared(P) if fl: seg += any(k == "1d" for _, k in fl) two += lay if any(k == "2d" for _, k in fl): TWO_D.append((P, [D for D, k in fl if k == "2d"])) if recip(P): rec += 1 recflag += bool(fl) elif fl: bad.append((S, (1,) + sg, [str(D) for D, _ in fl])) print(f" {sets} sets of rank 2 ({rk1} collinear skipped), " f"{16 * sets} signed G, {time.time() - t0:.1f} s") print(f" +-reciprocal G: {rec}, with a flagged factor {recflag}") print(f" flagged with a segment factor: {seg}; flagged on two " f"parallel lines: {two}") check("C3 SEGMENT and TWO LAYERS: no flagged G breaks either", seg == two == 0) for x in bad[:6]: print(f" {x}") print(f" flagged, not +-reciprocal: {len(bad)}") check("KILL no flagged G that is not +-reciprocal", not bad) def cross(u, v): return u[0] * v[1] - u[1] * v[0] def hull(points): """The convex hull's vertices, counterclockwise (monotone chain).""" pts = sorted(set(points)) out = [] for seq in (pts, pts[::-1]): part = [] for p in seq: while len(part) >= 2 and cross( (part[-1][0] - part[-2][0], part[-1][1] - part[-2][1]), (p[0] - part[-1][0], p[1] - part[-1][1])) <= 0: part.pop() part.append(p) out += part[:-1] return out def parallelogram(points): """The hull's 4 vertices v0..v3 with v0 + v2 = v1 + v3, or None.""" v = hull(points) if len(v) == 4 and all(v[0][i] + v[2][i] == v[1][i] + v[3][i] for i in (0, 1)): return v return None def midline_pairs(G, u): """Root pairs t0, 1/conj(t0) of G(z, .) at 8 points z, z along u: their count and the largest |Im R|/|R|, or None when G does not sit on three lines along u.""" g = gcd(abs(u[0]), abs(u[1])) u = (u[0] // g, u[1] // g) _, s, r = ext_gcd(u[0], u[1]) # s u0 + r u1 = 1 w = (-r, s) # det(u, w) = 1 terms = {(cross(x, w), cross(u, x)): c for x, c in terms_of(G).items()} js = sorted({j for _, j in terms}) if len(js) != 3: return None j0, alpha, A = js[0], js[1] - js[0], js[2] - js[0] pairs, worst = 0, 0.0 for k in range(8): z = np.exp(2j * np.pi * (k + SQ2 - 1) / 8) co = [sum(c * z ** i for (i, j), c in terms.items() if j - j0 == d) for d in range(A + 1)] roots = np.roots(co[::-1]) for t0 in roots: if abs(t0) <= 1 + 1e-6: continue if min(abs(roots - 1 / np.conj(t0))) > 1e-7: continue pairs += 1 wv = t0 / abs(t0) a, X, Y = co[0], co[alpha] * wv ** alpha, co[A] * wv ** A R = X ** A * Y ** (-alpha) * a ** (alpha - A) worst = max(worst, abs(R.imag) / abs(R)) return pairs, worst def ext_gcd(a, b): if b == 0: return (abs(a), 1 if a >= 0 else -1, 0) g, x, y = ext_gcd(b, a % b) return g, y, x - (a // b) * y def section_proof(): print(f"PROOF -- the later steps over the {len(TWO_D)} G with a " f"2-dimensional flagged factor") notpar = notx = unlayered = pairs = 0 worst = 0.0 for G, Ds in TWO_D: pts = list(terms_of(G)) for D in Ds: v = parallelogram(list(terms_of(D))) if v is None: notpar += 1 continue u = (v[1][0] - v[0][0], v[1][1] - v[0][1]) res = midline_pairs(G, u) if res is None: unlayered += 1 else: pairs += res[0] worst = max(worst, res[1]) c = parallelogram(pts) inner = [p for p in pts if c is None or p not in c] if c is None or len(inner) != 1 or any( 2 * inner[0][i] != c[0][i] + c[2][i] for i in (0, 1)): notx += 1 print(f" P not a parallelogram: {notpar}; the support not the " f"centered X: {notx}; not on three lines along P's side: " f"{unlayered}") print(f" MIDLINE: {pairs} root pairs, largest |Im R|/|R| " f"{worst:.2e}") check("C4 the proof's steps hold and MIDLINE's R is real", notpar == notx == unlayered == 0 and pairs > 0 and worst < 1e-9) def main(): t0 = time.time() section_controls() print() section_box() print() section_proof() 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())