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.     

Eventually positive solutions of first order nonlinear differential equations with a deviating argument

The following first order nonlinear differential equation with a deviating argument $ x'(t) + p(t)[x(\tau (t))]^\alpha = 0 $ is considered, where α > 0, α ≠ 1, p ∈ C[t ₀; ∞), p(t) > 0 for t ≧ t ₀, τ ∈ C[t ₀; ∞), lim _t→∞ τ(t) = ∞, τ(t) < t for t ≧ t ₀. Every eventually positive solution x(t) satisfying lim _t→∞ x(t) ≧ 0. The structure of solutions x(t) satisfying lim _t→∞ x(t) > 0 is well known. In this paper we study the existence, nonexistence and asymptotic behavior of eventually positive solutions x(t) satisfying lim _t→∞ x(t) = 0.     

Recurrence relations based on minimization and maximization

Explicit and asymptotic solutions are presented to the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + min_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) for the cases (1) α + β < 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and g(n) = δ_nI. (2) α + β > 1, min(α, β) > 1, $\text{log}{}_2\text{α}\text{log}{}_2\text{β}$ is rational, and (a) g(n) = δ_n1, (b) g(n) = 1. The general form of this recurrence was studied extensively by Fredman and Knuth [J. Math. Anal. Appl.48 (1974), 534–559], who showed, without actually solving the recurrence, that in the above cases $\text{M(n) = Ω(n}{}^{\mathrm{<mtext>1\; +\; </mtext><mtext>1</mtext><mtext>\gamma </mtext>}}\text{)}$, where γ is defined by α^?γ + β^?γ = 1, and that $\text{lim}{}_{\mathrm{n\; \to \; \infty }}\text{M(n)}\text{n}{}^{\mathrm{1\; +\; \gamma }}$ does not exist. Using similar techniques, the recurrence M(1) = g(1), M(n + 1) = g(n + 1) + max_{1 ? t ? n}(αM(t) + βM(n + 1 ? t)) is also investigated for the special case α = β < 1 and g(n) = 1 if n is odd = 0 if n is even.     

Asymptotic properties of matrix differential operators

For given matrices A(s) and B(s) whose entries are polynomials in s, the validity of the following implication is investigated: ?_ylim_{t → ∞}A(D) y(t) = 0 ? lim_{t → ∞}B(D) y(t) = 0. Here D denotes the differentiation operator and y stands for a sufficiently smooth vector valued function. Necessary and sufficient conditions on A(s) and B(s) for this implication to be true are given. A similar result is obtained in connection with an implication of the form ?_yA(D) y(t) = 0, lim_{t → ∞}B(D) y(t) = 0, C(D) y(t) is bounded ? lim_{t → ∞}E(D) y(t) = 0.     

On the Semicontinuity of Curvature Integrals

Let H_j(K, ·) be the j – th elementary symmetric function of the principal curvatures of a convex body K in Euclidean d – space. We show that the functionals ∫_bd f(H_j(K, x)) dℋ︁^d—1(x) depend upper semicontinuously on K, if f : [0, ∞) is concave, lim_t→0f(t) = 0, and lim_t→∞f(t)/t = 0. An analogous statement holds for integrals of elementary symmetric functions of the principal radii of curvature.     

Heavy-traffic extreme value limits for Erlang delay models

We consider the maximum queue length and the maximum number of idle servers in the classical Erlang delay model and the generalization allowing customer abandonment—the M/M/n+M queue. We use strong approximations to show, under regularity conditions, that properly scaled versions of the maximum queue length and maximum number of idle servers over subintervals [0,t] in the delay models converge jointly to independent random variables with the Gumbel extreme value distribution in the quality-and-efficiency-driven (QED) and ED many-server heavy-traffic limiting regimes as n and t increase to infinity together appropriately; we require that t _n →∞ and t _n =o(n ^1/2?ε ) as n→∞ for some ε>0.     

Sojourns and extremes of Fourier sums and series with random coefficients

Let X(t) be the trigonometric polynomial Σ^k_j=0a_j(U_tcosjt+V_jsinjt), –∞< t<∞, where the coefficients U_t and V_t are random variables and a_j is real. Suppose that these random variables have a joint distribution which is invariant under all orthogonal transformations of R^2k–2. Then X(t) is stationary but not necessarily Gaussian. Put L_t(u) = Lebesgue measure {s: 0?s?t, X(s) > u}, and M(t) = max{X(s): 0?s?t}. Limit theorems for L_t(u) and $\text{P}\text{(M(t) > u)}$ for u→∞ are obtained under the hypothesis that the distribution of the random norm (Σ^k_j=0(U²_j+V²_j))^{1 2} belongs to the domain of attraction of the extreme value distribution exp{ e^–2}. The results are also extended to the random Fourier series (k=∞).     

Moderate deviations and Erdös-Rényi-Shepp laws for weighted sums

