Companions of the inequalities of Fejér--Jackson and Young

Summary Applications of some well-known theorems of Jackson and Young lead to the sharp inequalities -1<ⁿ_k-1Σ(cos(kx)+sin(kx))/k (n ≥1; 1<x<π) and -1/2Si(π)<ⁿ_k-1Σ(cos(kx)·sin(kx))/k (n ≥1; xЄR) We prove that the following counterpart is valid for all integers n ≥1 and real numbers xЄ (0, π): -3/2≤ⁿ_k-1Σ(cos(kx)-sin(kx))/k where the sign of equality holds if and only if n =2 and x = π /2.     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

A recurrence relation for the square root

The behavior of the sequence x_{n + 1} = x_n(3N − x_n²)/2N is studied for N > 0 and varying real x₀. When 0 < x₀ < (3N)^1/2 the sequence converges quadratically to N^1/2. When x₀ > (5N)^1/2 the sequence oscillates infinitely. There is an increasing sequence β_r, with β₋₁ = (3N)^1/2 which converges to (5N)^1/2 and is such that when β_r < x₀ < β_{r + 1} the sequence {x_n} converges to (−1)^rN^1/2. For x₀ = 0, β₋₁, β₀,… the sequence converges to 0. For x₀ = (5N)^1/2 the sequence oscillates: x_n = (−1)ⁿ(5N)^1/2. The behavior for negative x₀ is obtained by symmetry.     

On deviations between empirical and quantile processes for mixing random variables

Let {X_n} be a strictly stationary φ-mixing process with Σ_j=1^∞ φ^1/2(j) < ∞. It is shown in the paper that if X₁ is uniformly distributed on the unit interval, then, for any t [0, 1], |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log log n)^3/4) a.s. and sup_0≤t≤1 |F_n⁻¹(t) − t + F_n(t) − t| = (O(n^−3/4(log n)^1/2(log log n)^1/4) a.s., where F_n and F_n⁻¹(t) denote the sample distribution function and tth sample quantile, respectively. In case {X_n} is strong mixing with exponentially decaying mixing coefficients, it is shown that, for any t [0, 1], |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log n)^1/2(log log n)^3/4) a.s. and sup_0≤t≤1 |F_n⁻¹(t) − t + F_n(t) − t| = O(n^−3/4(log n)(log log n)^1/4) a.s. The results are further extended to general distributions, including some nonregular cases, when the underlying distribution function is not differentiable. The results for φ-mixing processes give the sharpest possible orders in view of the corresponding results of Kiefer for independent random variables.     

Off-line dynamic maintenance of the width of a planar point set

Agarwal, P.K. and M. Sharir, Off-line dynamic maintenance of the width of a planar point set, Computational Geometry: Theory and Applications 1 (1990) 65-78. In this paper we present an efficient algorithm for the off-line dynamic maintenance of the width of a planar point set in the following restricted case: We are given a real parameter W and a sequence Σ=(σ₁,...,σ_n) of n insert and delete operations on a set S of points in ², initially consisting of n points, and we want to determine whether there is an i such that the width of S the ith operation is less than or equal to W. Our algorithm runs in time O(nlog³n) and uses O(n) space.     

On the L convergence of Lagrange interpolating entire functions of exponential type

Let f: be a continuous, 2π-periodic function and for each n ε let t_n(f; ·) denote the trigonometric polynomial of degree n interpolating f in the points 2kπ/(2n + 1) (k = 0, ±1, …, ±n). It was shown by J. Marcinkiewicz that lim_{n → ∞} ∝₀^2π¦f(θ) − t_n(f θ)¦^p dθ = 0 for every p > 0. We consider Lagrange interpolation of non-periodic functions by entire functions of exponential type τ > 0 in the points kπ/τ (k = 0, ± 1, ± 2, …) and obtain a result analogous to that of Marcinkiewicz.     

Cesàro Asymptotics for Orthogonal Polynomials on the Unit Circle and Classes of Measures

The convergence in L²( ) of the even approximants of the Wall continued fractions is extended to the Cesàro–Nevai class CN, which is defined as the class of probability measures σ with lim_n→∞ ∑ⁿ⁻¹_k=0 |a_k|=0, {a_n}_n0 being the Geronimus parameters of σ. We show that CN contains universal measures, that is, probability measures for which the sequence {|_n|² dσ}_n0 is dense in the set of all probability measures equipped with the weak-* topology. We also consider the “opposite” Szeg class which consists of measures with ∑^∞_n=0 (1−|a_n|²)^1/2<∞ and describe it in terms of Hessenberg matrices.     

