Black Box Groups

and other

Non-Deterministic Problems of Group Theory

Alexandre Borovik

Lyon, 7 April 2003

Black Box Group

random, independent, uniformly distributed elements random, independent, uniformly distributed elements given as

[figure: X; y; z; x; ...]

• permutations, or

• matrices in GL_{n}(q),

• … “Format”: n^{2} log q

[figure: X; y; z; x; ...]

• (sometimes) find orders: |x| Aim: determine X Recognition of black box is highly technical and uses CFSG.

Two simple examples in my lectures later:

• Recognition of Sym_{n} and Alt_{n} as Galois groups (Davenport-Smith)

• Constructive recognition of Sym_{n} (Bratus’-Pak).

In this talk, I concentrate on a general set-up and realtions to combinatorial group theory Generation of random elements, Leedham-Green et al.: Γ_{k}(G) set of generating k-tuples

graph with edges:

(g_{1}, …, g_{i}, …, g_{k}) ⟶ (g_{1}, …, g_{j}^{±1}g_{i}, …, g_{k})
(g_{1}, …, g_{i}, …, g_{k}) ⟶ (g_{1}, …, g_{i}g_{j}^{±1}, …, g_{k})

Walk randomly over this graph and choose random g_{i}.

Random walk on Γ_{k}(G) Pak: For k large, the mixing time is polynomial in log |G|. Mixing time: number t of steps s.t. after t steps

