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

Necessary and sufficient conditions for functions involving the tri- and tetra-gamma functions to be completely monotonic

The psi function ψ(x) is defined by ψ(x)=Γ^′(x)/Γ(x), where Γ(x) is the gamma function. We give necessary and sufficient conditions for the function ψ^″(x)+[ψ^′(x+α)]² or its negative to be completely monotonic on (−α,∞), where . We also prove that the function [ψ^′(x)]²+λψ^″(x) is completely monotonic on (0,∞) if and only if λ1. As an application of the latter conclusion, the monotonicity and convexity of the function e^pψ(x+1)−qx with respect to x(−1,∞) are thoroughly discussed for p≠0 and .     

Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

Quadratic Hermite–Padé polynomials associated with the exponential function

The asymptotic behavior of quadratic Hermite–Padé polynomials associated with the exponential function is studied for n→∞. These polynomials are defined by the relation

(*)

p_n(z)+q_n(z)e^z+r_n(z)e^2z=O(z³ⁿ⁺²) as z→0,

where O(·) denotes Landau's symbol. In the investigation analytic expressions are proved for the asymptotics of the polynomials, for the asymptotics of the remainder term in (*), and also for the arcs on which the zeros of the polynomials and of the remainder term cluster if the independent variable z is rescaled in an appropriate way. The asymptotic expressions are defined with the help of an algebraic function of third degree and its associated Riemann surface. Among other possible applications, the results form the basis for the investigation of the convergence of quadratic Hermite–Padé approximants, which will be done in a follow-up paper.     

A Criterion of Normality Concerning Holomorphic Functions Whose Derivative Omits a Function

The authors discuss the normality concerning holomorphic functions and get the following result. Let F be a family of holomorphic functions on a domain D ⊂ ℂ, all of whose zeros have multiplicity at least k, where k ≥ 2 is an integer. And let h(z) ≢ 0 be a holomorphic function on D. Assume also that the following two conditions hold for every f ∈ F: (a) f(z) = 0 ⇒ |f ^(k)(z)| < |h(z)|; (b) f ^(k)(z) ≠ h(z). Then F is normal on D.     

The Asymptotic Worst-Case Behavior of the FFD Heuristic for Small Items

The First-Fit-Decreasing (FFD) algorithm is one of the most famous and most studied methods for an approximative solution of the bin-packing problem. The question on the parametric behavior of the FFD heuristic for small items was raised in D. S. Johnson's thesis (1973, MIT, Cambridge, MA) and in E. G. Coffman et al. (1987, SIAM J. Comput.7, 1–17): what is the asymptotic worst-case ratio for FFD when restricted to lists with item sizes in the interval (0, α] for α ≤ . Let R^∞_FFD(α) denote the asymptotic worst-case ratio for these lists. In his thesis, Johnson gave the values of R^∞_FFD(α) for and he conjectured that

Full-size image