Let X₀,X₁,… be i.i.d. random variables with E(X₀)=0, E(X²₀)=1 and E(exp{tX₀})<∞ for any |t|<t₀. We prove that the weighted sums V(n)=∑_j=0^∞a_j(n)X_j, n?1 obey a moderately large deviation principle if the weights satisfy certain regularity conditions. Then we prove a new version of the Erdös-Rényi-Shepp laws for the weighted sums.     

Extensions of Szegö's theory of orthogonal polynomials,III

Let {ø _n (dμ)} be a system of orthonormal polynomials on the unit circle with respect to a measuredμ. Szegö's theory is concerned with the asymptotic behavior ofø _n (dμ) when logμ′∈L ¹. In what follows we will discuss the asymptotic behavior of the ratioø _n (dμ ₂)/ø _n (dμ ₁) on the unit circle whendμ ₁ anddμ ₂ are close in a sense (e.g.,dμ ₂=gdμ ₁, where g≥0 is such thatQ(e ^it )g(t) andQ(e ^it )/g(t) are bounded for a suitable polynomialQ) and μ ₁ ^′ >0 almost everywhere or (a somewhat weaker requirement) lim _n→∞Φ _n (dμ ₁,0)=0 for the monic polynomial Φ _n . The asymptotic behavior of the same fraction outside the unit circle was discussed in an earlier paper.     

Some soluble cases of the discrete logarithm problem

Letg be a primitive λ-root modn. Then the powersg ^t mod,n, fort=1, 2, ..., λ(n) represent a (cyclic) subgroupC _λ(n) (of order λ(n)) ofM _n , the group of order ?(n), representingall primitive residue classes modn. To computet backwards fromg ^t modn is calledthe discrete logarithm problem inC _λ(n), also expressible by $$a \equiv g^t \bmod n \Leftrightarrow t \equiv \log _g a\bmod \lambda \left( n \right).$$ The purpose of this paper is to point out some cases, in which this problem can be solved by astraight-forward formula only, with no element of guessing or collecting factorizations or the like involved at all, taking timeO(log³ n) or less to compute (orO(log^2+ε n), if fast multiplication of multiple precision integers is used).—One very simple case is given by the modulusn=10 ^s , fors≥4. To give just one instance of this case: Forn=10⁸, if the primitive λ-rootg=3¹⁷ ≡ 29140163 modn is chosen, anda=g ^t modn, then $$a \equiv 4962873 \cdot \frac{{a^{250000} - 1}}{{5000000}}\bmod 5000000.$$      

On the value of a random minimum spanning tree problem

Suppose we are given a complete graph on n vertices in which the lenghts of the edges are independent identically distributed non-negative random variables. Suppose that their common distribution function F is differentiable at zero and D = F′ (0) > 0 and each edge length has a finite mean and variance. Let L_n be the random variable whose value is the length of the minimum spanning tree in such a graph. Then we will prove the following: lim_{n → ∞}E(L_n) = ζ(3)/D where ζ(3) = Σ_{k = 1}^∞ 1/k³ = 1.202… and for any ε > 0 lim_{n → ∞} Pr(|L_n^?ζ(3)/D|) > ε) = 0.     

A note on strong summability of two-dimensional Walsh-Fourier series

The paper deals with the strong summability of Marcinkiewicz means with a variable power. Let $$H_n \left( {f,x,y,A_n } \right): = \tfrac{1} {n}\sum\nolimits_{l = 1}^n {\left( {e^{\left. {A_n } \right|\left. {S_{ll} \left( {f,x,y} \right) - f\left( {x,y} \right)} \right|^{{1 \mathord{\left/ {\vphantom {1 2}} \right. \kern-\nulldelimiterspace} 2}} } - 1} \right)} .$$ It is shown that if A _n ↑ ∞ arbitrary slowly, there exists f ∈ C(I ²) such that lim _n→∞ H _n (f, 0, 0, A _n ) = +∞. At the same time, for every f ∈ C (I ²) there exists A _n (f) ↑ ∞ such that lim _n→∞ H _n (f, x, y, A _n ) = 0 uniformly on I ².     

The asymptotic number of geometries

A simple proof is given that lim_n?t8(log₂ log₂g_n)/n = 1, where g_n denotes the number of distinct combinatorial geometries on n point     

Subalgebras of matrix algebras generated by companion matrices

Let f,g∈Z[X] be monic polynomials of degree n and let C,D∈M_n(Z) be the corresponding companion matrices. We find necessary and sufficient conditions for the subalgebra Z〈C,D〉 to be a sublattice of finite index in the full integral lattice M_n(Z), in which case we compute the exact value of this index in terms of the resultant of f and g. If R is a commutative ring with identity we determine when R〈C,D〉=M_n(R), in which case a presentation for M_n(R) in terms of C and D is given.     

On a continuous analogue of the stochastic difference equation Xn=ρXn-1+Bn

