Collision mechanisms

Grading a collision by δ does not say what puts one at full dimension. What does is a criterion that DERIVES δ rather than a column that agrees with it, and it starts from the shape a collision takes where the two factorizations share a factor: the collision can then be written with one factorization reading p·n times q and the other p times n·q — a block being one factor of a factorization in the semiring, a product of integer factors with no negative coefficient that splits into no two such — one block of each factorization carrying the shared p, the negative factor n moving between them, and any blocks that agree on both sides riding along as spectators. Now look along a direction. Initial forms multiply, and each is stripped of its single-term factor before the two sides are compared, so the face separates ONLY IF n's initial form has more than one term and at least one of p's and q's does: if n's is a single term both sides read the same stripped pair from p and q, and if p's and q's are both single terms both sides read n's alone. That direction is proved, and it is the one a sampled reading cannot reach — it bounds the separating faces from above, and so bounds δ from BELOW.

The converse holds with one clause, and the two together make the face law exact. Spectators contribute the same stripped form to both sides and cancel, so with P, N, Q for the stripped initial forms of p, n, q along the direction, the two sides read the multisets {P·N, Q} and {P, N·Q}, equal exactly when N = 1 or P = Q, by cancellation in the polynomial ring. So a face separates the two factorizations if and only if n's initial form has more than one term and p and q do not read the same stripped initial form there, both directions proved. The accident the sampled readings could not exclude is exactly that shared form, and at the 18 objects the criterion is stated at in the (2, 6) box it never fires, for a reason: at 17 of them q is a three-term factor whose polygon is a segment, so its only many-term initial form is q itself, three terms against p's two, and at the witness p and q are distinct two-term factors — the 231 face readings there confirmed a theorem about those objects. A factor's initial form has more than one term exactly when the direction is normal to a positive-dimensional face of that factor's own polygon — an edge, at product dimension 2 — so the law reads: δ = 1 exactly when the polygon of n has an edge parallel to an edge of the polygon of p or of q along which p and q read different stripped initial forms. And the clause bites. With p = 1 + t, n = 1 − t + t² and q = (1 + t) + y(1 + t + t²) + y²(1 + t), the product (1 + t³)·q is a 14-term 0/1 collision with exactly two factorizations — {1 + t³, q} and {1 + t, n·q}; in menu clothes {2, 16}·{2, 4, 6, 12, 18, 24, 36} = {2, 4}·{2, 6, 16, 18, 24, 96, 144}, a size pair outside both boxes — whose bottom and top edges are both parallel to n's segment and both read q's initial form as 1 + t, which is p: no proper face separates, and δ = 2 where the edge form without its clause reads 1. So an edge of n's polygon fails to separate in two ways, which an object may mix: no parallel edge on p or q, the witness at every edge, or a shared form, this object at every edge.

Every δ = 1 object reached is the six-term identity in different clothes — or, at the two seeded by {8, 27}, its homogenization x² − xy + y² — with n a three-term factor lying on p's own line and a two-term spectator riding along. The witness is the only object with no spectator at all, and its n is five terms spanning two dimensions whose polygon's edges miss the directions of both two-term factors present, (1, 0) and (1, −1). That is what full dimension inherited from no face means concretely, and it is not the extra dimension a six-member menu makes available: the dimension of n's polygon agrees with δ at every object too, and agrees only because every collinear n reached happens to sit on p's line. A collinear n on a line neither factor shares would read dimension 1 and δ = 2, which the criterion says and that column cannot.

The criterion's own hypothesis is its boundary. It is stated at 18 of the 22 in-frame objects the (2, 6) box holds and cannot be stated at the other four, whose two factorizations share no factor whatever: each is four blocks p₁n₁, p₂n₂ against p₁n₂, p₂n₁ over two nonnegative and two negative factors, no block of one side dividing a block of the other. There is no p, n or q to read a face against, so the criterion is not false there; it is UNSTATED, and what stands there is classified below.

