Opened 6 months ago
Closed 4 months ago
#16059 closed defect (fixed)
Equality vs hash for braid groups
Reported by: | tmonteil | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.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 tmonteil)
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 5 months ago by chapoton
- Description modified (diff)
- Keywords Cayley added; Caylay removed
comment:2 Changed 5 months ago by tmonteil
- Branch set to u/tmonteil/equality_vs_hash_for_braid_groups
Changed 5 months ago by tmonteil
Changed 5 months ago by tmonteil
comment:3 Changed 5 months ago by tmonteil
- Commit set to 141adb09fe3e8f45079d706135dc071dc2e1eec7
- Description modified (diff)
- Status changed from new to needs_review
comment:4 Changed 5 months ago by tmonteil
comment:5 Changed 5 months ago by tscrim
- Reviewers set to Travis Scrimshaw
comment:6 Changed 5 months ago by tmonteil
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 4 months ago by vbraun_spam
- Milestone changed from sage-6.2 to sage-6.3
comment:8 Changed 4 months ago by chapoton
- Status changed from needs_review to needs_work
sage -t --long src/sage/groups/braid.py # 1 doctest failed
comment:9 Changed 4 months ago by git
- Commit changed from 141adb09fe3e8f45079d706135dc071dc2e1eec7 to 1e7d2f07e3cdb7d99a0cd0502078791a47176153
comment:10 Changed 4 months ago by tscrim
- Branch changed from u/tmonteil/equality_vs_hash_for_braid_groups to u/tscrim/equality_hash_braid_groups-16059
- 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_groups-16059 |
d54f18c | Added extra doctest. |
comment:11 Changed 4 months ago by tmonteil
- Branch changed from u/tscrim/equality_hash_braid_groups-16059 to u/tmonteil/equality_hash_braid_groups-16059
comment:12 Changed 4 months ago by tmonteil
- 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 4 months ago by tscrim
- Status changed from needs_review to positive_review
I like this doctest better. Positive review. Thanks.
comment:14 Changed 4 months ago by vbraun
- Branch changed from u/tmonteil/equality_hash_braid_groups-16059 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.