On a cardinal group invariant related to decompositions of Abelian groups

For each Abelian groupG, a cardinal invariant χ(G) is introduced and its properties are studied. In the special caseG = ℤ ⁿ , the cardinalχ(ℤ ⁿ ) is equal to the minimal cardinality of an essential subset of ℤ ⁿ , i.e., a of a subsetA ⊂ ℤ ⁿ such that, for any coloring of the group ℤ ⁿ inn colors, there exists an infinite one-color subset that is symmetric with respect to some pointα ofA. The estimaten( ^{n +} l)/2 ≤χ(ℤ ⁿ ) < 2n is proved for alln and the relationχ(ℤ ⁿ ) =n(n + 1)/2 forn ≤ 3. The structure of essential subsets of cardinalityχ(ℤ ⁿ ) in ℤ ⁿ is completely described forn ≤ 3. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 341–350, September, 1998.     

On the distribution of reducible polynomials

Let ℛ _n (t) denote the set of all reducible polynomials p(X) over ℤ with degree n ≥ 2 and height ≤ t. We determine the true order of magnitude of the cardinality |ℛ _n (t)| of the set ℛ _n (t) by showing that, as t → ∞, t ² log t ≪ |ℛ₂(t)| ≪ t ² log t and t ⁿ ≪ |ℛ _n (t)| ≪ t _n for every fixed n ≥ 3. Further, for 1 < n/2 < k < n fixed let ℛ _k,n (t) ⊂ ℛ _n (t) such that p(X) ∈ ℛ _k,n (t) if and only if p(X) has an irreducible factor in ℤ[X] of degree k. Then, as t → ∞, we always have t ^k+1 ≪ |ℛ _k,n (t)| ≪ t ^k+1 and hence |ℛ _n−1,n (t)| ≫ |ℛ _n (t)| so that ℛ _n−1,n (t) is the dominating subclass of ℛ _n (t) since we can show that |ℛ _n (t)∖ℛ _n−1,n (t)| ≪ t ⁿ⁻¹(log t)².On the contrary, if R _n ^s (t) is the total number of all polynomials in ℛ _n (t) which split completely into linear factors over ℤ, then t ²(log t) ⁿ⁻¹ ≪ R _n ^s (t) ≪ t ² (log t) ⁿ⁻¹ (t → ∞) for every fixed n ≥ 2.      

Moments of the maximum of normed partial sums of ρ^--mixing random variables

Let {Xn,n ≥ 1} be a sequence of identically distributed ρ^--mixing random variables and set Sn =∑i^n=1 Xi,n ≥ 1,the suffcient and necessary conditions for the existence of moments of supn≥1 ｜Sn/n^1/r｜^p（0 〈 r 〈 2,p 〉 0） are given,which are the same as that in the independent case.     

Effect of the initial estimator on the asymptotic behavior of one-step M-estimator

For a general (real) parameter, let M _nbe the M-estimator and M _n ⁽¹⁾ be its one-step version (based on a suitable initial estimator M _n ⁽⁰⁾). It is known that, under certain regularity conditions, n(M _n ⁽¹⁾-M _n)=O _p(1). The asymptotic distribution of n(M _n ⁽¹⁾-M _n) is studied; it is typically non-normal and it reveals the role of the initial estimator M _n ⁽⁰⁾.Work of this author was partially supported by the Office of Naval Research, Contract No. N00014-83-K-0387     

A Theorem on Discrete,Torsion Free Subgroups of Isom H <Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Let H ⁿ be the hyperbolic n-space with n⩾ 2. Suppose that Γ H ⁿ is a discrete, torsion free subgroup and a is a point in the domain of discontinuity Ω (Γ). Let p be the projection map from H ⁿ to the quotient manifold M=H ⁿ/Γ. In this paper we prove that there exists an open neighborhood U of a in H ⁿ∪ Ω (Γ) such that p is an isometry on U∩ H ⁿ.Mathematics Subject Classification (2000). primary: 51M10; secondary: 22E40, 57M50.     

