Opened 6 years ago

Closed 6 years ago

#12667 closed defect (fixed)

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

Reported by: mshimo Owned by: sage-combinat
Priority: major Milestone: sage-5.0
Component: combinatorics Keywords: root system
Cc: sage-combinat Merged in: sage-5.0.beta11
Authors: Mark Shimozono Reviewers: Anne Schilling
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #6588 Stopgaps:

Description (last modified by jdemeyer)

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.

  1. 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.

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

fixing a weight.

Apply: trac_12667_root_lattice_ms.patch

Attachments (1)

trac_12667_root_lattice_ms.patch (13.5 KB) - added by mshimo 6 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 6 years ago by mshimo

  • Description modified (diff)

comment:2 Changed 6 years ago by mhansen

  • Description modified (diff)

comment:3 Changed 6 years ago by mhansen

  • Description modified (diff)

comment:4 Changed 6 years ago by 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

comment:5 follow-up: Changed 6 years ago by aschilling

  • Cc sage-combinat added
  • Reviewers set to Anne Schilling

comment:6 in reply to: ↑ 5 ; follow-up: Changed 6 years ago by 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

comment:7 in reply to: ↑ 6 ; follow-up: Changed 6 years ago by aschilling

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

Anne

comment:8 in reply to: ↑ 7 Changed 6 years ago by aschilling

  • Dependencies set to #6588

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

comment:9 follow-up: Changed 6 years ago by mshimo

  • Description modified (diff)

Changed 6 years ago by mshimo

comment:10 in reply to: ↑ 9 Changed 6 years ago by aschilling

  • Description modified (diff)
  • Status changed from new to needs_review

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

Anne

comment:11 Changed 6 years ago by aschilling

  • Status changed from needs_review to positive_review

comment:12 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:13 Changed 6 years ago by jdemeyer

  • Merged in set to sage-5.0.beta11
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.