Menu collisions

A menu's normalizer, read as a function of β rather than as a number, is a Dirichlet polynomial: the sum of m^−β over the menu's members. A route's weight is then set by a product of such polynomials, and the collisions above are the pairs of products that agree identically in β. They are generic rather than exotic: 4849 colliding pairs, falling into 4487 classes by the product they share. Measured directly, one scaling family accounts for 4369 of them: writing Z_A for the polynomial of a menu A, and cA for A with every member multiplied by c, they are the instances of Z_A·Z_cB = Z_cA·Z_B; another is {2}, {3, 6} against {3}, {2, 4}, both products 6^−β + 12^−β. What a collision count does NOT measure is non-unique factorization, and reading it that way is a non sequitur: a collision is compatible with unique factorization — 2·6 = 3·4 in the integers — being only a regrouping of one multiset of factors into two blocks. The scaling family is exactly that, the moved factor a single monomial, and so is the two-prime example just given. Where the failure is genuine it is the product's. Write x for p^−β at each prime p and a menu becomes a polynomial with every coefficient 0 or 1; a factor carrying a negative coefficient cannot itself stand in a nonnegative semiring, so the remaining factors pair around it two ways and the product has two different irreducible factorizations; and since the factors of a product are those of its two menus together, that negative factor belongs to one menu or the other, which makes carrying one a property of a SINGLE menu and never of the pairing. Call a menu that carries one a seed. At the census's scope that is almost nothing: 4839 of the 4849 pairs sit in a product that factors uniquely and are regroupings outright, and the other 10 sit in the 6 products that factor non-uniquely, each in exactly two ways, every one of them generated by one of the three seeds the scope holds, {2, 16}, {4, 32} and {2, 8, 32}. The semiring is genuinely not factorial, and the failure is not confined to a single prime: reading two of them at once as x and y, {8, 27}·{4, 6, 9} and {2, 3}·{16, 36, 81} span the same six products, and the negative-coefficient factor the others pair around is x² − xy + y² — the one-variable case's x² − x + 1 homogenized. WHEN factorization fails is graded by the two menus' sizes, their numbers of members: a product of menus of sizes s₁ and s₂ has s₁s₂ terms counted with multiplicity, and factorization in this semiring is classified by number of terms (van de Woestijne 2011), so it is classified by SIZE PAIR — at any bound on the elements, and by theorem rather than by census. Products at sizes (2, 2), (2, 4) and (3, 3) — 4, 8 and 9 terms — factor uniquely, several variables included. The one failing pair with both menus of size at most 3 is (2, 3), at 6 terms, and there non-uniqueness is forced onto a line: the exponent vectors of the shared product's terms lie in an arithmetic progression along a single direction, so the mechanism is an image of the one-variable one — a monomial substitution where that direction is nonnegative, a homogenization where it is mixed, and there is no third kind at that size. The two-prime pair above is exactly that case, a size-2 menu against a size-3 one. Confirmed on this corpus's own menus, every one of size 2 and 3 with elements in {2..32} and of size 4 with elements in {2..24}: not one product at 4, 8 or 9 terms factors non-uniquely, and all 39 found at 6 terms are collinear. The one-variable reading does not survive size 5 as a statement about whole products, though. At the size pair (2, 5), {2, 54}·{2, 6, 10, 30, 90} and {2, 6}·{2, 10, 54, 90, 810} share the ten-element product {4, 12, 20, 60, 108, 180, 324, 540, 1620, 4860}, which factors two ways with exponent vectors that lie on no line at all — the image of no one-variable polynomial under either operation. What hid it is menu SIZE: the pair needs a menu of five members and no census above goes past four. The elements need not be large for it — read at the cheapest primes the same family is {2, 16}·{2, 4, 6, 12, 24} against {2, 4}·{2, 6, 16, 24, 96}, largest member 96 against the first reading's 810. Taken whole, then, that product is past one variable; taken one edge at a time it is not, and grading that difference is the block below. What limits the door is therefore not the algebra alone but REALIZATION — whether menus carrying those polynomials assemble into an actual world — and realization's teeth are exactly one degeneracy: the unrealized collisions coincide precisely with the all-singleton ones, 44 of 44, where the four singleton menus of such a pair force equal move products, hence equal leading moves, hence a conflict at the first state. Everything with a non-singleton menu realizes, 4805 of 4849.

