implement the shard intersection order on permutations

[chapoton]

This is a poset (and even a lattice) introduced by N. Reading in 2011.

It has nice properties, similar to that of noncrossing partitions.

Let's have it in sage.

[chapoton]

New commits:

​5d0cf22

trac #18345 implement the shard intersection order of type A

[darij]

You might have forgotten to git-add the main file?

[git]

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

​c8d9000

trac #18347 main file was forgotten

[chapoton]

oops, indeed, I was a bit too quick

Do you think that descending_runs should be integrated into runs ?

[darij]

I don't know -- this seems to be a matter of taste.

[vdelecroix]

Hello,

1. In decreasing_runs why are you creating a list to return a tuple? You would better use

   return tuple(tuple([n + 1 - i for i in r]) for r in s_bar.runs())
   

2. What is the point of the cached_function on shard_preorder_graph? As far as I understand the information is only temporarily used to construct the poset. The poset constructor basically makes comparison between all pairs. So you are storing information that will never be used beyond constructing the poset.

• proposition 1: implement better the data to initialize the poset from
• (ugly) proposition 2: clear the cache when you are done

  Sn = [s.decreasing_runs() for s in Permutations(n)]
  P = Poset([Sn, shard_compares], cover_relations=False)
  shard_preorder_graph.clear_cache()
  return P
  

3. This

   dico1 = {}
   # conversion: integer -> index of run in r1
   for i, bloc in enumerate(r1):
       for j in bloc:
           dico1[j] = i
   

   can be

   dico1 = {j:i for i,bloc in enumerate(r1) for j in bloc}
   

Vincent

[git]

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

​e32ecc3

trac #18347 some of the reviewer's minor comments

[chapoton]

Thanks for the comments. I have corrected the two minor ones.

About the caching: indeed, this is used only in the poset, but used many times.

It is not clear to me how to avoid that. One could precompute in the poset method all these digraphs, and keep them in a list or a dictionary, and make the shard_compares method an internal one. I am not convinced that this would make things more clear.

[vdelecroix]

Replying to chapoton:

Thanks for the comments. I have corrected the two minor ones.

About the caching: indeed, this is used only in the poset, but used many times.

It is currently not used in the poset, only during its construction! Just have a look at the ugly poset code. It is not lazy at all.

4. runs and decreasing_runs should return the same data. It is currently list for one of them and tuple for the other.

5. Why did you wrote the following comment in shard_compares?

   # We assume that r1 has less runs than r0
   

6. The function shard_preorder_graph only depends on the interval not on the runs themselves. So you are storing too much in the cache of this function. Make the input a tuple of pairs

   sage: s = Permutation([2,8,3,9,6,4,5,1,7])
   sage: runs = s.decreasing_runs()
   sage: shard_preorder_graph(runs) == \
   ....:    shard_preorder_graph(tuple((r[0],r[-1]) for r in runs))
   True
   

   And you should really think moving it somewhere else as this has nothing to do with permutations. This is just a comparability graph given by the inclusion order on intervals. Isn't it?

Vincent

[vdelecroix]

Replying to vdelecroix:

Replying to chapoton:

And you should really think moving it somewhere else as this has nothing to do with permutations. This is just a comparability graph given by the inclusion order on intervals. Isn't it?

This is not quite true, sorry. You are building a comparability graph that also does depend on the order of the input. Not only on the intervals themselves...

Vincent

[git]

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

​88b08d5

trac #18347 more reviewer comments, still not the main one

[chapoton]

Hello,

yes, this is a rather subtle order, I think. It is indeed closely related to noncrossing partitions and to the weak order, but not in obvious ways. For example, the Mobius number is the number of connected partitions.

Concerning 4: I have added an option to specify the output of decreasing runs. Should I do the same for runs ?

Concerning 5: I have added this as a simple necessary condition

concerning 6: I have made shard_preorder_graph input a tuple of pairs

[vdelecroix]

Why not making it a poset on permutations?

Replying to chapoton:

Hello,

yes, this is a rather subtle order, I think. It is indeed closely related to noncrossing partitions and to the weak order, but not in obvious ways. For example, the Mobius number is the number of connected partitions.

Concerning 4: I have added an option to specify the output of decreasing runs. Should I do the same for runs ?

I think so.

Concerning 5: I have added this as a simple necessary condition

concerning 6: I have made shard_preorder_graph input a tuple of pairs

Nice.

I uploaded a branch at public/18347 in which instead of storing every graph in an external function I created a new class for ShardPosetElement. It does some precomputation. It is much cleaner. It is just a toy implementation to let you see. Your previous shard_compares is now ShardPosetElement.__le__.

Beyond these technicalities:

• you must put more definitions (about the order, etc)
• you should put more relevant doctest!

          sage: P = posets.ShardPoset(4); P
          Finite poset containing 24 elements
          sage: len(P.maximal_chains())
          34
          sage: P.is_selfdual()
          False
  

  is clearly not enough!

Vincent

[git]

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

