Convergence of mock Fourier series

For certain Cantor measures μ on ℝⁿ, it was shown by Jorgensen and Pedersen that there exists an orthonormal basis of exponentialse ^2πiγ·x for λεΛ. a discrete subset of ℝⁿ called aspectrum for μ. For anyL ¹ functionf, we define coefficientsc _γ(f)=∝f(y)e ^−2πiγiy dμ(y) and form the Mock Fourier series ∑_λ∈Λ^cλ(f)e ^2πiλ·x . There is a natural sequence of finite subsets Λ_n increasing to Λ asn→∞, and we define the partial sums of the Mock Fourier series by We prove, under mild technical assumptions on μ and Λ, thats _n(f) converges uniformly tof for any continuous functionf and obtain the rate of convergence in terms of the modulus of continuity off. We also show, under somewhat stronger hypotheses, almost everywhere convergence forfεL ¹. Research supported in part by the National Science Foundation, Grant DMS-0140194.     

Algebraic polynomials least deviating from zero in measure on a segment

We investigate the problem of algebraic polynomials with given leading coefficients that deviate least from zero on the segment [–1, 1] with respect to a measure, or, more precisely, with respect to the functional μ(f) = mes{x ∈ [–1, 1]: ∣f (x)∣ ≥ 1}. We also discuss an analogous problem with respect to the integral functionals ∫_–1¹ φ (∣f (x)∣) dx for functions φ that are defined, nonnegative, and nondecreasing on the semiaxis [0, +∞).     

Large Monotone Paths in Graphs with Bounded Degree

 We prove that for every ε>0 and positive integer r, there exists Δ₀=Δ₀(ε) such that if Δ>Δ₀ and n>n(Δ,ε,r) then there exists a packing of K _n with ⌊(n−1)/Δ⌋ graphs, each having maximum degree at most Δ and girth at least r, where at most εn ² edges are unpacked. This result is used to prove the following: Let f be an assignment of real numbers to the edges of a graph G. Let α(G,f) denote the maximum length of a monotone simple path of G with respect to f. Let α(G) be the minimum of α(G,f), ranging over all possible assignments. Now let α_Δ be the maximum of α(G) ranging over all graphs with maximum degree at most Δ. We prove that Δ+1≥α_Δ≥Δ(1−o(1)). This extends some results of Graham and Kleitman [6] and of Calderbank et al. [4] who considered α(K _n ). Received: March 15, 1999?Final version received: October 22, 1999     

Testing linear operators—An average case study

Given a specification linear operatorS, we want to test an implementation linear operatorA and determine whether it conforms to the specification operator according to an error criterion. In an earlier paper [3], we studied a worst case error in which we test whether the error is no more than a given bound ε>0 for all elements in a given setF, i.e., sup _{fεf∥Sf—Af∥≤ε}. In this work, we study the average error instead, i. e., ∫ _F ∥Sf-Af∥²μ(df)ɛ≤², where μ is a probability measure onF. We assume that an upper boundK on the norm of the difference ofS andA is given a priori. It turns out that any finite number of tests is in general inconclusive with the average error. Therefore, as in the worst case, we allow a relaxation parameter α>0 and test for weak conformance with an error bound (1+α)ε. Then a finite number of tests from an arbitrary orthogonal complete sequence is conclusive. Furthermore, the eigenvectors of the covariance operatorC _μ of the probability measure μ provide an almost optimal test sequence. This implies that the test set isuniversal; it only depends on the set of valid inputsF and the measure μ, and is independent ofS, A, and the other parameters of the problem. However, the minimal number of tests does depend on all the parameters of the testing problem, i.e., ε, α,K, and the eigenvalues ofC _μ. In contrast to the worst case setting, it also depends on the dimensiond of the range space ofS andA. This work was done while consulting at Bell Laboratories, and is partially supported by the National Science Foundation and the Air Force Office of Scientific Research.     

Fuzzy sets and join spaces associated with rough sets

Let μ _X be the rough membership function. One compares μ _A with μ_A∪B and μ_A∪B, by the associated hyperoperations. One finds a condition such that a functionμ ε [0, 1] ^H may be a rough membership function.     

Generalized convexity and concavity of the optimal value function in nonlinear programming