for all integers m ≥ 4. J. Csirik (1993, J. Algorithms15, 1–28) proved that, for all integers m ≥ 5, this conjecture is true when m is even. When m is odd, he further showed where G_m ≡ 1 + (m² + m − 1)/(m(m + 1)(m + 2)) = F_m + 1/(m(m + 1)(m + 2)). These results leave open the values of R^∞_FFD(α) for 0 < α < 1/5 that are not the reciprocals of integers. In this paper we resolve the remaining open cases.     

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n^{2 + max(α, β)}) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(n^max(α, β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a “Monge property” and that the SMAWK algorithm on monotone matrices can therefore be applied.     

Stability interval for explicit difference schemes for multi-dimensional second-order hyperbolic equations with significant first-order space derivative terms

In this piece of work, we introduce a new idea and obtain stability interval for explicit difference schemes of O(k²+h²) for one, two and three space dimensional second-order hyperbolic equations u_tt=a(x,t)u_xx+α(x,t)u_x-2η²(x,t)u,u_tt=a(x,y,t)u_xx+b(x,y,t)u_yy+α(x,y,t)u_x+β(x,y,t)u_y-2η²(x,y,t)u, and u_tt=a(x,y,z,t)u_xx+b(x,y,z,t)u_yy+c(x,y,z,t)u_zz+α(x,y,z,t)u_x+β(x,y,z,t)u_y+γ(x,y,z,t)u_z-2η²(x,y,z,t)u,0<x,y,z<1,t>0 subject to appropriate initial and Dirichlet boundary conditions, where h>0 and k>0 are grid sizes in space and time coordinates, respectively. A new idea is also introduced to obtain explicit difference schemes of O(k²) in order to obtain numerical solution of u at first time step in a different manner.     

CONVEX CONCENTRATION INEQUALITIES FOR CONTINUOUS GAS AND STOCHASTIC DOMINATION

In this article, we consider the continuous gas in a bounded domain ∧ of R^＋ or R^d described by a Gibbsian probability measure μη∧ associated with a pair interaction φ, the inverse temperature β, the activity z 〉 0, and the boundary condition η. Define F ∫ωf（s）wA（ds）. Applying the generalized Ito＇s formula for forward-backward martingales （see Klein et M. [5]）, we obtain convex concentration inequalities for F with respect to the Gibbs measure μη∧. On the other hand, by FKG inequality on the Poisson space, we also give a new simple argument for the stochastic domination for the Gibbs measure.     

On the Uniform Approximation of a Class of Analytic Functions by Bruwier Series

For a class of analytic functions f(z) defined by Laplace–Stieltjes integrals the uniform convergence on compact subsets of the complex plane of the Bruwier series (B-series) ∑^∞_n=0 λ_n(f) , λ_n(f)=f⁽ⁿ⁾(nc)+cf⁽ⁿ⁺¹⁾(nc), generated by f(z) and the uniform approximation of the generating function f(z) by its B-series in cones |arg z|< is shown.     

Polynomial projectors preserving homogeneous partial differential equations

A polynomial projector Π of degree d on is said to preserve homogeneous partial differential equations (HPDE) of degree k if for every and every homogeneous polynomial of degree k, q(z)=∑_|α|=ka_αz^α, there holds the implication: q(D)f=0q(D)Π(f)=0. We prove that a polynomial projector Π preserves HPDE of degree if and only if there are analytic functionals with such that Π is represented in the following form

with some , where u_α(z)z^α/α!. Moreover, we give an example of polynomial projectors preserving HPDE of degree k (k1) without preserving HPDE of smaller degree. We also give a characterization of Abel–Gontcharoff projectors as the only Birkhoff polynomial projectors that preserve all HPDE.     

Entire functions that share a polynomial with their derivatives

Let f be a nonconstant entire function, k and q be positive integers satisfying k>q, and let Q be a polynomial of degree q. This paper studies the uniqueness problem on entire functions that share a polynomial with their derivatives and proves that if the polynomial Q is shared by f and f^′ CM, and if f^(k)(z)−Q(z)=0 whenever f(z)−Q(z)=0, then f≡f^′. We give two examples to show that the hypothesis k>q is necessary.     

On an infinite series of Abel occurring in the theory of interpolation

The purpose of this paper is to show that for a certain class of functions f which are analytic in the complex plane possibly minus (−∞, −1], the Abel series f(0) + Σ_{n = 1}^∞ f⁽ⁿ⁾(nβ) z(z − nβ)^{n − 1}/n! is convergent for all β>0. Its sum is an entire function of exponential type and can be evaluated in terms of f. Furthermore, it is shown that the Abel series of f for small β>0 approximates f uniformly in half-planes of the form Re(z) − 1 + δ, δ>0. At the end of the paper some special cases are discussed.     

A Two-Parameter Family of Orthogonal Polynomials with Respect to a Jacobi-Type Weight on the Unit Circle

A two-parameter family of polynomials is introduced by a recursion formula. The polynomials are orthogonal on the unit circle with respect to the weight ω_{α, β}(θ) = |(1 − z)^α(1 + z)^β|², α, β > − , z = e^iθ. Explicit representation, norm estimates, shift identities, and explicit connection to Jacobi polynomials on the real interval [−1, 1] is presented.     

An explicit extension formula of bounded holomorphic functions from analytic varieties to strictly convex domains

We consider a strictly convex domain D ⁿ and m holomorphic functions, φ₁,…, φ_m, in a domain . We set V = {z ε Ω: φ₁(z) = ··· = φ_m(z) = 0}, M = V ∩ D and ∂M = V ∩ ∂D. Under the assumptions that the variety V has no singular point on ∂M and that V meets ∂D transversally we construct an explicit kernel K(ζ, z) defined for ζ ε ∂M and z ε D so that the integral operator Ef(z) = ∝ _{ζ ε ∂M} f(ζ) K(ζ, z) (z ε D), defined for f ε H^∞(M) (using the boundary values f(ζ) for a.e. ζ ε ∂M), is an extension operator, i.e., Ef(z) = f(z) for z ε M and furthermore E is a bounded operator from H^∞ to H^∞(D).     

The Norm and Regularized Trace of the Cauchy Transform

In this paper, the norm of the Cauchy transform C is obtained on the space L ²(D, dμ), where dμ = ω(|z|) dA(z). Also, (for the case ω ≡ 1), the first regularized trace of the operator C* C on L ²(Ω) is obtained. The results are illustrated by examples, with different specific choices of the function ω and the domain Ω.__________Translated from Matematicheskie Zametki, vol. 77, no. 6, 2005, pp. 844–853.Original Russian Text Copyright ©2005 by M. R. Dostanic.     

Müntz-type theorem on the segments emerging from the origin

A necessary and sufficient condition is obtained for the linear span of a system of monomials {z^λ:λΛ} to be dense in the space of all continuous functions defined on the line segments emerging from the origin, where Λ is a set of nonnegative integers. The result is a generalization of the Müntz theorem to the segments emerging from the origin and an extension of the Mergelyan theorem to lacunary polynomials.     

Pseudoprime values of the Fibonacci sequence, polynomials and the Euler function

We show that if α > 1 is any fixed integer, then for a sufficiently large x > 1, the nth Fibonacci number F_n is a base α pseudopfime only for at most (4 + o(1))π(x) of posifive integers n x. The same result holds for Mersenne numbers 2ⁿ — 1 and for one more general class of Lucas sequences. A slight modification of our method also leads to similar results for polynomial sequences f(n), where f ∊ [X]. Finally, we use a different technique to get a much sharper upper bound on the counting fimction of the positive integers n such that φ(n) is a base α pseudoprime, where φ is the Euler function.     

Remark on a double-inequality for the Riemann zeta function

Let ζ be the Riemann zeta function and δ(x)=1/(2^x-1). For all x>0 we have

(1-δ(x))ζ(x)+αδ(x)<ζ(x+1)<(1-δ(x))ζ(x)+βδ(x),