Refine growing letters - Githubissues

videlec commented 2 years ago

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 commented 2 years ago

Author: Sébastien Labbé

seblabbe commented 2 years ago

Commit: c625f9e

seblabbe commented 2 years ago

comment:1

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

New commits:

c625f9e 32594: adding letter_growth_types method

seblabbe commented 2 years ago

Branch: u/slabbe/32594

videlec commented 2 years ago

comment:2

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

videlec commented 2 years ago

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 commented 2 years ago

comment:4

ok

seblabbe commented 2 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from c625f9e to c649f32

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from c649f32 to 11d2679

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

11d2679 32594: added some more comments about the loop invariant

seblabbe commented 2 years ago

comment:9

Added few more comments. Now need review.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

7dd5c27 32594: while loop -> inner while loop

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 11d2679 to 7dd5c27

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from 7dd5c27 to a89e941

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

a89e941 32594: few more comments about m vs morphism self

seblabbe commented 2 years ago

comment:12

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

videlec commented 2 years ago

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

videlec commented 2 years ago

Changed commit from a89e941 to a5e4c76

videlec commented 2 years ago

New commits:

a5e4c76 32594: simplifications

videlec commented 2 years ago

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 commented 2 years ago

comment:15

If you are ok you can set to positive review.

seblabbe commented 2 years ago

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

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

ce5ca81 32594: fix multiple line statement

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 2 years ago

Changed commit from a5e4c76 to ce5ca81

seblabbe commented 2 years ago

Reviewer: Vincent Delecroix, Sébastien Labbé

seblabbe commented 2 years ago

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

vbraun commented 2 years ago

Changed branch from u/vdelecroix/32594 to ce5ca81

sagemath / sage

Refine growing letters #32594