ΠΕΡΙΛΗΨΗ

Η διδακτορική διατριβή της Άννας Καρασούλου επικεντρώνεται στην επίλυση πολυωνυμικών συστημάτων χρησιμοποιώντας εργαλεία από την αλγεβρική και την συνδυαστική γεωμετρία. Η χρήση συνδυαστικών μεθόδων κατέστη απαραίτητη για την εκμετάλλευση της δομής και της αραιότητας των πολυωνυμικών εξισώσεων. Περιγράφονται επίσης γεωμετρικοί αλγορίθμοι για την διάσπαση πολυτόπων κατά Minkowski, με απώτερη εφαρμογή την παραγοντοποίηση των αντίστοιχων πολυωνύμων στο πλαίσιο της εκμετάλλευσης της αραιότητάς τους. Η κ. Άννα Καρασούλου αντιμετώπισε με επιτυχία ορισμένα μη τετριμμένα προβλήματα, τα οποία επιγραμματικά αναφέρουμε εδώ και τα αναλύουμε στην συνέχεια.

Το πρώτο πρόβλημα είναι ο υπολογισμός τύπου της αραιής απαλοίφουσας (sparse resultant) και της αραιής διακρίνουσας (sparse discriminant) [START_REF] Busé | Resultant of an equivariant polynomial system with respect to the symmetric group[END_REF], [START_REF] Dickenstein | Plane mixed discriminants and toric Jacobians[END_REF], [START_REF] Emiris | Sparse Discriminants and Applications[END_REF], με χρήση της δομής των εξισώσεων. Επιπλέον μελετήθηκε και βρέθηκε κλειστός τύπος για τον βαθμό της διακρίνουσας και της απαλοίφουσας πολυωνυμικών εξισώσεων καθώς και η μεταξύ τους σχέση.

Ειδικότερα, διενεργήθηκε μελέτη τύπων για τον βαθμό της αραιής (μεικτής) διακρίνουσας και της αραιής απαλοίφουσας πολυωνυμικών εξισώσεων. Ο σκοπός της μελέτης αυτής είναι να διερευνηθεί ο τρόπος υπολογισμού της αραιής διακρίνουσας ενός καλώς ορισμένου συστήματος μέσω ενός τύπου που την συνδέει με την αραιή απαλοίφουσα ενός υπερπροσδιορισμένου πολυωνυμικού συστήματος, εξετάζοντας τα αραιά πολυώνυμα μέσω της θεωρίας των πολυτόπων του Νεύτωνα. Στα πλαίσια της μελέτης αυτής προέκυψαν δύο ερευνητικές εργασίες [START_REF] Emiris | Sparse Discriminants and Applications[END_REF], [START_REF] Dickenstein | Plane mixed discriminants and toric Jacobians[END_REF], οι οποίες περιγράφονται αναλυτικά στα κεφάλαια 4 και 6. Στο κεφάλαιο 4 μελετάται η σχέση της αραιής διακρίνουσας και της απαλοίφουσας με έμφαση στις εφαρμογές της διακρίνουσας. Μελετάται η σχέση της αραιής διακρίνουσας με την αραιή απαλοίφουσα του συστήματος των πολυωνύμων επαυξημένου με τον Τορικό Ιακωβιανό πίνακα του συστήματος. Η σχέση αυτή οδηγεί σε έναν τύπο για την αραιή διακρίνουσα, ο οποίος επιτρέπει τον υπολογισμό της αποτελεσματικά, χωρίς την εισαγωγή νέων μεταβλητών, όπως γίνεται με τη μέθοδο του Cayley. Δίνεται επίσης μία απόδειξη για τον συνολικό βαθμό της αραιής διακρίνουσας 2 πολυωνύμων, καθώς και ένας τύπος για την αραιή διακρίνουσα όταν ένα εκ των πολυωνύμων παραγοντοποιείται, χρησιμοποιώντας τα πολύτοπα του Νεύτωνα.

Στο κεφάλαιο 5 περιγράφεται η μελέτη που διενεργήθηκε , πάνω στην διακρίνουσα των ομογενών συμμετρικών πολυωνύμων, δηλαδή των αναλλοίωτων συστημάτων κάτω από την δράση της συμμετρικής ομάδας. Αναζητήθηκε και βρέθηκε κλειστός τύπος για τον υπολογισμό της απαλοίφουσας και της διακρίνουσας τέτοιου συστήματος.

Το δεύτερο πρόβλημα το οποίο αντιμετώπισε είναι το NP-δύσκολο πρόβλημα του υπολογισμού της διάσπασης πολυτόπων κατά Minkowski με χρήση προσεγγιστικών [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF] και αλγορίθμων ακριβείας [START_REF] Emiris | On the space of minkowski summands of a convex polytope[END_REF], καθώς και η μελέτη του προβλήματος του αθροίσματος υποσυνόλων (subset sum) σε αυθαίρετη διάσταση [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF]. Στο κεφάλαιο 7 μελετάται και προτείνεται αλγόριθμος για τον υπολογισμό όλων των μη τετριμμένων, ανάγωγων διασπάσεων κατά Minkowski, ενός οποιουδήποτε κυρτού πολυτόπου διάστασης d, το οποίο έχει κορυφές με ακέραιες συντεταγμένες. Για τον υπολογισμό αυτό μελετήθηκε ο κώνος όλων των συνδυαστικά ισοδύναμων πολυτόπων. Η υλοποίηση δίνεται σε Sage.

Στο κεφάλαιο 8 μελετώνται δύο NP-δύσκολα προβλήματα: το πρόβλημα της διάσπασης κατά Minkowski των ακέραιων πολυτόπων στο επίπεδο και το πρόβλημα του αθροίσματος υποσυνόλων (Subset sum) σε αυθαίρετη διάσταση (kD-SS). Στο πρόβλημα απόφασης δίνεται ένα σύνολο S από διανύσματα διάστασης k, ένα διάνυσμα στόχος t και πρέπει να αποφασιστεί αν υπάρχει ένα υποσύνολο του S το οποίο αθροίζει στο t. Στο αντίστοιχο πρόβλημα βελτιστοποίησης ζητείται υποσύνολο ώστε το αντίστοιχο άθροισμα να προσεγγίζει το διάνυσμα στόχο. Αποδεικνύουμε μέσω αναγωγής από το Set Cover ότι για γενική διάσταση k το αντίστοιχο πρόβλημα βελτιστοποίησης kD-SS-opt δεν είναι ΑPX παρόλο που το κλασικό πρόβλημα 1D-SS-opt έχει PTAS. Η προσέγγισή μας σχετίζει το kD-SS με το πρόβλημα του Closest Vector. Παρουσιάζουμε έναν O(n 3 /ϵ 2 ) προσεγγιστικό αλγόριθμο για το 2D-SS-opt, όπου n είναι ο πληθάριθμος του S και ϵ > 0 φράσσει το αθροιστικό σφάλμα και σχετίζεται με μία ιδιότητα του δοθέντος αντικειμένου από τον χρήστη. Μετά από μία αναγωγή από το πρόβλημα βελτιστοποίησης της διάσπασης κατά Minkowski στο 2D-SS-opt προσεγγίζουμε το εξής: Δοθέντος ενός πολυγώνου Q και μίας παραμέτρου ϵ > 0 , υπολογίζουμε τα δύο πολύτοπα της διάσπασης και , όπου

Q ′ = A + B είναι τέτοιο ώστε το Q και το Q ′ διαφέρουν κατά O(ϵD), όπου D η διάμετρος του Q, ή η Hausdorff απόσταση του Q από το Q ′ είναι O(ϵD). Η υλοποίηση διατίθεται στο Github.

ABSTRACT

The contribution of the thesis is threefold. We worked on Problems in the areas of algebraic algorithms, computational geometry and algebraic combinatorics. The first Problem is computing the discriminant, when the system's dimension varies. Thus solving polynomial equations and systems by exploiting the structure and sparseness of them have been studied. Specifically, closed formulas for the degree of the sparse (mixed) discriminant and the sparse resultant of polynomial equations have been studied, as well as relationships between them. Closed formulas when one of the polynomials factors in the context of the theory of sparse elimination using the Newton polytope have been proposed. The main purpose is to facilitate the computation of the sparse (or mixed) discriminant of a well-constrained polynomial system and to generalize the formula that connects the mixed discriminant with the sparse resultant. The results of this work are presented in Chapter 4 and 6 of the thesis and have been published in [START_REF] Emiris | Sparse Discriminants and Applications[END_REF] and [START_REF] Dickenstein | Plane mixed discriminants and toric Jacobians[END_REF] . In Chapter 5 we are given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols. We then prove that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant of a multivariate homogeneous symmetric polynomial. The results of this work have been published in [START_REF] Busé | Resultant of an equivariant polynomial system with respect to the symmetric group[END_REF].

The second Problem is computing the Minkowski decomposition of a polytope and the third one was the problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension.

Firstly, we present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope, using the cone of combinatorially equivalent polytopes. An implementation is given in sage. The results of this work are presented in Chapter 7 of the thesis and have been published in [START_REF] Emiris | On the space of minkowski summands of a convex polytope[END_REF] .

Secondly, we consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. Our approach relates kD-SS with the well studied Closest Vector Problem. On the positive side, we present a O(n 3 /ϵ 2 ) approximation algorithm for 2D-SS-opt, where n is the cardinality of the multiset and ϵ > 0 bounds the additive error in terms of some property of the input. We state two variations of this algorithm, which are more suitable for implementation. Employing a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former: For an input polygon Q and parameter ϵ > 0, we compute summand polygons A and B, where Q ′ = A + B is such that some geometric function differs on Q and Q ′ by O(ϵ D), where D is the diameter of Q, or the Hausdorff distance between Q and Q ′ is also in O(ϵ D). We conclude with experimental results based on our implementations. The results of this work are presented in Chapter 8 of the thesis and have been published in [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF], [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF].

Finally, in Chapter 9 we provide extensions and open problems.

SUBJECT AREA: Algebraic Algorithms, Computational Geometry and Algebraic Combinatorics KEYWORDS: Discriminant, Resultant, Decomposition, Polytopes, Multidimensional Subset Sum, Approximation Algorithms

ΣΥΝΟΠΤΙΚΗ ΠΑΡΟΥΣΙΑΣΗ ΤΗΣ ΔΙΔΑΚΤΟΡΙΚΗΣ ΔΙΑΤΡΙΒΗΣ

Η διδακτορική διατριβή της Άννας Καρασούλου επικεντρώνεται στην επίλυση πολυωνυμικών συστημάτων χρησιμοποιώντας εργαλεία από την αλγεβρική και την συνδυαστική γεωμετρία. Η χρήση συνδυαστικών μεθόδων κατέστη απαραίτητη για την εκμετάλλευση της δομής και της αραιότητας των πολυωνυμικών εξισώσεων. Περιγράφονται επίσης γεωμετρικοί αλγορίθμοι για την διάσπαση πολυτόπων κατά Minkowski, με απώτερη εφαρμογή την παραγοντοποίηση των αντίστοιχων πολυωνύμων στο πλαίσιο της εκμετάλλευσης της αραιότητάς τους.

Το πρόβλημα του υπολογισμού της αραιής απαλοίφουσας και της αραιής διακρίνουσας:

Οι πολυωνυμικές εξισώσεις και τα αντίστοιχα συστήματά τους εμφανίζονται σε πλειάδα επιστημονικών και τεχνολογικών εφαρμογών και η επίλυσή τους αποτελεί θεμελιώδες πρόβλημα της Υπολογιστικής Άλγεβρας. Η απαλοίφουσα ενός συστήματος πολυωνυμικών εξισώσεων είναι ένα νέο πολυώνυμο στους συντελεστές του συστήματος, ο μηδενισμός του οποίου αποτελεί αναγκαία και επαρκή συνθήκη ύπαρξης ριζών. Η διακρίνουσα αποτελεί ένα θεμελιώδες εργαλείο στην εξέταση των πολυωνυμικών συστημάτων. H σχέση της με την απαλοίφουσα είναι άρρηκτη. Για παράδειγμα, η διακρίνουσα ενός πολυωνύμου σε μία μεταβλητή αντιστοιχεί στην απαλοίφουσα του πολυωνύμου και της παραγώγου του.

Η θεωρία αραιής αλγεβρικής απαλοιφής ασχολείται με τη μελέτη της απαλοίφουσας (και της διακρίνουσας), για τη μελέτη και τον υπολογισμό των ριζών πολυωνυμικών συστημάτων σε τορικές ποικιλότητες (varieties). Αυτή η θεωρία έχει τις απαρχές της στην δουλειά των Gel'fand, Kapranov και Zelevinsky. Οι μέθοδοι που χρησιμοποιούμε εκμεταλλεύονται την στενή σχέση αλγεβρικής και συνδυαστικής γεωμετρίας, όπως αυτή εκφράζεται μέσω του πολύτοπου του Νεύτωνα ενός πολυωνύμου. Η κ. Καρασούλου μελέτησε συστήματα πολλών μεταβλητών αραιών πολυωνύμων.

Κατά το διάστημα 2011-2013 έγινε μελέτη πάνω στην επίλυση πολυωνυμικών εξισώσεων και συστημάτων με εκμετάλλευση της δομής και της αραιότητάς τους. Ειδικότερα, διενεργήθηκε μελέτη τύπων για τον βαθμό της αραιής (μεικτής) διακρίνουσας και της αραιής απαλοίφουσας πολυωνυμικών εξισώσεων. Ο σκοπός της μελέτης αυτής είναι να διερευνηθεί ο τρόπος υπολογισμού της αραιής διακρίνουσας ενός καλώς ορισμένου συστήματος μέσω ενός τύπου που συνδέει την αραιή διακρίνουσα με την αραιή απαλοίφουσα ενός υπερπροσδιορισμένου πολυωνυμικού συστήματος, εξετάζοντας τα αραιά πολυώνυμα μέσω της θεωρίας των πολυτόπων του Νεύτωνα. Στα πλαίσια της μελέτης αυτής προέκυψαν δύο ερευνητικές εργασίες. Η εργασία με τίτλο «Plane mixed discriminants and toric Jacobians» [START_REF] Dickenstein | Plane mixed discriminants and toric Jacobians[END_REF], παρουσιάστηκε στο συνέδριο SIAM Conference on Applied Algebraic Geometry, Colorado, USA. Στην εργασία με τίτλο «Sparse Discriminants and Applications» [START_REF] Emiris | Sparse Discriminants and Applications[END_REF] περιγράφεται η σχέση της αραιής διακρίνουσας και της απαλοίφουσας με έμφαση στις εφαρμογές της διακρίνουσας. Μελετάται η σχέση της αραιής διακρίνουσας με την αραιή απαλοίφουσα του συστήματος των πολυωνύμων επαυξημένου με τον Τορικό Ιακωβιανό πίνακα του συστήματος. Η σχέση αυτή οδηγεί σε έναν τύπο για την αραιή διακρίνουσα, ο οποίος επιτρέπει τον υπολογισμό της αποτελεσματικά, χωρίς την εισαγωγή νέων μεταβλητών, όπως γίνεται με τη μέθοδο του Cayley. Δίνεται επίσης μία απόδειξη για τον συνολικό βαθμό της αραιής διακρίνουσας δύο πολυωνύμων, καθώς και ένας τύπος για την αραιή διακρίνουσα όταν ένα εκ των πολυωνύμων παραγοντοποιείται, χρησιμοποιώντας τα πολύτοπα του Νεύτωνα.

Το διάστημα 2014-2016 η κ. Άννα Καρασούλου επισκέφθηκε δύο φορές το INRIA Sophia-Antipolis στην Γαλλία και διενεργήθηκε μελέτη, πάνω στην διακρίνουσα των ομογενών συμμετρικών πολυωνύμων πολλών μεταβλητών και βρέθηκε κλειστός τύπος για τον υπολογισμό της και της διάσπασής της. Επιπλέον μελετήθηκαν συστήματα n ομογενών πολυωνύμων n μεταβλητών, τα οποία είναι αναλλοίωτα κάτω από την δράση της συμμετρικής ομάδας n στοιχείων. Αναζητήθηκε και βρέθηκε κλειστός τύπος για τον υπολογισμό της απαλοίφουσας τέτοιου συστήματος. Αποδείχθηκε ότι η απαλοίφουσα μπορεί να διασπαστεί ως γινόμενο απαλοιφουσών, οι οποίες δίνονται σε όρους πηλίκα διαφορών. Επιπλέον βρέθηκε συνδυαστικός τύπος για τον ακριβή υπολογισμό των πολλαπλοτήτων των παραγόντων που εμφανίζονται στην διάσπαση. Μία πρώτη έκδοση της εργασίας αυτής παρουσιάστηκε στο συνέδριο Applications of Real Algebraic Geometry (ARAG), Aalto University, Finland. Στην συνέχεια δημοσιεύτηκε η ερευνητική εργασία με τίτλο «Resultant of an equivariant polynomial system with respect to the symmetric group» [START_REF] Busé | Resultant of an equivariant polynomial system with respect to the symmetric group[END_REF], η οποία παρουσιάστηκε επίσης στο διεθνές Εργαστήριο Applications of Computer Algebra (ACA), Kalamata, Greece.

Το πρόβλημα της διάσπασης ενός κυρτού πολυγώνου με ακέραιες κορυφές και προβλήματα βελτιστοποίησης:

Δοθέντος ενός κυρτού πολυγώνου με ακέραιες κορυφές εξετάζουμε αλγορίθμους που μας επιτρέπουν να το διασπάσουμε σε δύο άλλα κυρτά πολύγωνα τέτοια ώστε το διανυσματικό άθροισμά τους, ή άθροισμα Minkowski, να ισούται με το αρχικό πολύγωνο. Υπό το πρίσμα της αλγεβρικής γεωμετρίας τα (κυρτά) πολύτοπα χαρακτηρίζουν με μεγαλύτερη ακρίβεια ένα πολυώνυμο από ό,τι ο συνολικός του βαθμός. Για το λόγο αυτό αποτελούν ένα θεμελιώδες αντικείμενο μελέτης στην θεωρία αραιής αλγεβρικής απαλοιφής. Η βασική κατασκευή πολυτόπων είναι το πολύτοπο του Νεύτωνα που ορίζεται για κάθε πολυώνυμο και εκφράζει την αραιότητα του πολυωνύμου. Το πρόβλημα της διάσπασης των πολυτόπων συνδέεται με την παραγοντοποίηση του πολυτόπου του Νεύτωνα ενός πολυωνύμου, το οποίο είναι θεμελιώδες πρόβλημα στην μελέτη και των υπολογισμό των πολυωνυμικών συστημάτων με πολλές μεταβλητές.

Το διάστημα 2015-2017 πραγματοποιήθηκε μελέτη για την διάσπαση των πολυτόπων κατά Minkowski. Στα πλαίσια της μελέτης αυτής προέκυψαν οι ακόλουθες ερευνητικές εργασίες.

Δημοσιεύτηκε η ερευνητική εργασία με τίτλο «Approximate subset sum and Minkowski decomposition of polytopes» [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF], [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF]. Στην εργασία αυτήν μελετάμε δύο N P -δύσκολα προβλήματα: το πρόβλημα της διάσπασης κατά Minkowski των ακέραιων πολυτόπων στο επίπεδο και το πρόβλημα του αθροίσματος υποσυνόλων (Subset sum) σε αυθαίρετη διάσταση (kD-SS). Στο πρόβλημα απόφασης δίνεται ένα σύνολο S από διανύσματα διάστα-σης k, ένα διάνυσμα στόχος t και πρέπει να αποφασιστεί αν υπάρχει ένα υποσύνολο του S το οποίο αθροίζει στο t. Στο αντίστοιχο πρόβλημα βελτιστο-ποίησης ζητείται υποσύνολο ώστε το αντίστοιχο άθροισμα να προσεγγίζει το διάνυσμα στόχο. Αποδεικνύουμε μέσω αναγωγής από το Set Cover ότι για γενική διάσταση k το αντίστοιχο πρόβλημα βελτιστοποίησης kD-SS-opt δεν είναι ΑPX παρόλο που το κλασικό πρόβλημα 1D-SS-opt έχει PTAS. Η προσέγγισή μας σχετίζει το kD-SS με το πρόβλημα του Closest Vector. Παρουσιάζουμε έναν O(n 3 /ϵ 2 ) προσεγγιστικό αλγόριθμο για το 2D-SS-opt, όπου n είναι ο πληθάριθμος του S και ϵ > 0 φράσσει το αθροιστικό σφάλμα και σχετίζεται με μία ιδιότητα του δοθέντος αντικειμένου από τον χρήστη. Μετά από μία αναγωγή από το πρόβλημα βελτιστοποίησης της διάσπασης κατά Minkowski στο 2D-SS-opt προσεγγίζουμε το εξής: Δοθέντος ενός πολυγώνου Q και μίας παραμέτρου ϵ > 0 , υπολογίζουμε τα δύο πολύτοπα της διάσπασης και , όπου

Q ′ = A + B είναι τέτοιο ώστε το Q και το Q ′ διαφέρουν κατά O(ϵD), όπου D η διάμετρος του Q, ή η Hausdorff απόσταση του Q από το Q ′ είναι O(ϵD). Η υλοποίηση διατίθεται στο Github.
Παράλληλα πραγματοποιήθηκε μελέτη και προτείνεται αλγόριθμος για τον υπολογισμό όλων των μη τετριμμένων, ανάγωγων διασπάσεων κατά Minkowski, ενός οποιουδήποτε κυρτού πολυτόπου διάστασης d, το οποίο έχει κορυφές με ακέραιες συντεταγμένες. Για τον υπολο-γισμό αυτό μελετήθηκε ο κώνος όλων των συνδυαστικά ισοδύναμων πολυτόπων. Η υλοποίηση δίνεται σε Sage. Η εργασία με τίτλο « On the space of Minkowski summands of a convex polytope » [START_REF] Emiris | On the space of minkowski summands of a convex polytope[END_REF].

Γενικεύσεις και ανοιχτά προβλήματα

Από την διατριβή αυτήν προκύπτουν κάποια ανοιχτά προβλήματα τα οποία παραθέτουμε στην συνέχεια. Από την σκοπιά της Υπολογιστικής Άλγεβρας και της Συνδυαστικής ένα πρόβλημα θα ήταν η γενίκευση του κλειστού τύπου για την απαλοίφουσα ενός συστήματος n ομογενών πολυωνύμων σε n μεταβλητές τα οποία μένουν αναλλοίωτα κάτω από την δράση άλλης ομάδας συμμετρίας ή να μελετηθεί το ίδιο αποτέλεσμα, αλλά για πολλαπλά συμμετρικά πολυώνυμα. Όμοια θα μπορούσε να γενικευτεί και ο κλειστός τύπος της διακρίνουσας του κεφαλαίου 5. Επιπλέον ένα άλλο πρόβλημα θα ήταν η γενίκευση των τύπων της διακρίνουσας του κεφαλαίου 6 για οποιονδήποτε αριθμό μεταβλητών. Από την σκοπιά της Υπολογιστικής Γεωμετρίας και των Αλγεβρικών Αλγορίθμων υπάρχουν κάποια προβλήματα που προκύπτουν από τα κεφάλαια 7 και 8. Το πρώτο είναι δοθέντος ενός πίνακα A ∈ Z m×d and b ∈ Z m τέτοιου ώστε Ax ⩽ b είναι η H-αναπαράσταση του κυρτού ακεραίου πολυτόπου P b , να οριστούν και να υπολογιστούν οι ακέραιοι προσεγγιστικοί προσθεταίοι του. Το δεύτερο πρόβλημα είναι να εφαρμόσουμε αυτές τις μεθόδους σε αλγεβρικά προβλήματα όπως η προσεγγιστική παραγοντοποίηση των πολυωνύμων ή τον έλεγχο της παραγοντοποίησης.

To my Family for their continues love and support and especially to my husband Konstantinos Lentzos and my son Nikolaos Lentzos. The distances are shown and the furthest point is in distance αδ|v|. b) After the trim a few cells remain. Every vector in the cells will be deleted and "represented" by one of the black vectors shown. Notice that the size of each cell depends on the vector that creates it: the shorter the vector the smaller the cell. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

INTRODUCTION

In this thesis we worked on problems in the areas of algebraic algorithms, computational geometry and algebraic combinatorics. The first problem is computing the discriminant of a well-constrained sparse polynomial system. The second one is computing the Minkowski decomposition (MinkDecomp) of lattice polytopes and the third one is the problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension k.

Solving polynomial equations and systems by exploiting the structure and sparseness of them have been studied. The polynomial equations and their respective systems are shown on a various scientific and technological applications . Their solution is the fundamental problem of Computational Algebra and Computational Algebraic Geometry. Specifically, closed formulas for the degree of the sparse (mixed) discriminant and the sparse resultant of polynomial equations have been studied, as well as relationships between them.

Closed formulas when one of the polynomials factors in the context of the theory of sparse elimination using the Newton polytope have been proposed. The main purpose is to facilitate the computation of the sparse (or mixed) discriminant of a well-constrained polynomial system and to generalize the formula that connects the mixed discriminant with the sparse resultant. The above led to two research papers [START_REF] Emiris | Sparse Discriminants and Applications[END_REF] and [START_REF] Dickenstein | Plane mixed discriminants and toric Jacobians[END_REF] .

The paper [START_REF] Emiris | Sparse Discriminants and Applications[END_REF] describes the sparse (or mixed) discriminant and its applications. It also relates it to the sparse resultant of an overconstrained polynomial system, considering the sparse polynomials via the theory of Newton polytopes.

Especially we present our main results relating the mixed discriminant with the sparse resultant of two bivariate Laurent polynomials with fixed support and their toric Jacobian.

On our way, we deduced a general multiplicativity formula for the mixed discriminant when one polynomial factors as f = f ′ •f ′′ . This formula occurred as a consequence of our main result, Theorem 6.3.3, and generalized known formulas in the homogeneous case to the sparse setting. Furthermore, we obtained a new proof of the bidegree formula for planar mixed discriminants. This work is described in Chapter 4.

In [START_REF] Busé | Resultant of an equivariant polynomial system with respect to the symmetric group[END_REF] we are given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols. We then prove that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant of a multivariate homogeneous symmetric polynomial.

Discriminant is a very useful tool, but also very hard to compute. The factorization formula that we propose, in the case of symmetric polynomials, reduces the computations significantly. Taking advantage of the polynomial symmetries, the idea is that we gather together the same factors by using combinatorial exponents in the appearing resultants. This work is described in Chapter 5.

In the paper [START_REF] Dickenstein | Plane mixed discriminants and toric Jacobians[END_REF] the closed formula of sparse (or mixed) discriminant for Laurent poly-nomials with fixed support is proved. The relationship between the sparse (or mixed) discriminant of two bivariate Laurent polynomials with fixed support, with the sparse resultant of these polynomials and their toric Jacobian is also given. This helps to obtain a new proof for the bidegree of the discriminant as well as to establish a multiplicativity formula of the mixed discriminant, when one of the polynomials is factorized. This work is described in Chapter 6.

In [START_REF] Emiris | On the space of minkowski summands of a convex polytope[END_REF] we present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope, using the cone of combinatorially equivalent polytopes. An implementation is given in sage. This work is described in Chapter 7.

In [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF], [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF] we consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension k. In kD-SS, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. Our approach relates kD-SS with the well studied Closest Vector Problem. On the positive side, we present a O(n 3 /ϵ 2 ) approximation algorithm for 2D-SS-opt, where n is the cardinality of the multiset and ϵ > 0 bounds the additive error in terms of some property of the input. We state two variations of this algorithm, which are more suitable for implementation. Employing a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former: For an input polygon Q and parameter ϵ > 0, we compute summand polygons A and B, where

Q ′ = A + B is such that some geometric function differs on Q and Q ′ by O(ϵ D)
, where D is the diameter of Q, or the Hausdorff distance between Q and Q ′ is also in O(ϵ D). We conclude with experimental results based on our implementations. This work is described in Chapter 8.

At the last Chapter we provide extensions and open problems.

BACKGROUND

In this chapter we are giving some definitions and describe some problems that we will refer to in later chapters.

Preliminaries

A formal definition of the affine space is given below, while Marcel Berger in [START_REF] Berger | Geometry I[END_REF] explains that , "An affine space is nothing more than a vector space whose origin we try to forget about, by adding translations to the linear maps".

Definition 2.1.1. An affine space is a set X that admits a free transitive action of a vector space V . That is, there is a map

X × V → X : (x, v) → x + v,
called translation by the vector v, such that 1. Addition of vectors corresponds to composition of translations, i.e., for all x ∈ X and

u, v ∈ V, x + (u + v) = (x + u) + v.
2. The zero vector acts as the identity, i.e., for all x ∈ X, x + 0 = x.

3. The action is free, i.e., if for a given vector v ∈ V exists a point x ∈ X such that

x + v = x then v = 0.
4. The action is transitive, i.e., for all points x, y ∈ X exists a vector v ∈ V such that

y = x + v.
The dimension of X is the dimension of the vector space of translations, V .

The vector v in Condition 4 that translates the point x to the point y is by Condition 3 unique, and is often written as v = -→ xy or as v = y -x. We have in fact a unique map

X × X → V : (x, y) → y -x such that y = x + (y -x) for all x, y ∈ X. It furthermore satisfies 1. For all x, y, z ∈ X, z -x = (z -y) + (y -x).
2. For all x, y ∈ X and u, v

∈ V, (y + v) -(x + u) = (y -x) + v -u.
3. For all x ∈ X, x -x = 0.

4. For all x, y ∈ X, y -x = -(x -y). Definition 2.1.5. Let x 1 , . . . , x n be vectors in a real vector space, and let λ 1 , . . . , λ n be non-negative scalars in R.

Then λ 1 x 1 + • • • + λ n x n is called a conic combination of the vectors x 1 , . . . , x n . If, in addition, λ 1 + • • • + λ n = 1, then it is a convex combination of x 1 , . . . , x n .
Definition 2.1.6. A polyhedron (plur: polyhedra), or polyhedral set in R d is the intersection of a finite number of half-spaces.

Rather than enumerating a list of n pairs (a i , b i ) defining single inequalities, it is usual to define a n × d matrix A which has the different a i as its n line vectors, and a vector b ∈ R n with the b i , so that it is possible to write the polyhedron as: {x|Ax ⩽ b} Definition 2.1.7. Let S 1 , ..., S r be sets of vectors. We define their Minkowski sum, or vector sum, as the set of vectors which can be written as the sum of a vector of each set. Namely:

S 1 + • • • + S r := {x 1 + • • • + x r |x i ∈ S i , ∀i}.
The Minkowski sum is commutative and associative.

Geometrically, the Minkowski sum is the set of points covered by any translation of one set by a vector in the other one.

P = {λ 1 v 1 + • • • + λ n v n + µ 1 r 1 + • • • + µ m r m |λ 1 + • • • + λ n = 1, λ i , µ i ⩾ 0}.
As we can see, polyhedra can be described either as a set of inequalities or as a set of generators. These two representations are commonly called H-representation (for halfspace) and V-representation (for vertex). If the representation is minimal, the vectors v i and r i in the V-representation presented here are called vertices and rays. There are two natural restrictions of this theorem, by excluding either of the conical and convex combinations.

