Counting reducible and singular bivariate polynomials

Among the bivariate polynomials over a finite field, most are irreducible. We count some classes of special polynomials, namely the reducible ones, those with a square factor, the “relatively irreducible” ones which are irreducible but factor over an extension field, and the singular ones, which have a root at which both partial derivatives vanish.     

Erd s–Turán Type Theorems on Quasiconformal Curves and Arcs

The theorems of Erd s and Turán mentioned in the title are concerned with the distribution of zeros of a monic polynomial with known uniform norm along the unit interval or the unit disk. Recently, Blatt and Grothmann (Const. Approx.7(1991), 19–47), Grothmann (“Interpolation Points and Zeros of Polynomials in Approximation Theory,” Habilitationsschrift, Katholische Universität Eichstätt, 1992), and Andrievskii and Blatt (J. Approx. Theory88(1977), 109–134) established corresponding results for polynomials, considered on a system of sufficiently smooth Jordan curves and arcs or piecewise smooth curves and arcs. We extend some of these results to polynomials with known uniform norm along an arbitrary quasiconformal curve or arc. As applications, estimates for the distribution of the zeros of best uniform approximants, values of orthogonal polynomials, and zeros of Bieberbach polynomials and their derivatives are obtained. We also give a negative answer to one conjecture of Eiermann and Stahl (“Zeros of orthogonal polynomials on regularN-gons,” in Lecture Notes in Math.1574(1994), 187–189).     

Ridge wavelets on the ball

We present a ridge polynomial wavelet-type system on the unit ball in such that any continuous function can be expanded with respect to these wavelets. The order of the growth of the degrees of polynomials is optimal. Coefficient functionals are the inner products of the function and the corresponding elements of a “dual wavelet system”. The “dual wavelets” is also a ridge polynomial system with the same growth of the degrees of polynomials. The system is redundant.     

Representation of real commutative rings

During the last 10 years there have been several new results on the representation of real polynomials, positive on some semi-algebraic subset of . These results started with a solution of the moment problem by Schmüdgen for compact semi-algebraic sets. Later, Wörmann realized that the same results could be obtained by the so-called “Kadison–Dubois” Representation Theorem.The aim of our paper is to present this representation theorem together with its history, and to discuss its implication to the representation of positive polynomials. Also recent improvements of both topics by T. Jacobi and the author will be included.     

On Local Smoothness Classes of Periodic Functions

We obtain a characterization of local Besov spaces of periodic functions in terms of trigonometric polynomial operators. We construct a sequence of operators whose values are (global) trigonometric polynomials, and yet their behavior at different points reflects the behavior of the target function near each of these points. In addition to being localized, our operators preserve trigonometric polynomials of degree commensurate with the degree of polynomials given by the operators. Our constructions are “universal;” i.e., they do not require an a priori knowledge about the smoothness of the target functions. Several numerical examples are discussed, including applications to the problem of direction finding in phased array antennas and finding the location of jump discontinuities of derivatives of different order.     

Almost strict total positivity and a class of Hurwitz polynomials

We establish sufficient conditions for a matrix to be almost totally positive, thus extending a result of Craven and Csordas who proved that the corresponding conditions guarantee that a matrix is strictly totally positive. Then we apply our main result in order to obtain a new criteria for a real algebraic polynomial to be a Hurwitz one. The properties of the corresponding “extremal” Hurwitz polynomials are discussed.     

Decomposition of Green polynomials of type A and Springer modules for hooks and rectangles

This paper deals with graded representations of the symmetric group on the cohomology ring of flags fixed by a unipotent matrix. We consider a combinatorial property, called the “coincidence of dimension” of the graded representations, and give an interpretation in terms of representation theory of the symmetric group in the case where the corresponding partition of the unipotent matrix is a hook or a rectangle. The interpretation is equivalent to a recursive formula of Green polynomials at roots of unity.     

The invariant polynomials characterizing U(n) tensor operators p, q,…, q, 0,…, 0 having maximal null space

We make use of the “path sum” function to prove that the family of stretched operator functions characterized by the operator irrep labels p,q,…,q, 0,…, 0 satisfy a pair of general difference equations. This family of functions is a generalization of Milne's p,q,…,q, 0, functions for U(n) and Biedenharn and Louck's p,q, 0 functions for U(3). The fact that this family of stretched operator functions are polynomials follows from a detailed study of their symmetries and zeros. As a further application of our general difference equations and symmetry properties we give an explicit formula for the polynomials characterized by the operator irrep labels p, 1, 0,…, 0.     

On the areas of cyclic and semicyclic polygons