In this paper we consider generalized convexity and concavity properties of the optimal value functionf ^* for the general parametric optimization problemP(_ε) of the form min _x f(x, ε) s.t.x∈R(ε). Many results on convexity and concavity characterizations off ^* were presented by the authors in a previous paper. Such properties off ^* and the solution set mapS ^* form an important part of the theoretical basis for sensitivity, stability and parametric analysis in mathematical optimization. We give sufficient conditions for several types of generalized convexity and concavity off ^*, in terms of respective generalized convexity and concavity assumptions onf and convexity and concavity assumptions on the feasible region point-to-set mapR. Specializations of these results to the parametric inequality-equality constrained nonlinear programming problem are provided. Research supported by Grant ECS-8619859, National Science Foundation and Contract N00014-86-K-0052, Office of Naval Research.     

Cramér-type conditions and quadratic mean differentiability

Summary Let (Ω,A) be a measurable space, let Θ be an open set inR ^k , and let {P _θ; θ∈Θ} be a family of probability measures defined onA. Let μ be a σ-finite measure onA, and assume thatP _θ≪μ for each θ∈Θ. Let us denote a specified version ofdP _θ /d _μ byf(ω; θ). In many large sample problems in statistics, where a study of the log-likelihood is important, it has been convenient to impose conditions onf(ω; θ) similar to those used by Cramér [2] to establish the consistency and asymptotic normality of maximum likelihood estimates. These are of a purely analytical nature, involving two or three pointwise derivatives of lnf(ω; θ) with respect to θ. Assumptions of this nature do not have any clear probabilistic or statistical interpretation. In [10], LeCam introduced the concept of differentially asymptotically normal (DAN) families of distributions. One of the basic properties of such a family is the form of the asymptotic expansion, in the probability sense, of the log-likelihoods. Roussas [14] and LeCam [11] give conditions under which certain Markov Processes, and sequences of independent identically distributed random variables, respectively, form DAN families of distributions. In both of these papers one of the basic assumptions is the differentiability in quadratic mean of a certain random function. This seems to be a more appealing type of assumption because of its probabilistic nature. In this paper, we shall prove a theorem involving differentiability in quadratic mean of random functions. This is done in Section 2. Then, by confining attention to the special case when the random function is that considered by LeCam and Roussas, we will be able to show that the standard conditions of Cramér type are actually stronger than the conditions of LeCam and Roussas in that they imply the existence of the necessary quadratic mean derivative. The relevant discussion is found in Section 3. This research was supported by the National Science Foundation, Grant GP-20036.     

Almost everywhere convergence of Cesàro means of Fourier series on the group of 2-adic integers

We prove the almost everywhere convergence of the Cesàro (C, α)-means of integrable functions σ _n ^α f → f for f ∈ L ¹(I), where I is the group of 2-adic integers for every α > 0. This theorem for the case of α = 1 was proved by the author [1]. For the case of the (C, 1) Fejér means there are several generalizations known with respect to some orthonormal systems. One could mention the papers [2, 9]. Research supported by the Hungarian National Foundation for Scientific Research (OTKA), grant no. T 048780.     

Hilbert’s irreducibility theorem for prime degree and general polynomials

Letf (X, t)εℚ[X, t] be an irreducible polynomial. Hilbert’s irreducibility theorem asserts that there are infinitely manyt ₀εℤ such thatf (X, t ₀) is still irreducible. We say thatf (X, t) isgeneral if the Galois group off (X, t) over ℚ(t) is the symmetric group in its natural action. We show that if the degree off with respect toX is a prime ≠ 5 or iff is general of degree ≠ 5, thenf (X, t ₀) is irreducible for all but finitely manyt ₀εℤ unless the curve given byf (X, t)=0 has infinitely many points (x ₀,t ₀) withx ₀εℚ,t ₀εℤ. The proof makes use of Siegel’s theorem about integral points on algebraic curves, and classical results about finite groups, going back to Burnside, Schur, Wielandt, and others. Supported by the DFG.     

Pressure and equilibrium states for countable state markov shifts

We give a general definition of the topological pressureP _top (f, S) for continuous real valued functionsf: X→ℝ on transitive countable state Markov shifts (X, S). A variational principle holds for functions satisfying a mild distortion property. We introduce a new notion of Z-recurrent functions. Given any such functionf, we show a general method how to obtain tight sequences of invariant probability measures supported on periodic points such that a weak accumulation pointμ is an equilibrium state forf if and only if εf ⁻ dμ<∞. We discuss some conditions that ensure this integrability. As an application we obtain the Gauss measure as a weak limit of measures supported on periodic points.     

Estimates for parametric Marcinkiewicz integrals in BMO and Campanato spaces

