Spec and patches for singular affine toric varieties / algebraic schemes

[vbraun]

This patch implements

• the Spec of affine toric varieties.
• patches for algebraic schemes with singular ambient toric varieties

In particular, Sage can now compute the dimension and smoothness for algebraic subschemes of singular toric varieties as well.

This uses both the Hilbert basis for cones and the algebraic schemes, and, therefore, depends on

• #10525: move algebraic subschemes of toric varieties to their rightful places
• #9918: triangulate point configurations
• #10023: Compute Hilbert basis of cone
• #10529: dimension() and is_smooth() for algebraic subschemes of toric varieties

Apply

1. trac_10540_toric_ideals.patch
2. trac_10540_Spec_of_affine_toric_variety.patch

[vbraun]

For the patch bot:

Depends on #9918, #10023, #10525, #10529

[vbraun]

My first version was a bit naive with the toric ideals. The updated patch implements the Hosten&Sturmfels algorithm to find a finite generating set of toric ideals.

[vbraun]

One more bug fixed. Also, the syntax is now much more sensible, in particular ToricIdeal is actually an ideal..

[vbraun]

Given the issue #10708 where the ideal dimension is completely off for some term orders, I find it prudent to convert the ideal to the standard reverse-degree lex order. The updated patch does precisely this.

[novoselt]

From PEP8: "Method definitions inside a class are separated by a single blank line." While this ticket inserts a bunch of second blank lines ;-)

[vbraun]

From PEP8: "A Foolish Consistency is the Hobgoblin of Little Minds" :-)

I changed to single blank lines in algebraic_schemes.py. Though I really find double blank lines in method def's improve readability especially if there are very long docstrings which themselves contain single blank lines.

[novoselt]

Comments/questions on the first patch (toric ideals):

1. The default names of variables are not described in the class constructor.
2. Perhaps, as an alternative to specifying names, it should be possible to specify the ring in which the ideal has to be constructed?
3. Out of curiosity: are there any reasons for using QQ as the default ring and not ZZ?
4. I liked the module documentation with many examples of different complexity and comments on them. Perhaps it is worth mentioning in the ideal constructor docstring that there is this extensive tutorial.

[vbraun]

I've added a possibility to specify the polynomial ring directly and documentation.

As for the base ring, really you only have to work over GF(2). During the Buchberger algorithm, all S-polynomials are of the form monomial=monomial. This is a very special case and implementing Buchbergers algorithm in this special case is probably faster than any general-purpose code. But then, its been fast enough for me so far. If you use smaller coefficient rings then converting it back into an ideal over QQ, say, gets more difficult. For example, if you use GF(2) then you have to manually give each generator alternating signs. So its probably most convenient to work over QQ.

[novoselt]

Looks good!

For the second patch:

5. (line 433) The implementation looks very confusing to me: why would you store in the field embedding_morphism an exception??? I would expect either returning the stored value if it exists, or constructing the default embedding into the ambient space...
6. (line 441) Am I right that embedding_origin may be a non-origin as in not (0,0,0)? In this case I kind of really don't like using the word origin, how about marked_point instead or embegging_marking or embedding_center to put it next to the embedding?
7. (line 1847) There should be no "local", this scheme is just isomorphic to a neighbourhood of the point.
8. (line 1859) ``result.embedding_morphism`` should be more like :meth:`embedding_morphism` or at least ``result.embedding_morphism()``, same for (1862).
9. (line 2076) affine_patch was used for compatibility with projective spaces, do we really need to change its name? If yes, then a) the old name should be kept as well for compatibility, b) how about covering_patch since toric varieties are printed as covered by 5 affine patches?
10. "algebraic" attached to patches seems a bit weird to me...
11. Aha, now I see that affine_patch is preserved. Now the question is - do we really need three functions or maybe affine_patch with several forms of input will do?..
12. (line 2169) Why 0 is listed as one of the ideal generators?
13. (line 2193) You have actually added a possibility to construct lattice polytopes from a list of points, without packing them into a matrix and then transposing ;-)

[vbraun]

5. (line 433) In some (singular) cases you can't express the embedding morphism as polynomial map, so it currently can't be represented in Sage. The embedding morphism is constructed as a byproduct of the patch, so we can't immediately raise an exception. Really, we only need the patch and the pull-back of ideals and never the embedding morphism.

6. (line 441) You are right, I changed it to embedding_center.

7. (line 1847) fixed.

8. (line 1859) fixed.

9. (line 2076) I removed the toric_algebraic_patch() which was an alias for affine_patch().

For projective space, affine_patch() returns the cover by affine space. The natural analog for toric varieties is the cover by an affine toric variety, and is again called affine_patch(). There is also a useful patch covering by an affine algebraic variety, which I called affine_algebraic_patch. I do want to distinguish affine_patch and affine_algebraic_patch since they produce very different output.

