Opened 6 years ago
Closed 6 years ago
#16059 closed defect (fixed)
Equality vs hash for braid groups
Reported by:  tmonteil  Owned by:  

Priority:  major  Milestone:  sage6.3 
Component:  group theory  Keywords:  braid group, hash, Cayley graph 
Cc:  Merged in:  
Authors:  Thierry Monteil  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  a5fce2a (Commits)  Commit:  a5fce2a1fbb4790b581d23ef2ec0841f05f14f67 
Dependencies:  Stopgaps: 
Description (last modified by )
Playing with braid groups for a demo today, i want to see its Cayley graph in a neighbourhood of the neutral element:
ball = set() ball.add(B.one()) for length in range(1,4): for w in Words(alphabet=B.gens(), length=length): ball.add(prod(w)) G = B.cayley_graph(elements=ball, generators=B.gens()) G.plot()
Hmmm, it looks locally like the free group, as if there was no relation !
s0 * s2
is a different vertex as s2 * s0
, while:
sage: s0 * s2 == s2 * s0 True
Indeed:
sage: hash(s0 * s2) 954209079 sage: hash(s2 * s0) 1883627875
There should be a canonical representation for elements in Braid groups. At least, two equal elements should have the same hash. Currently, cayley_graph
answers something wrong !
After the modification, the Cayley group looks like:
Attachments (2)
Change History (16)
comment:1 Changed 6 years ago by
 Description modified (diff)
 Keywords Cayley added; Caylay removed
comment:2 Changed 6 years ago by
 Branch set to u/tmonteil/equality_vs_hash_for_braid_groups
Changed 6 years ago by
Changed 6 years ago by
comment:3 Changed 6 years ago by
 Commit set to 141adb09fe3e8f45079d706135dc071dc2e1eec7
 Description modified (diff)
 Status changed from new to needs_review
comment:4 Changed 6 years ago by
comment:5 Changed 6 years ago by
 Reviewers set to Travis Scrimshaw
comment:6 Changed 6 years ago by
Actually, there is already an indirect check when G
answers Digraph on 31 vertices
(to be compared to Digraph on 40 vertices
for the free group, some vertices are merged). Is it enough ?
Otherwise, i do not know a short way to represent directed graphs in Sage, but i could add a test for the undirected version of the graph using sparse6_string
representation along the following lines just after the previous example, though i am not sure it is easy to read:
sage: graph_string = ':^_`aa`ddd`aHhh_lmmmfLqqlStt_HjWxxvW{{' sage: G.to_undirected().is_isomorphic(Graph(graph_string)) True
What do you think ?
comment:7 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:8 Changed 6 years ago by
 Status changed from needs_review to needs_work
sage t long src/sage/groups/braid.py # 1 doctest failed
comment:9 Changed 6 years ago by
 Commit changed from 141adb09fe3e8f45079d706135dc071dc2e1eec7 to 1e7d2f07e3cdb7d99a0cd0502078791a47176153
comment:10 Changed 6 years ago by
 Branch changed from u/tmonteil/equality_vs_hash_for_braid_groups to u/tscrim/equality_hash_braid_groups16059
 Commit changed from 1e7d2f07e3cdb7d99a0cd0502078791a47176153 to d54f18c175cc3a5d3db58a3add26178c65afe01c
 Status changed from needs_work to needs_review
Sorry for letting this slip away. I've added an extra doctest which makes the fix more explicit (at least to those of us who don't know how big the a 4 ball of a free group is :p
). If you're happy with this, then positive review.
New commits:
3e11dba  Merge branch 'u/tmonteil/equality_vs_hash_for_braid_groups' of trac.sagemath.org:sage into u/tscrim/equality_hash_braid_groups16059

d54f18c  Added extra doctest.

comment:11 Changed 6 years ago by
 Branch changed from u/tscrim/equality_hash_braid_groups16059 to u/tmonteil/equality_hash_braid_groups16059
comment:12 Changed 6 years ago by
 Commit changed from d54f18c175cc3a5d3db58a3add26178c65afe01c to a5fce2a1fbb4790b581d23ef2ec0841f05f14f67
@tscrim : now i get your point. I have merged the two Cayley graph doctests in a single one to avoid repetitions, with a sentence to explain the difference with the free group.
@chapoton : i removed the direct hash test whose output depends on the architecture.
comment:13 Changed 6 years ago by
 Status changed from needs_review to positive_review
I like this doctest better. Positive review. Thanks.
comment:14 Changed 6 years ago by
 Branch changed from u/tmonteil/equality_hash_braid_groups16059 to a5fce2a1fbb4790b581d23ef2ec0841f05f14f67
 Resolution set to fixed
 Status changed from positive_review to closed
Could you add an
is_isomorphic()
check to the Cayley graph of the corresponding free group (or some other way of showing it's not the Cayley graph of the free group)? Once that is done, you can set a positive review on my behalf.