Black Box Groups Lyon, 10 April 2003

Alexandre Borovik

Black Box

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

An example when we are not given actual elements, only partial information:

Galois group of a polynomial

[figure: f(x) ∈ ℤ[x]; mod q; mod r; mod p; ...]

Reduction modulo random prime number p:

f̄(x) = f̄_{1} ⋯ f̄_{k}, deg f̄_{i} = d_{i},
f_{i} irreducible over 𝔽_{p}
(d_{1}, …, d_{k}) cycle structure of random g ∈ Gal(f)

f(x) ∈ ℤ[x] irreducible polynomial, deg f = n

Reduction modulo random prime number p:

f̄(x) = f̄_{1} ⋯ f̄_{k}, deg f̄_{i} = d_{i},
f_{i} irreducible over 𝔽_{p}

Čebotarev Density Theorem: (d_{1}, …, d_{k}) are lengths of cycles of a random element from G = Gal(f) in its action on the roots of f.

This is a black box!

Sym_{n} and Alt_{n} as Galois groups f(x) ∈ ℤ[x] irreducible polynomial, deg f = n Generically: Gal(f) = Sym_{n} or Alt_{n}. How can one check that f(x) is generic?

Gal(f) = Sym_{n} or Alt_{n}? Reduction modulo random prime number p:

f̄(x) = f̄_{1} ⋯ f̄_{k}, deg f̄_{i} = d_{i}, f̄_{i} irreducible
(d_{1}, …, d_{k}) cycle structure of random g ∈ Gal(f)

Davenport & Smith: If G = Sym_{n} or Alt_{n} then, with probability \frac{log 2}{log n}, we get a cycle of prime length n/2 < q < n, which confirms that G is at least 4-transitive (Jordan)

C. Jordan: If a transitive permutation group on n letters contains a cycle of prime length

n/2 < q < n

then G is at least 4-transitive

Classification of Finite Simple Groups (CFSG):

4-transitive groups are

Sym_{n}, Alt_{n} or a Mathieu group: M_{11}, M_{12}, M_{22}, M_{23}, M_{24}.

Elementary observations: If Gal(F) = Sym_{n},

• an n-cycle occurs with probability 1/n.

• A permutation with 2 cycles (p_{1}, p_{2}), p_{1} + p_{2} = n

occurs with probability

\frac{1}{p_{1}p_{2}}

In general: every finite simple group G has “frequent” elements of orders specific for G.

Typical Example: Matrix Groups

X = ⟨x_{1}, …, x_{k}⟩ ⩽ GL_{n}(𝔽_{q})

is the matrix group of big dimension, so that |X| is astronomical.

• Statistical study of ‘random’ products of x_{1}, …, x_{k} is the only known approach to identification of X.

• Determination of orders involves either

– factorisation of integers into primes, or – the discrete logarithm problem over finite

fields.

Orders of elements in GL_{n}(q):

• |x| is the minimal divisor d of |GL_{n}(q)| such that

x^{d} = 1

• Factorisation is hard

• Exponentiation is easy:

x^{100} = x^{2^{6}+2^{5}+2^{2}}
= x^{2}^{2}^{2}^{2}^{2}^{2} · x^{2}^{2}^{2}^{2}^{2} · x^{2}^{2}

x^{d} requires < 2 log_{2} d multiplications Construction of black boxes for:

X ⩽ GL_{N}(𝔽_{q}),
X = ⟨x_{1}, …, x_{k}⟩

Product Replacement Algorithm: Celler / Leedham-Green / Murray / Niemeyer / O’Brian Product replacement algorithm

• Start with (x_{1}, …, x_{k}) generating X

• Randomly replace

(x_{1}, …, x_{i}, …, x_{k}) ⟵ (x_{1}, …, x_{j}^{±1}x_{i}, …, x_{k})
(x_{1}, …, x_{i}, …, x_{k}) ⟵ (x_{1}, …, x_{i}x_{j}^{±1}, …, x_{k})

• select random x_{i}.

Product replacement algorithm: random walk on the graph: Γ_{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})

Product Replacement Algorithm:

• Very good practical performance

• Biased in artificial examples, say, in X = (Alt_{n})^{n!/8}

(Babai-Pak).

• In general, Γ_{k}(G) is not connected

• Γ_{k}(G) is connected for large k > 2 log_{2} |G| (Babai). In that case

the diameter < C · log^{2} |G|

