Convexity Properties of the Cone of Nonnegative Polynomials

We study metric properties of the cone of homogeneous nonnegative multivariate polynomials and the cone of sums of powers of linear forms, and the relationship between the two cones. We compute the maximum volume ellipsoid of the natural base of the cone of nonnegative polynomials and the minimum volume ellipsoid of the natural base of the cone of powers of linear forms and compute the coefficients of symmetry of the bases. The multiplication by (x₁ ² + ··· + x_n ²)^m induces an isometric embedding of the space of polynomials of degree 2k into the space of polynomials of degree 2(k+m), which allows us to compare the cone of nonnegative polynomials of degree 2k and the cone of sums of 2(k+m)-powers of linear forms. We estimate the volume ratio of the bases of the two cones and the rate at which it approaches 1 as m grows.     

Optimization Over the Boolean Hypercube Via Sums of Nonnegative Circuit Polynomials

Various key problems from theoretical computer science can be expressed as polynomial optimization problems over the boolean hypercube. One particularly successful way to prove complexity bounds for these types of problems is based on sums of squares (SOS) as nonnegativity certificates. In this article, we initiate optimization problems over the boolean hypercube via a recent, alternative certificate called sums of nonnegative circuit polynomials (SONC). We show that key results for SOS-based certificates remain valid: First, for polynomials, which are nonnegative over the n-variate boolean hypercube with constraints of degree d there exists a SONC certificate of degree at most \(n+d\). Second, if there exists a degree d SONC certificate for nonnegativity of a polynomial over the boolean hypercube, then there also exists a short degree d SONC certificate that includes at most \(n^{O(d)}\) nonnegative circuit polynomials. Moreover, we prove that, in opposite to SOS, the SONC cone is not closed under taking affine transformation of variables and that for SONC there does not exist an equivalent to Putinar’s Positivstellensatz for SOS. We discuss these results from both the algebraic and the optimization perspective.

     

On generic and maximal k-ranks of binary forms

In what follows, we pose two general conjectures about decompositions of homogeneous polynomials as sums of powers. The first one (suggested by G. Ottaviani) deals with the generic k-rank of complex-valued forms of any degree divisible by k in any number of variables. The second one (by the fourth author) deals with the maximal k-rank of binary forms. We settle the first conjecture in the cases of two variables and the second in the first non-trivial case of the 3-rd powers of quadratic binary forms.     

Connes' embedding conjecture and sums of hermitian squares

We show that Connes' embedding conjecture on von Neumann algebras is equivalent to the existence of certain algebraic certificates for a polynomial in noncommuting variables to satisfy the following nonnegativity condition: The trace is nonnegative whenever self-adjoint contraction matrices of the same size are substituted for the variables. These algebraic certificates involve sums of hermitian squares and commutators. We prove that they always exist for a similar nonnegativity condition where elements of separable II₁-factors are considered instead of matrices. Under the presence of Connes' conjecture, we derive degree bounds for the certificates.     

Bounding Averages Rigorously Using Semidefinite Programming: Mean Moments of the Lorenz System

We describe methods for proving bounds on infinite-time averages in differential dynamical systems. The methods rely on the construction of nonnegative polynomials with certain properties, similarly to the way nonlinear stability can be proved using Lyapunov functions. Nonnegativity is enforced by requiring the polynomials to be sums of squares, a condition which is then formulated as a semidefinite program (SDP) that can be solved computationally. Although such computations are subject to numerical error, we demonstrate two ways to obtain rigorous results: using interval arithmetic to control the error of an approximate SDP solution, and finding exact analytical solutions to relatively small SDPs. Previous formulations are extended to allow for bounds depending analytically on parametric variables. These methods are illustrated using the Lorenz equations, a system with three state variables (x, y, z) and three parameters \((\beta ,\sigma ,r)\). Bounds are reported for infinite-time averages of all eighteen moments \(x^ly^mz^n\) up to quartic degree that are symmetric under \((x,y)\mapsto (-x,-y)\). These bounds apply to all solutions regardless of stability, including chaotic trajectories, periodic orbits, and equilibrium points. The analytical approach yields two novel bounds that are sharp: the mean of \(z^3\) can be no larger than its value of \((r-1)^3\) at the nonzero equilibria, and the mean of \(xy^3\) must be nonnegative. The interval arithmetic approach is applied at the standard chaotic parameters to bound eleven average moments that all appear to be maximized on the shortest periodic orbit. Our best upper bound on each such average exceeds its value on the maximizing orbit by less than 1%. Many bounds reported here are much tighter than would be possible without computer assistance.     

