forum.polymake.org

Posted: **11 Jun 2021, 13:03**

Hi,

I have a question about the "intersect" and "set_theoretic_intersection" commands in polymake. I made an example down below with two tropical hypersurfaces in R^{4}. Polymake then tells me that their stable intersection is two-dimensional, whereas their set-theoretic intersection is one-dimensional. Is polymake by any chance removing a lineality space in the set-theoretic intersection or?

The corresponding code is as follows:

Code: Select all

application "tropical";
$f1 = toTropicalPolynomial("min(a+b+c-20,b+c+w+5,d+2*b+1,c+2*w)", qw( a b c d w ));
$f2 = toTropicalPolynomial("min(2*a+b-5,a+b+w+3,2*b+w-2,b+c+w+10)", qw( a b c d w ));
$V1 = new Hypersurface<Min>(POLYNOMIAL=>$f1);
$V2 = new Hypersurface<Min>(POLYNOMIAL=>$f2);
$W12 = set_theoretic_intersection($V1,$V2);
$V12 = intersect($V1,$V2);
print $W12->DIM;
print $V12->DIM;

Thanks in advance!

Posted: **11 Jun 2021, 17:16**

That's a difficult question in the sense that these functions reside in Simon Hampe's extension atint, which became bundled a while ago. Thing is: no-one is currently working on that code.

Nonetheless, we will check. Just be a bit patient, please.

Posted: **11 Jun 2021, 20:06**

Oh dear, oh dear, this was all so long ago

I haven't worked on polymake for four years and I can see from the source that a few changes were made. Also, I don't have a working local polymake at the moment, so my diagnosis is at least half guesswork.

Here's what I can tell. The function set_theoretic_intersection eventually uses fan_intersection in convex_hull_tools.cc. The documentation in convex_hull_tools.h says that "All coordinates should be given non-tropically-homogeneously", i.e. dehomogenized. However as far as I can tell, the coordinates of the cycles are just given to the fan_intersection function as is:

Code: Select all

  const Matrix<Rational> &arays = A.give("VERTICES");
  const IncidenceMatrix<> &acones = A.give("MAXIMAL_POLYTOPES");
  const Matrix<Rational> &alineality = A.give("LINEALITY_SPACE");

  const Matrix<Rational> &brays = B.give("VERTICES");
  const IncidenceMatrix<> &bcones = B.give("MAXIMAL_POLYTOPES");
  const Matrix<Rational> &blineality = B.give("LINEALITY_SPACE");

  fan_intersection_result result = fan_intersection(arays,alineality,acones, brays,blineality,bcones);

Instead, dehomogenization takes place *after* the intersection.

If I perform this little cheat in the polymake-in-a-box:

Code: Select all

$cheat1 = new Cycle<Min>(VERTICES=>tdehomog($V1->VERTICES), MAXIMAL_POLYTOPES=>$V1->MAXIMAL_POLYTOPES,LINEALITY_SPACE=>tdehomog($V1->LINEALITY_SP
ACE));     
$cheat2 = new Cycle<Min>(VERTICES=>tdehomog($V2->VERTICES), MAXIMAL_POLYTOPES=>$V2->MAXIMAL_POLYTOPES, LINEALITY_SPACE=>tdehomog($V2->LINEALITY_S
PACE));
$cheatintersect = set_theoretic_intersection($cheat1,$cheat2);

the intersection now has the correct dimension 2! Of course the objects are nonsense since their vertices are not tropically homogenous, but the input to fan_intersection is now correct, hence so is the result.

So, my diagnosis would be: This is a bug and someone should switch the dehomogenization to *before* the fan_intersection. It's probably faster if someone else than me does this, it'll take me ages to find the git repo url, see if my credentials still work, figure out ninja, etc. etc.... (Michael is so not buying me beer for this...)

Posted: **11 Jun 2021, 20:24**

Just to blame the right guy: The bug seems to have been in the original already, see https://github.com/simonhampe/atint/blo ... l_tools.cc

In earlier times a-tint used to not use tropically homogeneous coordinates, I suspect this got lost in the transition somehow?
In that case this would have gone unnoticed for quite some time, so feel free to challenge my diagnosis...

EDIT: I can currently only access https://github.com/polymake/polymake and I can't seem to find the testsuites in there - so I can't verify, whether we just chose sufficently naive tests to simply overlook this problem.

Posted: **11 Jun 2021, 21:15**

Okay, I think I might have a minimal example worked out - and might have discovered a second bug (related to this one):
When the set-theoretic-intersection is empty, I get a

Code: Select all

polymake: ERROR: Invalid chart coordinate

The "special" thing about the example is that both hypersurfaces have lineality spaces, in particular the first one has one whose generator is *not* normalized w.r.t tropical homogeneity (which I think is fine?):

Code: Select all

tropical > print $V1->LINEALITY_SPACE;                                                                                                                      
0 1 1 -2 -2 1

