fan isomorphism check

[vbraun]

This patch implements testing for isomorphism (equivalence up to GL(n,ZZ) rotation) of fans

  sage: m1 = matrix([(1, 0), (0, -5), (-3, 4)])
  sage: m2 = matrix([(3, 0), (1, 0), (-2, 1)])
  sage: m1.elementary_divisors() == m2.elementary_divisors() == [1,1,0]
  True
  sage: fan1 = Fan([Cone([m1*vector([23, 14]), m1*vector([   3,100])]), 
  ...               Cone([m1*vector([-1,-14]), m1*vector([-100, -5])])])
  sage: fan2 = Fan([Cone([m2*vector([23, 14]), m2*vector([   3,100])]), 
  ...               Cone([m2*vector([-1,-14]), m2*vector([-100, -5])])])
  sage: fan1.is_isomorphic(fan2)
  True
  sage: fan1.isomorphism(fan2)
  Fan morphism defined by the matrix
  [18  1 -5]
  [ 4  0 -1]
  [ 5  0 -1]
  Domain fan: Rational polyhedral fan in 3-d lattice N
  Codomain fan: Rational polyhedral fan in 3-d lattice N

This is implemented by first computing the isomorphisms of auxiliary labelled graphs, and then trying to lift those to actual fan morphisms.

Apply:

• attachment: trac_13189_Hirzebruch_Jung_continued_fraction.patch
• attachment: trac_13189_virtual_rays.patch
• attachment: trac_13189_fan_isomorphism.patch
• attachment: trac_13189_cone_isomorphism.patch
• attachment: trac_13189_reviewer.patch

Depends on #12544

CC: @novoselt

Component: algebraic geometry

Keywords: toric

Author: Volker Braun

Reviewer: Andrey Novoseltsev

Merged: sage-5.3.beta2

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

[vbraun]

Description changed:

--- 
+++ 
@@ -21,3 +21,7 @@

This is implemented by first computing the isomorphisms of auxiliary labelled graphs, and then trying to lift those to actual fan morphisms.

+Apply: + attachment: trac_13189_Hirzebruch_Jung_continued_fraction.patch + attachment: trac_13189_virtual_rays.patch +* attachment: trac_13189_fan_isomorphism.patch

[vbraun]

Attachment: trac_13189_Hirzebruch_Jung_continued_fraction.patch.gz

Updated patch

[vbraun]

Updated patch

[vbraun]

Description changed:

