IdealAffineToricVariety gives incorrect results

[jgmbenoit]

See Description field in Pull requests #3.

[olexandr-konovalov]

@jgmbenoit thanks - this seems to be an important issue: an old example from a published paper can not be reproduced any more. Could you perhaps copy the full description here, to avoid redirection to the PR which may be even closed in the future?

[jgmbenoit]

Testing the package itself against the samples given in the documentation with the help of ExtractExamples (section 5.4 in GAPDoc Reference Manual) exhibits an unexpected `return', at least for blind eyes. We observe

 gap> J:=IdealAffineToricVariety([[1,0],[3,4]]);
 <two-sided ideal in Rationals[x_1,x_2,x_3,x_4,x_5], (3 generators)>
 gap> GeneratorsOfIdeal(J);
 [ -x_4^4+x_1, -x_4^3+x_2, -x_4^2+1 ]

while we expect

 gap> J:=IdealAffineToricVariety([[1,0],[3,4]]);
 [ two-sided ideal in PolynomialRing(..., [ x_1, x_2 ]), (3 generators) ]
 gap> GeneratorsOfIdeal(J);
 [ -x_2^2+x_1, -x_2^3+x_1^2, -x_2^4+x_1^3 ]

As pointed out by the upstream maintainer [private communication], the article "Computing with toric varieties'' in "Journal of Symbolic Computation" volume 42 issue 5 (May 2007, pages 511-532) [doi:10.1016/j.jsc.2006.08.005] uses this example as illustration (example 2.18 (b) p 520). At the time of patching, it is not clear neither to the upstream maintainer nor to the package maintainer whether or not the two answers are equivalent. Further investigations are on their ways.

Meanwhile, to not introduce a faulty correction, the example is replaced by its sibling (example 2.18 (a) p 520) whose the expected and observed final answers are the same:

 gap> J:=IdealAffineToricVariety([[0,1],[2,-1]]);
 <two-sided ideal in Rationals[x_1,x_2,x_3], (1 generators)>
 gap> GeneratorsOfIdeal(J);
 [ -x_2^2+x_1 ]

Note that this test failure might hide a serious bug.

[fingolfin]

Upon closer inspection, I am afraid neither result is correct: First off, there was a bug in IdealAffineToricVariety which I fixed in f25a3141394a0fb26407bcdaace784b5af520945

But even after that, I think the implementation of IdealAffineToricVariety simply is incorrect, respectively the "algorithm" there only produces a subideal of the correct ideal.

I cross checked with Sage, and it produces a larger ideal.

As far as I can tell, the reason is that toric only uses a generating set of the nullspace of the DualSemigroupGenerators of the cone to produce generators of the toric ideal. But that is not guaranteed to give a generating set of the toric ideal. Indeed, consider this:

gap> L:=[[0,1],[2,-1]];;
gap>  u:=DualSemigroupGenerators(L);
[ [ 0, 0 ], [ 1, 0 ], [ 1, 1 ], [ 1, 2 ] ]
gap> u:=Filtered(DualSemigroupGenerators(L),v->not IsZero(v));
[ [ 0, 1 ], [ 1, 0 ], [ 2, -1 ], [ 3, -2 ], [ 4, -3 ] ]
gap> B:=NullspaceIntMat(u);;Display(B);
[ [   1,   0,   0,  -4,   3 ],
  [   0,   1,   0,  -3,   2 ],
  [   0,   0,   1,  -2,   1 ] ]

These three kernel generators correspond to the following three binomial generators of the toric ideal:

x_1 x_5^3 - x_4^4
x_2 x_5^2 - x_4^3
x_3 x_5 - x_4^2

and this is precisely the generating set IdealAffineToricVariety produces after my fix in f25a3141394a0fb26407bcdaace784b5af520945

But that is not enough: If you subtract the second and third kernel generators, you get the vector [ 0, 1, -1, -1, 1 ] corresponding to the binomial x_2x_5 - x_3x_4, which is contained in the toric ideal, but is not contained in the ideal returned by IdealAffineToricVariety. We can verify this using a Groebner basis computation as follows:

gap> J:=IdealAffineToricVariety([[1,0],[3,4]]);;
gap> AssignGeneratorVariables(PolynomialRing(Rationals,5));
#I  Assigned the global variables [ x_1, x_2, x_3, x_4, x_5 ]
gap> x_1*x_5^3 - x_4^4 in J;
true
gap> x_2*x_5^2 - x_4^3 in J;
true
gap> x_3*x_5 - x_4^2 in J;
true
gap> x_2*x_5 - x_3*x_4 in J;
false

I have no idea where the generators from the paper come from.

[fingolfin]

BTW, I also verified against sage:

sage: c = Cone([(1,0), (3,4)])
sage: X = AffineToricVariety(c)
sage: X.Spec()
Spectrum of Quotient of Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field by the ideal (-z0*z3 + z4^2, -z0*z2 + z3*z4, -z0*z1 + z3^2, -z0*z1 + z2*z4, z2*z3 - z1*z4, z2^2 - z1*z3)

Or:

sage: A = matrix([ [ 0, 1, 2, 3, 4 ], [ 1, 0, -1, -2, -3 ] ]); ToricIdeal(A)
Ideal (-z1*z3 + z0*z4, -z1*z2 + z0*z3, z3^2 - z2*z4, -z1^2 + z0*z2, z2*z3 - z1*z4, z2^2 - z1*z3) of Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field

One can verify that after relabeling (z0 <-> x_1 and so on) we get an ideal which contains the ideal computed by toric, but also the missing elements...

[jgmbenoit]

@fingolfin When you say Sage, which software is really involved ?

[fingolfin]

As far as I know, this is "proper" Sage code, writte by Andrey Novoseltsev and Volker Braun in Python (though I guess internally, they might be using some other software to compute Groebner bases; alas, for these examples, a naive implementation, such as the one found in GAP, is fully sufficient).

[fingolfin]

BTW, the output of the manual example looks very strange:

gap> J:=IdealAffineToricVariety([[1,0],[3,4]]);
[ two-sided ideal in PolynomialRing(..., [ x_1, x_2 ]), (3 generators) ]

This suggests that the base ring is in two variables, not 5. Hmmm. The generators given in the manual example) look as if they were obtained by projecting from 5 dimensions down to 2 (notably, the exponents in the generators correspond precisely to the last two columns of the nullspace matrix B I gave in a previous comment).

It is also weird that there are brackets [ and ] around the output. I thought GAP always printed ideals with angular braces < and >.

[wdjoyner]

On Wed, Dec 28, 2016 at 3:08 PM, Max Horn notifications@github.com wrote:

BTW, the output of the manual example looks very strange:

gap> J:=IdealAffineToricVariety([[1,0],[3,4]]); [ two-sided ideal in PolynomialRing(..., [ x_1, x_2 ]), (3 generators) ]

This suggests that the base ring is in two variables, not 5. Hmmm. The generators given in the manual example) look as if they were obtained by projecting from 5 dimensions down to 2 (notably, the exponents in the generators correspond precisely to the last two columns of the nullspace matrix B I gave in a previous comment).

What is the ideal J for which CC[x1,x2]/J is the toric coordinate ring associated to the cone \sigma = {(a+3b,4b) | a>=0, b>=0} \subset QQ?

It is also weird that there are brackets [ and ] around the output. I thought GAP always printed ideals with angular braces < and >.

Can you possibly try the toric commands in GAP 4.2?

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/gap-packages/toric/issues/4#issuecomment-269533213, or mute the thread https://github.com/notifications/unsubscribe-auth/AADIt5UJsbrGdVOIq3SCE6fgqeZC7PqEks5rMsGpgaJpZM4LWphS .

[fingolfin]

@wdjoyner As to trying the toric command in GAP 4.2: I never used GAP before 4.4, so I have no idea whether it would run, but if that's the version used to create the paper and manual example, that might indeed explain the differing output formatting. And perhaps also the differing output? Though I don't see how the curren code could possible produce something in 2 instead of 5 variables?

While at it, I wonder what version of toric was used to produce the paper? Version 1.2 of toric already contains the same code for IdealAffineToricVariety as version 1.8, and produces the same output for me, differing from the manual. So my guess is that something changed between 1.0 and 1.2 that affected this? But sadly I could not find neither toric 1.0 nor 1.1 (and also not 1.3 -- the toric 1.3 on the GAP servers is a copy of toric 1.2).

[wdjoyner]

On Wed, Dec 28, 2016 at 3:19 PM, Max Horn notifications@github.com wrote:

@wdjoyner https://github.com/wdjoyner As to trying the toric command in GAP 4.2: I never used GAP before 4.4, so I have no idea whether it would run, but if that's the version used to create the paper and manual example, that might indeed explain the differing output formatting. And perhaps also the differing output? Though I don't see how the curren code could possible produce something in 2 instead of 5 variables?

While at it, I wonder what version of toric was used to produce the paper? Version 1.2 of toric already contains the same code for IdealAffineToricVariety as version 1.8, and produces the same output for me, differing from the manual. So my guess is that something changed between 1.0 and 1.2 that affected this? But sadly I could not

I don't think so. I found earlier versions and that part is the same. I think Alexander K made me change Star to ToricStar before acceptance. The paper used the command Star (not ToricStar), so it must have been a version before toric was accepted as a GAP package. I don't have a copy of that earlier version.

Possibly GAP's null space command for integer matrices different in 4.4 than in 4.4? Just a guess.

find neither toric 1.0 nor 1.1 (and also not 1.3 -- the toric 1.3 on the GAP servers is a copy of toric 1.2).

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/gap-packages/toric/issues/4#issuecomment-269534636, or mute the thread https://github.com/notifications/unsubscribe-auth/AADItzloSEkDT5gv0HcG4w3SCftI05bwks5rMsQ-gaJpZM4LWphS .

[fingolfin]

@wdjoyner as to your other question: aha, are your indirectly telling me that I am misinterpreting the purpose of IdealAffineToricVariety? This is of course quite possible -- I am not exactly an expert on toric varieties, after all. But let's see, its documentation says "the GAP ideal defining the toric variety associated to the cone generated by the vectors in L."

I interpreted this as saying that it does the following (and the code seemed to support that): Given the lattice L, compute a generating set G := g_1,...,g_k of the semigroup S associated to the dual lattice, via DualSemigroupGenerators (in this example, this happens to give k=5 generators). Then use the fact that the affine toric variety corresponds to Spec(CC[S]), which in turn is equivalent to the variety associated to the variety V(I_G) \subseteq CC[x_1,...,x_k], where k is as above, and the ideal is given by

I_G := < x^a - x^b | a,b \in NN^k, a-b \in L >

Since this is the "standard" way, (an, now that I am reading your paper, I see it is mentioned there as Lemma 2.13), and since this very closely matches what the code in IdealAffineToricVariety does, I assumed that this is also what was the documentation meant, and what the intended output was (except that the code for IdealAffineToricVariety does not produce enough binomials to really generate I_G)

That all said, of course one can in principled hopw to describe a toric variety with another coordinate ring. But looking at examples 2.17 and 2.18 in the paper, I don't quite understand what happens there...

For starters, in example 2.17, there is a claim that the ring R_\tau is isomorphic to

F[x,y,z,w] / <w z^2 -x, xy - z^2 >

which I don't understand -- there is an appeal to Lemma 2.13, but I don't see how Lemma 2.13 helps here, as it is not (yet) effective: It gives us a description of the ideal, but that description is not yet finite; one still has to consider all elements of the nullspace of a certain matrix, and it is in general not enough to just look at an arbitrary generating set for it...

And indeed, isn't the relator yw-1 missing in 2.17? A quick Groebner basis calculation (can b done by hand) verifies that It is not implied by the given relators w z^2 -x and xy - z^2, yet it holds in R_\tau... Adding that relator, we can simplify the isomorphism, by eliminating x using the relator wz^2-x; plugging that into xy - z^2 yields wz^2y-z^2 = z^2*(yw-1), which is redundant, so we end up with

R_\tau \cong F[y,z,w] / < yw - 1 >

Next, the first part of example 2.18 computes IdealAffineToricVariety([[0,1],[2,-1]]), which back (and also in toric 1.8) produced [ -x_2^2+x_1 ]. In the paper, it then goes on to say After “projectivizing”, this is consistent with the above example. Presuambly, this refers to Example 2.12 (and not 2.17, as one might think, or at least as I first thought -- "above" is a bit ambigious ;-).

However, with the change I made to the code earlier today, the computation now returns [ x_1*x_3-x_2^2 ]. And this matches perfectly the term xz-y^2 from Example 2.12, no need for "projectivizing".

So, all in all, I am still tempted to say that there was (a) a bug (fixed by commit f25a3141394a0fb26407bcdaace784b5af520945), which fixes the first part of Example 2.18; and (b) Lemma 2.13 as stated is not effective, and that leads to problems in Examples 2.17 and the second part of 2.18, and in the implementation of IdealAffineToricVariety.

[fingolfin]

@wdjoyner I don't think a change in the nullspace command of GAP would be sufficient to exaplin the difference between the results toric 1.2 to 1.8 produce, and what is printed in the manual and the paper. To go from 2 to 5 variables in the ideal, the number of generators of the semigroup would have to change, or the algorithm in IdealAffineToricVariety; the nullspace computation cannot affect it. Hence my question whether something in that code might have changed between publication of the paper, and of the package...

[wdjoyner]

On Wed, Dec 28, 2016 at 4:45 PM, Max Horn notifications@github.com wrote:

@wdjoyner https://github.com/wdjoyner I don't think a change in the nullspace command of GAP would be sufficient to exaplin the difference between the results toric 1.2 to 1.8 produce, and what is printed in the manual and the paper. To go from 2 to 5 variables in the ideal, the number of generators of the semigroup would have to change, or the algorithm in IdealAffineToricVariety; the nullspace computation cannot affect it. Hence my question whether something in that code might have changed between publication of the paper, and of the package...

I wonder if one or more of the d0's should be a d instead. In the example gap> L:=[[1,0],[3,4]]; they have the values d0=5, d=2. The exponents in the terms generating the ideal associated to L obviously come from the non-trivial terms in gap> DualSemigroupGenerators(L); [ [ 0, 0 ], [ 0, 1 ], [ 1, 0 ], [ 2, -1 ], [ 3, -2 ], [ 4, -3 ] ] These get converted into a matrix M, gap> M; [ [ 0, 1 ], [ 1, 0 ], [ 2, -1 ], [ 3, -2 ], [ 4, -3 ] ] and its null space is generated by gap> B:=NullspaceIntMat(M); [ [ 1, 0, 0, -4, 3 ], [ 0, 1, 0, -3, 2 ], [ 0, 0, 1, -2, 1 ] ] It's the last 2 coordinates which are needed, not all 5.

—

You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/gap-packages/toric/issues/4#issuecomment-269545987, or mute the thread https://github.com/notifications/unsubscribe-auth/AADIt4s2Qmra0XGPajoo8WCt_bCBXQNAks5rMthkgaJpZM4LWphS .

[wdjoyner]

On Wed, Dec 28, 2016 at 4:42 PM, Max Horn notifications@github.com wrote:

@wdjoyner https://github.com/wdjoyner as to your other question: aha, are your indirectly telling me that I am misinterpreting the purpose of IdealAffineToricVariety? This is of course quite possible -- I am not exactly an expert on toric varieties, after all. But let's see, its documentation says "the GAP ideal defining the toric variety associated to the cone generated by the vectors in L."

I interpreted this as saying that it does the following (and the code seemed to support that): Given the lattice L, compute a generating set G := g_1,...,g_k of the semigroup S associated to the dual lattice, via DualSemigroupGenerators (in this example, this happens to give k=5 generators). Then use the fact that the affine toric variety corresponds to Spec(CC[S]), which in turn is equivalent to the variety associated to the variety V(I_G) \subseteq CC[x_1,...,x_k], where k is as above, and the ideal is given by

I_G := < x^a - x^b | a,b \in NN^k, a-b \in L >

Since this is the "standard" way, (an, now that I am reading your paper, I see it is mentioned there as Lemma 2.13), and since this very closely matches what the code in IdealAffineToricVariety does, I assumed that this is also what was the documentation meant, and what the intended output was (except that the code for IdealAffineToricVariety does not produce enough binomials to really generate I_G)

That all said, of course one can in principled hopw to describe a toric variety with another coordinate ring. But looking at examples 2.17 and 2.18 in the paper, I don't quite understand what happens there...

For starters, in example 2.17, there is a claim that the ring R_\tau is isomorphic to

F[x,y,z,w] / <w z^2 -x, xy - z^2 >

which I don't understand -- there is an appeal to Lemma 2.13, but I don't see how Lemma 2.13 helps here, as it is not (yet) effective: It gives us a description of the ideal, but that description is not yet finite; one still has to consider all elements of the nullspace of a certain matrix, and it is in general not enough to just look at an arbitrary generating set for it...

And indeed, isn't the relator yw-1 missing in 2.17? A quick Groebner basis calculation (can b done by hand) verifies that It is not implied by the given relators w z^2 -x and xy - z^2, yet it holds in R_\tau... Adding that relator, we can simplify the isomorphism, by eliminating x using the relator wz^2-x; plugging that into xy - z^2 yields wz^2y-z^2 = z^2*(yw-1), which is redundant, so we end up with

R_\tau \cong F[y,z,w] / < yw - 1 >

Next, the first part of example 2.18 computes IdealAffineToricVariety([[0,1],[2,-1]]), which back (and also in toric 1.8) produced [ -x_2^2+x_1 ]. In the paper, it then goes on to say After “projectivizing”, this is consistent with the above example. Presuambly, this refers to Example 2.12 (and not 2.17, as one might think, or at least as I first thought -- "above" is a bit ambigious ;-).

However, with the change I made to the code earlier today, the computation now returns [ x_1*x_3-x_2^2 ]. And this matches perfectly the term xz-y^2 from Example 2.12, no need for "projectivizing".

Agreed.

So, all in all, I am still tempted to say that there was (a) a bug (fixed by commit f25a314 https://github.com/gap-packages/toric/commit/f25a3141394a0fb26407bcdaace784b5af520945), which fixes the first part of Example 2.18; and (b) Lemma 2.13 as stated is not effective, and that leads to problems in Examples 2.17 and the second part of 2.18, and in the implementation of IdealAffineToricVariety.

I missed this email and should have read it before my last reply. I agree with all this. I think IdealAffineToricVariety should be removed from toric and the documentation. It's not used elsewhere (fortunately).

Thanks to everyone for these long emails and explanations. It's been many years since I've thought about these things and I've forgotten the details.

Should I email the new files? I'm not practiced at producing patches.

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/gap-packages/toric/issues/4#issuecomment-269545617, or mute the thread https://github.com/notifications/unsubscribe-auth/AADIt1gbdEjf9yHdZPfaYrQttpAZoRxqks5rMtfHgaJpZM4LWphS .

[fingolfin]

@wdjoyner apologies for dropping the balls on this.

We can do that of course (remove IdealAffineToricVariety). No need to send patches. I'll prepare a pull request instead which you can review, if you like, and once it's in, we can make that new release.

[wdjoyner]

On Feb 1, 2017 5:32 AM, "Max Horn" notifications@github.com wrote:

@wdjoyner https://github.com/wdjoyner apologies for dropping the balls on this.

We can do that of course (remove IdealAffineToricVariety). No need to send patches. I'll prepare a pull request instead which you can review, if you like, and once it's in, we can make that new release.

Thank you!

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/gap-packages/toric/issues/4#issuecomment-276624107, or mute the thread https://github.com/notifications/unsubscribe-auth/AADItwVhpStkbxCMxmLVLMNPQtnwnFC6ks5rYF9GgaJpZM4LWphS .

[olexandr-konovalov]

IdealAffineToricVariety has been removed: it returned incorrect results and fixing it was non-trivial. @wdjoyner if are you happy to close this issue, please do.

[wdjoyner]

On Thu, Feb 2, 2017 at 11:37 AM, Alexander Konovalov < notifications@github.com> wrote:

IdealAffineToricVariety has been removed: it returned incorrect results and fixing it was non-trivial. @wdjoyner https://github.com/wdjoyner if are you happy to close this issue, please do.

Looks good. I didn't see a way to close this on github.

[olexandr-konovalov]

@wdjoyner you should be - you have admin rights for this repository. You can't do this by email, but if you log in, scroll https://github.com/gap-packages/toric/issues/4 till the place to enter new comment. There're are two buttons under it - "close issue" and "comment". Press "close issue" (you may also input some text, if you wish).

I will close it myself later, unless you want to try to do this now.

[wdjoyner]

Looks great, thanks everyone!

[jgmbenoit]

You are welcome, Jerome

On 03/02/17 02:48, david joyner wrote:

Looks great, thanks everyone!

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/gap-packages/toric/issues/4#issuecomment-277109855, or mute the thread https://github.com/notifications/unsubscribe-auth/AIFYLCq7QlTLPIw-EIsnWoGi78uH6eSYks5rYl1AgaJpZM4LWphS.

-- Jerome BENOIT, Ph.D. | jgmbenoit-at+rezozer*dot_net http://www.rezozer.net/