On the spectral norms of Cauchy–Toeplitz and Cauchy–Hankel matrices

In this study, we have found upper and lower bounds for the spectral norm of Cauchy–Toeplitz and Cauchy–Hankel matrices in the forms T_n=[1/(a+(i−j)b)]ⁿ_i,j=1, H_n=[1/(a+(i+j)b)]ⁿ_i,j=1.     

Generalized Hadamard Matrices

The paper studies a generalized Hadamard matrix H = (g _{i j}) of order n with entries gi j from a group G of order n. We assume that H satisfies: (i) For m k, G = {g _{m i} g k i ^-1 i = 1,...., n} (ii) g _1i = g _i1 = 1 for each i; (iii) g _ij ^-1 = g _ji for all i, j. Conditions (i) and (ii) occur whenever G is a(P, L) -transitivity for a projective plane of order n. Condition (iii) holds in the case that H affords a symmetric incidence matrix for the plane. The paper proves that G must be a 2-group and extends previous work to the case that n is a square.     

A self-normalized Erd s—Rényi type strong law of large numbers

The original Erd s—Rényi theorem states that max_0kn∑^k+[clogn]_i=k+1X_i/[clogn]→α(c),c>0, almost surely for i.i.d. random variables {X_n, n1} with mean zero and finite moment generating function in a neighbourhood of zero. The latter condition is also necessary for the Erd s—Rényi theorem, and the function α(c) uniquely determines the distribution function of X₁. We prove that if the normalizing constant [c log n] is replaced by the random variable ∑^k+[clogn]_i=k+1(X²_i+1), then a corresponding result remains true under assuming only the exist first moment, or that the underlying distribution is symmetric.     

Disjoint skolem sequences and related disjoint structures

A Skolem sequence of order n is a sequence S = (s₁, s₂…, s²ⁿ) of 2n integers satisfying the following conditions: (1) for every k ∈ {1, 2,… n} there exist exactly two elements s_i,S_j such that S_i = S_j = k; (2) If s_i = s_j = k,i < j then j ? i = k. In this article we show the existence of disjoint Skolem, disjoint hooked Skolem, and disjoint near-Skolem sequences. Then we apply these concepts to the existence problems of disjoint cyclic Steiner and Mendelsohn triple systems and the existence of disjoint 1-covering designs. © 1993 John Wiley & Sons, Inc.     

Utilizing Shelve Slots: Sufficiency Conditions for Some Easy Instances of Hard Problems

In this paper we present a minimal set of conditions sufficient to assure the existence of a solution to a system of nonnegative linear diophantine equations. More specifically, suppose we are given a finite item set U = {u₁, u₂, . . . , u_k} together with a "size" v_i ≡ v(u_i) ∈ Z⁺, such that v_i ≠ v_j for i ≠ j, a "frequency" a_i ≡ a(u_i) ∈ Z⁺, and a positive integer (shelf length) L ∈ Z⁺ with the following conditions: (i) L = ∏ⁿ_j=1p_j(p_j ∈ Z⁺ ∀j, p_j ≠ p_l for j ≠ l) and v_i = ∏ _j∈Aip_j, A_i ⊆ {l, 2, . . . , n} for i = 1, . . . , n; (ii) (A_i\{⋂^k_j=1A_j}) ∩ (A_l\{⋂^k_j=1A_j}) = ⊘∀i ≠ l. Note that v_i|L (divides L) for each i. If for a given m ∈ Z⁺, ∑ⁿ_i=1a_iv_i = mL (i.e., the total size of all the items equals the total length of the shelf space), we prove that conditions (i) and (ii) are sufficient conditions for the existence of a set of integers {b₁₁, b₁₂, . . . , b_1m, b₂₁, . . . , b_n1, . . . , b_nm}⊆ N such that ∑^m_j=1b_ij = a_i, i = 1, . . . , k, and ∑^k_i=1b_ijv_i = L, j =1, . . . , m (i.e., m shelves of length L can be fully utilized). We indicate a number of special cases of well known NP-complete problems which are subsequently decided in polynomial time.     

Fast formula of a reliability ofm-consecutive-k-out-of-n:F system with cyclek