Theorem 2.1.9. (Minkowski-Weyl for cones) Any polyhedral cone is a finitely generated closed cone, and conversely. That is, P is a polyhedral cone if and only if there are vectors r 1 , . . . , r m of R d such that:

P = {µ 1 r 1 + • • • + µ m r m |µ i ⩾ 0}.
Let us now define our main object of study:

Definition 2.1.10. A polytope is a bounded polyhedron.

In other words a polytope is the convex hull of a finite set in R d . If the finite set is A = {m 1 , . . . , m l } ⊂ R d , then the polytope can be expressed as

Conv(A) = {λ 1 m 1 + • • • + λ l m l : λ i ⩾ 0, l ∑ i=1 λ i = 1}.
Q b = {(a 1 , . . . , a d ) ∈ R d : a i ⩾ 0, d ∑ i=1 a i ⩽ d}. Definition 2.1.13. A simplex is defined to be the convex hull of d + 1 points m 1 , . . . , m n+1 such that m 2 -m 1 , . . . , m d+1 -m 1 are a basis of R d .
We will now define the faces of a polytope P ⊂ R d . Let a non zero vector v ∈ R d . Definition 2.1.14. An affine hyperplane is defined by an equation of the form < m, v >= -a (the minus sing simplifies certain formulas). The supporting hyperplane has the property that the face of P determined by v is equal to

P v = P ∩ {m ∈ R d :< m, v >= -a P (v)} ̸ = ∅
and P lies in the half-space

P ⊂ {m ∈ R d :< m, v >⩾ -a P (v)}.
An other approach could be the following: Let P be a polytope and a, x be vectors of R d , a ̸ = 0 and b a scalar. We say (a, b) is a valid inequality for P , if the inequality < a, x >⩽ b holds for any point x ∈ P . Definition 2.1.16. For any valid inequality of a polytope, the subset of the polytope of vectors which are tight for the inequality is called a face of the polytope. That is, the set F is a face of the polytope P if and only if

F = {x ∈ P | < a, x >= b},
for some valid inequality (a, b) of P . The set of faces of a polytope P is denoted by F (P ).

Faces of polytopes can be partially ordered by inclusion, that is, some faces are contained in the others. The partially ordered set of faces of a polytope is called its face lattice. Definition 2.1.17. Let P be a polytope. The face lattice of the polytope, L(P ), is the set of faces F (P ) partially ordered by inclusion. That is, for F and G in L(P ), we have F ⩽ G if and only if F ⊂ G. When the term face lattice is used, it generally implies we are considering the faces as abstract elements ordered by inclusion, leaving aside geometrical notions.

Definition 2.1.18. If L(P ) is the face lattice of a polytope, a chain S is a subset of L(P ) which is totally ordered, that is, for any distinct F, G ∈ S, we have either F ⊂ G or G ⊂ F . The length of a chain is its cardinality minus one. If {F 1 , . . . , F n } is a chain, there is an ordering i 1 , . . . , i n such that

F i 1 ⊂ • • • ⊂ F in .
Theorem 2.1.19. (Face lattices) Let P be a polytope, and L(P ) its face lattice. Then we have the following:

• The face lattice L(P ) has a unique minimal element, which is the empty set, and a unique maximal element, which is P .

• The face lattice L(P ) is graded, which means that all maximal chains of L(P ) have the same length.

• Let F and G be two faces in L(P ). Then there is a unique maximal face F ∧ G they both contain, and a unique minimal face F ∨ G containing them.

Definition 2.1.20. Let P be a polytope, and F a face of P . The rank of F in the face lattice L(P ) is the length of the longest chain of L(P ) which has empty set and F as minimal and maximal elements respectively.

Notations

• A set A ⊂ R n is a configuration, if it is contained in Z n .
• The configurations A 1 , . . . , A n are called essential, if the affine dimension of the lattice ZA 1 + • • • + ZA k equals k -1 and for all I ⊊ {1, . . . , k} the affine dimension of the lattice generated by {A i : i ∈ I} is greater or equal than |I|.

• Dense or full configurations are those, who consists of all the lattice points in their convex hull.

Partitions

Let us now describe throw an example how we arrive to multinomial coefficients through binomial.

• Think of the binomial (

) = 10! 4!(10-4)! as the number of ways to distribute 10 objects to two recipients such that one receives 4 objects and the other the remaining 6.

• Writing ( 10 4, 6

) = 10! 4!6! instead of just ( 10 4
) makes explicit the number of objects each recipient receives.

• The multinomial coefficient ( 10 3, 4, 3 ) = 10! 3!4!3! counts the ways to distribute 10 objects to three recipients such that -the 1 st recipient receives 3 objects -the 2 nd recipient receives 4 objects -the 3 rd recipient receives 3 objects In general, the multinomial coefficient is defined as

( n λ 1 , λ 2 , . . . , λ k ) = n! λ 1 !λ 2 ! . . . λ k !
and equals the number of distributions of n distinct objects to k distinct the recipient i receives exactly λ i objects.

(α 1 + α 2 + • • • + α k ) n = ∑ λ 1 +•••+λ k =n ( n λ 1 , . . . , λ k ) ∏ 1⩽j⩽k α λ j j
What is a partition?

• λ is a partition of n , denoted as λ ⊢ n, If λ = (λ 1 , . . . , λ k ) is a weakly decreasing sequence of nonnegative integers,

λ 1 ⩾ • • • ⩾ λ k ⩾ 0 that sum up to n, i.e. λ 1 + • • • + λ k = n.
• The number of nonzero λ i 's is called the length of λ and is denoted as l(λ).

For example 4 has the following five partitions: Let us now Count partitions with certain specifications. The following is a fundamental example which leads to the definition of s λ 's How many partitions of 20 have

4 3 + 1 2 + 2 2 + 1 + 1 1 + 1 + 1 + 1 So (2,
• one block of size 5

• three blocks of size 4

• three blocks of size 1 ?

Seems that ( 20 1, 1, 1, 4, 4, 4, 5

) = 20! (1!) 3 (4!) 3 (5!) 1
has something to do with the answer! But it is too large to be the correct answer, since the recipients in ( )

are distinct instead of identical as we want! That is, the multinomial counts the following distributions as different: The equivalence principle comes to the rescue: We may arrange the assignment of • the blocks of size 1 to the first three recipients in any of 3! ways • the blocks of size 4 to the next three recipients in any of 3! ways • the blocks of size 5 to the last recipient in any of 1! ways and end up with an "equivalence partition". So there are ( 20 1, 1, 1, 4, 4, 4, 5

{17} → recipient 1 {3} → recipient 2 {11} → recipient 3 {2, 5,
) / 3!3!1!
partitions of 20 with blocks of the required description.

In a more formal way a partition is a sequence of weakly decreasing positive integers which is often written as λ = (λ 1 , . . . , λ k ). The number k is called the length of λ and will be denoted by l(λ). When ∑ k i=1 λ i = p we will say such a λ is a partition of p and write λ ⊢ p.

Given a partition λ ⊢ n, its associated multinomial coefficient is defined as the integer

( n λ 1 , λ 2 , . . . , λ l(λ) ) := n! λ 1 !λ 2 ! • • • λ l(λ) ! . ( 2.1)
It counts the number of distributions of n distinct objects to l(λ) distinct recipients such that the recipient i receives exactly λ i objects. In this counting, the objects are not ordered inside the boxes, but the boxes are ordered. To avoid the count of the permutations between the boxes having the same number of objects we have to divide (2.1) by the number of all these permutations. If s j denotes the number of boxes having exactly j objects, j ∈ [n], then this number of permutations is equal to ∏ n j=1 s j !. Thus, for any partition λ ⊢ n we define the integer

m λ := 1 ∏ n j=1 s j ! ( n λ 1 , λ 2 , . . . , λ l(λ)
)

.

(2.2)

Symmetric polynomials

An n-variable

polynomial f (x 1 , • • • , x n ) is called symmetric, if it
does not change by any permutation of its variables. The symmetric n-variable polynomials form a ring. A very common example of such polynomial is the Vandermonde determinant that we analyze below. Symmetric polynomials except for having their own interest, many times reduce a difficult polynomial problem to an easier one by studying it in a symmetric environment. This method is so often used in invariant theory, that is called symmetrization.

Definition 2.4.1. Symmetrization is therefore a process that converts any polynomial in n variables to a symmetric one in the same number of variables. Thus the symmetrization of a monomial

X a 1 1 • • • X an n is defined as S(X a 1 1 • • • X an n ) = ∑ σ∈Sn X a 1 σ(1) • • • X an σ(n) ,
where S n stands for the symmetric group.

Example 2.4.2. The symmetrization of

X 3 1 X 2 in 3 variables X 1 , X 2 , X 3 is just S(X 3 1 X 2 ) = X 3 1 X 2 + X 3 1 X 3 + X 3 2 X 3 + X 3 3 X 1 + X 3 2 X 1 .
Symmetric polynomials are widely used in statistics through bootstrapping processes [START_REF] Korolyuk | Mathematics and Its Applications[END_REF], in chemistry [START_REF] Barakat | Characteristic polynomials of chemical graphs via symmetric function theory[END_REF], in algebra [1], combinatorics [START_REF] Stanley | Some combinatorial properties of jack symmetric functions[END_REF], presentation theory of symmetric groups, general linear groups [START_REF] Green | The characters of the finite general linear groups[END_REF], and geometry [START_REF] Helgason | Differential geometry and symmetric spaces[END_REF].

For example, a distinguished family of symmetric polynomials called Schur polynomials, that are indexed by combinatorial objects called Young diagrams, describes the character theory of the symmetric group. The Schur polynomials and their generalizations such as Jack and Macdonald polynomials [START_REF]Symmetric Functions and Hall Polynomials[END_REF] are related to geometric objects such as symmetric spaces and flag varieties. They have also found connection with representation theory of super Lie algebras [START_REF] Sahi | The capelli problem for gl(m|n) and the spectrum of invariant differential operators[END_REF][START_REF] Sergeev | Calogero-moser operator and super jacobi polynomials[END_REF]. Besides their connection with representation theory, symmetric functions also have an application to mathematical physics. They are applied in Boson-Femion correspondence which are applied in string theory [START_REF] Green | Superstring theory: volume 2, loop amplitudes, anomalies and phenomenology[END_REF] and integrable systems [START_REF] Miwa | Solitons: Differential equations, symmetries and infinite dimensional algebras[END_REF]. There is also an interesting connection to quantum physics: the Jack polynomials are the eigenstates of the Hamiltonian of the quantum n-body problem.

Monomial symmetric polynomials

The monomial symmetric polynomial m a is determined by X a = X a 1 1 • • • X an n as the sum of all those obtained by symmetry from X a . Let us denote d its degree

a 1 + • • • + a n .
Consider n-tuples a = (a 1 , a 2 , . . . , a n ) and define the relation '' ∼ " between them, which expresses that one is a permutation of the other. Since m a = m β , when β is a permutation of a, one usually considers only those m a for which a 1 ⩾ a 2 ⩾ . . . ⩾ a n and add up to d; in other words the Young diagrams or partitions of d. Thus one can simply write

m α = ∑ β∼α X β
where b ranges over all distinct permutations of a.

Example 2.4.3. Given a partition a = (2, 1, 1) we get the corresponding symmetric polynomial

m (2,1,1) (X 1 , X 2 , X 3 ) = X 2 1 X 2 X 3 + X 1 X 2 2 X 3 + X 1 X 2 X 2 3 .
The monomial symmetric polynomials form a basis of the infinite dimensional vector space of symmetric polynomials and as a consequence every symmetric polynomial F can be written as a linear combination of them. To this point, it suffices to separate the different types of monomials occurring in F . In particular, if F has integer coefficients, then so will the linear combination.

Power sum symmetric polynomials

For each integer k ⩾ 0, the monomial symmetric polynomial m (k,0,...,0) (X 1 , . . . , X n ) is of special interest. It is called the k-th power sum symmetric polynomial and is denoted as

s k (X 1 , . . . , X n ), so s k (X 1 , . . . , X n ) = X k 1 + X k 2 + • • • + X k n
Any symmetric polynomial in X 1 , . . . , X n can be expressed as a polynomial expression with rational coefficients in the power sum symmetric polynomials s 1 (X

g(X) = n ∏ i=1 (X -X i ) = ∑ j∈Z (-1) j e j X n-j , ( 2.3)
whose coefficients are, up to sign, the elementary symmetric polynomials of X 1 , . . . , X n ,

e j = e j (X 1 , . . . , X n ) = ∑ 1⩽i 1 ⩽...⩽i j ⩽n j ∏ k=1 X i k , j ⩾ 0
and e j = 0, for j < 0 and j > n, e 0 = 1.

An equivalent definition of elementary symmetric polynomials is the following: The elementary symmetric polynomials are particular cases of monomial symmetric polynomials. For 0 ⩽ k ⩽ n, we define

e k (X 1 , . . . , X n ) = m α (X 1 , . . . , X n ),
where a = (1, . . . ,

1 k , 0, . . . , 0 n-k
).

If now we give to the ring of polynomials in X 1 , . . . , X n over Z a name, R = Z[X 1 , . . . , X n ], then the symmetric group S n of all permutations of {1, . . . , n} acts on R. That is a permutation σ ∈ S n gives rise to an automorphism a σ : S → S, defined as

a σ (g(X 1 , . . . , X n )) = g(X σ(1) , . . . , X σ(n) ), σ ∈ S n , f ∈ Z[X 1 , . . . , X n ]. A polynomial F ∈ R is called a symmetric polynomial if for all σ ∈ S n F (X 1 , . . . , X n ) = F (X σ(1) , . . . , X σ(n) ).
The polynomials in R that are invariant under the action form a subring of R, R 0 = {S n -invariant polynomials in R}.

The product form (2.3) shows that the e j are invariant under the action and hence Z[e 1 , . . . , e n ] ⊂ R 0 . In fact it is an equality. This theorem is also true for any ℜ commutative ring. Then every symmetric polynomial in ℜ[X 1 , . . . , X n ] is a polynomial in the elementary symmetric polynomials in a unique way.

In other words if F (X 1 , . . . , X n ) is symmetric, then there exists a unique polynomial q ∈ ℜ[X 1 , . . . , X n ] such that q(e 1 , . . . , e n ) = F (X 1 , . . . , X n ).

The discriminant of g in (2.3) is

∆(g) = ∏ 1⩽i<j⩽n (X i -X j ) 2 .
It is invariant under S n and lies in the coefficient field of g. Expressing ∆ in the terms of the e j is not so easy, although the proof of the Fundamental Theorem of Symmetric Polynomials shows an algorithm which determines the expression for a given S n -invariant polynomial in terms of the elementary ones. For example, in the case n = 2, the discriminant of g can be written in the terms of the elementary symmetric functions of the X i as

∆(g) = (X 1 -X 2 ) 2 = X 2 1 -2X 1 X 2 + X 2 2 = (X 1 + X 2 ) 2 -4X 1 X 2 = e 2 1 -4e 2 . The square root of the discriminant √ ∆ = ∏ 1⩽i<j⩽n (X i -X j ) is not symmetric. In fact √
∆ is fixed by A n but not by S n , where A n stands for the subset of S n that formed by even permutations and it is a group that called the alternating group. This polynomial, that we usually denote by V (X 1 , . . . , X n ) is the value of the Vandermonde determinant of the matrix:

     1 X 1 X 2 1 • • • X d-1 1 1 X 2 X 2 2 • • • X d-1 2 . . . . . . . . . . . . 1 X n X 2 n • • • X d-1 n      .

Complete homogeneous symmetric polynomials

A symmetric polynomial is homogeneous in the variables X 1 , . . . , X n of degree d, if every monomial in it has total degree d. The total degree d of a monomial cX a 1 1 , . . . , X an n is the sum of the exponents, that is

d = a 1 + • • • + a n .
For each nonnegative integer k, the complete homogeneous symmetric polynomial h k (X 1 , . . . , X n ) is the sum of all distinct monomials of degree k in the variables X 1 , . . . , X n . For instance

h 3 (X 1 , X 2 , X 3 ) = = X 3 1 + X 2 1 X 2 + X 2 1 X 3 + X 1 X 2 2 + X 1 X 2 X 3 + X 1 X 2 3 + X 3 2 + X 2 2 X 3 + X 2 X 2 3 + X 3 3 .
The polynomial h k (X 1 , . . . , X n ) is also the sum of all distinct monomial symmetric polynomials of degree k in X 1 , . . . , X n , for instance for the given example

h 3 (X 1 , X 2 , X 3 ) = m (3) (X 1 , X 2 , X 3 ) + m (2,1) (X 1 , X 2 , X 3 ) + m (1,1,1) (X 1 , X 2 , X 3 ).
All symmetric polynomials in variables X 1 , . . . , X n can be built up from complete homogeneous ones h 1 (X 1 , . . . , X n ), . . . , h n (X 1 , . . . , X n ) via multiplications and additions.

For example, for n = 2, the relevant complete homogeneous symmetric polynomials are

h 1 (X 1 , X 2 ) = X 1 +X 2 , and h 2 (X 1 , X 2 ) = X 2 1 +X 1 X 2 +X 2 2 .
Thus the polynomial X 3 1 +X 3 2 -26 takes the form

X 3 1 + X 3 2 -7 = -2h 1 (X 1 , X 2 ) 3 + 3h 1 (X 1 , X 2 )h 2 (X 1 , X 2 ) -26.
An important aspect of complete homogeneous symmetric polynomials is their relation to elementary symmetric polynomials, which can be given as the identities

k ∑ i=0 (-1) i e i (X 1 , . . . , X n )h k-i (X 1 , . . . , X n ) = 0,
for all k > 0, and any number of variables n.

Since e 0 (X 1 , . . . , X n ) and h 0 (X 1 , . . . , X n ) are both equal to 1, one can isolate either the first or the last terms of these summations; the former gives a set of equations that allows to recursively express the successive complete homogeneous symmetric polynomials in terms of the elementary symmetric polynomials, and the latter gives a set of equations that allows doing the inverse. This implicitly shows that any symmetric polynomial can be expressed in terms of the h k (X 1 , . . . , X n ) with 1 ⩽ k ⩽ n: one first expresses the symmetric polynomial in terms of the elementary symmetric polynomials and then expresses those in terms of the mentioned complete homogeneous ones.

In contrast to the situation for the elementary and complete homogeneous polynomials, a symmetric polynomial in n variables with integral coefficients need not be a polynomial function with integral coefficients of the power sum symmetric polynomials.

Example 2.4.7. For n = 2, the symmetric polynomial

m (2,1) (X 1 , X 2 ) = X 2 1 X 2 + X 1 X 2 2
has the expression

m (2,1) (X 1 , X 2 ) = 1 2 s 1 (X 1 , X 2 ) 3 -1 2 s 2 (X 1 , X 2 )s 1 (X 1 , X 2 ).
For n = 3 one gets a different expression

m (2,1) (X 1 , X 2 , X 3 ) = X 2 1 X 2 + X 1 X 2 2 + X 2 1 X 3 + X 1 X 2 3 + X 2 2 X 3 + X 2 X 2 3 = s 1 (X 1 , X 2 , X 3 )s 2 (X 1 , X 2 , X 3 ) -s 3 (X 1 , X 2 , X 3 ).

Basics for Algorithms and their Running Time

Let two algorithms of input size n and their running times f (n) and g(n). That is f (n) and g(n) are functions from positive integers to positive reals. We define the Big-O notation and we say that f = O(g) or f grows no faster than g, if there is a constant c > 0 such that f (n) ⩽ c • g(n). The analog of ⩾ is defined as f = Ω(g) that means g = O(f ), and the analog of = is defined as f = Θ(g) that means f = O(g) and f = Θ(g). The rules that make f (n) in O(f (n)) as simple as possible are:

1. Multiplicative constants can omitted.

2. n a dominates n b if a > b.

3. Any exponential dominates any polynomial.

4. Any polynomial dominates any logarithm.

Problem 1. Mergesort

The Algorithm for sorting a list of numbers is the Algorithm 1: We are given a list of numbers L and we split it into two halves. We then recursively sort each half and then merge the two sorted sublists. This is a divide and conquer strategy.

Algorithm 1: mergesort input : A list of numbers L = [1, • • • , n] output: a sorted list L if n > 1: then return merge (mergeshort ( [1, • • • , ⌊ n 2 ⌋] ) , mergeshort ( [⌊ n 2 ⌋, • • • , n] ) ) else return L
In case we have as input two sorted lists L 1 , L 2 and we want to merge them into a single sorted list, we use the Algorithm 2, where • denotes concatenation.

The merge procedure does a constant amount of work per recursive call (provided the required array space is allocated in advance), for a total running time of O(k + l). Thus merge's are linear and merge sort is O(n log n).

Problem 2. Set Cover

Greedy algorithms build up a solution step by step, by choosing the next step that offers the most obvious and immediate benefit.

The greedy algorithm of Set Cover is the following:

Algorithm 2: merge input : A list of numbers L 1 = [1, • • • , k], L 2 = [1, • • • , l] output: a sorted list L if k = 0: then return L 2 = [1, • • • , l] if l = 0: then return L 1 = [1, • • • , k] if L 1 ⩽ L 2 : then return L 1 • merge ( L 1 = [2, • • • , k] , L 2 = [1, • • • , l] ) ) else return L 2 • merge ( L 1 = [1, • • • , k] , L 2 = [2, • • • , l] ) ) Algorithm 3: Set Cover input : A set of elements B; sets S 1 , • • • , S m ⊂ B. output: A selection of the S i whose union is B. cost : Number of sets picked. repeat
Pick the set S i with the largest number of uncovered elements. until until all elements of B are covered: ;

The greedy scheme is not optimal, but it is not far from optimal. In particular, if B contains n elements and the optimal cover consists of k sets, then greedy algorithm will use at most k ln n sets see [START_REF] Dasgupta | Algorithms[END_REF]. The ratio between the greedy algorithm's solution an the optimal solution varies from input but it is less than ln n. The maximum ratio is called approximation factor of the greedy algorithm.

NP-complete problems (or Hard problems)

Dynamic programming is a very powerful algorithmic paradigm in which a problem is solved by identifying a collection of subproblems and tackling them one by one, smallest first, using the answers to small problems to help figure out larger ones, until all of them are solved.

The defining characteristic of search problems is that there is an efficient checking algorithm C that takes as input the given instance I, the proposed solution S and outputs true if and only if S is a solution to instance I. The running time of C(I, S) is counted by a polynomial in |I|, the length of the instance. We denote the class of all search problems by NP.

Nondeterministic polynomial time (NP) problem means that a solution to any search problem can be found and veryfied in polynomial time by a nondeterministic algorithm. NP was original defined not as a class of search problems but as a class of decision problems, i.e. algorithmic questions that can be answered by yes or no.

The class of all search problems that can be solved in polynomial time is denoted by P. Problem 3. Knapsack We are given integer weights w 1 , • • • , w n and integer values v 1 , • • • , v n for n items. We are also given a weight capacity W and a target t (the former is present in the original optimization problem, the latter is added to make it search problem). We seek a set of items whose total weight is at most W and whose total value is at least t. If no such set exists, we should say so.

It is an NP-complete problem.

Problem 4. Subset Sum

Suppose that each item's value is equal to its weight (all given in binary) and the target t is the same as the capacity W . We seek a subset of a given set of integers that add up to exactly t. This problem is called Subset Sum and it is a special case of Knapsack.

CONTRIBUTIONS OF THIS THESIS

In [START_REF] Emiris | Sparse Discriminants and Applications[END_REF] we describe discriminants in a general context, and relate them to an equally useful object, namely the resultant of an overconstrained polynomial system. We discuss several relevant applications in geometric modeling so as to motivate the use of such algebraic tools in further geometric problems. We focus on exploiting the sparseness of polynomials via the theory of Newton polytopes and sparse elimination. See Chapter 4. The main result of [START_REF] Busé | Resultant of an equivariant polynomial system with respect to the symmetric group[END_REF] (Theorem 4) is to prove a general decomposition formula of the resultant of a S n -equivariant homogeneous polynomial system. This decomposition is given in terms of other resultants that are in principle easier to compute and that are expressed in terms of the divided differences of the input polynomial system. We emphasize that the multiplicity of each factor appearing in this decomposition is also given. The appearance of divided differences is not new in the context of S n -equivariant polynomial system since it allows to produce some invariants in a natural way (e.g. [START_REF] Faugére | Solving polynomial systems globally invariant under an action of symmetric group and application to the equillibria of n vortices in the plane[END_REF][START_REF] Perminov | Discriminants of symmetric polynomials[END_REF]). Another important point is that this formula is universal, that is to say that it remains valid (in particular it still has the correct geometric meaning) under any specialization of the coefficient ring of the input polynomial system. This kind of property is particularly important for applications in the fields of number theory and arithmetic geometry where the value of the resultant is as important as its vanishing.

The second main contribution of this paper is a decomposition of the discriminant of a homogeneous symmetric polynomial (Theorem 5). The work on this result was motivated by the unpublished note [START_REF] Perminov | Discriminants of symmetric polynomials[END_REF] by N. Perminov and S. Shakirov where a tentative formula is given without a complete proof. Another motivation was to improve the computations of discriminants for applications in convex geometry, following a paper by J. Nie where the boundary of the cone of non-negative polynomials on an algebraic variety is studied by means of discriminants [START_REF] Nie | Discriminants and non-negative polynomials[END_REF]. We emphasize that the discriminant formula is obtained as a byproduct of our first formula on the resultant of a S n -equivariant polynomial system. Therefore, it inherits the same features : it allows to split the discriminant into several resultants with multiplicities and it is universal. See Chapter 5 In [START_REF] Dickenstein | Plane mixed discriminants and toric Jacobians[END_REF] we mainly work in the case n = 2, where the results are more transparent and the basic ideas are already present, but all our results and methods can be generalized to any number of variables. This will be addressed in a subsequent paper [START_REF] Dickenstein | Mixed discriminants and toric jacobians[END_REF]. Consider for instance a system of two polynomials in two variables and assume that, the first polynomial factors as

f 1 = f ′ 1 • f ′′ 1 .
Then, the discriminant also factors and we thus obtain a multiplicativity formula for it, which we make precise in Corollary 6.4.1. This significantly simplifies the discriminant's computation and generalizes the formula in [START_REF] Busé | A computational approach to the discriminant of homogeneous polynomials[END_REF] for the classical homogeneous case. This multiplicativity formula is a consequence of our main result (Theorem 6.3.3 in dimension 2, see also Theorem 6.3.4 in any dimension) relating the mixed discriminant and the resultant of the given polynomials and their toric Jacobian (see Section 6.3 for precise definitions and statements). As another consequence of Theorem 6.3.3, we reprove, in Corollary 6.3.6, the bidegree formula for planar mixed discriminants in [START_REF] Cattani | Mixed discriminants[END_REF]. See Chapter 6. In the classical problem of MinkDecomp, which is NP-complete, we are seeking a pair of polytopes whose Minkowski sum equals the input polytope. In this work, we compute instead all possible Minkowski summands. In the first step, we compute the cone of combinatorially equivalent polytopes U (A) b , a subcone of U (A) whose rays and lines generate all the Minkowski summands of P b . Then, we appropriately shift these rays so that they correspond to integer Minkowski summands. We give an algorithm and its implementation in sage [START_REF] Stein | Sage Mathematics Software[END_REF] performing the computation of all Minkowski summands in any dimension d, extending ideas from [START_REF] Henk | Integral decompositions of polyhedra and some applications in mixed integer programming[END_REF]. See Chapter 7.

We introduce the kD-SS problem; it is clearly NP-complete. For its optimization version, we prove that it cannot be approximated efficiently within a constant factor, for general k ⩾ 2, hence it does not belong to APX, although the classic 1D-SS-opt has an FPTAS.

Next, we design algorithms with additive errors in the plane. We start with 2D-SS-opt: given a multiset S, |S| = n, target t and 0 < ϵ < 1, the algorithm returns, in O(n 3 ϵ -2 ) time, a subset of S whose vectors sum up to t ′ , such that dist(t, t ′ ) ⩽ OP T + ϵM n , where M n = max P n . We also describe two more approximation algorithms which are expected to have better experimental behavior; we implement them and report on experimental results.

Applying one of these algorithms yields an approximation algorithm for MinkDecomp (Section 8.4): If Q is the input polygon the algorithm returns polygons A and B whose Minkowski sum defines polygon

Q ′ such that vol(Q) ⩽ vol(Q ′ ) ⩽ vol(Q) + ϵD 2 , per(Q) ⩽ per(Q ′ ) ⩽ per(Q) + 2ϵD, i(Q) ⩽ i(Q ′ ) ⩽ i(Q) + ϵD 2 , where D is the diameter of Q. The Hausdorff distance of Q and Q ′ is bounded by d H (Q, Q ′ ) ⩽ ϵ/2D. See Chapter 8.

DISCRIMINANTS AND RESULTANTS

Polynomial algebra offers a standard, powerful, and robust approach to handle several important problems in geometric modeling and other areas. A key tool is the discriminant of a univariate polynomial, or of a well-constrained system of polynomial equations, which expresses the existence of multiple (or degenerate) roots. We describe discriminants in a general context, and relate them to an equally useful object, namely the resultant of an overconstrained polynomial system. We discuss several relevant applications in geometric modeling so as to motivate the use of such algebraic tools in further geometric problems. We focus on exploiting the sparseness of polynomials via the theory of Newton polytopes and sparse elimination.

Introduction

Polynomial algebra offers a standard approach to handle several problems in geometric modeling and other fields, which provides both powerful and robust methods. Polynomials arise in a variety of scientific and engineering applications, and can be manipulated either algebraically or numerically. Here we mostly focus on tools relevant for algebraic computation, but also useful in numerical calculations. In particular, the study and solution of systems of polynomial equations has been a major topic. Discriminants is a key tool when examining well-constrained systems, including the case of one univariate polynomial. Their theoretical study is a thriving and fruitful domain today, but they are also very useful in a variety of applications. Through the related software development, these algebraic tools can be applied in various practical questions.

The best studied discriminant is that of one polynomial in one variable, probably known since high school, where one studies the discriminant of a quadratic polynomial f (x) = ax 2 + bx + c, a ̸ = 0. Polynomial f has a double (real) root if and only if its discriminant

∆ = b 2 -4ac
is equal to zero. Equivalently, this can be defined as the condition for f (x) and its derivative f ′ (x) to have a common root:

∃ x : f (x) = ax 2 + bx + c = f ′ (x) = 2ax + b = 0 ⇔ ∆ = 0. (4.1)
One can similarly consider the discriminant of a univariate polynomial of any degree. If we wish to calculate the discriminant of a polynomial f of degree five in one variable, we consider the condition that both polynomial and its derivative vanish:

f (x) = ax 5 + bx 4 + cx 3 + dx 2 + ex + g = 0, f ′ (x) = 5ax 4 + 4bx 3 + 3cx 2 + 2dx + e = 0.
In this case, elimination theory reduces the computation of discriminant ∆ to the computation of a 9 × 9 Sylvester determinant, expressing the resultant of f, f ′ . If we develop this determinant, we encounter an instance of the fact that the number of its monomials increases exponentially with the input degree:

∆ = -2050a 2 g 2 bedc + 356abed 2 c 2 g -80b 3 ed 2 cg + 18dc 3 b 2 g e -746agdcb 2 e 2 + 144ab 2 e 4 c -6ab 2 e 3 d 2 -192a 2 be 4 d -4d 2 ac 3 e 2 + 144d 2 a 2 ce 3 -4d 3 b 3 e 2 -4c 3 e 3 b 2 -80abe 3 dc 2 + 18b 3 e 3 dc + 18d 3 acbe 2 + d 2 c 2 b 2 e 2 -27b 4 e 4 -128a 2 e 4 c 2 + 16ac 4 e 3 -27 a 2 d 4 e 2 + 256a 3 e 5 + 3125a 4 g 4 + 160a 2 gbe 3 c + 560a 2 gdc 2 e 2 + 1020 a 2 gbd 2 e 2 + 160ag 2 b 3 ed + 560ag 2 d 2 cb 2 + 1020ag 2 b 2 c 2 e -192 b 4 ecg 2 + 24ab 2 ed 3 g + 24abe 2 c 3 g + 144b 4 e 2 dg -6b 3 e 2 c 2 g + 14 4dc 2 b 3 g 2 -630dac 3 bg 2 -630d 3 a 2 ceg -72d 4 acbg -72dac 4 e g -4d 3 c 2 b 2 g -1600ag 3 cb 3 -2500a 3 g 3 be -50a 2 g 2 b 2 e 2 -3750a 3 g 3 dc + 2000a 2 g 3 db 2 + 2000a 3 g 2 ce 2 + 825a 2 g 2 d 2 c 2 + 2250a 2 g 3 b c 2 + 2250a 3 g 2 ed 2 -900a 2 g 2 bd 3 -900a 2 g 2 c 3 e -36agb 3 e 3 -1600 a 3 ge 3 d + 16d 3 ac 3 g -128d 2 b 4 g 2 + 16d 4 b 3 g -27c 4 b 2 g 2 + 108ac 5 g 2 + 108a 2 d 5 g + 256b 5 g 3 .
One univariate polynomial is the smallest well-constrained system. We can generalize the definition of discriminant to any well-constrained system of multivariate polynomials.

In this chapter we are concerned with systems of polynomials and, in particular, sparse polynomials, in other words polynomials with fixed support, or set of nonzero terms.

A related and equally useful tool is the resultant, or eliminant. The solvability of an overconstrained set of multivariate polynomials is equivalent to the vanishing of the resultant, which is again a polynomial in the input coefficients. The resultant generalizes the coefficient matrix of an overconstrained linear system and the Sylvester determinant of two polynomials in a single variable. We shall recall the (sparse) resultant, a fundamental object in sparse (or toric) elimination theory, and we shall connect it to the (sparse) discriminant. Here, sparsity means that only certain monomials in each of the n + 1 polynomials have nonzero coefficients. Resultants are described in the sequel and their relation to discriminants is explained.

It shall become obvious that computing the (mixed) discriminant is an elimination problem, much akin to resultants. Discriminant computation is NP-hard when the system's dimension varies. There have been several approaches for computing discriminants, based on Gröbner bases or resultants. Recently, in [START_REF] Emiris | Sparse implicitization by interpolation: Characterizing non-exactness and an application to computing discriminants[END_REF], they focused on computing the discriminant of a multivariate polynomial via interpolation, based on [START_REF] Emiris | An output-sensitive algorithm for computing projections of resultant polytopes[END_REF], which essentially leads to an algorithm for predicting the discriminant's Newton polytope, hence its nonzero terms. This yields a new, efficient, and output-sensitive algorithm which, however, remains to be juxtaposed in practice to earlier approaches.

The rest of this chapter is organized as follows. The next section gives some applications of the discriminant, while Section 4.3 provides some general information about sparse elimination theory and resultants. Section 4.4 gives a general description of the discriminant and its properties.

Applications

In this section, we present some applications of discriminants, in order to motivate their study. Some applications are analyzed in depth, but others are only listed so as to show the breadth of possible applicability.

The main geometric application comes from the fact that discriminants express special geometric configurations, such as tangency between curves in the plane. Consider the following system of two polynomials in two variables:

f 1 = ax 2 1 + bx 1 x 2 + cx 2 2 + dx 1 + ex 2 + g, f 2 = hx 2 1 + ix 1 x 2 + jx 2 2 + kx 1 + lx 2 + m.
The condition that the two quadrics f 1 , f 2 are tangent is equivalent to the condition that the system's discriminant ∆ vanishes, where ∆ is of degree 12 and has 3210 monomials in coefficients a, b, c, d, e, g, h, i, j, k, l, m. An interesting remark, which we shall investigate in Section 4.4, is that the discriminant of a well-constrained system can be reduced to that of a single univariate polynomial, albeit of higher degree. In this case, the system's discriminant equals the discriminant of

f = ax 2 1 x 3 + bx 1 x 2 x 3 + cx 2 2 x 3 + dx 1 x 3 + ex 2 x 3 + gx 3 + hx 2 1 x 4 + ix 1 x 2 x 4 +jx 2 2 x 4 + kx 1 x 4 + lx 2 x 4 + mx 4 .
Another geometric application of discriminants is in the computation of the Voronoi diagram of ellipses, or of general smooth convex closed sets, see Figure 4.1 (right). Expressing the Voronoi circle externally tangent to three given ellipses reduces to a discriminant computation. If the Voronoi circle of center (v 1 , v 2 ) has radius √ s, then for each of the three ellipses, we consider the resulting discriminant ∆ i expressing tangency between the i-th ellipse and the Voronoi circle, for i = 1, 2, 3. We thus get the following 3 × 3 polynomial system [START_REF] Emiris | Exact delaunay graph of smooth convex pseudo-circles: General predicates, and implementation for ellipses[END_REF]:

∆ 1 (v 1 , v 2 , s) = ∆ 2 (v 1 , v 2 , s) = ∆ 3 (v 1 , v 2 , s) = 0, see Figure 4.1 (left).
The above system has one common root that specifies the unique Voronoi circle, but has several other roots that correspond to other (complex) tritangent circles to the three ellipses.

For a line to be tangent to two ellipses, the discriminant of the polynomials, expressing tangency between each ellipse and an (unknown) line, should vanish. All the real roots of the discriminant are the values of the parameter that correspond to the tangency points, which in turn allows us to compute the implicit equations of all bitangent lines. There are four bitangents to two disjoint ellipses unless the latter constitute a degenerate situation.

The discriminant is encountered in further geometric applications, for example in the description of the topology of plane curves [START_REF] González-Vega | Efficient topology determination of implicitly defined algebraic plane curves[END_REF]. In real algebraic geometry, the number of real roots of a real polynomial is constant, when the coefficients vary on each connected component of the zero set (or zero locus) of the (sparse) mixed discriminant, given that for the number of real roots to increase, two complex roots should merge. Discriminants are thus used in solving systems of polynomial inequalities and in zerodimensional system solving [START_REF] Faugére | Classification of the perspective-three-point problem: Discriminant variety and real solving polynomial systems of inequalities[END_REF], in root classification and computation of real roots of square systems of sparse polynomials [START_REF] Dickenstein | Extremal real algebraic geometry and a-discriminants[END_REF], in detecting real roots for n-variate (n + 2)monomial polynomials with integer exponents [START_REF] Bihan | Faster real feasibility via circuit discriminants[END_REF], in the description of the topology of real algebraic plane curves [START_REF] González-Vega | Efficient topology determination of implicitly defined algebraic plane curves[END_REF], and in the determination of cusp points of parallel manipulators [START_REF] Moroz | On the determination of cusp points of 3-rpr parallel manipulators[END_REF].

In [START_REF] Emiris | Minkowski decomposition of convex lattice polygons[END_REF], based on precomputed discriminants, they classify, isolate with rational points, and compare the real roots of polynomials of degree up to 4. In [START_REF] Guárdia | Higher newton polygons in the computation of discriminants and prime ideal decomposition in number fields[END_REF] they present an algorithm for computing discriminants and prime ideal decomposition in number fields.

The algorithm computes the p-valuation of the index of a generating equation f (x) as well; in particular, it determines the discriminant of the number field, once one is able to factorize the discriminant of the defining equation. In [START_REF] Bosman | A polynomial with galois group sl[END_REF], a key point is to show that the univariate polynomial below, with rational coefficients, namely:

x 17 -5x 16 + 12x 15 -28x 14 + 72x 13 -132x 12 + 116x 11 - -74x 9 + 90x 8 -28x 7 -12x 6 + 24x 5 -12x 4 -4x 3 -3x -1 has Galois group SL 2 (F 16
). This is achieved by the use of discriminants and their factorization. Furthermore, in [START_REF] Faugére | Algebraic cryptanalysis of the pkc 2009 algebraic surface cryptosystem[END_REF] they break the Algebraic Surface Cryptosystem (ASC) proposed in 2009. The main idea is to decompose ideals deduced from the ciphertext in order to avoid to solve the section-finding problem. They achieve this by an algorithm that computes and factors resultants.

Another application is an algebraic problem, which arises from considering pairs of differential equations on the plane of the form

ẋ = P (x, y), ẏ = Q(x, y),
where P and Q are polynomials in x, y. To find the equilibrium points we have to find the intersections of the curves P (x, y) = 0 = Q(x, y) and also to decide whether they touch at these points, and whether the discriminant ∆ vanishes there. Lastly, discriminants can be found in applied physics, e.g. in dark matter search [START_REF] Cheng | Minimal kinematic constraints and mt2[END_REF]. Moreover, in [START_REF] Godwin | The precise determination of maxwell sets for cuspoid catastrophes[END_REF] are established the algebraic conditions for a polynomial to have a pair of minima that have a common horizontal tangent, by computing, among others, a resultant and giving a factorization of the discriminant of a polynomial. This condition is exactly that required by the Maxwell convention of catastrophe theory. The extremal monomials and coefficients of the discriminant have interesting combinatorial descriptions. This has important applications in singularity theory and number theory.

Let us conclude with the following example, which is an application of (sparse) mixed discriminants that concerns the determination of real roots.

Example 4.2.1. [START_REF] Dickenstein | A world of binomials[END_REF] The Wilkinson polynomial

W 20 = 20 ∏ i=1 (x + i) = 20 ∑ j=0 c j x j
is well known for its numerical instability [94]. It has 20 real roots, but the polynomial W 20 (x) + 10 -9 x 19 has only 12 real roots and 4 pairs of complex roots, which do not seem to have small imaginary part, as one of these pairs is approximately equal to -16.57173899 ± 0.8833156071i. On the other hand, if we subtract 10 -9 x 19 from W 20 we get a polynomial with 14 real zeros. This unstable behavior could be explained by the fact that the vector of coefficients (20!, . . . , 210, 1) of W 20 is very close not only to the variety (set) of ill-posed polynomials, but also very close to a singular point of this variety.

In [START_REF] Dickenstein | A world of binomials[END_REF], there are experiments with the following 2-dimensional family of polynomials of degree 20: W (a, b, x) := W 20 (x) + ax 19 + bx 18 .

The corresponding discriminant ∆(a, b) defines a singular curve traced inside the discriminant locus. The singularities of ∆(a, b) = 0 are close to the point a = b = 0, i.e., to the vector of coefficients of the W ilkinson polynomial. Considering the distance, not just to the variety of ill-posed problems, but also to its singular locus would correspond, in the case of conditioning of square m × m matrices in linear algebra, to consider not only the smallest and greatest singular values, but also the behavior of the intermediate ones.

Sparse elimination theory

This section introduces sparse (or toric) elimination theory and its main tool, the sparse resultant.

Classical elimination theory and the classical multivariate resultant have a long and rich history that includes such luminaries as Euler, Bézout, Cayley and Macaulay; see [START_REF] Cox | Using Algebraic Geometry[END_REF]Figure 4.2: The figure is by B. Mourrain using software Mathemagix [92], see also [START_REF] Dickenstein | A world of binomials[END_REF] 28 , 93]. Having been at the crossroads between pure and computational mathematics, it became the victim, in the second quarter of this century, of the polemic led by the promoters of abstract approaches. Characteristically, the third edition of van der Waerden's Modern Algebra has a chapter on elimination theory and resultants that has disappeared from later editions.

