is_primitive of WordMorphism is broken

[slabbe]

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

[slabbe]

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?

[slabbe]

tested on sage-4.3.1

[slabbe]

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

[abmasse]

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.