Scope. The face law is a criterion, proved in both directions, and checked at 157 faces over the 18 shared-factor objects of the (2, 6) box, 39 of them separating, with no disagreement either way; why the shared form never fires at those 18 is a property of them. The parallel-edge form with its clause is the criterion restated at product dimension 2 and wears its tier. The 14-term object is a property, its two factorizations counted and every proper face read. Nothing here disturbs the grading on Menu collisions: no face of an object without a shared factor was read at all.

verifiers: explore_descent26_why.py, explore_descent26_close.py, explore_descent26_mix.py, explore_face_accident.py

Where the criterion is unstated the shape is still forced. Call two factorizations of one product mixing when, the blocks common to both set aside as spectators, no block of either divides a block of the other, and shared otherwise. At twelve terms the block sizes on a side are {2, 6}, {3, 4} or {2, 2, 3}, and a mixing pair carries no spectator at all: one would leave a six-term residue, whose only collision is the six-term identity — shared, 1 + v dividing 1 + v³ — or a four-term one, which factors uniquely. So wherever a three-term block sits on one side or the other it is reducible — an irreducible one would have to divide a block across — and a reducible three-term 0/1 polynomial is collinear, 1 + v^a + v^b along one direction v (the trinomial lemma). One lemma then does the rest, the cycle lemma: a six-term product tiled two ways as a three-term block times a binomial, with the binomials distinct, is the six-term identity in some power v^s — each binomial pairs the six exponents as a perfect matching, the two matchings' union is one alternating hexagon, and a hexagon of steps s and k closes only when one step is three times the other. Slice every block along the cosets of v, run the lemma on the slices, and two outcomes remain. A mixing pair with a three-term block on one side or the other is one-variable — every block a polynomial in v — or, in coordinates with v primitive — a monomial that is no proper power — and z off its line, it is the family {1 + v^2e + v^4e, (1 + v^3e) + z(1 + v^e)} against {1 + v^3e, (1 + v^2e + v^4e) + z(1 + v^e + v^2e)}, e ≥ 1. The family mixes at every e and every z off the line: its four-term and six-term blocks split no further, and no block divides one across, 1 + v^e and 1 + v^e + v^2e sharing no cyclotomic factor. And the one twelve-term shape the slicing never meets — no three-term block on either side, (2, 6) against (2, 6) — is shared, always, by the binomial-pair criterion below; so every mixing pair at twelve terms carries a three-term block, and the dichotomy is the whole of twelve terms.

Every mixing object the sweeps on Menu collisions met is this family in menu clothes at e = 1. The four of the (2, 6) box are {2, 16} against {2, 8, 32} with m·{1, 2, 4}, v the monomial of 2 and z that of m/2; and the (3, 4) half holds it from the other side. Read into blocks, its 71 in-frame collisions are 55 shared, every one the six-term identity beside a spectator binomial, and 16 mixing, every one {2, 8, 32} against c′·{1, 8} ∪ m·{1, 2} with c′ ∈ {2, 3} — exactly the 16 pairs the seed reading there leaves where the collinear seed's partner is itself a seed. On the line the family is present too, at z = v^j, and to exponent 24 it is all there is: 201 one-variable products of a three-term by a four-term block collide, 124 of their pairs mix, and every one carries the family's pair {1 + v^2e + v^4e, (1 + v^3e) + v^j(1 + v^e)} at some e from 1 to 6 — at two of them the six-term block on the other side splits, and that side reads three blocks against two.

Scope. The dichotomy is a theorem at twelve terms in frame, in any number of variables, on the cycle lemma, the trinomial lemma and the binomial-pair criterion; the family's mixing at every e is a property. The (3, 4) reading is exact over its box, sizes 3 in {2..32} against 4 in {2..24}; the one-variable search is exact to exponent 24, the cycle lemma checked beside it at every six-term product to exponent 30; nothing is claimed of one variable past that bound — whether one-variable mixing with a three-term block is still the family there is not asked here.