Moreover, when the number of variables exceeds four or five, elimination methods lead to matrices which are, of course, too large for hand calculations and quite demanding computationally. However, the advent of modern computers has revived this area. The last decade has seen efficient resultant-based solutions of certain algorithmic as well as applied problems. Some of these problems were impossible to tackle with other methods in real time. These areas include, among others, robotics [START_REF] Canny | The complexity of robot motion planning[END_REF], and geometric modeling [START_REF] Manocha | Algorithms for intersecting parametric and algebraic curves II: Multiple intersections[END_REF].

The classical (or projective) resultant of a system of n homogeneous polynomials in n variables vanishes exactly when there exists a common solution in projective space. The sparse (or toric) resultant of n + 1 polynomials in n variables characterizes solvability over a smaller space which coincides with affine space under certain genericity conditions. Sparse elimination theory concerns the study of resultants and discriminants associated with toric varieties, in other words varieties defined for a given set of support points. This theory has its origin in the work of Gel'fand, Kapranov and Zelevinsky on multivariate hypergeometric functions. Singularities of such functions are discriminants, whereas the denominator of rational hypergeometric functions is a product of resultants, that is, a product of special discriminants.

Let us start with some definitions: conv(A) denotes the convex hull of set A. Volume, denoted by Vol(•), is always considered normalized with respect to the lattice Z n , so that

Q ′ 1 = conv(A ′ 1 ), Q ′′ 1 = conv(A ′′ 1 ), Q 2 = conv(A 2 )
, and

Q 1 = conv(A 1 )
a primitive triangle or simplex has volume equal to 1. As usual

Q 1 + Q 2 denotes the Minkowski sum of Q 1 and Q 2 . The Newton polytope N (f ) of a nonzero polynomial f = ∑ a∈A⊂Z n c a x a , c a ̸ = 0,
is the polytope with integer vertices defined as the convex hull of A; the latter is the support of f and contains precisely the exponents occurring in f with non-zero coefficients. Sparsity is measured in geometric terms by the Newton polytope of the polynomial, but what does sparsity mean? The number of nonzero monomials is not necessarily small, but they are modeled by the Newton polytope, thus leading to rich theory, which exploits combinatorial ideas and properties. The main notion, of course, is that a polynomial system is characterized by those monomials in each of the polynomials that have nonzero coefficients. Here is an example.

Example 4.3.1. Consider specific polynomials f ′

1 , f ′′ 1 , f 2 and their supports, which are full dimensional in Z 2 as follows:

A ′ 1 = {(0, 0), (0, 1), (1, 0)}, A ′′ 1 = {(0, 0), (0, 1), (1, 0)}, A 2 = {(0, 0), (0, 1), (1, 0)}. Let f 1 = f ′ 1 • f ′ 1 , then its support is A 1 = A ′ 1 + A ′′ 1 = {(0, 0), (0, 1), (1, 0), ( 2
, 0), (0, 2), (1, 1)}. All Newton polytopes (here, polygons) can be seen in Figure 4.3.

Example 4.3.2. Consider polynomials f ′

1 , f ′′ 1 , f 2 and their supports, as follows: A ′ 1 = {(0, 0), (0, 1), (0, 2), (1, 0)}, A ′′ 1 = {(0, 0), (0, 1), (1, 0), (2, 0)}, and A 2 = {(0, 0), (0, 1), (0, 2), (1, 0), (2, 0), (2, 1), [START_REF] Apery | Elimination: le cas d'une variable[END_REF][START_REF] Apery | Elimination: le cas d'une variable[END_REF]

, (1, 2)}. If f 1 = f ′ 1 • f ′′ 1 ,

then its support is

A 1 = A ′ 1 + A ′′ 1 = {(0, 0), (0, 1)
, (1, 0), (2, 0), (0, 2), (1, 1), (2, 1), (0, 3), (1, 2), (2, 2), (3, 0)}. All Newton polytopes (here, polygons) can be seen in

Q ′ 1 = conv(A ′ 1 ), Q ′′ 1 = conv(A ′′ 1 )
, and

Q 1 = conv(A 1 )
Figure 4.5: The Newton polygons Q 2 = conv(A 2 ), and

Q 1 + Q 2 = conv(A 1 + A 2 )
The

mixed volume M V (Q 1 , . . . , Q n ) of n convex polytopes Q i in R n is
!Vol(Q 1 ), when Q 1 = • • • = Q n .
Mixed volume is multilinear with respect to scalar multiplication and Minkowski addition of the Q i 's.

The cornerstone of sparse elimination theory is the following theorem.

Theorem 1. [START_REF] Bernstein | The number of roots of a system of equations[END_REF] The mixed volume of the Newton polytopes of polynomials f 1 (x), . . . , f n (x) in n variables bounds the number of common solutions of f 1 (x) = 0, . . . , f n (x) = 0 in the algebraic torus (K * ) n , where K is an algebraically closed field of the coefficients. If the coefficients of the polynomials are sufficiently generic, then the number of common solutions equals the mixed volume.

This bound generalizes, to the sparse case, Bézout's classical bound, which is equal to the product of the n polynomials' total degrees, and bounds the number of solutions in n-dimensional complex projective space. For polynomials whose supports are simplices, as in Example 4.3.1, the mixed volume and Bézout's bound coincide.

Mixed volume can be computed in terms of Minkowski sum volumes:

M V n (Q 1 , . . . , Q n ) = n ∑ k=1 (-1) n-k ∑ I⊂{1,...,n},|I|=k Vol ( ∑ i∈I Q i ) .
This implies, for n = 2:

M V (Q 1 , Q 2 ) = Vol(Q 1 + Q 2 ) -Vol(Q 1 ) -Vol(Q 2 ). (4.2)
In general, this formula does not lead to efficient computation. Instead, an efficient algorithm and implementation has been developed in [START_REF] Canny | Efficient incremental algorithms for the sparse resultant and the mixed volume[END_REF].

Resultants

The strong interest in multivariate resultants is explained, because resultant-based methods have been found to be very efficient for solving certain classes of small and mediumsize problems, say of dimension up to 10. For a system of n + 1 arbitrary polynomial equations in n variables, it is a polynomial in the coefficients, hence it eliminates n variables. The resultant is defined when all polynomial coefficients are symbolic, but typically used when only some of them are symbolic.

One example is the determinant of the coefficient matrix of n + 1 linear polynomials. Unless the coefficients are very particularly chosen, the resultant vanishes for a particular specialization of all coefficients if and only if the given system has a non-trivial solution.

Another example is the Sylvester resultant, namely for n = 1. Then, the resultant equals the determinant of Sylvester's matrix. For generic polynomials f 1 (x), f 2 (x) of degrees one and two, respectively, Sylvester's matrix S is as follows:

{ f 1 (x) = a 1 x + a 0 f 2 (x) = b 2 x 2 + b 1 x + b 0 } and S =   a 1 a 0 0 0 a 1 a 0 b 2 b 1 b 0   . (4.
3)

The resultant equals det

S = a 2 1 b 0 + a 2 0 b 2 -a 0 a 1 b 1 .
Thus S is an instance of a resultant matrix, in other words a matrix whose determinant yields the resultant. The principal merit of resultant matrices is that they reduce the solution of a non-linear system to a matrix problem, where we can use an arsenal of numeric linear algebra techniques and software, see e.g. [START_REF] Cox | Using Algebraic Geometry[END_REF][START_REF] Dickenstein | Solving Polynomial Equations: Foundations, Algorithms, and Applications (Algorithms and Computation in Mathematics)[END_REF]. By construction, the existence of common solutions implies a decrease of matrix rank.

In most applications, we deal with well-constrained systems, namely systems of k polynomials in k unknowns. To obtain an overconstrained system, for which the resultant is defined, we should either add an extra polynomial or "hide" a variable in the coefficient field [START_REF] Cox | Using Algebraic Geometry[END_REF][START_REF] Dickenstein | Solving Polynomial Equations: Foundations, Algorithms, and Applications (Algorithms and Computation in Mathematics)[END_REF]93].

We now formally define the resultant polynomial of an overconstrained system. Definition 4.3.3. The resultant Res(f 0 , . . . , f n ) of n + 1 polynomials f 0 , . . . , f n in n variables is an irreducible polynomial in the coefficients of f 0 , . . . , f n , which vanishes whenever f 0 , . . . , f n have a common root.

The sparse resultant has an analogous definition when the f i are specified by their supports A i ⊆ Z n . Formally, the sparse resultant of f 0 , . . . , f n ), where each f i has support A i , is an irreducible polynomial with integer coefficients over the coefficients of the f i such that it vanishes precisely when the system

f 0 = f 1 = • • • = f n = 0 has a solution in (C * ) n .
The Newton polytope of the (sparse) resultant is called the resultant polytope, and it can be effectively computed by the algorithm in [START_REF] Emiris | An output-sensitive algorithm for computing projections of resultant polytopes[END_REF].

Discriminants

In this section we introduce discriminants of well constrained systems, provide some definitions and overview relevant properties in section 4.4.1.

Gel'fand, Kapranov and Zelevinsky [START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF] established the following definition, which we shall formally state later: The (sparse) mixed discriminant ∆(f 1 , . . . , f n ) of n polynomials in n variables is the irreducible polynomial in the coefficients of the f i which vanishes whenever the system f 1 = • • • = f n = 0 has a multiple root or, equivalently, a root which is not simple. Consider a system of two polynomials in two variables:

f 1 (x 1 , x 2 ) = a 0 + a 1 x 1 + a 2 x 2 1 + a 3 x 2 + a 4 x 2 2 + a 5 x 1 x 2 , f 2 (x 1 , x 2 ) = b 0 + b 1 x 1 + b 2 x 2 .
Their discriminant shows whether a common root is singular.

Let us formalize the definition of (sparse) discriminants. We consider n (finite) lattice configurations A 1 , . . . , A n in Z n and we denote by Q 1 , . . . , Q n their respective convex hulls. Let f 1 , . . . , f n be Laurent polynomials with support A 1 , . . . , A n respectively:

f i (x) = ∑ α∈A i c i,α x α , i = 1 . . . , n. (4.4)
We define the discriminantal variety to be the closure of the locus of coefficients c i,a for which the associated system of n polynomial equations in n unknowns x = (x 1 , . . . , x n ), over an algebraically closed field K, namely:

f 1 (x) = • • • = f n (x) = 0, (4.5)
has a non-degenerate multiple root.

Before the general definition we present the simplest case.

Example 4.4.1. Given a generic univariate polynomial of degree d,

P (z) = a 0 + a 1 z + • • • + a d z d , a d ̸ = 0,
there exists an irreducible polynomial ∆(P ) = ∆(a 0 , . . . , a d ) ∈ Z[a 0 , . . . , a d ], unique up to sign, called the discriminant, which verifies ∆(a 0 , . . . , a n ) ̸ = 0 if and only if all roots of P are simple for any specialization of the coefficients in C, with a d ̸ = 0. Thus ∆(a 0 , . . . , a n ) = 0 if and only if there exists z ∈ C with P (z) = P ′ (z) = 0. In fact, the corresponding Sylvester resultant R(P, P ′ ) equals a d ∆(P ).

This discriminant is an instance of both A-discriminant and mixed discriminant and mixed discriminant, which are defined below.

Geometrically, the discriminant hypersurface

{a = (a 0 , . . . , a d ) ∈ C d+1 : ∆(a) = 0}
is the projection over the first d + 1 coordinates of the intersection of the hypersurfaces

{(a, z) ∈ C d+2 : a 0 +a 1 z +• • •+a d z d = 0} and {(a, z) ∈ C d+2 : a 1 +2a 2 z +• • •+da d z d-1 = 0},
in other words the variable z is eliminated.

An isolated solution u ∈ (K * ) n is a nondegenerate multiple root if the n gradient vectors

( ∂f i ∂x 1 (u), . . . , ∂f i ∂x n (u)
) are linearly dependent, but any n -1 of them are linearly independent.

We now give the definition of (sparse) A-discriminant from [START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF]. It is related to some support set A, thus capturing the sparse structure of the data.

Definition 4.4.2. Consider the polynomial defined from system (4.4) for n = 1. We denote by ∆ A the (sparse) A-discriminant, which is the unique (up to sign) irreducible polynomial with integer coefficients, in the parameter coefficients c i,a , where we follow the previous notation. ∆ A vanishes whenever the hypersurface is not smooth. Otherwise we refer to set A as a defective support, and set ∆ A = 1.

Let A 1 , . . . , A n be pointsets in Z n , as specified for system (4.4). We define the (sparse) mixed discriminant from [START_REF] Cattani | Mixed discriminants[END_REF], which captures the structure in a given well-constrained polynomial system.

Definition 4.4.3. If the discriminantal variety is a hypersurface, we define the (sparse) mixed discriminant of system (4.5) to be the unique up to sign irreducible polynomial ∆ A 1 ,...,An with integer coefficients in the unknown parameters c i,a , which defines this hypersurface. Otherwise, we say that the system is defective and set ∆ A 1 ,...,An = 1.

We now relate the previous two notions with an important construction in algebraic combinatorics. Let A 1 , . . . , A n be supports in Z n , defining Laurent polynomials, then A shall be specified to be the corresponding Cayley matrix. This matrix is defined to ave 2n rows and m = ∑ n i=1 |A i | columns. We introduce n new variables y 1 , . . . , y n in order to encode the system f 1 = • • • = f n = 0 in a single polynomial with support in A. This is known as the Cayley trick and yields polynomial

ϕ(x, y) = y 1 f 1 (x) + • • • + y n f n (x).
The Cayley matrix is: We introduce two new variables a, b in order to encode the system

A =       1 0 . . . 0 0 1 . . . 0 . . . . . . . . . . . . 0 0 . . . 0 A 1 A 2 . . . A n       . By [18, Theorem 2.1], the mixed discriminant ∆ A 1 ,...,
h 1 = h 2 = 0 in a single polynomial, namely ϕ(x, y, a, b) = ah 1 (x, y) + bh 2 (x, y).
Then, A is the Cayley matrix associated to the supports A 1 , A 2 :

A =     1 1 1 0 0 0 0 0 0 1 1 1 6 0 0 0 3 1 0 3 1 6 0 0     ,
and the A-discriminant ∆ A (c) = ∆ A (c 11 , . . . , c 23 ) is the mixed discriminant of h 1 , h 2 . Now ∆ A (c) = 0 whenever there exists a common zero (x, y) ∈ K 2 , making both h 1 , h 2 vanish, which is not simple.

It turns out that ∆ A (c) is a polynomial of degree 90 in c, with 58 monomials and huge integer coefficients.

∆(f 1 ) = 1 a n Res d 1 ,d 1 -1 (f 1 , f ′ 1 )
For

f (x) = ax 2 + bx + c f ′ (x) = 2ax + b we find Res(f, f ′ ) = a b c 2a b 0 0 2a b = -a(b 2 -4ac) so that D = b 2 -4ac.
• The Newton polytope of f , N (f ), is the convex hull of the set of exponents of its monomials with non-zero coefficient.

• The discriminant polytope is

N (∆). f (x 1 , x 2 ) = 8x 2 + x 1 x 2 -24x 2 2 -16x 2 1 + 220x 2 1 x 2 - 34x 1 x 2 2 -84x 3 1 x 2 + 6x 2 1 x 2 2 -8x 1 x 3 2 + 8x 3 1 x 2 2 + 8x 3 1 + 18x 3 2 • It holds dim(N (∆)) = n -d + 1.
• Knowing N (∆), reduces the computation of ∆ to a linear algebra problem

Multiplicativity formulae for Sparse Resultants and Discriminants

In this section we review existing work on the discriminant degree, and on multiplicativity formulae for sparse resultants and discriminants.

We start with the necessary notation for a theorem on the degree of the mixed discriminant of two polynomials with fixed supports. A subset F ⊆ A is called face of A, if F is the intersection of A with a face of the polytope conv(A). We shall write Res(f 1 , . . . , f n ) and

∆(f 1 , . . . , f n ) without subscripts to imply Res A 1 ,...,An (f 1 , . . . , f n ) and ∆ A 1 ,...,An (f 1 , . . . , f n ).
Let π denote the projection to RA/RF , where F is a face of A. We set

u(F, A) := Vol ( conv(π(A)) -conv(π(A -F ))
)

.

If e 1 and e 2 are parallel edges in Q 1 and Q 2 with same orientation, that is, same inward normal direction, then we call them strongly parallel. Let E i denote the set of edges of A i and set

P := {(e 1 , e 2 ) ∈ E 1 × E 2 : e 1 is strongly parallel to e 2 }.
We write l(e) for the normalized length of an edge e with respect to the lattice

Z n . If v ∈ Vert(A 2 )
, where Vert(A 2 ) are the vertices of A 2 , we define its mixed multiplicity as follows:

mm(v) := M V (Q 1 , Q 2 ) -M V (conv(A 2 -{v}), Q 1 ).
Let us introduce polynomial ∆A 1 ,...,An = ∆ i(A 1 ,...,An) A 1 ,...,An defined as the power of the mixed discriminant ∆ A 1 ,...,An raised to the index

i(A 1 , . . . , A n ) = [Z n : ZA 1 + • • • + ZA n ].
The latter stands for the index of lattice ZA 1 + • • • + ZA n+1 in Z n , as a subgroup. In general, this index equals 1. Let the discriminant degree in the coefficients of the i-th input polynomial be denoted by

δ i = deg A i ( ∆A i ,A j ), i = 1, 2.
Then, the following theorem holds.

Theorem 2. [18]

Let A 1 and A 2 be full-dimensional supports in Z n . Then δ i equals

2 • Vol(Q j ) + 2 • M V (Q i , Q j ) - ∑ (e i ,e j )∈P
min{u(e i , A i ), u(e j , A j )}l(e j ) -

∑ v∈ Vert(A i ) mm(v),
where i = 1, 2 and j = 2, 1, in other words {i, j} = {1, 2}.

An explicit degree formula for the special cases of plane curves is also presented in [START_REF] Cattani | Mixed discriminants[END_REF]Corollary 3.15]. We correct this formula. The degree of ∆ A 1 ,A 2 can be computed as follows:

δ 1 = area(Q 1 + Q 2 ) + area(Q 1 ) -perimeter(Q 2 ), δ 2 = area(Q 1 + Q 2 ) + area(Q 2 ) -perimeter(Q 1 ),
where

Q i = conv(A i ), i = 1, 2, Q 1 + Q 2 is their Minkowski sum.
The area (like volume above) is normalized, so that a primitive triangle has area 1 and the perimeter of

Q i is the cardinality of ∂Q i ∩ Z 2 .
Computing resultants and discriminants is usually a computationally hard task. However, if one polynomial factors as

f 1 = f ′ 1 • f ′′ 1
, both resultant and discriminant factors, and we thus obtain a multiplicativity formula. This significantly simplifies the corresponding computation.

Let us recall the case when one polynomial factors as a product of two polynomials, in the case of resultants. The multiplicativity formula for sparse resultants can be found in [80, Proposition 7.1], see also [START_REF] Sombra | A poisson formula for the sparse resultant[END_REF]Corollary 2.20]. Consider polynomials f 1 , . . . , f n+1 in variables x 1 , . . . , x n and let