10. (line 2169) I added an extra line to filter out the 0 generator to the ideal, though mathematically it of course makes no difference.

11. (line 2193) thanks for reminding me :-)

[vbraun]

Updated patch

[novoselt]

I am getting the following:

novoselt@geom:/disk/scratch/novoselt/sage-4.7.1.alpha2/devel/sage-main$ ../../sage -t sage/schemes/generic/toric_ideal.py 
sage -t  "devel/sage-main/sage/schemes/generic/toric_ideal.py"
**********************************************************************
File "/disk/scratch/novoselt/sage-4.7.1.alpha2/devel/sage-main/sage/schemes/generic/toric_ideal.py", line 24:
    sage: IA.ker()
Expected:
    Free module of degree 3 and rank 1 over Integer Ring
    User basis matrix:
    [ 1 -2  1]
Got:
    Free module of degree 3 and rank 1 over Integer Ring
    Echelon basis matrix:
    [ 1 -2  1]
**********************************************************************
File "/disk/scratch/novoselt/sage-4.7.1.alpha2/devel/sage-main/sage/schemes/generic/toric_ideal.py", line 39:
    sage: IA.ker()
Expected:
    Free module of degree 4 and rank 2 over Integer Ring
    User basis matrix:
    [ 1 -1 -1  1]
    [ 1 -2  1  0]
Got:
    Free module of degree 4 and rank 2 over Integer Ring
    Echelon basis matrix:
    [ 1  0 -3  2]
    [ 0  1 -2  1]
**********************************************************************
File "/disk/scratch/novoselt/sage-4.7.1.alpha2/devel/sage-main/sage/schemes/generic/toric_ideal.py", line 298:
    sage: IA.ker()
Expected:
    Free module of degree 3 and rank 1 over Integer Ring
    User basis matrix:
    [ 1 -2  1]
Got:
    Free module of degree 3 and rank 1 over Integer Ring
    Echelon basis matrix:
    [ 1 -2  1]
**********************************************************************
File "/disk/scratch/novoselt/sage-4.7.1.alpha2/devel/sage-main/sage/schemes/generic/toric_ideal.py", line 379:
    sage: IA.ker()
Expected:
    Free module of degree 3 and rank 1 over Integer Ring
    User basis matrix:
    [ 1 -2  1]
Got:
    Free module of degree 3 and rank 1 over Integer Ring
    Echelon basis matrix:
    [ 1 -2  1]
**********************************************************************
File "/disk/scratch/novoselt/sage-4.7.1.alpha2/devel/sage-main/sage/schemes/generic/toric_ideal.py", line 420:
    sage: IA._ideal_quotient_by_variable(R, J0, 0)
Expected:
    Ideal (z2*z3^2 - z0*z1*z4, z1*z3 - z0*z2,
           z2^2*z3 - z1^2*z4, z1^3*z4 - z0*z2^3)
    of Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field
Got:
    Ideal (z2*z3^2 - z0*z1*z4, z2^2*z3 - z1^2*z4, z1^2*z3*z4 - z0*z1*z2*z4, z1^4*z4^2 - z0*z1*z2^3*z4) of Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field
**********************************************************************
4 items had failures:
   2 of  26 in __main__.example_0
   1 of   6 in __main__.example_4
   1 of   7 in __main__.example_7
   1 of   8 in __main__.example_8
***Test Failed*** 5 failures.
For whitespace errors, see the file /home/novoselt/.sage//tmp/.doctest_toric_ideal.py
	 [7.1 s]

Also, it seems that with -long option the long test is really long both on my machine and on sage.math, although I didn't try any other version of Sage but 4.7.1.alpha2. Applying Hilbert cone speed up does not seem to help.

[vbraun]

Updated patch

[vbraun]

Andrey reported a performance regression in Sage-4.7.1.alpha2 for the long doctests. The reason is that the syntax for computing the LLL-reduced kernel changed from A.right_kernel(LLL=True) to A.right_kernel(basis='LLL'). Unfortunately #10746 did not add a deprecation warning, but then we were the only users of the LLL=True syntax. The result was that Sage-4.7.1.alpha2 computed the naive ideal with the echelon form of the kernel and not the LLL-reduced form, which makes the Groebner basis computations much much harder.

The updated patch switches to the new syntax and works as fast as before.

[vbraun]

One of the doctests crashes with Sage-4.7.alpha2 because of #11481.

[vbraun]

The doctests pass with the patch from #11481.

[novoselt]

Everything works now and once #11481 is approved, I am happy to switch this one (and #10529) to positive review!

[novoselt]

Hi Jeroen, if there is any chance to include this ticket into 4.7.1, it would be greatly appreciated! (I am participating in a toric summer school in a month and it would be great if this functionality was available in a stable release by then.)