train-tracks

[5e1794c3-77c0-453a-bf39-4b14c1cb833c]

We propose to implement in Sage the train-tracks package developed by Thierry Coulbois:

The main feature and the main achievement of the program is to compute train-track representative for (outer) automorphisms of free groups. phi.train track() computes a train-track representative for the (outer) automorphism phi. This train-track can be either an absolute train-track or a relative train-track. The celebrated theorem of Bestvina and Feighn assures that if phi is fully irreducible (iwip), then there exists an absolute train-track representing phi. The train-track(relative=False) method will terminate with either an absolute train-track or with a topological representative with a reduction: an invariant strict subgraph with non-trivial fundamental group. One more feature of train-tracks (absolute or relative) is to lower the number of Nielsen paths. Setting the stable=True option will return a train-track with at most one indivisible Nielsen path (per exponential stratum if it is a relative train-track).

See also:

• https://github.com/coulbois/sage-train-track
• https://www.i2m.univ-amu.fr/perso/thierry.coulbois/train-track/

• 31223: Add sage-train-track as an optional package

CC: @tscrim @sagetrac-tmonteil @videlec

Component: group theory

Keywords: free-group automorphism

Author: Dominique Benielli, Thierry Coulbois

Branch/Commit: public/train-track @ dcc540c

Issue created by migration from https://trac.sagemath.org/ticket/20154

[5e1794c3-77c0-453a-bf39-4b14c1cb833c]

comment:41

ok - use the it.next method, but instead next(it) ok - print(something)

in commit 020d0a2 python3 compatibility

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

737c4e5

doc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 020d0a2 to 737c4e5

[fchapoton]

comment:43

there remains two lines with old-style python2 print (in the doctests) see red plugin in latest patchbot report (which also gives two false positives that can be ignored)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

25934b5

last print phython3 style

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 737c4e5 to 25934b5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

7db874b

constructions doc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 25934b5 to 7db874b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

0e0d7da

still print

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7db874b to 0e0d7da

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 0e0d7da to 2d36957

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

2d36957

construction

[fchapoton]

comment:49

doc does not build, and there remains old-style prints, see my patchbot's latest report

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c390257	still print
496bd4a	doc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 2d36957 to 496bd4a

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c3aae43

doc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 496bd4a to c3aae43

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

45d380b

doc

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c3aae43 to 45d380b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 45d380b to af88066

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

af88066

improve tests coverage

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d35c1d2

tests coverage

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from af88066 to d35c1d2

[videlec]

comment:55

Hello Dominique, Thierry,

There are two current problems (see the failing doctests of patchbot):

• the comparison between elements of the free group changed. Before we had the following order on generators x_0^-1, x_0, x_1^-1, x_1, ... But with your branch, because you use direct comparison on the Tietze generators, it became x_n^-1, x_{n-1}^-1, ..., x_0^-1, x_0, x_1, ..., I think the former was preferable. What do you think?

• there are a lot of failure related to the free_group.py being moved. You just need to change the occurrence of sage.groups.free_group by sage.groups.free_groups.free_group everywhere.

[d53c3c1f-61cc-4040-be1f-8ec5f87eb3a8]

comment:56

No problem for the order of the generators and their inverses. However the reason for rewriting the _cmp_ method was that I want the neutral element to be smaller than all other elements of the free group. Which was not the case with the previous version.

I do not know how the previous order was implemented (deep inside GAP ?)

[tscrim]

comment:57

In the current Sage, it calls the comparison between the (lib)GAP objects; so my understanding is GAP handles the comparison.

[5e1794c3-77c0-453a-bf39-4b14c1cb833c]

comment:58

Hello All,

My last commits do not appear in the ticket comments:

• I did my best to remove failures that appear in the patchchboot log (the make worked on my computer strange behavior?), and improve tests coverage, that seems to be a blocked point.

• For the order generators in my sens the remark from Vincent was about the previous version of free_group but the traintrack version because a lot of order changed with the use of free group generators of Gap. But maybe, I confuse and the re-writting of _cmp method also change the orther.

Best regards Dominique

---

New commits:

f060b61	tests failures correction
7a7da77	tests failuures

[5e1794c3-77c0-453a-bf39-4b14c1cb833c]

