category root lattice realization issue: infinite loop while trying to reflect to the positive chamber

[mshimo]

version 5.0 beta7

sage/combinat/root_system/root_lattice_realizations.py element methods to_positive_chamber, reduced_word may give infinite loops for affine root systems

R=sage.combinat.root_system.all.RootSystem(['A',1,1])
rl = R.root_lattice()
mu = rl.from_vector(vector([0,1]))
mu.to_positive_chamber()

For elements of a root lattice realization:

1. Added method reflect which reflects across a hyperplane orthogonal

to a (co)root.

2. Renamed to_positive_chamber to to_dominant_chamber, and added case checking

for affine root systems which prevents infinite looping. Root systems that are not finite and not affine are not checked.

3. Added method weyl_action which acts on a vector by a Weyl group element.
4. Added method weyl_stabilizer which returns indices of simple reflections

fixing a weight.

Apply: trac_12667_root_lattice_ms.patch

[nthiery]

Hi Mark,

What is the right sage-combinat way to handle a situation where the function input will lead to an infinite loop? Can I just assert conditions that will ensure things like that don't happen, or should I emit a more precise error? Pointing me to example code will suffice.

Sorry for my delayed answer. In the affine case, please add a test on level; something like:

     assert not self.parent().is_affine() or self.level() >= 0, "This element is not in the orbit of the fundamental chamber"

For the general Kac-Moody case: I think we can assume that a user playing with those has some non trivial background. In that case, and unless there is a cheap and easy to implement test as in the affine case, it would be perfectly fine to write in the documentation something like:

    INPUT:

    - ``self`` -- an element in the orbit of the fundamental chamber

    .. warning::

        The behavior of this method is not specified if ``self`` is
	not in the orbit of the fundamental chamber (the algorithm may
	run in an infinite loop). This never occurs for finite root
	systems. For affine Weyl groups, an element is in the orbit of
	the fundamental chamber iff it is of positive level (see
	:meth:`level`), and this is currently checked, but do not rely
	on it::

	     sage: ...

Otherwise put: as long as it is well documented, it is preferable for power users to have a feature that needs to be used with care, than no feature. Sage should be usable as a race car for those who wants one.

Cheers,

Nicolas

[aschilling]

Hi Mark,

Here are some comments. First of all, I moved your patch up in the queue since presumably you want it to go into Sage soon. Then I can do the testing on the sage-combinat queue.

• Please use "hg qrefresh -e" and add a description of the changes you made. This should

appear at the beginning of the file. The same description can then be used on the trac server once you upload it there.

• Nicolas once told me that every method should have a one-line short description. Then a more detailed description can follow. So for example in your new method "def reflection" have one line with a description

Also, for consistency in

"Reflect self across the hyperplane orthogonal to root."

should it be "Reflects ...."?

• Please use the syntax

.. warning

for the warning.

Also, there are doctest failures

sage -t "devel/sage-combinat/sage/combinat/root_system/root_lattice_realizations.py" File "/Applications/sage-5.0.beta7/devel/sage-combinat/sage/combinat/root_system/root_lattice_realizations.py", line 522:

sage: Phi.cover_relations()

Exception raised:

Traceback (most recent call last):

File "/Applications/sage-5.0.beta7/local/bin/ncadoctest.py", line 1231, in run_one_test

self.run_one_example(test, example, filename, compileflags)

File "/Applications/sage-5.0.beta7/local/bin/sagedoctest.py", line 38, in run_one_example

OrigDocTestRunner?.run_one_example(self, test, example, filename, compileflags)

File "/Applications/sage-5.0.beta7/local/bin/ncadoctest.py", line 1172, in run_one_example

compileflags, 1) in test.globs

File "<doctest main.example_16[3]>", line 1, in <module>

Phi.cover_relations()###line 522:

sage: Phi.cover_relations()

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 1198, in cover_relations

return [c for c in self.cover_relations_iterator()]

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 1213, in cover_relations_iterator

yield map(self._vertex_to_element,(u,v))

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 698, in _vertex_to_element

return self._list[vertex]

TypeError?: tuple indices must be integers, not RootSpace?_with_category.element_class

File "/Applications/sage-5.0.beta7/devel/sage-combinat/sage/combinat/root_system/root_lattice_realizations.py", line 527:

sage: Phi.cover_relations()

Exception raised:

Traceback (most recent call last):

File "/Applications/sage-5.0.beta7/local/bin/ncadoctest.py", line 1231, in run_one_test

self.run_one_example(test, example, filename, compileflags)

File "/Applications/sage-5.0.beta7/local/bin/sagedoctest.py", line 38, in run_one_example

OrigDocTestRunner?.run_one_example(self, test, example, filename, compileflags)

File "/Applications/sage-5.0.beta7/local/bin/ncadoctest.py", line 1172, in run_one_example

compileflags, 1) in test.globs

File "<doctest main.example_16[5]>", line 1, in <module>

Phi.cover_relations()###line 527:

sage: Phi.cover_relations()

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 1198, in cover_relations

return [c for c in self.cover_relations_iterator()]

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 1213, in cover_relations_iterator

yield map(self._vertex_to_element,(u,v))

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 698, in _vertex_to_element

return self._list[vertex]

TypeError?: tuple indices must be integers, not RootSpace?_with_category.element_class

File "/Applications/sage-5.0.beta7/devel/sage-combinat/sage/combinat/root_system/root_lattice_realizations.py", line 532:

sage: Phi.cover_relations()

Exception raised:

Traceback (most recent call last):

File "/Applications/sage-5.0.beta7/local/bin/ncadoctest.py", line 1231, in run_one_test

self.run_one_example(test, example, filename, compileflags)

File "/Applications/sage-5.0.beta7/local/bin/sagedoctest.py", line 38, in run_one_example

OrigDocTestRunner?.run_one_example(self, test, example, filename, compileflags)

File "/Applications/sage-5.0.beta7/local/bin/ncadoctest.py", line 1172, in run_one_example

compileflags, 1) in test.globs

File "<doctest main.example_16[7]>", line 1, in <module>

Phi.cover_relations()###line 532:

sage: Phi.cover_relations()

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 1198, in cover_relations

return [c for c in self.cover_relations_iterator()]

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 1213, in cover_relations_iterator

yield map(self._vertex_to_element,(u,v))

File "/Applications/sage-5.0.beta7/local/lib/python/site-packages/sage/combinat/posets/posets.py", line 698, in _vertex_to_element

return self._list[vertex]

TypeError?: tuple indices must be integers, not RootSpace?_with_category.element_class

1 items had failures:

3 of 9 in main.example_16

*Test Failed* 3 failures. For whitespace errors, see the file /Users/anne/.sagetmp/root_lattice_realizations_29723.py

[5.0 s]

---

The following tests failed:

sage -t "devel/sage-combinat/sage/combinat/root_system/root_lattice_realizations.py"

Total time for all tests: 5.0 seconds

---

Though these doctest failures also seem to appear without your patch applied.

Best,

Anne

[aschilling]

Ok, I found the patch that broke the above doctests and moved your patch up. The doctests look good now.

Anne

[aschilling]

Hi Mark,

I posted a quick reviewer's patch on sage-combinat. If you are satisfied, please fold it into yours and post the result on trac (details in a private e-mail).

Thanks,

Anne

[aschilling]

I checked the new version of the patch and everything looks good. Positive review.

Anne