On a problem of H. Shapiro

Let μ be a real measure on the line such that its Poisson integral M(z) converges and satisfies|M(x+iy)|Ae^−cyα, y→+∞,for some constants A,c>0 and 0<α1. We show that for 1/2<α1 the measure μ must have many sign changes on both positive and negative rays. For 0<α1/2 this is true for at least one of the rays, and not always true for both rays. Asymptotical bounds for the number of sign changes are given which are sharp in some sense.     

On the Positivity of the Fundamental Polynomials for Generalized Hermite–Fejér Interpolation on the Chebyshev Nodes

It is shown that the fundamental polynomials for (0, 1, …, 2m+1) Hermite–Fejér interpolation on the zeros of the Chebyshev polynomials of the first kind are non-negative for −1x1, thereby generalising a well-known property of the original Hermite–Fejér interpolation method. As an application of the result, Korovkin's 10theorem on monotone operators is used to present a new proof that the (0, 1, …, 2m+1) Hermite–Fejér interpolation polynomials offC[−1, 1], based onnChebyshev nodes, converge uniformly tofasn→∞.     

Universal Polynomial Majorants on Convex Bodies

Let K be a convex body in ^d (d2), and denote by B_n(K) the set of all polynomials p_n in ^d of total degree n such that |p_n|1 on K. In this paper we consider the following question: does there exist a p*_nB_n(K) which majorates every element of B_n(K) outside of K? In other words can we find a minimal γ1 and p*_nB_n(K) so that |p_n(x)|γ |p*_n(x)| for every p_nB_n(K) and x ^d\K? We discuss the magnitude of γ and construct the universal majorants p*_n for evenn. It is shown that γ can be 1 only on ellipsoids. Moreover, γ=O(1) on polytopes and has at most polynomial growth with respect to n, in general, for every convex body K.     

A Nonsymmetric Correlation Inequality for Gaussian Measure

Letμbe a Gaussian measure (say, onRⁿ) and letK,LRⁿbe such thatKis convex,Lis a “layer” (i.e.,L={x: ax, ub} for somea, bRanduRⁿ), and the centers of mass (with respect toμ) ofKandLcoincide. Thenμ(K∩L)μ(K)·μ(L). This is motivated by the well-known “positive correlation conjecture” for symmetric sets and a related inequality of Sidak concerning confidence regions for means of multivariate normal distributions. The proof uses the estimateΦ(x)> 1−((8/π)^1/2/(3x+(x²+8)^1/2))e^−x2/2,x>−1, for the (standard) Gaussian cumulative distribution function, which is sharper than the classical inequality of Komatsu.     

Rook-by-rook rook theory: Bijective proofs of rook and hit equivalences

Suppose μ and ν are integer partitions of n, and N>n. It is well known that the Ferrers boards associated to μ and ν are rook-equivalent iff the multisets [μ_i+i:1iN] and [ν_i+i:1iN] are equal. We use the Garsia–Milne involution principle to produce a bijective proof of this theorem in which non-attacking rook placements for μ are explicitly matched with corresponding placements for ν. One byproduct is a direct combinatorial proof that the matrix of Stirling numbers of the first kind is the inverse of the matrix of Stirling numbers of the second kind. We also prove q-analogues and p,q-analogues of these results. We also use the Garsia–Milne involution principle to show that for any two rook boards B and B^′, if B and B^′ are bijectively rook-equivalent, then B and B^′ are bijectively hit-equivalent.     

A pointwise convergence for Sobolev space functions

Let 1<p<∞, and k,m be positive integers such that 0(k−2m)pn. Suppose ΩRⁿ is an open set, and Δ is the Laplacian operator. We will show that there is a sequence of positive constants c_j such that for every f in the Sobolev space W^k,p(Ω), for all xΩ except on a set whose Bessel capacity B_k−2m,p is zero.     

Arithmetic progressions consisting of unlike powers

In this paper we present some new results about unlike powers in arithmetic progression. We prove among other things that for given k 4 and L 3 there are only finitely many arithmetic progressions of the form with x_i , gcd(x₀, x_l) = 1 and 2 l_i L for i = 0, 1, …, k − 1. Furthermore, we show that, for L = 3, the progression (1, 1,…, 1) is the only such progression up to sign. Our proofs involve some well-known theorems of Faltings [9], Darmon and Granville [6] as well as Chabauty's method applied to superelliptic curves.     

On groups with conjugacy classes of distinct sizes

A finite group G is called an ah-group if any two distinct conjugacy classes of G have distinct cardinality. We show that if G is an ah-group, then the non-abelian socle of G is isomorphic to one of the following:

1. , for 1a5, a≠2.

2. A₈.

3. PSL(3,4)^e, for 1e10.

4. A₅×PSL(3,4)^e, for 1e10.

Based on this result, we virtually show that if G is an ah-group with π(G) 2,3,5,7 , then F(G)≠1, or equivalently, that G has an abelian normal subgroup.In addition, we show that if G is an ah-group of minimal size which is not isomorphic to S₃, then the non-abelian socle of G is either trivial or isomorphic to one of the following:

1. , for 3a5.

2. PSL(3,4)^e, for 1e10.

Our research lead us to interesting results related to transitivity and homogeneousity in permutation groups, and to subgroups of wreath products of form Z₂S_n. These results are of independent interest and are located in appendices for greater autonomy.     