• Conjecture. If G is simple, Γ_{k}(G) is connected for k ⩾ 3.

Product Replacement Algorithm:

• Pak: If G_{n} are simple, |G_{n}| ⟶ ∞, then Γ_{k}(G) has a connected component Γ′_{k}(G),

\frac{|Γ′_{k}(G)|}{|Γ_{k}(G)|} ⟶ 1

• Pak: If k is sufficiently big, mixing time of a random walk on Γ_{k}(G) is bounded by a polynomial in k and log |G|.

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|.

Conjecture. For k ⩾ 4, Aut F_{k} has (T).

Questions about a black box group X: Identification problem: Determine the isomorphism type of X with given degree of certainty. Verification problem: Is X isomorphic to the given group 𝔾? Constructive recognition: Find an explicit isomorphism

X ⟶ 𝔾 Bratus & Pak, Constructive recognition of Sym_{n}, assuming that we can determine the orders of the elements.

We suspect that X ≃ Sym_{n}, n = 2k.

How can we prove this?

We suspect that X ≃ Sym_{n}, n = 2k. How can we prove this?

• Goldbach’s Conjecture: n = p_{1} + p_{2}, p_{1}, p_{2} distinct primes (checked for n < 10^{20}).

• Find x, |x| = p_{1}p_{2}.

y_{1} = x^{p_{2}} = (1, 2, …, p_{1})
y_{2} = x^{p_{1}} = (p_{1} + 1, …, n)

y_{1} = x^{p_{2}} = (1, 2, …, p_{2})
y_{2} = x^{p_{1}} = (p_{1} + 1, …, n)

• Find y with |y| = 2q_{1}q_{2}, q_{1}, q_{2} odd primes. Compute a transposition

a = x^{q_{1}q_{2}}.

• Check if a interchanges a point from y_{1} with a point from y_{2}, that is,

ay_{1} ≠ y_{1}a and ay_{2} ≠ y_{2}a. If not, repeat the search for a transposition.

y_{1} = x^{p_{2}} = (1, 2, …, p_{1})
y_{2} = x^{p_{1}} = (p_{1} + 1, …, n)
a transposition mixing y_{1} and y_{2}

• Compute b = y_{1}ay_{2}. This is a cycle of length p_{1} + p_{2} = n.

• Compute a_{1} = a^{b^{p_{1}−1}}. Without loss of generality:

b = (1, 2, …, n), a = (p_{1}, p_{1}+1), a_{1} = (1, 2)

b and a_{1} generate Sym_{n}.

b = (1, 2, …, n), a_{1} = (1, 2)

• Compute, by conjugating by b, a_{2} = (2, 3), …, a_{n−1} = (n−1, n), a_{n} = (n, 1).

So we have the standard generators a_{1} = (1, 2), …, a_{n−1} = (n − 1, n), a_{n} = (n, 1).

So we have the standard generators a_{1} = (1, 2), a_{2} = (2, 3), …, a_{n} = (n, 1).

• For an arbitrary x ∈ X, compute x^{−1}a_{1}x = (x(1), x(2)).

By checking which of a_{i} this element commutes with, determine {x(1), x(2)}.

• Analogously, find {x(2), x(3)}, …, {x(n), x(1)}.

• This will give

x(1), … x(n)

• So we can efficiently compute

x(1), … x(n)

• which establishes establishes an isomorphism

X ⟶ Sym_{n}.

The effort so far was concentrated on X ⩽ GL_{N}(𝔽_{q}) simple matrix group X = ⟨x_{1}, …, x_{k}⟩ Distribution of orders of elements is specific for every finite simple group and allows to determine X Routines for GAP and MAGMA People working in the area:

Babai, Beals, Bratus, Brookshank, Celler, Cooperman, Conder, Finkelstein, Holt, Leedham-Green, Linton, Lübeck, Kantor, Lubotzky, Murray, Neumann, Niemeyer, O’Brien, Pak, Palfy, Praeger, Rees, Seres, … Comments

1. Substitute for prime factorisation

X ⩽ GL_{N}(𝔽_{q})
|GL_{N}(𝔽_{q})| = q^{N(N−1)/2}(q − 1) ⋯ (q^{N} − 1)
= r_{1}^{a_{1}} ⋯ r_{m}^{a_{m}} the finest one can get
|x|_{≈} = the least number
l = r_{1}^{b_{1}} ⋯ r_{m}^{b_{m}},
x^{l} = 1.

