Menu seeds

At two and three members, which menus are seeds is arithmetic on the exponents with no polynomial factored at all. The lever is a count. If a polynomial with every coefficient 0 or 1 is a product of two nonnegative ones, evaluate at 1: the value is the number of terms, each factor's value is at least its own number of terms, and the product's terms all lie among the pairwise products of the factors'. The two inequalities close on each other, so term counts MULTIPLY and both factors are themselves 0/1. That is elementary and is read here as a lemma of the classification of factorization in this semiring by number of terms (van de Woestijne 2011), not as anything new; what is new is using it one menu at a time. When the number of members is PRIME the count admits no nontrivial split, so one of any two nonnegative factors of the core has a single term, and a single term is what the content division has just removed: no nonnegative factorization of the core survives, and being a seed is exactly being REDUCIBLE over the integers — the semiring question becomes a classical one. Two and three members are prime.

At two members it closes in the elements. Write g for gcd(m, n) and d for the largest integer with m/g and n/g both perfect d-th powers; then {m, n} is a seed exactly when d has an odd prime factor. The core is U^d + V^d for coprime monomials U, V, and a sum of d-th powers factors over the integers exactly on that condition. Twelve menus of {2..64} pass. At three members it closes in the exponent vectors: a seed exactly when the core's exponent vectors are collinear — the core is then 1 + x^a + x^b along a single direction — and {0, a, b} meets all three residues modulo 3, and {a, b} is not {1, 2}. The middle clause is divisibility by 1 + x + x², the polynomial of the primitive cube roots of unity; the last removes that factor itself, which is irreducible. Five menus of {2..64} pass, carrying three distinct trinomials between them. That a cyclotomic factor — one whose roots are roots of unity — is the ONLY route into a reducible 0/1 trinomial is classical and is what warrants the middle clause; what is proved here is the reduction to it — the collinearity — which is why a criterion for a many-variable object never has to leave one variable. Each criterion is a parametric family rather than a list, so seeds are generable without a bound and only a sweep's PARTNER side is sampled by element size.

Four members keep neither mechanism: 44 seeds among the 31,465 menus of {2..32}, of which exactly 1, {2, 4, 16, 32}, has collinear exponents and none carries the cube roots' trinomial 1 + u + u² in any monomial u — each carries a binomial instead, which the last block proves is forced. What the term count leaves there is the shape of the NON-seeds instead — every reducible one a product of two 0/1 binomials, the only split four admits. And the collinear seeds are what the collision sweeps keep returning to: {2, 8, 32} is the unique collinear three-member seed of {2..32} as {2, 4, 16, 32} is the unique four-member one, and their product is the one place either box holds where a collinear seed meets a collinear seed, which is what makes it the graded instance it is.

Scope. The term-count lemma and the prime-size identity are proved. The two-member criterion is proved and checked against factorization at all 1953 menus of {2..64} with no disagreement; the three-member one is checked the same way at all 39,711, and its middle clause rests on the classical trinomial classification, cited rather than re-derived here. The four-member reading is an observation over the one box named.

verifier: explore_seed_shape.py

The collinearity clause at three members is one case of a bound that holds at every size: a seed of n members has core dimension at most n − 2 for n ≥ 3, and at most n − 3 for n ≥ 5. What carries both is a lemma about three terms: a 0/1 trinomial whose exponents are not collinear is irreducible outright — a change of monomial variables writes it as X^m(1 + X^a) + X^m′Y^c, which is Eisenstein at any root of 1 + X^a. If n exponent vectors have affine rank n − 1 they are affinely independent, so every one of them is a corner and the hull is an (n−1)-simplex. A simplex is indecomposable, but that means less than it sounds: its only Minkowski summands are scaled copies of itself, and it IS the sum of two of those, so indecomposability alone never forbids a factorization. What it does fix is the factors' hulls — both are scaled copies of the simplex — and over any triangular face of the simplex both factors then carry a genuine triangle, which would factor that face's trinomial. At rank n − 2 with n ≥ 5 the hull is a simplex with one term inside it, or a pyramid, or has a simplex for every face; each is indecomposable by the same chain of triangles, and each has a triangular face carrying no term but its corners — a simplex has more triangles than one inside term can touch — so the face argument runs unchanged. Such a core is irreducible over the integers and cannot be a seed. The hypothesis n ≥ 3 carries the argument: a SEGMENT has no triangular face, and 1 + x³ = (1 + x)(1 − x + x²) is the standing witness against the bound at two members — the negative factor the six-term identity turns on. At three members the bound is the collinearity clause; at four it gives dimension 2, which caps the seed side of every three-against-four collision at every bound and not merely inside a box; at five it gives 2 again.