Changed commit from d35c1d2 to 7a7da77

[videlec]

comment:59

Replying to @sagetrac-coulbois:

No problem for the order of the generators and their inverses. However the reason for rewriting the _cmp_ method was that I want the neutral element to be smaller than all other elements of the free group. Which was not the case with the previous version.

It was...

sage: F = FreeGroup(['a','b'])
sage: a,b = F.gens()
sage: l = [a,b,~a,~b,a*b,~a*b,F.one()]
sage: sorted(l)
[1, a^-1, a, b^-1, b, a^-1*b, a*b]
sage: F.one() < a
True
sage: a < F.one()
False

What is wrong with the above? It is first sorted by length and then (almost) lexicographically. This is indeed different from order on lists which is straight lexicographic.

I do not know how the previous order was implemented (deep inside GAP ?)

It indeed used the gap comparison which seems reasonable to me.

[5e1794c3-77c0-453a-bf39-4b14c1cb833c]

comment:60

The ticket test failled status comes from a a problem with pathboot see http://ask.sagemath.org/question/33899/doc-test-fail-in-patchboot-and-not-on-my-computer/

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c9da8b0

Merge branch 'public/train-track' in 7.3.b9

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 7a7da77 to c9da8b0

[fchapoton]

comment:62

coverage is not yet 100%

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c9da8b0 to 857ff2c

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

2c332df	test coverage
857ff2c	Merge branch 'public/train-track' of git://trac.sagemath.org/sage into public/train-track

[5e1794c3-77c0-453a-bf39-4b14c1cb833c]

comment:64

The patchboot is now on test passed (TestsPassed 7.3.rc0 Ubuntu/14.04/x86_64/3.13.0-92-generic/librae), please review our work on train track for its intergration in sage

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

8f9c87c

try foreign latex failure

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 857ff2c to 8f9c87c

[tscrim]

comment:66

I do still plan on reviewing this, but I need some things to settle down first before I can do a large-scale code review.

[videlec]

comment:67

what about [comment:59]? I see no need to change _cmp_.

[videlec]

comment:68

reference needed is not a valid reference ;-)

[videlec]

comment:69

In the documentation of almost all examples of automorphism the information is duplicated as in

This is a pseudo-Anosov mapping class of the 5-punctured
sphere. Thus this is not an iwip. However, its representative
on the rose in train-track.

OUTPUT:

an Automorphism of F_4 given in [BH] see also [Kapovich].
This is a pseudo-Anosov mapping class of the 5-punctured     <-- exact copy!
sphere. Thus this is not an iwip. However, its representative
on the rose in train-track.

[5e1794c3-77c0-453a-bf39-4b14c1cb833c]

comment:70

Replying to @videlec:

what about [comment:59]? I see no need to change _cmp_.

the rewriting of _cmp_ order leads to some modifications outside free_group for tests, but I did changes, so I think is ok unless if there are some GAP reasons.

[videlec]

comment:71

Replying to @sagetrac-dbenielli:

Replying to @videlec:

what about [comment:59]? I see no need to change _cmp_.

the rewriting of _cmp_ order leads to some modifications outside free_group for tests, but I did changes, so I think is ok unless if there are some GAP reasons.

This is precisely my question: why is _cmp_ changed at all?

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 8f9c87c to a13b02d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a13b02d

remove _cmp

[videlec]

comment:73

Hello,

Commenting is not removing. More importantly, you have to revert all the changes you have done in previous commits related to this change of comparison order.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a13b02d to cd64177

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cd64177

remove __cmp and tests induced

[d53c3c1f-61cc-4040-be1f-8ec5f87eb3a8]

comment:75

We revert to the _cmp_ method of FreeGroupElement to that of the GAP-wrapper (meaning that we removed the _cmp_ method from the free_groups/free_group.py file). Warning: this comparison is undocumented and it seems that it first compares the length of reduced words and then sort words of equal length in alphabetic order. In our train-track package it is mainly used while running the Nielsen-Whitehead algorithm to invert automorphisms (see FreeGroupMorphism.invert()). The order wrapped from GAP is satisfactory in this purpose.

We revert the doc-tests (that we had previously modified) from sage/groups/finitely_presented.py which use this order.

All doc-tests pass.

We now wait for other things to improve according to reviewers.