Almost linear upper bounds on the length of general davenport—schinzel sequences

Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We obtain almost linear upper bounds on the length λ_s(n) of Davenport—Schinzel sequences composed ofn symbols in which no alternating subsequence is of length greater thans+1. These bounds are of the formO(nα(n)^O(α(n)5-3)), and they generalize and extend the tight bound Θ(nα(n)) obtained by Hart and Sharir for the special cases=3 (α(n) is the functional inverse of Ackermann’s function), and also improve the upper boundO(n log*n) due to Szemerédi. Work on this paper has been supported in part by a grant from the U.S. — Israeli Binational Science Foundation.     

Distribution of Nonlinear Congruential Pseudorandom Numbers Modulo Almost Squarefree Integers

The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. In this paper we present a new bound on the s-dimensional discrepancy of nonlinear congruential pseudorandom numbers over the residue ring \Bbb Z_M{\Bbb Z}_M modulo M for an “almost squarefree” integer M. It is useful to recall that almost all integers are of this type. Moreover, if the generator is associated with a permutation polynomial over \Bbb Z_M{\Bbb Z}_M we obtain a stronger bound “on average” over all initial values. This bound is new even in the case when M = p is prime.     

p-convergence in measure of a sequence of measurable functions and corresponding minimal elements of c 0

We characterize convergence in measure of a sequence (f_n)_n of measurable functions to a measurable function f by elements of c₀, which express the quality of convergence of (f_n)_n to f. This characterization motivates the introduction of a new notion of convergence, called “p-convergence in measure” (p > 0), which is stronger than convergence in measure. We prove the existence of “minimal” elements in c₀ which characterize the convergence in measure of (f_n)_n to f.      

Cantor set and interpolation

In 1998, Y. Benyamini published interesting results concerning interpolation of sequences using continuous functions ℝ → ℝ. In particular, he proved that there exists a continuous function ℝ → ℝ which in some sense “interpolates” all sequences (x _n ) _n∈ℤ ∈ [0, 1]^ℤ “simultaneously.” In 2005, M.R. Naulin and C. Uzcátegui unified and generalized Benyamini’s results. In this paper, the case of topological spaces X and Y with an Abelian group acting on X is considered. A similar problem of “simultaneous interpolation” of all “generalized sequences” using continuous mappings X → Y is posed. Further generalizations of Naulin-Uncátegui theorems, in particular, multidimensional analogues of Benyamini’s results are obtained.     

Ramsey Theory and Bandwidth of Graphs

 The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log ₂ n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”. Received: September 2, 1998?Final version received: November 29, 1999     

Singular Probability Distributions and Fractal Properties of Sets of Real Numbers Defined by the Asymptotic Frequencies of Their <Emphasis Type="Italic">s</Emphasis>-Adic Digits

Properties of the set T _s of “particularly nonnormal numbers” of the unit interval are studied in detail (T _s consists of real numbers x some of whose s-adic digits have the asymptotic frequencies in the nonterminating s-adic expansion of x, and some do not). It is proved that the set T _s is residual in the topological sense (i.e., it is of the first Baire category) and is generic in the sense of fractal geometry (T _s is a superfractal set, i.e., its Hausdorff-Besicovitch dimension is equal to 1). A topological and fractal classification of sets of real numbers via analysis of asymptotic frequencies of digits in their s-adic expansions is presented. Dedicated to V. S. Korolyuk on occasion of his 80th birthday __________ Published in Ukrains'kyi Matematychnyi Zhurnal, Vol. 57, No. 9, pp. 1163–1170, September, 2005.     

Banach spaces and groups — Order properties and universal models

We deal with two natural examples of almost-elementary classes: the class of all Banach spaces (over ℝ or ℂ) and the class of all groups. We show that both of these classes do not have the strict order property, and find the exact place of each one of them in Shelah’sSOP _n (strong order property of ordern) hierarchy. Remembering the connection between this hierarchy and the existence of universal models, we conclude, for example, that there are “few” universal Banach spaces (under isometry) of regular density characters. This publication is numbered 789 in the list of publications of Saharon Shelah. The research was supported by The Israel Science Foundation.     

Measure theory of statistical convergence

The question of establishing measure theory for statistical convergence has been moving closer to center stage, since a kind of reasonable theory is not only fundamental for unifying various kinds of statistical convergence, but also a bridge linking the studies of statistical convergence across measure theory, integration theory, probability and statistics. For this reason, this paper, in terms of subdifferential, first shows a representation theorem for all finitely additive probability measures defined on the σ-algebra of all subsets of N, and proves that every such measure can be uniquely decomposed into a convex combination of a countably additive probability measure and a statistical measure (i.e. a finitely additive probability measure μ with μ(k) = 0 for all singletons {k}). This paper also shows that classical statistical measures have many nice properties, such as: The set of all such measures endowed with the topology of point-wise convergence on forms a compact convex Hausdorff space; every classical statistical measure is of continuity type (hence, atomless), and every specific class of statistical measures fits a complementation minimax rule for every subset in N. Finally, this paper shows that every kind of statistical convergence can be unified in convergence of statistical measures. This work was supported by the National Natural Science Foundation of China (Grant Nos. 10771175, 10471114)     