Now, as long as all vertices and lin space generators are normalized, this bug won't occur: The additional tropical dimension just doesn't factor into the intersection since everything lives at x_0=0 anyway. Now if the lineality space is *not* normalized, things go awry.

For my minimal example, first of all note the following:

Code: Select all

tropical > $line1 = new Cycle<Max>(VERTICES=>[[1,0,0,0,0],[0,0,1,1,0],[0,0,0,-1,0],[0,0,-1,0,0]],MAXIMAL_POLYTOPES=>[[0,1],[0,2],[0,3]],WEIGHTS=>[1,1,1]);                                                                                                                                                        
tropical > $line2 = new Cycle<Max>(VERTICES=>[[1,0,0,0,1],[0,0,1,1,0],[0,0,0,-1,0],[0,0,-1,0,0]],MAXIMAL_POLYTOPES=>[[0,1],[0,2],[0,3]],WEIGHTS=>[1,1,1]);                                                                                                                                   
tropical > print set_theoretic_intersection($line1,$line2);
                                                                                                                                                            
polymake:  ERROR: Invalid chart coordinate

These are two tropical lines in threespace that don't intersect. I suspect that the error occurs when trying to dehomogenize the empty ray matrix at the end? I think this should be fixed automatically by putting the dehomogenization in the proper place. In any case it should definitely be a test case.

In any case, assuming that an empty intersection is indicated by an error message, let's look at the following:

Code: Select all

tropical > $line1 = new Cycle<Max>(VERTICES=>[[1,0,0,0,0],[0,0,1,1,0],[0,0,0,-1,0],[0,0,-1,0,0]],MAXIMAL_POLYTOPES=>[[0,1],[0,2],[0,3]],WEIGHTS=>[1,1,1]);
tropical > $line2 = new Cycle<Max>(VERTICES=>[[1,0,0,0,1],[0,0,1,1,0],[0,0,0,-1,0],[0,0,-1,0,0]],MAXIMAL_POLYTOPES=>[[0,1],[0,2],[0,3]],WEIGHTS=>[1,1,1], LI
NEALITY_SPACE=>[[0,0,0,0,1]]);                                                                                                                                                                                                                                                                                                                
tropical > print set_theoretic_intersection($line1,$line2)->DIM;                                                                                            
1

This works fine, the lineality space is normalized. Let's try this with a non-normalized version:

Code: Select all

tropical > $line1 = new Cycle<Max>(VERTICES=>[[1,0,0,0,0],[0,0,1,1,0],[0,0,0,-1,0],[0,0,-1,0,0]],MAXIMAL_POLYTOPES=>[[0,1],[0,2],[0,3]],WEIGHTS=>[1,1,1]);
tropical > $line2 = new Cycle<Max>(VERTICES=>[[1,0,0,0,1],[0,0,1,1,0],[0,0,0,-1,0],[0,0,-1,0,0]],MAXIMAL_POLYTOPES=>[[0,1],[0,2],[0,3]],WEIGHTS=>[1,1,1], LI
NEALITY_SPACE=>[[0,1,1,1,2]]);                                                                                                                              
                                                                                                                                                            
tropical > print set_theoretic_intersection($line1,$line2)->DIM;                                                                                            

polymake:  ERROR: Invalid chart coordinate

So, all in all, I think my initial assumption was correct: The set-theoretic intersection needs non-homogenous coordinates to work and we didn't notice it until now because we were always being good little tropical geometers and using nicely homogenized coordinates

Posted: **17 Jun 2021, 12:47**

Thanks for looking into this Simon! We will try to take care of this next week.

Posted: **07 Jul 2021, 14:54**

Hi,
I have fixed the problem with set_theoretic_intersection following Simon's comments.
Now, we get the following dimensions in your example.

Code: Select all

application "tropical";
$f1 = toTropicalPolynomial("min(a+b+c-20,b+c+w+5,d+2*b+1,c+2*w)", qw( a b c d w ));
$f2 = toTropicalPolynomial("min(2*a+b-5,a+b+w+3,2*b+w-2,b+c+w+10)", qw( a b c d w ));
$V1 = new Hypersurface<Min>(POLYNOMIAL=>$f1);
$V2 = new Hypersurface<Min>(POLYNOMIAL=>$f2);
$W12 = set_theoretic_intersection($V1,$V2);
$V12 = intersect($V1,$V2);
print $W12->DIM;
2
print $V12->DIM;
2

The change will be available in the next polymake release. In the meanwhile, if you need to compute some more intersections, just let me know.

forum.polymake.org

Stable intersection not contained in set-theoretic intersection

Stable intersection not contained in set-theoretic intersection

Re: Stable intersection not contained in set-theoretic intersection

Re: Stable intersection not contained in set-theoretic intersection

Re: Stable intersection not contained in set-theoretic intersection

Re: Stable intersection not contained in set-theoretic intersection

Re: Stable intersection not contained in set-theoretic intersection

Re: Stable intersection not contained in set-theoretic intersection