Geek Minute

All that is geek...

About

Contact Info

News Letter



Email:

Friday, October 28, 2005

Andrews-Curtis Conjecture

Problem
The Bradley BEAR group that I am involved in is looking to prove/disprove the following concept.

Definitions
Alphabet: X={x₁, x₂,..., x_n}

Syllables: x₁^±1, x₂^±1,..., x_n^±1

Words: Strings of syllables
    Ex: x₁ x₂ x₁^-1 x₅

Syllables are words of length one.
The (unique) word of length zero is denoted *.

Words are multiplied by using concatenation (and reduction)
Ex:
w₁ = x₁ x₃ x₂^-1
w₂ = x₂ x₃^-1 x₄

w₁ * w₂ = (x₁ x₃ x₂^-1) * (x₂ x₃^-1 x₄) = x₁ x₄

You can only reduce when the inverses are touching.

Given w, to form w^-1 read right to left and change the signs (NOTE: w * w^-1 = *)

Ex: w = x₁ x₃ x₂^-1 → w^-1 = x₂ x₃^-1 x₁^-1

List of Moves on Collections of Words
Let (r₁, r₂, ..., r_n} be a list of n words on n letters.
(1) r_j → r_j^-1
(2) r_j → w₁r_jw₁^-1
(3) r_j → r_j r_k or r_k r_j for some j≠k
(4) In all words, replace x_i throughout with
       i) x_i^-1
      ii) x_i x_k (k≠i)
     iii) x_k x_i (k≠i)
(5)Add one new letter x_n+1 and one new word r_n+1 = x_n+1 to the list
(6)The opposite of (5), if possible
(7)Just add * to the list
(8)Remove * from the list

Equivalence
Two lists of words, W₁, W₂, are T-Equivalent if one can be transformed to the other by a sequence of moves of type (1)-(8). W₁ ^~_T W₂

Two lists of words are N-Equivalent if one can be transformed to the other by a sequence of moves of type (1)-(6). W₁ ^~_N W₂

Let {W_o} denote the trivial list of words.

Andrews-Curtis Conjecture (1960's)
If W ^~_T {W_o}, then W ^~_N {W_o}

I.e. if a collection of words can be transformed to {} by moves (1)-(8), then it can be transformed to {} by moves (1)-(6).

It is believed that AC is false. Potential counterexamples include:
{c^-1 b c b^-2, a^-1 c a c^-2, b^-1 a b a^-2}
{b a ² b^-1 a^-3, a b² a^-1 b^-3}
{a b a b^-1 a^-1 b^-1, a⁴ b⁵}

These are known to be T-equivalent to {w_o, but cannot be shown to be N-equivalent.

If there is no algorithm to reconize balanced presentations of the trivial group, then AC is false.

Posted by Jon Heizer at 5:05 PM