f 1 = f ′ 1 • f ′′ 1 be a product of two polynomials, where all relevant supports are A 1 , A ′ 1 , A ′′ 1 , A 2 , . . . , A n+1 ⊆ Z n respectively. Then, Res(f ′ 1 f ′′ 1 , f 2 , . . . , f n+1 ) = Res(f ′ 1 , f 2 , . . . , f n+1 ) • Res(f ′′ 1 , f 2 , . . . , f n+1 ). (4.6)
We now pass to discriminants. The multiplicativity property of the discriminant in the case of (dense) homogeneous polynomials was already known to Sylvester [START_REF] Sturmfels | The newton polytope of the resultant[END_REF], and has been generalized by Busé and Jouanolou [START_REF] Busé | A computational approach to the discriminant of homogeneous polynomials[END_REF]. They prove that for any n, when all A i 's correspond to (the lattice points in) a dilate of the standard simplex and

A i = A ′ 1 + A ′′ 1 is the sum of two dilates of the simplex then, given polynomials f ′ 1 , f ′′ 1 , f 2 , . . . , f n with corresponding supports A ′ 1 , A ′′ 1 , A 2 , . . . , A n , ∆(f 1 , . . . , f n ) = ∆(f ′ 1 , . . . , f n ) • ∆(f ′′ 1 , . . . , f n ) • Res(f ′ 1 , f ′′ 1 , . . . , f n ) 2 .
Recall that the discriminant of n -1 homogeneous polynomials of degree 1 equals 1 by convention.

Theorem 3. [START_REF] Busé | A computational approach to the discriminant of homogeneous polynomials[END_REF][START_REF] Sturmfels | The newton polytope of the resultant[END_REF]

Let f ′ 1 , f ′′ 1 , f 2 , . . . , f n-1 be n homogeneous polynomials in R[x 1 , . . . , x n ], of degrees d ′ 1 , d ′′ 1 , d 2 , . . . , d n-1 ⩾ 1, respectively. Then ∆(f ′ 1 f ′′ 1 , f 2 , . . . , f n-1
) factors as follows:

(-1) d ′ 1 d ′′ 1 d 2 ...d n-1 • ∆(f ′ 1 , f 2 , . . . , f n-1 ) • ∆(f ′′ 1 , f 2 , . . . , f n-1 ) • Res(f ′ 1 , f ′′ 1 , f 2 , . . . , f n-1 ) 2 .
Our current work focuses on multiplicativity formulas for the mixed discriminant in the case n = 2, with fixed supports, always within the realm of sparse elimination theory [START_REF] Dickenstein | Plane mixed discriminants and toric Jacobians[END_REF], aiming at efficient algorithms. It turns out that a key issue is to understand the relation between the mixed discriminant of two bivariate Laurent polynomials, where one factors, and the sparse resultant of those three bivariate polynomials.

RESULTANT OF AN EQUIVARIANT POLYNOMIAL SYSTEM WITH RESPECT TO THE SYMMETRIC GROUP

Given a system of n ⩾ 2 homogeneous polynomials in n variables which is equivariant with respect to the symmetric group of n symbols, it is proved that its resultant can be decomposed into a product of several resultants that are given in terms of some divided differences. As an application, we obtain a decomposition formula for the discriminant of a multivariate homogeneous symmetric polynomial.

Introduction

The analysis and solving of polynomial systems are fundamental problems in computational algebra. In many applications, polynomial systems are structured and it is very useful to develop special methods in order to take into account structures. In this paper, we will focus on systems of n homogeneous polynomials f 1 , . . . , f n in n variables x 1 , . . . , x n that are globally invariant under the action of the symmetric group S n of n symbols. More precisely, we will assume that for any integer i ∈ {1, 2, . . . , n} and any permutation σ

∈ S n σ(f i ) := f i (x σ(1) , x σ(2) , . . . , x σ(n) ) = f σ(i) (x 1 , x 2 , . . . , x n ).
In the language of invariant theory these systems are called equivariant with respect to the symmetric group S n , or simply S n -equivariant (see for instance [97, §4] or [START_REF] Dieudonne | Invariant theory, old and new[END_REF]Chapter 1]). Some recent interesting developments based on Gröbner basis techniques of this kind of systems, when the coordinates of the roots are all distinct, can be found in [START_REF] Faugére | Solving polynomial systems globally invariant under an action of symmetric group and application to the equillibria of n vortices in the plane[END_REF]. In this work, we will study the resultant of S n -equivariant homogeneous polynomial systems in order to reveal their structure.

There are special cases for which a decomposition of the resultant of a S n -equivariant homogeneous polynomial system is known. In the case n = 2, any S 2 -equivariant homogeneous polynomial system is of the form

F {1} (x 1 , x 2 ) := a 0 x d 1 + a 1 x d-1 1 x 2 + • • • + a d x d 2 , F {2} (x 1 , x 2 ) := F {1} (x 2 , x 1 )
and one can show [2, Exercice 67] that there exists an irreducible polynomial

K d ∈ Z[a 0 , . . . , a d ] such that Res ( F {1} , F {2} ) = F {1} (1, 1)F {1} (1, -1)K 2 d = ( d ∑ i=0 a i ) ( d ∑ i=0 (-1) i a i ) K 2 d .
As another example, suppose n ⩾ 2, d = 1 and set F {i} (x 1 , . . . , x n ) = ax i + be 1 (x 1 , . . . , x n ), i = 1, . . . , n. Then, since the resultant of n linear forms in n variables is the determinant of the matrix of their associated linear system, it is a straightforward computation to show that Res ( F {1} , . . . , F {n} ) = a n-1 (a + nb).

The main result of this paper (Theorem 4) is to prove a general decomposition formula of the resultant of a S n -equivariant homogeneous polynomial system. This decomposition is given in terms of other resultants that are in principle easier to compute and that are expressed in terms of the divided differences of the input polynomial system. We emphasize that the multiplicity of each factor appearing in this decomposition is also given. The appearance of divided differences is not new in the context of -equivariant polynomial system since it allows to produce some invariants in a natural way (e.g. [START_REF] Faugére | Solving polynomial systems globally invariant under an action of symmetric group and application to the equillibria of n vortices in the plane[END_REF][START_REF] Perminov | Discriminants of symmetric polynomials[END_REF]). Another important point is that this formula is universal, that is to say that it remains valid (in particular it still has the correct geometric meaning) under any specialization of the coefficient ring of the input polynomial system. This kind of property is particularly important for applications in the fields of number theory and arithmetic geometry where the value of the resultant is as important as its vanishing.

The discriminant of a homogeneous polynomial is also a fundamental tool in the field of computer algebra. Although the discriminant of the generic homogeneous polynomial of a given degree is irreducible, for some class of polynomials it can be decomposed and this decomposition is always deeply connected to the geometric properties of the class of polynomials. The second main contribution of this paper is a decomposition of the discriminant of a homogeneous symmetric polynomial (Theorem 5). The work on this result was motivated by the unpublished note [START_REF] Perminov | Discriminants of symmetric polynomials[END_REF] by N. Perminov and S. Shakirov where a tentative formula is given without a complete proof. We emphasize that the discriminant formula is obtained as a byproduct of our first formula on the resultant of a S n -equivariant polynomial system. Therefore, it inherits the same features : it allows to split the discriminant into several resultants with multiplicities and it is universal.

The paper is organized as follows. In Section 5.2 we state the main result of this paper, namely a decomposition formula of a S n -equivariant homogeneous polynomial system, and we also introduce the notions and notations that are needed (divided differences and partitions). The proof of this decomposition formula is provided in Section 5.4. The decomposition formula of the discriminant of a homogeneous symmetric polynomial is proved and discussed in Section 5.3.

The main result

In order to describe our main result, we first need to introduce some notations on divided differences and partitions. Hereafter, R denotes an arbitrary commutative ring. In addition, for any integer p the set {1, 2, . . . , p} will be denoted by [p] and given a finite set I, |I| will stand for its cardinality.

Notations

Divided differences

Let P 1 , ..., P n be n homogeneous polynomials in R[x 1 , . . . , x n ] of the same degree d > 1.

Their divided differences are recursively defined by P {i} := P i for all i = 1, . . . , n and

P {i 1 ,...,i k } := P {i 1 ,...,i k-1 } -P {i 1 ,...,i k-2 ,i k } x i k-1 -x i k
for any given set of (distinct) integers

I := {i 1 , . . . , i k } ⊂ [n].
It is well known that P I depends on the set I and not on the order of the integers i 1 , . . . , i k for instance, as a consequence of the Newton's interpolation formula. Another important property is the following : if P I are polynomials for all I such that |I| = 2, that is to say if

x i -x j divides P {i} -P {j} for all i, j ∈ [n], (5.1)
then P I are homogeneous polynomials for all I ⊂ [n]. Indeed, for any J ⊂ [n] and any triple of distinct integers i, j, k such that J ∩ {i, j, k} = ∅, a straightforward application of the definition of divided differences yields the equality

(x i -x j )P J∪{i,j} -(x i -x k )P J∪{i,k} + (x j -x k )P J∪{j,k} = 0
which can be rewritten as

(x i -x k ) ( P J∪{i,j} -P J∪{i,k} ) = (x j -x k ) ( P J∪{i,j} -P J∪{j,k}
) .

From here the claimed property follows by induction on |I|. In addition, we observe that P I is an homogeneous polynomial of degree d -|I| + 1. In particular, P I = 0 if d + 1 < |I| ⩽ n and P I = P J for all subsets I and J of

[n] such that |I| = |J| = d + 1 ⩽ n.
Example 5.2.1. Any polynomial system of three linear homogeneous polynomials in 3 variables satisfying (5.1) is of the form   

P {1} = (a + d)x 1 + bx 2 + cx 3 P {2} = ax 1 + (b + d)x 2 + cx 3 P {3} = ax 1 + bx 2 + (c + d)x 3 .
and straightforward computations show that P {1,2} = P {1,3} = P {2,3} = d and P {1,2,3} = 0.

S n -equivariant polynomial systems

Consider a polynomial system of n homogeneous polynomials F {1} , . . . , F {n} ∈ R[x 1 , . . . , x n ] of the same degree d ⩾ 1 and assume that it is S n -equivariant, that is to say that for any integer i ∈ {1, 2, . . . , n} and any permutation σ

∈ S n σ(F {i} ) := F {i} (x σ(1) , x σ(2) , . . . , x σ(n) ) = F {σ(i)} (x 1 , x 2 , . . . , x n ). (5.2)
Equivalently, this means that for all i = 1, . . . , n

F {i} (x 1 , . . . , x n ) = d ∑ l=0 x l i S l (x 1 , . . . , x n )
where S l is a symmetric homogeneous polynomials in R[x 1 , . . . , x n ] of degree d -l for all l = 0, . . . , d. Suppose given in addition a partition λ ⊢ n and consider the morphism of polynomial algebras where j ∈ [n] is such that ρ λ (x j ) = y i . Moreover, these polynomials also satisfy (5.1) and hence their divided differences are also polynomials; we will denote them by F I λ (y 1 , . . . , y l(λ) ), where I ⊂ [l(λ)]. Moreover, we have the following 'lifting" property : Given

ρ λ : R[x 1 , . . . , x n ] → R[y 1 , . . . , y l(λ) ] F (x 1 , . . . , x n ) → F (y 1 , . . . ,
( F {i 1 ,...,i k } ) = F {σ(i 1 ),...,σ(i k )} . (5.3) Now, observe that if ρ λ (x i ) = ρ λ (x j ) then ρ λ (F {i} ) = ρ λ (F {j} ),
I = {i 1 , . . . , i k } ⊂ [n], define J = {j 1 , . . . , j k } ⊂ [l(λ)] by the equality ρ λ (x ir ) = y jr for all r ∈ [k]. Then, if |J| = |I| we have that ρ λ (F I (x 1 , . . . , x n )) = F J λ (y 1 , . . . , y l(λ) ).

The decomposition formula

We are now ready to state the main result of this paper, namely a decomposition of the multivariate resultant of a S n -equivariant system of homogeneous polynomials of the same degree.

Theorem 4. Assume n ⩾ 2 and suppose given a S n -equivariant system of homogeneous polynomials F {1} , . . . , F {n} ∈ R[x 1 , . . . , x n ] of the same degree d ⩾ 1. Then, we have that

Res ( F {1} , . . . , F {n} ) = R 0 × ∏ λ⊢n l(λ)⩽d Res ( F {1} λ , F {1,2} λ , . . . , F {1,2,...,l(λ)-1} λ , F {1,2,...,l(λ)} λ ) m λ where R 0 = 1 if d ⩾ n and R 0 = ( F {1,...,d+1} ) m 0 if d < n.
In this latter case, the integer m 0 is defined by

m 0 = nd n-1 - d ∑ k=1 A n,k B d,k where A n,k := ∑ λ⊢n l(λ)=k m λ , B d,k := e k-1 (d, d -1, d -2, . . . , d -k + 1)
and where e k-1 stands for the (k -1)-th elementary symmetric polynomial in k variables.

Before giving the proof of this theorem which is postponed at the end of the chapter, in Section 5.4, we make observations on some computational aspects of this theorem. First, we emphasize that the above formula is universal, meaning that it holds in the ring of coefficients of the polynomials system F {1} , . . . , F {n} over Z and that it remains valid under any specialization of these coefficients. For that purpose, we use the formalism of the resultant as developed in [START_REF] Jouanolou | Le formalism du resultant[END_REF] (see also [71, Chapter IX] and [START_REF] Cox | Using Algebraic Geometry[END_REF]Chapter 3]), in particular the resultant is normalized by setting Res(x 1 , . . . , x n ) = 1. Besides that, we will also use many computation rules and properties of the resultant in the proof of Theorem 4.

The number of resultant factors appearing in the decomposition formula is in relation with the cardinality of the set of partitions of n. This quantity has been extensively studied and we refer the interested reader to the classical book [START_REF]Symmetric Functions and Hall Polynomials[END_REF]. These resultant factors can be computed separately, for instance by means of the Macaulay formula, but the situation is even better : all these factors can be deduced from a very small number of resultant computations since they are actually universal with respect to the integers λ 1 , λ 2 , . . . , λ l(λ) defining a partition, providing l(λ) is fixed. As a consequence, all the resultant factors appearing in the decomposition formula given in Theorem 4 can be obtained as specializations of only min{n, d} resultant computations. The following example illustrates this property.

Example 5.2.2. Consider the polynomials

F {i} (x 1 , . . . , x n ) = ax 2 i + bx i e 1 (x 1 , . . . , x n ) + ce 1 (x 1 , . . . , x n ) 2 + de 2 (x 1 , . . . , x n ), i = 1, . . . , n.
The partition λ = (n) yields the factor Res

( F {1} λ ) = a + nb + n 2 c + ( n 2 ) d
with multiplicity m λ = 1. From Theorem 4 we know that the other factors come from the partitions of length 2. They are of the form λ

= (m, n -m) with n -1 ⩾ m ⩾ n -m ⩾ 1.
The divided difference F {1,2} is equal to a(x 1 + x 2 ) + be 1 and we have

ρ λ (e 1 ) = mx 1 + (n -m)x 2 , ρ λ (e 2 ) = ( m 2 ) x 2 1 + m(n -m)x 1 x 2 + ( n -m 2 ) x 2 , F {1,2} λ = ρ λ ( F {1,2} ) = a(x 1 + x 2 ) + bρ λ (e 1 ) = a(x 1 + x 2 ) + b(mx 1 + (n -m)x 2 ).
Therefore, such a partition λ = (m, n -m) yields the factor Res

( F {1} (m,n-m) , F {1,2} (m,n-m) ) = ab 2 nm+2 dm 2 ab-1/2 dmb 2 n 2 +1/2 dm 2 b 2 n-2 dmna 2 -4 cmna 2 -2 dmabn + 1/2 dn 2 a 2 + 2 dm 2 a 2 + a 2 bn -1/2 dna 2 + cn 2 a 2 + 4 cm 2 a 2 -ab 2 m 2 + a 3 (5.4)
which is computed as the determinant of a 3 × 3 Sylvester matrix. To summarize, if n = 2 (and d = 2) we get

Res(F {1} , F {2} ) = Res ( F {1} ( 2
)
) Res

( F {1} (1,1) , F {1,2} (1,1)
) = (a + 2b + 4c + d) (a + b) 2 (a -d)
where Res

( F {1} (1,1) , F {1,2} (1,1)
) is obtained by specialization of (5.4). If n > 2 (and d = 2) then it is easy to check that F {1,2,3} = a. Therefore, if n = 2k + 1, k being a positive integer, then

Res(F {1} , F {2} ) = (a) m 0 ( a + nb + n 2 c + ( n 2 ) d ) n-1 ∏ m=k+1 Res ( F {1} (m,n-m) , F {1,2} (m,n-m) ) n! m!(n-m)!
where the resultants in this formula are again given by (5.4) and

m 0 = n2 n-1 -1 -3 n-1 ∑ m=k+1 n! m!(n -m)! (for B 2,1 = 1, B 2,2 = 3, A n,1 = 1 and A n,2 = ∑ n-1 m=k+1 n! m!(n-m)! .) If n = 2k with k > 1 then Res(F {1} , F {2} ) = (a) m 0 ( a + nb + n 2 c + ( n 2 ) d ) Res ( F {1} (k,k) , F {1,2} (k,k) ) 1 2 n! (k!) 2 × n-1 ∏ m=k+1 Res ( F {1} (m,n-m) , F {1,2} (m,n-m) ) n! m!(n-m)!
where the resultants in this formula are always given by (5.4) and

m 0 = n2 n-1 -1 - 3 2 n! (k!) 2 -3 n-1 ∑ m=k+1 n! m!(n -m)! .
Before closing this example, we emphasize that the resultants appearing in Theorem 4 are not always irreducible polynomials. For instance, in the case where n = 2k we have that Res

( F {1} (k,k) , F {1,2} (k,k) ) = (a + bk) 2 (a -dk).
(5.5)

However, we notice that Res(F {1} λ ) is obviously always irreducible.

From a geometric point of view, Theorem 4 shows that the solutions of the algebraic polynomial system {F {1} = 0, . . . , F {n} = 0} (5.6) can be decomposed into several components that correspond to the algebraic systems

{F {1} λ = 0, . . . , F {1,...,l(λ)} λ = 0}, λ ⊢ n, l(λ) ⩽ d.
Each component has multiplicity m λ and it corresponds to a particular configuration of the roots of the initial system, namely the roots whose coordinates can be grouped, up to permutations, into l(λ) blocks of identical value and of size λ 1 , . . . , λ l(λ) respectively.

The component corresponding to the partition λ = (1, . . . , 1) is interesting for some applications as it corresponds to solutions of (5.6) whose coordinates are all distinct (e.g. [START_REF] Faugére | Solving polynomial systems globally invariant under an action of symmetric group and application to the equillibria of n vortices in the plane[END_REF]).

A usual trick for dealing with this component is to sum up all the divided differences of the same order to get symmetric polynomials. More precisely, since the polynomials F {1} , F {2} , . . . , F {n} satisfy the property (5.3), for any integer k ∈ [n] the polynomials

∑ I⊂[n], |I|=k F I = ∑ I⊂[n], |I|=k F σ(I) = ∑ I⊂[n], |I|=k σ(F I ) = σ   ∑ I⊂[n], |I|=k F I  
are symmetric (i.e. invariant under the action of S n ). As such, they can be rewritten by using the elementary symmetric polynomials and the number of roots of the component corresponding to λ = (1, . . . , 1) is hence reduced by a factor n!. In general, the above property is no longer true if we consider F I λ instead of F I , λ ̸ = (1, 1, . . . , 1). Nevertheless, it is possible to reformulate Theorem 4 by means of these sums of divided differences of the same order.

Proposition 5.2.3. Take again the notation of Theorem 4. Let λ be a partition of n such that l(λ) ⩽ d and for all integer k ∈ [l(λ)] define the polynomial

F (k) λ := 1 ( l(λ) k ) ∑ I⊂[l(λ)], |I|=k F I λ
(assuming that the coefficient ring contains the rational numbers). Then, we have that

Res ( F {1} λ , F {1,2} λ , . . . , F {1,2,...,l(λ)-1} λ , F {1,2,...,l(λ)} λ ) = Res ( F (1) λ , F (2) λ , . . . , F (l(λ)) λ
) .

Proof. First, we claim that for any subset I ⊂ [l(λ)] such that |I| = l(λ) -1 then

F I λ = F {1,2,...,l(λ)-1} λ mod ( F {1,2,...,l(λ}) λ ) . (5.7)
This is a consequence of the technical Lemma 5.2.4 which is given after the proof of this proposition. From (5.7) we deduce that ∑

I⊂[l(λ)], |I|=l(λ)-1 F I λ = l(λ) F {1,2,...,l(λ)-1} λ mod ( F {1,2,..

.,l(λ}) λ

) .

In the same way, for any subset I ⊂ [l(λ)] such that |I| = l(λ) -2, Lemma 5.2.4 shows that

F I λ = F {1,2,...,l(λ)-2} λ mod ( { F I λ } |I|=l(λ)-1 , F {1,2,..

.,l(λ}) λ

) .

Using (5.7), this equality can be simplified to give

F I λ = F {1,2,...,l(λ)-2} λ mod ( F {1,2,...,l(λ)-1} λ , F
{1,2,...,l(λ}) λ

) .

We deduce that

∑ I⊂[l(λ)], |I|=l(λ)-2 F I λ = ( l(λ) 2 ) F {1,2,...,l(λ)-2} λ mod ( F {1,2,...,l(λ)-1} λ , F {1,2,..

.,l(λ}) λ

) .

By applying iteratively this method, we obtain for all k = 1, . . . , l(λ) -1 the equality ) .

∑ I⊂[l(λ)], |I|=l(λ)-k F I λ = ( l(λ) k ) F {1,
From these equalities, the invariance of the resultant under elementary transformations yields the claimed result (proceed from the right to the left).

Lemma 5.2.4. Using the notation of Section 5.2.1.1, let I and J be two subsets of [n] of the same cardinality r with 1 ⩽ r ⩽ n -1. Then, the polynomial P I -P J belongs to the ideal of polynomials generated by the (r + 1) th divided differences, i.e.

P I -P J ∈ (. . . , P K , . . .) K⊂[n],|K|=r+1 .

Proof. If |I ∩J| = r -1 then P I -P J is a multiple of a divided difference P K with |K| = r +1 by definition of divided differences (by choosing the appropriate order for the elements of I and J). Otherwise, r ⩾ 2, |I ∩ J| < r -1 and hence there exist j ∈ J \ I and i ∈ I \ J (observe that i ̸ = j necessarily). Now, P I -P J = P I -P (I\{i})∪{j} + P (I\{i})∪{j} -P J

where the term P I -P (I\{i})∪{j} is a multiple of a divided difference

P K with |K| = r+1 since |I ∩ ((I \ {i}) ∪ {j})) | = r -1.
So, to prove that P I -P J belongs to the ideal generated by the (r + 1) th divided differences amounts to prove that P (I\{i})∪{j} -P J belongs to this ideal. But notice that |J ∩ ((I \ {i}) ∪ {j}) | = |I ∩ J| + 1. Therefore, one can repeat this operation to reach a cardinality of r -1 and from there the conclusion follows.

Discriminant of a homogeneous symmetric polynomial

The discriminant of a homogeneous polynomial is a rather complicated object which is known to be irreducible as a polynomial in the coefficients of the input polynomial (see for instance [13, §4] and [START_REF] Demazure | Resultant, discriminant[END_REF][START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF]). In this section, we will show that it decomposes if the homogeneous polynomial is assumed to be symmetric. We will actually provide a decomposition formula (Theorem 5) that we will obtain as a particular case of our main result (Theorem 4).

Fix a positive integer n ⩾ 2. For any integer p we will denote by e p (x 1 , . . . , x n ) the p th elementary symmetric polynomial in the variables x 1 , . . . , x n . They satisfy the equality

∑ p⩾0 e p (x)t p = n ∏ i=1 (1 + x i t)
(observe that e 0 (x) = 1 and that e p (x) = 0 for all p > n). For any partition λ = (λ

1 ⩾ • • • ⩾ λ k )
we also define the polynomial

e λ (x) := e λ 1 (x)e λ 2 (x) • • • e λ k (x) ∈ Z[x 1 , . . . , x n ].
Given a positive integer d, it is well known that the set (5.9)

{e λ (x) : λ = (λ 1 , . . . , λ k ) ⊢ d such that n ⩾ λ 1 ⩾ λ 2 ⩾ • • • ⩾ λ k } (5.
We will denote by U its universal ring of coefficients Z[c λ : λ ⊢ d]. In addition, for all i ∈ {1, . . . , n}, we will denote the partial derivatives of F by

F {i} (x 1 , . . . , x n ) := ∂F ∂x i (x 1 , . . . , x n ) ∈ U[x 1 , . . . , x n ] d-1 .
Finally, we recall that the discriminant of F , denoted ∆(F ), is defined by the equality

d a(n,d) ∆(F ) = Res ( F {1} , F {2} , . . . , F {n} ) ∈ U (5.10)
where

a(n, d) := (d -1) n -(-1) n d ∈ Z.
It is an homogeneous polynomial of degree n(d -1) n-1 in U. The integer factor d a(n,d) is important to ensure that the discriminant ∆(F ) yields the expected smoothness criterion under any specialization (especially in coefficient rings having nonzero characteristic), namely : Let S be an algebraically closed field and g be a nonzero homogeneous polynomial in S[x 1 , . . . , x n ], then ∆(g) = 0 if and only if the hypersurface defined by the polynomial g in the projective space P n-1 S is singular. For a detailed study of the discriminant and its numerous properties, mostly inherited from the ones of the resultant, we refer the reader to [START_REF] Busé | On the discriminant scheme of homogeneous polynomials[END_REF][START_REF] Demazure | Resultant, discriminant[END_REF][START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF] and the references therein. Lemma 5.3.1. The partial derivatives F {1} , F {2} , . . . , F {n} of the symmetric polynomial F form a S n -equivariant system of homogeneous polynomials of degree d -1.

Proof. Since F is a polynomial in the elementary symmetric polynomials, the chain rule formula for the derivation of composed functions shows that there exist min{d, n} homogeneous symmetric polynomials S k (x 1 , . . . , x n ) such that for all i = 1, . . . , n

F {i} = ∂F ∂x i = min{d,n} ∑ k=1 ∂e k ∂x i S k (x 1 , . . . , x n ).
(5.11)

Moreover, for any pair of integers i, j we have

∂e j ∂x i = j-1 ∑ r=0
(-1) r x r i e j-1-r .

(5.12)

Therefore, we deduce that σ ( F {i} ) = F {σ(i)} for any σ ∈ S n , as claimed.

As a consequence of this lemma, Theorem 4 can be applied in order to decompose the resultant of the polynomials F {1} , F {2} , . . . , F {n} and hence, by (5.10), to decompose the discriminant of the symmetric polynomial F . We take again the notation of Theorem 4.

Theorem 5. Assume that n ⩾ 2 and d ⩾ 2. With the above notation, we have that

d a(n,d) ∆ (F ) = R 0 × ∏ λ⊢n l(λ)<d Res ( F {1} λ , F {1,2} λ , . . . , F {1,2,...,l(λ)-1} λ , F {1,2,...,l(λ)} λ ) m λ where R 0 = 1 if d > n and R 0 = ( F {1,...,d} ) m 0 if d ⩽ n.
In this latter case, m 0 is defined by

m 0 := n(d -1) n-1 - d-1 ∑ k=1 A n,k B d-1,k where A n,k := ∑ λ⊢n l(λ)=k m λ , B d-1,k := e k-1 (d -1, d -2, . . . , d -k),
and if F is given explicitly by (5.9) then F {1,...,d} = (-1) d-1 c (d) .

Proof. All these formulas are obtained by specialization of the formulas given in Theorem 4 with the difference that the polynomials F {i} , i = 1, . . . , n are of degree d -1 whereas they are of degree d as in Theorem 4.

We emphasize that the formula given in this theorem is independent of the choice of basis that is used to represent F , although we have chosen the basis (5.8) for illustrations. We also mention that the formula given in Proposition 5.2.3 also applies here (this is actually the point of view used in [START_REF] Perminov | Discriminants of symmetric polynomials[END_REF]). Below, we give two examples corresponding to low degree polynomials, namely the cases d = 2 and d = 3. In these two cases the number of variables n is large compared to d and the formulas given in Theorem 5 are hence computationally very interesting since a resultant computation in n variables is replaced by several resultant computations in at most d variables.

Case n ⩾ d = 2

The generic homogeneous polynomial of degree 2 can be written as

F = c (2) e 2 + c (1,1) e 2 1 .
Its derivatives are

F {i} = c (2) ∂e 2 ∂x 1 + 2c (1,1) e 1 ∂e 1 ∂x 1 = c (2) (e 1 -x 1 ) + 2c (1,1) e 1
and hence we deduce that Res

( F {1} (2) ) = (n -1)c (2) + 2nc (1,1) .
Observe that this polynomial is not irreducible over

Z[c (2) , c (1,1) ] if n is odd since it is divisible by 2.
It is also not hard to check that m (2) = 1 and m 0 = n-1 here. Finally, since a(n, 2) = 0 if n is even and a(n, 2) = 1 if n is odd, we get

∆(F ) = { -c n-1 (2) ( (n -1)c (2) + 2nc (1,1) ) if n is even, c n-1
(2)

( n-1 2 c (2) + nc (1, 1
)

)
if n is odd .

Case n ⩾ d = 3 Consider the generic homogeneous polynomial of degree 3

F = c (3) e 3 + c (2,1) e 2 e 1 + c (1,1,1) e 3 1 .
The formula given in Theorem 5 shows that

3 2 n -(-1) n 3 ∆(F ) = c m 0 (3) Res ( F {1} (n) ) ⌊ n 2 ⌋ ∏ k=1 Res ( F {1} (n-k,k) , F {1,2} (n-k,k) ) m (n-k,k)
where all the factors can be described explicitly. To begin with, from (5.11) and (5.12) we get that for all i = 1, . . . , n

F {i} = c (3) ( e 2 -x i e 1 + x 2 i ) + c (2,1) (e 2 + e 1 (e 1 -x i )) + 3c (1,1,1) e 2 1 .

It follows immediately that

Res

( F {1} (n) ) = ( n -1 2
) c (3) + 3 ( n 2 ) c (2,1) + 3n 2 c (1,1,1) .
Now, let (n -k, k) be a partition of length 2 of n. A straightforward computation shows that for any pair of distinct integers i, j we have

F {i,j} = c (3) (x i + x j -e 1 ) -c (2,1) e 1
and we deduce, by means of a single (Sylvester) resultant computation that Res

( F {1} (n-k,k) , F {1,2} (n-k,k) ) = c 2 (3) (( n -1 2
) c (3) + 3 ( n 2 ) c (2,1) + 3n 2 c (1,1 ,1)
)

- 1 2 k(n -k) ( (n -2) c 3 (3) + ( 24c (1,1,1) + 3nc (2,1) ) c 2 (3) + (3n -6) c 2 (2,1) c (3) + nc 3 (2,1)
) .

The multiplicity m (n-k,k) are equal to the binomial

( n k ) for all k = 1, . . . , ⌊ n 2 ⌋ except if n is even and k = n 2 in which case m ( n 2 , n 2 ) = 1 2 ( n n 2
)

. Finally, it remains to determine the integer m 0 . We have

m 0 = n2 n-1 -m (n) -3 ∑ λ⊢n l(λ)=2 m λ = n2 n-1 -1 -3 ⌊ n 2 ⌋ ∑ k=1 m (n-k,k) . But since 2 ⌊ n 2 ⌋ ∑ k=1 m (n-k,k) = n-1 ∑ k=1 ( n k ) = 2 n -2 = 2(2 n-1 -1),
we finally deduce that m 0 = (n -3)2 n-1 + 2.

To illustrate this general formula, we check the two particular cases n = 3 and n = 4. If n = 3, we obtain

∆(F ) = c (3) 2 ( c (3) + 9 c (2,1) + 27 c (1,1,1) ) ( -c (2,1) 2 c (3) -c (2,1) 3 + c (1,1,1) c (3) 2 ) 3
where Res

( F {1} ( 3
) ) = ( c (3) + 9 c (2,1) + 27 c (1,1,1) ) , m (3) = 1
and Res

( F {1} (2,1) , F {1,2} (2,1)
) = 3 ( -c (2,1) 2 c (3) -c (2,1) 3 + c (1,1,1) c (3) 2 ) , m (2,1) = 3.
If n = 4 we get

∆(F ) = -c (3) 10 ( c (3) + 2 c (2,1) ) 9 ( 6 c (2,1) + 16 c (1,1,1) + c (3) ) × ( 4 c (1,1,1) c (3) 2 -3 c (2,1) 2 c (3) -2 c (2,1) 3 ) 4 (5.13)
where Res

( F {1} ( 4
) ) = 3 ( 6 c (2,1) + 16 c (1,1,1) + c (3) ) , m (4) = 1, Res ( F {1} (3,1) , F {1,2} (3,1)
) = 3 ( 4 c (1,1,1) c (3) 2 -3 c (2,1) 2 c (3) -2 c (2,1) 3 ) , m (3,1) = 4
and Res

( F {1} (2,2) , F {1,2} (2,2) ) = - ( c (3) + 2 c (2,1) ) 3 , m (2,2) = 3. (5.14)
For the Clebsch surface whose canonical equation is given by

h(x 1 , x 2 , x 3 , x 4 ) = x 3 1 + x 3 2 + x 3 3 + x 3 4 -(x 1 + x 2 + x 3 + x 4 ) 3 = 3e 3 -3e 2 e 1 = 0,
we recover that h/3 defines a smooth cubic in every characteristic except 5 (see [84, §5.4]). Indeed, (5.13) shows that ∆(h/3) = ∆(e 3 -e 2 e 1 ) = -(-1) 9 (-6 + 1)(-3 + 2) 4 = -5.

Remark 5.3.2.

Contrary to what was expected in [START_REF] Perminov | Discriminants of symmetric polynomials[END_REF], the resultant factors appearing in Theorem 5 are not always irreducible (see e.g. (5.14)). However, in all the experiments we noted that these resultant factors were always powers of irreducible polynomials (ground ring assumed to be a field), but we do not known if this is true in general. As an illustration, we notice that the resultant (5.5) appearing in Example 5.2.2 contains two irreducible and distinct factors, but it becomes a power of a single irreducible polynomial (over a field) when specialized to get the discriminant formula in the case n ⩾ d = 3. Indeed, comparing the notation in these two examples we get d = -b = c (3) + c (2,1) .

Proof of the Main Theorem

We take again the notation of Section 5.2. We begin by splitting the resultant of the F {i} 's into several factors by means of their divided differences. This process can be divided into steps where we increase iteratively the order of the divided differences. Thus, in the first step we make use of the first order divided differences and write

Res ( F {1} , F {2} , . . . , F {n} ) = ± Res ( F {1} , (x 1 -x 2 )F {1,2} , (x 1 -x 3 )F {1,3} , . . . , (x 1 -x n )F {1,n} ) . (5.15)
The divided differences F {1,j} are of degree d -1. If d -1 = 0 then they are all equal to the same constant (see Section 5.2.1.1) and it is straightforward to check that we get the claimed formula in this case, that is to say

Res ( F {1} , F {2} , . . . , F {n} ) = ( F {1,2} ) n-1 Res ( F {1} (n) ) = ( F {1,2} ) n-1 F {1} (1, 1, . . . , 1).
If d -1 > 0, then (5.15) shows that the resultant of the F {i} 's splits into 2 n-1 factors by using the multiplicativity property of the resultant : for each polynomial (x 1 -x j )F {1,j} , j = 2, . . . , n, there is a choice between (x 1 -x j ) and the divided difference F {1,j} . Thus, these factors are in bijection with the subsets of [n] which contain 1. If

I 1 = {1, i 2 , i 3 , . . . , i n-k+1 } ⊂ [n]
is such a subset, then the corresponding factor is simply

±Res ( F {1} , F {1,j 1 } , F {1,j 2 } , . . . , F {1,j k-1 } , x 1 -x i 2 , x 1 -x i 3 , . . . , x 1 -x i n-k+1 )
where {j 1 , . . . , j k-1 } = [n] \ I 1 . Moreover, by the specialization property of the resultant this factor is equal to

±Res ( F {1} 1 , F {1,2} 1 , F {1,3} 1 , . . . , F {1,k} 1 ) (5.16)
where we set F {1,r} 1 := ρ I 1 (F {1,jr} ), ρ I 1 being a specialization map defined by

ρ I 1 : k[x 1 , . . . , x n ] → k[x 1 , . . . , x k ] x j , j ∈ I 1 → x 1 x jr , r = 1, . . . , k -1 → x r+1 .
Roughly speaking, this amounts to put all the variables x j , j ∈ I 1 , in the "same box" and to renumber the other variables from 2 to k. Now, one can proceed to the second step by introducing the second order divided differences. For that purpose, we start from the factor (5.16) obtained at the end of the previous step. If k ⩽ 2 the procedure stops. Otherwise, if k > 2 then we can proceed exactly as in the first step, since 2,k} ) .

