is_primitive of WordMorphism is broken

[seblabbe]

Let us define the following morphism over 3 letters:

sage: substitution=WordMorphism('a->b,b->ac,c->a')

Then we get

sage: substitution.is_primitive()
False

but also

sage: (substitution^2).is_primitive()
True

---

expected behaviour:

See the description of ".is_primitive()":
Returns True if self is primitive.
A morphism ϕ is primitive if there exists an positive integer k such
that for all α∈Σ, ϕk(α) contains all the letters of Σ.

So, if a morphism is primitive, so are all its powers. And if there is
a power which is primitive, so is the morphism itself. In the example
above, both outputs should be "True".

This was reported here (via 'Report a problem'):

http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/5ed1186c229e7343?hl=en

CC: @sagetrac-abmasse

Component: combinatorics

Author: Sébastien Labbé

Reviewer: Alexandre Blondin Massé

Merged: sage-4.3.2.alpha1

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

[seblabbe]

comment:2

I just posted a patch which solves the described problem. The solution uses the following algorithm:

ALGORITHM: 
 
   Let `m` be the incidence matrix of a endomorphism on a monoid  
   of `d` letters. The endomorphism is primitive if and only if 
   there exists `k` such that `1 \leq k \leq (d-1)^2+1` and `m^k`  
   contains no zero. 

Are we sure this is true? Is there a proof of that somewhere?

[seblabbe]

Attachment: trac_8095_wordmorph_is_primitive-sl.patch.gz

tested on sage-4.3.1

[seblabbe]

comment:4

I found a reference for the above statement (Automatic sequences of Allouche and Shallit).

[sagetrac-abmasse]

Author: slabbe

[sagetrac-abmasse]

comment:5

Tested on sage-4.3.1 as well and it works.
It fixes the reported problem as well.
All tests passed when running ``sage -t morphism.py".
Positive review.

[sagetrac-abmasse]

Reviewer: abmasse

[sagetrac-mvngu]

Changed reviewer from abmasse to Alexandre Blondin Massé

[sagetrac-mvngu]

Changed author from slabbe to Sébastien Labbé

[sagetrac-mvngu]

Merged: sage-4.3.2.alpha1