There are significantly more nonegative polynomials than sums of squares

We study the quantitative relationship between the cones of nonnegative polynomials, cones of sums of squares and cones of sums of even powers of linear forms. We derive bounds on the volumes (raised to the power reciprocal to the ambient dimension) of compact sections of the three cones. We show that the bounds are asymptotically exact if the degree is fixed and number of variables tends to infinity. When the degree is larger than two, it follows that there are significantly more nonnegative polynomials than sums of squares and there are significantly more sums of squares than sums of even powers of linear forms. Moreover, we quantify the exact discrepancy between the cones; from our bounds it follows that the discrepancy grows as the number of variables increases.     

Max-algebraic attraction cones of nonnegative irreducible matrices

It is known that the max-algebraic powers A^r of a nonnegative irreducible matrix are ultimately periodic. This leads to the concept of attraction cone Attr(A, t), by which we mean the solution set of a two-sided system λ^t(A)A^r⊗x=A^r+t⊗x, where r is any integer after the periodicity transient T(A) and λ(A) is the maximum cycle geometric mean of A. A question which this paper answers, is how to describe Attr(A,t) by a concise system of equations without knowing T(A). This study requires knowledge of certain structures and symmetries of periodic max-algebraic powers, which are also described. We also consider extremals of attraction cones in a special case, and address the complexity of computing the coefficients of the system which describes attraction cone.     

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 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.     

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.     

Ankeny-Artin-Chowla type congruences modulo p 3

The goal of this paper is to use algebraic techniques to compute sums of powers of roots of certain polynomials and derive congruences of Ankeny-Artin-Chowla types modulo p ³.     

Bernoulli numbers and sums of powers

There have been many studies of Bernoulli numbers since Jakob Bernoulli first used the numbers to compute sums of powers, 1 ^p + 2 ^p + 3 ^p + ··· + n^p , where n is any natural number and p is any non-negative integer. By examining patterns of these sums for the first few powers and the relation between their coefficients and Bernoulli numbers, the author hypothesizes and proves a new recursive algorithm for computing Bernoulli numbers, sums of powers, as well as m-ford sums of powers, which enrich the existing literatures of Bernoulli numbers.     

The cone of nonnegative polynomials with nonnegative coefficients and linear operators preserving this cone

Let be the cone of real univariate polynomials of degree ≤ 2n which are nonnegative on the real axis and have nonnegative coefficients. We describe the extremal rays of this convex cone and the class of linear operators, acting diagonally in the standard monomial basis, preserving this cone.     

Comparison between the best approximations by lacunary and ordinary polynomials

We denote E_n(f) and E _k ⁿ (f) the best uniform approximations to a continuous function f defined on [a,b] by the sets of algebraic polynomials of degree ≤n and algebraic polynomials of degree ≤n with the coefficients of x^k (k≤n) being zero. In this paper, in cases of r<k and r≥k while [a, b]=[−1,1] (or r<k,k≤r<2k and r>2k while [a,b]=[0, 1]), we separately discuss the condtions for r-times continuously differentiable function f which enables .     

Poincaré series

Let N_α denote the number of solutions to the congruence F(x_i,..., x_m) ≡ 0 (mod p^α) for a polynomial F(x_i,..., x_m) with integral p-adic coefficients. We examine the series \(\varphi (t) = \sum\nolimits_{\alpha = 0}^\infty {N_{\alpha ^{t^\alpha } } } \) . called the Poincaré series for the polynomial F. In this work we prove the rationality of the series ?(t) for a class of isometrically equivalent polynomials of m variables, m ≥ 2, containing the sum of two forms ?_n(x, y) + ?_n+1(x, y) respectively of degrees n and n+1, n ≥ 2. In particular the Poincaré series for any third degree polynomial F₃(x, y) (over the set of unknowns) with integral p-adic coefficients is a rational function of t.     

On Representation of a Solution to the Cauchy Problem by a Fourier Series in Sobolev-Orthogonal Polynomials Generated by Laguerre Polynomials

We consider the problem of representing a solution to the Cauchy problem for an ordinary differential equation as a Fourier series in polynomials l _r,k ^α (x) (k = 0, 1,...) that are Sobolev-orthonormal with respect to the inner product

$$\left\langle {f,g} \right\rangle = \sum\limits_{v = 0}^{r - 1} {{f^{(v)}}(0){g^{(v)}}} (0) + \int\limits_0^\infty {{f^{(r)}}(t)} {g^{(r)}}(t){t^\alpha }{e^{ - t}}dt$$

, and generated by the classical orthogonal Laguerre polynomials L _k ^α (x) (k = 0, 1,...). The polynomials l _r,k ^α (x) are represented as expressions containing the Laguerre polynomials L _n ^α?r (x). An explicit form of the polynomials l _r,k+r ^α (x) is established as an expansion in the powers x ^r+l , l = 0,..., k. These results can be used to study the asymptotic properties of the polynomials l _r,k ^α (x) as k→∞and the approximation properties of the partial sums of Fourier series in these polynomials.

     

New class of polynomials

Summary For the simple Bessel polynomials y_n(x), the Rodrigues' formula is y_n(x)==2⁻ⁿe^2/xDⁿ(x²ⁿe^−2/x). The present work generalizes the idea of the simple. Bessel polynomials of Krall-Frink. It is of great interest to investigate the class of polynomials which are closely connected with the Rodrigues' expression e^3/xDⁿ(x³ⁿe^−3/x) or more generally with e^k/xDⁿ(x^kne^−k/x).     