In this paper, the authors consider the behaviors of a class of parametric Marcinkiewicz integrals μ _Ω ^ρ , μ _Ω,λ ^*,ρ and μ _Ω,S ^ρ on BMO(ℝ ⁿ ) and Campanato spaces with complex parameter ρ and the kernel Ω in Llog⁺ L(S ⁿ⁻¹). Here μ _Ω,λ ^*,ρ and μ _Ω,S ^ρ are parametric Marcinkiewicz functions corresponding to the Littlewood-Paley g _λ *-function and the Lusin area function S, respectively. Under certain weak regularity condition on Ω, the authors prove that if f belongs to BMO(ℝ ⁿ ) or to a certain Campanato space, then [μ _Ω,λ ^*,ρ (f)]², [μ _Ω,S ^ρ (f)]² and [μ _Ω ^ρ (f)]² are either infinite everywhere or finite almost everywhere, and in the latter case, some kind of boundedness are also established.     

A recurrence property of smooth functions

LetP andQ be real polynomials of degreesd ande, respectively, andf a periodic function. It is shown that, iff iss times differentiable atQ(0), wheres≧7de ³ log 14e ³, then for every ɛ>0 the diophantine inequality ≧FF5C;P(x)f(Q(x)) -P(0)f(Q(0)) -y≧ εx≠0, has a solution. This settles in particular a question raised by Furstenberg and Weiss [6].     

Parabolic Implosion and Julia-Lavaurs Sets in the Exponential Family

We deal with all the maps from the exponential family f _ε(z) = (e ⁻¹ + ε)exp(z), with ε ≥ 0. Let h _ε = HD(J _r,ε) be the Hausdorff dimension of the radial Julia sets J _r,ε. Observing the phenomenon of parabolic implosion, it is shown that the function ε ↦ h _ε is not continuous from the right.     

Extensions of the measurable choice theorem by means of forcing

Using the method of forcing of set theory, we prove the following two theorems on the existence of measurable choice functions: LetT be the closed unit interval [0,1] and letm be the usual Lebesgue measure defined on the Borel subsets ofT. Theorem1. LetS⊂T×T be a Borel set such that for alltεT,S _t ^def={x|(t,x)εS} is countable and non-empty. Then there exists a countable series of Lebesgue-measurable functionsf _n: T→T such thatS _t={f_n(t)|nεω} for alltε[0,1],W _x={y|(x,y)εW} is uncountable. Then there exists a functionh:[0,1]×[0,1]→W with the following properties: (a) for each xε[0,1], the functionh(x,·) is one-one and ontoW _x and is Borel measurable; (b) for eachy, h(·, y) is Lebesgue measurable; (c) the functionh is Lebesgue measurable.     

Parabolic Implosion and Julia-Lavaurs Sets in the Exponential Family

We deal with all the maps from the exponential family f _ε(z) = (e ⁻¹ + ε)exp(z), with ε ≥ 0. Let h _ε = HD(J _r,ε) be the Hausdorff dimension of the radial Julia sets J _r,ε. Observing the phenomenon of parabolic implosion, it is shown that the function ε ↦ h _ε is not continuous from the right. The research of the first author was supported in part by the NSF Grant DMS 0100078.     

Vague convergence of sums of independent random variables

A sequence (μ _n) of probability measures on the real line is said to converge vaguely to a measureμ if∫ fdμ _n →∫ fdμ for every continuous functionf withcompact support. In this paper one investigates problems analogous to the classical central limit problem under vague convergence. Let ‖μ‖ denote the total mass ofμ andδ ₀ denote the probability measure concentrated in the origin. For the theory of infinitesimal triangular arrays it is true in the present context, as it is in the classical one, that all obtainable limit laws are limits of sequences of infinitely divisible probability laws. However, unlike the classical situation, the class of infinitely divisible laws is not closed under vague convergence. It is shown that for every probability measureμ there is a closed interval [0,λ], [0,e ⁻¹] ⊂ [0,λ] ⊂ [0, 1], such thatβμ is attainable as a limit of infinitely divisible probability laws iffβ ε [0,λ]. In the independent identically distributed case, it is shown that if (x ₁ + ... +x _n)/a _n, a_n → ∞, converges vaguely toμ with 0<‖μ‖<1, thenμ=‖μ‖δ ₀. If furthermore the ratiosa _n+1/a _n are bounded above and below by positive numbers, thenL(x)=P[|X ₁|>x] is a slowly varying function ofx. Conversely, ifL(x) is slowly varying, then for everyβ ε (0, 1) one can choosea _n → ∞ so that the limit measure=βδ ₀. To the memory of Shlomo Horowitz This research was partially supported by the National Science Foundation.     

Another View of the CLT in Banach Spaces