And the ceiling is HALF THE SIZE: no reducible core of n members has dimension above ⌊n/2⌋, by the same two pieces at every size. A hull of dimension d > n/2 has fewer than 2d corners, and a d-polytope with fewer than 2d corners is indecomposable (Przesławski and Yost 2016), so both factors' hulls are scaled copies of it; and fewer than 2d terms cannot spoil every triangular face — a simplex has C(d+1, 3) triangles against the (d−2)(d−1) its at most d − 2 inside terms can touch, and any other hull has a facet missing two of the terms, where the same argument runs one dimension down until it ends at a triangle. That face's trinomial would factor. The sweeps agree: at nine members none of the 31,521 dimension-5 classes of {2..24} is reducible, at ten none of the 4,067 dimension-6 classes of {2..20}. The bound is exactly what a nonnegative split gives (ab terms at dimension at most a + b − 2), and seeds reach it at every size from four on: (1 − x + x²)(A + Σ y_iB_i) with each (1 − x + x²)A and (1 − x + x²)B_i one of 1 + x³, 1 + x² + x⁴ — {2, 16, 6, 24, 96} at five members and dimension 2, and (1 + x³)(1 + y + z) as the menu {2, 6, 10, 16, 48, 80} at six and dimension 3. So a seed of dimension 3 needs six members at least and is reached there, and the pairing of two members against six is where the collision sweeps found the one collision inherited from no face of its hull.

Scope. All three dimension bounds are proved, the half-size one resting on the cited polytope theorem for its indecomposability step; the trinomial lemma is checked at all 1,758 non-collinear three-member menus of {2..24}, and the bounds hold with no exception at three members over the 39,711 menus of {2..64}, at four over the 30,077 dimension-3 menus of {2..32}, at every class of dimension n − 1 or n − 2 from five to ten members over {2..24} (five, six, nine) and {2..20} (seven, eight, ten), and at every class above ⌊n/2⌋ over those same boxes through ten members. The attaining family is a construction.

verifiers: explore_seed_rank_law.py, explore_seed_rank_nine.py, explore_seed_confine.py

Every negative factor written out above is 1 − x + x², which vanishes at a primitive sixth root of unity. Call a factor torsion-rooted when it vanishes at some tuple of roots of unity — a torsion point of the torus — and torsion-free when it vanishes at none, and call a seed rooted or free by its negative factor — and mixed where a core carries several negative factors and they differ in kind, free then meaning every one of them is. Along a line, where the core is a polynomial in one variable, torsion-rooted means carrying a cyclotomic factor. The split is decidable: a factor sees a torsion point only through the lattice its exponent differences span, so it is rewritten in a basis of that lattice, and a bound of Mann's on minimal vanishing sums of roots of unity — in such a sum of r terms, normalized to contain 1, every root has order dividing the product of the primes up to r — makes one finite search over that lattice's torsion decisive.

