16
\$\begingroup\$

If you are not familiar with Braid-Theory I recommend that you read this first. This question assumes that you are at least familiar with the concepts at hand and assumes you are well familiar with group-theory

Let us define \$\sigma_n\$ to be the braid in which the \$n\$th strand (One indexed) from the top crosses over the \$n+1\$th strand, and \$\sigma_n^-\$ to be the inverse of \$\sigma_n\$ (That is the \$n+1\$th strand crosses the \$n\$th strand).

The braid group \$B_n\$ is then generated by \$\langle\sigma_1,\sigma_2,\sigma_3,\dots,\sigma_{n-1}\rangle\$. Thus every braid on \$B_n\$ can be written as the product of the \$\sigma\$-braids.1

Determining if two braids on a group are equal is not a simple task. It may be pretty obvious that \$\sigma_1\sigma_3 = \sigma_3\sigma_1\$, but it is a little less obvious that for example \$\sigma_2\sigma_1\sigma_2 = \sigma_1\sigma_2\sigma_1\$.2

So the question is "How can we determine if two braids are the same?". Well the two examples above each represent a bit of this. In general the following relations, called Artin's relations, are true:

  • \$\sigma_i\sigma_j = \sigma_j\sigma_i; i - j > 1\$

  • \$\sigma_i\sigma_{i+1}\sigma_i = \sigma_{i+1}\sigma_i\sigma_{i+1}\$

We can use these two relations in conjunction with the group axioms to prove that any equal braids are equal. Thus two braids are equal iff the repeated application of these relations and the group axioms can demonstrate so.

Task

You will write a program or function to take two braids and determine whether or not they are equal. You may also optionally take a positive integer representing the order of the group.

This is a question so answers will be scored in bytes, with less bytes being better.

Input and Output

You should represent a Braid as an ordered list of generators, (or any equivalent structure, e.g. vector). You may represent the generators in any reasonable form (e.g. an integer, a two tuple of a positive integer and a boolean).

On par with standard rules you should output one of two distinct values, an accept an reject.

Test Cases

[], [] -> True [1,-1], [] -> True [1,2,1], [2,1,2] -> True [1,3], [3,1] -> True [1,3,2,1],[3,2,1,2] -> True [1,4,-4,3,2,1], [3,2,1,2] -> True [2,2,1], [2,1,2] -> False [1,2,-1], [-1,2,1] -> False [1,1,1,2],[1,1,2] -> False

1: Note that while \$B_n\$ satisfies all the properties of a group the operation on our braid group is not commutative, and thus our group is not abelian.

2: If you would like to verify this for yourself I suggest applying \$\sigma_1^-\$ to both sides, If you draw the two out on paper, or model them with actual strings it should become apparent why this is the case.

Improve this question
\$\endgroup\$
0

3 Answers 3

Reset to default
12
\$\begingroup\$

Haskell, 190 bytes

i!j|j<0=reverse$map(0-)$i!(-j)|i==j=[i,i+1,-i]|i+1==j=[i]|i+j==0=[j+1]|i+j==1=[-j,-i,j] _!j=[j] j%(k:a)|j+k==0=a j%a=j:a i&a=foldr(%)[]$foldr((=<<).(!))[i]a a?n=map(&a)[1..n] (a#b)n=a?n==b?n

Try it online!

How it works

Let Fn be the free group on n generators x1, …, xn. One of the first results in braid theory (Emil Artin, Theorie der Zöpfe, 1925) is that we have an injective homomorphism f : Bn → Aut(Fn) where the action fσi of σi is defined by

fσi(xi) = xixi + 1xi−1,
fσi(xi + 1) = xi,
fσi(xj) = xj for j ∉ {i, i + 1}.

The inverse fσi−1 is given by

fσi−1(xi) = xi + 1,
fσi−1(xi + 1) = xi + 1−1xixi + 1,
fσi−1(xj) = xj for j ∉ {i, i + 1}

and of course composition is given by fab = fa ∘ fb.

To test whether a = b ∈ Bn, it suffices to test that fa(xi) = fb(xi) for all i = 1, …, n. This is a much simpler problem in Fn, where we only need to know how to cancel xi with xi−1.

In the code:

  • i!j computes fσi(xj) (where either i or j may be negative, representing an inverse),
  • foldr(%)[] performs reduction in the free group,
  • i&a computes fa(xi),
  • a?n computes [fa(x1), …, fa(xn)],
  • and (a#b)n is the equality test for a = b in Bn.
Improve this answer
\$\endgroup\$
0
7
\$\begingroup\$

Python 2, 270 263 260 250 249 241 bytes

def g(b,i=0): while i<len(b)-1: R,s=b[i:i+2] if R<0<s:b[i:i+2]=[[],[s,-R,-s,R],[s,R]][min(abs(R+s),2)];i=-1 i+=1 return b def f(a,b): b=g(a+[-v for v in b][::-1]);i=0 while i<len(b)and b[0]>0:b=b[1:]+[b[0]];i+=1 return g(b)==[]

Try it online!

Implementation of the 'subword reversing' method of solving the braid isotopy problem: a=b iff ab^-1 = the identity.

Algorithm taken from: Efficient solutions to the braid isotopy problem, Patrick Dehornoy; he describes several other algorithms which may be of interest...

This algorithm works by marching left to right in the list, searching for a negative number followed by a positive number; i.e., a sub-word of the form xi-1xj with i,j >0.

It uses the following equivalences:

xi-1xj = xjxixj-1xi-1 if i=j+1 or j=i+1

xi-1xj= identity (empty list) if i==j

xi-1xj = xjxi-1 otherwise.

By repeated application, we end up with a list of the form w1 + w2, where every element of w1 is positive and every element of w2 is negative. (This is the action of the function g).

We then apply g a second time to the list w2 + w1; the resulting list should be empty iff the original list was equivalent to the identity.

Improve this answer
\$\endgroup\$
1
  • 2
    \$\begingroup\$ By Corollary 3.5 of that paper, when applying g for the second time, you can apply it on reverse(w1+w2) instead of w2+w1, which will save a few bytes: Try it online! \$\endgroup\$ Commented Nov 22, 2021 at 3:29
2
\$\begingroup\$

Wolfram Language (Mathematica), 110 bytes

!FreeQ[(r=Reverse)[Or@@#||Or@@-r@#2//.(s=i_||j_/;i<0<j:>Switch[i+j,0,1<0,1|-1,j||-i||-j||i,_,j||i])]//.s,1<0]&

Try it online!

A port of Chas Brown's Python answer.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.