mixing.py
Checks: COLLIDE: The cycle lemma theorem; COLLIDE: The mixing theorem theorem; COLLIDE: The family mixes at every e property; COLLIDE: The binomial-pair criterion criterion.
Cited on: COLLIDE.
To run it: save mixing.py, with collide.py beside it; needs sympy.
"""mixing.py -- two factorizations at twelve terms where no block divides
a block across, and the lemma that pins them.
QUESTION. Two atomic factorizations X and Y of one nonnegative product
F, with the blocks both sides hold set aside as SPECTATORS, are SHARED
when some block of one side divides some block of the other (on the
multiset of Z-irreducible atoms), and MIXING when none does. At
coefficient sum twelve -- twelve terms counted with multiplicity, the
value of every product of a three-menu and a four-menu, or of a
two-menu and a six-menu -- which mixing pairs exist? Does the answer
need the product to be 0/1, or does it hold for every nonnegative
product of content 1? And between two binomials, (1 + u) H = (1 + u')
H', what decides mixing at any size?
THE ARGUMENT (written before the engine). F has content 1 and value
F(1) = 12; blocks are atomic, so none is a monomial and each has value
at least 2. Blocks are read up to monomial factors.
(A) SPECTATORS FORCE SHARING. A common block S of value 2, 3, 4 or 6
leaves a residue F / S of value 6, 4, 3 or 2 carrying two
distinct atomic factorizations. Over N a polynomial of value 2,
3 or 4 factors uniquely and one of value 6 is non-unique only as
X^a (1 + X^b + ... + X^(5b)), whose factorizations {1 + X^b,
1 + X^(2b) + X^(4b)} and {1 + X^b + X^(2b), 1 + X^(3b)} are
shared, 1 + X^b dividing 1 + X^(3b) (van de Woestijne's
classification, arXiv:1103.0709, counted with multiplicity). So a mixing
pair has no spectator, and a side is {12}, {2, 6}, {3, 4} or {2, 2, 3} by
value; a side {12} is one atomic block every block across divides.
(B) EVERY BLOCK OF A MIXING PAIR IS REDUCIBLE. A Z-irreducible block
is an atom of F and lies in some block across, which it divides.
A block of value 2 is a binomial with distinct terms (content 1).
One of value 3 is a 0/1 trinomial, since a binomial of value 3
is Eisenstein at 2 after a unimodular change of variables, so by
the trinomial lemma of collide.py it is collinear:
T = 1 + v^a + v^b along one primitive monomial v.
(C) THE CYCLE LEMMA, FOR MULTISETS. Let a six-slot multiset of
integers be tiled two ways, T + {0, alpha} = S + {0, s}, T and
S three-slot multisets, alpha, s distinct and positive. At each
point the alpha- and s-edges meet equally often, so the edges split into
alternating closed trails. A trail of one edge of each kind joins
the same two points, forcing alpha = s, so there is one trail of
three edges of each kind. Its signed alpha-steps sum to an odd
A and its s-steps to an odd B with |A|, |B| <= 3 and A alpha + B s
= 0, so {|A|, |B|} = {1, 3}: s = 3 alpha or alpha = 3 s, and the
three steps of the shorter kind share a sign. Walking the three
sign patterns of the longer steps visits six consecutive
multiples of the shorter step, all distinct. So the multiset is a
set, m + g {0, 1, ..., 5} with g = min(alpha, s), and the two
tilings, each multiset read as the exponents of a polynomial in
v, are the six-term identity (1 + x)(1 + x^2 + x^4) =
(1 + x + x^2)(1 + x^3) in x = v^g. A tiling with a doubled point
has no second binomial at all.
(D) THE TOP SLICE. Let X hold the trinomial T along v, R = F / T the
rest of X (value 4, nonnegative), and suppose F does not lie in
one coset of the line Z v. Slice every polynomial along the cosets
of Z v: F_c = T R_c. The quotient lattice is free abelian, so for a
generic weight w vanishing on v the top slice of a product is the
product of the top slices. Every atom of T lies in Z[v, 1/v] and
divides the v-CONTENT (the gcd of the slices) of the block of Y
holding it; if a single block of Y had nonmonomial content, T
would divide it. So two blocks of Y have nonmonomial content, their
top slices have value at least 2 each, and the top slice of F,
T R_top, has value 3 R_top(1) >= 4: R_top(1) >= 2 at every vertex
of R's coset support. R has value 4 and at least two
cosets, so it has exactly two, of value 2 each. Each slice of F is
L, the product of Y's blocks on the line, times the one spanning
block's slice there (cosets add as sets), so the spanning block's
two slices have equal value: monomials, value 3, or value 2
beside L of value 3. A slice of R that is twice a monomial makes
F's slice 2 m T, of content 2, while every block has content 1
(Gauss, F having content 1): only a slice 2 m' of a spanning
four-block beside L = T' can carry it, and 2 m' T' = 2 m T makes
T' = T up to a monomial, which is sharing; so R's slices are
binomials,
1 + v^alpha and z (1 + v^beta), z off the line.
(E) THE CASES. The sumset bound in an ordered group makes exactly one
block Z* of Y span both cosets, the rest lying on the line.
Y = {B, S}, Z* = B = 1 + z': S is one slice, S = T (1 + v^alpha),
and T divides S. Y = {B, S}, Z* = S: B = 1 + v^s on the line
divides both slices, T (1 + v^alpha) = B S_0 and T (1 + v^beta) =
B S_1 with S_c of value 3, and (C) reads each slice as the binomial
itself (s = alpha, S_0 = T) or the six-term identity, where T fixes
e: T = 1 + v^2e + v^4e with alpha = e, s = 3e, or T = 1 + v^e +
v^2e with alpha = 3e, s = e. Both slices alike: S = S_0 (1 + z)
is not atomic. Slices (binomial, identity) with T = 1 + v^e + v^2e:
B = 1 + v^e divides R = (1 + v^e) + z (1 + v^3e). What is left is
T = 1 + v^2e + v^4e, alpha = 3e, beta = e:
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)}.
Y with a trinomial T': Z* = T' leaves the line blocks a value-4
content, and slices of value 8 and 4 against 6 and 6. Z* a
binomial across: both slices of F are one polynomial, alpha = beta,
R = (1 + v^alpha)(1 + z), and the binomial across is 1 + z, a
spectator. Z* the four-block Q': T' lies on the line, T (1 +
v^alpha) = T' Q'_0, and (C) makes T and T' the two trinomials of
the identity at one e, so alpha = beta and R and Q' are each a
product of two binomials sharing 1 + z, a spectator.
THE DICHOTOMY: at value twelve, for any nonnegative F of content 1, a mixing
pair has a trinomial block T ((H) below closes the sides {2, 6} against
{2, 6}, the one pair of shapes without one), and either F lies in one coset
of T's line or the pair is the family. No 0/1 hypothesis is used: (A) counts
with multiplicity, (B) needs content 1, (C) and (H) are proved for multisets,
and (D) and (E) read values.
(F) THE FAMILY MIXES AT EVERY e >= 1, z off the line. With G =
Phi6(v^e) + z, irreducible as Eisenstein in the coordinate off
the line at any prime factor of the squarefree Phi6(v^e), the
blocks are Phi3(v^e) Phi6(v^e) and (1 + v^e) G
against (1 + v^e) Phi6(v^e) and Phi3(v^e) G. The cyclotomic atoms
of 1 + v^e, Phi3(v^e) and Phi6(v^e) are pairwise disjoint (their
indices differ at the prime 2 or the prime 3), so no block divides
one across. The trinomial and the binomial are atoms by value;
a nonnegative split of (1 + v^e) G or Phi3(v^e) G puts G in a part
G k with k on the line, whose slice k z needs k a monomial, and
then the part has Phi6's negative coefficient.
(G) THE BINOMIAL-PAIR CRITERION, any size, any number of variables.
A pair (1 + u) H = (1 + u') H' MIXES when neither binomial divides a
block across, H and H' each read as one block. Write u = w^s, u' = w'^k
with w, w' primitive. Off one line the binomials' atoms are cyclotomics
in different primitive monomials, so 1 + u, squarefree and coprime to
1 + u', divides H'. On a line, v primitive, g = gcd(s, k), s = g s',
k = g k', W = v^g: if s' or k' is even the binomials are coprime
again; if s' = 1 the one binomial divides the other. With s', k'
odd and at least 3, 1 + W^s' and 1 + W^k' share only the atom 1 + W, each
once, so 1 + u divides H' iff (1 + W)^2 divides every slice P_c of
P along the cosets of Z W -- the same condition as 1 + u' dividing
H. Since P_c = (1 + W^s') H_c, P_c'(-1) = s' H_c(-1). So:
NEITHER BINOMIAL DIVIDES A BLOCK ACROSS IFF u, u' lie on one
line, s', k' are coprime odd integers >= 3, and some slice has
H_c(-1) != 0.
No positivity is used.
(H) TWELVE SEATS NO SUCH CYCLE. H_c(-1) sums, over the alternating
closed trails of the two matchings on the slice's multiset, the
signed sums A of their s'-steps: every step is odd, so each
s'-edge's lower end has the parity of the trail's start when the
step is up and the other parity when it is down. A trail of m
edges of each kind, B the signed sum of its k'-steps, closes with
A s' + B k' = 0, |A|, |B| <= m; a
nonzero A is a multiple of k' and its B of s', so m >= max(s', k')
>= 5. Twelve slots hold one such trail of m = 5 beside a two-slot
trail, which forces s' = k', or one of m = 6, where A is even,
|A| = 2k' <= 6 forces k' = 3, and |B| = 2s' <= 6 forces s' = 3 =
k'. So every binomial pair of value twelve is shared, multisets
included, and with (E) the dichotomy is the whole of value twelve.
DESIGN. collide.py supplies the Z-factors and the menus' cores.
Sections:
CONTROL: the six-term identity's two factorizations read SHARED; the
ten-term pair {0,3} + {0,2,4,6,8} = {0,5} + {0,2,3,4,6}, in menu
clothes {2,16} x {2,8,32,128,512} = {2,64} x {2,8,16,32,128},
counted and read MIXING, the criterion reading MIXING there too.
CYCLE: every T = {0, a, b} with 0 <= a <= b <= 30, every alpha in
1..30 and every s != alpha a positive point of the multiset (a
peel's s is one): T + {0, alpha} peeled by {0, s} from its least
point; every success is recorded as direct
or not and compared with the six-term identity.
FAMILY: e = 1..4 with z a second variable, and four menu realizations;
the counter's factorizations, the classification, and the
product's term count.
BOX: every pair of a three-menu of {2..32} and a four-menu of
{2..24} with a seed on either side; the atoms of the product are
the two menus' atoms, so no product is factored. Every pair with
two or more atomic factorizations is read: in frame (the product
0/1) or not, Newton dimension, and every pair of its
factorizations classified -- spectators, block values, shared or
mixing, every mixing block reducible, and each mixing pair
matched against the family or found on one line.
BINOMIAL: every multiset H of six points in 0..12 with least point
0 and every s in 1..12: P = (1 + v^s) H, every second binomial
tiling k, the criterion's reading from H_c(-1) against direct
division. The same at value ten (five points in 0..14, s in 1..14)
and fourteen (seven points in 0..10, s in 1..10), where the
criterion must meet mixing pairs.
LINE: the family member e = 1 on the line at z = v^8, and the two
supports where the other side splits into three blocks; counted
and classified.
PREDICTIONS (fixed before the engine).
P1 CONTROL: the six-term identity reads SHARED; the ten-term pair has
exactly 2 atomic factorizations and reads MIXING; the criterion
reads MIXING at it with H(-1) != 0.
P2 CYCLE: every success with alpha != s is direct and is m + g {0,
..., 5} with g = min(alpha, s) and max = 3 g; no multiset with a
doubled point has a second tiling.
P3 FAMILY: every member has 12 terms, all 1, exactly 2 atomic
factorizations, and reads MIXING with no spectator.
P4 BOX: the pairs walked number 85,253, and those whose product
factors two ways 336, of which 71 lie in frame (TRANSPLANT: an
earlier count of this box). In frame, every pair is shared with a
spectator or mixing and the family at e = 1. Out of frame, every
mixing pair lies on one line (Newton dimension 1); how many mixing
pairs exist out of frame is the measurement. In and out of frame
alike: no mixing pair has a spectator, every block of a mixing pair
is reducible, and every mixing pair has a trinomial block.
P5 BINOMIAL: at value twelve every second tiling reads SHARED by the
criterion and by division, direct or not; at ten and fourteen the
criterion and division agree at every pair and MIXING occurs.
P6 LINE: the line members read MIXING [ruled: the one member built, e = 1,
j = 8, checked for its factorizations and shapes]; the split supports read
two atomic factorizations of value shapes (2, 2, 3) and (3, 4), MIXING.
KILLS. P1 is the positive control: if it misses, nothing after it is
read. A success in CYCLE that is not the identity, or any non-direct
success, kills (C). A mixing pair in BOX of Newton dimension 2 or more
that is not the family, in frame or out of it, kills (D) or (E), and
out of frame it names the multiset step. A mixing pair with a
spectator kills (A); one with an irreducible block kills (B). A
BINOMIAL row at twelve read MIXING by either reading kills (H); a
disagreement of the criterion with division anywhere kills (G). A
family member that is shared or counts other than 2 kills (F).
FINDINGS. Every prediction held and no kill fired.
P1 the six-term identity reads 2 factorizations, SHARED; the ten-term
pair 2 factorizations, MIXING at shapes (2, 5) against (2, 5), and
the same in menu realizations, where the two products agree; the
criterion reads MIXING with H(-1) = 5.
P2 54,435 peels, T and alpha to 30, give 17 second tilings, all 17
direct and the
six-term identity; no multiset with a doubled point has one.
P3 e = 1..4: 12 terms, 2 factorizations, MIXING, the template's own
e; {2,8,32} x {2,6,12,16}, {2,18,162} x {2,10,30,54} and
{3,12,48} x {5,7,14,40} at e = 1 and {2,32,512} x {2,3,12,128} at
e = 2, each 2 factorizations and MIXING.
P4 13,350 menus with 1 and 17 seeds; 85,253 pairs, 336 whose product
factors two ways, 71 in frame: 55 SHARED with a spectator and 16
MIXING, every one the family at e = 1, all 71 at Newton dimension
2. Out of frame all 265 are SHARED, 263 at dimension 2 with no
spectator and 2 at dimension 1 with one; the out-of-frame clause of
P4 therefore had no mixing pair to read and is printed, not counted, and
the box meets the non-0/1 half of the dichotomy only on its shared side.
The lemma clauses held at all 16 mixing pairs.
P5 value twelve: 3,036 tiling pairs, 2,503 with a doubled point,
none MIXING by either reading; value ten: 88 pairs, 2 MIXING, both
direct; value fourteen: 326 pairs, 13 MIXING, 11 of them with a
doubled point. The criterion equals division at every pair.
P6 the line member e = 1, j = 8 has 2 factorizations, MIXING at
(2, 6) against (3, 4); the supports {0,1,3,...,11,14} and its
reflection have 2 each, MIXING at (2, 2, 3) against (3, 4).
RUN RECORD. python mixing.py: 9 of 9 checks, 29.3 s, peak commit 87.7 MB, the
out-of-frame clause printed. The first run was killed at 520 MB during the box
walk: every block product of every pair sat in one cache. The caches are now
cleared after each pair; nothing else changed.
"""
import os
import sys
import time
from collections import Counter
from itertools import combinations, combinations_with_replacement
from math import gcd
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
from collide import ( # noqa: E402
GENS, Dp, menu_factors, negative, nonneg, prod, rank, set_partitions,
zfactors)
CHECKS = []
R = len(GENS)
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 ev(*e):
return tuple(list(e) + [0] * (R - len(e)))
def dp(pairs):
"""A Dp from (exponent list, coefficient) pairs."""
out = Counter()
for e, c in pairs:
out[ev(*e)] += c
return Dp(out)
def uni(exps):
"""The one-variable polynomial with these exponents, in x0."""
return dp([((e,), 1) for e in exps])
# ------------------------------------------------ atoms and factorizations
ATOM_ID, ATOMS, ATOM_VAL = {}, [], []
def aid(f):
key = frozenset(f.d.items())
if key not in ATOM_ID:
ATOM_ID[key] = len(ATOMS)
ATOMS.append(f)
ATOM_VAL.append(sum(f.coeffs()))
return ATOM_ID[key]
PN = {}
def prod_nn(ids):
"""The product of the atoms with these ids, and whether it is
nonnegative; ids a sorted tuple."""
if ids not in PN:
p = prod([ATOMS[i] for i in ids])
PN[ids] = (p, nonneg(p))
return PN[ids]
AT = {}
def atomic_block(ids):
"""Nonnegative, and no split into two nonnegative sub-products."""
if ids in AT:
return AT[ids]
ok = prod_nn(ids)[1]
n = len(ids)
if ok and n > 1:
seen = set()
for r in range(1, n):
for sub in combinations(range(n), r):
a = tuple(sorted(ids[i] for i in sub))
if a in seen:
continue
seen.add(a)
b = tuple(sorted(ids[i] for i in range(n) if i not in sub))
if prod_nn(a)[1] and prod_nn(b)[1]:
ok = False
break
if not ok:
break
AT[ids] = ok
return ok
def factorizations(ids):
"""The distinct atomic factorizations of the product of the atoms
with these ids: sorted tuples of blocks, a block a sorted id tuple."""
out = set()
for part in set_partitions(list(range(len(ids)))):
blocks = tuple(sorted(tuple(sorted(ids[i] for i in b))
for b in part))
if all(atomic_block(b) for b in blocks):
out.add(blocks)
return sorted(out)
def value(block):
v = 1
for i in block:
v *= ATOM_VAL[i]
return v
def within(a, b):
"""Multiset inclusion of atom ids: block a divides block b."""
return not (Counter(a) - Counter(b))
def classify(x, y):
"""SHARED or MIXING, with spectators set aside."""
cx, cy = Counter(x), Counter(y)
common = cx & cy
xs = sorted((cx - common).elements())
ys = sorted((cy - common).elements())
shared = any(within(a, b) or within(b, a) for a in xs for b in ys)
return {
"verdict": "SHARED" if shared else "MIXING",
"spectators": sum(common.values()),
"shape": (tuple(sorted(value(b) for b in xs)),
tuple(sorted(value(b) for b in ys))),
"reducible": all(len(b) > 1 for b in xs + ys),
"trinomial": any(value(b) == 3 and len(support(b)) == 3
for b in xs + ys),
"x": xs, "y": ys}
def support(block):
p = prod_nn(block)[0]
return p.d
# ------------------------------------------------ the family's template
def sub(a, b):
return tuple(i - j for i, j in zip(a, b))
def add(a, b):
return tuple(i + j for i, j in zip(a, b))
def scale(k, a):
return tuple(k * i for i in a)
def line_of(points):
"""For collinear points: (primitive direction, least point,
positions as multiples of the direction), else None."""
pts = sorted(points)
diffs = [sub(p, pts[0]) for p in pts[1:]]
if rank([pts[0]] + list(pts[1:])) != 1:
return None
base = next(d for d in diffs if any(d))
g = 0
for c in base:
g = gcd(g, abs(c))
v = tuple(c // g for c in base)
pos = []
for d in diffs:
k = next(dc // vc for dc, vc in zip(d, v) if vc)
assert tuple(k * vc for vc in v) == d
pos.append(k)
if min(pos) < 0:
v = scale(-1, v)
pos = [-k for k in pos]
return v, pts[0], [0] + pos
def pairs_split(points, steps):
"""Split the points into runs {p, p + t1, ...} along the given step
lists, in order; return the runs' starting points or None."""
pts = set(points)
if not steps:
return [] if not pts else None
first = steps[0]
size = len(first)
for start in sorted(pts):
run = {add(start, t) for t in first}
if len(run) == size and run <= pts:
rest = pairs_split(pts - run, steps[1:])
if rest is not None:
return [start] + rest
return None
def family_e(x, y):
"""e when {x, y} is the family up to monomials, else None."""
for side, other in ((x, y), (y, x)):
vals = sorted(value(b) for b in side)
if vals != [3, 4] or sorted(value(b) for b in other) != [2, 6]:
continue
blocks = side + other
if any(set(prod_nn(b)[0].coeffs()) != {1} for b in blocks):
return None
t = next(b for b in side if value(b) == 3)
q = next(b for b in side if value(b) == 4)
bi = next(b for b in other if value(b) == 2)
s6 = next(b for b in other if value(b) == 6)
ln = line_of(list(support(t)))
if ln is None:
return None
v, _, pos = ln
if pos[1] * 2 != pos[2] or pos[1] % 2:
return None
e = pos[1] // 2
ve = scale(e, v)
zero = scale(0, v)
qs = pairs_split(list(support(q)),
[[zero, scale(3, ve)], [zero, ve]])
ss = pairs_split(list(support(s6)),
[[zero, scale(2, ve), scale(4, ve)],
[zero, ve, scale(2, ve)]])
bs = pairs_split(list(support(bi)), [[zero, scale(3, ve)]])
if qs is None or ss is None or bs is None:
return None
zq, zs = sub(qs[1], qs[0]), sub(ss[1], ss[0])
if zq != zs or rank([zero, v, zq]) != 2:
return None
return e
return None
# ------------------------------------------------ one-variable multisets
def peel(points, k):
"""The multiset S with points = S + {0, k}, peeled from the least
point, or None."""
work = Counter(points)
out = []
while work:
x = min(work)
for y in (x, x + k):
if work[y] <= 0:
return None
work[y] -= 1
if work[y] == 0:
del work[y]
out.append(x)
return out
def divides_binomial(points, s):
"""Whether 1 + v^s divides the polynomial whose exponent multiset
is given (least exponent 0 or more)."""
top = max(points)
c = [0] * (top + 1)
for p in points:
c[p] += 1
q = [0] * (top + 1)
for i in range(top + 1):
q[i] = c[i] - (q[i - s] if i >= s else 0)
return all(q[i] == 0 for i in range(max(0, top - s + 1), top + 1))
def criterion(h, s, k):
"""MIXING iff s/g and k/g are odd, both at least 3, and some class
of h mod g has a nonzero alternating sum."""
g = gcd(s, k)
s1, k1 = s // g, k // g
if s1 % 2 == 0 or k1 % 2 == 0 or s1 == 1 or k1 == 1:
return "SHARED", None
sums = [0] * g
for x in h:
sums[x % g] += (-1) ** ((x - x % g) // g)
return ("MIXING" if any(sums) else "SHARED"), sums
def by_division(h, s, hp, k):
shared = (divides_binomial(hp, s) or divides_binomial(h, k)
or (k % s == 0 and (k // s) % 2 == 1)
or (s % k == 0 and (s // k) % 2 == 1))
return "SHARED" if shared else "MIXING"
# ------------------------------------------------------------ sections
def count_and_read(f):
ids = tuple(sorted(aid(a) for a in zfactors(f)))
facts = factorizations(ids)
reads = [classify(x, y) for x, y in combinations(facts, 2)]
return facts, reads
def section_control():
section("CONTROL -- the six-term identity and the ten-term pair")
facts, reads = count_and_read(uni(range(6)))
control("the six-term identity has 2 atomic factorizations, SHARED",
len(facts) == 2 and [r["verdict"] for r in reads] == ["SHARED"])
ten = [0, 2, 3, 4, 5, 6, 7, 8, 9, 11]
facts, reads = count_and_read(uni(ten))
print(f" ten-term pair: {len(facts)} factorizations, "
f"{[r['verdict'] for r in reads]}, shapes "
f"{[r['shape'] for r in reads]}")
a, b = (2, 16), (2, 8, 32, 128, 512)
c, d = (2, 64), (2, 8, 16, 32, 128)
same = (Counter(m * n for m in a for n in b)
== Counter(m * n for m in c for n in d))
ids = tuple(sorted(aid(f) for f in menu_factors(a) + menu_factors(b)))
mf = factorizations(ids)
mr = [classify(x, y)["verdict"] for x, y in combinations(mf, 2)]
verdict, sums = criterion([0, 2, 4, 6, 8], 3, 5)
print(f" in menu realizations: products agree {same}, {len(mf)} "
f"factorizations, {mr}; criterion {verdict}, H(-1) = {sums}")
control("the ten-term pair has 2 factorizations and reads MIXING, as "
"numbers and as menus, and the criterion reads MIXING",
len(facts) == 2 and [r["verdict"] for r in reads] == ["MIXING"]
and same and len(mf) == 2 and mr == ["MIXING"]
and verdict == "MIXING")
def section_cycle(top=30):
section(f"CYCLE -- T + {{0, alpha}} peeled by {{0, s}}, "
f"T and alpha to {top}")
tried = found = direct = 0
bad = []
for a in range(0, top + 1):
for b in range(a, top + 1):
t = [0, a, b]
for alpha in range(1, top + 1):
pts = t + [x + alpha for x in t]
for s in sorted({x for x in pts if x > 0}):
if s == alpha:
continue
tried += 1
if peel(pts, s) is None:
continue
found += 1
g, h = min(alpha, s), max(alpha, s)
ok = (len(set(pts)) == 6 and h == 3 * g
and sorted(pts) == [min(pts) + g * i
for i in range(6)])
direct += len(set(pts)) == 6
if not ok:
bad.append((t, alpha, s))
print(f" {tried} peels tried, {found} second tilings, {direct} "
f"direct, {len(bad)} not the six-term identity")
if bad:
print(f" first: {bad[:5]}")
check("every second tiling is direct and the six-term identity",
found > 0 and not bad and direct == found)
def family_blocks(e):
a = dp([((0,), 1), ((2 * e,), 1), ((4 * e,), 1)])
b = dp([((0,), 1), ((3 * e,), 1), ((0, 1), 1), ((e, 1), 1)])
c = dp([((0,), 1), ((3 * e,), 1)])
d = dp([((0,), 1), ((2 * e,), 1), ((4 * e,), 1),
((0, 1), 1), ((e, 1), 1), ((2 * e, 1), 1)])
return a, b, c, d
FAMILY_MENUS = [((2, 8, 32), (2, 16, 6, 12), 1),
((2, 18, 162), (2, 54, 10, 30), 1),
((2, 32, 512), (2, 128, 3, 12), 2),
((3, 12, 48), (5, 40, 7, 14), 1)]
def section_family():
section("FAMILY -- e = 1..4 with z a second variable, and in menus")
ok = True
for e in range(1, 5):
a, b, c, d = family_blocks(e)
f = a * b
facts, reads = count_and_read(f)
es = [family_e(r["x"], r["y"]) for r in reads]
row = (f == c * d and len(f.d) == 12 and set(f.coeffs()) == {1}
and len(facts) == 2
and [r["verdict"] for r in reads] == ["MIXING"]
and reads[0]["spectators"] == 0 and es == [e])
ok &= row
print(f" e = {e}: {len(f.d)} terms, {len(facts)} factorizations,"
f" {[r['verdict'] for r in reads]}, template e {es}")
for m1, m2, e in FAMILY_MENUS:
ids = tuple(sorted(aid(x) for x in menu_factors(m1)
+ menu_factors(m2)))
facts = factorizations(ids)
reads = [classify(x, y) for x, y in combinations(facts, 2)]
es = [family_e(r["x"], r["y"]) for r in reads]
terms = Counter(a * b for a in m1 for b in m2)
row = (len(terms) == 12 and set(terms.values()) == {1}
and len(facts) == 2
and [r["verdict"] for r in reads] == ["MIXING"]
and reads[0]["spectators"] == 0 and es == [e])
ok &= row
print(f" {set(m1)} x {set(m2)}: {len(facts)} factorizations, "
f"{[r['verdict'] for r in reads]}, template e {es}")
check("every member has 12 terms, 2 factorizations, MIXING, no "
"spectator, and the template's e", ok)
def binomial_census(n_h, top):
rows = {}
for rest in combinations_with_replacement(range(0, top + 1), n_h - 1):
h = (0,) + rest
for s in range(1, top + 1):
pts = list(h) + [x + s for x in h]
for k in sorted({x for x in pts if x > 0}):
if k == s:
continue
hp = peel(pts, k)
if hp is None:
continue
key = (tuple(sorted(pts)), min(s, k), max(s, k))
if key in rows:
continue
crit, _ = criterion(h, s, k)
div = by_division(list(h), s, hp, k)
rows[key] = (crit, div, len(set(pts)) == len(pts))
return rows
def section_binomial():
section("BINOMIAL -- (1 + v^s) H = (1 + v^k) H', H a multiset")
ok_all = True
for n_h, top, value_ in ((6, 12, 12), (5, 14, 10), (7, 10, 14)):
t0 = time.time()
rows = binomial_census(n_h, top)
agree = sum(c == d for c, d, _ in rows.values())
mixing = sum(c == "MIXING" for c, _, _ in rows.values())
nondirect = sum(not dr for _, _, dr in rows.values())
mix_nd = sum(c == "MIXING" and not dr
for c, _, dr in rows.values())
print(f" value {value_}: {len(rows)} tiling pairs ({nondirect} "
f"with a doubled point), criterion = division at {agree}, "
f"MIXING {mixing} ({mix_nd} with a doubled point)"
f" [{time.time() - t0:.1f} s]")
ok = agree == len(rows) and len(rows) > 0
if value_ == 12:
ok &= mixing == 0 and nondirect > 0
else:
ok &= mixing > 0
ok_all &= ok
check("the criterion agrees with division everywhere; value twelve "
"never mixes, doubled points included; ten and fourteen do",
ok_all)
def section_line():
section("LINE -- the family with z = v^j, and the split supports")
a = uni([0, 2, 4])
b = uni([0, 3, 8, 9])
f = a * b
facts, reads = count_and_read(f)
line_ok = (set(f.coeffs()) == {1} and len(f.d) == 12
and len(facts) == 2
and [r["verdict"] for r in reads] == ["MIXING"]
and sorted(reads[0]["shape"]) == [(2, 6), (3, 4)])
print(f" e = 1, j = 8: {len(facts)} factorizations, "
f"{[(r['verdict'], r['shape']) for r in reads]}")
split_ok = True
base = [0, 1, 3, 4, 5, 6, 7, 8, 9, 10, 11, 14]
for pts in (base, [14 - x for x in base]):
facts, reads = count_and_read(uni(pts))
shapes = [r["shape"] for r in reads]
print(f" support {sorted(pts)}: {len(facts)} factorizations, "
f"{[r['verdict'] for r in reads]}, shapes {shapes}")
split_ok &= (len(facts) == 2
and [r["verdict"] for r in reads] == ["MIXING"]
and sorted(shapes[0]) == [(2, 2, 3), (3, 4)])
check("the line member and both split supports read MIXING",
line_ok and split_ok)
def section_box():
section("BOX -- three-menus of {2..32} against four-menus of "
"{2..24}")
t0 = time.time()
menus = {3: list(combinations(range(2, 33), 3)),
4: list(combinations(range(2, 25), 4))}
ids, seeds = {}, {3: [], 4: []}
for size, ms in menus.items():
for m in ms:
fs = menu_factors(m)
ids[m] = [aid(f) for f in fs]
if any(negative(f) for f in fs):
seeds[size].append(m)
print(f" {len(menus[3])} and {len(menus[4])} menus, "
f"{len(seeds[3])} and {len(seeds[4])} seeds"
f" [{time.time() - t0:.1f} s]")
pairs = {(a, b) for a in seeds[3] for b in menus[4]}
pairs |= {(a, b) for a in menus[3] for b in seeds[4]}
found = []
for a, b in sorted(pairs):
facts = factorizations(tuple(sorted(ids[a] + ids[b])))
if len(facts) >= 2:
found.append((a, b, facts))
PN.clear()
AT.clear()
print(f" {len(pairs)} pairs walked, {len(found)} collisions"
f" [{time.time() - t0:.1f} s]")
tally = Counter()
frame_ok = out_ok = lemma_ok = True
out_mixing = []
for a, b, facts in found:
frame = len({m * n for m in a for n in b}) == 12
f = prod([prod_nn(blk)[0] for blk in facts[0]])
dim = rank(list(f.d))
for x, y in combinations(facts, 2):
r = classify(x, y)
e = None
if r["verdict"] == "MIXING":
e = family_e(r["x"], r["y"])
key = ("in" if frame else "out", r["verdict"],
r["spectators"] > 0, dim, e)
tally[key] += 1
if r["verdict"] == "MIXING":
lemma_ok &= (r["spectators"] == 0 and r["reducible"]
and r["trinomial"])
if frame:
frame_ok &= e == 1
else:
out_ok &= dim == 1
out_mixing.append((a, b, r["shape"], dim))
elif frame:
frame_ok &= r["spectators"] > 0
n_in = sum(1 for a, b, _ in found
if len({m * n for m in a for n in b}) == 12)
print(" frame, verdict, spectator, dimension, family e: pairs")
for key, n in sorted(tally.items(), key=str):
print(f" {key}: {n}")
for a, b, shape, dim in out_mixing[:12]:
print(f" out of frame MIXING {set(a)} x {set(b)} shape {shape}"
f" dimension {dim}")
if len(out_mixing) > 12:
print(f" ... {len(out_mixing) - 12} more")
print(f" {n_in} collisions in frame, {len(found) - n_in} out"
f" [{time.time() - t0:.1f} s]")
check("85253 pairs, 336 factoring two ways, 71 in frame (the earlier "
"count)",
len(pairs) == 85253 and len(found) == 336 and n_in == 71)
check("in frame: shared with a spectator, or MIXING and the family "
"at e = 1", frame_ok)
print(f" out of frame: {len(out_mixing)} MIXING pairs, every one on "
f"one line: {out_ok}")
check("every MIXING pair: no spectator, every block reducible, a "
"trinomial block", lemma_ok)
def main():
t0 = time.time()
section_control()
section_cycle()
section_family()
section_binomial()
section_line()
section_box()
print()
n, ok = len(CHECKS), sum(CHECKS)
print(f"{ok} of {n} checks pass [{time.time() - t0:.1f} s]")
return 0 if ok == n else 1
if __name__ == "__main__":
sys.exit(main())