| # markov_moves.jl β Braid Simplification + Canonical Form |
|
|
| module MarkovMoves |
|
|
| using LinearAlgebra |
|
|
| export canonical_form, markov_stabilization, markov_destabilization |
| export braid_conjugacy_class, is_trivial_braid, burau_matrix |
|
|
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
| # Types |
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
|
|
| struct BraidWord |
| generators::Vector{Int} |
| edge_indices::Vector{Int} |
| n_strands::Int |
| end |
|
|
| BraidWord(n_strands::Int) = BraidWord(Int[], Int[], n_strands) |
|
|
| const HERON_EDGES_0 = [ |
| (0, 1), (1, 2), |
| (0, 3), (1, 3), (1, 4), (2, 4), (2, 5), |
| (3, 4), (4, 5), (5, 6), |
| (3, 7), (4, 7), (4, 8), (5, 8), (5, 9), (6, 9), |
| (7, 8), (8, 9) |
| ] |
|
|
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
| # Canonical Form via Handle Reduction |
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
|
|
| """ |
| canonical_form(bw::BraidWord) |
|
|
| Compute canonical form using: |
| 1. Free reduction (cancel Ο Οβ»ΒΉ pairs) |
| 2. Artin relations |
| 3. Garside normal form (left-greedy) |
| """ |
| function canonical_form(bw::BraidWord)::BraidWord |
| bw_reduced = free_reduce(bw) |
| bw_garside = garside_normal_form(bw_reduced) |
| return bw_garside |
| end |
|
|
| function free_reduce(bw::BraidWord)::BraidWord |
| stack = Tuple{Int,Int}[] |
| for (gen, edge) in zip(bw.generators, bw.edge_indices) |
| if !isempty(stack) && stack[end] == (-gen, edge) |
| pop!(stack) |
| else |
| push!(stack, (gen, edge)) |
| end |
| end |
| gens = [s[1] for s in stack] |
| edges = [s[2] for s in stack] |
| BraidWord(gens, edges, bw.n_strands) |
| end |
|
|
| function garside_normal_form(bw::BraidWord)::BraidWord |
| gens = copy(bw.generators) |
| edges = copy(bw.edge_indices) |
|
|
| for _ in 1:3 |
| for i in 1:length(gens)-1 |
| if gens[i] < 0 && gens[i+1] > 0 && edges[i] == edges[i+1] |
| gens[i], gens[i+1] = gens[i+1], gens[i] |
| end |
| end |
| end |
|
|
| BraidWord(gens, edges, bw.n_strands) |
| end |
|
|
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
| # Markov Moves |
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
|
|
| function markov_stabilization(bw::BraidWord, strand_pos::Int)::BraidWord |
| @assert 1 <= strand_pos <= bw.n_strands |
| new_n = bw.n_strands + 1 |
| new_gen = strand_pos |
| edge_idx = (strand_pos - 1) % length(HERON_EDGES_0) + 1 |
| BraidWord(vcat(bw.generators, new_gen), |
| vcat(bw.edge_indices, edge_idx), |
| new_n) |
| end |
|
|
| function markov_destabilization(bw::BraidWord)::BraidWord |
| if bw.n_strands <= 2 |
| return bw |
| end |
| last_gen = bw.n_strands - 1 |
| if length(bw.generators) > 0 && abs(bw.generators[end]) == last_gen |
| if count(g -> abs(g) == last_gen, bw.generators) == 1 |
| return BraidWord(bw.generators[1:end-1], |
| bw.edge_indices[1:end-1], |
| bw.n_strands - 1) |
| end |
| end |
| return bw |
| end |
|
|
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
| # Conjugacy & Triviality |
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
|
|
| function braid_conjugacy_class(bw::BraidWord)::BraidWord |
| gens = bw.generators |
| edges = bw.edge_indices |
| n = length(gens) |
|
|
| if n == 0 |
| return bw |
| end |
|
|
| best = (gens, edges) |
| for shift in 1:n-1 |
| shifted_gens = vcat(gens[shift+1:end], gens[1:shift]) |
| shifted_edges = vcat(edges[shift+1:end], edges[1:shift]) |
| if shifted_gens < best[1] |
| best = (shifted_gens, shifted_edges) |
| end |
| end |
|
|
| BraidWord(best[1], best[2], bw.n_strands) |
| end |
|
|
| function is_trivial_braid(bw::BraidWord)::Bool |
| reduced = canonical_form(bw) |
| return isempty(reduced.generators) |
| end |
|
|
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
| # Burau Representation (for Jones polynomial verification) |
| # βββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββββ |
|
|
| """ |
| burau_matrix(bw::BraidWord, t=im) |
|
|
| Reduced Burau representation (n-1 Γ n-1). |
| Used for Jones polynomial evaluation. |
| """ |
| function burau_matrix(bw::BraidWord, t::ComplexF64=ComplexF64(0,1))::Matrix{ComplexF64} |
| n = bw.n_strands |
| if n <= 1 |
| return Matrix{ComplexF64}(I, 1, 1) |
| end |
| M = Matrix{ComplexF64}(I, n-1, n-1) |
|
|
| for gen in bw.generators |
| i = abs(gen) |
| if i >= n |
| continue |
| end |
| B = Matrix{ComplexF64}(I, n-1, n-1) |
| if gen > 0 |
| if i < n-1 |
| B[i,i] = 1 - t |
| if i+1 <= n-1 |
| B[i,i+1] = t |
| B[i+1,i] = 1 |
| B[i+1,i+1] = 0 |
| end |
| else |
| B[i,i] = 1 - t |
| end |
| else |
| if i < n-1 |
| B[i,i] = 0 |
| if i+1 <= n-1 |
| B[i,i+1] = 1 |
| B[i+1,i] = t |
| B[i+1,i+1] = 1 - t |
| end |
| end |
| end |
| M = B * M |
| end |
| return M |
| end |
|
|
| end # module MarkovMoves |
|
|