Hankel determinants and orthogonal polynomials

We develop a general context for the computation of the determinant of a Hankel matrix H_n = (α_i+j)0i,jn, assuming some suitable conditions for the exponential (or ordinary) generating function of the sequence (α_n)_n0. Several well-known particular cases are thus derived in a unified way.     

On Equivalence of Moduli of Smoothness

It is known that iffW^k_p, thenω_m(f, t)_ptω_m−1(f′, t)_p…. Its inverse with any constants independent offis not true in general. Hu and Yu proved that the inverse holds true for splinesSwith equally spaced knots, thusω_m(S, t)_ptω_m−1(S′, t)_pt²ω_m−2(S″, t)_p…. In this paper, we extend their results to splines with any given knot sequence, and further to principal shift-invariant spaces and wavelets under certain conditions. Applications are given at the end of the paper.     

The maximum spectral radius of -free graphs of given order and size

Suppose that G is a graph with n vertices and m edges, and let μ be the spectral radius of its adjacency matrix.Recently we showed that if G has no 4-cycle, then μ²-μn-1, with equality if and only if G is the friendship graph.Here we prove that if m9 and G has no 4-cycle, then μ²m, with equality if G is a star. For 4m8 this assertion fails.     

On the chromatic number of random graphs

In this paper we consider the classical Erdős–Rényi model of random graphs G_n,p. We show that for p=p(n)n^−3/4−δ, for any fixed δ>0, the chromatic number χ(G_n,p) is a.a.s. ℓ, ℓ+1, or ℓ+2, where ℓ is the maximum integer satisfying 2(ℓ−1)log(ℓ−1)p(n−1).     

Group actions and invariants in algebras of generic matrices

We show that the fixed elements for the natural GL_m-action on the universal division algebra UD(m,n) of m generic n×n-matrices form a division subalgebra of degree n, assuming n3 and 2mn²−2. This allows us to describe the asymptotic behavior of the dimension of the space of SL_m-invariant homogeneous central polynomials p(X₁,…,X_m) for n×n-matrices. Here the base field is assumed to be of characteristic zero.     

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.     

disjoint cycles containing specified independent vertices

Let k1 be an integer and G be a graph of order n3k satisfying the condition that σ₂(G)n+k-1. Let v₁,…,v_k be k independent vertices of G, and suppose that G has k vertex-disjoint triangles C₁,…,C_k with v_iV(C_i) for all 1ik.Then G has k vertex-disjoint cycles such that

(i) for all 1ik.

(ii) , and

(iii) At least k-1 of the k cycles are triangles.

The condition of degree sum σ₂(G)n+k-1 is sharp.

On Weighted Mean Convergence of Lagrange Interpolation for General Arrays

For n1, let {x_jn}_j=1ⁿ be n distinct points and let L_n[·] denote the corresponding Lagrange Interpolation operator. Let W : →[0,∞). What conditions on the array {x_jn}_{1jn, n1} ensure the existence of p>0 such

Full-size image

for every continuous f : → with suitably restricted growth, and some “weighting factor” φ^b? We obtain a necessary and sufficient condition for such a p to exist. The result is the weighted analogue of our earlier work for interpolation arrays contained in a compact set.     

On sharp Burkholder–Rosenthal-type inequalities for infinite-degree U-statistics

In this paper, we present a method that allows one to obtain a number of sharp inequalities for expectations of functions of infinite-degree U-statistics. Using the approach, we prove, in particular, the following result: Let D be the class of functions f :R₊→R₊ such that the function f(x+z)−f(x) is concave in xR₊ for all zR₊. Then the following estimate holds: for all fD and all U-statistics ∑_1i1<<ilnY_i1,…,il(X_i1,…,X_il) with nonnegative kernels Y_i1,…,il :R^l→R₊, 1i_kn; i_r≠i_s, r≠s; k,r,s=1,…,l; l=0,…,m, in independent r.v.'s X₁,…,X_n. Similar inequality holds for sums of decoupled U-statistics. The class D is quite wide and includes all nonnegative twice differentiable functions f such that the function f″(x) is nonincreasing in x>0, and, in particular, the power functions f(x)=x^t, 1<t2; the power functions multiplied by logarithm f(x)= (x+x₀)^t ln(x+x₀), 1<t<2, x₀max(e^{(3t2−6t+2)/(t(t−1)(2−t))},1); and the entropy-type functions f(x)=(x+x₀)ln(x+x₀), x₀1. As an application of the results, we determine the best constants in Burkholder–Rosenthal-type inequalities for sums of U-statistics and prove new decoupling inequalities for those objects. The results obtained in the paper are, to our knowledge, the first known results on the best constants in sharp moment estimates for U-statistics of a general type.     

Delay optimization of linear depth boolean circuits with prescribed input arrival times

We consider boolean circuits C over the basis Ω={,} with inputs x₁, x₂,…,x_n for which arrival times are given. For 1in we define the delay of x_i in C as the sum of t_i and the number of gates on a longest directed path in C starting at x_i. The delay of C is defined as the maximum delay of an input.Given a function of the form

f(x₁,x₂,…,x_n)=g_n−1(g_n−2(…g₃(g₂(g₁(x₁,x₂),x₃),x₄)…,x_n−1),x_n)