Opened 8 years ago

Closed 8 years ago

#8095 closed defect (fixed)

is_primitive of WordMorphism is broken

Reported by: slabbe Owned by: slabbe
Priority: major Milestone: sage-4.3.2
Component: combinatorics Keywords:
Cc: abmasse Merged in: sage-4.3.2.alpha1
Authors: Sébastien Labbé Reviewers: Alexandre Blondin Massé
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by 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

Attachments (1)

trac_8095_wordmorph_is_primitive-sl.patch (2.5 KB) - added by slabbe 8 years ago.
tested on sage-4.3.1

Download all attachments as: .zip

Change History (7)

comment:1 Changed 8 years ago by slabbe

  • Description modified (diff)

comment:2 Changed 8 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 8 years ago by slabbe

  • Status changed from needs_review to needs_work

Changed 8 years ago by slabbe

tested on sage-4.3.1

comment:4 Changed 8 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 8 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 8 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.