Commutative Extended Complex Numbers and Connected Trigonometry

In order to construct an extension of the complex numbers, we consider an n-dimensional commutative algebra generated by the n vectors 1, e, ..., eⁿ⁻¹ where the fundamental element satisfies the basic relation eⁿ = −1. These spaces can be classified according to the values of n: prime number, power of a prime number, general number. The question of the invertibility leads to the definition of a pseudo-norm for which the triangle inequality is not satisfied (the n = 1, 2 cases excepted). When one tries to pass from the polar form the cartesian one, one obtains functions generalizing the usual circular and hyperbolic functions and their inverse. The extended sine and hyperbolic sine functions thus constructed satisfy a determinantal-type relation and they lay the foundation of a new trigonometry for which summation and derivative formulas are given. An extended 2π quantity is defined as the periodicity of the generalized circular functions. This formalism is applied to solve the nth order differential equations (∑ⁿ⁻¹_i=1 (∂n/∂φⁿ_i) ± ω) ƒ(φ) = 0. As a further application, the solutions of the n-laplacian operator are derived.     

The complexity of finding generalized paths in tournaments

Given a tournament with n vertices, we consider the number of comparisons needed, in the worst case, to find a permutation υ₁υ₂…υ_n of the vertices, such that the results of the games υ₁υ₂, υ₂υ₃,…, υ_n−1υ_n match a prescribed pattern. If the pattern requires all arcs to go forwrd, i.e., υ₁ → υ₂, υ₂ → υ₃,…, υ_n−1 → υ_n, and the tournament is transitive, then this is essentially the problem of sorting a linearly ordered set. It is well known that the number of comparisons required in this case is at least cn lg n, and we make the observation that O(n lg n) comparisons suffice to find such a path in any (not necessarily transitive) tournament. On the other hand, the pattern requiring the arcs to alternate backward-forward-backward, etc., admits an algorithm for which O(n) comparisons always suffice. Our main result is the somewhat surprising fact that for various other patterns the complexity (number of comparisons) of finding paths matching the pattern can be cn lg^αn for any α between 0 and 1. Thus there is a veritable spectrum of complexities, depending on the prescribed pattern of the desired path. Similar problems on complexities of algorithms for finding Hamiltonian cycles in graphs and directed graphs have been considered by various authors, [2, pp. 142, 148, 149; 4].     

A Randomized Parallel Algorithm for Planar Graph Isomorphism

We present a parallel randomized algorithm running on aCRCW PRAM, to determine whether two planar graphs are isomorphic, and if so to find the isomorphism. We assume that we have a tree of separators for each planar graph (which can be computed by known algorithms inO(log² n) time withn^{1 + ε}processors, for any ε > 0). Ifnis the number of vertices, our algorithm takesO(log(n)) time with processors and with a probability of failure of 1/nat most. The algorithm needs 2 · log(m) − log(n) + O(log(n)) random bits. The number of random bits can be decreased toO(log(n)) by increasing the number of processors ton^{3/2 + ε}, for any ε > 0. Our parallel algorithm has significantly improved processor efficiency, compared to the previous logarithmic time parallel algorithm of Miller and Reif (Siam J. Comput.20(1991), 1128–1147), which requiresn⁴randomized processors orn⁵deterministic processors.     

Asymptotic expansions in the conditional central limit theorem

Let X_n, n , be i.i.d. with mean 0, variance 1, and E(¦X_n¦^r) < ∞ for some r 3. Assume that Cramér's condition is fulfilled. We prove that the conditional probabilities P(1/√n Σ_{i = 1}ⁿ X_i t¦B) can be approximated by a modified Edgeworth expansion up to order o(1/n^{(r − 2)/2)}), if the distances of the set B from the σ-fields σ(X₁, …, X_n) are of order O(1/n^{(r − 2)/2)}(lg n)^β), where β < −(r − 2)/2 for r and β < −r/2 for r . An example shows that if we replace β < −(r − 2)/2 by β = −(r − 2)/2 for r (β < −r/2 by β = −r/2 for r ) we can only obtain the approximation order O(1/n^{(r − 2)/2)}) for r (O(lg lgn/n^{(r − 2)/2)}) for r ).     

Instability of the Rossby–Haurwitz wave in the invariant sets of perturbations