We investigate the “generalized Heron polynomial” that relates the squared area of an n-gon inscribed in a circle to the squares of its side lengths. For a (2m+1)-gon or (2m+2)-gon, we express it as the defining polynomial of a certain variety derived from the variety of binary (2m−1)-forms having m−1 double roots. Thus we obtain explicit formulas for the areas of cyclic heptagons and octagons, and illuminate some mysterious features of Robbins' formulas for the areas of cyclic pentagons and hexagons. We also introduce a companion family of polynomials that relate the squared area of an n-gon inscribed in a circle, one of whose sides is a diameter, to the squared lengths of the other sides. By similar algebraic techniques we obtain explicit formulas for these polynomials for all n7.     

Affine Hecke algebras and the Schubert calculus

Using a combinatorial approach that avoids geometry, this paper studies the structure of K_T(G/B), the T-equivariant K-theory of the generalized flag variety G/B. This ring has a natural basis (the double Grothendieck polynomials), where is the structure sheaf of the Schubert variety X_w. For rank two cases we compute the corresponding structure constants of the ring K_T(G/B) and, based on this data, make a positivity conjecture for general G which generalizes the theorems of M. Brion (for K(G/B)) and W. Graham (for H_T^*(G/B)). Let [X^λ]K_T(G/B) be the class of the homogeneous line bundle on G/B corresponding to the character of T indexed by λ. For general G we prove “Pieri–Chevalley formulas” for the products , , , and , where λ is dominant. By using the Chern character and comparing lowest degree terms the products which are computed in this paper also give results for the Grothendieck polynomials, double Schubert polynomials, and ordinary Schubert polynomials in, respectively K(G/B), H_T^*(G/B) and H^*(G/B).     

Certificates for nonnegativity of polynomials with zeros on compact semialgebraic sets

We prove a criterion for an element of a commutative ring to be contained in an archimedean subsemiring. It can be used to investigate the question whether nonnegativity of a polynomial on a compact semialgebraic set can be certified in a certain way. In case of (strict) positivity instead of nonnegativity, our criterion simplifies to classical results of Stone, Kadison, Krivine, Handelman, Schmüdgen et al. As an application of our result, we give a new proof of the following result of Handelman: If an odd power of a real polynomial in several variables has only nonnegative coefficients, then so do all sufficiently high powers.Partially supported by the DFG project 214371 “Darstellung positiver Polynome”.     

Positivity of certain sums over Jacobi kernel polynomials

We present a computer-assisted proof of positivity of sums over kernel polynomials for ultraspherical Jacobi polynomials.     

Chains of dog-ears for completely positive matrices

A necessary and sufficient condition to determine the complete positivity of a matrixwith a particular graph, in dependence of complete positivity of smaller matrices, is given. Under some singularity assumptions, this condition furnishes a characterization for completely positive matrices with a “non-crossing cycle” as associated graph. In particular the characterization holds for singular pentadiagonal matrices.     

A class of mechanically decidable problems beyond Tarski's model

By means of dimension-decreasing method and cell-decomposition,a practical algorithm is proposed to decide the positivity of a certain class of symmetric polynomials,the numbers of whose elements are variable.This is a class of mechanically decidable problems beyond Tarski model.To im- plement the algorithm,a program nprove written in maple is developed which can decide the positivity of these polynomials rapidly.     

On the combinatorics of the Boros-Moll polynomials

The Boros-Moll polynomials arise in the evaluation of a quartic integral. The original double summation formula does not imply the fact that the coefficients of these polynomials are positive. Boros and Moll proved the positivity by using Ramanujan’s Master Theorem to reduce the double sum to a single sum. Based on the structure of reluctant functions introduced by Mullin and Rota along with an extension of Foata’s bijection between Meixner endofunctions and bi-colored permutations, we find a combinatorial proof of the positivity. In fact, from our combinatorial argument one sees that it is essentially the binomial theorem that makes it possible to reduce the double sum to a single sum.     

Interpolation of Sparse Multivariate Polynomials over Large Finite Fields with Applications

We develop a Las Vegas-randomized algorithm which performs interpolation of sparse multivariate polynomials over finite fields. Our algorithm can be viewed as the first successful adaptation of the sparse polynomial interpolation algorithm for the complex field developed by M. Ben-Or and P. Tiwari (1988, in “Proceedings of the 20th ACM Symposium on the Theory of Computing,” pp. 301–309, Assoc. Comput. Mach., New York) to the case of finite fields. It improves upon a previous result by D. Y. Grigoriev, M. Karpinski, and M. F. Singer (1990, SIAM J. Comput.19, 1059–1063) and is by far the most time efficient algorithm (time and processor efficient parallel algorithm) for the problem when the finite field is large. As applications, we obtain Monte Carlo-randomized parallel algorithms for sparse multivariate polynomial factorization and GCD over finite fields. The efficiency of these algorithms improves upon that of the previously known algorithms for the respective problems.     

