Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

The hyperdeterminant and triangulations of the 4-cube


Authors: Peter Huggins, Bernd Sturmfels, Josephine Yu and Debbie S. Yuster
Journal: Math. Comp. 77 (2008), 1653-1679
MSC (2000): Primary 52B55; Secondary 68W30
DOI: https://doi.org/10.1090/S0025-5718-08-02073-5
Published electronically: February 4, 2008
MathSciNet review: 2398786
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The hyperdeterminant of format $ 2\times 2 \times 2 \times 2$ is a polynomial of degree $ 24$ in $ 16$ unknowns which has $ 2894276$ terms. We compute the Newton polytope of this polynomial and the secondary polytope of the $ 4$-cube. The $ 87959448 $ regular triangulations of the $ 4$-cube are classified into $ 25448$ $ D$-equivalence classes, one for each vertex of the Newton polytope. The $ 4$-cube has $ 80876$ coarsest regular subdivisions, one for each facet of the secondary polytope, but only $ 268$ of them come from the hyperdeterminant.


References [Enhancements On Off] (What's this?)

  • 1. E. Allman and J. Rhodes: Phylogenetic invariants for stationary base composition, Journal Symbolic Computation 41 (2006) 138-150. MR 2197150 (2006j:92041)
  • 2. F. Block and J. Yu: Tropical convexity via cellular resolutions, Journal of Algebraic Combinatorics 24 (2006) 103-114. MR 2245783 (2007f:52041)
  • 3. R. W. Cottle: Minimal triangulation of the 4-cube, Discrete Math. 40 (1982) 25-29. MR 676709 (84d:05065a)
  • 4. A. Conca, S. Hosten and R. Thomas: Nice initial complexes of some classical ideals, Algebraic and geometric combinatorics, Contemp. Math., 423, Amer. Math. Soc., Providence, RI, 2006, pp. 11-42. MR 2298753
  • 5. D. Cox, J. Little and D. O'Shea: Using Algebraic Geometry, Graduate Texts in Mathematics 185, second edition, Springer Verlag, New York, 2005. MR 2122859 (2005i:13037)
  • 6. J. De Loera: Nonregular triangulations of products of simplices, Discrete and Computational Geometry 15 (1996) 253-264. MR 1380393 (97i:52017)
  • 7. V. de Silva and L.-H. Lim: Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM Journal on Matrix Analysis and Applications, to appear.
  • 8. A. Dickenstein, E.M. Feichtner and B. Sturmfels: Tropical discriminants, Journal of the American Mathematical Society, 20 (2007) 1111-1133.
  • 9. M. Develin and B. Sturmfels: Tropical convexity, Documenta Math. 9 (2004) 1-27. MR 2054977 (2005i:52010)
  • 10. J. De Loera, J. Rambau and F. Santos: Triangulations: Applications, Structures and Algorithms, Algorithms and Computation in Mathematics, Springer Verlag, Heidelberg, to appear.
  • 11. E. Gawrilow and M. Joswig: Polymake: a framework for analyzing convex polytopes, in Polytopes -- Combinatorics and Computation, eds. G. Kalai and G.M. Ziegler, Birkhäuser, 2000, pp. 43-74. MR 1785292 (2001f:52033)
  • 12. I.M. Gel$ '$fand, M.M. Kapranov, A.V. Zelevinsky: Discriminants, Resultants, and Multidimensional Determinants; Birkhäuser, Boston, MA, 1994. MR 1264417 (95e:14045)
  • 13. H. Hirai: A geometric study of the split decomposition, Discrete and Computational Geometry 36 (2006) 331-361. MR 2252108 (2007f:52025)
  • 14. P. Lévay: On the geometry of a class of $ N$-qubit entanglement monotones, Journal of Physics A 38 (2005) 9075-9085. MR 2185885 (2006m:81070)
  • 15. J.-G. Luque and J.-Y. Thibon: The polynomial invariants of four qubits, Phys. Rev. A 67, 042303 (2003). MR 2039690 (2004k:81098)
  • 16. J. Pfeifle and J. Rambau: Computing triangulations using oriented matroids, in Algebra, Geometry and Software Systems (M. Joswig and N. Takayama, eds.) Springer Verlag, 2003, pp. 49-76. MR 2011753 (2004i:68233)
  • 17. J. Rambau: TOPCOM: triangulations of point configurations and oriented matroids. Mathematical Software (Beijing, 2002), World Sci. Publishing, River Edge, NJ, 2002, 330-340. MR 1932619
  • 18. F. Santos: The Cayley trick and triangulations of products of simplices, In Integer Points in Polyhedra - Geometry, Number Theory, Algebra, Optimization, (eds. A. Barvinok, M. Beck, C. Haase, B. Reznick, and V. Welker), Contemporary Mathematics 374, Amer. Math. Soc., Providence, 2005. MR 2134757 (2005j:00018)
  • 19. B. Sturmfels and S. Sullivant: Combinatorial secant varieties, Quarterly Journal of Pure and Applied Mathematics, 2 (2006) 285-309, (Special issue: In Honor of Robert MacPherson). MR 2252121
  • 20. B. Sturmfels and J. Yu: Classification of six-point metrics, Electronic Journal of Combinatorics 11 (2004/05) R44. MR 2097310 (2005m:51016)
  • 21. J.G. Sumner and P.D. Jarvis: Using the tangle: a consistent construction of phylogenetic distance matrices for quartets, Math. Biosci. 204 (2006) 49-67. MR 2269665 (2007g:92057)
  • 22. J.M.F. ten Berge: Kruskal's polynomial for $ 2 \times 2 \times 2$-arrays and a generalization to $ 2 \times n \times n$-arrays, Psychometrika 58 (1991) 631-636.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 52B55, 68W30

Retrieve articles in all journals with MSC (2000): 52B55, 68W30


Additional Information

Peter Huggins
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720
Email: phuggins@math.berkeley.edu

Bernd Sturmfels
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720
Email: bernd@math.berkeley.edu

Josephine Yu
Affiliation: Department of Mathematics, University of California, Berkeley, California 94720
Address at time of publication: Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Email: jyu@math.mit.edu

Debbie S. Yuster
Affiliation: Department of Mathematics, Columbia University, New York, New York 10027
Address at time of publication: DIMACS Center, Rutgers University, Piscataway, New Jersey 08854
Email: yuster@math.rutgers.edu

DOI: https://doi.org/10.1090/S0025-5718-08-02073-5
Received by editor(s): February 9, 2006
Received by editor(s) in revised form: January 6, 2007
Published electronically: February 4, 2008
Article copyright: © Copyright 2008 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society