Stability of the Rossby–Haurwitz (RH) wave of subspace H₁H_n in an ideal incompressible fluid on a rotating sphere is analytically studied (H_n is the subspace of homogeneous spherical polynomials of degree n). It is shown that any perturbation of the RH wave evolves in such a way that its energy K(t) and enstrophy η(t) decrease, remain constant or increase simultaneously. A geometric interpretation of variations in the perturbation energy is given. A conservation law for arbitrary perturbations is obtained and used to classify all the RH-wave perturbations in four invariant sets M₋ⁿ, M₊ⁿ, H_n and M₀ⁿ−H_n depending on the value of their mean spectral number χ(t)=η(t)/K(t). The energy cascade of growing (or decaying) perturbations has opposite directions in the sets M₋ⁿ and M₊ⁿ due to a hyperbolic dependence between K(t) and χ(t). A factor space with a factor norm of the perturbations is introduced using the invariant subspace H_n of neutral perturbations as the zero factor class. While the energy norm controls the perturbation part belonging to H_n, the factor norm controls the perturbation part orthogonal to H_n. It is shown that in the set M₋ⁿ (χ(t)<n(n+1)), any nonzonal RH wave of subspace H₁H_n (n2) is Liapunov unstable in the energy norm. This instability has nothing in common with the orbital (Poincaré) instability and is caused by asynchronous oscillations of two almost coinciding RH-wave solutions. It is also shown that the exponential instability is possible only in the invariant set M₀ⁿ−H_n. A necessary condition for this instability is given. The condition states that the spectral number χ(t) of the amplitude of each unstable mode must be equal to n(n+1), where n is the RH-wave degree. The growth rate is estimated and the orthogonality of the unstable normal modes to the RH wave is shown. The instability in the invariant set M₊ⁿ of small-scale perturbations (χ(t)>n(n+1)) is still open problem.     

Estimation of dimension functions of band-limited wavelets

The dimension function D_ψ of a band-limited wavelet ψ is bounded by n if its Fourier transform is supported in [−(2ⁿ⁺²/3)π,(2ⁿ⁺²/3)π]. For each and for each , 0<<δ=δ(n), we construct a wavelet ψ with supp

Full-size image

such that D_ψ>n on a set of positive measure, which proves that [−(2ⁿ⁺²/3)π,(2ⁿ⁺²/3)π] is the largest symmetric interval for estimating the dimension function by n. This construction also provides a family of (uncountably many) wavelet sets each consisting of infinite number of intervals.     

Simultaneous similarity of matrices

In this paper we solve completely and explicitly the long-standing problem of classifying pairs of n × n complex matrices (A, B) under the simultaneous similarity (TAT⁻¹, TBT⁻¹). Roughly speaking, the classification decomposes to a finite number of steps. In each step we consider an open algebraic set ⁰_n,2,r,π M_n × M_n (M_n = the set of n × n complex-valued matrices). Here r and π are two positive integers. Then we construct a finite number of rational functions ø₁,…,ø_s in the entries of A and B whose values are constant on all pairs similar in _n,2,r,π to (A, B). The values of the functions ø_i(A, B), I = 1,…, s, determine a finite number (at most κ(n, 2, r)) of similarity classes in _n,2,r,π. Let S_n be the subspace of complex symmetric matrices in M_n. For (A, B) ε S_n × S_n we consider the similarity class (TAT^t, TBT^t), where T ranges over all complex orthogonal matrices. Then the characteristic polynomial |λI − (A + xB)| determines a finite number of similarity classes for almost all pairs (A, B) ε S_n × S_n.     

Spreading Rumors Rapidly Despite an Adversary

In thecollect problem(M. Saks, N. Shavit, and H. Woll,in“Proceedings of the 2nd ACM–SIAM Symposium on Discrete Algorithms, 1991),nprocessors in a shared-memory system must each learn the values ofnregisters. We give a randomized algorithm that solves the collect problem inO(n log³ n) total read and write operations with high probability, even if timing is under the control of a content-oblivious adversary (a slight weakening of the usual adaptive adversary). This improves on both the trivial upper bound ofO(n²) steps and the best previously known bound ofO(n^3/2 log n) steps, and is close to the lower bound of Ω(n log n) steps. Furthermore, we show how this algorithm can be used to obtain a multiuse cooperative collect protocol that isO(log³ n)-competitive in the latency model of Ajtaiet al.(“Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science,” 1994); andO(n^1/2 log^3/2 n)-competitive in the throughput model of Aspnes and Waarts (“Proceedings of the 28th ACM Symposium on Theory of Computing,” 1996). In both cases the competitive ratios are within a polylogarithmic factor of optimal.     