Power sums with applications to multizeta and zeta zero distribution for Fq[t]

We study the sum of integral powers of monic polynomials of a given degree over a finite field. The combinatorics of cancellations are quite complicated. We prove several results on the degrees of these sums giving direct or recursive formulas, congruence conditions and degree bounds for them. We point out a ‘duality’ between values for positive and negative powers. We show that despite the combinatorial complexity of the actual values, there is an interesting kind of a recursive formula (at least when the finite field is the prime field) which quickly leads to many interesting structural facts, such as Riemann hypothesis for Carlitz–Goss zeta function, monotonicity in degree, non-vanishing and special identity classification for function field multizeta, as easy consequences.     

Combinatorial interpretations of the q-Faulhaber and q-Salié coefficients

Recently, Guo and Zeng discovered two families of polynomials featuring in a q-analogue of Faulhaber's formula for the sums of powers and a q-analogue of Gessel-Viennot's formula involving Salié's coefficients for the alternating sums of powers. In this paper, we show that these are polynomials with symmetric, nonnegative integral coefficients by refining Gessel-Viennot's combinatorial interpretations.     

Exponential sums and singular hypersurfaces

We give upper bounds for the absolute value of exponential sums in several variables attached to certain polynomials with coefficients in a finite field. This bounds are given in terms of invariants of the singularities of the projective hypersurface defined by its highest degree form. For exponential sums attached to the reduction modulo a power of a large prime of a polynomial f with integer coefficients and veryfying a certain condition on the singularities of its highest degree form, we give a bound in terms of the dimension of the Jacobian quotient . Received: 3 November 1997     

On Cones of Nonnegative Quartic Forms

Historically, much of the theory and practice in nonlinear optimization has revolved around the quadratic models. Though quadratic functions are nonlinear polynomials, they are well structured and many of them are found easy to deal with. Limitations of the quadratics, however, become increasingly binding as higher-degree nonlinearity is imperative in modern applications of optimization. In recent years, one observes a surge of research activities in polynomial optimization, and modeling with quartic or higher-degree polynomial functions has been more commonly accepted. On the theoretical side, there are also major recent progresses on polynomial functions and optimization. For instance, Ahmadi et al. (Math Program Ser A 137:453–476, 2013) proved that checking the convexity of a quartic polynomial is strongly NP-hard in general, which settles a long-standing open question. In this paper, we proceed to study six fundamentally important convex cones of quartic forms in the space of super-symmetric tensors, including the cone of nonnegative quartic forms, the sums of squared forms, the convex quartic forms, and the sums of fourth-power forms. It turns out that these convex cones coagulate into a chain in a decreasing order with varying complexity status. Potential applications of these results to solve highly nonlinear and/or combinatorial optimization problems are discussed.     

Gale duality bounds for roots of polynomials with nonnegative coefficients

We bound the location of roots of polynomials that have nonnegative coefficients with respect to a fixed but arbitrary basis of the vector space of polynomials of degree at most d. For this, we interpret the basis polynomials as vector fields in the real plane, and at each point in the plane analyze the combinatorics of the Gale dual vector configuration. This approach permits us to incorporate arbitrary linear equations and inequalities among the coefficients in a unified manner to obtain more precise bounds on the location of roots. We apply our technique to bound the location of roots of Ehrhart and chromatic polynomials. Finally, we give an explanation for the clustering seen in plots of roots of random polynomials.     

Sudoku-like arrays,codes and orthogonality

This paper is concerned with constructions and orthogonality of generalized Sudoku arrays of various forms. We characterize these arrays based on their constraints; for example Sudoku squares are characterized by having strip and sub-square constraints. First, we generalize Sudoku squares to be multi-dimensional arrays with strip and sub-cube constraints and construct mutually orthogonal sets of these arrays using linear polynomials. We add additional constraints motivated by elementary intervals for low discrepancy sequences and again give a construction of these arrays using linear polynomials in detail for 3 dimensional and a general construction method for arbitrary dimension. Then we give a different construction of these hypercubes due to MDS codes. We also analyze the orthogonality of all of the Sudoku-like hypercubes we consider in this paper.     

Moments and sums of squares for polynomial optimization and related problems

