Gcd of multivariate polynomials via Newton polytopes

We study geometric criteria to determine coprimality between multivariate polynomials. Our main contribution is the development of a polynomial-time algorithm (on the number of monomials) that detects coprimality of multivariate polynomials using Newton polytopes. We also show how to construct the gcd of two bivariate polynomials using their Newton polygons.     

Bounds on the coefficients of tension and flow polynomials

The goal of this article is to obtain bounds on the coefficients of modular and integral flow and tension polynomials of graphs. To this end we use the fact that these polynomials can be realized as Ehrhart polynomials of inside-out polytopes. Inside-out polytopes come with an associated relative polytopal complex and, for a wide class of inside-out polytopes, we show that this complex has a convex ear decomposition. This leads to the desired bounds on the coefficients of these polynomials.     

多元整系数多项式因式分解的一种理论和算法

本文将ｔ（ｔ是大于２的整数）元整系数多项式看成为系数为ｔ－２元整系数多项式的二元多项式，建立了多元整系数多项式因式分解的一种新理论，进而得到了分解多元整系数多项式的一个有力的算法。     

Minkowski Length of 3D Lattice Polytopes

We study the Minkowski length L(P) of a lattice polytope P, which is defined to be the largest number of non-trivial primitive segments whose Minkowski sum lies in P. The Minkowski length represents the largest possible number of factors in a factorization of polynomials with exponent vectors in P, and shows up in lower bounds for the minimum distance of toric codes. In this paper we give a polytime algorithm for computing L(P) where P is a 3D lattice polytope. We next study 3D lattice polytopes of Minkowski length 1. In particular, we show that if Q, a subpolytope of P, is the Minkowski sum of L=L(P) lattice polytopes Q _i , each of Minkowski length 1, then the total number of interior lattice points of the polytopes Q ₁,??,Q _L is at most 4. Both results extend previously known results for lattice polygons. Our methods differ substantially from those used in the two-dimensional case.     

On factorization of polynomials in henselian valued fields

Guàrdia, Montes and Nart generalized the well-known method of Ore to find complete factorization of polynomials with coe?cients in finite extensions of p-adic numbers using Newton polygons of higher order (cf. [Trans. Amer. Math. Soc. 364 (2012), 361–416]). In this paper, we develop the theory of higher order Newton polygons for polynomials with coe?cients in henselian valued fields of arbitrary rank and use it to obtain factorization of such polynomials. Our approach is different from the one followed by Guàrdia et al. Some preliminary results needed for proving the main results are also obtained which are of independent interest.     

Ehrhart Polynomials of Matroid Polytopes and Polymatroids

We investigate properties of Ehrhart polynomials for matroid polytopes, independence matroid polytopes, and polymatroids. In the first half of the paper we prove that, for fixed rank, Ehrhart polynomials of matroid polytopes and polymatroids are computable in polynomial time. The proof relies on the geometry of these polytopes as well as a new refined analysis of the evaluation of Todd polynomials. In the second half we discuss two conjectures about the h ^*-vector and the coefficients of Ehrhart polynomials of matroid polytopes; we provide theoretical and computational evidence for their validity.     

Multiplication of a Schubert polynomial by a Schur polynomial

Schur polynomials are a special case of Schubert polynomials. In this paper, we give an algorithm to compute the product of a Schubert polynomial with a Schur polynomial on the basis of Schubert polynomials. This is a special case of the general problem of the multiplication of two Schubert polynomials, where the corresponding algorithm is still missing. The main tools for the given algorithm is a factorization property of a special class of Schubert polynomials and the transition formula for Schubert polynomials.     

Möbius Polynomials of Face Posets of Convex Polytopes

The Möbius polynomial is an invariant of ranked posets, closely related to the Möbius function. In this paper, we study the Möbius polynomial of face posets of convex polytopes. We present formulas for computing the Möbius polynomial of the face poset of a pyramid or a prism over an existing polytope, or of the gluing of two or more polytopes in terms of the Möbius polynomials of the original polytopes. We also present general formulas for calculating Möbius polynomials of face posets of simplicial polytopes and of Eulerian posets in terms of their f-vectors and some additional constraints.     

Notes on the Roots of Ehrhart Polynomials

We determine lattice polytopes of smallest volume with a given number of interior lattice points. We show that the Ehrhart polynomials of those with one interior lattice point have largest roots with norm of order n², where n is the dimension. This improves on the previously best known bound n and complements a recent result of Braun where it is shown that the norm of a root of a Ehrhart polynomial is at most of order n². For the class of 0-symmetric lattice polytopes we present a conjecture on the smallest volume for a given number of interior lattice points and prove the conjecture for crosspolytopes. We further give a characterisation of the roots of Ehrhart polyomials in the three-dimensional case and we classify for n ≤ 4 all lattice polytopes whose roots of their Ehrhart polynomials have all real part -1/2. These polytopes belong to the class of reflexive polytopes.     

Lattice polytopes of degree 2

A theorem of Scott gives an upper bound for the normalized volume of lattice polygons with exactly i>0 interior lattice points. We will show that the same bound is true for the normalized volume of lattice polytopes of degree 2 even in higher dimensions. In particular, there is only a finite number of quadratic polynomials with fixed leading coefficient being the h^∗-polynomial of a lattice polytope.     

Hom-polytopes

