Probability Measures

and

Computational Complexity

Alexandre Borovik

Lyon, 14 April 2003

Motivation

• “Average case” complexity

• “Fast checks”: easy answers to most instances of hard problems

Applications: Group theoretic cryptography Quotient tests We compute in a finitely presented group

G = ⟨x_{1}, …, x_{m} | r_{1}, …, r_{n}⟩ = F/R. Elements x, y ∈ G are freely reduced words in the free group

F = ⟨x_{1}, …, x_{m}⟩

with a routine checking whether x = y in G ⟺ xy^{−1} ∈ R.

Quotient tests for identity in G:

work with a smaller factor group H = F/Q, R < Q, with a quicker identity routine:

x ∉ Q ⟹ x ∉ R.

How one can measure the relative efficiency of a quotient test?

A case study G = B_{n} braid group given by

\binom{n}{2} “band generators” s_{ij}

Two tests: which is best? B_{n} ⟶ Sym_{n} s_{ij} ↦ (ij) B_{n} ⟶ ℤ s_{ij} ↦ 1

w ↦ \{ \begin{matrix}the sum of \\ exponents \\ of generators \end{matrix} Given a “random” element

x ∈ F_{\frac{n(n−1)}{2}} = ⟨x_{1}, …, x_{\frac{n(n−1)}{2}}⟩,

which is more likely:

x = 0 in ℤ  or  x = 1 in Sym_{n}?

Random element: produced by a lazy random walk of length k. We need “laziness” to avoid the odd/even length disparity: at every step, pause with probability \frac{1}{n} Probability to hit 1:

r_{k}(ℤ) ∼ \frac{1}{\sqrt{2πk}} · (1 − \frac{1}{n})^{−1}

r_{k}(Sym_{n}) ⩽ \frac{1}{n!} + ane^{−\frac{2k}{n}}

a ≈ 1 does not depend on n

[Diaconis-Shashahani]

For k ≈ 1000, n ≈ 100 the test

B_{n} ⟶ Sym_{n}

is incomparably better than B_{n} ⟶ ℤ Testing conjugacy: p_{k} = probability for two random walks of length k to produce conjugate elements

p_{k}(ℤ) ≈ \frac{1}{2\sqrt{πk}}
p_{k}(Sym_{n}) ≈ \frac{1}{n^{2}}  [Babai and Pyber]

Now the test

B_{n} ⟶ Sym_{n}

is not better than

B_{n} ⟶ ℤ

Some lessons:

• there is need for practical methods for engineering style, “back of the envelope” calculations

• even in simplest problems we are at the frontiers of existing theories

• “asymptotically best” does not mean “best”

On the free group F_{m}, we need

families of atomic probabilty measures of varying mean length of words.

• Should be natural in the context of computational group theory.

• Easy to study asymptotic behaviour when the mean word length tends to infinity.

• Easy, ‘back of an envelope’ estimates of probabilities of ‘standard’ subsets:

– (normal) subgroups,

– cosets with respect to subgroups,

– conjugacy classes,

– sets of words of special nature (say, squares or commutators).

• Many sets we wish to measure are context free languages.

• An important subclass: regular subsets (produced by deterministic finite automata):

– finitely generated subgroups and their cosets;

– cones: sets of all words which start with the given initial segment.

– Closed under

∗ Boolean operations,

∗ translation by elements of F,

∗ conjugation.

A natural choice: Measures generated by random walks

[figure: x; x^{−1}; y; y^{−1}; x; y; y^{−1}; x; x^{−1}; y^{−1}; x^{−1}; y; y^{−1}]

A no-return random walk on the Cayley tree for the free group F = ⟨x, y⟩.

No return random walk on the tree as a random word generator

• Start at 1

– either return 1 with probability s,

– or move to one of the 2m adjacent vertices with probability

\frac{1 − s}{2m}.

• When at a vertex v ≠ 1, – either return v with probability s,

– or move, with probability

\frac{1 − s}{2m − 1},

to one of the 2m − 1 adjacent vertices lying away from 1.

In other words: take random freely reduced words w of random lengths |w| distributed by the exponential law

P (|w| = k) = s(1 − s)^{k}.

We get the atomic probability measure

μ_{s}(w) = \frac{s(1 − s)^{|w|}}{2m · (2m − 1)^{|w|−1}} for w ≠ 1
μ_{s}(1) = s

Mean length: L_{s} such that

s = \frac{1}{L_{s} + 1}

L_{s} → ∞ ⟺ s → 0 Renormalisation:

μ_{s}^{∗}(w) = (\frac{2m}{2m − 1} · \frac{1}{s}) · μ_{s}(w).

μ_{s}^{∗} is multiplicative:

μ_{s}^{∗}(u ∘ v) = μ_{s}^{∗}(u)μ_{s}^{∗}(v);

u ∘ v denotes the product such that |uv| = |u| + |v| i.e. there is no cancellation.

μ_{s} is almost multiplicative:

μ_{s}(u ∘ v) = cμ_{s}(u)μ_{s}(v)

A similar approach, Flajolet et al.: “Boltzmann Sampler” for random combinatorial objects: If a thing A is made from things B and C then

p(A) = p(B) · p(C)

For R ⊂ F, its measure μ(R) is the analytic function

μ(R) : (0, 1) → ℝ
s ↦ μ_{s}(R)

We are interested in its behaviour at

s → 0^{+}

which is the same as the mean length L_{s} → ∞ Sphere S_{k} = { w | |w| = k } Relative frequencies of R ⊂ F:

f_{k} = \frac{|R ∩ S_{k}|}{|S_{k}|}

Frequency measure:

λ(w) = \frac{1}{2m(2m − 1)^{|w|−1}}, if w ≠ 1,
λ(1) = 1
λ(R) = ∑_{k=1}^{∞} f_{k}(R)

Generating functions Set t = μ_{s}^{∗}(x_{i}) (x_{i} a generator) Let R ⊂ F ∖ {1}, r_{k} = |R ∩ S_{k}|.

μ^{∗}(R) = ∑_{k=0}^{∞} r_{k}t^{k}

the generating function for the number of elements of length k in R.

μ(R) = s ∑_{k=0}^{∞} f_{k}(1 − s)^{k}

is essentially the generating function for the relative frequencies

f_{k} = \frac{|R ∩ S_{k}|}{|S_{k}|}.

Linear approximation at s = 0:

μ(R) = μ_{0} + μ_{1}s + o(s)

Hardy and Littlewood:

μ_{0}(R) = lim_{n→∞} \frac{1}{n} (f_{1} + ⋯ + f_{n}) .

(the Cesaro limit) If H < F and |F : H| < ∞,

μ_{0}(H) = \frac{1}{|F : H|}

For the subgroup H consisting of all elements of even length,

{f_{k}} = 1, 0, 1, 0, 1, 0, …
μ_{0}(H) = lim_{n→∞} \frac{1}{2n} (1 + 0 + ⋯ + 1 + 0)
= \frac{1}{2}
= \frac{1}{|F : H|}

Linear approximation at s = 0:

μ(R) = μ_{0} + μ_{1}s + o(s)

Tauberian theorem by Hardy and Littlewood: If μ_{0}(R) = 0, then

μ_{1}(R) = ∑_{k=1}^{∞} f_{k}(R)

Linear approximation at s = 0:

μ(R) = μ_{0} + μ_{1}s + o(s)

If the frequency measure

λ(R) = ∑_{k=1}^{∞} f_{k}(R)

exists, then

μ_{0}(R) = 0

and

μ_{1}(R) = λ(R)

Classification of sets by size:

• Thick: μ_{0}(R) exists, μ_{0}(R) > 0 and μ(R) = μ_{0}(R) + o(1)

• Thin: μ_{0}(R) = 0, μ_{1}(R) = ∑ f_{k} exists and μ(R) = μ_{1}(R)s + o(s)

• Sparse: μ_{0}(R) = 0, μ_{1}(R) = ∑ f_{k} exists and lim sup ^{k} \sqrt{f_{k}} < 1

(exponential decline of f_{k} with a global bound)

• Intermediate density subsets: μ_{0}(R) = 0 but μ_{1}(R) does not exist.

• Singular sets: μ_{0}(R) does not exist.

Degrees of polynomial growth

f : F ⟶ ℝ^{⩾0}

The average value f on the sphere S_{k}:

E_{k} = ∑_{|w|=k} \frac{f(w)}{|S_{k}|}

E_{k} = ∑_{|w|=k} \frac{f(w)}{|S_{k}|}

For every fixed s ∈ (0, 1), the mean value E_{f}(s) of f with respect to μ_{s}:

E_{f}(s) = ∑_{w∈F} f(w)μ_{s}(w)

= s ∑_{k=0}^{∞} E_{k}(1 − s)^{k}.

E_{f}(s) = ∑_{w∈F} f(w)μ_{s}(w)

= s ∑_{k=0}^{∞} E_{k}(1 − s)^{k}.

f has polynomial growth of degree d on average if

∫_{0}^{1} \frac{E_{f}(s)}{s^{d}}ds

converges when s → 0^{+} The definition is natural; f(w) = |w|^{d} has growth of degree d on average.

Let χ be the characteristic function of R ⊂ F. R is polynomially negligible if, for every d,

|w|^{d}χ(w)

has growth of degree at most 0 on average. (Can be ignored in ‘cut and paste’ computations of average case complexity.)

Theorem Let R ⊲ F be a normal subgroup.

• If G = F/R is not recurrent then R is thin:

μ(R) = μ_{1}(s)s + o(s).

• If G = F/R is not amenable then R is sparse and polynomially negligible.

Co-diagonal subgroup D ⊲ F = ⟨x_{1}, …, x_{m}⟩: the kernel of the homomorphism

F ⟶ ℤ, x_{i} ↦ 1

μ(D) = \frac{(m − 1)}{m\sqrt{2 − \frac{2}{m}}} · \sqrt{s} + o(\sqrt{s})

D is not polynomially negligible.

Quotient test revisited:

B_{n} ⟶ ℤ = F/D
B_{n} ⟶ Sym_{n} = F/S
μ(D) ≈ \begin{matrix}√ & \overline{s} \\ √ & \overline{2} \end{matrix}
μ(S) ≈ \frac{1}{n!} + μ_{1}s + o(s)

Can be shown: μ_{1} < 10 Theorem If K ◁ F, F/K = G finite then

μ(K) = μ_{0} + μ_{1}(s) + o(s)
μ_{0} = \frac{1}{|G|}
μ_{1} = \frac{1}{2m} + \frac{1}{|G|} · \frac{2m − 1}{2m} · ∑_{i=2}^{|G|} \frac{1}{1 − λ_{i}}

where

1 = λ_{1} > λ_{2} ⩾ ⋯ ⩾ λ_{|G|}

are the eigenvalues of the simple random walk on G.

Of course, 1 − λ_{2} is the spectral gap of G: determines the mixing time of random walk on G = F/K

Multiplicative measure: logarithmic rescaling of convergence Quotient test revisited:

F_{m} ⟶ ℤ/n!ℤ = F/K
F_{m} ⟶ Sym_{n} = F/S

m = \frac{n(n − 1)}{2}

μ(K) = \frac{1}{n!} + μ_{1}(K)s + ⋯
μ(S) = \frac{1}{n!} + μ_{1}(S)s + ⋯

Character theory yields:

μ_{1}(K) ≈ \frac{n!}{π^{2}}
μ_{1}(S) < 10

Context-free and regular sets

• Chomski and Schutzenberger: If R is a context free language then μ(R) is an algebraic function.

• We can uniformise μ(R) at s = 0:

μ(R) = m_{0} + m_{1}s^{1/n} + m_{2}s^{2/n} + ⋯

• If R is a regular set (produced by a finite automaton) then μ(R) is a rational function.

• If R is rational then

– either R is thick, μ(R) = μ_{0}(R) + O(s), μ_{0}(R) > 0

– or R is sparse, μ(R) = μ_{1}(R)s + O(s^{2})

Regular sets If A and B are regular subsets in F,

• A ∪ B, A ∩ B and A ∖ B are regular.

• The prefix closure Ā of A is regular. Here, the prefix closure Ā is the set of all initial segments of all words in A.

• The product and the inverse set

AB = { ab | a ∈ A, b ∈ B }

A^{−1} = { a^{−1} | a ∈ A }

are regular.

• Every finite subset is regular.

• If ϕ : F ⟶ F is an endomorphism then ϕ(A) is regular.

Thick regular sets A cone C = C(w) is a set of all elements in F containing the given word w as initial segment. Obviously, cones are thick regular sets:

μ(C(w)) = \frac{1}{|S_{|w|}|} + O(s).

Theorem A regular subset R ⊂ F is thick if and only if its prefix closure R̄ contains a cone.