Opened 7 months ago

Closed 5 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)

Cayley_before.png (79.6 KB) - added by tmonteil 6 months ago.
Cayley_after.png (55.8 KB) - added by tmonteil 6 months ago.

Download all attachments as: .zip

Change History (16)

comment:1 Changed 7 months ago by chapoton

  • Description modified (diff)
  • Keywords Cayley added; Caylay removed

comment:2 Changed 6 months ago by tmonteil

  • Branch set to u/tmonteil/equality_vs_hash_for_braid_groups

Changed 6 months ago by tmonteil

Changed 6 months ago by tmonteil

comment:3 Changed 6 months ago by tmonteil

  • Commit set to 141adb09fe3e8f45079d706135dc071dc2e1eec7
  • Description modified (diff)
  • Status changed from new to needs_review

comment:4 Changed 6 months ago by tmonteil

  • Authors set to Thierry Monteil

comment:5 Changed 6 months ago by tscrim

  • Reviewers set to Travis Scrimshaw

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.

comment:6 Changed 6 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 6 months ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:8 Changed 6 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 6 months ago by git

  • Commit changed from 141adb09fe3e8f45079d706135dc071dc2e1eec7 to 1e7d2f07e3cdb7d99a0cd0502078791a47176153

Branch pushed to git repo; I updated commit sha1. New commits:

5a25fcdMerge remote-tracking branch 'trac/u/tmonteil/equality_vs_hash_for_braid_groups' into develop.6.2
1e7d2f0Remove direct hash computation that depends on the architecture.

comment:10 Changed 5 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:

3e11dbaMerge branch 'u/tmonteil/equality_vs_hash_for_braid_groups' of trac.sagemath.org:sage into u/tscrim/equality_hash_braid_groups-16059
d54f18cAdded extra doctest.

comment:11 Changed 5 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 5 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 5 months ago by tscrim

  • Status changed from needs_review to positive_review

I like this doctest better. Positive review. Thanks.

comment:14 Changed 5 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
Note: See TracTickets for help on using tickets.