Asymptotic Recurrence and Waiting Times for Stationary Processes

Let be a discrete-valued stationary ergodic process distributed according to P and let x=(..., x _–1, x ₀, x ₁,...) denote a realization from X. We investigate the asymptotic behavior of the recurrence time R _n defined as the first time that the initial n-block reappears in the past of x. We identify an associated random walk, on the same probability space as X, and we prove a strong approximation theorem between log R _n and . From this we deduce an almost sure invariance principle for log R _n. As a byproduct of our analysis we get unified proofs for several recent results that were previously established using methods from ergodic theory, the theory of Poisson approximation and the analysis of random trees. Similar results are proved for the waiting time W _n defined as the first time until the initial n-block from one realization first appears in an independent realization generated by the same (or by a different) process.     

Determinants of Matrices Associated with Incidence Functions on Posets

Let S = x ₁,...,x _n} be a finite subset of a partially ordered set P. Let f be an incidence function of P. Let denote the n × n matrix having f evaluated at the meet of x _i and x _j as its i, j-entry and denote the n × n matrix having f evaluated at the join of x _i and x _j as its i, j-entry. The set S is said to be meet-closed if for all 1 i, j n. In this paper we get explicit combinatorial formulas for the determinants of matrices and on any meet-closed set S. We also obtain necessary and sufficient conditions for the matrices and on any meet-closed set S to be nonsingular. Finally, we give some number-theoretic applications.     

<Emphasis Type="Italic">N</Emphasis>-commutators

The N-commutator is conjecturally a well-defined nontrivial operation on for x = (x ₁, ... , x _n ) if and only if N = n ² + 2n - 2. This is proved for n = 2 and confirmed by computer experiments for n < 5. Under 2- and 5-commutators the algebra of divergence-free vector fields in two dimensions is an sh-Lie (strong homotopic Lie) algebra in the sense of Stasheff. Similarly, W(2) is an sh-Lie algebra with respect to 2- and 6-commutators.     

Manifolds with involution

In this paper, we determine the groups (k _i are odd), (k _i are odd and (k _i are even andn>k _l ), (k _i are even andn>k _l ), (k _i are even andn>k _l ,k _l 12),J _n ^1,2,J _n ^2,3,J _n ^1,4. And we obtain the relation Im _n ^k =J _n ^l,k .     

Complete variable-length “fix-free” codes

A set of codewords isfix-free if it is both prefix-free and suffix-free: no codeword in the set is a prefix or a suffix of any other. A set of codewords {x ₁,x ₂,...,x _n } over at-letter alphabet is said to becomplete if it satisfies the Kraft inequality with equality, so that

Kernels of sequences of complex numbers and their regular transformations

It is proved that , where U(a, r) is the ball of radius r with center at the pointa, is the smallest closed convex set containing the kernel of any sequence {y_n} obtained from the sequence {x_n} by means of a regular transformation (c_nk) satisfying the condition , where x, x_n, c_nk (n, k=1, 2,...) are complex numbers.Traslated from Matematicheskie Zametki, Vol. 22, No. 6, pp. 815–823, December, 1977.     

A new bound for an extension of Mason’s theorem for functions of several variables

In this paper, using the generalized Wronskian, we obtain a new sharp bound for the generalized Masons theorem [1] for functions of several variables. We also show that the Diophantine equation (The generalized Fermat-Catalan equation) where , such that k out of the n-polynomials are constant, and under certain conditions for has no non-constant solution. Received: 20 March 2003     

Singular series in the problem of the representation of a system of numbers by a system of forms

A system of Diophantine equations is considered for integers n₁,...,₂, $$\phi ^{\left( k \right)} \left( {x_1 , \ldots ,x_s } \right) = n_k \left( {k = 1, \ldots ,2} \right)$$ , Ф^(k)(x₁,...,x_s)=n_k (k=1,...,ρ), where Ф^(k) are integral forms of degree d is s variables. The singular integral and singular series of this problem are investigated.     

The Descent Monomials and a Basis for the Diagonally Symmetric Polynomials

Let R(X) = Q[x ₁, x ₂, ..., x _n] be the ring of polynomials in the variables X = {x ₁, x ₂, ..., x _n} and R*(X) denote the quotient of R(X) by the ideal generated by the elementary symmetric functions. Given a S _n, we let g In the late 1970s I. Gessel conjectured that these monomials, called the descent monomials, are a basis for R*(X). Actually, this result was known to Steinberg [10]. A. Garsia showed how it could be derived from the theory of Stanley-Reisner Rings [3]. Now let R(X, Y) denote the ring of polynomials in the variables X = {x ₁, x ₂, ..., x _n} and Y = {y ₁, y ₂, ..., y _n}. The diagonal action of S _n on polynomial P(X, Y) is defined as Let R (X, Y) be the subring of R(X, Y) which is invariant under the diagonal action. Let R *(X, Y) denote the quotient of R (X, Y) by the ideal generated by the elementary symmetric functions in X and the elementary symmetric functions in Y. Recently, A. Garsia in [4] and V. Reiner in [8] showed that a collection of polynomials closely related to the descent monomials are a basis for R *(X, Y). In this paper, the author gives elementary proofs of both theorems by constructing algorithms that show how to expand elements of R*(X) and R *(X, Y) in terms of their respective bases.     

On Fraenkel’s <Emphasis Type="Italic">N</Emphasis>-Heap Wythoff’s Conjectures

The N-heap Wythoffs game is a two-player impartial game with N piles of tokens of sizes Players take turns removing any number of tokens from a single pile, or removing (a₁,..., a_N) from all piles - a_i tokens from the i-th pile, providing that where is the nim addition. The first player that cannot make a move loses. Denote all the P-positions (i.e., losing positions) by Two conjectures were proposed on the game by Fraenkel [7]. When are fixed, i) there exists an integer N₁ such that when . ii) there exist integers N₂ and _2 such that when , the golden section.In this paper, we provide a sufficient condition for the conjectures to hold, and subsequently prove them for the three-heap Wythoffs game with the first piles having up to 10 tokens.AMS Subject Classification: 91A46, 68R05.     