verifiers: explore_mixing34.py, explore_mixing26.py

The twelve-term shape with no three-term block is a binomial times a block against a binomial times a block: (1 + u)·H = (1 + u′)·H′ with u ≠ u′ monomials and H, H′ six-term 0/1 blocks — a two-member menu's core being a binomial. Such a pair carries no spectator, and no six-term block divides a block across, so it is shared exactly when one binomial divides a block of the other side — the other binomial, or the six-term block beside it; and that question is decided at any block size by one object, read on the two blocks as they stand — whether each is atomic, a block in the sense above rather than a product of two, is the pair's question and not the criterion's. Each binomial pairs the product's exponent vectors as a perfect matching, a term h of H with h + u; the union of the two matchings is a disjoint union of even alternating cycles, u-steps and u′-steps in turn. Off one line — u and u′ powers of two distinct primitive monomials — every irreducible factor of 1 + u is a cyclotomic polynomial in the primitive monomial under u alone and none is associate to a factor of 1 + u′, so 1 + u divides H′ outright: shared for free, as the twelve lattice points of a 4 × 4 square with its corners removed are, tiled by horizontal and by vertical dominoes. On one line, u = v^s and u′ = v^k with v primitive, put g = gcd(s, k), s′ = s/g, k′ = k/g and w = v^g, and split the support — the product's set of exponent vectors — along the cosets of w: each slice P_c is a polynomial in w alone, tiled by s′-pairs and by k′-pairs, and 1 + u divides H′ exactly when it divides every slice of it. Of different parity, s′ and k′ make the two binomials coprime and shared follows as off the line; s′ = 1 or k′ = 1 is one binomial dividing the other. Both odd, 1 + w^s′ and 1 + w^k′ share the one factor 1 + w, each exactly once, and every other factor of 1 + w^s′ already divides every slice of H′; so 1 + u divides H′ iff (1 + w)² divides every slice iff P_c′(−1) = 0 at every c — the same condition read from either side, the multiplicity of 1 + w in a slice being one more than in either block's. The pair mixes if and only if u and u′ lie on one line, s/g and k/g are coprime odd integers at least 3, and some slice has P_c′(−1) ≠ 0 — at any size, in any number of variables.

The cycles compute that derivative. With both steps odd, parity alternates round every cycle of a slice, and a cycle of 2m points closes when its signed s′-steps and signed k′-steps cancel, a·s′ + b·k′ = 0 with a ≡ b ≡ m (mod 2) and |a|, |b| ≤ m: (a, b) is the cycle's closing sum, and P_c′(−1) is s′ times a signed sum of the a's, one per cycle. A nonzero a is a multiple of k′ and its b a multiple of s′, so a cycle carrying one has at least 2·max(s′, k′) ≥ 10 points: a rectangle closes with a = 0, an 8-cycle does, and a 12-cycle does — its even a would be 6 = 2k′ with b = 2s′ ≤ 6, forcing s′ = k′ = 3 — while no 6-cycle exists at all with coprime odd steps at least 3, the cycle lemma's hexagon being the divisible case k = 3s. The shortest cycle with a nonzero closing sum is the 10-cycle at (s′, k′) = (3, 5). Twelve points seat no 10-cycle — the two left over would have to close a cycle of their own, which two distinct steps cannot — so every cycle of a twelve-term pair closes at zero, and (2, 6) against (2, 6) is shared, always, in any number of variables. The one-variable census agrees: among the 15,459 pairs of binomial tilings of a twelve-point support to exponent 36, every cycle off the divisible branch closes at zero and no support carries an 8-cycle at all; and the 19 pairs of atomic factorizations of that shape to exponent 30 are shared, each binomial dividing the other side's block.

