Extension of the Kibble-Slepian formula for Hermite polynomials using boson operator methods

The Kibble-Slepian formula expresses the exponential of a quadratic form Q(x) = x^tS(I + S)^?1x, S^t = S, in n variables x = col(x₁,…, x_n) as a series of products of Hermite polynomials, thus generalizing Mehler's formula. This extension is restricted, however, to the case where the diagonal elements of the symmetric matrix S are all unity. We derive the general formula for an arbitrary symmetric matrix S, where I + S is positive definite, using techniques familiar from the boson operator treatment of the harmonic oscillator in quantum mechanics.     

Nonsingularity of least common multiple matrices on gcd-closed sets

Let n be a positive integer. Let S={x₁,…,x_n} be a set of n distinct positive integers. The least common multiple (LCM) matrix on S, denoted by [S], is defined to be the n×n matrix whose (i,j)-entry is the least common multiple [x_i,x_j] of x_i and x_j. The set S is said to be gcd-closed if for any x_i,x_j∈S,(x_i,x_j)∈S. For an integer m>1, let ω(m) denote the number of distinct prime factors of m. Define ω(1)=0. In 1997, Qi Sun conjectured that if S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. In this paper, we settle completely Sun's conjecture. We show the following result: (i). If S is a gcd-closed set satisfying max_x∈S{ω(x)}?2, then the LCM matrix [S] is nonsingular. Namely, Sun's conjecture is true; (ii). For each integer r?3, there exists a gcd-closed set S satisfying max_x∈S{ω(x)}=r, such that the LCM matrix [S] is singular.     

The characterization of sort sequences