We briefly review the duality between moment problems and sums of squares (s.o.s.) representations of positive polynomials, and compare s.o.s. versus nonnegative polynomials. We then describe how to use such results to define convergent semidefinite programming relaxations in polynomial optimization as well as for the two related problems of computing the convex envelope of a rational function and finding all zeros of a system of polynomial equations.     

Nonlinear subelliptic equations

A finitely generated quadratic module or preordering in the real polynomial ring is called stable, if it admits a certain degree bound on the sums of squares in the representation of polynomials. Stability, first defined explicitly in Powers and Scheiderer (Adv Geom 1, 71–88, 2001), is a very useful property. It often implies that the quadratic module is closed; furthermore, it helps settling the Moment Problem, solves the Membership Problem for quadratic modules and allows applications of methods from optimization to represent nonnegative polynomials. We provide sufficient conditions for finitely generated quadratic modules in real polynomial rings of several variables to be stable. These conditions can be checked easily. For a certain class of semi-algebraic sets, we obtain that the nonexistence of bounded polynomials implies stability of every corresponding quadratic module. As stability often implies the non-solvability of the Moment Problem, this complements the result from Schmüdgen (J Reine Angew Math 558, 225–234, 2003), which uses bounded polynomials to check the solvability of the Moment Problem by dimensional induction. We also use stability to generalize a result on the Invariant Moment Problem from Cimpric et al. (Trans Am Math Soc, to appear).     

The digit generating function of a polynomial

The average frequency of 1 occurring as the kth digit in the binary expansion of squares, cubes, and generally the values of a polynomial is studied. In particular, it turns out that the generating function of these frequencies is rational for the important special cases of powers, linear and quadratic polynomials. For higher degree polynomials, the behaviour seems to be much more chaotic in general, which is exhibited by two examples of cubic polynomials.     

Bounds on degrees of p-adic separating polynomials

We study a discrete optimization problem introduced by Babai, Frankl, Kutin, and Štefankovi? (2001), which provides bounds on degrees of polynomials with p-adically controlled behavior. Such polynomials are of particular interest because they furnish bounds on the size of set systems satisfying Frankl-Wilson-type conditions modulo prime powers, with lower degree polynomials providing better bounds. We elucidate the asymptotic structure of solutions to the optimization problem, and we also provide an improved method for finding solutions in certain circumstances.     

Polynomials with and without determinantal representations

The problem of writing real zero polynomials as determinants of linear matrix polynomials has recently attracted a lot of attention. Helton and Vinnikov [9] have proved that any real zero polynomial in two variables has a determinantal representation. Brändén [2] has shown that the result does not extend to arbitrary numbers of variables, disproving the generalized Lax conjecture. We prove that in fact almost no real zero polynomial admits a determinantal representation; there are dimensional differences between the two sets. The result follows from a general upper bound on the size of linear matrix polynomials. We then provide a large class of surprisingly simple explicit real zero polynomials that do not have a determinantal representation. We finally characterize polynomials of which some power has a determinantal representation, in terms of an algebra with involution having a finite dimensional representation. We use the characterization to prove that any quadratic real zero polynomial has a determinantal representation, after taking a high enough power. Taking powers is thereby really necessary in general. The representations emerge explicitly, and we characterize them up to unitary equivalence.     

Diophantine m-tuples for linear polynomials II. Equal degrees

In this paper we prove the best possible upper bounds for the number of elements in a set of polynomials with integer coefficients all having the same degree, such that the product of any two of them plus a linear polynomial is a square of a polynomial with integer coefficients. Moreover, we prove that there does not exist a set of more than 12 polynomials with integer coefficients and with the property from above. This significantly improves a recent result of the first two authors with Tichy [A. Dujella, C. Fuchs, R.F. Tichy, Diophantine m-tuples for linear polynomials, Period. Math. Hungar. 45 (2002) 21-33].     

Sparse squares of polynomials

We answer a question left open in an article of Coppersmith and Davenport which proved the existence of polynomials whose powers are sparse, and in particular polynomials whose squares are sparse (i.e., the square has fewer terms than the original polynomial). They exhibit some polynomials of degree having sparse squares, and ask whether there are any lower degree complete polynomials with this property. We answer their question negatively by reporting that no polynomial of degree less than has a sparse square, and explain how the substantial computation was effected using the system CoCoA.

     

On Jordan’s inequality

We present sharp upper and lower bounds for the function \(\sin (x)/x\). Our bounds are polynomials of degree 2n, where n is any nonnegative integer.