Random polytopes in thed-dimensional cube

LetC ^d be the set of vertices of ad-dimensional cube,C ^d ={(x ₁, ...,x _d ):x _i =±1}. Let us choose a randomn-element subsetA(n) ofC ^d . Here we prove that Prob (the origin belongs to the convA(2d+x2d))=(x)+o(1) ifx is fixed andd . That is, for an arbitrary>0 the convex hull of more than (2+)d vertices almost always contains 0 while the convex hull of less than (2-)d points almost always avoids it.     

A system of basis invariants of the group Bn

In 1968 Flatto announced the conjecture that the polynomials _±(±x ₁±x ₂±±x _n )^2s ,s=1,n, are algebraically independent. This conjecture was confirmed by Haeuslein. A new proof of this result is given.Translated from Ukrainskií Geometricheskií Sbornik, Issue 29, 1986, pp. 54–55.     

Factorial functions and stirling numbers of fractional orders

The aim of this paper is to study the binomial coefficients ( _n ^x ), the factorial polynomials [x]_n and [x]ⁿ, the Stirling numbers of first and second kind, namely s(n,k) and S(n,k), in the case that n ∈ ? is replaced by real α ∈ ?. In the course of the paper, the Vandermonde convolution formula is presented in an infinite series frame, the binomial coefficient function ( _a ^x ), α ∈ ?, is sampled in terms of the binomial coefficients ( _k ^x ) for k ∈ ?_o, Bell numbers of fractional orders are introduced. Emphasis is placed on the fractional order Stirling numbers s(α,k) and S(α,k), first studied here. Some applications of the S(α,k) are given.     

On the product of sign vectors and unit vectors

