On theorems of Gelfond and Selberg concerning integral-valued entire functions

For each sN define the constant θ_s with the following properties: if an entire function g(z) of type t(g)<θ_s satisfies then g is a polynomial; conversely, for any δ>0 there exists an entire transcendental function g(z) satisfying the display conditin and t(g)<θ_s+δ. The result θ₁=log2 is known due to Hardy and Pólya. We provide the upper bound θ_sπs/3 and improve earlier lower bounds due to Gelfond (1929) and Selberg (1941).     

Polynomial functions and permutation polynomials over some finite commutative rings

We extend some classical results on polynomial functions . We prove all results in algebraic methods avoiding any combinatorial calculation. As applications of our methods, we obtain some interesting new results on permutation polynomials in several variables over some finite commutative rings.     

Asymptotics of zeros of polynomials arising from rational integrals

We prove that the zeros of the polynomials Pm(a) of degree m, defined by Boros and Moll via

     

Robust Algorithms for the Stable Set Problem

The stable set problem is to find in a simple graph a maximum subset of pairwise non-adjacent vertices. The problem is known to be NP-hard in general and can be solved in polynomial time on some special classes, like cographs or claw-free graphs. Usually, efficient algorithms assume membership of a given graph in a special class. Robust algorithms apply to any graph G and either solve the problem for G or find in it special forbidden configurations. In the present paper we describe several efficient robust algorithms, extending some known results.     

Multivariate Polynomial Minimization and Its Application in Signal Processing

We make a conjecture that the number of isolated local minimum points of a 2n-degree or (2n+1)-degree r-variable polynomial is not greater than n ^r when n 2. We show that this conjecture is the minimal estimate, and is true in several cases. In particular, we show that a cubic polynomial of r variables may have at most one local minimum point though it may have 2^r critical points. We then study the global minimization problem of an even-degree multivariate polynomial whose leading order coefficient tensor is positive definite. We call such a multivariate polynomial a normal multivariate polynomial. By giving a one-variable polynomial majored below a normal multivariate polynomial, we show the existence of a global minimum of a normal multivariate polynomial, and give an upper bound of the norm of the global minimum and a lower bound of the global minimization value. We show that the quartic multivariate polynomial arising from broad-band antenna array signal processing, is a normal polynomial, and give a computable upper bound of the norm of the global minimum and a computable lower bound of the global minimization value of this normal quartic multivariate polynomial. We give some sufficient and necessary conditions for an even order tensor to be positive definite. Several challenging questions remain open.     

On bifurcation points of a complex polynomial

Let be a polynomial of degree . Assume that the set there is a sequence s.t. and is finite. We prove that the set of generalized critical values of (hence in particular the set of bifurcation points of ) has at most points. Moreover, We also compute the set effectively.

     

A functional equation arising from multiplication of quantum integers

For the quantum integer [n]_q=1+q+q²+?+qⁿ⁻¹ there is a natural polynomial multiplication such that [m]_q⊗_q[n]_q=[mn]_q. This multiplication leads to the functional equation f_m(q)f_n(q^m)=f_mn(q), defined on a given sequence of polynomials. This paper contains various results concerning the construction and classification of polynomial sequences that satisfy the functional equation, as well open problems that arise from the functional equation.     

Approximation Constants in Equidistant Lagrange Interpolation

In this paper we present a new limit relation for the equidistant Lagrange interpolation polynomials to |x|, (0, 1] on the internal [–1, 1]. The result extends a well-known result of D. L. Berman and S. M. Losinskii. Furthermore, we briefly discuss on a possible connection of the limit relation to another prominent constant in best uniform polynomial approximation for |x| - the so-called Bernstein constant.     

Borel Subalgebras Redux with Examples from Algebraic and Quantum Groups

Both building upon and revising previous literature, this paper formulates the general notion of a Borel subalgebra B of a quasi-hereditary algebra A. We present various general constructions of Borel subalgebras, establish a triangular factorization of A, and relate the concept to graded Kazhdan–Lusztig theories in the sense of Cline et al. (Tôhoku Math. J. 45 (1993), 511–534). Various interesting types of Borel subalgebras arise naturally in different contexts. For example, `excellent" Borel subalgebras come about by abstracting the theory of Schubert varieties. Numerous examples from algebraic groups, q-Schur algebras, and quantum groups are considered in detail.     

Choiceless polynomial time

Turing machines define polynomial time (PTime) on strings but cannot deal with structures like graphs directly, and there is no known, easily computable string encoding of isomorphism classes of structures. Is there a computation model whose machines do not distinguish between isomorphic structures and compute exactly PTime properties? This question can be recast as follows: Does there exist a logic that captures polynomial time (without presuming the presence of a linear order)? Earlier, one of us conjectured a negative answer. The problem motivated a quest for stronger and stronger PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choiceless fragment of PTime. Our computation model is a version of abstract state machines (formerly called evolving algebras). The idea is to replace arbitrary choice with parallel execution. The resulting logic expresses all properties expressible in any other PTime logic in the literature. A more difficult theorem shows that the logic does not capture all of PTime.