RELATIVE WIDTH OF SMOOTH CLASSES OF MULTIVARIATE PERIODIC FUNCTIONS WITH RESTRICTIONS ON ITERATED LAPLACE DERIVATIVES IN THE L2-METRIC

For two subsets W and V of a Banach space X, let Kn(W, V, X) denote the relative Kolmogorov n-width of W relative to V defined by Kn (W, V, X) := inf sup Ln f∈W g∈V∩Ln inf ‖f-g‖x,where the infimum is taken over all n-dimensional linear subspaces Ln of X. Let W2(△r) denote the class of 2w-periodic functions f with d-variables satisfying ∫[-π,π]d |△rf(x)|2dx ≤ 1,while △r is the r-iterate of Laplace operator △. This article discusses the relative Kolmogorov n-width of W2(△r) relative to W2(△r) in Lq([-r, πr]d) (1 ≤ q ≤∞), and obtain its weak asymptotic result.     

A Singular Riesz Product in the Nevai Class and Inner Functions with the Schur Parameters in ∩p>2 l

There exist singular Riesz products dσ=∏^∞_κ=1 (1+Re(α_κζ^n_κ)) on the unit circle with the parameters (a_n)_n0 of orthogonal polynomials in L²(dσ) satisfying ∑^∞_n=0 |a_n|^p<+∞ for every p, p>2. The Schur parameters of the inner factor of the Cauchy integral ∫ (ζ−z)⁻¹ dσ(ζ), σ being such a Riesz product, belong to ∩_p>2 l^p.     

Discrete time parametric models with long memory and infinite variance

We study a large class of infinite variance time series that display long memory. They can be represented as linear processes (infinite order moving averages) with coefficients that decay slowly to zero and with innovations that are in the domain of attraction of a stable distribution with index 1 < α < 2 (stable fractional ARIMA is a particular example). Assume that the coefficients of the linear process depend on an unknown parameter vector β which is to be estimated from a series of length n. We show that a Whittle-type estimator β_n for β is consistent (β_n converges to the true value β₀ in probability as n → ∞), and, under some additional conditions, we characterize the limiting distribution of the rescaled differences (n/logn)^1/ga(β_n − β₀).     

Onα-Symmetric Multivariate Characteristic Functions

Ann-dimensional random vector is said to have anα-symmetric distribution,α>0, if its characteristic function is of the form((|u₁|^α+…+|u_n|^α)^1/α). We study the classesΦ_n(α) of all admissible functions: [0, ∞)→ . It is known that members ofΦ_n(2) andΦ_n(1) are scale mixtures of certain primitivesΩ_nandω_n, respectively, and we show thatω_nis obtained fromΩ_2n−1byn−1 successive integrations. Consequently, curious relations between 1- and 2- (or spherically) symmetric distributions arise. An analogue of Askey's criterion gives a partial solution to a question of D. St. P. Richards: If(0)=1,is continuous, lim_t→∞ (t)=0, and⁽²ⁿ⁻²⁾(t) is convex, thenΦ_n(1). The paper closes with various criteria for the unimodality of anα-symmetric distribution.     

Reduktion von Präzedenzstrukturen

Zusammenfassung Es wird zunächst der Begriff des (transitiv) irreduziblen KernsG _* eines gerichteten GraphenG eingeführt und einige Eigenschaften von irreduziblen Kernen hergeleitet. — Es wird insbesondere gezeigt, daß mit höchstens 0(n ³) elementaren Rechenoperationen die Bestimmung eines Kernes eines beliebigen gerichteten Graphen mitn Ecken möglich ist. — Für Ablaufprobleme zeigt dieses Resultat, daß höchstens 0(n ³) Operationen notwendig sind, um alle redundanten Nebenbedingungen zu eliminieren.

---

Summary A (transitive) irreducible kernelG _* of a directed graphG is introduced as a partial graph ofG, which has the same transitive closure asG while no proper subgraph ofG _* has this property. — The author shows that at most 0(n ³) elementary operations are necessary to obtain a kernel of an arbitrary graph wheren is the number of vertices ofG. In the case of scheduling problems this result shows that at most 0(n ³) operations are needed to eliminate all redundant constraints.