Mixed lattice polytope theory with a view towards sparse polynomial systems

Abstract

Diese Arbeit befasst sich mit verschiedenen gemischten Fragestellungen aus der Gitterpolytoptheorie. Damit sind Fragestellungen gemeint, die sich auf Tupel von Gitterpolytopen beziehen und für die somit sowohl die Struktur der einzelnen Polytope als auch deren Lage zueinander eine Rolle spielen. Eine zentrale Motivation hierfür ist der berühmte Satz von Bernstein-Khovanskii-Kushnirenko, der die Anzahl an Lösungen eines polynomiellen Gleichungssystems durch das gemischte Volumen des Tupels der Newton-Polytope der Polynome beschränkt. Ziel dieser Arbeit ist es, verschiedene Probleme an der Grenze zwischen algebraischer und diskreter Geometrie aus dem Blickwinkel einer gemischten Gitterpolytoptheorie zu behandeln und damit sowohl die Relevanz dieses Gebietes zu illustrieren als auch die Entwicklung der Grundlagen auf diesem Feld voranzutreiben. Im ersten Teil der Arbeit führen wir grundlegende Begriffe und Notationen ein. Im zweiten Teil präsentieren wir Resultate über die Cayley-Summe eines Tupels von Gitterpolytopen, welche wir an verschiedenen anderen Stellen in dieser Arbeit benötigen. Im dritten Teil widmen wir uns der gemischten Diskriminanten eines Tupels von ganzzahligen Punktkonfigurationen. Diese ist ein Polynom, das enkodiert unter welchen Bedingungen ein polynomielles Gleichungssystem bestimmte mehrfache Nullstellen hat. Wir geben eine hinreichende kombinatorische Bedingung für die Existenz dieser gemischten Diskrimanten und beweisen damit eine Vermutung von Cattani et. al. Der vierte Teil ist der Entwicklung eines Algorithmus für die Klassifikation von Tripeln von Gitterpolytopen im R3 mit gegebenem gemischten Volumen gewidmet. Nach dem Satz von BKK ist dies äquivalent zu der Klassifikation von generischen Systemen trivariater Polynome mit gegebener Anzahl von Lösungen. Anhand einer Implementierung dieses Algorithmus erhalten wir eine vollständige Klassifikation dieser Tripel mit gemischtem Volumen höchstens vier. Im fünften Teil dieser Arbeit untersuchen wir Tupel von Gitterpolytopen, deren gemischter Grad höchstens eins ist. Wir zeigen, dass es in jeder Dimension abgesehen von einer gut verstandenen Familie von Tupeln nur endlich viele exzeptionelle Tupel mit gemischtem Grad eins gibt. Des Weiteren klassifizieren wir solche Tupel in Dimension drei vollständig. Im sechsten und letzten Teil dieser Arbeit zeigen wir eine obere Schranke an das Volumen der Minkowski-Summe eines Tupels konvexer Körper, dessen gemischtes Volumen gegeben ist. Unsere Schranke ist asymptotisch scharf und in den Spezialfällen von Dimension zwei und drei finden wir darüber hinaus eine scharfe exakte Schranke.

This work treats several mixed questions in the theory of lattice polytopes. By that we mean questions that are in terms of tuples of lattice polytopes and for which one has to consider not only the structure of the single lattice polytopes in the tuple, but also their alignment with respect to each other. Central motivation for treating such questions comes from the famous Bernstein-Khovanskii-Kushnirenko theorem. This result bounds the number of solutions of a polynomial system by the mixed volume of the tuple of Newton polytopes of the polynomials. The scope of this work is to treat different problems at the intersection of algebraic and discrete geometry from the point of view of a mixed lattice polytope theory. In the course of this we illustrate the relevance of this field of research and make progress in the development of its foundations. The first chapter is dedicated to the introduction of basic concepts and notation. In the second chapter we present results about the Cayley sum of a tuple of lattice polytopes that we make use of in several parts of this work. The third chapter deals with the mixed discriminant of a tuple of point configurations, which is a polynomial that encodes the conditions for a system of polynomial equations to have a multiple root. We prove a sufficient combinatorial condition for the existence of the mixed discriminant and employ this to solve a conjecture by Cattani et. al. In the fourth chapter we present an algorithm for the classification of triples of lattice polytopes in R3 with a given mixed volume. By the BKK-theorem, this is equivalent to the classification of generic systems of trivariate polynomials with a given number of solutions. Via this algorithm, we obtain a complete classification of triples of lattice polytopes with mixed volume at most four. The fifth chapter treats tuples of lattice polytopes whose mixed degree is at most one. We show that, in dimension at least four, there exist only finitely many exceptional tuples of mixed degree one that are not part of a well-understood family. We furthermore present a complete classification of such tuples in dimension three. Finally, in chapter six we prove an upper bound on the volume of the Minkowksi sum of a tuple of convex bodies in terms of its mixed volume. Our bound is asymptotically sharp. In dimensions two and three we furthermore prove an exact sharp bound.