And the emptiness is twelve's. At ten terms, {0, 3} + {0, 2, 4, 6, 8} = {0, 5} + {0, 2, 3, 4, 6} — in menu clothes {2, 16}·{2, 8, 32, 128, 512} = {2, 64}·{2, 8, 16, 32, 128} — is the product Φ₂Φ₅Φ₆Φ₁₀ of cyclotomic polynomials whose two sides, Φ₅Φ₁₀ against Φ₅Φ₆ beside their binomials, are its only two factorizations, each block atomic and neither dividing across: mixing with no three-term block, on a single 10-cycle at (3, 5) with closing sum (5, −3) and P′(−1) = 15. It is the only such collision at ten terms to exponent 30, its dilate by 2 aside, and at fourteen terms there are 24 to exponent 24 — a 14-cycle at (3, 7), (5, 7) or (3, 5), or the 10-cycle beside a rectangle. What twelve lacks is not the mechanism but the room to seat it.

Scope. The criterion is proved for a pair of binomials against blocks of any size, in any number of variables, read on the two blocks as they stand; the sharing at twelve terms is a theorem on it. The census is one-variable and exact in its boxes: binomial tilings to exponent 36, atomic factorizations to exponent 30 at ten and twelve terms and 24 at fourteen, with the criterion agreeing with the atomic classification at every pair it was read against. The ten-term specimen's uniqueness holds to exponent 30 and the fourteen-term count to 24; the absence of an 8-cycle on the line is exact to exponent 36 and claimed no further; and of one-variable mixing with a three-term block past exponent 24 nothing is claimed here either.

verifiers: explore_mixing26.py

Whether a pair collides at all, before any grading, has a closed form wherever the seed's core is exactly two factors irreducible over the integers. Write that core as n·p, with n the factor carrying a negative coefficient and p the nonnegative one, and let the partner's core be a single irreducible q. A factorization in the semiring is a grouping of the integer factors n, p, q into blocks; the groupings are five. Any grouping holding n alone is rejected. {n·p}, {q} always stands, n·p being the seed's own core — 0/1, and unsplittable since its only split isolates n. {n·q}, {p} stands exactly when n·q has no negative coefficient, its only split isolating n the same way. And the single block n·p·q never stands, {q}, {n·p} splitting it. So the product is non-unique exactly when n·q has no negative coefficient — unless q is p itself, where the two standing groupings are one multiset of blocks and the product is unique. The derivation uses nothing of n and p beyond their signs and the seed's core being 0/1, so it holds at every seed of that shape, whichever side of the pair the seed sits on; and the same five groupings give the sibling — a two-factor core with BOTH factors negative is unique against any single-factor partner, with no scan run.

The shape is the box's and not one core's. Both seed cores on the two-member side of {2..32} are of it — (1 + x)(1 − x + x²), shared by {2, 16}, {3, 24} and {4, 32}, and {8, 27}'s x³ + y³ = (x + y)(x² − xy + y²), the first two-variable seed core any walk here has had — and 735,357 of the box's 736,281 six-member menus have a single-factor core, so the scan decides the pairing of a two-member seed with a six-member menu at 99.87% of the box and the counter — the direct enumeration of a product's factorizations into blocks, which the sweeps run — is spent only on the rest. That is what the wide (2, 6) walk was bought with. And the full-dimension witness is the scan firing: its seed {3, 4, 8, 9, 18, 24} has a two-factor core, its partner {2, 3} the single factor x + y, and n·q there is the second factorization's own six-term factor, nonnegative as written.

Scope. Proved at every seed whose core is two irreducible factors with exactly one negative, against every single-factor partner. The q = p clause was found by the counter on a rehearsal box, where the scan without it disagreed at 72 of 13,517 pairs, every one a six-member seed with p = 1 + x against a two-member partner of core 1 + x; with the clause, 0 disagreements wherever the counter was run alongside — 114,449 pairs in {2..24} and 96,072 in {2..32}. Where the partner's core has two or more factors, or the seed's three or more, the scan says nothing and the counter decides; and the scan decides collision or not and never δ, which needs the factorizations and the faces.

verifiers: explore_descent26.py, explore_descent26_wide.py