is_iwip has false positives

[naomiandrew]

Here are two representatives of the same (reducible) outer automorphism of F_3, where the first is a false positive for is_iwip:

import train_track as tt

phi1=tt.FreeGroupAutomorphism('x->y,y->yxZ,z->YzXYZyxZy')
phi2=tt.FreeGroupAutomorphism('x->yxZyyYzXY,y->yxZyyxZYzXY,z->Z')
inner=tt.FreeGroupAutomorphism('x->yxZyxYzXY,y->yxZyyYzXY,z->yxZyzYzXY')

phi2==inner*phi1

phi1.is_iwip(verbose=1)
phi2.is_iwip(verbose=1)

The problem seems to come from the algorithm detecting if the Nielsen path is primitive, which also gives the wrong answer:

phi1.train_track().domain().lies_in_a_free_factor('aYBZBXYB',verbose=1)

Here I think that not enough is being checked: as far as I can tell the algorithm checks if every edge is used, and then if various Whitehead graphs are connected. But even on the rose there are primitive elements with connected Whitehead graphs (they need not be particularly complex: aab is enough). They do have cut vertices, though since proper powers have the same Whitehead graph as their roots this is still insufficient for full primitivity checking.

The description of the algorithm in Kapovich's paper does have a step involving the connectivity of local Whitehead graphs. But it seems to be in a different place: it happens after the automorphism is known to be primitively atoroidal, while this implementation doesn't appear to have an earlier check for this.

[coulbois]

I am impressed: this bug is quite deeply hidden. I have to go back to the code. I hope the problem is only in the lies_in_a_free_factor().

I could reproduce the bug exactly as you described it with my Sage9.3 (Yes I know I have to update) on my Ubuntu Laptop.

Do you have any suggestion to fix that ?

Thanks.

Thierry

[coulbois]

I checked both my code and Kapovich papers. The only mistake in my code is the GraphWithInverses.lies_in_a_free_factor(). My code only check connetedness of Whitehead graphs and, as pointed out by Naomi, this is not enough.

It would be better to add a is_primitive() method in FreeGroup.

I cannot remember the correct algorithm to check primitivity of an element or to decide if it lies in a free factor.

Someone knows ?

Else I will find it in the Robinson or in my old notes...

[videlec]

I think this is coded in the stallings package of P. Weil (file `about_free_factors.py'). It refers to Silva, Weil "On an algorithm to decide whether a free group is a free factor of another", Theoretical Informatics and Applications 42 (2008) 395-414.