The least size of a free seed is 3. A two-member core is 1 plus a monomial, every factor of which is cyclotomic; and 1 + x⁴ + x⁵ = (1 + x + x²)(x³ − x + 1) — the plastic number's polynomial in −x beside the cube roots' — is the menu {2, 32, 64}, one of the five three-member seeds of {2..64} by the criterion above. Ljunggren and Tverberg (a reducible 0/1 trinomial's non-cyclotomic part is irreducible or 1) make that the trinomial rule: a three-member seed is free exactly when its non-cyclotomic part is negative, 98 of the 435 trinomials to degree 30. Along a line the least DEGREE is 5 — none at 4 or below, four at 5 — five terms first reach a free seed at degree 7, 1 + x + x³ + x⁴ + x⁷ = (1 + x + x² + x³ + x⁴)(x³ − x² + 1), and FREE IS THE GENERIC KIND: from degree 7 on the free seeds outnumber the rooted at every degree, 7,966 against 767 at degree 16. The shape throughout is a cyclotomic cofactor beside a torsion-free negative factor; a census of 0/1 polynomials reducible with no cyclotomic factor at all counts something else and excludes exactly this shape.

In the plane the swept boxes of five to nine members hold 37 seeds — 28 of six members in {2..24}, 9 of eight in {2..20}, none of five, seven or nine there — 35 rooted and TWO free: {2, 3, 4, 8, 16, 24}, core (1 + x)[x(1 + x²) + y(1 − x + x²)], and its mirror {2, 3, 6, 12, 16, 24}, core (1 + x)[x(1 − x + x²) + y(1 + x²)], both of dimension 2. Both are free by hand: with x = e^iθ on the unit circle the two coefficients of the bracket have moduli |2cos θ| and |2cos θ − 1|, a zero with |y| = 1 needs them equal, and they are equal only at cos θ = ¼ — where x + x⁻¹ = ½ is no algebraic integer, so x is no root of unity. The factor does meet the unit torus, at that point; it meets no torsion point. Every seed in these boxes has cofactor 1 + x, which forces an even number of terms — a 0/1 polynomial vanishing at x = −1 identically in y has as many even exponents of x as odd — so the odd sizes are empty there and not in general, the three-member seed above being odd. Writing the bracket A + L with A in x alone, the split is whether L can vanish where A does: x(1 − x + x²) + L is rooted at a sixth root beside a vanishing sum of L's monomials, and x(1 + x²) + y(1 − x + x²) is not, its two pieces vanishing nowhere together. Of the 35 rooted, 14 have a zero with one coordinate off 1 in the lattice's own coordinates and 21 only off those axes, so a cyclotomic factor of a coordinate restriction is the wrong invariant more often than not, and 20 contain a whole torsion line.

Scope. The size floor is proved, two members excluded and three attained; the degree floor and the generic count are exhaustive over every 0/1 polynomial with constant term 1 to degree 16, and the trinomial rule to degree 30 with the cited theorem re-verified on every reducible trinomial there. The two plane witnesses are free by the proof given and by the complete search; the 35 rooted ones and their axis and line counts are observations over the five boxes named, every one decided at order 6. The common cofactor is a print over those boxes at six and eight members; at four it is the theorem of the next block.

verifiers: explore_seed_torsion.py, explore_seed_line_floor.py, explore_seed_plane_floor.py

The closure is a theorem rather than a census. THE COFACTOR THEOREM: a four-term 0/1 polynomial, in any number of variables, whose core is reducible over the integers is divisible by a binomial 1 + u for some monomial u; and with it, every negative factor of a non-collinear four-member seed is torsion-rooted. A four-member core has a torsion zero only where its monomials split into two antipodal pairs — a vanishing sum of four roots of unity has no other shape, by Mann's bound — so such a zero is read off the exponent vectors alone, and it is this pairing the proof turns on. Dimension 3 is irreducible outright: the hull is a tetrahedron, each factor's hull a scaled copy of it, and a facet carries a trinomial with non-collinear exponents, irreducible by the lemma above. Along a line, Mills's theorem on quadrinomials (the non-cyclotomic part of xⁿ ± x^m ± x^p ± 1 is irreducible except for four listed forms, none of them with every sign plus) gives a reducible core a cyclotomic factor, the pairing at its root writes the core as xⁱ(1 + x^s) + x^k(1 + x^t) with s and t sharing their 2-adic valuation, and 1 + x^d, d that power of 2 times the gcd of the odd parts, divides both halves. In the plane a factorization g·h is pushed onto the line by y → x^K for every K past the hull's width, which keeps both factors' terms distinct; Mills makes one factor's image cyclotomic for infinitely many K — a factor free of y is then cyclotomic in x and vanishes on a line x = ζ outright; otherwise its image's degree grows with K, Hajós's bound (a nonzero root of a polynomial of t terms has multiplicity below t) gives that image unboundedly many distinct roots of unity ζ, each a torsion point (ζ, ζ^K) on the factor's curve, and the Ihara–Serre–Tate theorem (an irreducible curve in the plane torus through infinitely many torsion points is a torsion coset, the locus w = ζ of one monomial w and one root of unity) puts such a coset on the curve. The core vanishes along it, so at its infinitely many torsion points one pairing of the four monomials holds, which forces both differences to be powers of w, and the line step then gives, with u = w^d: the core is (1 + u)(m₁ q_s(u) + m₂ q_t(u)) with q_n the alternating sum 1 − u + ⋯ + uⁿ⁻¹, s and t odd. Off a line the ratio m₂/m₁ is no power of u; the bracket's non-cyclotomic part is then irreducible — by Capelli's criterion (Y^j − C is reducible over a field only when C is a p-th power for a prime p dividing j, or −4 times a fourth power with 4 | j), read over the rational functions of u's line and carried to the integers by Gauss's lemma — and it vanishes at the torsion point sending u to 1 and that ratio to −1, since q_s(1) = q_t(1) = 1. Along a line the ratio can be a power of u, and then that point is gone: the same shape is free at degree 5, 1 + x³ + x⁴ + x⁵ = (1 + x)(1 − x + x² + x⁴). The 43 non-collinear four-member seeds of {2..32} are the census instance — 41 with bracket m₁ + m₂(1 − u + u²), two with core a binomial times 1 + u³ and negative factor 1 − u + u² itself — and the statement is checked past the census over every four-point configuration of [0, 6]² up to translation (1,921 reducible, every one with a binomial factor and a quadrilateral hull), of [0, 2]³ at dimension 3 (none reducible) and the line to degree 60 (14,825 seeds, each with a binomial factor). So a free seed of the plane has at least five members: three are collinear and four are closed by the theorem. What five members carry, and what about them is still open, is Five members: a free factor beside a rooted one.

Scope. The cofactor theorem and the four-member closure are proved in every number of variables, resting on Mills, Hajós, Ihara–Serre–Tate and Capelli as cited, with Mann's bound supplying the pairing. The 43 non-collinear four-member seeds of {2..32} are the census the theorem was read from, and the box counts beside them are checks of a proved statement, not its evidence. That a free seed of the plane has at least five members is this theorem with the three-member criterion above.

verifiers: explore_seed_cofactor.py, explore_seed_plane_floor.py

A five-member core can carry a torsion-free negative factor, and everywhere the plane has been searched a rooted factor stands beside it. The menu {2, 6, 16, 96, 1536} has core 1 + x³ + y(1 + x⁴ + x⁸) = (1 − x + x²)[(1 + x) + y(1 + x + x²)(x⁴ − x² + 1)], the bracket linear in y with coprime coefficients and so irreducible, and torsion-free by hand. With x = e^iθ on the unit circle write t = 2 + 2cos θ: then |1 + x|² = t, |1 + x + x²|² = (t − 1)² and |x⁴ − x² + 1|² = (t² − 4t + 1)², so a zero with |y| = 1 needs the two coefficients' moduli equal, which is t = (t − 1)²(t² − 4t + 1)² — a sextic irreducible over the integers with two of its roots non-real. So no root of it has all its conjugates real, while 2 + 2cos(2πk/n) does: no root of unity makes the moduli agree. The factor does meet the unit torus, at the sextic's four real roots; it meets no torsion point. Beside it stands 1 − x + x², vanishing at a primitive sixth root of unity — the seed is mixed.

At five members a cyclotomic factor forces that shape. THE ROW LEMMA: let a five-member core have a factor vanishing along a whole torsion coset w = ζ, and take monomial coordinates in which w is x. That factor divides every row of the core in y, each row a 0/1 polynomial in x vanishing at ζ, and the nonzero rows' term counts sum to five. A single term never vanishes, so a non-collinear core leaves the counts 2 and 3: a binomial 1 + x^s up to a monomial, at whose root ζ^s = −1, so that ζ has even order; and a trinomial, whose three terms at ζ are a rotated 1 + ω + ω² by Mann's bound, so that the order is divisible by 3. So ζ has order divisible by 6, and the rows' greatest common divisor G — a factor of the binomial row, which is a product of cyclotomics outright — is a product of cyclotomics of such orders. Each of those has degree at least 2, its constant and leading terms 1, and the value 1 at the all-ones point — every variable set to 1 — and so has G: nonnegative coefficients would sum to more than 1 there, so G carries a negative one and is a rooted negative factor. Five being prime, what remains takes the value 5 at that point. It is the bracket A + y^kB whose coefficients are the two rows divided by G, and it is irreducible: at k = 1 outright, and past it by Capelli's criterion, since A and B are coprime with values 2 and 3 at the all-ones point and neither of those is a perfect power. So the rooted factor sits on the value-1 side and any free one on the value-5 side, the reverse of the line's arrangement, and a five-member seed with EVERY negative factor free carries no cyclotomic factor at all — the shape a line first reaches at degree 12, with seven terms, and never with five. The box [0, 8]² holds no such seed: of its 25,621,596 five-point subsets, 130 are seeds, and they are 33 mixed — every one the identity exhibited here, read in some direction w — and 97 rooted, of two further identities. So the least size at which the plane holds a seed free outright stays six, attained by the two six-member witnesses, and whether five ever reaches it is the line's question wearing the plane's coat: by the row lemma such a core has no factor carrying a torsion coset at all, and a reducible 0/1 polynomial of five terms with no cyclotomic factor is what the line does not show either.

Scope. The exhibit is a proof: the factorization and the sextic's irreducibility and root count are computed exactly, the freedom argued from them, and the same factor read free by the complete torsion test (dimension 2, seven terms, orders dividing 1260, no zero). The row lemma is proved as stated at five members, resting on Mann's bound and Capelli's criterion as cited, and it holds at all 130 seeds of the box. The counts are an observation over [0, 8]², complete there: every five-point core is read up to translation and the box's symmetries, through a decomposability test on the hull that no reducible core fails. The line's census of the reducible 0/1 polynomials with no cyclotomic factor is exhaustive to degree 16: the first sit at degree 12 with seven terms, and none in the range has five. Six as the least size free outright is that census beside the two six-member witnesses; past exponent 8 it is open.

verifiers: explore_seed_pentanomial.py, explore_seed_line_floor.py