Scope. Exhaustive at the collision census's own scope — menus drawn from {2..16} ∪ {32} of size at most 3, the realization search's opening moves scanned to scale 8. The singleton direction is proved, whichever order the menus are taken in along the routes. The size-pair account carries the tiers of its parts: the classification by number of terms and the uniqueness at 4, 8 and 9 are the cited prior work, holding at any element bound and in several variables; the collinearity at 6 terms is proved here from that classification together with its own reduction of the several-variable case to the one-variable one; the sweep is exhaustive over the box named there. Both multi-prime specimens are hand constructions rather than census finds: the six-product pair sits outside the collision census's scope and inside the sweep's box, and the size-5 pair outside both, each verified exactly on the menus given; nothing is asserted about the size pair (2, 5) at large. The same scan cross-checks, from outside its proof, the coprime half of the coprimality dichotomy the door rests on: zero coprime realizations across all 4849 collisions, against 4805 realizations for worlds free to recycle.

verifiers: explore_rogue_world.py, explore_menu_factorization.py, explore_menu_reach.py

What the size-5 escape ends is the one-variable reading of a WHOLE product. A sharper one sits underneath it, and that one survives everywhere either this corpus or the literature reaches. Collect the exponent vectors of a shared product — one per term, as above — and take their convex hull. Looking at that hull from a chosen direction picks out a face: the terms whose vectors are extreme that way, a corner or an edge or something of higher dimension. The same look applied to a factor keeps its own extreme terms, its initial form, and initial forms multiply exactly as the factors they come from do. So a collision is never confined to the product it happens on: it restricts to EVERY face of the hull, each face carrying a collision of its own in lower dimension. The support-only half of that is classical and settled — the hull of a product is the Minkowski sum of the factors' hulls (Ostrowski), and enumerating those decompositions is a published factorization instrument (Gao and Lauder 2001) — and it is strictly weaker than the collision: {0, 1} + {0, 1, 3} and {0, 1, 2} + {0, 2} share a sumset and a term count with different convolutions. The productive half is the other one.

Grade a colliding pair by that restriction. The descent dimension δ is the smallest dimension of a face on which the two factorizations already differ — each initial form stripped first of any single-term factor, since a one-term factor is an atom that may sit beside either factorization and moving it is not a difference of mechanism. Small δ says the mechanism is INHERITED from a face rather than new at full dimension. δ ≥ 1 always: at a corner every initial form is a single term — a point decomposes only into points — and its coefficient divides the 1 the product carries there, so stripping leaves nothing on either side, a factor that has become 1 being no factor at all. No corner ever grades anything. The size-(2, 5) escape reads δ = 1, and what sits on the edge it descends to is (1 + v³)(1 + v + v²) = (1 + v)(1 + v² + v⁴) — the six-term identity itself, the case that escape was supposed to have left behind. Up to ten terms that is the rule: δ ≤ 1 throughout, so every mechanism there is one-variable on some edge. The term count does the work. Products of 4, 8 and 9 terms factor uniquely and every other count up to 10 is trivial or prime, save 6 and 10; what those two leave is the six-term form, three sporadic ten-term identities and two ten-term two-parameter families. The six-term form and the three sporadics spend one of their two free exponents on a translation, so their exponent vectors are collinear however they are lifted, and the families descend because the independence of their two parameters supplies a direction cutting an edge that carries the six-term identity. They are not all the SAME mechanism, though, and the rule does not say they are: those three sporadic identities regroup the three cyclotomic factors of 1 + x + ⋯ + x⁹ — one of them bare, two with a further cyclotomic factor riding along — and are not images of the six-term one. Whether any collision anywhere reaches δ ≥ 2 — full dimension, inherited from no face — is the question those counts locate, and it is answered below. No count below twelve can produce one: 11 is prime and so factors uniquely, which makes 12 the first COMPOSITE count past the classification. At twelve terms the menus can pair only as (2, 6) or (3, 4), and the qualifier is load-bearing: a menu's polynomial has every coefficient 0 or 1, so a factor carrying a coefficient above 1 is outside the menu frame altogether — the literature's own twelve-term example is such a factor — and those two size pairs exhaust the menu question rather than the polynomial one. The twelve-term instance this corollary names reads δ = 1 like everything below it.