(x 2 -x j )F {1,2,j} 1 = F {1,2} 1 -F {1,j} 1 , j = 3, . . . , k, we get Res ( F {1} 1 , F {1,2} 1 , F {1,3} 1 , . . . , F {1,k} 1 ) = ± Res ( F {1} , F {1,2} , (x 2 -x 3 )F {1,2,3} , (x 2 -x 4 )F {1,2,4} , . . . , (x 2 -x k )F {1,
So, we are exactly in the same setting as in the previous step and hence we split this factor similarly. As a result, the factors we obtain are in bijection with subsets I 2 of [n] that contain 2 but not 1. After this second step is completed, then one can continue to the third step, and so on. This splitting process stops for a given factor if either it involves divided differences of distinct orders or either the order of some divided differences is higher than the degree d.

In summary, the above process shows that the resultant Res ( F {1} , F {2} , . . . , F {n} ) splits into factors that are in bijection with ordered collections of subsets (I 1 , . . . , I k ) that satisfy the following three conditions :

• 1 ⩽ k ⩽ min{d, n} and ∅ ̸ = I j ⊂ [n] for all j ∈ [k],
•

I 1 ⨿ I 2 ⨿ . . . ⨿ I k = [n] (disjoint union, so this is a partition of [n]), • 1 = min(I 1 ) < min(I 2 ) < • • • < min(I k ).
Definition 5.4.1. A collection of subsets (I 1 , . . . , I k ) satisfying to the three above conditions will be called an admissible partition (of [n]).

Given an admissible partition (I 1 , . . . , I k ), we define the specialization map

ρ (I 1 ,...,I k ) : k[x 1 , . . . , x n ] → k[x 1 , . . . , x k ] x r , r ∈ I s → x s
and the polynomials F {1,2,...,r} (I 1 ,...,I k ) := ρ (I 1 ,...,I k ) (F {1,i 2 ,...,ir} ), r = 1, . . . , k, where we set

i 1 := 1 = min(I 1 ) < i 2 := min(I 2 ) < • • • < i k := min(I k ).
Then, the factor of the resultant of the F {i} 's corresponding to the admissible partition (I 1 , . . . , I k ) is given by ) .

R (I 1 ,...,I k ) := Res ( F {1} (I 1 ,...,I k ) , F {1,2} (I 1 ,.
Therefore, we proved that

Res ( F {1} , F {2} , . . . , F {n} ) = ± ( F {1,...,d+1} ) µ × ∏ (I 1 ,...,I k ) R (I 1 ,...,I k ) (5.17)
where the product runs over all admissible partitions of [n] and µ is an integer. Moreover, µ > 0 if and only if n > d.

Now, we define an equivalence relation ∼ on the set of admissible partitions of [n].

Given two admissible partitions (I 1 , . . . , I k ) and (J 1 , . . . , J k ′ ), we set

(I 1 , . . . , I k ) ∼ (J 1 , . . . , J k ′ ) ⇔ { k = k ′ and ∃ σ ∈ S k such that |I l | = |J σ(l) | for all l ∈ [k].
It is straightforward to check that this binary relation is reflexive, symmetric and transitive so that it defines an equivalence relation. We denote by [(I 1 , . . . , I k )] its equivalence classes. Consider the admissible partitions (L 1 , . . . , L k ) such that

l 1 := |L 1 | ⩾ l 2 := |L 2 | ⩾ . . . l k := |L k | and
(5.18)

L j := { 1 + j-1 ∑ i=1 l i , 2 + j-1 ∑ i=1 l i , . . . , j ∑ i=1 l i } for all j ∈ [k].
Obviously, there is exactly one such admissible partition in each equivalent class of ∼. Moreover, these admissible partitions are in bijection with the partitions λ ⊢ n of length k by setting λ := (l 1 , l 2 , . . . , l k ) ⊢ n. As a consequence, we deduce that there is a bijection between the equivalence classes of ∼ and the partitions λ ⊢ n of length k and we write Proof. Let λ be a partition of n and consider the equivalent class [λ]. The multinomial coefficient (2.1) counts the different ways of filling k = (λ) boxes J 1 , . . . , J k with λ j elements in the box J j . These choices take into account the order between the boxes, but not inside the boxes. These boxes J j can obviously be identified with subsets of [n]. Moreover, there exists a unique permutation σ ∈ S k such that

1 = min(J σ(1) ) < min(J σ(2) ) < • • • min(J σ(k) )
and hence such that the collection of subsets (J σ(1) , J σ(2) , . . . , J σ(k) ) is an admissible partition. Therefore, any choice for filling the boxes J 1 , . . . , J k can be associated to a factor in the decomposition. Conversely, such a factor is associated to an admissible partition (I 1 , . . . , I k ), but there are possibly several choices, i.e. permutations in S k , that give a way of filling the boxes J 1 , . . . , J k : it is possible to permute boxes that have the same cardinality. Therefore, we conclude that the cardinality of the equivalent class represented by a partition λ ⊢ n is exactly m λ .

The following result shows that admissible partitions that are equivalents give the same factor, up to sign, in the splitting process. ) .

Proof. Let (I 1 , . . . , I k ) be an admissible partition and set

i 1 := 1 = min(I 1 ) < i 2 := min(I 2 ) < • • • < i k := min(I k ).
Its corresponding factor in the splitting process is nothing but the resultant, up to sign, of the following list of n polynomials in the n variables x 1 , . . . , x n :

F {1} , F {1,i 2 } , . . . , F {1,i 2 ,...,i k } , {x i 1 -x r } r∈I 1 \{1} , . . . , {x i k -x r } r∈I k \{i k } . (5.19)
Now, let (J 1 , J 2 , . . . , J k ) be another admissible partition such that [(I 1 , . . . , I k )] = [(J 1 , J 2 , . . . , J k )] and set

j 1 := 1 = min(J 1 ) < j 2 := min(J 2 ) < • • • < j k := min(J k ).
The corresponding factor of (J 1 , J 2 , . . . , J k ) can be described similarly as the resultant, up to sign, of the polynomials

F {1} , F {1,j 2 } , . . . , F {1,j 2 ,...,j k } , {x j 1 -x r } r∈J 1 \{1} , . . . , {x j k -x r } r∈J k \{j k } . (5.20)
First, observe that it is sufficient to prove that R (I 1 ,...,I k ) = ±R (J 1 ,...,J k ) by assuming that

|I σ(l) | = |J l | for all l ∈ [k]
where σ is an elementary transposition (a permutation which exchanges two successive elements and keeps all the others fixed) in S k . This is because S k is generated by the elementary transpositions and because of the transitivity of ∼. So, let s ∈ [k -1] and assume that

|I s | = |J s+1 |, |I s+1 | = |J s | and |I l | = |J l | for all l ∈ [k] \ {s, s + 1}.
Let us choose a permutation τ ∈ S n such that

     τ (I l ) = J l and τ (i l ) = j l for all l ∈ [k], τ (I s ) = J s+1 and τ (i s ) = j s+1 , τ (I s+1 ) = J s and τ (i s+1 ) = j s .
By the property (5.3), the application of τ on the list of polynomials (5.19) returns the following list of polynomials F {1} , F {1,j 2 } , . . . , F {1,j 2 ,...,j s-1 ,j s+1 } , F {1,j 2 ,...,j s-1 ,js,j s+1 } , . . . , F {1,j 2 ,...,j k } ,

{x j 1 -x r } r∈J 1 \{1} , . . . , { x j s-1 -x r } r∈J s-1 \{j s-1 } , { x j s+1 -x r } r∈J s+1 \{j s+1 } , {x js -x r } r∈Js\{js} , . . . , {x j k -x r } r∈J k \{j k } . (5.21)
By the invariance, up to sign, of the resultant under permutations of polynomials and variables, we get that the resultant of the list of polynomials (5.19), i.e. R (I 1 ,...,I k ) , is equal to the resultant of the list of polynomials (5.21) up to sign. Now, by definition of divided differences we have that F {1,j 2 ,...,j s-1 ,js} = F {1,j 2 ,...,j s-1 ,j s+1 } + (x js -x j s+1 )F {1,j 2 ,...,j s-1 ,js,j s+1 } so that the resultant of the polynomials (5.21) is equal, up to sign, to the resultant of the polynomials (5.20), i.e. R (J 1 ,...,J k ) , by invariance of the resultant under the above elementary transformation and permutations of polynomials. Therefore, we have proved that

R (I 1 ,...,I k ) = ±R (J 1 ,...,J k ) .
Finally, to conclude the proof, let (L 1 , . . . , L k ) be the particular representative of the class [λ] = [(I 1 , . . . , I k )] as defined in (5.18). Then, it is clear by the definitions that ρ (L 1 ,...,L k ) = ρ λ and that

R (L 1 ,...,L k ) = Res ( F {1} λ , F {1,2} λ , . . . , F {1,2,...,l(λ)-1} λ , F {1,2,...,l(λ)} λ
) .

The comparison of (5.17), Lemma 5.4.2 and Proposition 5.4.

3 shows that if d ⩾ n then Res ( F {1} , . . . , F {n} ) = ± ∏ λ⊢n Res ( F {1} λ , F {1,2} λ , . . . , F {1,2,...,l(λ)-1} λ , F {1,2,...,l(λ)} λ ) m λ (5.22) and if n > d then Res ( F {1} , . . . , F {n} ) = ± ( F {1,...,d+1} ) µ ∏ λ⊢n l(λ)⩽d Res ( F {1} λ , F {1,2} λ , . . . , F {1,2,...,l(λ)-1} λ , F {1,2,...,l(λ)} λ ) m λ . (5.23)
To determine the integer µ, we compare the degrees with respect to the coefficients of the F {i} 's. The resultant on the left side is homogeneous of degree d n-1 with respect to the coefficients of each polynomial F {i} , so it is homogeneous of degree nd n-1 with respect to the coefficients of all the polynomials F {i} , i = 1, . . . , n. Given a partition λ ⊢ n, l(λ) ⩽ d, the polynomial F {1,2,...,j} λ , 1 ⩽ j ⩽ l(λ) is of degree d -j + 1. Therefore, the resultant associated to this partition λ is homogeneous with respect to the coefficients of the F {i} 's of degree

l(λ) ∑ j=1 d(d -1) • • • (d -l(λ) + 1) d -j + 1 = e l(λ)-1 (d, d -1, . . . , d -l(λ) + 1).
Finally, since F {1,2,...,d+1} is homogeneous of degree one in the coefficient of the F {i} 's, we deduce that

µ = nd n-1 - ∑ λ⊢n l(λ)⩽d m λ .e l(λ)-1 (d, d -1, . . . , d -l(λ) + 1), that is to say µ = nd n-1 - d ∑ k=1 ∑ λ⊢n l(λ)=k m λ .e k-1 (d, d -1, . . . , d -k + 1).
From here we see immediately that µ is equal to the integer m 0 defined in the statement of Theorem 4.

To conclude the proof of Theorem 4, it remains to determine the signs that occur in the formulas (5.22) and (5.23). To this end, we examine the specialization of them, when

F {i} = x d i , i = 1, . . . , n.
First, the resultant of the F {i} 's is equal to 1 (normalization of the resultant). Now, given any partition λ ⊢ n, it is straightforward to check that

F {1} λ = x d 1 .
Then applying iteratively the defining property of the divided differences from j = 1 to j = l(λ), we get that F {1,2,...,j} λ = x d j mod (x 1 , . . . , x j-1 ), j = 1, . . . , l(λ). Now, using the multiplicativity property of the resultant and its invariance under elementary transformations, we deduce that all the resultants associated to a partition λ specialize to 1. Similarly we observe that F {1,...,d+1} also specializes to 1 when n > d, and this concludes the proof of Theorem 4.

MIXED DISCRIMINANTS

Polynomial algebra offers a standard approach to handle several problems in geometric modeling. A key tool is the discriminant of a univariate polynomial, or of a well-constrained system of polynomial equations, which expresses the existence of a multiple root. We describe discriminants in a general context, and focus on exploiting the sparseness of polynomials via the theory of Newton polytopes and sparse (or toric) elimination. We concentrate on bivariate polynomials and establish an original formula that relates the discriminant of two bivariate Laurent polynomials with fixed support, with the sparse resultant of these polynomials and their toric Jacobian. This allows us to obtain a new proof for the bidegree of the discriminant as well as to establish multipicativity formulas arising when one polynomial can be factored.

Introduction

Polynomial algebra offers a standard and powerful approach to handle several problems in geometric modeling. In particular, the study and solution of systems of polynomial equations has been a major topic. Discriminants provide a key tool when examining wellconstrained systems, including the case of one univariate polynomial. Their theoretical study is a thriving and fruitful domain today, but they are also very useful in a variety of applications.

The best studied discriminant is probably known since high school, where one studies the discriminant of a quadratic polynomial f (x) = ax 2 + bx + c = 0 (a ̸ = 0). The polynomial f has a double root if and only if its discriminant ∆ 2 = b 2 -4ac is equal to zero. Equivalently, this can be defined as the condition for f (x) and its derivative f ′ (x) to have a common root:

∃ x : f (x) = ax 2 + bx + c = f ′ (x) = 2ax + b = 0 ⇔ ∆ 2 = 0. (6.1)
One can similarly consider the discriminant of a univariate polynomial of any degree. If we wish to calculate the discriminant ∆ 5 (f ) of a polynomial f of degree five in one variable, we consider the condition that both f and its derivative vanish:

f (x) = ax 5 + bx 4 + cx 3 + dx 2 + ex + g = 0, f ′ (x) = 5ax 4 + 4bx 3 + 3cx 2 + 2dx + e = 0.
In this case, elimination theory reduces the computation of ∆ 5 to the computation of a 9×9 Sylvester determinant, which equals a ∆ 5 (f ). If we develop this determinant, we find out that the number monomials in the discriminant increases rapidly with the input degree:

∆ 5 = -2050a 2 g 2 bedc + 356abed 2 c 2 g -80b 3 ed 2 cg + 18dc 3 b 2 g e -746agdcb 2
+ 560ag 2 d 2 cb 2 + 1020ag 2 b 2 c 2 e -192 b 4 ecg 2 + 24ab 2 ed 3 g + 24abe 2 c 3 g + 144b 4 e 2 dg -6b 3 e 2 c 2 g + 14 4dc 2 b 3 g 2 -630dac 3 bg 2 -630d 3 a 2 ceg -72d 4 acbg -72dac 4 e g -4d 3 c 2 b 2 g -1600ag 3 cb 3 -2500a 3 g 3 be -50a 2 g 2 b 2 e 2 -3750a 3 g 3 dc + 2000a 2 g 3 db 2 + 2000a 3 g 2 ce 2 + 825a 2 g 2 d 2 c 2 + 2250a 2 g 3 b c 2 + 2250a 3 g 2 ed 2 -900a 2 g 2 bd 3 -900a 2 g 2 c 3 e -36agb 3 e 3 -1600 a 3 ge 3 d + 16d 3 ac 3 g -128d 2 b 4 g 2 + 16d 4 b 3 g -27c 4 b 2 g 2 + 108ac 5 g 2 + 108a 2 d 5 g + 256b 5 g 3 .
In fact, if we compute the resultant of f and xf ′ by means of the 10 × 10 Sylvester determinant, we find the more symmetric output: a g ∆ 5 (f ). This formula is very well known for univariate discriminants [START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF], and we generalize it in Theorem 6.3.3.

One univariate polynomial is the smallest well-constrained system. We are concerned with multivariate systems of sparse polynomials, in other words, polynomials with fixed support, or set of nonzero terms. Sparse (or toric) elimination theory concerns the study of resultants and discriminants associated with toric varieties. This theory has its origin in the work of Gel'fand, Kapranov and Zelevinsky on multivariate hypergeometric functions. Discriminants arise as singularities of such functions [START_REF] Gel'fand | Hyper-geo-metric functions and toric varieties[END_REF].

Gel'fand, Kapranov and Zelevinsky [START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF] established a general definition of sparse discriminant, which gives as special case the following definition of (sparse) mixed discriminant (see Section 6.2 for the relation with the discriminant of the associated Cayley matrix and with the notion of mixed discriminant in [START_REF] Cattani | Mixed discriminants[END_REF]). In case n = 2, the mixed discriminant detects tangencies between families of curves with fixed supports. In general, the mixed discriminant ∆ A 1 ,...,An (f 1 , . . . , f n ) of n polynomials in n variables with fixed supports A 1 , . . . , A n ⊂ Z n is the irreducible polynomial (with integer coprime coefficients, defined up to sign) in the coefficients of the f i which vanishes whenever the system

f 1 = • • • = f n = 0
has a multiple root (that is, a root which is not simple) with non-zero coordinates, in case this discriminantal variety is a hypersurface (and equal to the constant 1 otherwise). The zero locus of the mixed discriminant is the variety of ill-posed systems [START_REF] Shub | Complexity of bézout's theorem i. geometric aspects[END_REF]. We shall work with the polynomial defining the discriminant cycle (see Section 6.2) which is defined as the power ∆ i(A 1 ,...,An) A 1 ,...,An of the mixed discriminant raised to the index

i(A 1 , . . . , A n ) = [Z n : ZA 1 + • • • + ZA n ], (6.2)
which stands for the index of lattice

ZA 1 + • • • + ZA n in Z n .
In general, this index equals 1 and so both concepts coincide.

Discriminants have many applications. Besides the classical application in the realm of differential equations to describe singularities, discriminants occur for instance in the de-scription of the topology of real algebraic plane curves [START_REF] González-Vega | Efficient topology determination of implicitly defined algebraic plane curves[END_REF], in solving systems of polynomial inequalities and zero-dimensional systems [START_REF] Faugére | Classification of the perspective-three-point problem: Discriminant variety and real solving polynomial systems of inequalities[END_REF], in determining the number of real roots of square systems of sparse polynomials [START_REF] Dickenstein | Extremal real algebraic geometry and a-discriminants[END_REF], in studying the stability of numerical solving [START_REF] Dickenstein | A world of binomials[END_REF], in the computation of the Voronoi diagram of curved objects [START_REF] Emiris | The predicates for the exact voronoi diagram of ellipses under the euclidean metric[END_REF], or in the determination of cusp points of parallel manipulators [START_REF] Moroz | On the determination of cusp points of 3-rpr parallel manipulators[END_REF].

Computing (mixed) discriminants is a (difficult) elimination problem. In principle, they can be computed with Gröbner bases, but this is very inefficient in general since these polynomials have a rich combinatorial structure [START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF]. Ad-hoc computations via complexes (i.e., via tailored homological algebra) are also possible, but they also turn out to be complicated. The tropical approach to compute discriminants was initiated in [START_REF] Dickenstein | Tropical discriminants[END_REF] and the tropicalization of mixed planar discriminants was described in [START_REF] Dickenstein | Singular tropical hypersurfaces[END_REF]. Recently, in [START_REF] Emiris | Sparse implicitization by interpolation: Characterizing non-exactness and an application to computing discriminants[END_REF], the authors focus on computing the discriminant of a multivariate polynomial via interpolation, based on [START_REF] Emiris | An output-sensitive algorithm for computing projections of resultant polytopes[END_REF][START_REF] Rincón | Computing tropical linear spaces[END_REF]; the latter essentially offers an algorithm for predicting the discriminant's Newton polytope, hence its nonzero terms. This yields a new output-sensitive algorithm which, however, remains to be juxtaposed in practice to earlier approaches.

We mainly work in the case n = 2, where the results are more transparent and the basic ideas are already present, but all our results and methods can be generalized to any number of variables. This will be addressed in a subsequent paper [START_REF] Dickenstein | Mixed discriminants and toric jacobians[END_REF]. Consider for instance a system of two polynomials in two variables and assume that, the first polynomial factors as

f 1 = f ′ 1 • f ′′ 1 .
Then, the discriminant also factors and we thus obtain a multiplicativity formula for it, which we make precise in Corollary 6.4.1. This significantly simplifies the discriminant's computation and generalizes the formula in [START_REF] Busé | A computational approach to the discriminant of homogeneous polynomials[END_REF] for the classical homogeneous case. This multiplicativity formula is a consequence of our main result (Theorem 6.3.3 in dimension 2, see also Theorem 6.3.4 in any dimension) relating the mixed discriminant and the resultant of the given polynomials and their toric Jacobian (see Section 6.3 for precise definitions and statements). As another consequence of Theorem 6.3.3, we reprove, in Corollary 6.3.6, the bidegree formula for planar mixed discriminants in [START_REF] Cattani | Mixed discriminants[END_REF].

The rest of this chapter is organized as follows. The next section overviews relevant existing work and definitions. In Section 6.3 we present our main results relating the mixed discriminant with the sparse resultant of the two polynomials and their toric Jacobian. In Section 6.4 we deduce the general multiplicativity formula for the mixed discriminant when one polynomial factors.

Previous work and notation

In this section we give a general description of discriminants and some definitions and notations that we are going to use in the following sections.

Given a set A ⊂ R n , let Q = conv(A) denote the convex hull of A. We say that A is a lattice set or configuration if it is contained in Z n , whereas a polytope with integer vertices is called a lattice polytope. We denote by Vol(•) the volume of a lattice polytope, normalized with respect to the lattice Z n , so that a primitive simplex has normalized volume equal to 1.

Normalized volume is obtained by multiplying Euclidean volume by n!.

Given a non-zero Laurent polynomial

f = ∑ a c a x a ,
the finite subset A of Z n of those exponents a for which c a ̸ = 0 is called the support of f . The Newton polytope N (f ) of f is the lattice polytope defined as the convex hull of A.

A (finite) set

A is said to be full, if it consists of all the lattice points in its convex hull. In [START_REF] Cattani | Mixed discriminants[END_REF], A is called dense in this case, but we prefer to reserve the word dense to refer to the classical homogeneous case. A subset F ⊆ A is called a face of A, denoted F ≺ A, if F is the intersection of A with a face of the polytope conv(A).

As usual Q 1 + Q 2 denotes the Minkowski sum of sets Q 1 and Q 2 in R n . The mixed volume M V (Q 1 , . . . , Q n ) of n convex polytopes Q i in R n
is the multilinear function with respect to Minkowski sum that generalizes the notion of volume in the sense that M V (Q, . . . , Q) = Vol(Q), when all Q i equal a fixed convex polytope Q.

The following key result is due to Bernstein and Kouchnirenko. The mixed volume of the Newton polytopes of n Laurent polynomials f 1 (x), . . . , f n (x) in n variables is an integer that bounds the number of isolated common solutions of f 1 (x) = 0, . . . , f n (x) = 0 in the algebraic torus (K * ) n , over an algebraically closed field K containing the coefficients. If the coefficients of the polynomials are generic, then the common solutions are isolated and their number equals the mixed volume. This bound generalized Bézout's classical bound to the sparse case: for homogeneous polynomials the mixed volume and Bézout's bound coincide.

Mixed volume can be defined in terms of Minkowski sum volumes as follows.

M V n (Q 1 , . . . , Q n ) = n ∑ k=1 (-1) n-k ∑ I⊂{1,...,n},|I|=k 1 n! Vol ( ∑ i∈I Q i ) .
This implies, for n = 2:

2M V (Q 1 , Q 2 ) = Vol(Q 1 + Q 2 ) -Vol(Q 1 ) -Vol(Q 2 ).

Definition 6.2.1. A family of finite lattice configurations

A 1 , . . . , A k in Z n is called essential if the affine dimension of the lattice ZA 1 + • • • + ZA k equals k -1,
and for all proper subsets I ⊂ {1, . . . , k} it holds that the affine dimension of the lattice generated by {A i , i ∈ I} is greater or equal than its cardinality |I|.

Definition/Theorem 1. [START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF][START_REF] Sturmfels | The newton polytope of the resultant[END_REF] Fix a family of n+1 finite lattice configurations A 1 , . . . , A n+1 which contains a unique essential subfamily {A i , i ∈ I}. Given Laurent polynomials f 1 , . . . , f n+1 in n variables with respective supports A 1 , . . . , A n+1 , the resultant Res A 1 ,...,A n+1 (f 1 , . . . , f n+1 ) is the irreducible polynomial with coprime integer coefficients (defined up to sign) in the coefficients of f 1 , . . . , f n+1 , which vanishes whenever f 1 , . . . , f n+1 have a common root in the torus (C * ) n . In fact, in this case, the resultant only depends on the coefficients of f i with i ∈ I.

If there exist more than one essential subfamilies, then the (closure of the) variety of solvable systems is not a hypersurface and in this case we set:

Res A 1 ,...,A n+1 (f 1 , . . . , f n+1 ) = 1.
In what follows, we consider n (finite) lattice configurations A 1 , . . . , A n in Z n and we denote by Q 1 , . . . , Q n their respective convex hulls. Let f 1 , . . . , f n be Laurent polynomials with support A 1 , . . . , A n respectively:

f i (x) = ∑ α∈A i c i,α x α , i = 1 . . . , n.
In [START_REF] Cattani | Mixed discriminants[END_REF] the mixed discriminantal variety, is defined as closure of the locus of coefficients c i,α for which the associated system

f 1 = • • • = f n = 0 has a non-degenerate multiple root x ∈ (K * ) n .
This means that x is an isolated root and the n gradient vectors

( ∂f i ∂x 1 (x), . . . , ∂f i ∂x n (x)
) are linearly dependent, but any n -1 of them are linearly independent. Definition 6.2.2. If the mixed discriminantal variety is a hypersurface, the mixed discriminant of the previous system is the unique up to sign irreducible polynomial ∆ A 1 ,...,An with integer coefficients in the unknowns c i,a which defines this hypersurface. Otherwise, the family is said to be defective and we set ∆ A 1 ,...,An = 1. The mixed discriminant cycle ∆A 1 ,...,An is equal to i(A 1 , . . . , A n ) times the mixed discriminant variety, and thus its equation equals ∆ A 1 ,...,An raised to this integer (defined in (6.2)).

By [18, Theorem 2.1], when the family A 1 , . . . , A n is non defective, the mixed discriminant ∆ A 1 ,...,An coincides with the A-discriminant defined in [START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF], where A is the Cayley matrix

A =       1 0 . . . 0 0 1 . . . 0 . . . . . . . . . . . . 0 0 . . . 1 A 1 A 2 . . . A n       .
This matrix has 2n rows and m = ∑ n i=1 |A i | columns, so 0 = (0, . . . , 0) and 1 = (1, . . . , 1) denote row vectors of appropriate lengths. We introduce n new variables y 1 , . . . , y n in order to encode the system

f 1 = • • • = f n = 0 in one polynomial with support in A, via the Cayley trick: ϕ(x, y) = y 1 f 1 (x) + • • • + y n f n (x). Note that i(A 1 , . . . , A n ) = [Z 2n , ZA].
In what follows when we refer to resultants or discriminants we will refer to the equations of the corresponding cycles, but we will omit the tildes in our notation. More explicitly, we will follow the convention in the article [START_REF] Sombra | A poisson formula for the sparse resultant[END_REF] by D'Andrea and Sombra. In general, both definitions coincide, but this convention allows us to present cleaner formulas. For instance, when the family A 1 , . . . , A n+1 is essential, our notion of resultant equals the resultant in [START_REF] Gelfand | Discriminants, resultants & multidimensional determinants[END_REF][START_REF] Sturmfels | The newton polytope of the resultant[END_REF] raised to the index i(A 1 , . . . , A n+1 ). In most examples these two lattices coincide, and so our resultant cycle equals the resultant variety and the associated resultant polynomial is irreducible.

It is straightforward to see in general from the definition, that in case where

∆ A ′ 1 ,...,An (f ′ 1 , . . . , f n ) = 0 or ∆ A ′′ 1 ,...,An (f ′′ 1 , . . . , f n ) = 0 or Res A ′ 1 ,A ′′ 1 ,...,An (f ′ 1 , f ′′ 1 , . . . , f n ) = 0 then, ∆ A ′ 1 +A ′′ 1 ,...,An (f ′ 1 f ′′ 1 , f 2 , . . . , f n ) = 0.
It follows from [START_REF] Esterov | Newton polyhedra of discriminants of projections[END_REF] that when each support configuration A i is full, the Newton polytope of the discriminant

∆ A ′ 1 +A ′′ 1 ,A 2 ,...,An (f ′ 1 f ′′ 1 , f 2 , . . . , f n ) equals the Minkowski sum of the Newton polytopes of the discriminants ∆ A ′ 1 ,A 2 ,...,An (f ′ 1 , f 2 , . . . , f n ) and ∆ A ′′ 1 ,A 2 ,...,An (f ′′ 1 , f 2 , . . . , f n ) plus two times the Newton polytope of the resultant Res A ′ 1 ,A ′′ 1 ,A 2 ,...,An (f ′ 1 , f ′′ 1 , f 2 , . . . , f n ).
So, a first guess would be that the factorization into the three factors in (6.5) above holds for general supports. We will see in Corollary 6.4.1 that indeed other factors may occur, which we describe explicitly. This behavior already occurs in the univariate case:

Example 6.2.5. Let A ′ 1 = {0, i 1 , . . . , i m , d 1 }, A ′′ 1 = {0, j 1 , . . . , j l , d 2 } be the support sets of f ′ 1 = a 0 + a i 1 x i 1 + • • • + a im x im + a d 1 x d 1 , f ′′ 1 = b 0 + b j 1 x j 1 + • • • + b j l x j l + b d 2 x d 2 respectively. Then ∆(f ′ 1 f ′′ 1 ) = ∆(f ′ 1 ) • ∆(f ′′ 1 ) • R(f ′ 1 , f ′′ 1 ) 2 • E, where E = a i 1 -m 0 0 b j 1 -m 0 0 a d 1 -im-m1 d 1 b d 2 -j l -m 1 d 2 , with m 0 := min{i 1 , j 1 } and m 1 := min{d 1 - i m , d 2 -j l }. On the other hand, in the full case i 1 = j 1 = 1, i m = d 1 -1, j l = d 2 -1, thus E = 1 because
its exponents are equal to zero.

A general formula

The aim of this section is to present a formula which relates the mixed discriminant with the resultant of the given polynomials and their toric Jacobian, whose definition we recall. Definition 6.3.1. Let f 1 (x 1 , . . . , x n ), . . . , f n (x 1 , . . . , x n ) be n Laurent polynomials in n variables. The associated toric Jacobian J T f equals x 1 • • • x n times the determinant of the Jacobian matrix of f, or equivalently, the determinant of the matrix:

      x 1 ∂f 1 ∂x 1 • • • x n ∂f 1 ∂x n . . . . . . . . . x 1 ∂f n ∂x 1 • • • x n ∂f n ∂x n       .
Note that the Newton polytope of J T f is contained in the sum of the Newton polytopes of f 1 , . . . , f n .

As we remarked before, we will mainly deal in this chapter with the case n = 2. Also, to avoid excessive notations and make the main results cleaner, we assume below that A 1 , A 2 are two finite lattice configurations whose convex hulls satisfy

dim(Q 1 ) = dim(Q 2 ) = 2.
Let f 1 , f 2 be polynomials with respective supports A 1 , A 2 :

f i (x) = ∑ α∈A i c i,α x α , i = 1, 2,
where x = (x 1 , x 2 ). We denote by Σ the set of primitive inner normals η ∈ (Z 2 ) * of the edges of A 1 + A 2 . We call A η i the face of A i where the inner product with η is minimized. We call this minumum value ν η i . We also denote by f η i the subsum of terms in f i with exponents in this face

f η i (x) = ∑ α∈A η i c i,α x α , i = 1, 2,
which is η-homogeneous of degree ν η i . Up to multiplying f i by a monomial (that is, after translation of A i ) we can assume without loss of generality that ν η i ̸ = 0. Now, A η i is either a vertex of A i (but not of both A 1 , A 2 since two vertices do not give a Minkowski sum edge), or its convex hull is an edge of A i (with inner normal η), which we denote by e η i . Note that if the face of A 1 + A 2 associated to η is a vertex, both polynomials f η i are monomials and their resultant locus has codimension two.

We denote by µ i (η) (i = 1, 2) the integer defined by the following difference:

µ i (η) = min{⟨η, m⟩, m ∈ A i -A η i } -ν η i . ( 6.6)
and by

µ(η) = min{µ 1 (η), µ 2 (η)}, (6.7)
the minimum of these two integers. Note that by our assumption that dim(Q i ) = 2, we have that µ(η) ≥ 1.

Without loss of generality, we can translate the support sets A η 1 , A η 2 to the origin and consider the line L η containing them. The residue (cycle

) Res A η 1 ,A η 2 (f η 1 , f η 2 )
is considered as before, with respect to the lattice L η ∩ Z 2 . Remark 6.3.2. As in Remark 6.2.3, if f η 1 is a monomial, the resultant equals the coefficient of f η 1 raised to the normalized length ℓ(e η 2 ) of the edge e η 2 of A 2 (that is, the number of integer points in the edge, minus 1). If η is an inner normal of edges A η 1 and A η 2 , then the resultant equals the irreducible resultant raised to the index of

ZA η 1 + ZA η 2 in L η ∩ Z 2 .
In particular, the exponent µ(η) = 1 if at least one of the configurations is full.

The following is our main result. Theorem 6.3.3. Let f 1 , f 2 be generic Laurent polynomials with respective supports A 1 , A 2 . Then,

Res A 1 ,A 2 ,A 1 +A 2 (f 1 , f 2 , J T f ) = ∆ A 1 ,A 2 (f 1 , f 2 ) • E,
where the factor E equals the finite product:

E = ∏ η∈Σ Res A η 1 ,A η 2 (f η 1 , f η 2 ) µ(η) .
Proof. Let X be the projective toric variety associated to A 1 + A 2 . This compact variety consists of an open dense set T X isomorphic to the torus (C * ) 2 plus one toric divisor D η for each η ∈ Σ. The Laurent polynomials f 1 , f 2 , J T f define sections L 1 , L 2 , L J of globally generated line bundles on X. The resultant Res A 1 ,A 2 ,A 1 +A 2 (f 1 , f 2 , J T f ) vanishes if and only if L 1 , L 2 , L J have a common zero on X, which could be at T X or at any of the D η .

There is an intersection point at T X if and only if there is a common zero of f 1 , f 2 and J T f in the torus (C * ) 2 . In this case, the discriminant

∆ A 1 ,A 2 (f 1 , f 2 ) would vanish. It follows that ∆ A 1 ,A 2 (f 1 , f 2 ) divides Res A 1 ,A 2 ,A 1 +A 2 (f 1 , f 2 , J T f ). (the indices [Z 2 : ZA 1 + ZA 2 ] and [Z 2 : ZA 1 + ZA 2 + Z(A 1 + A 2 )] are equal).
If instead there is a common zero at some D η , this translates into the fact that f η 1 , f η 2 and (J T f ) η = J T f η (with obvious definition) have a common solution. But as f η i are ηhomogeneous, they satisfy the weighted Euler equalities:

η 1 x 1 ∂f η i ∂x 1 + η 2 x 2 ∂f η i ∂x 2 = ν η i f i , i = 1, 2, (6.8)
from which we deduce that J T f η lies in the ideal I(f η 1 , f η 2 ) and so, the three polynomials will vanish exactly when there is a nontrivial common zero of f η 1 and f η 2 . This implies that all facet resultants Res A η

1 ,A η 2 (f η 1 , f η 2 ) divide Res A 1 ,A 2 ,A 1 +A 2 (f 1 , f 2 , J T f ).

Now, we wish to see that the resultant Res

A η 1 ,A η 2 (f η 1 , f η 2 )
raised to the power µ(η) occurs as a factor. The following argument would be better written in terms of the multihomogeneous polynomials in the Cox coordinates of X which represent L 1 , L 2 , L J [START_REF] Cattani | Residues and resultants[END_REF]. Fix a primitive inner normal direction η ∈ Σ of A 1 + A 2 , let t be a new variable and define the following polynomials

F i (t, x) = ∑ α∈A i c i,α t ⟨η,α⟩-ν η i x α , i = 1, 2, (6.9)
so that

F i (1, x) = f i (x), F i (0, x) = f η i (x), i = 1
, 2, and we can write

f η i (x) = F η i (t, x) -t µ i (η) G i (t, x), i = 1, 2, (6.10)
where the polynomials G i are defined by these equalities. The polynomials F 1 , F 2 , J T F define the sections L 1 , L 2 , L J . For each t, we deduce from the bilinearity of the determinant, that there exists a polynomial H(t, x) such that the toric Jacobian can be written as

J T F = J T f η + t µ(η) H(t, x).
But, as we remarked, J T f η lies in the ideal I(f η 1 , f η 2 ), and using the equalities (6.10), we can write

J T F = H 1 (t, x) + t µ(η) H 2 (t, x), with H 1 ∈ I(F 1 , F 2 ).
Note that if for instance η 1 ̸ = 0, then the power of x 1 in each monomial of F i can be obtained from the power of t and the power of x 2 , that is, we could use t and x 2 as "variables" instead. We will denote by Res X the resultant defined over X [START_REF] Cattani | Residues and resultants[END_REF]. Therefore,

Res A 1 ,A 2 ,A 1 +A 2 (f 1 , f 2 , J T f ) = Res X A 1 ,A 2 ,A 1 +A 2 (F 1 , F 2 , t µ(η) H 2 ).
Now, it follows from Theorem 6.2.4 that

Res X A 1 ,A 2 ,A 1 +A 2 (F 1 , F 2 , t µ(η) ) = Res A η 1 ,A η 2 (f η 1 , f η 2 ) µ(η) is a factor of Res A 1 ,A 2 ,A 1 +A 2 (f 1 , f 2 , J T f )
. Indeed, no positive power of t divides H 2 for generic coefficients. Considering all possible η ∈ Σ we get the desired factorization. Theorem 6.3.3 and the proof will be extended to the general n-variate setting in a forthcoming paper [START_REF] Dickenstein | Mixed discriminants and toric jacobians[END_REF]. We only state here the following general version without proof. Recall that a lattice polytope P of dimension n in R n is said to be smooth if at each every vertex there are n concurrent facets and their primitive inner normal directions form a basis of Z n . In particular, integer dilates of the unit simplex or the unit (hyper)cube are smooth. Theorem 6.3.4. Let P ⊂ R n be a smooth lattice polytope of dimension n. Let A i = (d i P ) ∩ Z n , i = 1, . . . , n, d 1 , . . . , d n ∈ Z >0 , and f 1 , . . . , f n polynomials with these supports, respectively. Then, we have the following factorization

Res A 1 ,...,An,A 1 +•••+An (f 1 , . . . , f n , J T f ) = ∆ A 1 ,...,An (f 1 , . . . , f n ) • E,
where the factor E equals the finite product:

E = ∏ η∈Σ Res A η 1 ,...,A η n (f η 1 , . . . , f η n ).
Note that all the exponents in E equal 1 and all the lattice indices equal 1.

When the given lattice configurations A i are the lattice points d i σ of the d i -th dilate of the standard simplex σ in R n , (that is, in the homogeneous case studied in [START_REF] Busé | A computational approach to the discriminant of homogeneous polynomials[END_REF]), formula (6.4) gives for any n in our notation:

Res

Res d 1 σ,...,dnσ,(d 1 +•••+dn)σ (f 1 , . . . , f n , J T f ) = ∆ d 1 σ,...,dnσ (f 1 , . . . , f n ) • n ∏ i=0 Res (d 1 σ) e i ,...,(dnσ) e i (f e i 1 , . . . , f e i n ).
It is straightforward to deduce from this expression the degree of the homogeneous mixed discriminant, obtained independently in [START_REF] Benoist | Degré d'homogénéité de l'ensemble des interactions complexes singulieres[END_REF][START_REF] Busé | A computational approach to the discriminant of homogeneous polynomials[END_REF][START_REF] Nie | Discriminants and non-negative polynomials[END_REF]. Similar formulas can be obtained, for instance, in the multihomogeneous case.

We recall the following definition from [START_REF] Cattani | Mixed discriminants[END_REF]. If v is a vertex of A i , we define its mixed multiplicity as

mm A 1 ,A 2 (v) := M V (Q 1 , Q 2 ) -M V (C i , Q j ), {i, j} = {1, 2}, (6.11)
where

C i = conv(A i -{v}).
Let Σ ′ ⊂ Σ be the set of inner normals of A 1 + A 2 that cut out, or define, edges e η i in both Q 1 , Q 2 . The factorization formula in Theorem 6.3.3 can be written as follows, and allows us to recover the bidegree formulas for planar mixed discriminants in [START_REF] Cattani | Mixed discriminants[END_REF]. Corollary 6.3.6. Let A 1 , A 2 be two lattice configurations of dimension 2 in the plane, and let f 1 , f 2 be polynomials with these respective supports. Then, the resultant of f 1 , f 2 and their toric Jacobian, namely

Res A 1 ,A 2 ,A 1 +A 2 (f 1 , f 2 , J T f )
, factors as follows:

∆ A 1 ,A 2 (f 1 , f 2 ) • ∏ v vertex of A 1 or A 2 c mm A 1 ,A 2 (v) v • ∏ η∈Σ ′ Res A η 1 ,A η 2 (f η 1 , f η 2 ) µ(η) . (6.
12)

The bidegree (δ 1 , δ 2 ) of the mixed discriminant ∆ A 1 ,A 2 (f 1 , f 2 ) in the coefficients of f 1 and f 2 , respectively, is then given by the following:

Vol(Q j ) + 2 • M V (Q 1 , Q 2 ) - ∑ η∈Σ ′ ℓ(e η j ) • µ(η) - ∑ v vertex of (A i ) mm A 1 ,A 2 (v), (6.13
)

where i ∈ {1, 2}, i ̸ = j.
Proof. To prove equality (6.12), we need to show by Theorem 6.3.3 that the factor

E = ∏ η∈Σ Res A η 1 ,A η 2 (f η 1 , f η 2 ) µ(η)
equals the product

∏ v vertex of A 1 or A 2 c mm A 1 ,A 2 (v) v • ∏ η∈Σ ′ Res A η 1 ,A η 2 (f η 1 , f η 2 ) µ(η) .
When η ∈ Σ ′ , i.e. η is a common inner normal to edges of both Q i , we get the same factor on both terms, since that our quantity µ(η) coincides with the index min{u(e 1 (η), A 1 ), u(e 2 (η), A 2 )}, in the notation of [START_REF] Cattani | Mixed discriminants[END_REF].

Assume then that η is only an inner normal to

Q 2 . So, A η 1 is a vertex v, f η 1 = cx v is a monomial (with coefficient c) and f η
2 is a polynomial whose support equals the edge e η 2 of A 2 orthogonal to η. In this case, Res A η

1 ,A η 2 (f η 1 , f η 2 ) = c ℓ(fη) by Remark 6.2.3. For such a vertex v, denote by E(v) the set of those η ′ / ∈ Σ ′ for which v + e η ′ 2 is an edge of Q 1 + Q 2 .
Note that it follows from the proof of [START_REF] Cattani | Mixed discriminants[END_REF]Prop.3.13] (cf in particular Figure 1 there), that there exist non negative integers µ ′ (η ′ ) such that

mm(v) = ∑ η ′ ∈ E(v) ℓ(e η ′ 2 ) • µ ′ (η ′ ). Indeed, µ(η ′ ) = µ ′ (η ′ ).
To compute the bidegree, we use the multilinearity of the mixed volume with respect to Minkowski sum. Observe that the toric Jacobian has bidegree (1, 1) in the coefficients For the denominator of (6.16), we use again Theorem 6.2.4 to write:

∏ η∈Σ ′ R A ′ 1 η ,A η 2 (f ′ 1 η , f η 2 ) µ ′ (η) • ∏ η∈Σ ′′ R A ′′ 1 η ,A η 2 (f ′′ 1 η , f η 2 ) µ ′′ (η) = ∏ η∈Σ R A ′ 1 η +A ′′ 1 η ,A η 2 (f ′ η 1 f ′′ η 1 , f η 2 ) µ(η) • E, because the products ∏ η∈Σ\Σ ′ R A ′ 1 η ,A η 2 (f ′ 1 η , f η 2 ) µ ′ (η) = ∏ η∈Σ\Σ ′′ R A ′′ 1 η ,A η 2 (f ′′ 1 η , f η 2 ) µ ′′ (η) = 1, since f ′ 1 η , f η 2 (resp. f ′′ 1 η , f η 2 )
are both monomials. To conclude the proof, simply assemble the above equations.

As a consequence, we have deg

A 1 ,A 2 ∆(f 1 , f 2 ) = = deg A ′ 1 ,A 2 ∆(f ′ 1 , f 2 ) + deg A ′′ 1 ,A 2 ∆(f ′′ 1 , f 2 ) + 2 • deg A ′ 1 ,A ′′ 1 ,A 2 R(f ′ 1 , f ′′ 1 , f 2 ) -deg(E).
When all the configurations are full and with the same normal fan, all the exponents µ(η) = µ ′ (η) = µ ′′ (η) = 1. Therefore, E = 1 and no extra factor occurs.

We define µ ′ 1 (η), µ ′′ 1 (η) as in (6.6). Indeed, we now fix η and will simply write µ ′ 1 , µ ′′ 1 , µ 1 , µ 2 . It happens that only one of the factors associated to η can occur in E with non zero coefficient. More explicitly, we have the following corollary, whose proof is straightforward. Corollary 6.4.2. With the notations of Corollary 6.4.1, for any η ∈ Σ it holds that:

• If µ ′ 1 = µ ′′ 1 , then µ ′ = µ ′′ = µ
and there is no factor in E "coming from η".

• If µ ′ 1 ̸ = µ ′′ 1 , assume wlog that µ 1 = µ ′ 1 < µ ′′ 1 .
There are three subcases: -If µ 2 ≤ µ 1 , again there is no factor in E "coming from η".

-If µ 1 = µ ′ 1 < µ 2 < µ ′′ 1 , then the resultant Res (A ′ 1 ) η ,A η 2 ((f ′ 1 ) η , f η 2 ) does not occur, but Res (A ′′ 1 ) η ,A η 2 ((f ′′ 1 ) η , f η 2 )
has nonzero exponent (this resultant could just be the coefficient of a vertex raised to the mixed multiplicity).

-If µ 1 = µ ′ 1 < µ ′′ 1 ≤ µ 2
, the situation is just the opposite than in the previous case.

Conclusion and future work

The intent of this book chapter was to present our main results relating the mixed discriminant with the sparse resultant of two bivariate Laurent polynomials with fixed support and their toric Jacobian. On our way, we deduced a general multiplicativity formula for the mixed discriminant when one polynomial factors as f = f ′ • f ′′ . This formula occurred as a consequence of our main result, Theorem 6.3.3, and generalized known formulas in the homogeneous case to the sparse setting. Furthermore, we obtained a new proof of the bidegree formula for planar mixed discriminants, which appeared in [START_REF] Cattani | Mixed discriminants[END_REF].

The generalization of our formulas to any number of variables will allow us to extend our applications and to develop effective computational techniques for sparse discriminants based on well tuned software for the computation of resultants.

ON THE SPACE OF MINKOWSKI SUMMANDS OF A CONVEX POLYTOPE

We present an algorithm for computing all Minkowski Decompositions (MinkDecomp) of a given convex, integral d-dimensional polytope, using the cone of combinatorially equivalent polytopes. An implementation is given in sage.

Introduction

Let A ∈ Z m×d be a matrix whose row vectors a i ∈ Z d positively span R d . For b ∈ R m the set In this work, we particularly focus on the integral decomposition of polytopes. The integral decomposition of polytopes has applications in various areas of mathematics such as integer and mixed integer programming [START_REF] Henk | Integral decompositions of polyhedra and some applications in mixed integer programming[END_REF], polynomial factorization [START_REF] Gao | Decomposition of polytopes and polynomials[END_REF] or implicitization [START_REF] Emiris | Minkowski decomposition and geometric predicates in sparse implicitization[END_REF]. Since it may happen that an integral polytope has a rational but not an integral decomposition, such a distinction does make sense. Although, qualitatively, a dilation resolves this problem, in many applications, e.g., factorization of polynomials, such a step is not allowed.

P b = {x ∈ R d | Ax ⩽ b}
Previous work on MinkDecomp algorithms mainly focuses in low dimension [START_REF] Emiris | Minkowski decomposition of convex lattice polygons[END_REF][START_REF] Emiris | Minkowski decomposition and geometric predicates in sparse implicitization[END_REF][START_REF] Gao | Decomposition of polytopes and polynomials[END_REF].

The problem of computing a Minkowski summand in general dimension is reduced to the feasibility of a linear program [START_REF] Kesh | Polynomial irreducibility testing through Minkowski summand computation[END_REF], thus deciding if a polytope is decomposable in order to test polynomial irreducibility. In [START_REF] Eisenschmidt | Computation of atomic fibers of z-linear maps[END_REF][START_REF] Henk | Integral decompositions of polyhedra and some applications in mixed integer programming[END_REF] is explored the cone of combinatorially equivalent polytopes and its computational aspects. Some classical work on polytope decomposition is presented in [START_REF] Mcmullen | Representations of polytopes and polyhedral sets[END_REF].

Computing the Space of Minkowski Summands

A system of inequalities Ax ⩽ b is feasible if it has a solution. Feasibility is characterized by Farkas' lemma. Switching from the H-representation to its V -representation, the cone U (A) is generated by 9 rays and 3 lines in Z 10 .

                0 1 1 1 0 1 1 0 0 0 1 0 0 0 -1 0 0 1 0 -1 0 0 -1 1 -1 0 0 -1 0 1                   x y z   ⩽                 4 4 3 3 0 2 0 1 0 1                 (7.
The normal cone of a face F of a polytope P in R d is the set

N (F ; P ) = {v ∈ R d | v ⊤ x = h(P, v) for all x ∈ F }.
The dimension of the normal cone of a k-dimensional face is (d-k). The normal fan N (P ) of P, which is the collection of the normal cones of all faces of P , is a complete fan in R d .

The support function of a polytope P in R d , h(P, ; ), is defined over all u ∈ R d as h(P, u) = max{u ⊤ x : x ∈ P }. In geometric terms, the evaluation of the support function at u ∈ R d implies that the hyperplane H u : x ⊤ u = h(P, u) contains P in one of its closed halfspaces and H u ∩ P ̸ = ∅. We call every such H u an active or supporting hyperplane of P .

Definition 7.2.2. Two polytopes

P, Q in R d are strongly combinatorially equivalent if, for all v ∈ R d dim{y ∈ P | v ⊤ y = h(P, v)} = = dim{y ∈ Q | v ⊤ y = h(Q, v)}.
If polytopes P, Q have the same defining hyperplanes, as in our setup, their normal fans are related by inclusion, i.e., one fan is a subfan of the other. If, in addition, P, Q are strongly combinatorially equivalent, Definition 7.2.2 implies N (P ) = N (Q). We can therefore say that two polytopes are strongly combinatorially equivalent if and only if they have the same normal fan.

Let us give some definitions related to MinkDecomp. Polytopes P 1 , P 2 in R d are homothetic if P 1 = ρP 2 + v for some v ∈ R d and ρ > 0. Definition 7.2.3. A polytope P in R d is called (homothetically) decomposable if two polytopes P 1 and P 2 exist with P = P 1 + P 2 , where P i in not homothetic to P for i ∈ {1, 2}. Otherwise P is (homothetically) indecomposable.

A polytope P 1 is a summand of a polytope P (denoted as P 1 ≺ P ) if there exists a scalar ρ > 0 and a polytope P 2 such that P = ρP 1 + P 2 .

In view of the definition above, trivial polytopes, i.e., points, are indecomposable.

For b ∈ U (A), we define the support vector η b of the polytope P b as η b = (h(P b , a 1 ), h(P b , a 2 ), . . . , h(P b , a d )) .

We note that η b ∈ Z m is the componentwise-least right hand side for which P b = P η b . Let us now define the set

U (A) b := {η v | v ∈ U (A) such that P v ≺ P b }. (7.4)
In [START_REF] Henk | Integral decompositions of polyhedra and some applications in mixed integer programming[END_REF][START_REF] Mcmullen | Representations of polytopes and polyhedral sets[END_REF][START_REF] Meyer | Indecomposable polytopes[END_REF], the authors show that U (A) b is a rational polyhedral subcone of U (A) whose structure and extreme rays convey important information on decomposability.

Theorem 7.2.4. [START_REF] Mcmullen | Representations of polytopes and polyhedral sets[END_REF], [START_REF] Meyer | Indecomposable polytopes[END_REF] The set U (A) b := {η v : v ∈ U (A) such that P v ≺ P b } is a rational polyhedral subcone of U (A) whose extreme rays correspond to indecomposable polytopes and its interior consists of all b ′ for which P b ′ is strongly combinatorially equivalent to P b .

Since U (A) b is a subcone of the homogeneous (i.e., defined by linear halfspaces) cone U (A), we wish to express U (A) b as a set of linear inequalities of type a ⊤ v ⩾ 0 where a, v ∈ R m . These inequalities should be imposed from the feasibility of Ax ⩽ v but, more importantly, they should incorporate the fact that strong combinatorial equivalence is preserved over all faces as well.

Since each face F of P b can be viewed as a polytope, we can express it as a set {x ∈

R d : A F x ⩽ b F } where A F ∈ Z λ×d , b F ∈ Z λ and λ ∈ N.
In this context, we can define U (A F ) and find its subcone U (A) b F containing all those y ∈ Z λ for which the polytope {x ∈ R d : A F x ⩽ y} is combinatorially equivalent to F . However, without reference to the original polytope P b , the computation of U (A F ) b F does not keep track of the restrictions imposed on the elements of U (A) b . This indicates that F should be expressed using equalities and inequalities from the original system Ax ⩽ b.

Example (Cont'd)

We will apply the procedure described above on a face of our example. Let us pick the facet F defined by

[1, 0, 1] ⊤ [x, y, z] = b 1 . Then the system A F x ⩽ b for the facet F is                   0 1 1 1 0 1 1 0 0 0 1 0 0 0 -1 0 0 1 0 -1 0 0 -1 1 -1 0 0 -1 0 1 -1 0 -1                     x y z   ⩽                   b 0 b 1 b 2 b 3 b 4 b 5 b 6 b 7 b 8 b 9 -b 1                   (7.5)
For the polyhedron defined by System (7.5), we obtain the following H-representation of U (A F ): The idea in Algorithm 4 is to repeat the above procedure for every face of the input polytope so that none of them "loses support". Note that visiting each face of P b is essential. If, for example, in the polytope of Figure 7.1 the algorithm does not visit the top facet, then some b ′ in the interior of U (A) b corresponds to the square pyramid. This happens because no restriction prevents the four top vertices to behave as one. This, however, is not acceptable since the square pyramid is not strongly combinatorially equivalent to P b . Also, starting with U (A) is necessary, since it determines the orientation of the outer normals of P b . If in our example we started the algorithm with U (A) = ∅, then we would get the reverse square pyramid as a summand of the polytope, which is not true.

Using the knowledge of the structure of the cone of combinatorially equivalent polytopes, we can compute all indecomposable Minkowski summands of a given polytope. It is however essential, once we have computed the rays of U (A) b , to read out those which produce non-trivial indecomposable polytopes. This is the content of Proposition 7.2.5.

We say that Ax ⩽ b, A ∈ Z m×d is an irredundant description of P b = {x : Ax ⩽ b}, if the removal of any of the inequalities of the linear system, results in a different polytope (or polyhedron). Notice that this is stronger than requiring b to be the support vector

P b = λ 1 P b 1 + • • • + λ k P b k + T (7.6)
where λ 1 , . . . , λ k ⩾ 0 and T = µ

1 P c 1 + • • • + µ d P c d , µ 1 , . . . , µ d ∈ R, is a translation.
Lemma 7.2.6. For each polytope

P c = {x ∈ R d : Ax ⩽ c}, A ∈ R m×d , 0 ̸ = c ∈ R d , such that Ax ⩽ c is feasible, 1. if Ax ⩽ -c is feasible then P c is a point 2. if Ax ⩽ -c

Example (Cont'd)

We consider the intersection I = U (A) ∩ i F i of all cones corresponging to faces F i of the polytope. We compute the V -representation of U (A) b and get its rays; I is a 7-dimensional cone, with rays:

b i Ax ⩽ b i vertex set: ±(1, 1, 0, 0, -1, 1, 0, 1, 0, 1) 0-dim {(0, 0, ±1)} ±(1, 1, 0, 0, -1, 1, 0, 1, 0, 1) 0-dim {(±1, 0, 0)}
±(1, 0, 0, 1, 0, 0, -1, -1, 0, 0) 0-dim {(0, ±1, 0)} (0, 0, 0, 0, 0, 0, 1, 1, 0, 0) 1-dim {(0, 0, 0), (0, -1, 0)} (0, 0, 0, 0, 0, 0, 0, 0, 1, 1) 1-dim {(0, 0, 0), (-1, 0, 0)} (1, 1, 0, 0, 0, 1, 0, 1, 0, 1) 1-dim {(0, 0, 0), (0, 0, 1)} (0, 0, 0, 0, 0, 1, 2, 2, 2, 2) 2-dim {(0, 0, 0), (-2, 0, 0), (0, -2, 0), (-2, -2, 0), } (-1, -1, 1)}

The rays ±b 1 , ±b 2 , ±b 3 correspond to points. The next three rays correspond to line segments and the last ray corresponds to a square pyramid, which are exactly the Minkowski summands of the polytope defined by System (7.3).

In order to find integer indecomposable summands, the rays of U (A) b may not suffice since they only convey information about the combinatorial type of a polytope.

To resolve this issue, we find an appropriate integer polytope corresponding to each P b i in Equation (7.6). More precisely, we find an integer polytope P b ′ i , combinatorially equivalent to P b i , such that for all 0 < λ < 1 and all v ∈ R d the polytope λP b ′ i + v is not integer. The first step is to dilate/shrink P b i enough, so that we get the "smallest possible" integer polytope corresponding to b i . This can be achieved in the following way: First ensure that one of the vertices of P b i is the origin, by translating the polytope if needed. Now consider the vertices v j = ( vs) is an integer polytope with the additional property that for any 0 < λ < 1 the polytope λP ′ b i is not.

a j1 b j1 , . . . , a jd b jd ) ∈ Q d , 1 ⩽ j ⩽ s, of P b i , where each a jk b jk is in reduced form. Then, define: gcd(v 1 , . . . , v s ) := gcd{a jk : 1 ⩽ j ⩽ s, 1 ⩽ k ⩽ d}, lcm(v 1 , . . . , v s ) := lcm{b jk : 1 ⩽ j ⩽ s, 1 ⩽ k ⩽ d}. It is not hard to see that P ′ b i := {x : Ax ⩽ λ ′ b i } where λ ′ = λ ′ (P b i ) := lcm(v 1 ,...,vs) gcd(v 1 ,...,
∑ j µ j cj yields a decomposition of P b as in Equation (7.6). If we want to find integral decompositions of P b , then the choices for the above λ i , µ j should be integers. This allows only a finite number of decompositions. is defined by adding each vector in A to each vector in B, namely:

A + B = {a + b | a ∈ A, b ∈ B}.
Problem 6. Minkowski Decomposition (MinkDecomp). Given a lattice convex polygon Q, decide if it is decomposable, that is, if there are nontrivial lattice polygons A and B such that A + B = Q, where + denotes Minkowski addition. Polygons A and B are called summands.

Problem 6 is proven NP-complete by Gao and Lauder [START_REF] Gao | Decomposition of polytopes and polynomials[END_REF] and can be reduced to a two dimensional Subset Sum problem as defined in Problem 8. For the reduction see Section 8.4. The approximation version of MinkDecomp can be defined as follows.

Problem 7. MinkDecomp-µ-approx.

Input: A lattice polygon Q, a parameter 0 < ϵ < 1 and a function µ. Output: Lattice polygons A, B such that 0 ≤ µ(A+B)-µ(Q) < ϵ•ϕ(D), where µ expresses a geometric property of a polygon, D is the diameter of Q, and ϕ a polynomial. We call such an output an ϵ • ϕ(D)-solution.

(Q, A + B) instead of µ(A + B) -µ(Q).
The problem is straightforward for ϵ > 1/2 by using an enclosing rectangle.

Problem 8. kD-Subset Sum (kD-SS).

Input: A multiset of vectors S = {v i | 1 ⩽ i ⩽ n} ⊂ Z k , for k ⩾ 1, and a target vector t ∈ Z k . Output: YES, if there exists a subset S ′ ⊆ S such that ∑ v i ∈S ′ v i = t, and NO otherwise.

We use a multiset to allow for multiple occurrence of the same vector. This is a generalization of the classic 1D-SS problem, and as such, it is also NP-complete. Here is the approximation version:

Problem 9. kD-SS-opt. Input: A multiset S = {v i | 1 ⩽ i ⩽ n} ⊂ Z k , for k ⩾ 1, and a target t ∈ Z k . Output: Subset S ′ ⊆ S whose corresponding vector sum t ′ = ∑ v i , v i ∈ S ′ , minimizes dist(t, t ′ ).
We consider the Euclidean distance l 2 throughout the paper, except where noted otherwise. Our algorithms could be generalized to any distance norm l p , 1 ⩽ p < ∞, due to the equivalence of any two norms on a finite-dimensional vector space. For more details see [START_REF] Carothers | Real Analysis[END_REF]Thm 8.22]. Definition 8.1.2. A PTAS (Polynomial Time Approximation Scheme) is an algorithm, which receives as input an instance of an optimization problem and a parameter ϵ > 0 and, in polynomial time in input size n (but with arbitrary dependence on ϵ), produces a solution which is within a factor 1+ϵ of being optimal for minimization problems or within 1-ϵ of the optimal for maximization problems. A PTAS can be specialized in two ways. An EPTAS (Efficient PTAS) has time complexity polynomial in n but independent of ϵ, and an FPTAS (Fully PTAS) has time complexity polynomial in both n and ϵ.

APX is the set of NP optimization problems that allow polynomial-time approximation algorithms with approximation ratio bounded by a constant. This class contains every problem with a PTAS. 1D-SS is not strongly NP-complete and can be solved exactly in pseudopolynomial time: given a multiset S of n positive integers and a target integer t > 0, this problem asks whether there exists a subset S ′ of S summing up to exactly t. This is solved in O(nt) by standard methods, see [START_REF] Cormen | Introduction to Algorithms[END_REF]; in fact these methods shall inspire our algorithms below. The current record bound has been recently improved to Õ( √ nt) [START_REF] Koiliaris | A faster pseudopolynomial time algorithm for subset sum[END_REF], where the soft big-Oh notation Õ shows that we have ignored polylogarithmic factors. In [START_REF] Bringmann | A near-linear pseudopolynomial time algorithm for subset sum[END_REF], they present a simple randomized algorithm running in Õ(n + t), which is likely to be near-optimal. This yields improvements upon the best known polynomial-space algorithms from time Õ(n 3 t) and space Õ(n 2 ) to time Õ(nt) and space Õ(n log t), assuming the Extended Riemann Hypothesis. Unconditionally, they obtain time Õ(nt 1+ρ ) and space Õ(nt ρ ) for any constant ρ > 0 All of these results concern randomized algorithms.

Let P i be the set of all possible vector sums that can be produced by summing up i vectors among the vectors of S. Then, P n ⊂ Z k is the set of all possible vector sums. Generalizing the idea of 1D-SS, kD-SS is solved in O(n|M n | k ), where M n = max P n is the farthest reachable point as a sum of input vectors. Moreover, 1D-SS-opt has an FPTAS, see [START_REF] Ibarra | Fast approximation algorithms for the knapsack and sum of subset problems[END_REF]. A related problem is the Multidimensional Knapsack. Firstly, it was proved in [START_REF] Magazine | A note on approximation schemes for multidimensional knapsack problems[END_REF], that this problem does not have an FPTAS. Later, in [START_REF] Kulik | There is no EPTAS for two-dimensional knapsack[END_REF], it was shown that it does not have an EPTAS, while Knapsack has an FPTAS, see [START_REF] Woeginger | When does a dynamic programming formulation guarantee the existence of an FPTAS?[END_REF][START_REF] Woeginger | When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?[END_REF]. The optimization version of 1D-SS is a special case of Knapsack and both are defined as maximization problems. In two or higher dimensions, it makes more sense to define kD-SS as a minimization problem, since a vector sum with maximum length may be far from the target vector. In fact, in dimension two or higher, the problem is not related to Multidimensional Knapsack but rather to CVP.

In the Closest Vector Problem (CVP), we are given a set of basis vectors B = {b 1 , . . . , b n }, where b i ∈ Z k , and a target vector t ∈ Z k , and we have to compute the closest vector to t in the lattice L(B) generated by B, where

L(B) = { n ∑ i=1 a i b i | a i ∈ Z}.
CVP is known to be in APX, and it is known that it cannot be approximated within a factor of 2 log 1-ϵ n with ϵ = (log(log n)) c , for c < 1/2 [START_REF] Arora | The hardness of approximate optima in lattices, codes, and systems of linear equations[END_REF][START_REF] Dinur | Approximating CVP to within almostpolynomial factors is NP-hard[END_REF].

MinkDecomp has received a fair share of attention. One application is in the factorization of bivariate polynomials through their Newton polygons: Consider a bivariate polynomial f ∈ K[x, y]. To each monomial x i y j appearing in f with a nonzero coefficient, we associate point (i, j) in the Euclidean plane. The Newton polygon of f is the convex hull of all these points. As noticed by Ostrowski in 1921, if a polynomial factors, then its Newton polygon has a Minkowski decomposition. An algorithm for polynomial irreducibility testing using MinkDecomp is presented in [START_REF] Kesh | Polynomial irreducibility testing through Minkowski summand computation[END_REF], motivated by previous similar work in [START_REF] Gao | Absolute irreducibility of polynomials via newton polytopes[END_REF]. They present a criterion for MinkDecomp that reduces the decision problem to a linear programming question. In [START_REF] Emiris | On the space of minkowski summands of a convex polytope[END_REF] they compute all possible Minkowski summands and not those in a particular Minkowski decomposition. The integer decomposition of polytopes has applications in various areas of mathematics such as integer and mixed integer programming [START_REF] Henk | Integral decomposition of polyhedra and some applications in mixed integer programming[END_REF].

Extending some results of [43, sec.4,5], we propose a polynomial-time algorithm that solves MinkDecomp approximately using a solver for 2D-SS-opt. A preliminary version of most of these results can be found in [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF] and in [START_REF] Emiris | Approximate subset sum and minkowski decomposition of polytopes[END_REF].

kD-SS-opt is not in APX

This section establishes that kD-SS-opt is not in APX, for general dimension k. For this, we shall adapt the approach used to prove that CVP is not in APX, see [START_REF] Arora | The hardness of approximate optima in lattices, codes, and systems of linear equations[END_REF]. Proposition 8.2.1. [START_REF] Bellare | Efficient probabilistically checkable proofs and applications to approximations[END_REF]Lem.4.1] For every c > 1 there is a polynomial time reduction that, given an instance ϕ of SAT, produces an instance of Set Cover {U, (S 1 , . . . , S m )} where U is the input set of integers and S 1 , . . . , S m are subsets of U, and integer K with the following property: If ϕ is satisfiable, there is an exact cover of size K, otherwise all set covers have size more than cK.

Given a CNF formula ϕ we invoke Proposition 8.2.1 and get an instance of the Set Cover problem. This is a gap introducing reduction; because if ϕ is satisfiable then the instance of Set Cover has a solution of size exactly K and if ϕ is not satisfiable every solution has size at least cK for a constant c. From this instance of Set Cover we create an instance for kD-SS-opt that preserves the gap. Now, if ϕ is satisfiable, the closest vector to a given target t has distance exactly K. If ϕ is not satisfiable, the closest vector in target t has distance at least cK.

We reduce kD-SS-opt to Set Cover for norm l 1 , but this can easily be generalized to any l p , where p is a positive integer. We say that a cover is exact if the sets in the cover are pairwise disjoint. Theorem 8.2.2. Given an instance U, (S 1 , . . . , S m ), K of the Set Cover problem where U is the set of elements, S i ⊂ U and K ∈ Z, we create an instance {v 1 , . . . , v m ; t} of kD-SS-opt. If the instance of the Set Cover has an exact cover of size K, then the minimum distance of a possible vector sum from t is smaller than K, otherwise it is larger than cK.

Proof. Let v i ∈ Z n+m , where |U| = n. We will create such a vector v i for every set S i , 1 ⩽ i ⩽ m. Let L = cK. Then the first n coordinates of each vector v i have their j-th coordinate (j ⩽ n) equal to L if the corresponding j-th element belongs to set S i , or 0 otherwise. The remaining m coordinates have 1 in the (n + i)-th coordinate and zeros everywhere else:

v i = (L • χ S i , 0, . . . , 1, . . . 0) = (L • χ S i , e i ),
where χ S i is the characteristic function of the set S i . The target vector t has in the first n coordinates L and the last m coordinates are zeros, t = (L, . . . , L, 0, . . . , 0). Now, let the instance of Set-Cover have an exact cover of size K. We will prove that the minimum distance of every v ∈ P n from target t is less than K. Without loss of generality, let the solution be {S 1 , . . . , S K }. For each S i , 1 ⩽ i ⩽ K, sum the corresponding vectors v i and let this sum be ζ ∈ Z n+m :

ζ = K ∑ i=1 v i = (L, . . . , L, n 1, . . . , 1 K 0, . . . , 0 m-K
).

The first n coordinates must sum up to (L, L . . . , L), because if one of the coordinates was 0, the solution would not be a cover and if one of them was greater than L, then some element is covered more than once and the solution would not be exact. Note that each of the first n coordinates is either 0 or greater than L. The key point is that in the last m coordinates we will have exactly K units and everything else 0. The distance of this vector

ζ from t is ∥ -t + ζ∥ 1 = ∥(0, . . . , 0, n 1, . . . , 1 K 0, . . . , 0 m-K )∥ 1 = K
Thus, there is a point in P n that its distance from t is at most K.

Let us consider the other direction, where the Set Cover instance has a solution set which contains a vector whose distance from t is larger than cK = L. We will show that the closest vector to t has distance at least L from t. This solution must have at least cK = L sets. As before, ∥ -t + ζ∥ 1 ⩾ L (this time the cover need not be exact).

Towards a contradiction, suppose there exists a vector ξ such that ∥ -t + ξ∥ 1 < L. If the corresponding sets do not form a cover of S, then one of the first n coordinates of ξ is 0 and this alone is enough for ∥ -t + ξ∥ 1 > L. If the sets form a cover that is not exact, then in at least one of the first n coordinates of ξ will be greater than L (for the element that is covered more than once) and will force ∥ -t + ξ∥ 1 to be greater than L. Finally, if the sets form an exact cover, the first n coordinates of ∥ -t + ξ∥ 1 will be 0. For the distance to be less than L, in the last m coordinates there must be less than L units implying that the sets in the cover are less than L contradicting our hypothesis.

In all cases, there cannot exist a vector whose distance from t is less than cK. We must run algorithm A with a suitable parameter ϵ so we can distinguish if the optimum solution t * is within distance K or not. When ϕ is satisfiable we would want (1 + ϵ)K < cK =⇒ ϵ < c -1. Set c ′ < c -1, call A with parameter ϵ = c ′ and let t ′ be the returned vector. In the case where ϕ is satisfiable and OP T ⩽ K we have

∥t -t ′ ∥ 1 ⩽ (1 + ϵ)OP T < cK
Of course if ϕ is not satisfiable for any t ′ we have that ∥t -t ′ ∥ 1 > cK. Thus, ∥t -t ′ ∥ 1 < cK if and only if ϕ is satisfiable. Since ϵ is a constant and A is in APX, we can decide SAT in polynomial time.

Although there can be no algorithm that returns a constant factor approximation with multiplicative error for general dimension k, we will present algorithms that approximate the solution with additive error, in the plane. Specifically, the returned vector t ′ is an (OP T +ϵM n ) solution, where M n = max P n is the largest possible vector sum.

Approximation algorithms for 2D-SS-opt

This section presents and analyzes three algorithms for 2D-SS-opt with additive error. The first is meant to introduce our algorithmic tools. The next two are implemented since they are more efficient in practice. The last one, the hybrid algorithm, combines ideas from the first two, namely annulus-slice and the grid-based algorithm. Whenever we refer to distance, it is the Euclidean distance.

The annulus-slice algorithm

The idea of this algorithm is to create all possible vector sums, step by step. At each step, if two vector sums are close to each other, one is deleted. The algorithm is given in Algorithm 5, Algorithm 6. Let us start with some notation.

• Input: the multiset S = {v i | 1 ⩽ i ⩽ n} for v i ∈ Z 2 and a parameter 0 < ϵ < 1 that bounds the Euclidean distance between the optimal and the returned solution.

• P i is the set of all possible vectors that can be produced by adding the first i vectors from S. P n is the set of all possible vector sums.

• E i = L i-1 ∪ [w + v i | w ∈ L i-1 ]
is the list created at the beginning of every step and that is about to get trimmed.

• L i =trim(E i , δ) is the trimmed list and δ = ϵ/2n, 0 ⩽ δ ⩽ 1. Notice that L i , E i ⊂ Z 2 .
At the beginning of the i-th step we create the list

E i = L i-1 ∪ [w + v i | w ∈ L i-1 ]
. Notice that addition is over Z 2 . After a point is found we calculate its length, sort E i based on the lengths and call trim (E i , ϵ/2n). For each vector u ∈ E i with length |u| and angle θ(u) from the x-axis, check all the vectors u ′ ∈ E i that have length that satisfy the condition: The distances are shown and the furthest point is in distance αδ|v|. b) After the trim a few cells remain. Every vector in the cells will be deleted and "represented" by one of the black vectors shown. Notice that the size of each cell depends on the vector that creates it: the shorter the vector the smaller the cell.

|u| ⩽ |u ′ | ⩽ (1 + δ)|u|. ( 8
If they also satisfy the condition:

θ(u) -δ ⩽ θ(u ′ ) ⩽ θ(u) + δ, (8.2)
remove u ′ from E i . The remaining trimmed list is the list L i . The two conditions ensure that dist(u ′ , u) ⩽ αδ|u|, where 1 ⩽ α ⩽ 2 is a constant. Indeed as seen in Figure 8.1 a), we use the cosine rule for the angle θ(u) -θ(u ′ ) which is at most δ to get the desired.

Every vector that is deleted from E i is not very far away from a vector in L i : Since all vectors have integer coordinates, any vector u ∈ E i such that |u| < 1/αδ < √ 2n/ϵ implies that αδ|u| < 1. Thus, the area around u does not contain any other other lattice points except u. Proof. Every vector in E i has length between (1+δ) r and (1+δ) r+1 . These are circles with center (0, 0) and radius (1+δ), (1+δ) 2 , . . . , (1+δ) r for some r. We call every two successive circles from an annulus a zone. We must cover all u ∈ P n , and r is the minimum such that (1 + δ) r > M n , where M n is the vector in E n with the largest length. Solving (1 + δ) r ⩾ M n for r, we get r ⩾ log 1+δ M n . We know that log(1 + δ) ⩽ δ for δ > -1. Therefore r ⩾ log M n log(1 + δ) ⩾ log M n δ .

∀u ∈ E i ,
Thus r = O(n ln M n /ϵ). Therefore, there are O(n log M n /ϵ) = O(n 2 /ϵ) many zones that can be created. Every zone is divided into cells. Each cell is taken in such a way that it covers 2δR of the inner circle of the zone, where R is the radius of this circle (Figure 8.1a). Thus, every zone between the circles with radius R and (1 + δ)R has at most 2πR/δR = 4πn/ϵ cells.

Since a list L i has at most an entry for every cell created in every zone, its size can be at most (n 2 /ϵ) • (4πn/ϵ) = O(n 3 ϵ -2 ).

L 0 =∅ for v i ∈ S do E i = L i-1 ∪ [L i-1 + [v i ]] L i = trim (E i , ϵ/2n) return L n
Let us now establish correctness of the algorithm. (8.4)

Since p ∈ L n-1 this means that p + v n ∈ E n and L n = trim (E n ). From the guarantee of function trim we know that ∃q ∈ L n : p + v n = q + r q , |r q | ⩽ δ|q|. (8.5) From (8.4), (8.5) we obtain v = z + v n = p + v n + r p = q + r q + r p . This proves that for v ∈ P n , there exists a vector q ∈ L n that approximates it; but how close are they? We will bound the length |r q + r p |. From (8.4) we get

|r p | ⩽ (n -1)δ max{L n-1 } ⩽ (n -1)δM n ,
and from (8.5) we get |r q | ⩽ δ|q|, q ∈ L n =⇒ |r q | ⩽ δM n .

Thus, |r q + r p | ⩽ |r q | + |r p | ⩽ (n -1)δM n + δM n ⩽ nδM n .

Setting δ = ϵ/2n, we ensure that every possible vector sum will be approximated by a vector in L n at most ϵM n far (Figure 8.2). Implementing and testing the algorithm, much better bounds are obtained, see Section 8.5.

Grid-based algorithm

In this subsection we describe a O(n 3 /ϵ 2 ) approximation grid-based algorithm for 2D-SS.

The input is a multiset S = {v i | 1 ⩽ i ⩽ n}, v i ∈ Z 2 . We define the list

E i = L i-1 ∪ [w + v i | w ∈ L i-1
] and, at step i, we trim it via Algorithm 5, using parameter δ to obtain trimmed list L i = trim (E i , δ) ⊂ Z 2 . Let P i be now the set of all possible vector sums defined by any subset of the first i vectors of S.

It turns out that the same approximation ratio ϵM n can be achieved by a faster algorithm that subdivides the plane into a grid, where vector M n ∈ E i has maximum length. Instead of creating different annulus-slice cells, we define a regular orthogonal grid cells. In the worst case we will have a vector in every cell and this means that the time to traverse the lists E i at each step is O(n 2 ϵ -2 ). Since we have n lists the total running time of the new algorithm is O(n 3 ϵ -2 ) and the space requirements are O(n 2 ϵ -2 ).

Also, every u ∈ P n is the sum of at most n vectors from S. In the worst case, every time we call trim, we represent a vector u ∈ E i by another one that has distance form u at most d. In that case we lost at most nd = ϵM n /2:

∀v ∈ P n ∃w ∈ L n : dist(v, w) ⩽ ϵM n .
Thus, for every given target vector t the algorithm will return an approximation solution that is nd = ϵM n far from being optimum. See ) and returns a solution t ′ such that dist(t, t ′ ) ⩽ OP T + ϵM n .

In the 2D case there is a factor of √ 2 that we omit from our approximation. This happens because the maximum distance inside a cell is not d but √ 2d. In general dimension k, the minimum distance is √ kd and this affects the algorithm in higher dimensions. However, using a general principle to turn pseudopolynomial dynamic programming algorithms into approximation algorithms, see [START_REF] Woeginger | When does a dynamic programming formulation guarantee the existence of an FPTAS?[END_REF][START_REF] Woeginger | When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?[END_REF], the algorithm generalizes to higher dimensions.

Hybrid algorithm

In this subsection we describe an algorithm that is a combination of annulus-slice and the grid-based algorithm, and is expected to perform better in practice.

The grid-based algorithm reduces the length of a vector by at most d. This reduction does not depend on the length of the vectors. On the other hand, it is fast, because it does not have to check any other vectors; for every vector it sees it rounds it on the spot, thus having linear time in the size of the lists. We can make a version of a circular grid, where each cell does not have a constant side length. For small vectors we create smaller cells and, as the length increases, so does the cell side. This way we can provide a better experimental approximation ratio. At step i, we have the list E i and we trim it with a factor δ. We will consider the polar coordinates of the vectors. For a vector v(ϕ, r) let ϕ = θ(v) be the angle with the x axis and r = |v| its Euclidean length. Let v be a vector in E i and, to get the list L i , we will replace v by v ′ = (ϕ ′ , r ′ ). First round its angle to a multiple of δ : ϕ ′ = ⌊ϕ/δ⌋. Next, we round its length. The idea is to round in such a way that shorter vectors are approximated better than the longer ones. We construct an array A with all the acceptable rounded lengths. The entries of A are the lengths [1, (1 + δ), . . . , (1 + δ) i ] for the minimum i, such that (1 + δ) i > M n . Solving this inequality we get that i = O(n log M n /ϵ), and this is the size of A. Now, for a vector v we just make a binary search in A for |v| that returns the zone such that and guarantees the same approximation error, since ∀v ∈ E i , ∃w ∈ Li : dist(v, w) ⩽ ϵ|w| as before. Lastly, the binary search may be avoided by using a method to round the lengths in O(1) time, thus avoiding the log |E i | factor. Therefore we arrive at the following lemma:

Lemma 8.3.5. With the above notation, the hybrid approximation algorithm runs in time O(n 3 ϵ -2 log M n ).

We expect the algorithm to offer better approximations in practice.

Approximating Minkowski Decomposition using 2D-SS-opt

In this section, we describe an algorithm for approximating MinkDecomp. We also state the connection between the Problem 7 and the proposed algorithm in Theorem 8.4.3, where we describe the solution that the algorithm provides for the MinkDecomp-µ-approx.

The algorithm takes an input polygon Q, transforms it to an instance {S, t} of 2D-SS-opt and calls the algorithm for the latter. Then the output is converted to an approximate solution to MinkDecomp. We remark that the algorithms for 2D-SS-opt return an array of several possible solutions. So the trivial ones can be ruled out.

Let Q be the input to MinkDecomp: Q = {v i | 0 ⩽ i ⩽ n} for v i ∈ Z 2 , such that ∑ n 0 v i = (0, 0). First, we create the multiset s(Q) of vectors by subtracting successive vertices of Q (in clockwise order): s(Q) = {v 0 -v 1 , v 1 -v 2 , . . . , v n -v 0 }. Each vector in s(Q) is called an edge vector and s(Q) is called the edge sequence of Q: For every edge vector (x, y) ∈ s(Q) we calculate its primitive vector e = (x/d, y/d). For each vector in s(Q), we compute the scalars d 0 , . . . , d ⌊log 2 d/2⌋+1 as follows: The sum of all vectors in S is also (0, 0). Using this construction, the number of the primitive vectors included are about log d for every v ∈ s(Q) keeping the size of S polynomial with respect to the number of edges of Q.

d i = 2 i , i =
As an example take an edge with endpoints (0, 0) and (100, 0) and the associated vector is v = (100, 0). Then d = 100 and e = (1, 0). Instead of including the vector (1, 0) 100 times we include in s(Q) the vectors: (1, 0), (2, 0), (4, 0), (8, 0), (16, 0), (32, 0) and (37, 0). Multiset S corresponds to a unique polygon up to translation determined by v 0 . This is a standard procedure, as in [START_REF] Emiris | Minkowski decomposition of convex lattice polygons[END_REF][START_REF] Gao | Decomposition of polytopes and polynomials[END_REF].

Proof. We observe that

s(Q ′ ) = s(A ′ ) ∪ s(B ′ ) = s a ∪ s b ∪ {v} ∪ {-v} =⇒ s(Q ′ ) = s(Q) ∪ {v} ∪ {-v}.
This equals adding to Q a single segment s of length |s| = |v| and Q ′ = Q + s. The length of vector v we add to close the gap, is the key factor to bound polygon Q ′ . From the guarantees of the 2D-SS-opt solution, we know that s a (respectively, s b ) sum up to a vector with length at most ϵ max{L n }. This is vector v and thus |v| ⩽ ϵ max{L n }. Since max{L n } ⩽ D, we get |s| = |v| ⩽ ϵD.

It follows that:

1. per(Q) = ∑ v∈s(Q) |v|, it follows per(Q ′ ) = per(Q) + 2|v| ⩽ per(Q) + 2ϵD. 2. vol(Q ′ ) ⩽ vol(Q) + sD ⩽ vol(Q) + ϵD 2 .
3. By Pick's theorem, vol(Q

) = i(Q) + b(Q)/2 -1 =⇒ i(Q) = vol(Q) -b(Q)/2 + 1. Note that b(Q) = ∑ ∀v∈s(Q) d v
, where v = (x, y) ∈ s(Q) and d v = gcd(x, y), as is Definition 8.4.1. Now, i(Q ′ ) = i(Q) + i(sD), since sD is the maximum volume added, and i(sD) ⩽ sD -b(sD)/2 + 1 ⩽ sD -1 ⩽ ϵD 2 . Thus, i(Q ′ ) ⩽ i(Q) + ϵD