Complete moment and integral convergence for sums of negatively associated random variables

For a sequence of identically distributed negatively associated random variables {Xn; n ≥ 1} with partial sums Sn = ∑i=1^n Xi, n ≥ 1, refinements are presented of the classical Baum-Katz and Lai complete convergence theorems. More specifically, necessary and sufficient moment conditions are provided for complete moment convergence of the form ∑n≥n0 n^r-2-1/pq anE（max1≤k≤n｜Sk｜^1/q-∈bn^1/qp）^＋〈∞to hold where r 〉 1, q 〉 0 and either n0 = 1,0 〈 p 〈 2, an = 1,bn = n or n0 = 3,p = 2, an = 1 （log n） ^1/2q, bn=n log n. These results extend results of Chow and of Li and Spataru from the indepen- dent and identically distributed case to the identically distributed negatively associated setting. The complete moment convergence is also shown to be equivalent to a form of complete integral convergence.     

Large deviations for random walks on Galton–Watson trees: averaging and uncertainty

 In the study of large deviations for random walks in random environment, a key distinction has emerged between quenched asymptotics, conditional on the environment, and annealed asymptotics, obtained from averaging over environments. In this paper we consider a simple random walk {X _n } on a Galton–Watson tree T, i.e., on the family tree arising from a supercritical branching process. Denote by |X _n | the distance between the node X _n and the root of T. Our main result is the almost sure equality of the large deviation rate function for |X _n |/n under the “quenched measure” (conditional upon T), and the rate function for the same ratio under the “annealed measure” (averaging on T according to the Galton–Watson distribution). This equality hinges on a concentration of measure phenomenon for the momentum of the walk. (The momentum at level n, for a specific tree T, is the average, over random walk paths, of the forward drift at the hitting point of that level). This concentration, or certainty, is a consequence of the uncertainty in the location of the hitting point. We also obtain similar results when {X _n } is a λ-biased walk on a Galton–Watson tree, even though in that case there is no known formula for the asymptotic speed. Our arguments rely at several points on a “ubiquity” lemma for Galton–Watson trees, due to Grimmett and Kesten (1984). Received: 15 November 2000 / Revised version: 27 February 2001 / Published online: 19 December 2001     

r-entropy,equipartition, and Ornstein’s isomorphism theorem inR n

A new approach is given to the entropy of a probability-preserving group action (in the context ofZ and ofR _n ), by defining an approximate “r-entropy”, 0<r<1, and lettingr → 0. If the usual entropy may be described as the growth rate of the number of essential names, then ther-entropy is the growth rate of the number of essential “groups of names” of width≦r, in an appropriate sense. The approach is especially useful for actions of continuous groups. We apply these techniques to state and prove a “second order” equipartition theorem forZ _m ×R _n and to give a “natural” proof of Ornstein’s isomorphism theorem for Bernoulli actions ofZ _m ×R _n , as well as a characterization of such actions which seems to be the appropriate generalization of “finitely determined”.     

On the minimal free resolution of finite sets in P N

Here we construct many possible free resolutions fors points inP ⁿ . In suitable ranges we construct configurations of points with “good” minimal free resolution and other configurations for which the difference with respect to a “good” resolution is prescribed in advance.     

Lempel–Ziv Factorization Using Less Time & Space

For 30 years the Lempel–Ziv factorization LZ _x of a string x = x[1..n] has been a fundamental data structure of string processing, especially valuable for string compression and for computing all the repetitions (runs) in x. Traditionally the standard method for computing LZ _x was based on Θ(n)-time (or, depending on the measure used, O(n log n)-time) processing of the suffix tree ST _x of x. Recently Abouelhoda et al. proposed an efficient Lempel–Ziv factorization algorithm based on an “enhanced” suffix array – that is, a suffix array SA _x together with supporting data structures, principally an “interval tree”. In this paper we introduce a collection of fast space-efficient algorithms for LZ factorization, also based on suffix arrays, that in theory as well as in many practical circumstances are superior to those previously proposed; one family out of this collection achieves true Θ(n)-time alphabet-independent processing in the worst case by avoiding tree structures altogether. The work of the first and third authors was supported in part by grants from the Natural Sciences & Engineering Research Council of Canada.     