Accuracy of several multidimensional refinable distributions

Compactly supported distributions f₁,..., f_r on ℝ^d are fefinable if each f_i is a finite linear combination of the rescaled and translated distributions f_j(Ax−k), where the translates k are taken along a lattice Γ ⊂ ∝^d and A is a dilation matrix that expansively maps Γ into itself. Refinable distributions satisfy a refinement equation f(x)=Σ_k∈Λ c_k f(Ax−k), where Λ is a finite subset of Γ, the c_k are r×r matrices, and f=(f₁,...,f_r)^T. The accuracy of f is the highest degree p such that all multivariate polynomials q with degree(q)<p are exactly reproduced from linear combinations of translates of f₁,...,f_r along the lattice Γ. We determine the accuracy p from the matrices c_k. Moreover, we determine explicitly the coefficients y_α,i(k) such that x^α=Σ _i=1 ^r Σ_k∈Γy_α,i(k) fi(x+k). These coefficients are multivariate polynomials y_α,i(x) of degree |α| evaluated at lattice points k∈Γ.     

Cauchy, Ferrers-Jackson and Chebyshev polynomials and identities for the powers of elements of some conjugate recurrence sequences

In this paper some decompositions of Cauchy polynomials, Ferrers-Jackson polynomials and polynomials of the form x ²ⁿ + y ²ⁿ , n ∈ ℕ, are studied. These decompositions are used to generate the identities for powers of Fibonacci and Lucas numbers as well as for powers of the so called conjugate recurrence sequences. Also, some new identities for Chebyshev polynomials of the first kind are presented here.     

Two cores of a nonnegative matrix

We prove that the sequence of eigencones (i.e., cones of nonnegative eigenvectors) of positive powers A^k$A^k$ of a nonnegative square matrix A is periodic both in max algebra and in nonnegative linear algebra. Using an argument of Pullman, we also show that the Minkowski sum of the eigencones of powers of A is equal to the core of A defined as the intersection of nonnegative column spans of matrix powers, also in max algebra. Based on this, we describe the set of extremal rays of the core.     

On the enumeration of certain weighted graphs

We enumerate weighted simple graphs with a natural upper bound condition on the sum of the weight of adjacent vertices. We also compute the generating function of the numbers of these graphs, and prove that it is a rational function. In particular, we show that the generating function for connected bipartite simple graphs is of the form p₁(x)/(1-x)^m+1. For nonbipartite simple graphs, we get a generating function of the form p₂(x)/(1-x)^m+1(1+x)^l. Here m is the number of vertices of the graph, p₁(x) is a symmetric polynomial of degree at most m, p₂(x) is a polynomial of degree at most m+l, and l is a nonnegative integer. In addition, we give computational results for various graphs.     

Approximation Properties of the Operators ⋎n+2r(f) and of Their Discrete Analogs

This paper is devoted to the study of the approximation properties of linear operators which are partial Fourier--Legendre sums of order n with 2r terms of the form _k=1 ^2r a_kP_n+k(x) added; here P _m(x) denotes the Legendre polynomial. Due to this addition, the linear operators interpolate functions and their derivatives at the endpoints of the closed interval [-1,1], which, in fact, for r= = 1 allows us to significantly improve the approximation properties of partial Fourier--Legendre sums. It is proved that these operators realize order-best uniform algebraic approximation of the classes of functions and A _q (B). With the aim of the computational realization of these operators, we construct their discrete analogs by means of Chebyshev polynomials, orthogonal on a uniform grid, also possessing nice approximation properties.     

Bilinear optimality constraints for the cone of positive polynomials

For a proper cone \({{\mathcal K}\subset\mathbb{R}^n}\) and its dual cone \({{\mathcal K}^*}\) the complementary slackness condition \({\langle{\rm {\bf x}},{\rm {\bf s}}\rangle=0}\) defines an n-dimensional manifold \({C({\mathcal K})}\) in the space \({{\mathbb R}^{2n}}\) . When \({{\mathcal K}}\) is a symmetric cone, points in \({C({\mathcal K})}\) must satisfy at least n linearly independent bilinear identities. This fact proves to be useful when optimizing over such cones, therefore it is natural to look for similar bilinear relations for non-symmetric cones. In this paper we define the bilinearity rank of a cone, which is the number of linearly independent bilinear identities valid for points in \({C({\mathcal K})}\) . We examine several well-known cones, in particular the cone of positive polynomials \({{\mathcal P}_{2n+1}}\) and its dual, and show that there are exactly four linearly independent bilinear identities which hold for all \({({\rm {\bf x}},{\rm {\bf s}})\in C({\mathcal P}_{2n+1})}\), regardless of the dimension of the cones. For nonnegative polynomials over an interval or half-line there are only two linearly independent bilinear identities. These results are extended to trigonometric and exponential polynomials. We prove similar results for Müntz polynomials.     

Characterization of certain classes of orthogonal polynomials related to elliptic functions

Summary In this paper we determine all orthogonal polynomials U_n(x) such that U_n(x)=x^−1/2 F _2n+1 (x ^1/2 ) and where f(t), u(t) have Taylor series expansions. Supported in part by N. S. F. grant GP-1593.