We study the polytopes of affine maps between two polytopes—the hom-polytopes. The hom-polytope functor has a left adjoint—tensor product polytopes. The analogy with the category of vector spaces is limited, as we illustrate by a series of explicit examples exhibiting various extremal properties. The main challenge for hom-polytopes is to determine their vertices. A polytopal analogue of the rank-nullity theorem amounts to understanding how the vertex maps behave relative to their surjective and injective factors. This leads to interesting classes of surjective maps. In the last two sections we focus on two opposite extremal cases—when the source and target polytopes are both polygons and are either generic or regular.     

The brick polytope of a sorting network

The associahedron is a polytope whose graph is the graph of flips on triangulations of a convex polygon. Pseudotriangulations and multitriangulations generalize triangulations in two different ways, which have been unified by Pilaud & Pocchiola in their study of flip graphs on pseudoline arrangements with contacts supported by a given sorting network.In this paper, we construct the brick polytope of a sorting network, obtained as the convex hull of the brick vectors associated to each pseudoline arrangement supported by the network. We combinatorially characterize the vertices of this polytope, describe its faces, and decompose it as a Minkowski sum of matroid polytopes.Our brick polytopes include Hohlweg & Lange’s many realizations of the associahedron, which arise as brick polytopes for certain well-chosen sorting networks. We furthermore discuss the brick polytopes of sorting networks supporting pseudoline arrangements which correspond to multitriangulations of convex polygons: our polytopes only realize subgraphs of the flip graphs on multitriangulations and they cannot appear as projections of a hypothetical multiassociahedron.     

Orientations, Lattice Polytopes, and Group Arrangements I: Chromatic and Tension Polynomials of Graphs

This is the first one of a series of papers on association of orientations, lattice polytopes, and group arrangements to graphs. The purpose is to interpret the integral and modular tension polynomials of graphs at zero and negative integers. The whole exposition is put under the framework of subgroup arrangements and the application of Ehrhart polynomials. Such a viewpoint leads to the following main results of the paper: (i) the reciprocity law for integral tension polynomials; (ii) the reciprocity law for modular tension polynomials; and (iii) a new interpretation for the value of the Tutte polynomial T(G; x, y) of a graph G at (1, 0) as the number of cut-equivalence classes of acyclic orientations on G.     

Smooth Fano Polytopes Whose Ehrhart Polynomial Has a Root with Large Real Part

The symmetric edge polytopes of odd cycles (del Pezzo polytopes) are known as smooth Fano polytopes. In this paper, we show that if the length of the cycle is 127, then the Ehrhart polynomial has a root whose real part is greater than the dimension. As a result, we have a smooth Fano polytope that is a counterexample to the two conjectures on the roots of Ehrhart polynomials.     

Non-projectability of polytope skeleta

We investigate necessary conditions for the existence of projections of polytopes that preserve full k-skeleta. More precisely, given the combinatorics of a polytope and the dimension e of the target space, what are obstructions to the existence of a geometric realization of a polytope with the given combinatorial type such that a linear projection to e-space strictly preserves the k-skeleton. Building on the work of Sanyal (2009), we develop a general framework to calculate obstructions to the existence of such realizations using topological combinatorics. Our obstructions take the form of graph colorings and linear integer programs. We focus on polytopes of product type and calculate the obstructions for products of polygons, products of simplices, and wedge products of polytopes. Our results show the limitations of constructions for the deformed products of polygons of Sanyal and Ziegler (2010) and the wedge product surfaces of Rörig and Ziegler (2011) and complement their results.     

A refinement of the Bernštein-Kušnirenko estimate

A theorem of Kušnirenko and Bernštein (also known as the BKK theorem) shows that the number of isolated solutions in a torus to a system of polynomial equations is bounded above by the mixed volume of the Newton polytopes of the given polynomials, and this upper bound is generically exact. We improve on this result by introducing refined combinatorial invariants of polynomials and a generalization of the mixed volume of convex bodies: the mixed integral of concave functions. The proof is based on new techniques and results from relative toric geometry.     

Facets and volume of Gorenstein Fano polytopes

It is known that every integral convex polytope is unimodularly equivalent to a face of some Gorenstein Fano polytope. It is then reasonable to ask whether every normal polytope is unimodularly equivalent to a face of some normal Gorenstein Fano polytope. In the present paper, it is shown that, by giving new classes of normal Gorenstein Fano polytopes, each order polytope as well as each chain polytope of dimension d is unimodularly equivalent to a facet of some normal Gorenstein Fano polytopes of dimension . Furthermore, investigation on combinatorial properties, especially, Ehrhart polynomials and volume of these new polytopes will be achieved. Finally, some curious examples of Gorenstein Fano polytopes will be discovered.     

Real Factorization of Multivariate Polynomials with Integer Coefficients

In the recent papers, a new efficient probabilistic semi-numerical absolute (i.e., complex) factorization algorithm for multivariate polynomials with integer coefficients is given. It is based on a simple property of the monomials arising after a generic linear change of coordinates for bivariate polynomials and on a deep result of complex algebraic geometry. Here, we consider the a priori simpler problem of factorization over the field of reals. We briefly review our algorithm for complex factorization and adapt it to solving the problem on the field of reals. This allows us to spare a significant part of the computations and to improve the range of tractability. The method provides factors with approximative coefficients and eventually exact factors in a suitable real algebraic extension of . Bibliography: 15 titles.     

On one method of factorization of polynomials

We propose and justify a numerical method of factorization of polynomials with complex coefficients. We construct and algorithm of factorization of polynomials with real coefficients into real factors in the case of multiple roots. Kiev National Economic University, Kiev. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 9, pp. 1281–1286, September, 1999.