Convergence theorems for the Birkhoff integral

We give sufficient conditions for the interchange of the operations of limit and the Birkhoff integral for a sequence (f _n ) of functions from a measure space to a Banach space. In one result the equi-integrability of f _n ’s is involved and we assume f _n → f almost everywhere. The other result resembles the Lebesgue dominated convergence theorem where the almost uniform convergence of (f _n ) to f is assumed.     

Random ergodic theorems and real cocycles

We study mean convergence of ergodic averages associated to a measure-preserving transformation or flow τ along the random sequence of times κ _n (ω) given by the Birkhoff sums of a measurable functionF for an ergodic measure-preserving transformationT. We prove that the sequence (k _n(ω)) is almost surely universally good for the mean ergodic theorem, i.e., that, for almost every, ω, the averages (*) converge for every choice of τ, if and only if the “cocycle”F satisfies a cohomological condition, equivalent to saying that the eigenvalue group of the “associated flow” ofF is countable. We show that this condition holds in many natural situations. When no assumption is made onF, the random sequence (k _n(ω)) is almost surely universally good for the mean ergodic theorem on the class of mildly mixing transformations τ. However, for any aperiodic transformationT, we are able to construct an integrable functionF for which the sequence (k _n(ω)) is not almost surely universally good for the class of weakly mixing transformations.     

Simplex-valued probability

We continue our study of generalized probability from the viewpoint of category theory. Assuming that each generalized probability measure is a morphism, we model basic probabilistic notions within the category cogenerated by its range. It is known that the closed unit interval I = [0, 1], carrying a suitable difference structure, cogenerates the category ID in which the classical and fuzzy probability theories can be modeled. We study generalized probability theories modeled within two different categories cogenerated by a simplex S _n = {(x ₁, x ₂, …, x _n ) ∈ I _n : $ \mathop \sum \limits_{i = 1}^n $ \mathop \sum \limits_{i = 1}^n x i ≤ 1}, carrying a suitable difference structure; since I and S ₁ coincide, for n = 1 we get the fuzzy probability theory as a special case. In the first case, when the morphisms preserve the so-called pure elements, the resulting category S _n D, n > 1, and ID are isomorphic and the generalized probability theories modeled in ID and S _n D are “the same”. In the second case, when the morphisms map each maximal element to a maximal element, the resulting categories WS _n D, n > 1, lead to different models of generalized probability theories. We define basic notions of the corresponding simplex-valued probability theories and mention some applications.     

Entropy structure

Investigating the emergence of entropy on different scales, we propose an “entropy structure” as a kind of master invariant for the entropy theory of topological dynamical systems. An entropy structure is a sequence of functionsh _k on the simplex of invariant measures which converges to the entropy functionh and which falls into a distinguished equivalence class defined by a natural equivalence relation capturing the “type of nonuniformity in convergence”. An entropy structure recovers several existing invariants, including the symbolic extension entropy h_sex and the Misiurewicz parameter h^*. Entropy theories of Misiurewicz, Katok, Brin—Katok, Newhouse, Romagnoli, Ornstein—Weiss and others all yield candidate sequences (h _k); we determine which of these exhibit the correct type of convergence and hence become entropy structures. One of the satisfactory sequences arises from a new treatment of entropy theory strictly in terms of continuous functions (in place of partitions or covers). The results allow the computation of symbolic extension entropy without reference to zero dimensional extensions. New light is shed on the property of asymptotich-expansiveness. Supported by the KBN grant 2 P03 A 04622.     

Siegel modular forms and representations

This paper explicitly describes the procedure of associating an automorphic representation of PGSp(2n,?) with a Siegel modular form of degree n for the full modular group Γ _n =Sp(2n,ℤ), generalizing the well-known procedure for n=1. This will show that the so-called “standard” and ldquo;spinor”L-functions associated with such forms are obtained as Langlands L-functions. The theory of Euler products, developed by Langlands, applied to a Levi subgroup of the exceptional group of type F _<4, is then used to establish meromorphic continuation for the spinor L-function when n=3. Received: 28 March 2000 / Revised version: 25 October 2000     

Waring’s problem with digital restrictions

The aim of this paper is to consider an analogue of Waring’s problem with digital restrictions. In particular, we prove the following result. Lets _q (n) be theq-adic sum of digits function and leth,m be fixed positive integers. Then fors>2 ^k there existsn ₀∈ℕ such that each integern≥n ₀ has a representation of the form We will even give an asymptotic formula for the number of representations ofn in this way. The result is shown with help of the circle method in combination with a “digital” version of Weyl’s Lemma. Dedicated to Professor Hillel Furstenberg The first author was supported by the Austrian Science Foundation project S8310. The second author was supported by the Austrian Science Foundation project S8308.