For a fixed unit vectora=(a ₁,...,a _n )S ^n-1, consider the 2 ⁿ sign vectors=(₁,..., _n ){±1{ ⁿ and the corresponding scalar products^·a = _n ⁱ⁼¹ = _i a _i . The question that we address is: for how many of the sign vectors must^.a lie between–1 and 1. Besides the straightforward interpretation in terms of the sums ±a ₂ , this question has appealing reformulations using the language of probability theory or of geometry.The natural conjectures are that at least 1/2 the sign vectors yield |.a|1 and at least 3/8 of the sign vectors yield |.a|<1 (the latter excluding the case when |a _i |=1 for somei). These conjectured lower bounds are easily seen to be the best possible. Here we prove a lower bound of 3/8 for both versions of the problem, thus completely solving the version with strict inequality. The main part of the proof is cast in a more general probabilistic framework: it establishes a sharp lower bound of 3/8 for the probability that |X+Y|<1, whereX andY are independent random variables, each having a symmetric distribution with variance 1/2.We also consider an asymptotic version of the question, wheren along a sequence of instances of the problem satisfying ||a||0. Our result, best expressed in probabilistic terms, is that the distribution of .a converges to the standard normal distribution, and in particular the fraction of sign vectors yielding .a between –1 and 1 tends to 68%.This research was supported in part by the Institute for Mathematics and its Applications with funds provided by the National Science Foundation.     

Parallel algorithm for linear diophantine equations

We consider a parallel-sequential algorithm to find all the solution of a linear Diophantine equation a_nx_n + a_n — 1x_n — 1 + +a₁x₁ = b, a_i, b, x_i Z⁺ by the method of dynamic upper bounds. Parallel processing and dichotomizing search are responsible for logarithmic time complexity of the algorithm. The auxiliary table memory requirements are 3n words. The algorithm can be applied in linear integer programming problems.Simferopol' University. Translated from Dinamicheskie Sistemy, No. 10, pp. 111–117, 1992.     

Simplexes of L-subdivisions of Euclidean spaces

It is shown that necessary and sufficient conditions for a basic simplex of a point lattice in Eⁿ space to be an L-simplex are equivalent to conditions imposed on the coefficients a_ij of the form _i,j=1 ⁿ a_ijx_ix_j– _i=1 ⁿ a_iix_i. namely, that it should assume positive values for all possible integer values of the variables x₁..., x_n (excluding the obvious n+1 cases when the form is equal to 0). These conditions are obtained for n 5.Translated from Matematicheskie Zametkij Vol. 10, No. 6, pp. 659–670, December, 1971.     

A strong law for weighted sums of i.i.d. random variables

A strong law is proved for weighted sumsS _n=a _in X _i whereX _i are i.i.d. and {a _in} is an array of constants. When sup(n ^–1|a _in | ^q )^1/q <, 1<q andX _i are mean zero, we showE|X| ^p <,p ^l+q ^–1=1 impliesS _n /n 0. Whenq= this reduces to a result of Choi and Sung who showed that when the {a _in} are uniformly bounded,EX=0 andE|X|< impliesS _n /n 0. The result is also true whenq=1 under the additional assumption that lim sup |a _in |n ^–1 logn=0. Extensions to more general normalizing sequences are also given. In particular we show that when the {a _in} are uniformly bounded,E|X|^1/< impliesS _n /n 0 for >1, but this is not true in general for 1/2<<1, even when theX _i are symmetric. In that case the additional assumption that (x ^1/ log^1/–1 x)P(|X|x)0 asx provides necessary and sufficient conditions for this to hold for all (fixed) uniformly bounded arrays {a _in}.     

An integral criterion for oscillation of linear differential equations of second order

It is proved that if for some n>2 the function x^1–nA_n(x), where A_n(x) is the n-th primitive ofa(x), is not bounded above, then the equation y +a(x)y = 0 oscillates.Translated from Matematicheskie Zametki, Vol. 23, No. 2, pp. 249–251, February, 1978.In conclusion, I thank R. S. Ismagilov for useful discussions about the problem of osillation.     

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.     

Random symmetric polynomials

Let {Q⁽ⁿ⁾(x₁,...,x_n)} be a sequence of symmetric polynomials having a fixed degree equal to k. Let {X_n1,...,X_nn}, n k, be some sequence of series of random variables (r.v.). We form the sequence of r.v. Y_n=Q⁽ⁿ⁾(X_n1, ... X_nn), n k One obtains limit theorems for the sequence Y_n, under very general assumptions.Translated from Veroyatnostnye Raspredeleniya i Matematicheskaya Statistika, pp. 170–188, 1986.     

The analytic spread of codimension two monomial varieties

Let ${\rm} A=k[{u_{1}^{a_{1}}},{u_{2}^{a_{2}}},\dots,{u_{n}^{a_{n}}},{u_{1}^{c_{1}}} \dots {u_{n}^{c_{n}}},{u_{1}^{b_{1}}} \dots {u_{n}^{b_{n}}}]\ \subset k[{u_{1}}, \dots {u_{n}}],$ where, a_j, b_j, C_j ∈ ?, a_j > 0, (b_j, C_j) ≠ (0,0) for 1 ≤ j ≤ n, and, further ${\underline b}:=\ ({b_{1}}, \dots,{b_{n}})\ \not=\ 0 $ and ${\underline c}:=\ ({c_{1}}, \dots,{c_{n}})\ \not=\ 0 $ . The main result says that the defining ideal I ? m = (x₁,…, x_n, y, z) ? k[x₁,…, x_n, y, z] of the semigroup ring A has analytic spread ?(I_m) at most three.     

Atomic Decomposition of Hardy Spaces Associated with Certain Laguerre Expansions

Let L _n ^a (x), n=0,1,…, be the Laguerre polynomials of order a>−1. Denote ℓ _n ^a (x)=(n!/Γ(n+a+1))^1/2 L _n ^a (x)e ^−x/2. Let

On the Greatest Common Di visor of u − 1 and v − 1 with u and v Near ${\cal S}$- units

In [2], it was shown that if a and b are multiplicatively independent integers and ɛ > 0, then the inequality gcd (aⁿ − 1,bⁿ − 1) < exp(ɛn) holds for all but finitely many positive integers n. Here, we generalize the above result. In particular, we show that if f(x),f₁(x),g(x),g₁(x) are non-zero polynomials with integer coefficients, then for every ɛ > 0, the inequality holds for all but finitely many positive integers n.     

On the convergence of the LJ search method

The convergence of the Luus-Jaakola search method for unconstrained optimization problems is established.Notation E _n Euclideann-space - f Gradient off(x) - ² f Hessian matrix - (·) ^T Transpose of (·) - I Index set {1, 2, ...,n} - [x _i1 ^*(j) ] Point around which search is made in the (j + 1)th iteration, i.e., [x _1l ^*(j) ,x _2l ^*(j) ,...,x _n1 ^*(j) ] - r _i ⁽ⁱ⁾ Range ofx _il ^*(i) in the (j + 1)th iteration - l ₁ min_i {r _i ⁽⁰⁾ } - l ₂ min_i {r _i ⁽⁰⁾ } - A _j Region of search in thejth iteration, i.e., {x E _n:x _il ^*(j-1) –0.5r _i ^(j-1) x _ix _il ^*(j-1) +0.5r _i ^(j-1) ,i I} - S _j Closed sphere with center origin and radius _j - Reduction factor in each iteration - 1– - (·) Gamma function Many discussions with Dr. S. N. Iyer, Professor of Electrical Engineering, College of Engineering, Trivandrum, India, are gratefully acknowledged. The author has great pleasure to thank Dr. K. Surendran, Professor, Department of Electrical Engineering, P.S.G. College of Technology, Coimbatore, India, for suggesting this work.     

Generating Uniform Random Vectors

In this paper, we study the rate of convergence of the Markov chain X _n+1=AX _n +b _n mod p, where A is an integer matrix with nonzero integer eigenvalues and {b _n } _n is a sequence of independent and identically distributed integer vectors. If _i±1 for all eigenvalues _i of A, then n=O((log p)²) steps are sufficient and n=O(log p) steps are necessary to have X _n sampling from a nearly uniform distribution. Conversely, if A has the eigenvalue ₁=±1, and _i±1 for all i1, n=O(p²) steps are necessary and sufficient.     

Uniqueness of solutions of boundary-value problems for operator-differential equations on a finite segment and on a semiaxis

For the equationL ₀ x(t)+L ₁x(t)+...+L _n x ⁽ⁿ⁾(t)=O, whereL _k,k=0,1,...,n, are operators acting in a Banach space, we establish criteria for an arbitrary solutionx(t) to be zero provided that the following conditions are satisfied:x ^(1–1) (a)=0, 1=1, ..., p, andx ^(1–1) (b)=0, 1=1,...,q, for - <a< b< (the case of a finite segment) orx ^(1–1) (a)=0, 1=1,...,p, under the assumption that a solutionx(t) is summable on the semiaxista with its firstn derivatives.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 3, pp. 279–292, March, 1994.This research was supported by the Ukrainian State Committee on Science and Technology.     

Minimal rates of entropy convergence for completely ergodic systems

If (X,T) is a completely ergodic system, then there exists a positive monotone increasing sequence {a _n } _n ^1/∞ with lim _n →∞a _n =∞ and a positive concave functiong defined on [1, ∞) for whichg(x)/x ² isnot integrable such that for all nontrivial partitions α ofX into two sets.     

Comparison between the best approximations by lacunary and ordinary polynomials

We denote E_n(f) and E _k ⁿ (f) the best uniform approximations to a continuous function f defined on [a,b] by the sets of algebraic polynomials of degree ≤n and algebraic polynomials of degree ≤n with the coefficients of x^k (k≤n) being zero. In this paper, in cases of r<k and r≥k while [a, b]=[−1,1] (or r<k,k≤r<2k and r>2k while [a,b]=[0, 1]), we separately discuss the condtions for r-times continuously differentiable function f which enables .     

Some examples of random walks on free products of discrete groups

Summary We consider the random walk (X_n) associated with a probability p on a free product of discrete groups. Knowledge of the resolvent (or Green's function) of p yields theorems about the asymptotic behaviour of the n-step transition probabilities p^*n(x)=P(X_n= x¦ X₀=e) as n. Woess [15], Cartwright and Soardi [3] and others have shown that under quite general conditions there is behaviour of the type p^*n(x)C_x^– n n^– 3/2. Here we show on the other hand that if G is a free product of m copies ofZ ^r and if (X_n) is the « average » of the classical nearest neighbour random walk on each of the factorsZ ^r, then while it satisfies an « n^–3/2 — law » for r small relative to m, it switches to an n^– r/2 -law for large r. Using the same techniques, we give examples of irreducible probabilities (of infinite support) on the free groupZ ^*m which satisfyn ^– for .     

Global controllability of conditionally periodic linear system

We use the notation: Rⁿ Is n-dimensional Euclidean space;S _a (x⁰)={x Rⁿ: ¦x-x ⁰ ¦ }; int Q is the interior of setQ Rⁿ. With any linear systemx=A (t)x +B (t) u, x Rⁿ,u R^m, (1)Translated from Matematicheskie Zametki, Vol. 32, No. 2, pp. 169–174, August, 1982.