Opened 12 years ago

Closed 12 years ago

is_primitive of WordMorphism is broken

Reported by: Owned by: slabbe slabbe major sage-4.3.2 combinatorics abmasse sage-4.3.2.alpha1 Sébastien Labbé Alexandre Blondin Massé N/A

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'):

comment:1 Changed 12 years ago by slabbe

• Description modified (diff)

comment:2 Changed 12 years ago by slabbe

• Cc abmasse added; slabbe removed
• Status changed from new to needs_review

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?

comment:3 Changed 12 years ago by slabbe

• Status changed from needs_review to needs_work

Changed 12 years ago by slabbe

tested on sage-4.3.1

comment:4 Changed 12 years ago by slabbe

• Status changed from needs_work to needs_review

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

comment:5 Changed 12 years ago by abmasse

• Authors set to slabbe
• Reviewers set to abmasse
• Status changed from needs_review to positive_review

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.

comment:6 Changed 12 years ago by mvngu

• Authors changed from slabbe to Sébastien Labbé
• Merged in set to sage-4.3.2.alpha1
• Resolution set to fixed
• Reviewers changed from abmasse to Alexandre Blondin Massé
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.