Power-series unification and reversion

In analysis, it is sometimes necessary to unite a pair of power series into a single power series. If x = x(z) = Σ_ja_jz^j and y = y(z) = Σ_jb_jz^j are given power series, then by eliminating the common parameter z, the power-series unification is obtained: y = y(x) = Σ_kc_kx^k, where the coefficients c_k are to be determined in terms of the given power-series coefficients a_j and b_j. In a special case that y = z, the power-series reversion is obtained: z = z(x) = Σ_kd_kx^k, where the coefficients d_k are to be expressed in terms of the original power-series coefficients a_j. In this paper, explicit and recurrent formulas for the desired coefficients are derived. A simple technique of matrix formulation is developed for simplicity of computation. Finally, a complete computer program with a typical example is presented.     

Trace formulas for Hecke operators, Gaussian hypergeometric functions, and the modularity of a threefold

We present simple trace formulas for Hecke operators Tk(p) for all p>3 on Sk(Γ₀(3)) and Sk(Γ₀(9)), the spaces of cusp forms of weight k and levels 3 and 9. These formulas can be expressed in terms of special values of Gaussian hypergeometric series and lend themselves to recursive expressions in terms of traces of Hecke operators on spaces of lower weight. Along the way, we show how to express the traces of Frobenius of a family of elliptic curves equipped with a 3-torsion point as special values of a Gaussian hypergeometric series over Fq, when . As an application, we use these formulas to provide a simple expression for the Fourier coefficients of η⁸(3z), the unique normalized cusp form of weight 4 and level 9, and then show that the number of points on a certain threefold is expressible in terms of these coefficients.     

Restricted partition functions as Bernoulli and Eulerian polynomials of higher order

Explicit expressions for restricted partition function W(s,d^m) and its quasiperiodic components W_j(s,d^m) (called Sylvester waves) for a set of positive integers d^m = {d₁, d₂, ..., d_m} are derived. The formulas are represented in a form of a finite sum over Bernoulli and Eulerian polynomials of higher order with periodic coefficients. A novel recursive relation for the Sylvester waves is established. Application to counting algebraically independent homogeneous polynomial invariants of finite groups is discussed. 2000 Mathematics Subject Classification Primary—11P81; Secondary—11B68, 11B37 The research was supported in part (LGF) by the Gileadi Fellowship program of the Ministry of Absorption of the State of Israel.     

Disk-like Tiles Derived from Complex Bases

For each positive integer k, the radix representation of the complex numbers in the base –k+i gives rise to a lattice self-affine tile T _k in the plane, which consists of all the complex numbers that can be expressed in the form ∑ _j≥1 d _j (–k+i)^–j , where d _j ∈{0, 1, 2, ...,k ²}. We prove that T _k is homeomorphic to the closed unit disk {z∈C:∣z∣ ≤ 1} if and only if k ≠ 2. The first author is supported by Youth Project of Tianyuan Foundation (10226031) and Zhongshan University Promotion Foundation for Young Teachers (34100-1131206); the second author is supported by National Science Foundation (10041005) and Guangdong Province Science Foundation (011221)     

A note on bound for norms of Cauchy–Hankel matrices

We determine bounds for the spectral and ??_p norm of Cauchy–Hankel matrices of the form H_n=[1/(g+h(i+j))]ⁿ_i,j=1≡ ([1/(g+kh)]ⁿ_i,j=1), k=0, 1,…, n –1, where k is defined by i+j=k (mod n). Copyright © 2002 John Wiley & Sons, Ltd.     

Best constants in Korn-Poincaré's inequalities on a slab

We establish the best constants in the Poincaré-type and the trace-type inequalities for the quadratic form $ \lambda ||\,{\rm div}\,{\rm u}\,||_{L^2 }^2 \, + \,2\,\mu \,||\,\,(\nabla {\rm u}\, + \,\nabla {\rm u}^{\rm T})/2\,||_{L^2 }^2 $ which is fundamental in elasticity theory, on the space of H¹ vector fields u on a slab vanishing on one or both of its sides. We similarly calculate those constants for the case of H¹ divergence-free vector fields. Our method, which is fairly general, has another practical application to the quadratic form ∑_j,k(a^jk?_ku, ?_ju)_L² with coefficients a ^jk = a^kj ε C in H¹ scalar functions u on a slab.     

Compactly supported wavelet bases for Sobolev spaces

In this paper we investigate compactly supported wavelet bases for Sobolev spaces. Starting with a pair of compactly supported refinable functions φ and in satisfying a very mild condition, we provide a general principle for constructing a wavelet ψ such that the wavelets ψ_jk:=2^j/2ψ(2^j·−k) ( ) form a Riesz basis for . If, in addition, φ lies in the Sobolev space , then the derivatives 2^j/2ψ^(m)(2^j·−k) ( ) also form a Riesz basis for . Consequently, is a stable wavelet basis for the Sobolev space . The pair of φ and are not required to be biorthogonal or semi-orthogonal. In particular, φ and can be a pair of B-splines. The added flexibility on φ and allows us to construct wavelets with relatively small supports.     

