implementation of the generalized associahedron as a polyhedral complex

[stumpc5]

The patch contains the implementation of the generalized associahedron, as constructed in [CFZ] Chapoton, Fomin, Zelevinsky - Polytopal realizations of the generalized associahedra, ​http://arxiv.org/abs/math/0202004.

sage: Associahedron(['A',3])
Generalized associahedron of type ['A', 3] with 14 vertices

The class inherits from Polyhedra, and uses several new methods for root spaces:

• RootLatticeRealization.index_bipartition, returns the bipartition of the indices of the Dynkin diagram vertices, if it is bipartite

• RootLatticeRealization.almost_positive_roots, returns the sorted list of positive and simple negative roots

• RootLatticeRealization.tau_plus_minus, returns two piecewise linear operators on the root space which are used to define the "tropical Coxeter element" in [CFZ]

• RootLatticeRealization.almost_positive_root_decomposition, returns the orbit decomposition of the almost positive roots under the dihedral group action of < tau_plus, tau_minus > as defined above

[stumpc5]

As many files are touched in #11187, this "depends" on it to apply properly.

[chapoton]

Apply trac_10817-generalized_associahedra-cs.patch

[chapoton]

Let us try without the dependency, which is not obviously needed.

Apply trac_10817-generalized_associahedra-cs.patch

[chapoton]

well, too bad, it does really depends on #11187

[stumpc5]

Replying to chapoton:

well, too bad, it does really depends on #11187

I removed the dependencies so we can get it done without waiting for the other patch - Thanks for looking at it!

[chapoton]

Apply trac_10817-generalized_associahedra-cs.patch

[chapoton]

A review has been done, and a reviewer patch follows soon.

[nthiery]

I just pushed the reviewer patch on the sage-combinat server; please check if you agree with it. I still want to have a last look, but this may not occur before next week (vacations here).

Cheers,

Nicolas

[nthiery]

Replying to nthiery:

I just pushed the reviewer patch on the sage-combinat server; please check if you agree with it. I still want to have a last look, but this may not occur before next week (vacations here).

Ok, I finally could do it. The patch is on the queue. If you are happy with it, you may fold the two patches, upload them here, and set a positive review on my behalf.

[stumpc5]

Thanks for the review -- you should add yourself as an author actually... .

I set a positive review on Nicolas' behalf.

Best, Christian

[nthiery]

For the record: all tests pass on 5.0 beta4, with the following patches applied:

trac_11003-folded.patch
trac_10998-categories-posets-nt.patch
trac_11118-finite_enumset_list_cache-fh.patch
trac_11250-action_coerce_doc-fh.patch
trac_11257_avoid_coercion_power_zero-nb.patch
trac_12483-family-workaround_12482-nt.patch
trac_12464-free_module_classcall-fh.patch
trac_12490-trac_role-fh.patch
trac_10670_integral_mobius_matrix_for_posets-fh.patch
trac_11382-subposet_to_vertex_speedup-fh.patch
trac_12484-free_module-monomials_cmp-nt.patch
trac_12489-freemod_eq-nt.patch
trac_10347_is_skew_symmetrizable-cs.patch
trac_12476-lattice_join_matrix_speedup-fh.patch
trac_9469-category-membership_without_arguments-nt.patch
trac_10603-union_enumset_elconstr_fix-fh.patch
trac_12528_free_module-optimize-nt.patch
trac_10817-generalized_associahedra-cs.patch
trac_10817-generalized_associahedra-review-nt.patch

Most of the above patches are either orthogonal or already merged in beta5, so I assume the test pass without them too.

[nthiery]

Replying to stumpc5:

Thanks for the review -- you should add yourself as an author actually... .

Bah, just my reviewer's job. You drove this patch through!

[jdemeyer]

There is a doctest failure on hawk (OpenSolaris? 06.2009-32):

**********************************************************************
File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-5.0.beta6/devel/sage-main/sage/combinat/root_system/associahedron.py", line 43:
    sage: sorted(Asso.Hrepresentation())
Expected:
    [An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0]
Got:
    [An inequality (0, -1) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (-1, 0) x + 1 >= 0]
**********************************************************************

[stumpc5]

Replying to jdemeyer:

There is a doctest failure on hawk (OpenSolaris? 06.2009-32):

    sage: sorted(Asso.Hrepresentation())

The buildbot doesn't find the failure, and the list has actually the same content. So the problem must be something with the cmp of inequalities.

I wouldn't know how to fix that in this patch actually.

Best, Christian

[jdemeyer]

On Cicero (Linux i386):

**********************************************************************
File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-5.0.beta6/devel/sage-main/sage/combinat/root_system/associahedron.py", line 43:
    sage: sorted(Asso.Hrepresentation())
Expected:
    [An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0]
Got:
    [An inequality (0, 1) x + 1 >= 0, An inequality (-1, 0) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0]
**********************************************************************

[stumpc5]

Replying to jdemeyer:

I updated the patch with this order in the sorted list of inequalities.

But now I see that the two machines you are using sort this list differently - in particular, we have no chance to get no failure on any of the two machines you used...

Any suggestions?

[nthiery]

Replying to stumpc5:

But now I see that the two machines you are using sort this list differently - in particular, we have no chance to get no failure on any of the two machines you used...

Any suggestions?

What about:

    sage: sorted(Asso.Hrepresentation(), key=repr)
    [An inequality (-1, 0) x + 1 >= 0, An inequality (0, -1) x + 1 >= 0, An inequality (0, 1) x + 1 >= 0, An inequality (1, 0) x + 1 >= 0, An inequality (1, 1) x + 1 >= 0]

Then the result should be sorted according to their string representation, and string comparison should be platform independent.

[stumpc5]

Replying to nthiery:

Replying to stumpc5: Then the result should be sorted according to their string representation, and string comparison should be platform independent.

Done - how can I know that string representations should be platform independent and some others aren't?

Thanks! Christian

[nthiery]

Replying to stumpc5:

Replying to nthiery:

Replying to stumpc5: Then the result should be sorted according to their string representation, and string comparison should be platform independent.

Done

Thanks! Positive review, assuming the tests pass.

how can I know that string representations should be platform independent and some others aren't?

Because:

• I am amost certain that Python compares strings lexicographically (it does for e.g. tuples; see ​http://docs.python.org/library/stdtypes.html; it's certainly specified somewhere for strings too)
• The Inequality class implements _repr_ independently of the platform
• On the other hand, this class does not implement cmp, so its behavior is unspecified. And likely to be platform dependent.

[stumpc5]

Replying to nthiery:

Thanks! Positive review, assuming the tests pass.

The buildbot somehow doesn't like the test

for root in L.almost_positive_roots():
         print 'tau({:<41}) ='.format(root), tau(root)

I guess, you added it, didn't you? On my 5.0.beta6, it passed though.

Best, Christian

[nthiery]

Replying to stumpc5:

Replying to nthiery:

Thanks! Positive review, assuming the tests pass.

The buildbot somehow doesn't like the test

for root in L.almost_positive_roots():
         print 'tau({:<41}) ='.format(root), tau(root)

I guess, you added it, didn't you? On my 5.0.beta6, it passed though.

Indeed.

Python has been upgraded to 2.7 in Sage 5.0. I guess this syntax for format was not yet supported in Python 2.6. Let's just wait for the buildbot to run on 5.0.