Implementation and experimental results

This section discusses the implementation of Algorithm 6 and Algorithm 7, both developed in Python3. The code can be accessed on Github1 and is roughly 750 lines long.

To test Algorithm 6 we created vectors v i at random with |v i | ⩽ 5000. For Algorithm 7 we create random points and take their convex hull to form input polygon Q. All tests were executed on an Intel Core i5-2320 @ 3.00 GHz with 8Gb RAM, 64-bit Ubuntu GNU/Linux. We measure volume, perimeter and Hausdorff distance and present their mean values.

Results for Algorithm 6 are shown in Figure 8.5 and for Algorithm 7 in Table 8.1. It is clear in Figure 8.5 that our results stay below the expected time and behave analogously. In Table 8.1 the results obtained are much better than the proven bounds and in most cases volume and perimeter are almost the same and the polygons differ slightly.

EXTENSIONS AND OPEN PROBLEMS

Several intriguing open questions emerge by the study of this thesis.

From the computational algebra and combinatorics point of view one direction is to generalize the result of Chapter 5 to multi-symmetric polynomials or other types of symmetry. The case of non-homogeneous polynomials can also be studied. The other direction is the generalization of our formulas in Chapter 6 to any number of variables. This will allow us to extend our applications and to develop effective computational techniques for sparse discriminants based on well tuned software for the computation of resultants.