​c57e836	Create a ShardPosetElement
​79d2e2b	Merge branch 'public/18347' into 6.7.b4
​d3375c0	trac #18347 as_tuple option for runs
​f250108	trac #18347 ok for the ShardPosetElement class
​70cf5e8	trac #18347 more serious doctesting

[git]

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

​db7c51a

trac #18347 more explanations in the doc

[chapoton]

I have added some explanations. Enough ?

[vdelecroix]

Hello,

What does connected_parts is doing in the git branch?

You should work harder on ShardPosetElement:

1. it would be better if it inherits from tuple (i.e. remove the p attribute and add tuple.__init__(self, p) in the constructor). Then remove the __hash__ and the __repr__ (they are already fine in tuple)

2. Implement the various operators __le__, __lt__, __gt__, __ge__ and check that it is coherent (this should be ok for __eq__ and __ne__ inherited from tuple)

3. Moreover, in __le__ you can not assume that self and other are of the same type. You should start the method with something like:

   if type(self) is not type(other) or len(self) != len(other):
       raise TypeError("these are not comparable")
   

4. Do you want to keep all attributes of ShardPosetElement public as they are?

Vincent

[git]

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

​d82ebd8	trac #18347 inherit from tuple
​878ed3a	trac #18347 remove connected_parts

[chapoton]

Hello

What does connected_parts is doing in the git branch?

Well, I removed it. Could go in another ticket maybe.

1. it would be better if it inherits from tuple (i.e. remove the p attribute and add tuple.__init__(self, p) in the constructor). Then remove the __hash__ and the __repr__ (they are already fine in tuple)

Done

2. Implement the various operators __le__, __lt__, __gt__, __ge__ and check that it is coherent (this should be ok for __eq__ and __ne__ inherited from tuple)

Is this really necessary ? This class is just there to help build the poset, there is no way it will be ever used for something else, I think.

3. Moreover, in __le__ you can not assume that self and other are of the same type. You should start the method with something like:

   if type(self) is not type(other) or len(self) != len(other):
       raise TypeError("these are not comparable")
   

Done

4. Do you want to keep all attributes of ShardPosetElement public as they are?

Once again, this class will probably not be very much used. So I do not see the point to hide things.

My motivation for this ticket was to have the poset, which is the main interesting thing here.

Thanks for your comments, by the way.

Frederic

[vdelecroix]

Hi,

Replying to chapoton:

I mostly agree with you for 2. and 4. But if you do not care about the elements, then the poset should be abstract on integers: i.e. just store a matrix of relations and send it to Poset. You do not want to know which permutation corresponds to which point in this poset?

Vincent

[chapoton]

Well. I did implement this just to compute the number of maximal chains and the mobius numbers. So only the "abstract" poset was needed. But of course, this is more useful to other people if the vertices of the poset are more or less labelled by permutations.

I do not think nevertheless that it is necessary to have the elements be permutations.

So I am happy with the current state of things..

[vdelecroix]

Replying to chapoton:

Well. I did implement this just to compute the number of maximal chains and the mobius numbers. So only the "abstract" poset was needed. But of course, this is more useful to other people if the vertices of the poset are more or less labelled by permutations.

I do not think nevertheless that it is necessary to have the elements be permutations.

So I am happy with the current state of things..

I see. Could you mention somewhere (probably in the docstring of ShardPosetElement and ShardPoset) that the elements are not permutation (for computational reasons). But hopefully they are easily recovered:

sage: P = posets.ShardPoset(4)
sage: mins = P.minimal_elements()[0]
sage: p = Permutation(mins)
[2, 3, 4, 1]
sage: p.decreasing_runs()
[[2], [3], [4, 1]]

(or a more relevant example)

Vincent

[git]

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

​707450f	Merge branch 'u/chapoton/18347' into 6.7.rc0
​98f5642	trac #18347 a little more doc about conversion to permutations

[chapoton]

ok, back to needs review. I have added some doc about back and forth conversion to permutations.

[vdelecroix]

Why did you put the INPUT block one kilometer away in Permutation.runs?!

[git]

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

​854de65

trac #18247 bad formatting

[chapoton]

ping ?

[vdelecroix]

pong!

[novoselt]

Why was a new class derived from tuple rather then something inheriting from SageObject??? It now triggers a warning included in doctest by #20667

[vdelecroix]

Inheriting from tuple is forbidden?

More interesting: what is the warning that was not here before?

[novoselt]

Nothing is forbidden, but ​http://doc.sagemath.org/html/en/developer/coding_in_python.html?highlight=sageobject and the result is ​http://git.sagemath.org/sage.git/diff/src/sage/combinat/shard_order.py?id=ed746286af38545c69edfc77c3a9f1cfde4665fd&id2=d5646a4e1a2c6f0575ca90b02085417b676e34dd

[vdelecroix]

The problem is that this error will not be solved by inheriting from SageObject since we need to initialize the content of the tuple... The inheritance from tuple is here for speed (the methods use __hash__ and __eq__).

Does the same warning show up with the following?

sage: class A(tuple):
....:    def __init__(self, a):
....:        tuple.__init__(a)
sage: a = A([1,2,3])

It works without any warning in IPython console...