The (3, 4) half has since been swept, and a sweep is a search over a box where everything above is a theorem. The box is this corpus's own menus — sizes 2 and 3 with elements in {2..32}, size 4 in {2..24} — walked wherever either side is a seed, which is the only way a pair can collide at all: 85,253 pairs. It returns 336 non-unique products, and the frame cuts them before anything is graded. A three-member menu against a four-member one gives twelve terms exactly when no two products coincide, and 265 of the 336 come out at ten terms or eight — a coefficient above 1, outside the frame just named. The in-frame population is 71, every one reads δ = 1, and the dimension column is what makes that a measurement rather than an artifact: all 71 sit at product dimension 2, so δ was free to read 2 at each of them and read 1 instead. The two products where δ ≤ dim forces the answer are both outside the frame.

Two readings sharpen that null result, and only the second leaves the box. The first says the box was not what constrained it, and it reads where the collisions are NOT. A pair's reachable dimension is the rank of the directions its two menus span and needs no factorization to compute; 96.5% of the walked box reaches dimension 3 or 4; and not one of those 82,249 pairs collides. Where dimension is plentiful there are no collisions at all — and it is not the seed holding the products down, since split by which half carries the seed both populations reach dimension 3 or 4 at better than 95%, the partner being unbounded. What collapses the dimension is the collision. Negativity cannot cancel across disjoint variables, so a second factorization must set the seed's negative factor beside a factor sharing its variables; where the seed is collinear — 64 of the 71 — the partner's core, its polynomial with its monomial content divided out, supplies one on the seed's own line at every one of them; and where that partner is not itself a seed — 48 of the 64 — the term count prices its core as two 0/1 binomials, one of them spent on that absorption and one direction left over. Dimension 2 by the law rather than by the box. Of the other 23, the 16 whose partner is itself a seed are one family, two-dimensional by its shape — one line and one direction off it — and mixing rather than sharing a factor (the mixing theorem); 7 are measured and unexplained. The graded instance itself, {2, 8, 32} against {2, 4, 16, 32}, sits outside the box and reads dimension 1 for a reason the seeds give: both halves are seeds, each the unique collinear one of its size in {2..32}, and their product is the only place either box holds where a collinear seed meets a collinear seed. All of that is still inside the boxes. The second reading is what carries out of them, being proved rather than searched, and it is a fact about seeds alone: a seed of n members has core dimension at most n − 2, at most n − 3 from five members on, and at most ⌊n/2⌋ at every size (the half-size ceiling). At four members that is 2, so the (3, 4) seed side is capped at every bound and not merely inside this box, while the same law puts a dimension-3 seed at six members or more, and most six-member seeds reach it. Whatever room the one surviving corridor has is therefore in the (2, 6) half, past every menu size swept here.