Distribution of a certain partition function modulo powers of primes

In this paper, we study a certain partition function a(n) defined by Σ _n≥0 a(n)q ⁿ := Π _n=1(1 − q ⁿ )⁻¹(1 − q ²ⁿ )⁻¹. We prove that given a positive integer j ≥ 1 and a prime m ≥ 5, there are infinitely many congruences of the type a(An + B) ≡ 0 (mod m ^j ). This work is inspired by Ono’s ground breaking result in the study of the distribution of the partition function p(n).     

Decrease rate of the probabilities ofε-deviations for the means of stationary processes

The asymptotic behavior asn → ∞ of the normed sumsσn =n ⁻¹ Σ _k ⁼⁰ⁿ⁻¹ Xk for a stationary processX = (X _n ,n ∈ ℤ) is studied. For a fixedε > 0, upper estimates for P(sup _k≥n |σ _k | ≥ε) asn → ∞ are obtained. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 366–372, September, 1998.     

On asymptotics of large Haar distributed unitary matrices

Let U _n be an n × n Haar unitary matrix. In this paper, the asymptotic normality and independence of Tr U _n , Tr U _n ² ,..., Tr U _n ^k are shown by using elementary methods. More generally, it is shown that the renormalized truncated Haar unitaries converge to a Gaussian random matrix in distribution. This revised version was published online in August 2006 with corrections to the Cover Date.     

Polynomial interpolation and sums of powers of integers

In this note, we revisit the problem of polynomial interpolation and explicitly construct two polynomials in n of degree k + 1, P_k(n) and Q_k(n), such that P_k(n) = Q_k(n) = f_k(n) for n = 1, 2,…?, k, where f_k(1), f_k(2),…?, f_k(k) are k arbitrarily chosen (real or complex) values. Then, we focus on the case that f_k(n) is given by the sum of powers of the first n positive integers S_k(n) = 1^k + 2^k + ??? + n^k, and show that S_k(n) admits the polynomial representations S_k(n) = P_k(n) and S_k(n) = Q_k(n) for all n = 1, 2,…?, and k ≥ 1, where the first representation involves the Eulerian numbers, and the second one the Stirling numbers of the second kind. Finally, we consider yet another polynomial formula for S_k(n) alternative to the well-known formula of Bernoulli.     

On the chromatic polynomial of a graph

Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()^α≤≤ () ^{n −ω}. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour number μ(G) of G: n− (n−ω)() ^{n −ω}≤μ(G)≤n−α() ^α. Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002     

NON-EMPTY CROSS-2-INTERSECTING FAMILIES OF SUBSETS

Let Cdenote the set of all k-subests of an n-set.Assume Alohtain in Ca,and A lohtain in (A,B) is called a cross-2-intersecting family if |A B≥2 for and A∈A,B∈B.In this paper,the best upper bounds of the cardinalities for non-empty cross-2-intersecting familles of a-and b-subsets are obtained for some a and b,A new proof for a Frankl-Tokushige theorem[6] is also given.     

Finite p-Groups in Which the Number of Subgroups of Possible Order is Less Than or Equal to $p^3 $

In this paper, groups of order pn in which the number of subgroups of possible order is less than or equal to p3 are classified. It turns out that if p 2, n ≥ 5, then the classification of groups of order pn in which the number of subgroups of possible order is less than or equal to p3 and the classification of groups of order pn with a cyclic subgroup of index p2 are the same.     

Computation of certain infinite series of the form for arbitrary real-valued k

We provide a general method from which one may obtain more arbitrary closed form solutions for infinite series of the form ∑f(n)n^k, for and sufficiently well-behaved f(n). We illustrate the methods for the special case of f(n)=aⁿ/n!, obtaining generalizations to the Bell numbers and polynomials.     

Stability of Doob—Meyer Decomposition Under Extended Convergence

