Refine growing letters

[videlec]

The aim is to refine WordMorphism.growing_letters to differentiate the various possible behaviors of |sigma^n(letter)|. This growth is always of the form alpha^n n^beta (where alpha is a Perron number and beta an integer). Without doing any linear algebra we could differentiate

• mortal (= ultimately empty or alpha=0)
• polynomial (alpha=1)
• exponential (alpha > 1)
  The output of the method will a 3-tuple of lists (mortal, polynomial, exponential) where
• mortal : list of mortal letters
• polynomial: a list of lists where polynomial[i] is the list of letters with growth n^i.
• exponential: list of at least exponentionally growing letters

The implementation can be done iteratively by "cleaning" the morphism

• use the already existing immortal_letters to detect mortal letters and remove them
• now run an iteration to detect cycles of letters and clean the morphism by removing letters belonging to cycles (each run give polynomially growing letters of higher and higher degrees)
• once there is no cycle anymore, the remaining letters are exponentially growing

CC: @sagetrac-jlepsova @seblabbe

Component: combinatorics

Author: Sébastien Labbé, Vincent Delecroix

Branch/Commit: ce5ca81

Reviewer: Vincent Delecroix, Sébastien Labbé

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

[seblabbe]

Author: Sébastien Labbé

[seblabbe]

Commit: c625f9e

[seblabbe]

comment:1

We did this this morning during the Sage Thursday's in Bordeaux.

---

New commits:

c625f9e

32594: adding letter_growth_types method

[seblabbe]

Branch: u/slabbe/32594

[videlec]

comment:2

Tu fais du sage en dehors des sage thursdays maintenant :)

[videlec]

comment:3

The "(mortal, polynomial, exponential)" would better be inside ``.

I don't understand the nested loop. Could you explain in the documentation or in comment how and why it works?

[seblabbe]

comment:4

ok

[seblabbe]

comment:5

Replying to @videlec:

Tu fais du sage en dehors des sage thursdays maintenant :)

C'était fait pendant, mais il y a eu une panne d'internet vers 11h45, donc j'ai fait le git push après déjeuner:)

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

5b0937c	32594: adding letter_growth_types method
c649f32	32594: added comments in the code

[sagetrac-git]

Changed commit from c625f9e to c649f32

[sagetrac-git]

Changed commit from c649f32 to 11d2679

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

11d2679

32594: added some more comments about the loop invariant

[seblabbe]

comment:9

Added few more comments. Now need review.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

7dd5c27

32594: while loop -> inner while loop

[sagetrac-git]

Changed commit from 11d2679 to 7dd5c27

[sagetrac-git]

Changed commit from 7dd5c27 to a89e941

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

a89e941

32594: few more comments about m vs morphism self

[seblabbe]

comment:12

And few more sorry. Now I stop. Needs review!

[videlec]

Changed branch from u/slabbe/32594 to u/vdelecroix/32594

[videlec]

Changed commit from a89e941 to a5e4c76

[videlec]

New commits:

a5e4c76

32594: simplifications

[videlec]

comment:14

I added a commit on top of yours. I did some modifications in the code in order to avoid building many dictionaries. Actually, the whole code is pure linear algebra and could be moved to matrices.

[videlec]

comment:15

If you are ok you can set to positive review.

[seblabbe]

comment:16

There is only one issue to be fixed:

src/sage/combinat/words/morphism.py:3283:38: E701 multiple statements on one line (colon)

After that fixed, I am fine with positive review.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

ce5ca81

32594: fix multiple line statement

[sagetrac-git]

Changed commit from a5e4c76 to ce5ca81

[seblabbe]

Reviewer: Vincent Delecroix, Sébastien Labbé

[seblabbe]

Changed author from Sébastien Labbé to Sébastien Labbé, Vincent Delecroix

[vbraun]

Changed branch from u/vdelecroix/32594 to ce5ca81