A sort sequenceS _n is a sequence of all unordered pairs of indices inI _n = 1, 2, ...,n. With a sort sequenceS _n, we associate a sorting algorithmA(S _n) to sort input setX = x ₁, x₂, ..., x_n as follows. An execution of the algorithm performs pairwise comparisons of elements in the input setX as defined by the sort sequenceS _n, except that the comparisons whose outcomes can be inferred from the outcomes of the previous comparisons are not performed. Let χ(S _n) denote the average number of comparisons required by the algorithmA(S _n assuming all input orderings are equally likely. Let χ*(n) and χ°(n) denote the minimum and maximum values, respectively, of χ(S _n) over all sort sequencesS _n. Exact determination of χ*(n), χO(n) and associated extremal sort sequences seems difficult. Here, we obtain bounds on χ*(n) and χO(n).     

Divisibility properties of power LCM matrices by power GCD matrices on gcd-closed sets

Let e and n be positive integers and S={x₁,…,x_n} a set of n distinct positive integers. For x∈S, define . The n×n matrix whose (i,j)-entry is the eth power (x_i,x_j)^e of the greatest common divisor of x_i and x_j is called the eth power GCD matrix on S, denoted by (S^e). Similarly we can define the eth power LCM matrix [S^e]. Bourque and Ligh showed that (S)∣[S] holds in the ring of n×n matrices over the integers if S is factor closed. Hong showed that for any gcd-closed set S with |S|≤3, (S)∣[S]. Meanwhile Hong proved that there is a gcd-closed set S with max_x∈S{|G_S(x)|}=2 such that (S)?[S]. In this paper, we introduce a new method to study systematically the divisibility for the case max_x∈S{|G_S(x)|}≤2. We give a new proof of Hong’s conjecture and obtain necessary and sufficient conditions on the gcd-closed set S with max_x∈S{|G_S(x)|}=2 such that (S^e)|[S^e]. This partially solves an open question raised by Hong. Furthermore, we show that such factorization holds if S is a gcd-closed set such that each element is a prime power or the product of two distinct primes, and in particular if S is a gcd-closed set with every element less than 12.     

PCR algorithm for parallel computing the solution of the general restricted linear equations

In this paper we present a parallel algorithm for parallel computing the solution of the general restricted linear equations Ax=b,x∈T, where T is a subspace of ? ⁿ and b∈AT. By this algorithm the solution x=A _T,S ⁽²⁾ b is obtained in n(log?₂ m+log?₂(n?s+1)+7)+log?₂ m+1 steps with P=mn processors when m≥2(n?1) and with P=2n(n?1) processors otherwise.     

On the parity of the partition function

Let N be the set of all positive integers and D a subset of N. Let p(D,n) be the number of partitions of n with parts in D and let |D(x)| denote the number of elements of D not exceeding x. It is proved that if D is an infinite subset of N such that p(D,n) is even for all n?n₀, then |D(x)|?logx/log2−logn₀/log2. Moreover, if D is an infinite subset of N such that p(D,n) is odd for all n?n₀ and , then |D(x)|?logx/log2−logn₀/log2. These lower bounds are essentially the best possible.     

Richardson's iteration for nonsymmetric matrices

To solve the linear N×N system (1) Ax=a for any nonsingular matrix A, Richardson's iteration (2) x_j+1=x_j-α_j(Ax_j-a), j=1,2,…,n, which is applied in a cyclic manner with cycle length n is investigated, where the α_j are free parameters. The objective is to minimize the error |x_n+1-x|, where x is the solution of (1). If the spectrum of A is known to lie in a compact set S, one is led to the Chebyshev-type approximation problem (3) min_p-1∈Vnmax_z∈S|p(z)|, where V_n is the linear span of z,z²,…,zⁿ. If p solves (3), then the reciprocals of the zeros of p are optimal iteration parameters α_j. It is shown that for a real problem (1) the iteration (2) can be carried out with real arithmetic alone, even when there are complex α_j. The stationary case n=1 is solved completely, i.e., for all compact sets S the problem (3) is solved explicitly. As a consequence, the converging stationary iteration processes can be characterized. For arbitrary closed disks S the problem (3) can be solved for all n∈$\text{N}$, and a simple proof is provided. The lemniscates associated with S are introduced. They appear as an important tool for studying the stability of the iteration (2).     

On a problem of Katona on minimal separating systems

Let S be an n-element set. In this paper, we determine the smallest number f(n) for which there exists a family of subsets of S{A₁,A₂,…,A_f(n)} with the following property: Given any two elements x, y ∈ S (x ≠ y), there exist k, l such that A_k ∩ A_l= ?, and x ∈ A_k, y ∈ A_l. In particular it is shown that f(n)= 3 log₃n when n is a power of 3.     

Ideals generated by reverse lexicographic segments

Let k be a field, and let S = k[x ₁, …, x _n ] be the polynomial ring in x ₁, …, x _n with coefficients in the field k. We study ideals of S which are generated by reverse lexicographic segments of monomials of S. An ideal generated by a reverse lexicographic segment is called a completely reverse lexicographic segment ideal if all iterated shadows of the set of generators are reverse lexicographic segments. We characterize all completely reverse lexicographic segment ideals of S and determine conditions under which they have a linear resolution.     

Overdetermined linear systems satisfying nonnegativity constraints

Let A be a nonnegative m × n matrix, and let b be a nonnegative vector of dimension m. Also, let S be a subspace of $\text{R}$ⁿ such that if P_S is the orthogonal projector onto S, then P_S ? 0. A necessary condition is given for the matrix A to satisfy the following property: For all b ? 0, if min[boxV]b ? Ax[boxV] is attained at x = x₀, then x₀ ? 0 and x₀ ? S. It is also shown that if a nonnegative matrix A has a nonnegative generalized inverse, then any submatrix of A also possesses a nonnegative generalized inverse.     

Numerical solution of a class of random boundary value problems

This paper deals with the nonlinear two point boundary value problem y″ = f(x, y, y′, R₁,…, R_n), x₀ < x < x_fS₁y(x₀) + S₂y′(x₀) = S₃, S₄y(x_f) + S₅y′(x_f) = S₆ where R₁,…, R_n, S₁,…, S₆ are bounded continuous random variables. An approximate probability distribution function for y(x) is constructed by numerical integration of a set of related deterministic problems. Two distinct methods are described, and in each case convergence of the approximate distribution function to the actual distribution function is established. Primary attention is placed on problems with two random variables, but various generalizations are noted. As an example, a nonlinear one-dimensional heat conduction problem containing one or two random variables is studied in some detail.     

More on the generalized macaulay theorem — II

Let k₁ ? k₂? ? ? k_n be given positive integers and let S denote the set of vectors x = (x₁, x₂, … ,x_n) with integer components satisfying 0 ? x₁ ? k_ni = 1, 2, …, n. Let X be a subset of S (l)X denotes the subset of X consisting of vectors with component sum l; F(m, X) denotes the lexicographically first m vectors of X; ?X denotes the set of vectors in S obtainable by subtracting 1 from a component of a vector in X; |X| is the number of vectors in X. In this paper it is shown that |?F(e, (l)S)| is an increasing function of l for fixed e and is a subadditive function of e for fixed l.     

A note on hypercube partitions

Two methods of partitioning an n-dimensional hypercube are considered. In the first method, referred to as the Stirling partitioning, we define l-dimensional partitions (l-partitions) which are defined in the 2-dimensional case by x₁ < x₂, x₂ < x₁, and x₂ = x₁. We show that (n ? k)-partitions are enumerated by the numbers T_n^k = (n ? k)! S_n^n?k, where S_n^n?k is the Stirling number of the second kind. In the second method, referred to as the Eulerian partitioning, we define k-boundary n-partitions as unions of n-partitions with their (n ?1)-through(n ? k)-partition boundaries. In the 2-dimensional case the 0 and 1 boundary 2-partitions are x₁ < x₂, x₂ ? x₁. We show that k boundary n-partitions are enumerated by the Eulerian numbers E_n^k. We apply these results to several combinatorial identities.     

Asymptotic properties of least squares estimators for discrete compound distributions

Let (X, Λ) be a pair of random variables, where Λ is an Ω (a compact subset of the real line) valued random variable with the density functiong(Θ: α) andX is a real-valued random variable whose conditional probability function given Λ=Θ is P {X=x|Θ} withx=x ₀, x₁, …. Based onn independent observations ofX, x ⁽ⁿ⁾, we are to estimate the true (unknown) parameter vectorα=(α ₁, α₂, ...,α_m) of the probability function ofX, P_α(X=∫_ΩP{X=x|Θ}g(Θ:α)dΘ. A least squares estimator of α is any vector \(\hat \alpha \left( {X^{\left( n \right)} } \right)\) which minimizes $$n^{ - 1} \sum\limits_{i = 1}^n {\left( {P_\alpha \left( {x_i } \right) - fn\left( {x_i } \right)} \right)^2 } $$ wherex ⁽ⁿ⁾=(x₁, x₂,…,x _n) is a random sample ofX andf _n(x_i)=[number ofx _i inx ⁽ⁿ⁾]/n. It is shown that the least squares estimators exist as a unique solution of the normal equations for all sufficiently large sample size (n) and the Gauss-Newton iteration method of obtaining the estimator is numerically stable. The least squares estimators converge to the true values at the rate of \(O\left( {\sqrt {2\log \left( {{{\log n} \mathord{\left/ {\vphantom {{\log n} n}} \right. \kern-0em} n}} \right)} } \right)\) with probability one, and has the asymptotically normal distribution.     

Additive energy of dense sets of primes and monochromatic sums

When K ≥ 1 is an integer and S is a set of prime numbers in the interval ( \(\tfrac{N} {2}\) , N] with |S| ≥ π*(N)/K, where π*(N) is the number of primes in this interval, we obtain an upper bound for the additive energy of S, which is the number of quadruples (x ₁, x ₂, x ₃, x ₄) in S ⁴ satisfying x ₁+x ₂ = x ₃+x ₄. We obtain this bound by a variant of a method of Ramaré and I. Ruzsa. Taken together with an argument due to N. Hegyvári and F. Hennecart, this bound implies that when the sequence of prime numbers is coloured with K colours, every sufficiently large integer can be written as a sum of no more than CK log log 4K prime numbers, all of the same colour, where C is an absolute constant. This assertion is optimal up to the value of C and answers a question of A. Sárközy.     

Note on bounds for multiplicities

Let S=K[x₁,…,x_n] be a polynomial ring and R=S/I be a graded K-algebra where I⊂S is a graded ideal. Herzog, Huneke and Srinivasan have conjectured that the multiplicity of R is bounded above by a function of the maximal shifts in the minimal graded free resolution of R over S. We prove the conjecture in the case that codim(R)=2 which generalizes results in (J. Pure Appl. Algebra 182 (2003) 201; Trans. Amer. Math. Soc. 350 (1998) 2879). We also give a proof for the bound in the case in which I is componentwise linear. For example, stable and squarefree stable ideals belong to this class of ideals.     

On the minimal positive homothetic image of a simplex containing a convex body

Let C be a convex body, and let S be a nondegenerate simplex in ? ⁿ . It is proved that the minimal coefficientσ > 0 for which the translate of σS contains C is $$\sum\limits_{j = 1}^{n + 1} {\mathop {\max \left( { - \lambda _j \left( x \right)} \right) + 1,}\limits_{x \in C} }$$ where λ ₁(x), ..., λ _n +1(x) are the barycentric coordinates of the point x ∈ ? ⁿ with respect to S. In the case C = [0, 1] ⁿ , this quantity is reduced to the form Σ _i=1 ⁿ 1/d _i (S), where d _i (S) is the ith axial diameter of S, i.e., the maximal length of the segment from S parallel to the ith coordinate axis.     

Divisibility properties of power GCD matrices and power LCM matrices

Let a,b and n be positive integers and the set S={x₁,…,x_n} of n distinct positive integers be a divisor chain (i.e. there exists a permutation σ on {1,…,n} such that x_σ(1)|…|x_σ(n)). In this paper, we show that if a|b, then the ath power GCD matrix (S^a) having the ath power (x_i,x_j)^a of the greatest common divisor of x_i and x_j as its i,j-entry divides the bth power GCD matrix (S^b) in the ring M_n(Z) of n×n matrices over integers. We show also that if a?b and n?2, then the ath power GCD matrix (S^a) does not divide the bth power GCD matrix (S^b) in the ring M_n(Z). Similar results are also established for the power LCM matrices.     

A note on matrix subalgebras containing a full Jordan block

Let A be a subalgebra of the full matrix algebra M_n(F), and suppose J∈A, where J is the Jordan block corresponding to xⁿ. Let $\text{S}$ be a set of generators of A. It is shown that the graph of $\text{S}$ determines whether A is the full matrix algebra M_n(F).     

On maximal antichains consisting of sets and their complements

Let 1 ? k₁ ? k₂ ? … ? k_n be integers and let S denote the set of all vectors x = (x₁, x₂, …, x_n) with integral coordinates satisfying 0 ? x_i ? k_i, i = 1, 2, …, n. The complement of x is (k₁ ? x₁, k₂ ? x₂, …, k_n ? x_n) and a subset X of S is an antichain provided that for any two distinct elements x, y of X, the inequalities x_i ? y_i, i = 1, 2, …, n, do not all hold. We determine an LYM inequality and the maximal cardinality of an antichain consisting of vectors and its complements. Also a generalization of the Erdös-Ko-Rado theorem is given.