Mahler measure and entropy for commuting automorphisms of compact groups

We compute the joint entropy ofd commuting automorphisms of a compact metrizable group. LetR _d = [u ₁ ^±1 ,...,[d ₁ ^±1 ] be the ring of Laurent polynomials ind commuting variables, andM be anR _d -module. Then the dual groupX _M ofM is compact, and multiplication onM by each of thed variables corresponds to an action _M of ^d by automorphisms ofX _M . Every action of ^d by automorphisms of a compact abelian group arises this way. IffR _d , our main formula shows that the topological entropy of is given by

Multiple Wick Product Chaos Processes

Let u(x) xR ^q be a symmetric nonnegative definite function which is bounded outside of all neighborhoods of zero but which may have u(0)=. Let p _x, (·) be the density of an R ^q valued canonical normal random variable with mean x and variance and let {G _x, ; (x, )R ^q ×[0,1 ]} be the mean zero Gaussian process with covariance

Application of the Chauvenet Test to Detection of Overliers in Observations Connected in a Homogeneous Markov Chain

Let be Gaussian random variables connected in a homogeneous Markov chain and let a sample sequence of length n with possible overliers be given. The asymptotic behavior of the distribution of the number N of Chauvenet overliers as is investigated for unknown mean and correlation. Bibliography: 3 titles.     

On fixed-point-free permutation properties in groups and semigroups

We say that a semigroup S is (fixed-point-free, for short f.p.f.) permutable, if, for some integer n and for every x₁,..., x_n in S, there exists a non-trivial (fixed-point-free) permutation on {1,..., n}, such that:

A Note on the Recursive Sequence x n + 1 = p k x n + p k − 1 x n − 1 +...+ p 1 x n − k + 1

We present some comments on the behavior of solutions of the difference equation where p _i 0, i = 1,..., k, k N, and x _–k ,..., x _–1 R.     

A functional limit theorem for Erdös and Rényi's law of large numbers

Summary We use the theory of large deviations on function spaces to extend Erdös and Rényi's law of large numbers. In particular, we show that with probability 1, the double-indexed set of paths {W _{N, n} } defined by where , {X _i : _i 1} is an iid sequence of random variables, andh(N)=[clogN] is relatively compact; the limit set is given by the set [xI ^*(x)1/c] whereI ^*(x) = ₀ ¹ I(x(t))dt andI is Cramér's rate function.     

On the rod placement theorem of Rybko and Shlosman

Given n−1 points on the real line and a set of n rods of strictly positive lengths , we get to choose an n-th point x_n anywhere on the real line and to assign the rods to the points according to an arbitrary permutation π. The rod is thought of as the workload brought in by a customer arriving at time x_k into a first in -first out queue which starts empty at − ∞. If any x_i equals x_j for i < j, service is provided to the rod assigned to x_i before the rod assigned to x_j. Let denote the set of departure times of the customers (rods). Let denote the number of choices for the location of x_n for which . Rybko and Shlosman proved that

Monomial congruences

Letn ₁,n ₂,...,n _t integers. It is proved that the monomial congruence is solvable for allm2 and (a, m)=1 if and only if (n ₁ ,n ₂ ..., n _t )=1.     

Capacity of sets and uniform distribution of sequences

In this paper the magnitude of the set of pointsx is studied for which the series , with complex numbersc _n and an increasing sequenceV(N) of real numbers, is unbounded. An answer in terms of capacities is given. This result is then used to obtain results about exceptional sets in the theory of uniform distribution, e.g. it is shown that the spectrum of any sequence has dimension zero.     

Limit theorems for the ratio of the empirical distribution function to the true distribution function

Summary We consider almost sure limit theorems for and where _n is the empirical distribution function of a random sample ofn uniform (0, 1) random variables anda _n 0. It is shown that (1) ifna _n /log₂ n then both and converge to 1 a.s.; (2) ifna _n /log₂ n=d>0 (d>1) then has an almost surely finite limit superior which is the solution of a certain transcendental equation; and (3) ifna _n /log₂ n0 then and have limit superior + almost surely. Similar results are established for the inverse function _n ^–1 .Supported by the National Science Foundation under MCS 77-02255