From the Computational Geometry, Optimization and Algebraic Algorithms point of view there are some related problem to Chapters 7 and 8. The first one is given A ∈ Z m×d and b ∈ Z m , such that Ax ⩽ b is the H-representation of a convex (integral) polytope P b , define and compute approximate (integral) summands. The second one would be to employ these methods in algebraic problems like approximate polynomial factoring or irreducibility testing. Given a polynomial f Q defined on its Newton polygon Q, we use MimkDecomp to find an approximation decomposition Q ′ = A ′ + B ′ . Using the irreducibility test in [START_REF] Salem | Factoring polynomials via polytopes[END_REF], we either find a bivariate factorization or that f Q ′ is irreducible. In the latter case, we use approximate polynomial factorization [START_REF] Kaltofen | Approximate factorization of multivariate polynomials using singular value decomposition[END_REF]. All monomials of f Q lie in the support of f Q ′ , therefore the corresponding coefficients are constrained by those of f Q . So, we need to determine whether there exist valid coefficients for the monomials that correspond to lattice points in Q ′ \ Q.

8. 2

 2 For every t the returned vector t ′ is in distance at most ϵM n + OP T , where OP T is the optimum distance. . . . . . . . . . . . . . . . . . . . . . . . . . 8.3 Two examples for two polygons Q. Their summands are shown and the red vector v is the new vector added to fill the gap. At the end, the new polygon Q ′ is Minkowski Sum of the two summands. . . . . . . . . . . . . . . . . . . 8.4 A worst case example where the vector v is (almost) perpendicular to the diameter D maximizing the extra volume added. Moreover, D and v have no lattice points thus the interior points added are also maximum (D is not vertical). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 8.5 Experimental results for 2D-SS-opt : a) ϵ = 0.2, b) ϵ = 0.30, c) n = 30, and d) n = 40. The blue line represents the expected time, the red dots correspond to our experiments. . . . . . . . . . . . . . . . . . . . . . . . . 122 PREFACE This dissertation is submitted for the degree of Doctor of Philosophy at the Department of Informatics and Telecommunications of National and Kapodistrian University of Athens.