The Combinatorics of a Class of Representation Functions

In the study of the irreducible representations of the unitary groupU(n), one encounters a class of polynomials defined onn²indeterminatesz_ij, 1i, jn, which may be arranged into ann×nmatrix arrayZ=(z_ij). These polynomials are indexed by double Gelfand patterns, or equivalently, by pairs of column strict Young tableaux of the same shape. Using the double labeling property, one may define a square matrixD(Z), whose elements are the double-indexed polynomials. These matrices possess the remarkable “group multiplication property”D(XY)=D(X) D(Y) for arbitrary matricesXandY, even though these matrices may be singular. ForZ=UU(n), these matrices give irreducible unitary representations ofU(n). These results are known, but not always fully proved from the extensive physics literature on representation of the unitary groups, where they are often formulated in terms of the boson calculus, and the multiplication property is unrecognized. The generality of the multiplication property is the key to understanding group representation theory from the purview of combinatorics. The combinatorial structure of the general polynomials is expected to be intricate, and in this paper, we take the first step to explore the combinatorial aspects of a special class which can be defined in terms of the set of integral matrices with given row and column sums. These special polynomials are denoted byL_{α, β}(Z), whereαandβare integral vectors representing the row sums and column sums of a class of integral matrices. We present a combinatorial interpretation of the multiplicative properties of these polynomials. We also point out the connections with MacMahon's Master Theorem and Schwinger's inner product formula, which is essentially equivalent to MacMahon's Master Theorem. Finally, we give a formula for the double Pfaffian, which is crucial in the studies of the generating function of the 3n−jcoefficients in angular momentum theory. We also review the background of the general polynomials and give some of their properties.     

Positivstellens?tze for real function algebras

We look for algebraic certificates of positivity for functions which are not necessarily polynomial functions. Similar questions were examined earlier by Lasserre and Putinar [Positivity and optimization for semi-algebraic functions (to appear), Proposition 1] and by Putinar [A Striktpositivestellensatz for measurable functions (corrected version) (to appear), Theorem 2.1]. We explain how these results can be understood as results on hidden positivity: The required positivity of the functions implies their positivity when considered as polynomials on the real variety of the respective algebra of functions. This variety is however not directly visible in general. We show how algebras and quadratic modules with this hidden positivity property can be constructed. We can then use known results, for example Jacobi’s representation theorem (Jacobi in Math Z 237:259–273, 2001, Theorem 4), or the Krivine-Stengle Positivstellensatz (Marshall in Positive polynomials and sums of squares. Mathematical Surveys and Monographs 146, 2008, page 25), to obtain certificates of positivity relative to a quadratic module of an algebra of real-valued functions. Our results go beyond the results of Lasserre and Putinar, for example when dealing with non-continuous functions. The conditions are also easier to check. We explain the application of our result to various sorts of real finitely generated algebras of semialgebraic functions. The emphasis is on the case where the quadratic module is also finitely generated. Our results also have application to optimization of real-valued functions, using the semidefinite programming relaxation methods pioneered by Lasserre [SIAM J Optim 11(3): 796–817, 2001; Lasserre in Moments, positive polynomials and their applications. Imperial College Press, London, 2009; Lasserre and Putinar in Positivity and optimization for semi-algebraic functions (to appear); Marshall in Positive polynomials and sums of squares. Mathematical Surveys and Monographs 146, 2008, page 25].     

Multi-step quasi-Newton methods for optimization

Quasi-Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. We show how “multi-step” methods (employing, in addition, data from previous iterations) may be constructed by means of interpolating polynomials, leading to a generalization of the “secant” (or “quasi-Newton”) equation. The issue of positive-definiteness in the Hessian approximation is addressed and shown to depend on a generalized version of the condition which is required to hold in the original “single-step” methods. The results of extensive numerical experimentation indicate strongly that computational advantages can accrue from such an approach (by comparison with “single-step” methods), particularly as the dimension of the problem increases.     

Expansions for the multivariate chi-square distribution

Three classes of expansions for the distribution function of the χ_k²(d, R)-distribution are given, where k denotes the dimension, d the degree of freedom, and R the “accompanying correlation matrix.” The first class generalizes the orthogonal series with generalized Laguerre polynomials, originally given by Krishnamoorthy and Parthasarathy [12]. The second class contains always absolutely convergent representations of the distribution function by univariate chi-square distributions and the third class provides also the probabilities for any unbounded rectangular regions. In particular, simple formulas are given for the three-variate case including singular correlation matrices R, which simplify the computation of third order Bonferroni inequalities, e.g., for the tail probabilities of max{χ_i²|1 ≤ i ≤ k} (k > 3).