--- 
+++ 
@@ -25,3 +25,4 @@
 * [attachment: trac_13189_Hirzebruch_Jung_continued_fraction.patch](https://github.com/sagemath/sage-prod/files/10655872/trac_13189_Hirzebruch_Jung_continued_fraction.patch.gz)
 * [attachment: trac_13189_virtual_rays.patch](https://github.com/sagemath/sage-prod/files/10655873/trac_13189_virtual_rays.patch.gz)
 * [attachment: trac_13189_fan_isomorphism.patch](https://github.com/sagemath/sage-prod/files/10655874/trac_13189_fan_isomorphism.patch.gz)
+* [attachment: trac_13189_cone_isomorphism.patch](https://github.com/sagemath/sage-prod/files/10655876/trac_13189_cone_isomorphism.patch.gz)

[vbraun]

comment:2

Attachment: trac_13189_virtual_rays.patch.gz

[vbraun]

Updated patch

[vbraun]

comment:3

Attachment: trac_13189_fan_isomorphism.patch.gz

Computing the graph automorphism group goes through GAP, which is slow. The updated patch uses a special version of the isomorphism check for 2-d fans which avoids this.

[novoselt]

comment:4

I thought Robert Miller wrote a very fast graph automorphism group code for Sage - am I confusing it with something else?

[vbraun]

comment:5

There is very nice code to compute one particular graph isomorphism, but I want to iterate over all graph isomorphisms. I'm doing this by combining the chose iso with the automorphisms of one of the graphs. But enumerating the automorphism group is using GAP, presumably you can gain more through group theory than what you can gain by making the graph theory fast.

[novoselt]

Reviewer: Andrey Novoseltsev

[novoselt]

Dependencies: #12544

[novoselt]

comment:7

Glanced through, spotted a few typos that I'll fix in the reviewer patch.

What do you mean by the following change of output description??

By default, ``True`` if ``self`` and ``other`` are in the same
`GL(n, \ZZ)`-orbit, ``False`` otherwise.

Do you mind if I also switch computation of the virtual rays to the fan constructor and allow user to specify them? It is convenient e.g. when considering an affine toric variety corresponding to a face of another cone, or a subfanfan with similar structure. Then coordinates on the smaller variety can match the bigger ones.

[novoselt]

comment:8

Got one error testing cone.py:

    Traceback (most recent call last):
      File "/home/novoselt/sage-5.2.beta0/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/home/novoselt/sage-5.2.beta0/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/home/novoselt/sage-5.2.beta0/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_26[13]>", line 9, in <module>
        frac = Hirzebruch_Jung_continued_fraction_list(k/d)
      File "/home/novoselt/sage-5.2.beta0/local/lib/python/site-packages/sage/rings/arith.py", line 4193, in Hirzebruch_Jung_continued_fraction_list
        if not sage.rings.rational.is_Rational(x):
    AttributeError: 'module' object has no attribute 'is_Rational'

The new module also has to be included into documentation, I think. Is there actually a particular reason why it is not just in fan.py?

[vbraun]

comment:9

Replying to @novoselt:

What do you mean by the following change of output description??

By default, ``True`` if ``self`` and ``other`` are in the same
`GL(n, \ZZ)`-orbit, ``False`` otherwise.

I'm trying to say that it returns whether the two fans are equivalent up to a GL(n,ZZ) basis change. Apparently not comprehensible enough ;-)

Do you mind if I also switch computation of the virtual rays to the fan constructor and allow user to specify them?

If you want to implement that, go for it.

[vbraun]

comment:10

Replying to @novoselt:

The new module also has to be included into documentation, I think. Is there actually a particular reason why it is not just in fan.py?

The fan_isomorphism.py file is just a way to prevent fan.py from getting too large. The relevant user-visible documentation is in fan.py, so I don't think we should include fan_isomorphism.py in the developer guide.

[novoselt]

Description changed:

--- 
+++ 
@@ -26,3 +26,4 @@
 * [attachment: trac_13189_virtual_rays.patch](https://github.com/sagemath/sage-prod/files/10655873/trac_13189_virtual_rays.patch.gz)
 * [attachment: trac_13189_fan_isomorphism.patch](https://github.com/sagemath/sage-prod/files/10655874/trac_13189_fan_isomorphism.patch.gz)
 * [attachment: trac_13189_cone_isomorphism.patch](https://github.com/sagemath/sage-prod/files/10655876/trac_13189_cone_isomorphism.patch.gz)
+* [attachment: trac_13189_reviewer.patch](https://github.com/sagemath/sage-prod/files/10655875/trac_13189_reviewer.patch.gz)

[novoselt]

comment:11

Tests pass now. The first patch is OK modulo changes, going through others...

[novoselt]

Attachment: trac_13189_reviewer.patch.gz

[novoselt]

comment:12

OK, positive review to Volker's patches modulo reviewer's one, which needs review now.

Changes:

• move virtual_rays method to fans only and allow specifying them during fan construction;
• allow addition of point collections, which results in some simplification of code and examples;
• a bunch of clarification/typo fixes in the documentation.

Also, am I right that with automatically chosen virtual rays the choice cannot affect the isomorphism of cones?

[novoselt]

Changed keywords from none to toric

[novoselt]

comment:13

For the record: I have removed trailing whitespaces on new lines in the reviewer patch, so I don't think that patchbot should complain. As far as I know, ticket numbers are automatically added, so it should not complain either. And all tests pass, patchbot errors are not related.

[vbraun]

Added commit message

[vbraun]

comment:14

Attachment: trac_13189_cone_isomorphism.patch.gz

I forgot the commit message in trac_13189_cone_isomorphism.patch, no actual code changes.

The reviewer patch looks good to me.

The virtual ray choice doesn't change whether or not there is a isomorphism of two cones / two fans (barring any bugs), but the matrix entries of the lattice map of course differ.

[jdemeyer]

Merged: sage-5.3.beta2