Scope. The face restriction and the polytope identity are the cited prior work; the descent dimension is a definition and δ ≥ 1 is proved from it. δ = 1 for the size-(2, 5) escape is exact on the one pair given. The bound up to ten terms and the twelve-term corollary are proved from the term-count classification cited in the block above, read in full, together with the grading of each family it leaves standing. Those are theorems and need no box; the twelve-term instance named with the corollary is a single graded object rather than a search. Everything from the (3, 4) sweep down is an observation over the box named there and carries its tier: exhaustive inside that box, silent outside it, and silent about the pairs the box excludes — among them the graded instance itself, whose four-member half reaches 32. The seed-dimension bound quoted at the end is proved and is the seeds page's; the collinear-seed reading of the graded instance is its census's. Each δ is read off a sampled set of directions, which can only overstate it by missing a face that differs, so the readings are upper bounds — the safe side for a search whose target is δ ≥ 2.

verifiers: explore_menu_faces.py, explore_descent_hunt.py, explore_seed_confine.py

Twelve terms, every coefficient 0 or 1, four 0/1 factors, and every proper face of its Newton polygon — corner and edge alike — induces the same factors on both sides. Only the whole polygon tells the two factorizations apart, so δ = 2 and the mechanism is inherited from no face. One witness settles an existence question, and this one is checked without a sampled search: for a two-dimensional polygon the faces can be enumerated outright, and they were. So the reading that survives the whole classification is false at the first term count where it could fail, and the classification of these collisions is structurally incomplete rather than merely unfinished.

Whether that failure is a curiosity or the rule is a second question, and the same pairing hunted through a wider box is what bears on it. Six-member menus with elements up to 32 number 736,281, against the 100,947 up to 24 that turned the witness up — 7.3 times the population, on a seed population nearly four times larger. That box carries 41 in-frame collisions, and they are 22 distinct pairs of cores: multiplying every member of a menu by one fixed integer changes its polynomial by a monomial and its core not at all, so one pair of cores wears several menu suits and counting at the menu counts one mechanism repeatedly. Of the 22, 21 read δ = 1 and exactly one reads δ = 2 — the identity above, wearing ten of those 41 suits. So the wider box turns up no full-dimension collision but the one already found: in the population walked it is a RARITY rather than the generic behaviour past the classification, and the incompleteness the witness opens is real and narrow.

The same box reads where the collisions are NOT, and it is the reading the (3, 4) half could not make: there the half-size ceiling caps a seed's core at dimension 2, so no seed could carry a third dimension into a pair by itself. At six members the cap is 3, and the wide box's seeds mostly reach it — 177 of its 203 six-member seeds have core dimension 3, against 26 at 2. A pair's reachable dimension contains its seed's core dimension and needs no factorization, so every one of the 177 × 465 = 82,305 pairs joining those seeds to a two-member menu reaches dimension 3 or more, and not one of them carries an in-frame collision: all 41 in-frame collisions of the wide box sit at product dimension 2, as the narrow box's 16 did. The room was there, seven times over, and went unused, which makes the confinement the surviving structure rather than the suspected one. And the witness's own seed has core dimension 2, so full dimension is not bought by the dimension a six-member seed can add — whatever selects it, it is not that.

Scope. The witness is exact and settles existence at any bound: the identity is checked as written, and the proper faces of its polygon are enumerated outright rather than sampled. That is what a δ of 2 needs and a δ of 1 does not — a sampled set of directions can only overstate δ, by missing a face that differs, so it is the safe side for reporting 1 and the unsafe side for reporting 2. The rarity and the confinement are observations over one box and are nothing more. A box bounds the SIZE of a menu's members and nothing the mathematics names, so alone in {2..32} can never mean alone — a wider box is a larger sample of an unbounded population, and every count here is a statement about the sample. The confinement is read over the in-frame population only: the wide box's products outside the frame — 4 of its 26 objects, where the narrow box had none — have no dimension reading here, so whether it extends to them is untested rather than settled. The menu frame is not the whole of the question either: a 0/1 polynomial can factor through a factor that is not 0/1, as the literature's own twelve-term example does, and nothing here has graded one.

verifiers: explore_descent26.py, explore_descent26_wide.py