Let B denote a separable Banach space with norm ‖⋅‖, and let μ be a probability measure on B for which linear functionals have mean zero and finite variance. Then there is a Hilbert space H _μ determined by the covariance of μ such that H _μ ⊆B. Furthermore, for all ε>0 and x in the B-norm closure of H _μ , there is a unique point, T _ε (x), with minimum H _μ -norm in the B-norm ball of radius ε>0 and center x. If X is a random variable in B with law μ, then in a variety of settings we obtain the central limit theorem (CLT) for T _ε (X) and certain modifications of such a quantity, even when X itself fails the CLT. The motivation for the use of the mapping T _ε (⋅) comes from the large deviation rates for the Gaussian measure γ determined by the covariance of X whenever γ exists. However, this is only motivation, and our results apply even when this Gaussian law fails to exist. Research partially supported by NSA Grant H98230-06-1-0053.     

On the solutions of the translation equation in rings of formal power series

We study in this paper solutions of the translation equation in rings of formal power series K[X] where K ∈R, C (so called one-parameter groups or flows), and even, more generally, homomorphisms Ф from an abelian group (G, +) into the group Г(K) of invertible power series in K[X]. This problem can equivalently be formulated as the question of constructing homomorphisms Ф from (G, +) into the differential group Г¹∞ describing the chain rules of higher order of C∞ functions with fixed point 0. In this paper we present the general form of these homomorphisms Ф : G → Г(K) (or L¹∞),Ф = (f_n ⁿ≤1,forwhich f₁ = l, f₂ = ... = f_p+l =0,f_p+2 ≠ 0 for fixed, but arbitrary p ≤ 0 (see Theorem 5, Corollary 6 and Theorem 6). This representation uses a sequence (w _n ^p )_n≥p+2 of universal polynomials in f_p+2 and a sequence of parameters, which determines the individual one-parameter group. Instead of (w _n ^p )_n≥p+2 we may also use another sequence (L _n ^p )_n≥p+2 of universal polynomials, and we describe the connection between these forms of the solutions.     

Testing of matrix-poset properties

Combinatorial property testing, initiated by Rubinfeld and Sudan [23] and formally defined by Goldreich, Goldwasser and Ron in [18], deals with the following relaxation of decision problems: Given a fixed property P and an input f, distinguish between the case that f satisfies P, and the case that no input that differs from f in less than some fixed fraction of the places satisfies P. An (ε, q)-test for P is a randomized algorithm that queries at most q places of an input f and distinguishes with probability 2/3 between the case that f has the property and the case that at least an ε-fraction of the places of f need to be changed in order for it to have the property. Here we concentrate on labeled, d-dimensional grids, where the grid is viewed as a partially ordered set (poset) in the standard way (i.e. as a product order of total orders). The main result here presents an (ε, poly(1/ε))-test for every property of 0/1 labeled, d-dimensional grids that is characterized by a finite collection of forbidden induced posets. Such properties include the “monotonicity” property studied in [9,8,13], other more complicated forbidden chain patterns, and general forbidden poset patterns. We also present a (less efficient) test for such properties of labeled grids with larger fixed size alphabets. All the above tests have in addition a 1-sided error probability. This class of properties is related to properties that are defined by certain first order formulae with no quantifier alternation over the syntax containing the grid order relations. We also show that with one quantifier alternation, a certain property can be defined, for which no test with query complexity of O(n ^1/4) (for a small enough fixed ε) exists. The above results identify new classes of properties that are defined by means of restricted logics, and that are efficiently testable. They also lay out a platform that bridges some previous results. A preliminary version of these results formed part of [14]. Research supported in part by grant 55/03 from the Israel Science Foundation.     

Higher order Riesz transforms associated with Bessel operators

In this paper we investigate Riesz transforms R _μ ^(k) of order k≥1 related to the Bessel operator Δ_μ f(x)=-f”(x)-((2μ+1)/x)f’(x) and extend the results of Muckenhoupt and Stein for the conjugate Hankel transform (a Riesz transform of order one). We obtain that for every k≥1, R _μ ^(k) is a principal value operator of strong type (p,p), p∈(1,∞), and weak type (1,1) with respect to the measure dλ(x)=x ^2μ+1  dx in (0,∞). We also characterize the class of weights ω on (0,∞) for which R _μ ^(k) maps L ^p (ω) into itself and L ¹(ω) into L ^1,∞(ω) boundedly. This class of weights is wider than the Muckenhoupt class of weights for the doubling measure dλ. These weighted results extend the ones obtained by Andersen and Kerman.