dualrs.py
Checks: DUAL: The chain at depth theorem; property; rule.
Cited on: DUAL.
To run it: save dualrs.py, with dualdeg.py, dualmult.py, dualn.py beside it; needs numpy.
"""dualrs.py -- the chain law's depth side through a class the chain's
step keeps: does a hidden window always hold a k with q g_k = 0?
QUESTION. dualn.py's setting: f monic of degree n, f(0) = +/-q, O =
Z[x]/(f), G = O/I, g_k = beta^k mod I, D = {0, ..., q - 1}, T_W the
sums over k in W of D g_k. The class RS: a finite abelian G with a
sequence g_0, g_1, ... generating it and satisfying
sum_m a_m g_(k+m) = 0 for every k >= 0 (a_m f's coefficients) and
g_k = 0 for k >= some t. O/I read at depth t is in RS, and so is
G/<g_k> with the images. GC: in RS, if T_W is uniform on G != 0, then
q g_k = 0 for some k in W.
HAND (frozen before the runs).
H1 If q g_k = 0, D g_k is q/r copies of <g_k>, r its order, so T_W is
uniform on G iff T_(W - k) is on G/<g_k>, and a chain step in the
quotient is one in G; GC therefore gives the depth side by
induction on |G| + |W|. Uniformity is monotone in W, so GC iff
W* = {k : q g_k != 0} never hides G != 0.
R1 q = l^e. U = O/beta^t O is an l-group, so U = O0/beta^t O0 with
O0 = Z_l[x]/(f0), f0 the factor of f over Z_l with f0 = x^r mod l
(Hensel; beta is a unit on the other factor). So a G in RS(f)
carries a sequence obeying f0's recurrence, f0 = x^r + a_(r-1)
x^(r-1) + ... + a_0, l | a_i, v_l(a_0) = e, read mod exp(G); and
every such f0 mod exp(G) is the factor, mod exp(G), of an integer
f with f(0) = +/-q, f = f0 (x + c) with c a unit and the constant
term set to +/-q. One sweep over f0 of degree r covers every
integer base whose local factor has degree r, and only those. In
an l-group each f0-sequence reaches 0 (g_(k+r) lies in
l <g_k, ..., g_(k+r-1)>), and G has rank <= r.
R2 A cyclic G never hides: a faithful chi has q chi(g_k) != 0 at
every k in W*. Skipped, with every G of exponent <= q (W* empty).
R3 g_k -> v^k g_k, v a unit of Z_l, keeps every order, so W* and
hiding, and maps f0 to a_i v^(r-i). At l = 2, r = 3 cubing is onto
the units: a_0 = q. At l = 3, r = 3: a_0 = 9u, u in {1, 4, 7}.
R4 chi in B_k iff chi in (q g_k)^perp - g_k^perp; W* hides iff the
B_k, q g_k != 0, cover every chi != 0. One bitmask per element.
R7 On (Z/l^m)^d, GL_d(Z/l^m) is transitive on the elements of each
order and commutes with the recurrence, so g_0 runs over 0 and
(l^j, 0, ..., 0) only.
PREDICTIONS (frozen). Every initial r-tuple, run until it reaches 0.
K integer cubics f = x^3 + a2 x^2 + a1 x + c0, c0 = +/-q, a1, a2 in
-2..2, G every product of cyclic l-groups of order <= 16 (q = 2,
4) or 27 (q = 3), and q = 4 at order 32 with a1, a2 even, every
triple of G^3 run to 64 terms, kept iff it reaches 0: 0 hiding.
A q = 4, r = 3, G of order 64, rank <= 3, exp >= 8, every a_1, a_2
even mod exp(G), a_0 = 4;
B q = 8, r = 3, G of order 64, exp >= 16, a_1, a_2 even, a_0 = 8;
C q = 9, r = 3, G of order 81, exp >= 27, a_1, a_2 in 3Z mod exp,
a_0 = 9u, u in {1, 4, 7};
D q = 4, r = 4, G of order <= 32, exp >= 8, a_1..a_3 even mod exp,
a_0 = 4u, u odd;
E the groups every invariant factor of which exceeds q, past order
64: q = 4 at (16, 8), (16, 16), (8, 8, 8), (32, 32); q = 8 at
(16, 16); q = 9 at (27, 27), a_0 = 9.
Predicted 0 hiding everywhere. KILL: any hiding sequence, printed
with G, f0 and its r-tuple; GC then dies.
L2 (frozen with T2 below, before its code) every noncyclic rank-2
l-group of order <= 256 at q = 2, 4, 8 and <= 243 at q = 3, 9,
f0 = x^2 + a_1 x + q u (u over the units mod squares, a_1 in lZ
mod exp G), and (added after the first run, whose q = 9 arm held
no group with both factors above q) (32, 32) at q = 4, 8 and
(27, 27) at q = 9; every (g_0, g_1) run to 0: at most 2 distinct lines
<q g_k> with ord q g_k = l. KILL: a sequence with 3. Its own
print: the sequences at 2, which must be > 0 for the bound to be
tested.
S2 r = 2 with no nilpotence: q = 2, 4 at order 16, 32, 64, q = 3 at
27, 81, every group, every a_0 = q u and every a_1 mod exp G, W*
cut to [0, 8) and [0, 12): 0 hiding (T2 reads any window).
L3 (frozen with R12, before its code) every initial triple under R7's
cut, run to 0, f0 = x^3 + a2 x^2 + a1 x + a0, a1, a2 in lZ mod
exp G: (4, 4, 4) q 2, a0 = 2; (8, 8, 8) q 2, a0 = 2; (8, 8, 8) q 4,
a0 = 4 (R3); (9, 9, 9) q 3, a0 in {3, 6}. KILL: a sequence hitting
more than B(l, 3) lines, 4 at l = 2 (of 7), 5 at l = 3 (of 13).
Its own print: each arm's histogram.
L4 (frozen with R13, after L3's run, before its code) at rank 2
inside cubic f0, case B, every triple under R7's cut: q 2 at
(4, 4), (8, 8); q 4 at (8, 8), (16, 16) and at (8, 8) with
x^3 + 4 alone; q 3 at (9, 9), a0 in {3, 6}, and (27, 27), a0 = 3,
a1, a2 in {0, 3, 6}. R13 read by brute span at every sequence
hitting all l + 1 lines, 2000 drawn per arm when more. KILL: one
with g_i off V_(i+1). TRANSPLANT from l = 2, predicted: some q 3
sequence hits all 4 lines.
BN (frozen with T4, before its engine) f0 = x^3 + a0, a0 = q u at
every unit u mod exp G, every rank-2 l-group of exponent above q:
every initial triple at order <= 32 at q = 2, 4 and <= 27 at q = 3,
and (--full) 3000 drawn per (G, a0) at the others of order <= 256
at q = 2, 4, 8 and <= 243 at q = 3, 9: T4's K is closed. KILL: one
sequence where it is not.
G (frozen with R16-T5 by hand, before the gate engine) e = 1, rank 2,
a1, a2 in lZ mod exp G, generating sequences only: q 2 at (4, 4),
(8, 4), (8, 8), every triple under R7's cut, a0 = 2, and (16, 8),
(16, 16), 2000 drawn; q 3 at (9, 9) every triple under R7's cut,
a0 = 3, (27, 27) 2000 drawn at each a0 in {3, 6, 12} (R3) and
(27, 9) 2000 drawn, a0 = 3; q 5 at (25, 25), 2000 drawn, a0 = 5.
G1 R's gates come from at most one non-D class, at most one per
depth. KILL: both
non-D classes in R, or two X gates at one depth.
G2 at most one non-degenerate D gate per depth in R, at its
level's X depth when both lie in R. KILL: two at one depth, or
one off its level's X depth (this clause, and C12's reach to
every <h> of order l^N2, added after the freeze, before the run).
G3 g_d <= l at every depth leaves a closed <h> in R. KILL: one
sequence without. T5 proves it, so its print checks the engine.
G4 (census) a closed <h> in R at every sequence read; the depths
with g_d > l counted, with their degenerate D gates, and (added
after the first run) the sequences where some |A_d|, d >= 1,
falls to 1; (added with this section's engine, before its run)
the sequences at each D, R16's three cases.
CONTROLS (read first).
C1 "reaches 0" dropped, W* cut to [0, 8), q = 2, order 16, integer
cubics: hiding sequences exist.
C2 O/I at every ideal read at some depth, cubic bases of dualn.py at
q^J <= 128, W* over [0, t): no hiding.
C3 R7's cut at (4, 4), C1's only hiding group: one g_0 per order,
and each hides iff its order class does.
CB the nil arm, which no hiding reaches: the engine's witness count
(characters no B_k covers) against a brute-force count over every
character and every k in W*, at sampled eventually-zero sequences
of (8, 8), (16, 8) at q = 4 and (27, 9) at q = 9, and at r = 2 of
(8, 8) at q = 4 and (9, 9) at q = 3; equal at every one.
C4 L2's code at r = 3: (8, 8), q = 4, x^3 + 4, every triple: some
sequence puts q g_k on all 3 lines (the example closing DERIVED).
Below 3, L2 is void.
C5 the line counter itself: q = 1, f = x^7 on (Z/2)^3, seven free
terms: some sequence hits all 7 lines (a counter reading only the
first l + 1 line bits stops at 3).
C6 R12 with l | f0(0) dropped: q = 1, f0 = x^3 + x + 1 on (2, 2, 2),
beta a unit of period 7, 7 terms: some sequence hits all 7 lines,
above B(2, 3) = 4.
C7 (added with L4's code, after its freeze) R13's reader on (8, 8),
q 4, x^3 + 4, g = (1, 0), (0, 1), 0, where V_1 misses (1, 0): no.
C11 T4's K at x^3 + 2x + 2 (a1 = 2) on (8, 8), q 2, every triple:
open at some sequence, so BN's reader can print a fail and K
leans on a1 = 0 (dualpw.py reads a closed <h> at every generating
sequence there).
C12 G's bitmask closure reader agrees with a brute character reader
(the character with kernel <h> a witness, read off character
values, R15) at every <h>, h not in lG, of order l^N2, on C4's
sequence and one generating sequence of each default q 2 arm.
C13 G's no: a bare list in (8, 8), q 2, with no closed <h> among all
twelve, found by search, printed with its largest g_d (above l, by
T5's count with l + 1 children at the root).
C14 G1's reader fires with R widened to every <h> of both sides of e,
x^3 + 2 on (8, 8).
C15, C16 each a planted break in G2's own reader: C15 counts the
degenerate D gates with the rest, C16 reads the level clause one
level off. Each fires.
FINDINGS (entered after the run, from its printed output).
C1 6144 hiding sequences without nilpotence. C2 0 of 1948 ideals
read at some depth hidden by their W*. C3 12 hiding (pair, order)
cells, 0 off, every order held. CB 1080 sequences, 0 off, 31
distinct witness counts, the least 12. C4 24576 triples of (8, 8)
hit all 3 lines. C5 most 7 lines. C6 {0: 1, 1: 49, 3: 294, 7: 168}:
168 sequences hit all 7. C7 says no.
L2 most 2 lines, 3095568 sequences at 2 under R7's cut: q 2, 861
(G, f0) pairs, 2047632 at 2; q 4, 849, 640640; q 8, 689, 13312;
q 3, 103, 385236; q 9, 115, 8748. S2 26392 runs, 0 hiding.
L3 most 4 at l = 2, 3 at l = 3; the kill misses. Sequences by lines
hit: (4, 4, 4) q 2, 4 f0, {0: 512, 1: 11776, 2: 29184, 3: 7680};
(8, 8, 8) q 2, 16 f0, {0: 2048, 1: 1624064, 2: 8699904,
3: 6057984, 4: 393216}; (8, 8, 8) q 4, 16 f0, {0: 196608,
1: 4390912, 2: 10223616, 3: 1966080}; (9, 9, 9) q 3, 18 f0,
{0: 26244, 1: 2847474, 2: 18895680, 3: 6928416}. B(2, 3) = 4 is
reached at (8, 8, 8) q 2; B(3, 3) = 5 is not reached.
L4 R13 0 off, read at 8640 sequences hitting all l + 1 lines (every
one at (8, 8) q 4 x^3 + 4, 512, and (4, 4) q 2, 128; 2000 drawn of
39936 at (8, 8) q 2, of 8192 at (8, 8) q 4, of 458752 at (16, 16)
q 4, of 314928 at (27, 27) q 3). (9, 9) q 3, 18 f0: most 3 lines,
{0: 2916, 1: 106434, 2: 209952, 3: 34992}; (27, 27) q 3, 9 f0:
{0: 1458, 1: 3209058, 2: 9430344, 3: 6176088, 4: 314928}, so the
TRANSPLANT held: q 3 reaches all 4 lines, at (27, 27) only. (9, 9)
cannot (by hand): a generating sequence reads its factors l^(e+1),
so M_C = C (a non-generating one spans a group whose qH is cyclic,
one line), and beta^k lies in lO0 for k >= 3 (f0 = x^3 mod l), so
hits fall at k = 0, 1, 2 only, at most 3 lines. The same count caps
L3's (4, 4, 4) q 2, (8, 8, 8) q 4 and (9, 9, 9) q 3 at 3, which is
why B(3, 3) = 5 is not reached; B(2, 3) = 4 is, above l^(e+1).
BN C11: open at 84096 sequences. 0 open: default 351174 sequences
over 16 (G, a0) pairs; --full 1014174 over 237.
G C12 passes (15 closed <h> in all), C13 prints a bare list of eight
with no closed <h>, largest g_d 5; C14 fires at 7680 of 7680, C15
at 6511, C16 at 20662: each reader can say no. G1, G2, G3 0 fails
over 604952 generating sequences: 1536 (4, 4), 344064 (8, 4),
122880 (8, 8) q 2, 122472 (9, 9) q 3, and 2000 drawn at each of
the seven drawn arms. D = 0, 1, 2 at 410548, 131362, 63042, each
class at every arm. G4: a closed <h> in R at every one. g_d > l at
3174, all at q 2 (3072 (8, 8), 13 (16, 8), 89 (16, 16)), each
over-full depth holding a degenerate D gate (by G1 and G2's zero
fails; the print sums 3072, 13, 90 such terms there); some |A_d| falls to 1
at 3072, 13 and 38 of them, never to 0. A degenerate D gate lies in
R at q 3 only in the (27, 27) draws (96, 93, 111), never over-full,
and at none of q 5's.
K 0 hiding: kept 419112 (q 2, order <= 16), 144012 (q 3, <= 27),
419112 (q 4, <= 16), 4128768 (q 4, order 32, a1, a2 even); each
count holds every initial triple reaching 0, the zero sequence,
the non-generating ones (which cannot hide) and automorphic
copies among them.
A 0 hiding: 416 (G, f0) pairs, 105119744 sequences under R7's cut.
B 0 hiding: 384 pairs, 100663296 sequences.
C 0 hiding: 81 pairs, 43046721 sequences (at exp 27, a_0 = 9u reads
u mod 3 only, so the three u are one).
D (--full) 0 hiding: 1216 pairs, 1212153856 sequences.
E (--full) 0 hiding: q = 4, 400 pairs, 1782579200 sequences under
R7's cut; q = 8, 64 pairs, 20971520; q = 9, 81 pairs, 172186884.
The kill misses at every family: GC holds at this scale, a pattern
at r >= 3; at r <= 2 it is T2 below, at x^3 + a0 T4.
DERIVED (by hand: GC at r <= 2, T2; not at full rank, T3; at x^3 + a0,
T4; toward r >= 3).
D1 RS is the quotients of U = O/beta^t O by its subgroups H, g_k the
class of beta^k: U is generated by 1, ..., beta^(t-1) under f's
relations and beta^t = 0. T_t is a complete residue system of U
(O/beta O = Z/q), so with Z = [0, t) - W*, T_(W*) + T_Z = U once
each, and W* hides U/H iff T_(W*) + H covers U m = |H|/q^|Z| times.
D2 V_k = <g_k, g_(k+1), ...> has V_k/V_(k+1) cyclic on g_k of order
n_k | q, as in the ring. A character built down from V_(t-1) meets
a constraint only at k in W* with n_k < q: there q chi(g_k) =
(q/n_k) chi(n_k g_k) is fixed before chi(g_k) is chosen.
D3 The filtration alone does not carry GC: a no-depth miss's g_0,
..., g_5 with elements z, q z = 0, appended to span the q g_k
satisfies q y_i in <y_(i+1), ...> for every i, and its window
still hides. A proof must use f's recurrence past u = max W*.
D4 In a least counterexample every nonzero subgroup K has a chain
over W* started at K that reaches G (the quotient G/K is smaller),
so every subgroup of order l is <q g_k> for some k in W*.
R5 S <= G is CLOSED when k in W*, q g_k in S imply g_k in S. A
nonzero proper closed S reduces GC at G to GC at G/S (in RS): a
witness chi of G/S for W*(G/S) lifts, since at k in W* with
q g_k in S, g_k is in S and chi(g_k) = 0. So a least
counterexample has none (D4 is |S| = l).
R6 (case A) If an invariant factor of G has order <= q, (qG)[l] is
not G[l], and a line of G[l] outside qG is closed (no q g_k lies
in it). So a least counterexample is CASE B: every invariant
factor exceeds q, every line of G[l] is <q g_k> with o_k = e + 1
(ord g_k = l^(o_k)).
R8 The closure of qG (the least closed subgroup over it) is qG +
<g_k : k in W*>: every k in W* enters at once. So in a least
counterexample the g_k, k in W*, generate G.
R9 T_t = T_(W*) + T_Z is a complete residue system of U (D1), so in
G, mu_(W*) * mu_Z = |H| u_G (mu_S the image of T_S counted with
multiplicity, u_G uniform). For k in Z, D g_k covers <g_k>
q/ord(g_k) times, and a sum of uniform measures on subgroups is
uniform on their sum: mu_Z is a multiple of u_(G_Z), G_Z =
<g_k : q g_k = 0>. So W* hides G iff mu_(W*) is invariant under
translation by G_Z, and a witness is nonzero on G_Z.
R10 (the dual) U^ is the f0-sequences c in Q_l/Z_l with c_k = 0 for
k >= t, G^ a subgroup of it, c_k = chi(g_k). q c_k is fixed by
c_(k+1), ..., c_(k+r) (a_0 = q times a unit), so the last nonzero
term of every c is killed by q, and a witness's last nonzero term
sits off W*.
R12 For a full lattice M in O0 (x) Q_l, the beta^k (k >= 0) in
M - lM put their images on at most B(l, r) = 1 + (l^(r-1) - 1)/
(l - 1) lines of M/lM. With i the least such k, every later one
lies in N = beta^(i+1) O0 cap M, whose image in M/lM is proper:
else N + lM = M, so N = M (Nakayama), beta^i lies in
beta^(i+1) O0 and, f0(0) != 0 (R1) letting beta^i cancel, beta
is a unit of O0, but l | f0(0). So the
later lines lie in a hyperplane. No window and no nilpotence is
read. L2 prints the bound at r = 2, L3 at r = 3, where C6 shows
the hypothesis l | f0(0) bites.
T2 (GC at r <= 2) q = l^e, f0 monic of degree <= 2 over Z_l,
l | f0(0), G a finite l-group, g_k obeying f0's recurrence, W
finite: W* never hides G != 0; no nilpotence is used (S2 sweeps
it). If the g_k span a proper subgroup, a chi != 0 vanishing on
it is a witness; else G = O0/L, L the kernel of x^k -> g_k (a
Z_l-lattice, not always an ideal), rank <= 2. R5 and R6 read
only G, the g_k and W*, and a quotient keeps f0 and W, so a
least counterexample is case B of rank 2 (R2), each of the l + 1
>= 3 lines of G[l] some <q g_k>. Both invariant factors above q
put L in l^(e+1) O0; with M = l^-(e+1) L, x -> l^e x maps M/lM
onto G[l] = l^e M / l^(e+1) M, and <q g_k> is a line iff beta^k
lies in M - lM, the line of beta^k mod lM. R12 allows two. No
invertibility of lattices enters, so a double root of f0 costs
nothing. With H1, the depth side holds wherever f's local factor
has degree <= 2.
T3 (no least counterexample at full rank) q = l^e, f0 monic of
degree r over Z_l, l | f0(0): a least counterexample has
2 <= rank G <= r - 1. At rank r it is case B (R6), L lies in
l^(e+1) O0 and T2's map carries M/lM onto G[l], whose
(l^r - 1)/(l - 1) lines are each some <q g_k> (D4); R12 reaches
l^(r-1) - 1 fewer. Rank 1 is R2; at r = 2, T3 is T2.
R13 (rank 2 <= s < r, case B) A Smith basis puts L = P + L_C, P
spanned by r - s basis vectors, L_C inside l^(e+1) C, C spanned by
the rest; pi: O0 -> C along P. Then M cap O0 = P + M_C and
lM cap O0 = P + l M_C (e >= 1), M_C = l^-(e+1) L_C, so q g_k spans
a line iff pi(beta^k) lies in M_C - l M_C, read in M_C/l M_C.
With i the least such k, later hits lie in
N_C = pi(beta^(i+1) O0) cap M_C; if its image is proper they lie
in a hyperplane, too few lines; else N_C = M_C (Nakayama) and
beta^i lies in beta^(i+1) O0 + P: P, inside L, holds
beta^i - beta^(i+1) y, so g_i lies in V_(i+1). A least
counterexample of rank s < r has V_i = V_(i+1). Where
l^(s-1) >= 3 the next hit i' must pass the same test (else at
most 2 + (l^(s-1) - 1)/(l - 1) lines, l^(s-1) - 2 too few), so at
s = r - 1, P a line, beta^(i' - i) = l^m eta, eta a unit of O0;
at e = 1 (f0 Eisenstein) beta^3 is l times a unit, so this alone
kills nothing. L4 reads R13. The rank-2 case is open: at r = 3
beta^m mod l ranges over <beta, beta^2>, and G = Z/8 x Z/8,
f0 = x^3 + 4, g = (1,0), (0,1), (1,1) puts q g_0, q g_1, q g_2 on
all three lines (C4).
R14 (the closure reduction) Every nonzero closed S holds a line of
G[l] and that line's closure (S <- S + <g_k : k in W*, q g_k in S>,
to a fixed point), so by R5 a least counterexample is CLOSURE-FREE:
every line's closure is G, l + 1 of them at rank 2. That puts every
line hit (an unhit line is closed) and the g_k, k in W*, generating
G, so it subsumes D4, R6, R8 and R13. W* read over the whole
sequence is the hardest case: a window's closures are smaller. In
R13's lattices at s = 2, P = Z_l p, c_k = pi(beta^k), G = C/L_C: W*
= {k : c_k not in lM_C}, the hits are the c_k in M_C - lM_C, and a
lattice X, L_C <= X <= C, is closed iff no k in W* has c_k in (l^-e
X cap C) - X. With R2 and T3, GC at every cubic local factor
follows from: no rank-2 case-B sequence is closure-free (dualpw.py
reads PW, which implies it, at q = 2, 4, 8, exponent <= 32). At G =
(Z/l^(e+1))^2 none is: g_k lies in lG for k >= 3 (l | a_i),
so W* lies in {0, 1, 2}; where a line is unhit (always at l >= 3),
any <h>, h not in lG, through it is closed (each q g_k, k in W*,
has order l off that line); at l = 2 with three lines hit <g_0> is
closed, q g_1
and q g_2 lying off its line, and g_0 is not in lG.
R15 (the primitive witness) If G/K is cyclic, the character chi with
kernel K is a witness iff K is closed: at k in W*, chi(g_k) = 0 iff
g_k is in K, and q chi(g_k) = 0 iff q g_k is. At rank 2, <h> is
such a K, K != G, whenever h is not in lG. In R14's lattices h
lifts to a primitive d, Z_l d = ker rho with rho a primitive functional
and n = v(rho(L_C)) >= e + 1; g_k lies in <h> iff v(rho(c_k)) >= n
and q g_k does iff v(rho(c_k)) >= n - e. So PW (some such <h>
closed, read by dualpw.py) says: some scalar f0-sequence rho(c_k)
avoids the valuations n - e, ..., n - 1 on W*.
T4 (the binomial factor) At f0 = x^3 + a0 mod exp G, GC holds. Here
g_(3a+i) = (-a0)^a g_i, so every term lies in <g_0>, <g_1> or
<g_2>, and a chi != 0 that is 0 or injective on each of the three
is a witness: at k in W*, q g_k != 0 lies in some <g_i>, so
q chi(g_k) != 0 unless chi kills <g_i>. At rank 2 take chi with
kernel K = <h>, h not in lG (R15). Every line of G[l] is some
<h>[l] (on Z/l^m1 x Z/l^m2, m1 >= m2: h = (1, 0) gives
(l^(m1-1), 0), and h = (l^(m1-m2) t, 1) gives (l^(m1-1) t,
l^(m2-1))), and K meets <g_i> trivially iff K[l] is not the line
L_i of <g_i>. If some line is no L_i, K goes through it; else l = 2
and L_0, L_1, L_2 are the three lines, and any K holding g_0 (some
does: g_0 = l^a h) kills <g_0> and meets the others trivially.
The step reads only that the terms lie in at most l + 1 cyclic
subgroups: no invariant factor, generation or nilpotence. Rank 1 is
R2, rank 3 T3, and a quotient keeps a1 = a2 = 0, so GC holds
wherever f's l-adic factor is x^3 + a0 (among integer cubics f =
x^3 +/- q); with H1 so does the depth side. BN reads K.
R16 (the edge) Let q = l (e = 1), so f0 is Eisenstein, O0 = Z_l[beta]
a DVR with l O0 = beta^3 O0; G = O0/L of rank 2 with invariant
factors l^N1 >= l^N2 >= l^2; p in L spans L mod l, p = beta^D eps
(D <= 2, eps a unit). C = (O0 (x) Q_l)/Q_l p, pi the projection,
c_k = pi(beta^k), O_C = pi(O0), L_C = pi(L), G = O_C/L_C (p
primitive, so Q_l p cap O0 = Z_l p). Omega_k = pi(beta^k O0) =
<c_k, c_(k+1), c_(k+2)>, Omega_(k+3) = l Omega_k, each step of index
<= l, and pi(l^a p) = 0 gives xi_0 c_(D+3a) + xi_1 c_(D+3a+1) +
xi_2 c_(D+3a+2) = 0, xi = w^a eps (w = l/beta^3), xi_0 a unit: the
step at D+3a is trivial, the other two have index l. So every
Omega_k is l^a Omega or l^a Omega' (Omega = Omega_D, Omega' =
Omega_(D+2)), the two ends of one edge e of the Bruhat-Tits tree
of C, and o = [O_C] is [Omega] at D = 0, 2, [Omega'] at D = 1.
R17 (the sides) c_(D+3a+1) lies in l^a Omega - l^a Omega', c_(D+3a+2)
in l^a Omega' - l^(a+1) Omega: the end [c_k] of the D+1 class lies
on Omega's side of e, of the D+2 class on Omega''s side. A D-class
c_(D+3a) = gamma_1 c_(D+3a+1) + gamma_2 c_(D+3a+2), gamma_i =
-xi_i/xi_0, lies on Omega's side iff l does not divide gamma_1, else
on Omega''s side or, where l divides both (DEGENERATE; then g_k
lies in V_(k+3)), in l^(a+1) Omega, a level up.
R18 (the gates) The subgroups of G are the lattices L_C <= M <= O_C,
the cyclic ones of order l^d the vertices at distance d from
v0 = [L_C], and the <h>, h not in lG, of order l^N2 those at
distance N2 with v0 on the geodesic from o (the CONE; at N1 = N2,
v0 = o and every vertex at distance N2). Such an <h> is closed (R5)
iff its chain l^j <h> never passes a GATE, the vertex <l g_k> at
depth n_k - 1 (k in W*, l^(n_k) = ord g_k), without taking its
direction <g_k>.
R19 (the region) R is the cone, or at N1 = N2 the <h> on o's side
(h not in H', H' the one V_k of index l in G). R lies on one side
of e, and only ends on that side put gates on R's chains, so one
non-D class X gives gates, the other none. An end l^j x0 in the
cone, x0 primitive in O_C, has order l^(N2 - j), and the X term at
level a has j = a + const: one X gate per depth. A non-degenerate
D term sits at its level's X depth. So a depth holds at most 2
gates unless a degenerate D term LANDS there from a deeper level:
it rises m(a) >= 1 levels, w^(-a) eps^(-1) in Z_l + l^m O0.
T5 (survival) R's root has l children in R (the cone: all but the one
toward o; at v0 = o, all but o'), every later vertex l. With A_d the
depth-d vertices some chain of R reaches past no broken gate, a
gate removes at most l - 1 children and two at one vertex all
l <= 2(l - 1), so |A_(d+1)| >= l |A_d| - (l - 1) g_d, g_d the
distinct gates at depth d, none at depth 0. If g_d <= l at every
depth, |A_d| >= l throughout: some <h> in R is closed, a witness
(R15). With R19 that holds at every sequence with no degenerate D
gate in R, and wherever at most l - 1 D gates share a depth.
R20 (the landers; derived after G's run, never run) g_(D+3a) =
l^a pi(beta^D w^(-a)), so a D term rises m(a) = delta(w^(-a)
eps^(-1)) levels, delta(u) = max{m : u in Z_l + l^m O0}, which is
an ultrametric closeness on O0^x/Z_l^x. The degenerate levels are
one class mod P or none, P the order of w in (O0/l)^x/F_l^x (P | l
at l odd, P | 4 at l = 2), all or none at P = 1. Two D terms land on
one level a < a' only if t = a' - a has P | t and m(a) = t + m(a'),
m(a') = delta(w^(-t)) (at l odd mu + v_l(t/P), mu = delta(w^P)). At
l = 3 a depth over-fills (X, its level's D and two landers, or three
landers) only at exponent >= 3^6 (P = 3, mu = 1, t = 3, m(a) = 4);
at l = 2 one lander beside its level's X and D already does, and
there no count of gates alone decides.
Case B stays open at 2 <= rank G <= r - 1, r >= 3, past T4 and, at
e = 1, past T5's hypothesis. The aim,
seen and not printed here: at r = 3, over the cubic local factors
(a_0 = q, a_1, a_2 even), every
generating eventually-zero sequence of (8, 8), (16, 8), (16, 16),
(8, 8, 8) at q = 4 and (16, 16) at q = 8, under R7's cut, had a
witness chi with chi(g_s) != 0, s the sequence's last k with
g_k != 0, and one of order exp G, each found apart. The sequences
with every line of G[l] some <q g_k> have q^|W*| = |G| at (8, 8),
where Hajos's theorem kills a hiding, and q^|W*| > |G| at (16, 8) at
q = 4 and (16, 16) at q = 4, 8, where it does not reach.
RUN RECORD. G alone: 24.1 s, 37.4 MB. Default 26/26, 133.4 s,
86.3 MB; D 288.3 s, 67.6 MB, under a memory guard. E (--full), its
three family() calls run alone: 400, 64, 81 (G, f0) pairs, hiding 0
at each, 1789.5 s, peak 249.4 MB, nearly all of it q = 4.
"""
import os
import random
import sys
import time
from itertools import product
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import numpy as np # noqa: E402
CHECKS = []
CHUNK = 1 << 18
def check(name, ok, detail=""):
CHECKS.append(bool(ok))
print(f" {'PASS' if ok else 'FAIL'} {name}" +
(f" ({detail})" if detail else ""), flush=True)
def groups(l, top, exact=False):
"""Every product of cyclic l-groups of order <= top (== top if
exact), as moduli lists, largest first."""
out = []
def rec(rest, cap, cur):
if cur and (not exact or rest == 0):
out.append(tuple(l ** x for x in cur))
for e in range(min(cap, rest), 0, -1):
rec(rest - e, e, cur + [e])
e = 0
while l ** (e + 1) <= top:
e += 1
rec(e, e, [])
return out
class Group:
"""G = prod Z/m_i, elements as indices 0..N-1 (0 the identity)."""
def __init__(self, ms):
self.ms = ms
self.E = max(ms)
self.els = np.array(list(product(*[range(m) for m in ms])),
dtype=np.int64)
self.N = N = len(self.els)
st = np.cumprod([1] + [m for m in ms[::-1]])[:-1][::-1]
self.st = np.array(st, dtype=np.int64)
self.add = self.index(self.els[:, None, :] +
self.els[None, :, :]).ravel()
R = self.els * np.array([self.E // m for m in ms], dtype=np.int64)
zero = (self.els @ R.T) % self.E == 0 # [x, chi]
self.W = (N + 63) // 64
bits = np.zeros((N, self.W * 64), dtype=bool)
bits[:, :N] = zero
self.perp = np.packbits(bits.reshape(N, self.W, 64)[:, :, ::-1],
axis=2, bitorder="big") \
.view(">u8").astype(np.uint64).reshape(N, self.W)
full = np.ones(self.W * 64, dtype=bool)
full[N:] = False
full[0] = False # chi = 0
self.full = np.packbits(full.reshape(self.W, 64)[:, ::-1],
axis=1, bitorder="big") \
.view(">u8").astype(np.uint64).reshape(self.W)
def index(self, v):
return ((v % np.array(self.ms, dtype=np.int64)) @ self.st)
def mul(self, c):
return self.index(c * self.els)
def homocyclic_firsts(G):
"""R7: on (Z/l^m)^d, g_0 in {0, (l^j, 0, ..., 0)} up to Aut."""
m, d = G.ms[0], len(G.ms)
if any(x != m for x in G.ms):
return None
out, c = [0], 1
while c < m:
out.append(int(G.index(np.array([c] + [0] * (d - 1)))))
c *= [p for p in range(2, m + 1) if m % p == 0][0]
return out
def block(G, q, a, ids, nil=True, window=None, terms=64):
"""Run the sequences whose initial r-tuples are the base-N digits
of ids, g_(k+r) = -(a_0 g_k + ... + a_(r-1) g_(k+r-1)). Returns
(cover, keep): cover the B_k's union as bitmasks over chi, keep
whether the sequence reaches 0 (the last r of `terms` zero; run
until all reach 0 when nil); window: cover only k < window."""
r, N = len(a), G.N
mula = [G.mul(-c) for c in a]
qm = G.mul(q)
seq = [ids // N ** (r - 1 - j) % N for j in range(r)]
cover = np.zeros((len(ids), G.W), dtype=np.uint64)
k = 0
while True:
g = seq[k]
if window is None or k < window:
qg = qm[g]
m = G.perp[qg] & ~G.perp[g]
m[qg == 0] = 0
cover |= m
nxt = mula[0][seq[k]]
for j in range(1, r):
nxt = G.add[nxt * N + mula[j][seq[k + j]]]
seq.append(nxt)
k += 1
if nil and window is None and k >= r and \
not any(np.any(s) for s in seq[k:k + r]):
break
if k + r >= terms:
break
if nil:
keep = np.all(np.stack([seq[j] == 0 for j in
range(len(seq) - r, len(seq))]), axis=0)
else:
keep = np.ones(len(ids), dtype=bool)
return cover, keep
def sweep(G, q, a, nil=True, window=None, terms=64, firsts=None):
"""Every r-tuple of G (g_0 in firsts if given). Returns (kept,
hiding, first hiding tuple)."""
r, N = len(a), G.N
rest = N ** (r - 1)
blocks = [(f * rest, (f + 1) * rest) for f in firsts] if firsts \
else [(0, N ** r)]
kept = hid = 0
first = None
for b0, hi in blocks:
for lo in range(b0, hi, CHUNK):
ids = np.arange(lo, min(hi, lo + CHUNK), dtype=np.int64)
cover, keep = block(G, q, a, ids, nil, window, terms)
hides = np.all(cover == G.full, axis=1) & keep
kept += int(keep.sum())
hid += int(hides.sum())
if first is None and hides.any():
i = int(ids[np.argmax(hides)])
first = tuple(tuple(G.els[i // N ** (r - 1 - j) % N])
for j in range(r))
return kept, hid, first
def local_coeffs(l, E, n):
"""Every (a_1..a_n) with l | a_i, read mod E."""
return list(product(range(0, E, l), repeat=n))
def integer_cubics(q, even=False):
rng = (-2, 0, 2) if even else range(-2, 3)
for c0 in (q, -q):
for a1 in rng:
for a2 in rng:
yield (c0, a1, a2)
def popcount(x):
"""Bits set per row of a uint64 array."""
v = x.view(np.uint8)
return np.unpackbits(v, axis=-1).reshape(x.shape[0], -1).sum(axis=1)
def brute_witnesses(ms, q, a, tup):
"""Characters chi != 0 with chi(g_k) = 0 or q chi(g_k) != 0 at every
k with q g_k != 0, by direct arithmetic; the sequence run to 0."""
E, r = max(ms), len(a)
s = [list(x) for x in tup]
while any(any(x) for x in s[-r:]):
s.append([(-sum(a[j] * s[-r + j][i] for j in range(r))) % m
for i, m in enumerate(ms)])
W = [x for x in s if any((q * xi) % m for xi, m in zip(x, ms))]
n = 0
for c in product(*[range(m) for m in ms]):
if not any(c):
continue
vals = [sum(ci * xi * (E // m) for ci, xi, m in zip(c, x, ms)) % E
for x in W]
n += all(v == 0 or (q * v) % E for v in vals)
return n
def control():
print("C controls", flush=True)
t0 = time.time()
hid = 0
for ms in groups(2, 16, exact=True):
G = Group(ms)
for a in integer_cubics(2):
hid += sweep(G, 2, a, nil=False, window=8, terms=11)[1]
check("C1 no nilpotence, W* cut to [0, 8), q 2 order 16: hiding "
"exists", hid > 0, f"{hid}, {time.time() - t0:.1f} s")
G = Group((4, 4))
order = [int(np.lcm.reduce([m // np.gcd(int(x), m) for x, m in
zip(e, G.ms)])) for e in G.els]
cells = off = 0
for a in integer_cubics(2):
for f in homocyclic_firsts(G):
orbit = [x for x in range(G.N) if order[x] == order[f]]
whole = sweep(G, 2, a, nil=False, window=8, terms=11,
firsts=orbit)[1]
rep = sweep(G, 2, a, nil=False, window=8, terms=11,
firsts=[f])[1]
cells += whole > 0
off += (whole > 0) != (rep > 0)
span = {order[f] for f in homocyclic_firsts(G)} == set(order)
check("C3 R7: one representative per order of g_0, and it hides iff "
"its orbit does, (4, 4)", span and cells > 0 and off == 0,
f"{cells} hiding (pair, order) cells, {off} off, every order "
f"{span}")
rnd = random.Random(7)
pairs = [((8, 8), 4, (4, 0, 0)), ((8, 8), 4, (4, 2, 6)),
((16, 8), 4, (4, 6, 8)), ((16, 8), 4, (12, 2, 4)),
((27, 9), 9, (9, 3, 6)), ((8, 8), 4, (4, 2)),
((8, 8), 4, (12, 6)), ((9, 9), 3, (3, 3)), ((9, 9), 3, (6, 0))]
seen = bad = 0
counts = set()
for ms, q, a in pairs:
G = Group(ms)
r = len(a)
ids = np.array(rnd.sample(range(G.N ** r), 3000), dtype=np.int64)
cover, keep = block(G, q, a, ids, terms=10 ** 6)
eng = popcount(G.full & ~cover)
for i in np.where(keep)[0][:120]:
tup = [tuple(int(x) for x in G.els[int(ids[i]) //
G.N ** (r - 1 - j) % G.N])
for j in range(r)]
b = brute_witnesses(ms, q, a, tup)
seen += 1
bad += b != int(eng[i])
counts.add(b)
check("CB the nil arm's witness count matches brute force",
seen > 0 and bad == 0 and len(counts) > 3,
f"{seen} sequences, {bad} off, {len(counts)} distinct counts, "
f"least {min(counts)}, {time.time() - t0:.1f} s")
return time.time() - t0
def section_c2():
from dualdeg import powers
from dualn import Base, cubic_bases
from dualmult import depth
t0 = time.time()
n_id = hid = 0
for a in cubic_bases():
B = Base(a, 128)
q = B.q
for L in B.Is:
t = depth(L, a, B.pw[1])
if t is None or L.N == 1:
continue
n_id += 1
pw = powers(a, t + 1)
gk = [pw[k] for k in range(t)]
Ws = [k for k in range(t)
if any(L.key(tuple(q * x for x in gk[k])))]
chars = L.characters()[1:]
N = L.N
ok = True
for c in chars:
vals = [sum(ci * xi for ci, xi in zip(c, gk[k])) % N
for k in Ws]
if not any(v and (q * v) % N == 0 for v in vals):
ok = False
break
hid += ok
check("C2 no ring ideal read at some depth is hidden by its W*",
n_id > 0 and hid == 0,
f"{hid} of {n_id}, {time.time() - t0:.1f} s")
def section_k():
print("K integer cubics, every triple to 64 terms", flush=True)
t0 = time.time()
total = 0
for q, l, top, even, exact in [(2, 2, 16, False, False),
(3, 3, 27, False, False),
(4, 2, 16, False, False),
(4, 2, 32, True, True)]:
kept = hid = 0
for ms in groups(l, top, exact=exact):
G = Group(ms)
for a in integer_cubics(q, even):
k_, h_, _ = sweep(G, q, a)
kept += k_
hid += h_
total += hid
print(f" q {q}, order {'' if exact else '<= '}{top}"
f"{', a1, a2 even' if even else ''}: kept {kept}, hiding "
f"{hid}, {time.time() - t0:.1f} s", flush=True)
check("K no eventually-zero sequence has W* hiding G", total == 0,
f"{total}")
def line_bits(G, l):
"""Element index -> the bit of its line of G[l] (0 off G[l] - 0),
and the number of lines."""
lm, muls = G.mul(l), [G.mul(c) for c in range(1, l)]
bit = np.zeros(G.N, dtype=np.int64)
n = 0
for x in range(1, G.N):
if lm[x] == 0 and bit[x] == 0:
for m in muls:
bit[m[x]] = 1 << n
n += 1
return bit, n
def lines_hit(G, q, a, l, firsts=None, terms=None, every=None):
"""Every r-tuple (g_0 in firsts if given), run to 0, or to `terms`
terms if given: per sequence the number of distinct lines <q g_k>
with ord q g_k = l, as a histogram {count: sequences}. every: a list
collecting the ids of the sequences hitting all lines."""
r, N = len(a), G.N
bit, n = line_bits(G, l)
bit = bit[G.mul(q)]
mula = [G.mul(-c) for c in a]
rest = N ** (r - 1)
blocks = [(f * rest, (f + 1) * rest) for f in firsts] if firsts \
else [(0, N ** r)]
hist = {}
for b0, hi in blocks:
for lo in range(b0, hi, CHUNK):
ids = np.arange(lo, min(hi, lo + CHUNK), dtype=np.int64)
seq = [ids // N ** (r - 1 - j) % N for j in range(r)]
acc = np.zeros(len(ids), dtype=np.int64)
k = 0
while (k < terms) if terms else \
any(np.any(x) for x in seq[k:k + r]):
acc |= bit[seq[k]]
nxt = mula[0][seq[k]]
for j in range(1, r):
nxt = G.add[nxt * N + mula[j][seq[k + j]]]
seq.append(nxt)
k += 1
cnt = sum((acc >> b) & 1 for b in range(n))
if every is not None:
every.extend(int(x) for x in ids[cnt == n])
for c, m in zip(*np.unique(cnt, return_counts=True)):
hist[int(c)] = hist.get(int(c), 0) + int(m)
return hist
def span(G, gens):
"""The subgroup of G generated by gens, as a set of indices."""
out, frontier = {0}, [0]
while frontier:
nxt = []
for x in frontier:
for g in gens:
y = int(G.add[x * G.N + g])
if y not in out:
out.add(y)
nxt.append(y)
frontier = nxt
return out
def run(G, a, i0):
"""The sequence of the initial tuple with id i0, run to 0."""
r, N = len(a), G.N
mula = [G.mul(-c) for c in a]
seq = [i0 // N ** (r - 1 - j) % N for j in range(r)]
k = 0
while any(seq[k:k + r]):
nxt = int(mula[0][seq[k]])
for j in range(1, r):
nxt = int(G.add[nxt * N + mula[j][seq[k + j]]])
seq.append(nxt)
k += 1
return seq
def r13(G, q, a, l, i0):
"""Whether g_i lies in V_(i+1), i least with ord q g_k = l."""
seq = run(G, a, i0)
qm, lm = G.mul(q), G.mul(l)
i = next(k for k, g in enumerate(seq)
if qm[g] != 0 and lm[qm[g]] == 0)
return seq[i] in span(G, set(seq[i + 1:]))
def section_l2():
print("L2 lines <q g_k> of order l, r = 2", flush=True)
t0 = time.time()
h7 = lines_hit(Group((2, 2, 2)), 1, (0,) * 7, 2, firsts=[1])
check("C5 the counter reads all 7 lines of (2, 2, 2): q = 1, f = x^7, "
"seven free terms", max(h7) == 7, f"most {max(h7)}")
h3 = lines_hit(Group((8, 8)), 4, (4, 0, 0), 2)
check("C4 r = 3, (8, 8), q 4, x^3 + 4: some sequence hits all 3 "
"lines", max(h3) == 3, f"histogram {h3}")
top = two = 0
for l, q, order, us, extra in [(2, 2, 256, (1, 3, 5, 7), []),
(2, 4, 256, (1, 3, 5, 7), [(32, 32)]),
(2, 8, 256, (1, 3, 5, 7), [(32, 32)]),
(3, 3, 243, (1, 2), []),
(3, 9, 243, (1, 2), [(27, 27)])]:
pairs, hist = 0, {}
for ms in [x for x in groups(l, order) if len(x) == 2] + extra:
G = Group(ms)
firsts = homocyclic_firsts(G)
for a0 in sorted({q * u % G.E for u in us}):
for (a1,) in local_coeffs(l, G.E, 1):
for c, n in lines_hit(G, q, (a0, a1), l,
firsts).items():
hist[c] = hist.get(c, 0) + n
pairs += 1
top = max(top, max(hist))
two += hist.get(2, 0)
print(f" q {q}, rank 2, order <= {order}"
f"{''.join(f', {x}' for x in extra)}: {pairs} (G, f0) pairs, "
f"sequences by lines hit {dict(sorted(hist.items()))}, "
f"{time.time() - t0:.1f} s", flush=True)
check("L2 r = 2: no sequence puts q g_k on 3 lines", top <= 2 and
two > 0, f"most {top}, {two} sequences at 2 under R7's cut")
def section_l3():
print("L3 lines <q g_k> of order l, r = 3, full rank", flush=True)
t0 = time.time()
h = lines_hit(Group((2, 2, 2)), 1, (1, 1, 0), 2, terms=7)
check("C6 l | f0(0) dropped: q 1, x^3 + x + 1 on (2, 2, 2), 7 terms, "
"some sequence hits all 7 lines", max(h) == 7, f"histogram {h}")
top = {}
for ms, l, q, a0s in [((4, 4, 4), 2, 2, (2,)), ((8, 8, 8), 2, 2, (2,)),
((8, 8, 8), 2, 4, (4,)), ((9, 9, 9), 3, 3, (3, 6))]:
G = Group(ms)
firsts = homocyclic_firsts(G)
hist, pairs = {}, 0
for a0 in a0s:
for a1, a2 in local_coeffs(l, G.E, 2):
for c, n in lines_hit(G, q, (a0, a1, a2), l,
firsts).items():
hist[c] = hist.get(c, 0) + n
pairs += 1
top[l] = max(top.get(l, 0), max(hist))
print(f" {ms} q {q}: {pairs} f0, sequences by lines hit "
f"{dict(sorted(hist.items()))}, {time.time() - t0:.1f} s",
flush=True)
check("L3 full rank r = 3: at most B lines, 4 at l = 2, 5 at l = 3",
top[2] <= 4 and top[3] <= 5, f"most {top}")
def section_l4(rng):
print("L4 rank 2 inside cubic f0, case B", flush=True)
t0 = time.time()
G = Group((8, 8))
g0, g1 = (int(G.index(np.array(v))) for v in ((1, 0), (0, 1)))
check("C7 R13's reader says no: (8, 8) q 4 x^3 + 4, g = (1, 0), "
"(0, 1), 0 has g_0 off V_1", not r13(G, 4, (4, 0, 0), 2,
g0 * G.N ** 2 + g1 * G.N))
bad = top3 = 0
for ms, l, q, a0s, a12 in [
((8, 8), 2, 4, (4,), [(0, 0)]),
((4, 4), 2, 2, (2,), None), ((8, 8), 2, 2, (2,), None),
((8, 8), 2, 4, (4,), None), ((16, 16), 2, 4, (4,), None),
((9, 9), 3, 3, (3, 6), None),
((27, 27), 3, 3, (3,), [(x, y) for x in (0, 3, 6)
for y in (0, 3, 6)])]:
G = Group(ms)
firsts = homocyclic_firsts(G)
hist, pairs, every, read = {}, 0, [], 0
for a0 in a0s:
for a1, a2 in a12 or local_coeffs(l, G.E, 2):
found = []
for c, n in lines_hit(G, q, (a0, a1, a2), l, firsts,
every=found).items():
hist[c] = hist.get(c, 0) + n
every.append(((a0, a1, a2), found))
pairs += 1
total = sum(len(f) for _, f in every)
cells = [(a, x) for a, f in every for x in f]
if total > 2000:
cells = rng.sample(cells, 2000)
for a, x in cells:
read += 1
bad += not r13(G, q, a, l, x)
if l == 3:
top3 = max(top3, max(hist))
tag = " x^3 + 4" if a12 == [(0, 0)] else ""
print(f" {ms} q {q}{tag}: {pairs} f0, sequences by lines hit "
f"{dict(sorted(hist.items()))}, R13 read at {read} of "
f"{total} hitting all, {time.time() - t0:.1f} s", flush=True)
check("L4 R13: every sequence read hitting all l + 1 lines has g_i "
"in V_(i+1)", bad == 0, f"{bad} off")
print(f" q 3, rank 2: most {top3} lines of 4 (TRANSPLANT predicted "
f"4)", flush=True)
def primitive_cyclics(G, l):
"""R15: every <h> with h not in lG, each once."""
lG = set(int(x) for x in G.mul(l))
out, seen = [], set()
for h in range(G.N):
if h not in lG:
S = frozenset(span(G, [h]))
if S not in seen:
seen.add(S)
out.append(S)
return out
def is_closed(qm, S, elems):
"""R5: k in W*, q g_k in S give g_k in S; elems the W* terms."""
return all(g in S or int(qm[g]) not in S for g in elems)
def binomial_k(G, seq, cyc, lines):
"""T4's K: a cyclic <h>, h not in lG, through a line no <g_i>[l]
(i < 3) is, else one holding g_0."""
taken = set()
for g in seq[:3]:
if g:
taken.add(next(x for x in span(G, [g]) if lines[x]))
free = [S for S in cyc if not any(x in taken for x in S if lines[x])]
return free[0] if free else next(S for S in cyc if seq[0] in S)
def section_w(rng_bn, full):
print("W rank 2 inside cubic f0, x^3 + a0: T4's closed <h>", flush=True)
t0 = time.time()
def binomial(G, l, q, a, seqs):
qm, lm = G.mul(q), G.mul(l)
lines = [bool(x) and lm[x] == 0 for x in range(G.N)]
cyc = primitive_cyclics(G, l)
return sum(not is_closed(qm, binomial_k(G, s, cyc, lines),
[g for g in s if qm[g]]) for s in seqs)
G = Group((8, 8))
ctl = binomial(G, 2, 2, (2, 2, 0),
(run(G, (2, 2, 0), i0) for i0 in range(G.N ** 3)))
check("C11 T4's K at x^3 + 2x + 2 on (8, 8), q 2, is open somewhere",
ctl > 0, f"{ctl} sequences")
total = fails = pairs = 0
for l, q, small, big in [(2, 2, 32, 256), (2, 4, 32, 256),
(2, 8, 0, 256), (3, 3, 27, 243),
(3, 9, 0, 243)]:
for ms in [x for x in groups(l, big if full else small)
if len(x) == 2]:
G = Group(ms)
if G.E <= q:
continue
for a0 in sorted({q * u % G.E for u in range(1, G.E) if u % l}):
a = (a0, 0, 0)
if G.N <= small:
ids = range(G.N ** 3)
else:
ids = [rng_bn.randrange(G.N ** 3) for _ in range(3000)]
fails += binomial(G, l, q, a, (run(G, a, i0) for i0 in ids))
total += len(ids)
pairs += 1
print(f" BN q {q}: {pairs} (G, a0) pairs so far, {total} "
f"sequences, {fails} open, {time.time() - t0:.1f} s",
flush=True)
check("BN T4's K is closed at every binomial sequence read",
fails == 0, f"{total} sequences, {pairs} (G, a0) pairs")
def mask_of(idx):
m = 0
for i in idx:
m |= 1 << int(i)
return m
class Tree:
"""T5's engine: G's cyclic subgroups as bitmasks, the <h>, h not in
lG, of order l^N2, and a memo for the joins V_k = V_(k+1) + <g_k>."""
def __init__(self, G, l):
self.G, self.l, N, E = G, l, G.N, G.E
self.A2 = G.add.reshape(N, N)
self.M = np.array([G.mul(j) for j in range(E)]) # [j, x]
self.ml = ml = G.mul(l)
ordx = np.zeros(N, dtype=np.int64)
for x in range(1, N):
y, o = x, 0
while y:
y, o = int(ml[y]), o + 1
ordx[x] = o
self.ordx = ordx
self.cyc = [mask_of(set(self.M[:, x])) for x in range(N)]
ids = {}
self.cid = [ids.setdefault(c, len(ids)) for c in self.cyc]
lG = set(int(v) for v in self.ml)
self.n1 = int(ordx.max())
self.n2 = int(min(ordx[G.index(np.eye(len(G.ms), dtype=np.int64)
[i])] for i in range(len(G.ms))))
seen, self.P = set(), []
for h in range(N):
if h in lG or self.cyc[h] in seen:
continue
seen.add(self.cyc[h])
if ordx[h] == self.n2:
self.P.append((h, self.cyc[h]))
self.memo = {}
def join(self, V, g):
key = (V, g)
if key not in self.memo:
els = [i for i in range(self.G.N) if V >> i & 1]
mul = self.M[:, g]
self.memo[key] = mask_of(np.unique(self.A2[np.ix_(els, mul)]))
return self.memo[key]
def suffixes(T, seq):
"""V_k as bitmasks, k = 0..len(seq) (V_len = 0)."""
V = [0] * (len(seq) + 1)
V[-1] = 1
for k in range(len(seq) - 1, -1, -1):
V[k] = T.join(V[k + 1], seq[k])
return V
def closed_ks(T, R, seq, q):
"""The <h> in R (as (h, mask)) closed for W* = {k : q g_k != 0}."""
mq = T.G.mul(q)
W = [(int(mq[g]), g) for g in seq if mq[g]]
return [K for K in R
if not any(K[1] >> x & 1 and not K[1] >> g & 1 for x, g in W)]
def brute_closed(T, R, seq, q):
"""The <h> in R whose character (a generator of <h>^perp) is a
witness, by direct arithmetic on character values."""
G, E = T.G, T.G.E
sc = np.array([E // m for m in G.ms], dtype=np.int64)
vals = (G.els * sc) @ G.els.T % E # [chi, x]
mq = G.mul(q)
W = [g for g in seq if mq[g]]
out = []
for h, Km in R:
perp = np.flatnonzero(vals[:, h] == 0)
chi = perp[np.argmax(T.ordx[perp])]
if all(vals[chi, g] == 0 or (q * vals[chi, g]) % E for g in W):
out.append((h, Km))
return out
def gates(T, R, seq, V, D):
"""R18's gates in R: (depth, key, class, level, degenerate)."""
out = []
for k, g in enumerate(seq):
if T.ordx[g] < 2:
continue
x = int(T.ml[g])
if not any(K[1] >> x & 1 for K in R):
continue
c, a = (k - D) % 3, (k - D) // 3
deg = c == 0 and bool(V[min(k + 3, len(seq))] >> g & 1)
out.append((int(T.ordx[g]) - 1, (T.cid[x], T.cid[g]), c, a, deg))
return out
def g1_fails(gs):
"""G1's reader: gates of both non-D classes, or two X at one depth."""
xs = {}
for d, key, c, a, deg in gs:
if c:
xs.setdefault(d, set()).add(key)
return (len({c for d, key, c, a, deg in gs if c}) > 1 or
any(len(v) > 1 for v in xs.values()))
def g2_fails(gs, deg_as_d=False, shift=0):
"""G2's reader: two non-degenerate D gates at one depth, or one off
its level's X depth. Its plants: deg_as_d counts the degenerate ones
too (C15), shift reads the level clause that many levels off (C16)."""
xdep = {a: d for d, key, c, a, deg in gs if c}
per = {}
for d, key, c, a, deg in gs:
if c:
continue
if not deg or deg_as_d:
per.setdefault(d, set()).add(key)
if not deg and a + shift in xdep and xdep[a + shift] != d:
return True
return any(len(v) > 1 for v in per.values())
def reach(T, R, seq):
"""|A_d|, d = 0..N2: the depth-d vertices of R's chains no gate
above depth d has broken."""
l, n2 = T.l, T.n2
W = [(int(T.ml[x]), x) for x in seq if T.ordx[x] >= 2]
out = [set() for _ in range(n2 + 1)]
for h, Km in R:
kd = min((int(T.ordx[g]) for x, g in W
if Km >> x & 1 and not Km >> g & 1), default=n2 + 1)
for d in range(min(kd, n2 + 1)):
out[d].add(T.cid[int(T.M[l ** (n2 - d) % T.G.E, h])])
return [len(a) for a in out]
def gate_read(T, seq, tally):
l, N = T.l, T.G.N
V = suffixes(T, seq)
if bin(V[0]).count("1") != N:
return
tally["seqs"] += 1
size = [bin(v).count("1") for v in V]
D = next(k for k in range(3) if size[k] == size[k + 1])
tally[f"D{D}"] += 1
if T.n1 == T.n2:
Hp = next(V[k] for k in (1, 2) if size[k] * l == N)
R = [K for K in T.P if not Hp >> K[0] & 1]
else:
R = T.P
gs = gates(T, R, seq, V, D)
tally["g1"] += g1_fails(gs)
tally["g2"] += g2_fails(gs)
tally["c15"] += g2_fails(gs, deg_as_d=True)
tally["c16"] += g2_fails(gs, shift=1)
per = {}
for d, key, c, a, deg in gs:
per.setdefault(d, [set(), 0])[0].add(key)
per[d][1] += deg
gmax = max((len(p[0]) for p in per.values()), default=0)
closed = closed_ks(T, R, seq, l)
tally["g3"] += gmax <= l and not closed
tally["g4"] += not closed
tally["degseq"] += any(x[4] for x in gs)
if gmax > l:
tally["over"] += 1
tally["over_deg"] += sum(p[1] for p in per.values()
if len(p[0]) > l)
tally["over_open"] += not closed
tally["over_thin"] += min(reach(T, R, seq)[1:]) == 1
def section_g(rng):
print("G rank 2 at e = 1: the gate count (R16-T5)", flush=True)
t0 = time.time()
G = Group((8, 8))
T = Tree(G, 2)
ix = lambda *v: int(G.index(np.array(v))) # noqa: E731
seq = run(G, (4, 0, 0), ix(1, 0) * G.N ** 2 + ix(0, 1) * G.N + ix(1, 1))
a, b = closed_ks(T, T.P, seq, 4), brute_closed(T, T.P, seq, 4)
ok, n = a == b, len(a)
for ms in ((4, 4), (8, 4), (8, 8)):
Gm = Group(ms)
Tm = Tree(Gm, 2)
for i0 in range(1, Gm.N ** 3, 97):
s = run(Gm, (2, 2, 0), i0)
if bin(suffixes(Tm, s)[0]).count("1") == Gm.N:
break
ca, cb = closed_ks(Tm, Tm.P, s, 2), brute_closed(Tm, Tm.P, s, 2)
ok &= ca == cb
n += len(ca)
check("C12 the closure reader agrees with the brute character reader "
"on C4's sequence and one sequence per q 2 arm", ok,
f"{n} closed <h> in all, {len(T.P)} <h> per (8, 8) sequence")
crng, plant = random.Random(17241), None
for _ in range(200000):
lst = [crng.randrange(1, G.N) for _ in range(crng.randrange(3, 9))]
if not closed_ks(T, T.P, lst, 2):
plant = lst
break
gm = 0
if plant is not None:
per = {}
for g in plant:
if T.ordx[g] >= 2:
per.setdefault(int(T.ordx[g]) - 1, set()).add(
(T.cid[int(T.ml[g])], T.cid[g]))
gm = max(len(v) for v in per.values())
check("C13 the reader's no: a bare list in (8, 8) with no closed <h> "
"among all twelve, its largest g_d above l", gm > 2,
f"{[tuple(int(c) for c in G.els[g]) for g in plant or []]}, "
f"largest g_d {gm}")
fired = read = 0
for f in homocyclic_firsts(G):
for rest in range(G.N ** 2):
s = run(G, (2, 0, 0), f * G.N ** 2 + rest)
V = suffixes(T, s)
if bin(V[0]).count("1") != G.N:
continue
read += 1
size = [bin(v).count("1") for v in V]
D = next(k for k in range(3) if size[k] == size[k + 1])
fired += g1_fails(gates(T, T.P, s, V, D))
check("C14 G1's reader fires with R widened to both sides of e "
"(x^3 + 2 on (8, 8))", fired > 0, f"{fired} of {read} sequences")
arms = [((4, 4), 2, (2,), None), ((8, 4), 2, (2,), None),
((8, 8), 2, (2,), None), ((16, 8), 2, (2,), 2000),
((16, 16), 2, (2,), 2000), ((9, 9), 3, (3,), None),
((27, 27), 3, (3, 6, 12), 2000), ((27, 9), 3, (3,), 2000),
((25, 25), 5, (5,), 2000)]
keys = ("seqs", "D0", "D1", "D2", "g1", "g2", "g3", "g4", "c15",
"c16", "over", "over_deg", "over_open", "over_thin", "degseq")
tot = dict.fromkeys(keys, 0)
for ms, l, a0s, draw in arms:
G = Group(ms)
T = Tree(G, l)
for a0 in a0s:
fs = [(a0, a1, a2) for a1 in range(0, G.E, l)
for a2 in range(0, G.E, l)]
t = dict.fromkeys(keys, 0)
if draw is None:
firsts = homocyclic_firsts(G) or range(G.N)
for a in fs:
for f in firsts:
for rest in range(G.N ** 2):
gate_read(T, run(G, a, f * G.N ** 2 + rest), t)
else:
while t["seqs"] < draw:
gate_read(T, run(G, rng.choice(fs),
rng.randrange(G.N ** 3)), t)
for k in keys:
tot[k] += t[k]
print(f" {ms} q {l} a0 {a0}: {t['seqs']} generating "
f"sequences{' (drawn)' if draw else ''} (D = 0, 1, 2 at "
f"{t['D0']}, {t['D1']}, {t['D2']}), |R| <= {len(T.P)}; "
f"G1 fails {t['g1']}, G2 {t['g2']}, G3 {t['g3']}; no "
f"closed <h> in R at {t['g4']}; a degenerate D gate at "
f"{t['degseq']}; g_d > l at {t['over']} ({t['over_deg']} "
f"degenerate D terms there, {t['over_open']} with no closed "
f"<h>, {t['over_thin']} with some |A_d| = 1); "
f"{time.time() - t0:.1f} s", flush=True)
check("C15 G2's count clause fires with degenerate D gates counted",
tot["c15"] > 0, f"{tot['c15']} sequences")
check("C16 G2's level clause fires read one level off",
tot["c16"] > 0, f"{tot['c16']} sequences")
check("G1 R's gates: at most one non-D class, one per depth", tot["g1"] == 0,
f"{tot['g1']} sequences")
check("G2 one non-degenerate D gate per depth, at its level's X depth",
tot["g2"] == 0, f"{tot['g2']} sequences")
check("G3 g_d <= l at every depth leaves a closed <h> in R",
tot["g3"] == 0, f"{tot['g3']} sequences")
print(f" G4 (census) no closed <h> in R at {tot['g4']} of "
f"{tot['seqs']} (D = 0, 1, 2 at {tot['D0']}, {tot['D1']}, "
f"{tot['D2']}); g_d > l at {tot['over']}, some |A_d| = 1 at "
f"{tot['over_thin']}; {time.time() - t0:.1f} s", flush=True)
def section_s2():
t0 = time.time()
scan = runs = 0
for q, l, tops in [(2, 2, (16, 32, 64)), (4, 2, (16, 32, 64)),
(3, 3, (27, 81))]:
for top in tops:
for ms in groups(l, top, exact=True):
G = Group(ms)
for u in range(1, G.E):
if u % l == 0:
continue
for a1 in range(G.E):
for win in (8, 12):
scan += sweep(G, q, (q * u % G.E, a1), nil=False,
window=win, terms=win + 3)[1]
runs += 1
check("S2 r = 2 without nilpotence, every a_1, W* cut to [0, 8) and "
"[0, 12): no hiding", runs > 0 and scan == 0,
f"{runs} runs, {scan} hiding, {time.time() - t0:.1f} s")
def family(name, l, q, r, orders, a0s, only=None):
t0 = time.time()
seqs = hid = pairs = 0
for top in orders:
for ms in only or groups(l, top, exact=True):
if len(ms) == 1 or len(ms) > r or max(ms) <= q:
continue
G = Group(ms)
firsts = homocyclic_firsts(G)
for a0 in sorted({a % G.E for a in a0s}):
for rest in local_coeffs(l, G.E, r - 1):
kept, h, first = sweep(G, q, (a0,) + rest,
terms=10 ** 6, firsts=firsts)
seqs += kept
pairs += 1
if h:
hid += h
print(f" HIDES G {ms}, f0 coeffs "
f"{(a0,) + rest}, {h} tuples, first {first}",
flush=True)
print(f" {name}: {pairs} (G, f0) pairs, {seqs} sequences, hiding "
f"{hid}, {time.time() - t0:.1f} s", flush=True)
check(f"{name.split()[0]} no hiding", hid == 0, f"{hid}")
def main():
t0 = time.time()
full = "--full" in sys.argv
control()
section_c2()
section_l2()
section_l3()
section_l4(random.Random(4))
section_w(random.Random(6), full)
section_g(random.Random(1724))
section_s2()
section_k()
family("A q 4 cubic, order 64", 2, 4, 3, [64], [4])
family("B q 8 cubic, order 64", 2, 8, 3, [64], [8])
family("C q 9 cubic, order 81", 3, 9, 3, [81], [9, 36, 63])
if full:
family("D q 4 quartic, order <= 32", 2, 4, 4, [16, 32],
[4 * u for u in range(1, 16, 2)])
family("E q 4, every invariant factor above q", 2, 4, 3, [0], [4],
only=[(16, 8), (16, 16), (8, 8, 8), (32, 32)])
family("E q 8, (16, 16)", 2, 8, 3, [0], [8], only=[(16, 16)])
family("E q 9, (27, 27)", 3, 9, 3, [0], [9], only=[(27, 27)])
print(f"{sum(CHECKS)}/{len(CHECKS)} checks pass, "
f"{time.time() - t0:.1f} s")
return 0 if all(CHECKS) else 1
if __name__ == "__main__":
sys.exit(main())