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

[sagetrac-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: attachment: trac_12667_root_lattice_ms.patch

Depends on #6588

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: root system

Author: Mark Shimozono

Reviewer: Anne Schilling

Merged: sage-5.0.beta11

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

[sagetrac-mshimo]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
+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

[mwhansen]

Description changed:

--- 
+++ 
@@ -4,7 +4,9 @@
 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()
+mu.to_positive_chamber()}}}
+```

[mwhansen]

Description changed:

--- 
+++ 
@@ -8,5 +8,5 @@
 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()}}}
+mu.to_positive_chamber()
 ```

[nthiery]

comment:4

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

[anneschilling]

Reviewer: Anne Schilling

[anneschilling]

comment:6

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
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
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
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/.sage//tmp/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

[anneschilling]

comment:7

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

Anne

[anneschilling]

comment:8

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

[anneschilling]

Dependencies: #6588

[sagetrac-mshimo]

Description changed:

--- 
+++ 
@@ -10,3 +10,14 @@
 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.
+