\frac{1}{2} ∑_{v∈Γ} |P (get at v) − \frac{1}{#Γ}| < \frac{1}{e}

Lubotzky–Pak: If Aut F_{k} satisfies Kazhdan property (T), then mixing time of a random walk on a component of Γ_{k}(G)

mix ⩽ C(k) · log_{2} |G|.

Kazhdan property (T) G a topological group, Q ⊂ G a compact set

K = inf_{ρ} inf_{v≠0} max_{q∈Q} \frac{∥ρ(q)(v) − v∥}{∥v∥} > 0

ρ: all unitary representations without fixed non-zero vectors

Centralisers of involutions in black box groups

Global exponent Assume that we know a computationally feasible E such that x^{E} = 1 for all x ∈ X. Factorise

E = 2^{l} · m , m odd.

Construction of involutions:

E = 2^{l} · m , m odd
x ↦ x^{m}, (x^{m})^{2}, …, (x^{m})^{2^{r}} ≠ 1, 1
i(x) := (x^{m})^{2^{r}} is an involution

Involutions in black box groups, commutative case: Simmons’ attack on repeated use of moduli in RSA.

• The key server distributes keysets (n, d, e) with de ≡ 1 mod (ϕ(n)),

reusing n but keeping the factorisation n = pq secret.

• However, the user knows n and de ≡ 1 mod (ϕ(n))

• E = de is a global exponent of (ℤ/nℤ)^{∗} However, the user can factorise n:

• (ℤ/nℤ)^{∗} is a black box group of global exponent E = de.

• Find an involution x ≠ −1 in (ℤ/nℤ)^{∗}.

• Since

x^{2} − 1 ≡ 0 mod n,

we have

n | (x − 1)(x + 1).

• Calculation of gcd(n, x − 1) and gcd(n, x + 1) yields a non-trivial factor of n.

Centralisers of involutions: If t is an involution, we have a map

ζ : X ⟶ C_{X}(t)
ζ_{1} : X ⟶ C_{X}(t)
x ↦ (t · t^{x})^{(m+1)/2} · x^{−1}, |t · t^{x}| odd
ζ_{2} : X ⟶ C_{X}(t)
x ↦ i(t · t^{x}), |t · t^{x}| even
ζ = ζ_{1} ∪ ζ_{2}

Cumulative product:

z := 1
z := z · ζ(x) for running x ∈ X

shows a good performance as a black box for C_{X}(t).

Application [B and Parker-Wilson]:

Computation of O_{p}(X) for matrix black box groups X in characteristic p > 2.

• For large p, unipotent and non-semisimple elements occur with probability ∼ 1/p and are “invisible”: a random element is semisimple.

• Computations are essentially done in pseudofinite groups. more on this in my lectures Why does ζ work? If c ∈ C_{X}(t),

ζ_{1}(cx) = (tt^{cx})^{(m+1)/2} · x^{−1} · c^{−1}
= (tt^{x})^{(m+1)/2} · x^{−1} · c^{−1}
= ζ_{1}(x) · c^{−1}

If x ∈ X are uniformly distributed and independent, then ζ_{1}(x) are uniformly distributed and independent in C_{X}(t) Black box in X generates a black box in C_{X}(t).

What about involutions ζ_{2}(x)?

• They generate a normal subgroup in C_{X}(t).

• What can be said about normal subgroups of black box groups?

Structural theory of black box groups

• If X is non-simple, how one can find a normal subgroup?

X = X′ ⟹ there are involutions t
Y ⊲ X ⟹ Y ∩ C_{X}(t) ⊲ C_{X}(t)

• How one can construct a good black box for the normal closure

⟨y_{1}^{X}, …, y_{k}^{X}⟩?

Andrews–Curtis graph for N ⊲ G Δ_{k}(G, N) = {(h_{1}, …, h_{k}) | ⟨h_{1}^{G}, …, h_{k}^{G}⟩ = N} Edges:

(x_{1}, …, x_{k}) ⟶ (x_{1}, …, x_{i}x_{j}, …, x_{k}), i ≠ j
(x_{1}, …, x_{k}) ⟶ (x_{1}, …, x_{i}^{−1}, …, x_{k})
(x_{1}, …, x_{k}) ⟶ (x_{1}, …, x_{i}^{w}, …, x_{k}), w ∈ G

Conjecture. A random walk on Δ_{k}(G, N) provides a fast black box for N.

The Andrews-Curtis Conjecture (1965):

Δ_{k}(F_{k}, F_{k}) is connected

Myasnikov: Δ_{k}(F_{k}^{(m)}, F_{k}^{(m)}) is connected for the free solvable group F_{k}^{(m)}.

Myasnikov & Myasnikov: Some potential counterexamples (originating in topology) are killed by application of genetic algorithms, say, in F = ⟨x, y⟩,

(x^{2}y^{−3}, xyxy^{−1}x^{−1}y^{−1}) ∼ (x, y)

(example by Akbulut and Kirbi, 1985).

Genetic Algorithms A less technical example: solving equations in a free group (Bormotov-Myasnikov and B-Booth).

• An equation in variable x over the free group F_{k} = ⟨a_{1}, …, a_{k}⟩

is a word

w(x, a_{1}, …, a_{k})

from the free product ⟨x⟩ ∗ F_{k}.

• u ∈ F_{k} is a solution if w(u, a_{1}, …, a_{k}) = 1.

• Population {u} is a finite set of approximate solutions.

• Fitness function measures the quality of an approximation u. In a naive approach, it is the length

l(w(u, a_{1}, …, a_{k}))

of the word w(u) after all cancellations.

• B-Booth: A population of fitness functions.

Survival of the fittest

• Start with a random population {u}.

• Aim at finding an element u of fitness 0 (an exact solution).

• Breeding: given u, v, their child is the concatenation of some beginning segment of u with an end segment of v.

• Fitter individuals participate in breeding more frequently than less fit ones.

• Mutation: insertion or deletion random letters a_{i} at or from random positions.

• Regularly cull less fit individuals.

Playing God. The rules of selection of breeding pairs, deletion unfit individuals, frequencies of mutations are chosen, by trial and error, for better performance of the algorithm.

Playing Darwin. A potential more sophisticated way of fine tuning the evolution:

Run a co-evolution of a population of solutions and population of selection parameters, like a co-evolution of flowers and bees.

B-Booth: An example of convergence of co-evolution to a deterministic algorithm.

It was first discovered that genetic algorithms do solve equations in free groups; and only later a theoretical explanation started to emerge. It appears that the existence of an efficient genetic algorithm for a group theoretic problem suggests the existence of a good deterministic algorithm.

Killing counterexamples to Andrews-Curtis: a more technical version of the same idea.

• A genetic version algorithm to Andrews-Curtis is exhausted.

• A counterexample is more likely, but genetic algorithms cannot produce a counterexample.

• Can a counterexample to Andrews-Curtis be found at the level of finite groups?

Finitary AC Conjecture

B, Lubotzky & Myasnikov: In a finite group G, the connected components of Δ_{k}(G, G) are those inherited from G/[G, G].

• No easy way to refute the AC conjecture using finite groups.

Let G = ⟨S⟩ and N ⊲ G. Restricted Andrews–Curtis graph \overline{Δ}_{k}(G, N): the same vertices as in Δ_{k}(G, N):

{ (h_{1}, …, h_{k}) | ⟨h_{1}^{G}, …, h_{k}^{G}⟩ = N } . Two vertices are connected by one of the edges:

(…, x_{i}, …, x_{j}, …) ⟶ (…, x_{i}x_{j}^{±1}, …,), i ≠ j
(…, x_{i}, …, x_{j}, …) ⟶ (…, x_{j}^{±1}x_{i}, …), i ≠ j
(…, x_{i}, …) ⟶ (…, x_{i}^{s}, …), s ∈ S
(…, x_{i}, …) ⟶ (…, x_{i}^{−1}, …).

Problem. Are \overline{Δ}_{k}(G, N) expanders?

• The “YES” answer would explain a good practical performance of the AC algorithm for generation random elements of normal subgroups.

• Related question: does the group AC_{k}(F_{k}) generated by the (reduced) Andrews-Curtis transformations of the free group F_{k} has Kazhdan’s Property (T)?

What about random elements in infinite groups? Later in my lectures