Let B₁, B₂, ... be a sequence of independent, identically distributed random variables, letX₀ be a random variable that is independent ofB_n forn?1, let ρ be a constant such that 0<ρ<1 and letX₁,X₂, ... be another sequence of random variables that are defined recursively by the relationshipsX_n=ρX_n-1+B_n. It can be shown that the sequence of random variablesX₁,X₂, ... converges in law to a random variableX if and only ifE[log⁺¦B₁¦]<∞. In this paper we let {B(t):0≦t<∞} be a stochastic process with independent, homogeneous increments and define another stochastic process {X(t):0?t<∞} that stands in the same relationship to the stochastic process {B(t):0?t<∞} as the sequence of random variablesX₁,X₂,...stands toB₁,B₂,.... It is shown thatX(t) converges in law to a random variableX ast →+∞ if and only ifE[log⁺¦B(1)¦]<∞ in which caseX has a distribution function of class L. Several other related results are obtained. The main analytical tool used to obtain these results is a theorem of Lukacs concerning characteristic functions of certain stochastic integrals.     

On the rate for uniform strong consistency of empirical distributions of independent nonidentically distributed multivariate random variables

Let X_j = (X_1j ,…, X_pj), j = 1,…, n be n independent random vectors. For x = (x₁ ,…, x_p) in R^p and for α in [0, 1], let F_j${}^1$(x) = αI(X_1j < x₁ ,…, X_pj < x_p) + (1 ? α) I(X_1j ≤ x₁ ,…, X_pj ≤ x_p), where I(A) is the indicator random variable of the event A. Let F_j(x) = E(F_j${}^1$(x)) and D_n = sup_{x, α} max_{1 ≤ N ≤ n} |Σ₀ⁿ(F_j${}^1$(x) ? F_j(x))|. It is shown that P[D_n ≥ L] < 4pL exp{?2(L²n^?1 ? 1)} for each positive integer n and for all L² ≥ n; and, as n → ∞, $\text{D}{}_{\mathrm{n}}\text{= 0((n}\text{log}\text{n)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{)}$ with probability one.     

Constructing polynomials of minimal growth

In [2] a cyclic diagonal operator on the space of functions analytic on the unit disk with eigenvalues (λ _n ) is shown to admit spectral synthesis if and only if for each j there is a sequence of polynomials (p _n ) such that lim _n→∞ p _n (λ _k ) = δ _j,k and lim sup _n→∞ sup _k>j |p _n (λ _k )|^1/k ≤ 1. The author also shows, through contradiction, that certain classes of cyclic diagonal operators are synthetic. It is the intent of this paper to use the aforementioned equivalence to constructively produce examples of synthetic diagonal operators. In particular, this paper gives two different constructions for sequences of polynomials that satisfy the required properties for certain sequences to be the eigenvalues of a synthetic operator. Along the way we compare this to other results in the literature connecting polynomial behavior ([4] and [9]) and analytic continuation of Dirichlet series ([1]) to the spectral synthesis of diagonal operators.     

The rate of convergence for backwards products of a convergent sequence of finite Markov matrices

Recent papers have shown that Π^∞_{k = 1}P(k) = lim_m→∞ (P(m) ? P(1)) exists whenever the sequence of stochastic matrices {P(k)}^∞_{k = 1} exhibits convergence to an aperiodic matrix P with a single subchain (closed, irreducible set of states). We show how the limit matrix depends upon P(1).In addition, we prove that lim_m→∞lim_n→∞ (P(n + m) ? P(m + 1)) exists and equals the invariant probability matrix associated with P. The convergence rate is determined by the rate of convergence of {P(k)}^∞_{k = 1} towards P.Examples are given which show how these results break down in case the limiting matrix P has multiple subchains, with {P(k)}^∞_{k = 1} approaching the latter at a less than geometric rate.     

C (n)-cardinals

For each natural number n, let C ⁽ⁿ⁾ be the closed and unbounded proper class of ordinals α such that V _α is a Σ _n elementary substructure of V. We say that κ is a C ⁽ⁿ⁾ -cardinal if it is the critical point of an elementary embedding j : V → M, M transitive, with j(κ) in C ⁽ⁿ⁾. By analyzing the notion of C ⁽ⁿ⁾-cardinal at various levels of the usual hierarchy of large cardinal principles we show that, starting at the level of superstrong cardinals and up to the level of rank-into-rank embeddings, C ⁽ⁿ⁾-cardinals form a much finer hierarchy. The naturalness of the notion of C ⁽ⁿ⁾-cardinal is exemplified by showing that the existence of C ⁽ⁿ⁾-extendible cardinals is equivalent to simple reflection principles for classes of structures, which generalize the notions of supercompact and extendible cardinals. Moreover, building on results of Bagaria et?al. (2010), we give new characterizations of Vopeňka’s Principle in terms of C ⁽ⁿ⁾-extendible cardinals.     

On the crossing number of cm × cn

We show that the M-crossing number cr_M(C_m × C_n) of C_m × C_n behaves asymptotically according to lim_n→∞ {cr_M(C_m × C_n)/((m − 2)n)} = 1, for each m ≥ 3. This result reinforces the conjecture cr(C_m × C_n) = (m − 2)n if 3 ≤ m ≤ n, which has been proved only for m ≤ 6. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 163–170, 1998