q-numbers coutings flags stable under a nilpotent endomorphism

[xcaruso]

Here is a small patch implementing the function q_jordan which computes the number of complete flags in F_q^n stable under a nilpotent linear endomorphism given by its Jordan type.

This function is used in ticket #13215.

Apply attachment: trac_13640_qjordan-4.patch

Component: combinatorics

Keywords: q-numbers

Author: Xavier Caruso

Reviewer: Frédéric Chapoton

Merged: sage-5.5.beta2

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

[xcaruso]

Author: caruso

[fchapoton]

Work Issues: doctest, cached_function

[fchapoton]

comment:3

• it does not look good to use a global variable dict_jordan

• You should instead use the decorator @cached_function to cache the results of a procedure.

• every procedure should be doctested.

• do you really need two procedures to do that ?

[xcaruso]

comment:4

Replying to @fchapoton:

• it does not look good to use a global variable dict_jordan
• You should instead use the decorator @cached_function to cache the results of a procedure.
• every procedure should be doctested.
• do you really need two procedures to do that ?

The main problem is that lists are not hashable. Therefore a cached function can't take a list as an argument and, consequently, I can't use the decorator @cached_function to cache the result of q_jordan (at least without changing the prototype of this function).
Moreover, working with just one function would imply to check the shape of the inputs at each recursive call (which is of course useless and may cost a lot).

I propose another implementation (using @cached_function and a nested function) in trac_13640_qjordan-2.patch. Please tell me whether it's better or not according to you.

[fchapoton]

comment:5

Thinking again about this, it now seems to me that q_jordan should be a method of the class Partitions. This is really the job of a partition constructor to check that something is a partition.

Maybe this would also solve the hash problem ?

[xcaruso]

comment:6

Ok. I attach a third implementation where q_jordan is a method of Partition. It works but it's quite slow. (I suspect a problem with @cached_method, but I'm not sure.)

[nthiery]

comment:7

Replying to @fchapoton:

Thinking again about this, it now seems to me that q_jordan should be a method of the class Partitions. This is really the job of a partition constructor to check that something is a partition.
Maybe this would also solve the hash problem ?

Sorry I did not comment earlier; the network at the airport was crappy. It would certainly be natural for the input to q_jordan to be a partition, and it should indeed fix the problem.

That being said, this does not necessarily imply that q_jordan should be a method of partitions. It might be more natural to put instead q_jordan with the other q-analogues, as a function taking a partition as input.

I let you judge which option is best.

Cheers,
Nicolas

[nthiery]

comment:8

Replying to @xcaruso:

Ok. I attach a third implementation where q_jordan is a method of Partition. It works but it's quite slow. (I suspect a problem with @cached_method, but I'm not sure.)

Did you run it with %prun? Among other things, it will tell you how many times the method is called, from which you can check whether the cache works.

Ah, in this situation, you probably want to use @cached_in_parent. Otherwise, the result for p.q_jordan() is cached in p. So if you recreate an identical partition as p2, p2.q_jordan won't see the cache in p.

Cheers,
Nicolas

[fchapoton]

comment:9

apply trac_13640_qjordan-4.patch

ok, here is a new variant. Still slow, I am afraid.

[fchapoton]

comment:10

apply trac_13640_qjordan-4.patch

here is a new one, thanks to Nicolas comments : with cached_in_parent_method

[xcaruso]

comment:12

Replying to @nthiery:

That being said, this does not necessarily imply that q_jordan should be a method of partitions. It might be more natural to put instead q_jordan with the other q-analogues, as a function taking a partition as input.

I let you judge which option is best.

Well, I prefer this. Therefore I propose another new patch with the function q_jordan in q_analogues but taking a Parition as input. (And note that @cached_function works well with this solution.)

[nthiery]

comment:13

Replying to @xcaruso:

Well, I prefer this. Therefore I propose another new patch with the function q_jordan in q_analogues but taking a Parition as input.

Sounds good to me.

(And note that @cached_function works well with this solution.)

Yup.

[fchapoton]

comment:14

Attachment: trac_13640_qjordan-4.patch.gz

apply trac_13640_qjordan-4.patch

here is a new patch, not touching partition.py at all

this seems ok to me

let us wait for the green light

[fchapoton]

Reviewer: Frédéric Chapoton

[fchapoton]

comment:15

ok, positive review

[fchapoton]

Changed author from caruso to Xavier Caruso

[jdemeyer]

Changed work issues from doctest, cached_function to none

[jdemeyer]

comment:16

I assume the positive review implies that the work issues have been solved?

[fchapoton]

comment:17

Yes, indeed. I should have removed them, sorry.

[jdemeyer]

Merged: sage-5.5.beta2