Automatic Smoothing Spline Projection Pursuit

Abstract

A highly flexible nonparametric regression model for predicting a response y given covariates {x_k}^d _k=1 is the projection pursuit regression (PPR) model ? = h(x) = β₀ + Σ_jβ_jf_j(α^T _jx) where the f_j , are general smooth functions with mean 0 and norm 1, and Σ^d _k=1α² _kj=1. The standard PPR algorithm of Friedman and Stuetzle (1981) estimates the smooth functions f_j using the supersmoother nonparametric scatterplot smoother. Friedman's algorithm constructs a model with M _max linear combinations, then prunes back to a simpler model of size M ≤ M _max, where M and M _max are specified by the user. This article discusses an alternative algorithm in which the smooth functions are estimated using smoothing splines. The direction coefficients α_j, the amount of smoothing in each direction, and the number of terms M and M _max are determined to optimize a single generalized cross-validation measure.     

Best Approximation with Linear Constraints: A Model Example

We consider best approximation in L_p( ), 1 ≤ p ≤ ∞, by means of entire functions y of exponential type subject to additional constraints Γ_j(y) = 0, j = 1, ..., K. Here Γ_j are (unbounded) linear functionals of the form Γ_j(y) = Dⁿy(s_j) − ∑ a_kD^ky(s_j) where s_j are fixed points.     

An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines

We give a new and efficient approximation algorithm for scheduling precedence-constrained jobs on machines with different speeds. The problem is as follows. We are given n jobs to be scheduled on a set of m machines. Jobs have processing times and machines have speeds. It takes p_j/s_i units of time for machine i with speed s_i to process job j with processing requirement p_j. Precedence constraints between jobs are given in the form of a partial order. If j k, processing of job k cannot start until job j's execution is completed. The objective is to find a non-preemptive schedule to minimize the makespan of the schedule. Chudak and Shmoys (1997, “Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA),” pp. 581–590) gave an algorithm with an approximation ratio of O(log m), significantly improving the earlier ratio of due to Jaffe (1980, Theoret. Comput. Sci.26, 1–17). Their algorithm is based on solving a linear programming relaxation. Building on some of their ideas, we present a combinatorial algorithm that achieves a similar approximation ratio but runs in O(n³) time. Our algorithm is based on a new and simple lower bound which we believe is of independent interest.     

A generalization of the inversion formulas of systems of power series in systems of implicit functions

Using a multidimensional analog of the logarithmic residue, equations are derived expressing the coefficients of the power series of implicit functionsx _j =_j(w)=_j(w₁,...,w_m), j=1,...,n, defined by the system of equations f_j(w, x)=F_j (w₁,...,w_m:z₁,...,x _n )=0, j=1,...,n,f _j , (0, 0)=0, F_j(0, 0)/z_k=_jk in a neighborhood of the point (0, 0)C _(w,x) ^m+n , in terms of the coefficients of the power series of the functions F_j(w, z), j=1, ..., n. As a corollary, well-known formulas are obtained for the inversion of multiple power series.Translated from Matematicheskie Zametki, Vol. 23, No. 1, pp. 47–54, January, 1978.     

Rook numbers and the normal ordering problem

For an element w in the Weyl algebra generated by D and U with relation DU=UD+1, the normally ordered form is w=∑c_i,jUⁱD^j. We demonstrate that the normal order coefficients c_i,j of a word w are rook numbers on a Ferrers board. We use this interpretation to give a new proof of the rook factorization theorem, which we use to provide an explicit formula for the coefficients c_i,j. We calculate the Weyl binomial coefficients: normal order coefficients of the element (D+U)ⁿ in the Weyl algebra. We extend these results to the q-analogue of the Weyl algebra. We discuss further generalizations using i-rook numbers.     

Construction of polynomials that are orthogonal with respect to a discrete bilinear form

We describe a new algorithm for the computation of recursion coefficients of monic polynomials {p _j } _j ^=0/n that are orthogonal with respect to a discrete bilinear form (f, g) := _k ^=1/m f(x _k )g(x _k )w _k ,m n, with real distinct nodesx _k and real nonvanishing weightsw _k . The algorithm proceeds by applying a judiciously chosen sequence of real or complex Givens rotations to the diagonal matrix diag[x ₁,x ₂, ...,x _m ] in order to determine an orthogonally similar complex symmetric tridiagonal matrixT, from whose entries the recursion coefficients of the monic orthogonal polynomials can easily be computed. Fourier coefficients of given functions can conveniently be computed simultaneously with the recursion coefficients. Our scheme generalizes methods by Elhay et al. [6] based on Givens rotations for updating and downdating polynomials that are orthogonal with respect to a discrete inner product. Our scheme also extends an algorithm for the solution of an inverse eigenvalue problem for real symmetric tridiagonal matrices proposed by Rutishauser [20], Gragg and Harrod [17], and a method for generating orthogonal polynomials based theoron [18]. Computed examples that compare our algorithm with the Stieltjes procedure show the former to generally yield higher accuracy except whenn m. Ifn is sufficiently much smaller thanm, then both the Stieltjes procedure and our algorithm yield accurate results.Research supported in part by the Center for Research on Parallel Computation at Rice University and NSF Grant No. DMS-9002884.     