2. Nature of algorithms Verification algorithms are one-sided: Is X ≃ 𝔾 (the target group)? If X contains an element of order not present in 𝔾, then X ≄ 𝔾 absolutely 3. The landscape is very different from the traditional group theory:

X = SL_{2}(2^{n})

• elements of even order are involutions

• involutions are conjugate • The frequency involutions in SL_{2}(2^{n}):

C = C_{X} (( \begin{matrix}1 & 1 \\ 0 & 1 \end{matrix} ))

= \{( \begin{matrix}1 & ∗ \\ 0 & 1 \end{matrix} )\}
|C| = 2^{n}
#(involutions ) = \frac{|X|}{2^{n}}
P (even order) = \frac{|X|}{2^{n}} · \frac{1}{|X|} = \frac{1}{2^{n}}

If n ≫ 1, X, for all practical purposes, contains no involution and no elements of even order.

4. Statistical approach fails for

B_{n}(q) = Ω_{2n+1}(q),
C_{n}(q) = P Sp_{2n}(q),

q odd: they have virtually the same statistics of orders of elements.

Here, Ω_{2n+1}(q) is the subgroup of index 2 in the

orthogonal group SO_{2n+1}(q), P Sp_{2n}(q) is the projective symplectic group.

Why?

Let G = G(\overline{𝔽}_{q}) be a simple algebraic group

• regular semisimple elements form an open subset of G

• statistics of orders of regular semisimple elements is determined by the Dynkin diagram of G, which are the same in the case of groups B_{n} and C_{n}, n ⩾ 3:

[figure: BC_{n}, n ≥ 2; …]

• But the conjugacy classes and the structure of centralisers of involutions (elements of order 2) are determined by the extended Dynkin diagrams which are different:

[figure: C̃_{n}, n ≥ 3; …; B̃_{n}, n ≥ 3; …]

• Luckily, the frequency of elements of even order in finite algebraic groups over fields of odd characteristic is at least \frac{1}{4}.

Idea: use involutions and their centralisers — if we can construct them.

Involutions in Black Box Groups Miller-Rabin Primality Test:

An odd integer n is prime ⇕

(ℤ/nℤ)^{∗} is cyclic of order n − 1 and contains

exactly one involution −1.

This is a verification problem: is X ≃ ℤ_{n−1}?

Explanation: If n = n_{1} ⋯ n_{k} with n_{1}, …, n_{k} pairwise coprime, then

(ℤ/nℤ)^{∗} = (ℤ/n_{1}ℤ)^{∗} × ⋯ × (ℤ/n_{k}ℤ)^{∗}
−1 mod n = −1 mod n_{1} × ⋯ × −1 mod n_{k}

(Chinese Remainder Theorem)

Miller-Rabin Primality Test:

• Factorise n − 1 = 2^{l} · m, m odd.

• Take random x ∈ (ℤ/nℤ)^{∗}.

• Compute

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

• If i(x) ≠ −1, return “n is not prime,,

• If i(x) = −1 for k random x, return n is prime with probability of error

⩽ \frac{1}{4^{k}}

Centralisers of involutions

Assume that we know a computationally feasible n such that x^{n} = 1 for all x ∈ X (for example, when X ⩽ GL_{d}(𝔽_{q}) for reasonably sized d and q.) Factorise

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

Construction of involutions:

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

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

ζ : X ⟶ C_{X}(t)
x ↦ (t · t^{x})^{(m+1)/2} · x^{−1},
when |t · t^{x}| odd

Why? If |t · t^{x}| = s is odd, the group ⟨t, t^{x}⟩ is the dihedral group of order 2s, and, by Sylow’s Theorem, t^{y} = t^{x} for some y ∈ ⟨t · t^{x}⟩. Then yx^{−1} ∈ C_{X}(t). It can be seen that

y = (t · t^{x})^{(m+1)/2}.

Construction of a black box for C_{X}(t) from a black box for X

If c ∈ C_{X}(t),

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

If x ∈ X are uniformly distributed and independent,

then ζ_{1}(x) are uniformly distributed and independent in C_{X}(t)

We have a remarkable analogy with the Brauer’s programme of classification of finite simple groups in terms of the centralisers of involutions.

Altseimer-Borovik:

• Used centralisers of involution for telling B_{n}(q) from C_{n}(q).

• Systematic development of involution-based algorithms of black box recognition.