Anm-consecutive-k-out-of-n:F system is a system ofn linearly arranged components which fails if and only if at leastm non-overlapping sequences ofk components fail, when there arek distinct components with failure probabilitiesq _i fori=1,...,k and where the failure probability of thej-th component (j=rk+i (1 ≤i ≤k) isq _j =q _i , we call this system by anm-consecutive-k-out-of-n:F system with cycle (or period)k. In this paper we give a formula of the failure probability ofm-consecutive-k-out-of-n:F system with cyclek via the failure probability of consecutive-k-out-of-n:F system.     

On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.     

Truncated Complex Moment Problems with a $ \widetilde{zz} $ Relation

We solve the truncated complex moment problem for measures supported on the variety K o \mathcal{K}\equiv { z ? \in C: z [(z)\tilde]\widetilde{z} = A+Bz+C [(z)\tilde]\widetilde{z} +Dz ² ,D 1 \neq 0}. Given a doubly indexed finite sequence of complex numbers g o g⁽²ⁿ⁾:g₀₀,g₀₁,g₁₀,?,g_0,2n,g_1,2n-1,?,g_2n-1,1,g_2n,0 \gamma\equiv\gamma^{(2n)}:\gamma_{00},\gamma_{01},\gamma_{10},\ldots,\gamma_{0,2n},\gamma_{1,2n-1},\ldots,\gamma_{2n-1,1},\gamma_{2n,0} , there exists a positive Borel measure m\mu supported in K \mathcal{K} such that g_ij=ò[`(z)]<sup>i</sup>z<sup>j</sup> dm (0 ￡ 1+j ￡ 2n) \gamma_{ij}=\int\overline{z}^{i}z^{j}\,d\mu\,(0\leq1+j\leq2n) if and only if the moment matrix M(n)( g\gamma ) is positive, recursively generated, with a column dependence relation Z [(Z)\tilde]\widetilde{Z} = A1+BZ +C [(Z)\tilde]\widetilde{Z} +DZ <sup>2</sup>, and card V(g) 3\mathcal{V}(\gamma)\geq rank M(n), where V(g)\mathcal{V}(\gamma) is the variety associated to g \gamma . The last condition may be replaced by the condition that there exists a complex number g<sub>n,n+1</sub> \gamma_{n,n+1} satisfying g<sub>n+1,n</sub> o [`(g)]_n,n+1=Ag_n,n-1+Bg_n,n+Cg_n+1,n-1+Dg_n,n+1 \gamma_{n+1,n}\equiv\overline{\gamma}_{n,n+1}=A\gamma_{n,n-1}+B\gamma_{n,n}+C\gamma_{n+1,n-1}+D\gamma_{n,n+1} . We combine these results with a recent theorem of J. Stochel to solve the full complex moment problem for K \mathcal{K} , and we illustrate the connection between the truncated and full moment problems for other varieties as well, including the variety z ^k = p(z, [(Z)\tilde] \widetilde{Z} ), deg p < k.     

Selection in Monotone Matrices and Computingkth Nearest Neighbors

Anm×nmatrix =(a_{i, j}), 1≤i≤mand 1≤j≤n, is called atotally monotonematrix if for alli₁, i₂, j₁, j₂, satisfying 1≤i₁<i₂≤m, 1≤j₁<j₂≤n.[formula]We present an[formula]time algorithm to select thekth smallest item from anm×ntotally monotone matrix for anyk≤mn. This is the first subquadratic algorithm for selecting an item from a totally monotone matrix. Our method also yields an algorithm of the same time complexity for ageneralized row-selection problemin monotone matrices. Given a setS={p₁,…, p_n} ofnpoints in convex position and a vectork={k₁,…, k_n}, we also present anO(n^4/3log^c n) algorithm to compute thek_ith nearest neighbor ofp_ifor everyi≤n; herecis an appropriate constant. This algorithm is considerably faster than the one based on a row-selection algorithm for monotone matrices. If the points ofSare arbitrary, then thek_ith nearest neighbor ofp_i, for alli≤n, can be computed in timeO(n^7/5 log^c n), which also improves upon the previously best-known result.     

Nonsingular Equations over Groups II

Let G be a group, t an element distinct from G, and r(t) = g ₁ t ^{l ₁} …g _k t ^{l _k}  ∈ G* ?t?, where each g _i is an element of G order greater than 2, and the l _i are nonzero integers such that l ₁ + l ₂+…+l _k  ≠ 0 and |l _i | ≠ |l _j | for i ≠ j. We prove that if k = 4, then the natural map from G to the one-relator product ?G*t | r(t)? is injective. This together with previous results show that the natural map from G is injective for k ≥ 1.     

A note on the stability of Jordan triple higher ring derivations

In the present paper, we establish the stability and the superstability of a functional inequality corresponding to the functional equation fn（xyx） = ∑i＋j＋k=n fi（x）fj （y）fk（x）. In addition, we take account of the problem of Jacobson radical ranges for such functional inequality.     

Approximations of Two-Place Functions by Finite Sums of Terms with Separable Variables

It is known that if a smooth function h in two real variables x and y belongs to the class Σ_n of all sums of the form Σⁿ_k=1ƒ_k(x) g_k(y), then its (n + 1)th order "Wronskian" det[h_xⁱy^j]ⁿ_i,j=0 is identically equal to zero. The present paper deals with the approximation problem h(x, y) Σⁿ_k=1ƒ_k(x) g_k(y) with a prescribed n, for general smooth functions h not lying in Σ_n. Two natural approximation sums T=T(h) Σ_n, S=S(h) Σ_n are introduced and the errors |h-T|, |h-S| are estimated by means of the above mentioned Wronskian of the function h. The proofs utilize the technique of ordinary linear differential equations.     

Limit Laws for Sums of Independent Random Products: the Lattice Case

Let {V _i,j ;(i,j)∈ℕ²} be a two-dimensional array of independent and identically distributed random variables. The limit laws of the sum of independent random products

On extremal point distributions in the Euclidean plane

We ask for the maximum σ _n ^γ of Σ _i,j=1 ⁿ ‖x _i-x _j‖^γ, where x ₁,χ,x _n are points in the Euclidean plane R ² with ‖x_i-x_j‖ ≦1 for all 1≦ i,j ≦ n and where ‖.‖^γ denotes the γ-th power of the Euclidean norm, γ ≧ 1. (For γ =1 this question was stated by L. Fejes Tóth in [1].) We calculate the exact value of σ _n ^γ for all γ γ 1,0758χ and give the distributions which attain the maximum σ _n ^γ . Moreover we prove upper bounds for σ _n ^γ for all γ ≧ 1 and calculate the exact value of σ ₄ ^γ for all γ ≧ 1. This revised version was published online in June 2006 with corrections to the Cover Date.     

Sudakov-type minoration for gaussian chaos processes

Consider a setA of symmetricn×n matricesa=(a _i,j) _i,j≤n . Consider an independent sequence (g _i) _i≤n of standard normal random variables, and letM=Esup_a∈A|Σ_i,j⪯na_i,jg_ig_j|. Denote byN ₂(A, α) (resp.N _t(A, α)) the smallest number of balls of radiusα for thel ₂ norm ofR ^{n 2} (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN ₂(A, α))^1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN _t≤K(δ)M. Work partially supported by an N.S.F. grant.     

The Weak Convergence for Functions of Negatively Associated Random Variables

Let {X_n, n1} be a sequence of stationary negatively associated random variables, S_j(l)=∑^l_i=1 X_j+i, S_n=∑ⁿ_i=1 X_i. Suppose that f(x) is a real function. Under some suitable conditions, the central limit theorem and the weak convergence for sums are investigated. Applications to limiting distributions of estimators of Var S_n are also discussed.     

Note on the local growth of iterated polynomials

The local behavior of the iterates of a real polynomial is investigated. The fundamental result may be stated as follows: THEOREM. Let x_i, for i=1, 2, ..., n+2, be defined recursively by x_i+1=f(x_i), where x₁ is an arbitrary real number and f is a polynomial of degree n. Let x_i+1?x_i≧1 for i=1, ..., n + 1. Then for all i, 1 ≦i≦n, and all k, 1≦k≦n+1?i, $$ - \frac{{2^{k - 1} }}{{k!}}< f\left[ {x_1 ,... + x_{i + k} } \right]< \frac{{x_{i + k + 1} - x_{i + k} + 2^{k - 1} }}{{k!}},$$ where f[x_i, ..., x_i+k] denotes the Newton difference quotient. As a consequence of this theorem, the authors obtain information on the local behavior of the solutions of certain nonlinear difference equations. There are several cases, of which the following is typical: THEOREM. Let {x_i}, i = 1, 2, 3, ..., be the solution of the nonlinear first order difference equation x_i+1=f(x_i) where x₁ is an arbitrarily assigned real number and f is the polynomial \(f(x) = \sum\limits_{j = 0}^n {a_j x^j } ,n \geqq 2\) . Let δ be positive with δ^n?1=|2^n?1/n!a_n|. Then, if n is even and a_n<0, there do not exist n + 1 consecutive increments Δx_i=x_i+1?x_i in the solution {x_i} with Δx_i≧δ. The special case in which the iterated polynomial has integer coefficients leads to a “nice” upper bound on a generalization of the van der Waerden numbers. Ap _k -sequence of length n is defined to be a strictly increasing sequence of positive integers {x ₁, ...,x _n } for which there exists a polynomial of degree at mostk with integer coefficients and satisfyingf(x _j )=x _j+1 forj=1, 2, ...,n?1. Definep _k (n) to be the least positive integer such that if {1, 2, ...,p _k (n)} is partitioned into two sets, then one of the two sets must contain ap _k -sequence of lengthn. THEOREM. p_n?2(n)≦(n!)^(n?2)!/2.     

On a generalization of a theorem of Erdős and Fuchs

Let A={a₁,a₂,…}(a₁<a₂<) be an infinite sequence of nonnegative integers, let k≥2 be a fixed integer and denote by r_k(A,n) the number of solutions of a_i1+a_i2++a_ik≤n. Montgomery and Vaughan proved that r₂(A,n)=cn+o(n^1/4) cannot hold for any constant c>0. In this paper, we extend this result to k>2.     

Nonhomogeneous recursions and Generalised Continued Fractions

Consider the (n+1)st order nonhomogeneous recursionX _k+n+1=b _k X _k+n +a _k ⁽ⁿ⁾ X _k+n-1+...+a _k ⁽¹⁾ X _k +X _k .Leth be a particular solution, andf ⁽¹⁾,...,f ⁽ⁿ⁾,g independent solutions of the associated homogeneous equation. It is supposed thatg dominatesf ⁽¹⁾,...,f ⁽ⁿ⁾ andh. If we want to calculate a solutiony which is dominated byg, but dominatesf ⁽¹⁾,...,f ⁽ⁿ⁾, then forward and backward recursion are numerically unstable. A stable algorithm is derived if we use results constituting a link between Generalised Continued Fractions and Recursion Relations.