Expression for restricted partition function through Bernoulli polynomials

Explicit expressions for restricted partition function W(s,d ^m ) and its quasiperiodic components W _j (s,d ^m ) (called Sylvester waves) for a set of positive integers d ^m ={d ₁,d ₂,…,d _m } are derived. The formulas are represented in a form of a finite sum over Bernoulli polynomials of higher order with periodic coefficients.      

A generalization of the Gagliardo inequality

Consider functions u₁, u₂,..., u_n ∈ D(ℝ^k) and assume that we are given a certain set of linear combinations of the form ∑_{i, j} a _ij ^(l) ∂_ju_i. Sufficient conditions in terms of coefficients a _ij ^(l) are indicated under which the norms are controlled in terms of the L¹-norms of these linear combinations. These conditions are mostly transparent if k = 2. The classical Gagliardo inequality corresponds to a single function u₁ = u and the collection of its partial derivatives ∂₁u,..., ∂_ku. Bibliography: 2 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 345, 2007, pp. 120–139.     

The Asymptotic Behavior of a Family of Sequences via Tauberian Theorems

We study the asymptotic behavior of a family of sequences defined by the following nonlinear induction relation c₀ = 1 and c_n ∑^k_{j = 1} r_jc_[n/mj] + ∑^k_{j = k + 1} r_jc_{[(n + 1)^1/mj] − 1} for n ≥ 1, where the r_j are real positive numbers and m_j are integers greater than or equal to 2. Depending on the fact that ∑^k_{j = 1} r_j is greater or lower than 1, we prove that c_n/n^α or c_n/(ln n)^α goes to some finite limit for some explicit α. Our study is based on Tauberian theorems and extends a result of Erdös et al.     

On Spectral Minimal Partitions: A Survey

Given a bounded open set Ω in \mathbbRⁿ{\mathbb{R}^n} (or a Riemannian manifold) and a partition of Ω by k open sets D _j , we can consider the quantity max _j λ(D _j ) where λ(D _j ) is the groundstate energy of the Dirichlet realization of the Laplacian in D _j . If we denote by \mathfrakL_k(W){\mathfrak{L}_k(\Omega)} the infimum over all the k-partitions of max _j λ(D _j ), a minimal (spectral) k-partition is then a partition which realizes the infimum. Although the analysis is rather standard when k = 2 (we find the nodal domains of a second eigenfunction), the analysis of higher k’s becomes non trivial and quite interesting.     

Über die Fourierkoeffizienten der Siegelschen Eisensteinreihen

It is well known that the Fourier coefficients a _n ^k (T) of Siegel's Eisenstein series of degree n and weight k are rational numbers with bounded denominators [14], [15]. In this paper we introduce a number b _n ^k (T), which is equal to a _n ^k (T) in many cases. This number can be computed in an elementary way. From our explicit formulas for b _n ^k (T) we can easily get results about the denominators of the Fourier coefficients a _n ^k (T), which are better than those obtained by Siegel in his difficult paper [15].     

Formulas for sums of powers of integers by functional equations

This paper presents a direct and simple approach to obtaining the formulas forS _k(n)= 1 ^k + 2 ^k + ... +n ^k wheren andk are nonnegative integers. A functional equation is written based on the functional properties ofS _k (n) and several methods of solution are presented. These lead to several recurrence relations for the functions and a simple one-step differential-recurrence relation from which the polynomials can easily be computed successively. Arbitrary constants which arise are (almost) the Bernoulli numbers when evaluated and identities for these modified Bernoulli numbers are obtained. The functional equation for the formulas leads to another functional equation for the generating function for these formulas and this is used to obtain the generating functions for theS _k 's and for the modified Bernoulli numbers. This leads to an explicit representation, not a recurrence relation, for the modified Bernoulli numbers which then yields an explicit formula for eachS _k not depending on the earlier ones. This functional equation approach has been and can be applied to more general types of arithmetic sequences and many other types of combinatorial functions, sequences, and problems.     

Universal robustness of scale‐free networks against cascading edge failures

Considering the effect of the local topology structure of an edge on cascading failures, we investigate the cascading reaction behaviors on scale‐free networks with respect to small edge‐based initial attacks. Adopt the initial load of an edge ij in a network to be L_ij = (k_ik_j)^α[(∑k_a)(∑k_b)]^β with k_i and k_j being the degrees of the nodes connected by the edge ij, where α and β are tunable parameters, governing the strength of the edge initial load, and Γ_i and Γ_j are the sets of neighboring nodes of i and j, respectively. Our aim is to explore the relationship between some parameters and universal robustness characteristics against cascading failures on scale‐free networks. We find by the theoretical analysis that the Baraba'si‐Albert (BA) scale‐free networks can reach the strongest robustness level against cascading failures when α + β = 1, where the robustness is quantified by a transition from normal state to collapse. And the network robustness has a positive correlation with the average degree. We furthermore confirm by the numerical simulations these results.