In what follows, we consider the relation between Aldous‘s extended convergence and weak convergence of filtrations. We prove that, for a sequence (X^n) of Ft^n )-special semimartingales, with canonical decomposition X^n =M^n A^n, if the extended convergence (X^n,F.^n)→(X,T. ) holds with a quasi-left continuous (Ft)-special semimartingale X = M A, then, under an additional assumption of uniform integrability,we get the convergence in probability under the Skorokhod topology: M^n↑P→M and A^n↑P→ A.     

Strong Approximation Theorems for Sums of Random Variables when Extreme Terms are Excluded

Let {X _n ;n≥1} be a sequence of i.i.d. random variables and let X ^(r) _n = X _j if |X _j | is the r-th maximum of |X ₁|, ..., |X _n |. Let S _n = X ₁+⋯+X _n and ^(r) S _n = S _n −(X ⁽¹⁾ _n +⋯+X ^(r) _n ). Sufficient and necessary conditions for ^(r) S _n approximating to sums of independent normal random variables are obtained. Via approximation results, the convergence rates of the strong law of large numbers for ^(r) S _n are studied. Received March 22, 1999, Revised November 6, 2000, Accepted March 16, 2001     

Distribution of Cardinalities of Row Spaces of Boolean Matrices of Order n

Let R(A) denote the row space of a Boolean matrix A of order n. We show that if n 7, then the cardinality |R(A)| (2^n–1 - 2^n–5, 2^n–1 - 2^n–6) U (2^n–1 - 2^n–6, 2^n–1). This result confirms a conjecture in [1].AMS Subject Classification (1991): 05B20 06E05 15A36Support partially by the Postdoctoral Science Foundation of China.Dedicated to Professor Chao Ko on the occasion of his 90th birthday     

Structure of augmentation quotients of finite homocyclic abelian groups

Let G be a finite abelian group and its Sylow p-subgroup a direct product of copies of a cyclic group of order p~r,i.e.,a finite homocyclic abelian group.LetΔ~n (G) denote the n-th power of the augmentation idealΔ(G) of the integral group ring ZG.The paper gives an explicit structure of the consecutive quotient group Q_n(G)=Δ~n(G)/Δ~(n 1)(G) for any natural number n and as a consequence settles a problem of Karpilovsky for this particular class of finite abelian groups.     

Estimates for the Rapid Decay of Concentration Functions of n-Fold Convolutions

We estimate the concentration functions of n-fold convolutions of one-dimensional probability measures. The Kolmogorov–Rogozin inequality implies that for nondegenerate distributions these functions decrease at least as O(n ^–1/2). On the other hand, Esseen⁽³⁾ has shown that this rate is o(n ^–1/2) iff the distribution has an infinite second moment. This statement was sharpened by Morozova.⁽⁹⁾ Theorem 1 of this paper provides an improvement of Morozova's result. Moreover, we present more general estimates which imply the rates o(n ^–1/2).     

The Nicolas and Robin inequalities with sums of two squares

In 1984, G. Robin proved that the Riemann hypothesis is true if and only if the Robin inequality σ(n) < e ^γ n log log n holds for every integer n > 5040, where σ(n) is the sum of divisors function, and γ is the Euler–Mascheroni constant. We exhibit a broad class of subsets of the natural numbers such that the Robin inequality holds for all but finitely many . As a special case, we determine the finitely many numbers of the form n = a ² + b ² that do not satisfy the Robin inequality. In fact, we prove our assertions with the Nicolas inequality n/φ(n) < e ^γ log log n; since σ(n)/n < n/φ(n) for n > 1 our results for the Robin inequality follow at once.      

A new implementation of an algorithm for the optimal assignment problem: An improved version of Munkres' algorithm

Existing implementations of Munkres' algorithm for the optimal assignment problem are shown to requireO(n ⁴) time in the worstn×n case. A new implementation is presented which runs in worst-case timeO(n ³) and compares favorably in performance with the algorithm of Edmonds and Karp for this problem.The results of this paper were obtained by the author while at the Department of Computer Science, Cornell University. This work was supported in part by a Vanderbilt University Research Council Grant.