2 .

 2 The dimension of the subspace L parallel to an affine set M is called the dimension of M . A point a ∈ R n is an affine set of dimension 0, because the subspace parallel to M = {a} is L = {0}. A line through two points a, b is an affine set of dimension 1, because the subspace parallel to it is the one-dimensional subspace {x = λ(ba)|λ ∈ R}. An (n -1)-dimensional affine set is called a hyperplane or a plane for short.

Definition 2 . 1 . 11 .Example 2 . 1 . 12 .

 21112112 A lattice polytope is a set of the form Conv(A), where A ⊂ Z d is finite. That is the convex hull of a set of points with integer coordinates. If the set of exponent vectors of all monomials of total degree at most b is A b = {m ∈ Z d ⩾0 : |m| ⩽ b}, then the convex hull of A b is a polytope (and it is also a simplex)

Definition 2 . 1 . 15 .

 2115 If a p (v) = -min m∈P (< m, v >), then we call the equation < m, v >= -a P (v) a supporting hyperplane of P and we call v an inner pointing normal.

Theorem 2 . 3 . 1 .

 231 Multinomial theorem

Figure 4 . 1 :

 41 Figure 4.1: Left: Voronoi circle for 3 ellipses. Right: An example of a Voronoi diagram for non-intersecting ellipses, and the corresponding Delaunay graph. Both figures reproduced from[START_REF] Emiris | Exact delaunay graph of smooth convex pseudo-circles: General predicates, and implementation for ellipses[END_REF]

Figure 4 .

 4 2 features sample points of ∆(a, b) = 0 inside a small box around the origin, which is the point lying in the intersection of the two coordinate arrows.

Figure 4 . 3 :

 43 Figure 4.3: The Newton polygonsQ ′ 1 = conv(A ′ 1 ), Q ′′ 1 = conv(A ′′ 1 ), Q 2 = conv(A 2 ), andQ 1 = conv(A 1 )

  Figure 4.4, and Figure 4.5.

Figure 4 . 4 :

 44 Figure 4.4: The Newton polygonsQ ′ 1 = conv(A ′ 1 ), Q ′′ 1 = conv(A ′′ 1 ), and Q 1 = conv(A 1 )

  An equals the A-discriminant of the associated Cayley matrix whenever ∆ A ̸ = 1. Let us give an example of the relation between A-discriminant and mixed discriminant.

Example 4 . 4 . 4 .

 444 Consider two planar configurations A 1 = {(6, 0), (0, 3), (0, 1)}, and A 2 = {(0, 6), (3, 0), (1, 0)}. These supports correspond to the following family of polynomials: h 1 (x, y) =c 11 x 6 + c 12 y 3 + c 13 y, h 2 (x, y) =c 21 y 6 + c 22 x 3 + c 23 x.

  Figure 4.6: The discriminant polytope

  so for any integer i ∈ [l(λ)] we can define without ambiguity the homogeneous polynomial of degree d F {i} λ (y 1 , y 2 , . . . , y l(λ) ) := ρ λ ( F {j} (x 1 , . . . , x n ) )

8 )

 8 is a basis (over Z) of the homogeneous symmetric polynomials of degree d in n variables. In other words, any homogeneous symmetric polynomial of degree d with coefficients in a commutative ring is obtained as specialization of the generic homogeneous symmetric polynomial of degree d F (x 1 , . . . , x n ) := ∑ λ⊢d c λ e λ (x) ∈ Z[c λ : λ ⊢ d][x 1 , . . . , x n ].

Lemma 5 . 4 . 2 .

 542 [λ] := [(I 1 , . . . , I k )] = [(L 1 , . . . , L k )]. Let λ be a partition of n, then the cardinality of the equivalence class [λ] is m λ .

Proposition 5 . 4 . 3 .

 543 Let λ be a partition of n. Then, for any admissible partition (I 1 , . . . , I k ) such that [λ] = [(I 1 , . . . , I k )], R (I 1 ,...,I k ) = ±Res (

e 2 +

 2 144ab 2 e 4 c -6ab 2 e 3 d 2 -192a 2 be 4 d -4d 2 ac 3 e 2 + 144d 2 a 2 ce 3 -4d 3 b 3 e 2 -4c 3 e 3 b 2 -80abe 3 dc 2 + 18b 3 e 3 dc + 18d 3 acbe 2 + d 2 c 2 b 2 e 2 -27b 4 e 4 -128a 2 e 4 c 2 + 16ac 4 e 3 -27 a 2 d 4 e 2 + 256a 3 e 5 + 3125a 4 g 4 + 160a 2 gbe 3 c + 560a 2 gdc 2 e 2 + 1020 a 2 gbd 2 e 2 + 160ag 2 b 3 ed

Problem 5 .

 5 is a polytope. The set of all non-empty polytopes P b arising this way can be parameterized by their right-hand side vectors b. Let us denote the set of such right hand side vectors b by U (A) = {b ∈ R m | P b ̸ = ∅} . (7.1) In this work, we present an algorithm solving the following problem: Minkowski Summands. Given A ∈ Z m×d and b ∈ R m , such that Ax ⩽ b is the H-representation of a convex integral polytope P b , compute all integral MinkDecomp of P b .

Lemma 7 . 2 . 1 (

 721 Farkas 1894). The system of inequalities Ax ⩽ b is feasible if and only if y ⊤ b ⩾ 0 for each y ⩾ 0 with A ⊤ y = 0.The dual, U* (A) = {y ∈ R m : y ⊤ b ⩾ 0 ∀b ∈ U (A)}, in view of Lemma 7.2.1 becomes U * (A) = {y ∈ R m : A ⊤ y = 0 and y ⩾ 0}. (7.2)It is immediate from Equation (7.2) that U * (A) is the intersection of ker(A ⊤ ) with the positive orthant R m + of R m . Therefore, U * (A) is a cone and its primal set U (A) is a cone as well and both contain the origin. Throughout we will use the following example.Example Consider the matrix A ∈ Z 10×3 and the vector b ∈ Z 10

Figure 7 . 1 :

 71 Figure 7.1: The polytope defined by System (7.3) and its 2 Minkowski summands.



  , and by mapping the bi 's back to the corresponding b i 's of the input system (note that b = (b 0 , . . . , b 9 , -b 1 )) we obtain the following two constraints: b 2 + b 8 ⩾ 0 and b 1 + b 4 + b 8 ⩾ 0.

Proposition 7 . 2 . 5 .

 725 η b of P b . The irredundant description of a full dimensional polytope P b is unique and each of its inequalities supports P b along a facet. Thus, if Ax ⩽ b is an irredundant description of a d-polytope with m facets then A ∈ Z m×d . Below we show that, if the input is an irredundant description of P b , then it is only the rays of U (A) b that account for the (in)decomposability of P b . Assume P b = {x : Ax ⩽ b}, A ∈ R m×d is a d-polytope with m facets. Then, the generating rays b 1 , . . . , b k of U (A) b correspond to nontrivial indecomposable polytopes, while the generating lines ±c 1 , . . . , ±c d of U (A) b correspond to points. Combining Proposition 7.2.5 and Theorem 7.2.4, we deduce that each MinkDecomp of P b into non-trivial indecomposable polytopes is a sum:

Figure 8 . 1 :

 81 Figure 8.1: a) A single cell for the dashed vector v. All vectors in the cell will be deleted. The distances are shown and the furthest point is in distance αδ|v|. b) After the trim a few cells remain. Every vector in the cells will be deleted and "represented" by one of the black vectors shown. Notice that the size of each cell depends on the vector that creates it: the shorter the vector the smaller the cell.

  ∃w ∈ L i : u = w + r w , |r w | ⩽ αδ|w| (8.3) hence, |w| ⩽ |u| ⩽ (1 + δ)|w|. See Figure 8.1.

Lemma 8 . 3 . 1 .

 831 Using the above notation, call functionL i =trim(E i , δ), with parameter δ = ϵ/2n and let M i = max{|u| : u ∈ E i }, the vector in E i with the largest length. It holds that |L i | = O(n 3 ϵ -2 ) for 1 ⩽ i ⩽ n.

Lemma 8 . 3 . 3 .

 833 For a multiset S = {v i | 0 ⩽ i ⩽ n} where v i ∈ Z 2 , every possible vector sum v ∈ P n can be approximated by a vector w such that∀v ∈ P n , ∃w ∈ L n , ∃r w ∈ Z 2 : v = w + r w , |r w | ⩽ nδM n ,Proof. The proof is by induction. The base step, it is easy to see that if we only have one element the theorem holds. The induction hypothesis∀v ∈ P n-1 , ∃w ∈ L n-1 , ∃r w : v = w + r w , |r w | ⩽ (n -1)δM n-1 . Now suppose v ∈ P n \ P n-1 because, if v ∈ P n-1, the theorem holds straight from the induction hypothesis. We write v as v = z + v n , z ∈ P n-1 , and the induction hypothesis holds for z, thus ∃p ∈ L n-1 , ∃r p : z = p + r p , |r p | ⩽ (n -1)δM n-1 .

  [-M n , M n ] × [-M n , M n ],where each square cell has edge of length d = ϵM n /2n.For each v(x, y) ∈ E i , the trimmed list L i stores the vector with its coordinates rounded to an integer multiple of d:∀v(x, y) ∈ E i ∃w(x ′ , y ′ ) ∈ L i : x ′ =value reaches when v and w are in the diagonal of the cell. The whole grid has size 2M n and since d = ϵM n /2n the grid has O((M n /d) 2 ) = O((n/ϵ) 2 )

Figure 8 . 2 . 8 . 3 . 4 .

 82834 TheoremThe grid-based algorithm runs in time O(n 3 ϵ -2 ), requires space O(n 2 ϵ -2

Figure 8 . 2 :

 82 Figure 8.2: For every t the returned vector t ′ is in distance at most ϵM n + OP T , where OP T is the optimum distance.

  (1 + δ) k ⩽ |v| ⩽ (1 + δ) k+1 and r ′ = bin_search(A, |v|) = (1 + δ) k . The plane is divided in O(δ) = O(n/ϵ) angles and O(n log M n /ϵ) different lengths. Each E i has size O(n 2 ϵ -2 log M n ).We have saved a quadratic factor, but incurred log |E i | for binary search. The whole algorithm runs inO(n|E i | log |E i |) = O(n 3 ϵ -2 log M n log n 2 log M n ϵ 2 )

Algorithm 7 :Definition 8 . 4 . 1 .

 7841 approx-MinkDecomp input : polygon Q, 0 ≤ ϵ ≤ 1 output: polygon Q' S = primitive_edge_sequence(Q) //get the edge sequence for the two summands s(A) = approx-2D-SS (S,(0,0)) s(B) = S\A A=get-points(s(A)) B=get-points(s(B)) return Q'= A + B Let v = (a, b) ∈ Z 2 be a vector and d = gcd(a, b) ∈ N. The primitive vector of v is e = (a/d, b/d).

  0, . . . , ⌊log 2 d/2⌋ and d ⌊log 2 d/2⌋+1 = d -⌊log 2 d/2⌋ ∑ i=0 d i . Thus, ∑ ⌊log 2 d/2⌋+1 i=0 d i = d. We include in S the vectors d i e and repeat the procedure for all vectors v ∈ s(Q), S = {(x/d, y/d)2 i | i = 0, . . . , ⌊log 2 d/2⌋, ⌊log 2 d/2⌋ + 1, d = gcd(x, y) : (x, y) ∈ s(Q)}.

2

 2

4 .Theorem 8 . 4 . 3 .

 4843 If we translate Q by s/2 units in the direction of v, then d H (Q, Q ′ ) = s/2 =⇒ d H (Q, Q ′ ) ⩽ ϵD/2.Therefore Theorem 8.4.2 solves Problem 7. A hard case is illustrated in Figure8.4, where the added vector is (almost) perpendicular to D maximizing the extra volume and number of interior lattice points. Theorem 8.4.2 leads to the following conclusion: The proposed algorithm provides a 2ϵD-solution for MinkDecomp-perapprox, an ϵD 2 -solution for MinkDecomp-vol-approx and MinkDecomp-latt_p-approx, and an ϵ/2D-solution for MinkDecomp-d H -approx.

Figure 8 . 4 :

 84 Figure 8.4: A worst case example where the vector v is (almost) perpendicular to the diameter D maximizing the extra volume added. Moreover, D and v have no lattice points thus the interior points added are also maximum (D is not vertical). #vertices #examples vol(Q)/vol(Q') per(Q)-per(Q') Hausdorff ϵ

Figure 8 . 5 :

 85 Figure 8.5: Experimental results for 2D-SS-opt : a) ϵ = 0.2, b) ϵ = 0.30, c) n = 30, and d) n = 40. The blue line represents the expected time, the red dots correspond to our experiments.

  The research questions were formulated by my supervisor, Prof. Ioannis Z. Emiris, who supported and inspired me in all stages during my PhD. The research was sophisticated, but conducting extensive investigation has allowed me to answer all the questions that we identified. I would like to thank him again for being my supervisor, for the trust he has shown to me from the very first day of our collaboration, helping me to pursue research on topics for which I am truly passionate and achieve those high impact results. His office door was always open and his email available anytime, even late at night or during holidays. also benefitted from my friends who kept me motivated. Many thanks to Theodosia Antonellou, Spyros Argiroiliopoulos, Kostas Athanasiou, Aimilia Basilaki, Xrisanthi Chimona, Mr. Charalampos and Ms. Mairy Christoforatos, Manousos Damorakis, Nikos Grivokostopoulos, Thalia Ioannou, Ifigeneia Makariti, Zacharias Mpikos, Baggelis Ntaloukas, Charilaos Vougioukas and their families for their continues support and love.I would like to express my gratitude and appreciation to my big family Karasoulos, Boutidis, Kapogiannis, Xiarchopoulos, Lentzos, Bouloukos, Kalabesios, Ronald and Sara Wildford, Antoni and Basiliki Kourtikaki, Ourania Kalpaxi, Irini and Nikianna Kapogianni, Anastasios and Nikolaos Giannakopoulos, Theodoros Kapogiannis, Christina Kapogianni, Dimitrios and Eleni Karasoulos, Nikolaos and Anna Kapogianni, Panagiota and Sotiria Zoumpou, Christina Lentzou, Nikolaos and Anastasia Lentzos for being by my side and for their love.

	Anna Karasoulou
	Athens, May 31, 2017
	Emiris, Prof. Aggelos Kiayias and Prof. Evangelos Raptis for their trust and tutoring me
	as assistant.
	I would like to thank Antigoni Galanaki and Tatiana Kyrou for helping me with the paper-
	work.

Fortunately, both Prof. Evangelos Raptis and Dr. Bernard Mourrain were always helping me, supporting me and encouraging me to continue to the next big step. Thank you for all of the meetings and chats over the years. I would also like to thank Dr. Bernard Mourrain for the funding of my two internships at INRIA Sophia Antipolis -Méditerranée. Many thanks to my tutors Prof. Ilias S. Kotsireas, for his enthusiasm, encouragement and advices and also Prof. Vassilis Zissimopoulos, Prof. Nikolaos Missirlis, and Prof. Michael N. Vrahatis for always being available and willing to answer my queries and guiding me through the project.

I would like to thank my co-authors and tutors Dr. Laurent Busé, Prof. Alicia Dickenstein, Prof. Ioannis Z. Emiris, Dr. Evelyne Hubert, Prof. Gregory Karagiorgos and Prof. Günter Rote, whom I consider myself fortunate to meet, and whose pieces of advise have been priceless.

I would like to thank my co-authors and friends Dr. Eleni Tzanaki, Charilaos Tzovas, Dr. Zafeirakis Zafeirakopoulos for productive collaboration. I would like to warmly thank my colleagues from the ΕρΓΑ laboratory, Galaad and Aromath team for their enthusiasm, collaboration, encouragement It was always helpful to share ideas and knowledge about my research. Specially thanks to Evangelos Anagnostopoulos, Dr. Vissarion Fisikopoulos, Dr. Christos Konaxis, Ioannis Psarros and Dr. Elias Tsigaridas for their advices. I would like to thank Prof. Dimitris Achlioptas, Dr. Ioannis Chamodrakas, Prof. Ioannis Z.

My sincere gratitude to Prof. Evangelos Raptis, Prof. Korina Rozi and Prof. Dimitrios Varsos for their continuous support and for being my tutors from my early stages until now.

I

My parents Nikolaos and Theophanie Karasoulou and my brother Dimitrios Karasoulos deserve a particular note of thanks: your wise advise and kind words have, as always, served me well. Thank you for your infinite support and love. Without you I wouldn't finish even the first classes of school, of piano Academy, of ballet Academy, of tennis Academy, of .... and most of all of becoming the person that I am today.

My love to my son Nikolaos Lentzos. Thank you for your infinite love and for making my life beautiful. Special thanks to my close family for looking after you while I was doing my research and writing this thesis and for providing funding for the early and the last years of my studies.

Finally, I seize this opportunity to express my love to my husband Konstantinos Lentzos and say a very very big thank you for bearing me in my worst, loving me, encouraging me and supporting me. I hope you enjoy your reading.

k in decreasing size order. Example 2.3.2. The partition

	1, 1) ⊢ 4 and has length l(2, 1, 1) = 3.
	Applying partitions on the variables x 1 , . . . , x n For any partition λ = (λ 1 , . . . , λ k ) ⊢ n, where
	k = l(λ),
	we construct k blocks of size λ 1 , . . . , λ (5, 3, 2, 2, 1) ⊢ 13 gives
	We fill in those blocks with the variables x 1 , . . . , x n . The λ i variables in the block i are
	identified by y i and this gives us a ring homomorphism
	ρ λ : A[x 1 , . . . , x n ] → A[y 1 , . . . , y k ]

Symmetric polynomials Definition 2.4.5. Let

  1 , . . . , X n ), . . . , s n (X 1 , . . . , X n ). X 1 , . . . , X n be indeterminates over Z, where n is a positive integer. The monic polynomial g ∈ Z[X 1 , . . . , X n ][X] having roots X 1 , . . . , X n expands as

	Remark 2.4.4. The ring of symmetric polynomials with coefficients in a field K of charac-
	teristic zero is equal to the polynomial ring K[s 1 , . . . , s n ].

  a classic function in geometry, taking values in N and generalizing the notion of volume, in the sense that mixed volume equals n

  d 1 σ,...,dnσ,δσ (f 1 , . . . , f n , Ji ) = ∆ d 1 σ,...,dnσ (f 1 , . . . , f n ) • Res (d 1 σ) e i ,...,(dnσ) e i (f e i 1 , . . . , f e i n ),where e 0 , . . . , e n are the canonical basis vectors (or e 0 = -e 1 -• • • -e n , if we consider the corresponding dehomogenized polynomials, by setting x 0 = 1). Note that Theorem 6.3.4 gives the following more symmetric formula:

	Corollary 6.3.5. With the previous notation, it holds:

  is not feasible then P c is a non-trivial polytope or P c is a point whose description Ax ⩽ c contains a non-active inequality (c ̸ = η c ).Proof. Since Ax ⩽ c is a polytope, feasibility of Ax ⩽ -c implies the existence of a point beyond all faces of P c . This cannot happen unless P c is a point. Arguing as above, we see that point 2 is true when P c is nontrivial. If, however, P c is a point, the feasibility of both Ax ⩽ ±c fails only if the description Ax ⩽ c contains a hyperplane that does not support P Thus, P b i is a non-trivial indecomposable summand of P b . If, on the other hand, a polytope P c i corresponds to an extreme line of U (A) b , then both Ax ⩽ c i and Ax ⩽ -c i are feasible. In this case, Lemma 7.2.6.1 implies that P c i is a point. Let P b = {x : Ax ⩽ b}, A ∈ Z m×d be a d-polytope with m facets. Then, P b is indecomposable if and only if cone U (A) b has a single generating ray.

	If we only want to decide whether P b is indecomposable, Proposition 7.2.5 is simplified as
	follows.
	Corollary 7.2.7.

c .

Proof of Proposition 7.2.5. If a polytope P b i corresponds to an extreme ray of U (A) b , then Ax ⩽ b i is feasible whereas Ax ⩽ -b i is not. Since, by definition, the cone U (A) b contains polytopes all whose inequalities are active, Lemma 7.2.6.2 rules out the case where dim(P b i ) = 0.

  Function µ(•) is specialized as follows: Euclidean volume vol(•), polygon perimeter per(•), number of interior lattice points i(•) or, by abuse of notation, we may consider the Hausdorff distance d H between Q and A + B denoted by d H

  Proof. Let ϕ be a given formula as an instance of SAT. Use Proposition 8.2.1 to get an instance of Set Cover and then the reduction from Theorem 8.2.2 to get an instance of kD-SS-opt. Suppose there exists an algorithm A for kD-SS-opt that is in APX. A returns a vector t ′ such that ∥t-t ′ ∥ 1 ⩽ (1+ϵ)OP T , where OP T = ∥t-t * ∥ 1 and t * is the closest vector in P n . From Theorem 8.2.2, if ϕ is satisfiable then OP T ⩽ K, and if ϕ is not satisfiable, then OP T > cK.

Theorem 8.2.3. kD-SS-opt is not in APX unless P=NP.

return E Algorithm 6: annulus

  Function trim uses time |E i | to consider all vectors and, in the worst case, we have to check each vector in E i against all others, thus leading to timeO(|E i | 2 ) = O(|L i | 2 ). Algorithm 6 takes time n • T (trim) = O(n|L n | 2 ) and overall, from Theorem 8.3.1, requires time O(n 5 ϵ -4 log 2 M n ).The algorithm stores at each step list L i , so space consumption isO(n 2 ϵ -2 log M n ). For δ = ϵ/2n, the running time of Algorithm 6 is in O(n 5 ϵ -4 log 2 M n ), and the space required is in O(n 2 ϵ -2 log M n ). -slice input : S ⊂ Z 2 , 0 ⩽ ϵ ⩽ 1 output: all approximation points L n ⊂ Z 2

	Theorem 8.3.2.

Algorithm 5: trim

input : E ⊂ Z 2 , 0 ⩽ δ ⩽ 1 output: a trimmed list L ⊂ Z 2 sort(E) for v k ∈ E do i = 1 while |v k+i | ⩽ (1 + δ)|v k | do if θ(v k+i ) -δ ⩽ θ(v k ) ⩽ θ(v k+i ) + δ then remove v k+i from E i = i + 1

Table 8 .

 8

	time(sec)

1: Results for MinkDecomp-µ-approx: input polygon Q, output Q ′ (per(Q) > 1000).

A. Karasoulou

https://github.com/tzovas/Approximation-Subset-Sum-and-Minkowski-Decomposition

A. Karasoulou

ACKNOWLEDGEMENTS

This dissertation could not have been completed without the great support that I have received from so many people over the years. I wish to offer my most heartfelt thanks. Without their cooperation I would not have been able to conduct this analysis. My sincere gratitude to my supervisor Prof. Ioannis Z. Emiris for teaching me all the aspects of research and generously offering me his advice.

Remark 6.2.3. Assume A 1 consists of a single point α and that {1} is the only essential subfamily of a given family A 1 , . . . , A n+1 . Let f 1 (x) = cx α . Then, for any choice of Laurent polynomials f 2 , . . . , f n+1 with supports A 2 , . . . , A n+1 , it holds that (cf. [

23, Proposition 2.2])

Res A 1 ,...,A n+1 (f 1 , . . . , f n ) = c M V (A 2 ,...,A n+1 ) . (6.3) With this convention, the following multiplicativity formula holds: Theorem 6.2.4. [START_REF] Sombra | A poisson formula for the sparse resultant[END_REF][START_REF] Pedersen | Product formulas for resultants and chow forms[END_REF] Let A ′ 1 , A ′′ 1 , A 1 , . . . , A n+1 be finite subsets of Z n with A 1 = A ′ 1 + A ′′ 1 . Let f 1 , . . . , f n+1 be polynomials with supports contained in A 1 , . . . , A n+1 and assume that

Cattani, Cueto, Dickenstein, Di Rocco and Sturmfels in [START_REF] Cattani | Mixed discriminants[END_REF] proved that the degree of the mixed discriminant ∆ is a piecewise linear function in the Plücker coordinates of a mixed Grassmanian. An explicit degree formula for plane curves is also presented in [START_REF] Cattani | Mixed discriminants[END_REF]Corollary 3.15]. In case A 1 , A 2 consist of all the lattice points in their convex hulls, they are two dimensional and with the same normal fan, then the bidegree of ∆ A 1 ,A 2 satisfies the following: bidegree of ∆ A 1 ,A 2 in the coefficients of f i equals:

The area is normalized, so that a primitive triangle has area 1 and the perimeter of Q i is the cardinality of ∂Q i ∩ Z 2 . We will recover the general formula for this degree and present it in Corollary 6.3.6.

Busé and Jouanolou consider in [START_REF] Busé | A computational approach to the discriminant of homogeneous polynomials[END_REF] the following equivalent definition of the mixed discriminant, in case where f 1 , . . . , f n are dense homogeneous polynomials in (x 0 , . . . , x n ) of degrees d 1 , . . . , d n respectively, that is, their respective supports A i = d i σ are all the lattice points in the d i -th dilate of the unit simplex σ in R n . It is the non-zero polynomial in the coefficients of f 1 , . . . , f n which equals

for all i ∈ {1, . . . , n}, where J i is the maximal minor of the Jacobian matrix associated to f 1 , . . . , f n obtained by deleting the i-th. We give a more symmetric and general formula in Corollary 6.3.5 below.

The multiplicativity property of the discriminant in the case of dense homogeneous polynomials was already known to Sylvester [START_REF] Sylvester | Sur l'extension de la théorie des résultants algébriques[END_REF] and generalized by Busé and Jouanolou in [START_REF] Busé | A computational approach to the discriminant of homogeneous polynomials[END_REF], where they proved that when in particular

, the following factorization holds:

from which we get that the bidegree of the resultant Res

Substracting the degree of the other factors and taking into account that the bidegree of the resultant Res A η

)), we deduce the formula (6.13), as desired.

The multiplicativity of the mixed discriminant

This section studies the factorization of the discriminant when one of the polynomials factors. We make the hypothesis that f ′ 1 , f ′′ 1 , f 2 have fixed support sets, and

in fact, its support is generically equal to A 1 . We will denote by µ ′ (η) (resp. µ ′′ (η)) the integer defined in (6.7), with A 1 replaced by

generic polynomials with these supports and let

where E equals the following product:

Proof. By Theorem 6.3.3, we get that

and similarly for

Let us write the numerator of (6.16) as follows:

Let us apply Theorem 6.2.4 to re-write it as follows:

, because the resultant of {h 1 , h 2 + gh 1 , . . . } equals the resultant of {h 1 , h 2 , . . . }, for any choice of polynomials h 1 , h 2 , g (with suitable supports). We employ again Theorem 6.2.4 to finalize the numerator as follows:

Algebraic combinatorics and resultant methods for polynomial system solving

The second and final step is to find a generating set of integer translations. Rather than repeating the above procedure for the trivial polytopes P c i in Equation ( 7 Proof. Since the rows of A positively span R d , the system Ax ⩽ 0 has a unique solution. Thus, the same holds for Ax ⩽ Ae i , with unique solution e i .

We therefore use the vectors c1 , . . . , cd ∈ U (A) b as generators of the integer translations in R d .

Summarizing, we have the following algorithm:

Ensure the origin is a vertex of P r i Compute the vertices (

The above algorithm returns a finite set b 1 , . . . , b k ∈ R m which, together with c1 , . . . , cd , produces all MinkDecomp of the input polytope P b . Thus, each way to write b = ∑ i λ i b i +

APPROXIMATING MULTIDIMENSIONAL SUBSET SUM AND THE MINKOWSKI DECOMPOSITION OF POLYGONS

We consider the approximation of two NP-hard problems: Minkowski Decomposition (MinkDecomp) of lattice polygons in the plane and the closely related problem of Multidimensional Subset Sum (kD-SS) in arbitrary dimension. In kD-SS, a multiset S of k-dimensional vectors is given, along with a target vector t, and one must decide whether there exists a subset of S that sums up to t. We prove, through a gap-preserving reduction from Set Cover that, for general dimension k, the corresponding optimization problem kD-SS-opt is not in APX, although the classic 1D-SS-opt has a PTAS. Our approach relates kD-SS with the well studied Closest Vector Problem. On the positive side, we present a O(n 3 /ϵ 2 ) approximation algorithm for 2D-SS-opt, where n is the cardinality of the multiset and ϵ > 0 bounds the additive error in terms of some property of the input. We state two variations of this algorithm, which are more suitable for implementation. Employing a reduction of the optimization version of MinkDecomp to 2D-SS-opt we approximate the former: For an input polygon Q and parameter ϵ > 0, we compute summand polygons A and B, where

We conclude with experimental results based on our implementations.

Introduction

This paper considers the fundamental combinatorial problem of Subset Sum, in the context of two and higher dimensions. We relate this problem to the decomposition of convex polygons and polytopes to Minkowski summands. This is motivated by a key concept in the study of multivariate polynomial systems, namely the Newton polytope of a polynomial.

Every polynomial is related to its Newton polytope, and a theorem by Ostrowski [START_REF] Ostrowski | On multiplication and factorization of polynomials, II. irreducibility discussion[END_REF] states that, if the Newton polytope of a polynomial does not have a Minkowski decomposition, then the polynomial is irreducible. Based on that, Gao [START_REF] Gao | Absolute irreducibility of polynomials via newton polytopes[END_REF] devised an irreducibility test for a polynomial, by checking whether its Newton polytope is decomposable. In this paper, we consider the problem of decomposition of integral polygons in the plane, by reducing this problem to a two-dimensional version of the Subset Sum. An approximate solution to the latter also provides a solution to the first. The Subset Sum problem is well studied from a theoretical perspective, but also for applications, e.g. in cryptosystems. The approximation approach on Subset Sum is mostly interested in the theoretical aspects of the problem or at least we are unaware of any practical use. The 2D-Subset Sum (generally, kD-Subset Sum) problem is defined below, and our motivation comes mainly from (approximate) factoring and irreducibility testing.

Let us start with some definitions. A polygon Q is called an (integral) lattice polygon, when all its vertices are points with integer coordinates. The weakness in this approach is that the algorithm returns a sequence of vectors that sums up to a vector close to (0, 0) but possibly not (0, 0). Hence the corresponding edge sequence does not form a closed polygon. To overcome this, we include in s a the vector v, defined so that when added to the last point it yields the first one. If the vectors in s a sum up to point (x, y), by including vector v = (-x, -y) the edge sequence s a ∪ {v} sums up to (0, 0). If we order the vectors by their angles, they form a closed, convex polygon denoted by A ′ . We do the same for the sequence s b . The vector used is -v = (x, y) and this sequence (ordered) also forms a closed, convex polygon, denoted by B ′ . Let s(A ′ ) = s a ∪ {v}, s(B ′ ) = s b ∪ {v} be the edge sequences, and consider Minkowski Sum Q ′ = A ′ + B ′ . We now measure the difference between Q ′ and Q. Let D denote the diameter of Q, which is the maximum distance between two vertices of Q.