Groups as uniformly automatic classes#
For abelian groups, addition is automatic because collecting a product in a polycyclic presentation never creates error terms. Once generators stop commuting, every collection step conjugates tail generators past head generators — and whether the class stays uniformly automatic depends on whether a synchronous automaton can absorb those corrections:
advice-definable constants (like \(s^2 = r^w\)) are free — write \(w\) on the advice tape;
inversion is free — it is addition with permuted arguments;
shifts at advice-marked positions are free;
genuine bilinearity between two unbounded values is fatal — it embeds integer multiplication, which no automaton recognizes.
autstr implements a family of group classes sitting right on the good side of that
line. Every member’s multiplication M(x, y, z) (meaning \(x \cdot y = z\)) is decided by
one automaton for the whole class.
Variable naming. Use single lowercase letters
[a-df-z](nevere), optionally with digits.
Finite abelian groups#
A group like \(\mathbb{Z}_2 \oplus \mathbb{Z}_3\) is encoded by LSB-first binary blocks, one
per cyclic factor, separated by #; the advice is the list of orders. A(x, y, z)
means \(z = x + y\).
from autstr.groups import FiniteAbelianGroups
ab = FiniteAbelianGroups()
print('A((1,1),(1,2),(0,0)) in Z2+Z3:', ab.check('A(x,y,z)', [2, 3], x=(1, 1), y=(1, 2), z=(0, 0)))
# One compiled automaton, evaluated over many groups: "has an element of order 4".
phi = 'exists x.((not A(x,x,x)) and (exists z.(A(x,x,z) and A(z,z,z))))'
dfa, _ = ab.evaluate(phi)
for orders in ([4], [3], [2, 3], [5, 6]):
print(f'orders={orders}: has an order-4 element =',
dfa.accepts([(s,) for s in ab.advice(orders)]))
A((1,1),(1,2),(0,0)) in Z2+Z3: True
orders=[4]: has an order-4 element = True
orders=[3]: has an order-4 element = False
orders=[2, 3]: has an order-4 element = True
orders=[5, 6]: has an order-4 element = True
Groups with a cyclic subgroup of index \(\le 2\)#
These are classified into six families over the cyclic part \(\mathbb{Z}_n\):
family |
group |
conjugation \(u\) |
twist square \(w\) |
|---|---|---|---|
|
\(\mathbb{Z}_2 \times \mathbb{Z}_n\) |
\(1\) |
\(0\) |
|
\(C_{2n}\) |
\(1\) |
\(1\) |
|
\(D_n\) |
\(-1\) |
\(0\) |
|
\(\mathrm{Dic}_n\) (e.g. \(Q_8\)) |
\(-1\) |
\(n/2\) |
|
\(SD_{2n}\) |
\(n/2-1\) |
\(0\) |
|
\(M_{2n}\) |
\(n/2+1\) |
\(0\) |
The advice is one family symbol followed by the binary digits of \(n\); the multiplication
is defined first-order from tiny primitives via UniformlyAutomaticClass.define.
from autstr.groups import IndexTwoCyclicGroups
%time idx2 = IndexTwoCyclicGroups()
print('multiplication automaton:', idx2.cls.class_automata['M'].num_states, 'states')
CPU times: user 3.38 s, sys: 83 ms, total: 3.47 s
Wall time: 3.46 s
multiplication automaton: 181 states
Multiplying in the quaternion group#
\(Q_8\) is dicyclic(4): with \(i = r\), \(j = s\), the element \((e, a)\) is \(r^a s^e\). The one
automaton decides every product — here \(i \cdot j\) and the famous \(j^2 = r^2 = -1\).
q8 = idx2.dicyclic(4)
i, j = (0, 1), (1, 0)
ij, jj = idx2.multiply(q8, i, j), idx2.multiply(q8, j, j)
print('i*j =', ij, ' j*j =', jj, '(= r^2 = -1)')
print('automaton confirms i*j:', idx2.check('M(x,y,z)', q8, x=i, y=j, z=ij))
i*j = (1, 1) j*j = (0, 2) (= r^2 = -1)
automaton confirms i*j: True
One automaton, the whole zoo#
Compile is non-abelian once; every member is then classified by running its advice word. The Klein four-group \(D_2\) is correctly seen as abelian.
nonabelian = 'exists x.(exists y.(exists z.(M(x,y,z) and (not M(y,x,z)))))'
dfa, tapes = idx2.evaluate(nonabelian)
assert tapes == ['advice']
zoo = [('Z2 x Z9', idx2.abelian(9)), ('C14', idx2.cyclic(7)),
('D2 (Klein)', idx2.dihedral(2)), ('D16', idx2.dihedral(16)),
('Q8', idx2.dicyclic(4)), ('SD32', idx2.semidihedral(16)),
('M32', idx2.modular(16))]
for name, advice in zoo:
print(f'{name:>12}: non-abelian = {dfa.accepts([(s,) for s in advice])}')
Z2 x Z9: non-abelian = False
C14: non-abelian = False
D2 (Klein): non-abelian = False
D16: non-abelian = True
Q8: non-abelian = True
SD32: non-abelian = True
M32: non-abelian = True
# A subtler separator: Q8 has a unique involution (central -1); D4 has several.
two_involutions = ('exists x.(exists y.((not Eq(x,y)) and (not Eq(x,o)) and '
'(not Eq(y,o)) and M(x,x,o) and M(y,y,o)))')
print('Q8 has two distinct involutions:', idx2.check(two_involutions, idx2.dicyclic(4), o=(0, 0)))
print('D4 has two distinct involutions:', idx2.check(two_involutions, idx2.dihedral(4), o=(0, 0)))
Q8 has two distinct involutions: False
D4 has two distinct involutions: True
Extraspecial \(p\)-groups: nilpotency class 2, growing rank#
For a fixed prime \(p\), the Heisenberg-type group of order \(p^{1+2n}\) has elements \((c, \mathbf a, \mathbf b)\) with
The commutator correction \(\langle \mathbf a, \mathbf b'\rangle\) is bilinear — but it pairs digits positionwise, so it is a running sum mod \(p\) in the automaton state. Growing the rank is fine; growing the modulus would embed unbounded modular multiplication and is provably not automatic.
from autstr.groups import ExtraspecialGroups
%time heis3 = ExtraspecialGroups(3)
g, h = (1, (2, 0), (1, 1)), (0, (1, 1), (2, 0))
gh = heis3.multiply(g, h)
print('g*h =', gh, ' automaton agrees:', heis3.check('M(x,y,z)', 2, x=g, y=h, z=gh))
# One automaton detects non-commutativity at every rank.
nonabelian = 'exists x.(exists y.(exists z.(M(x,y,z) and (not M(y,x,z)))))'
dfa, _ = heis3.evaluate(nonabelian)
for n in range(4):
print(f'rank {n} (order 3^{1 + 2 * n}): non-abelian =',
dfa.accepts([(s,) for s in heis3.advice(n)]))
CPU times: user 190 ms, sys: 4.01 ms, total: 194 ms
Wall time: 194 ms
g*h = (2, (0, 1), (0, 1)) automaton agrees: True
rank 0 (order 3^1): non-abelian = False
rank 1 (order 3^3): non-abelian = True
rank 2 (order 3^5): non-abelian = True
rank 3 (order 3^7): non-abelian = True
Class-2 groups of bounded rank-width#
The extraspecial groups above pair all generators. Relax that to any commutator
form whose crossing block has bounded linear rank, and you get the bounded-rank-width
class-2 groups. CutRankGroups(p, r, d) presents them: a member is a central extension
of \((\mathbb{Z}/p^d)^n\) given by a commutator form, and the advice spells out, cut by cut,
a rank-\(\le r\) factorisation of the crossing block. The multiplication automaton carries
\(r\) linear functionals instead of the digits it has read — that is where “rank-width”
enters. With \(d = 1\) this is the field \(\mathbb{F}_p\); with \(d > 1\) the width is measured
over the chain ring \(\mathbb{Z}/p^d\).
from autstr.groups import CutRankGroups
G = CutRankGroups(2) # width 1 over F_2
n = 3
form = G.clique_form(n) # the extraspecial pairing, as a cut-rank form
adv = G.advice(n, form)
print('multiplication automaton:', G.cls.class_automata['M'].num_states, 'states')
g, h = ((1,), (1, 0, 1)), ((0,), (0, 1, 1)) # elements are (center, generators)
z = G.multiply(n, form, g, h)
print('g*h =', z, ' automaton agrees:', G.check('M(x,y,z)', adv, x=g, y=h, z=z))
print('non-abelian member:', G.check(nonabelian, adv))
multiplication automaton: 6 states
g*h = ((0,), (1, 1, 0)) automaton agrees: True
non-abelian member: True
# A different layout over the same class: a matching form (disjoint pairs).
form2 = G.matching_form(n)
adv2 = G.advice(n, form2)
a, b = ((0,), (1, 1, 0)), ((1,), (0, 1, 1))
print('matching-form product:', G.multiply(n, form2, a, b),
G.check('M(x,y,z)', adv2, x=a, y=b, z=G.multiply(n, form2, a, b)))
matching-form product: ((1,), (1, 0, 1)) True
Over the chain ring (\(d > 1\), exponent \(p^d\)) the advice alphabet grows so fast that the
multiplication automaton can no longer be built — yet the same members can still be
queried by evaluating the law on the fly. That is the subject of the
implicit-evaluation notebook, which also compares the two paths’ running times. The
tree-layout variant CutRankTreeGroups and the graph analog RankWidthClass
(see the graphs notebook) share this exact machinery.