Polytope bounds on multivariate value sets

We improve the upper bounds for the cardinality of the value set of a multivariable polynomial map over a finite field using the polytope of the polynomial. This generalizes earlier bounds only dependent on the degree of a polynomial.     

On value sets of polynomials over a field

Let F be any field. Let p(F) be the characteristic of F if F is not of characteristic zero, and let p(F)=+∞ otherwise. Let A₁,…,A_n be finite nonempty subsets of F, and let

with k{1,2,3,…}, a₁,…,a_nF{0} and degg<k. We show that

When kn and |A_i|i for i=1,…,n, we also have

consequently, if nk then for any finite subset A of F we have

In the case n>k, we propose a further conjecture which extends the Erdős–Heilbronn conjecture in a new direction.     

Some conditional expectation identities for the multivariate normal

We give formulas for the conditional expectations of a product of multivariate Hermite polynomials with multivariate normal arguments. These results are extended to include conditional expectations of a product of linear combination of multivariate normals. A unified approach is given that covers both Hermite and modified Hermite polynomials, as well as polynomials associated with a matrix whose eigenvalues may be both positive and negative.     

On Radon’s recipe for choosing correct sites for multivariate polynomial interpolation

A class of sets correct for multivariate polynomial interpolation is defined and verified, and shown to coincide with the collection of all correct sets constructible by the recursive application of Radon’s recipe, and a recent concrete recipe for correct sets is shown to produce elements in that class.     

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.     

Pseudozeros of multivariate polynomials

The pseudozero set of a system of polynomials in complex variables is the subset of which is the union of the zero-sets of all polynomial systems that are near to in a suitable sense. This concept is made precise, and general properties of pseudozero sets are established. In particular it is shown that in many cases of natural interest, the pseudozero set is a semialgebraic set. Also, estimates are given for the size of the projections of pseudozero sets in coordinate directions. Several examples are presented illustrating some of the general theory developed here. Finally, algorithmic ideas are proposed for solving multivariate polynomials.

     

Some properties of multivariate extreme value distributions and multivariate tail equivalence

Summary Denote byH ak-dimensional extreme value distribution with marginal distributionH _i (x)=Λ(x)=exp(−e ^−x ),x∈R ¹. Then it is proved thatH(x)=Λ(x ₁)...Λ(x _k ) for anyx=(x ₁, ...,x _k ) ∈R ^k , if and only if the equation holds forx=(0,...,0). Next some multivariate extensions of the results by Resnick (1971,J. Appl. Probab.,8, 136–156) on tail equivalence and asymptotic distributions of extremes are established.     

On the complexity of the multivariate resultant

The multivariate resultant is a fundamental tool of computational algebraic geometry. It can in particular be used to decide whether a system of n$n$ homogeneous equations in n$n$ variables is satisfiable (the resultant is a polynomial in the system’s coefficients which vanishes if and only if the system is satisfiable). In this paper, we investigate the complexity of computing the multivariate resultant.     

Guaranteed error bounds for the initial value problem using polytope arithmetic

In this paper we propose and compare modifications of the method of co-ordinate transformations for finding guaranteed bounds for the numerical solution of the initial value problem. These modifications are judged on their success in overcoming exponentially too large growth of the computed error bound.     

A Gilmore-Gomory construction of integer programming value functions

In this paper, we analyze how sequentially introducing decision variables into an integer program (IP) affects the value function and its level sets. We use a Gilmore-Gomory approach to find parametrized IP value functions over a restricted set of variables. We introduce the notion of maximal connected subsets of level sets - volumes in which changes to the constraint right-hand side have no effect on the value function - and relate these structures to IP value functions and optimal solutions.     

Density of multivariate homogeneous polynomials on star like domains

The famous Weierstrass theorem asserts that every continuous function on a compact set in ${\mathbb{R}}^d$ can be uniformly approximated by algebraic polynomials. A related interesting problem consists in studying the same question for the important subclass of homogeneous polynomials containing only monomials of the same degree. The corresponding conjecture claims that every continuous function on the boundary of convex 0-symmetric bodies can be uniformly approximated by pairs of homogeneous polynomials. The main objective of the present paper is to review the recent progress on this conjecture and provide a new unified treatment of the same problem on non convex star like domains. It will be shown that the boundary of every 0-symmetric non convex star like domain contains an exceptional zero set so that a continuous function can be uniformly approximated on the boundary of the domain by a sum of two homogeneous polynomials if and only if the function vanishes on this zero set. Thus the Weierstrass type approximation problem for homogeneous polynomials on non convex star like domains amounts to the study of these exceptional zero sets. We will also present an extension of a theorem of Varjú which describes the exceptional zero sets for intersections of star like domains. These results combined with certain transformations of the underlying region will lead to the discovery of some new classes of convex and non convex domains for which the Weierstrass type approximation result holds for homogeneous polynomials.     

Polynomially solvable cases for the maximum stable set problem

We describe two classes of graphs for which the stability number can be computed in polynomial time. The first approach is based on an iterative procedure which, at each step, builds from a graph G a new graph G′ which has fewer vertices and has the property that (G′) = (G) − 1. For the second class, it can be decided in polynomial time whether there exists a stable set of given size k.     

Polynomials,random walks and risk processes: a multivariate framework

This paper is concerned with two families of multivariate polynomials: the Appell polynomials and the Abel-Gontcharoff polynomials. Both families are well-known in the univariate case, but their multivariate version is much less standard. We first provide a simple interpretation of these polynomials through particular constrained random walks on a lattice. We then derive nice analytical results for two special cases where the parameters of the polynomials are randomized. Thanks to the interpretation and randomization of the polynomials, we can derive new results and give other insights for the study of two different risk problems: the ruin probability in a multiline insurance model and the size distribution in a multigroup epidemic.     

Capturing the multivariate extremal index: bounds and interconnections

The multivariate extremal index function is a direction specific extension of the well-known univariate extremal index. Since statistical inference on this function is difficult it is desirable to have a broad characterization of its attributes. We extend the set of common properties of the multivariate extremal index function and derive sharp bounds for the entire function given only marginal dependence. Our results correspond to certain restrictions on the two dependence functions defining the multivariate extremal index, which are opposed to Smith and Weissman’s (1996) conjecture on arbitrary dependence functions. We show further how another popular dependence measure, the extremal coefficient, is closely related to the multivariate extremal index. Thus, given the value of the former it turns out that the above bounds may be improved substantially. Conversely, we specify improved bounds for the extremal coefficient itself that capitalize on marginal dependence, thereby approximating two views of dependence that have frequently been treated separately. Our results are completed with example processes.      

A note on the Lasserre hierarchy for different formulations of the maximum independent set problem

In this note, we consider several polynomial optimization formulations of the maximum independent set problem and the use of the Lasserre hierarchy with these different formulations. We demonstrate using computational experiments that the choice of formulation may have a significant impact on the resulting bounds. We also provide theoretical justifications for the observed behavior.