Se você não está familiarizado com a teoria da trança, recomendo que você leia isso primeiro. Esta pergunta pressupõe que você esteja pelo menos familiarizado com os conceitos em questão e que você esteja familiarizado com a teoria de grupos

Definamos σ _n ser a trança em que o n ° de cadeia (Uma indexado) da parte superior atravessa a n + 1 th cadeia, e σ _n ^- ser a inversa da σ _n (Isto é o n + 1 th strand cruza a n- ésima strand).

O grupo de trança B _n é então gerado por <σ ₁ , σ ₂ , σ ₃ ,. . . , σ _n-1 > . Assim, toda trança em B _n pode ser escrita como o produto das tranças σ. ¹

Determinar se duas tranças em um grupo são iguais não é uma tarefa simples. Pode ser bastante óbvio que σ ₁ σ ₃ = σ ₃ σ ₁ , mas é um pouco menos óbvio que, por exemplo, σ ₂ σ ₁ σ ₂ = σ ₁ σ ₂ σ ₁ . ²

Portanto, a pergunta é "Como podemos determinar se duas tranças são iguais?". Bem, os dois exemplos acima representam um pouco disso. Em geral, as seguintes relações, chamadas relações de Artin, são verdadeiras:

• σ _i σ _j = σ _j σ _i ; i - j> 1

• σ _i σ _{i + 1} σ _i = σ _{i + 1} σ _i σ _{i + 1}

Podemos usar essas duas relações em conjunto com os axiomas do grupo para provar que quaisquer tranças iguais são iguais. Assim, duas tranças são iguais se a aplicação repetida dessas relações e os axiomas do grupo puderem demonstrar isso.

Tarefa

Você escreverá um programa ou função para pegar duas tranças e determinar se são iguais ou não. Você também pode, opcionalmente, pegar um número inteiro positivo representando a ordem do grupo.

Esta é uma questão de código-golfe, para que as respostas sejam pontuadas em bytes, com menos bytes sendo melhores.

Entrada e saída

Você deve representar um Braid como uma lista ordenada de geradores (ou qualquer estrutura equivalente, por exemplo, vetor). Você pode representar os geradores de qualquer forma razoável (por exemplo, um número inteiro, duas tuplas de um número inteiro positivo e um booleano).

A par das regras de problemas de decisão padrão, você deve gerar um de dois valores distintos, aceitar uma rejeição.

Casos de teste

[],       []              -> 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: Observe que, enquanto B _n satisfaz todas as propriedades de um grupo, a operação em nosso grupo de tranças não é comutativa e, portanto, nosso grupo não é abeliano.}

^{2: Se você deseja verificar isso por si mesmo, sugiro aplicar σ ₁ - a ambos os lados. Se você desenhar os dois no papel ou modelá-los com strings reais, deve ficar claro por que esse é o caso.}

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

Experimente online!

Como funciona

Seja F _n o grupo livre em n geradores x ₁ ,…, x _n . Um dos primeiros resultados da teoria das tranças (Emil Artin, Theorie der Zöpfe , 1925) é que temos um homomorfismo injetivo f : B _n → Aut ( F _n ) onde a ação f _{σ i} de σ _i é definida por

f _{σ i} ( x _i ) = x _i x _{i + 1} x _i ⁻¹ ,
f _{σ i} ( x _{i + 1} ) = x _i ,
f _{σ i} ( x _j ) = x _j para j ∉ { i , i + 1}.

A inversa f _{σ i ^-1} é dada por

f _{σ i ⁻¹} ( x _i ) = x _{i + 1} ,
f _{σ i ^-1} ( x _{i + 1} ) = x _{i + 1} ⁻¹ x _i x _{i + 1} ,
f _{σ i ⁻¹} ( x _j ) = x _j para j ∉ { i , i + 1}

e, é claro, a composição é dada por f _ab = f _a ∘ f _b .

Para testar se a = b ∈ B _n , basta testar se f _a ( x _i ) = f _b ( x _i ) para todos os i = 1,…, n . Esse é um problema muito mais simples em F _n , onde precisamos saber apenas como cancelar x _i com x _i ^-1 .

No código:

• i!jcalcula f _{σ i} ( x _j ) (em que um iou jpode ser negativo, representando um inverso),
• foldr(%)[] realiza redução no grupo livre,
• i&acalcula f _a ( x _i ),
• a?ncalcula [ f _a ( x ₁ ),…, f _a ( x _n )],
• e (a#b)né o teste de igualdade para a = b em B _n .

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)==[]

Experimente online!

Implementação do método 'subword reversing' para resolver o problema de isotopia da trança: a = b iff ab ^ -1 = a identidade.

Algoritmo retirado de: Soluções eficientes para o problema de isotopia da trança, Patrick Dehornoy ; ele descreve vários outros algoritmos que podem ser de interesse ...

Esse algoritmo funciona marcando da esquerda para a direita na lista, procurando um número negativo seguido por um número positivo; ou seja, uma sub-palavra da forma x _i ^-1 x _j com i, j> 0.

Ele usa as seguintes equivalências:

x _i ^-1 x _j = x _j x _i x _j ^-1 x _i ^-1 se i = j + 1 ou j = i + 1

x _i ^-1 x _j = identidade (lista vazia) se i == j

x _i ^-1 x _j = x _j x _i ^-1 caso contrário.

Por aplicação repetida, terminamos com uma lista da forma w1 + w2, onde todo elemento de w1é positivo e todo elemento de w2é negativo. (Esta é a ação da função g).

Em seguida, aplicamos guma segunda vez à lista w2 + w1; a lista resultante deve estar vazia se a lista original for equivalente à identidade.