Note on the heights of random recursive trees and random m-ary search trees

A process of growing a random recursive tree T_n is studied. The sequence {T_n} is shown to be a sequence of “snapshots” of a Crump–Mode branching process. This connection and a theorem by Kingman are used to show quickly that the height of T_n is asymptotic, with probability one, to c log n. In particular, c = e = 2.718 … for the uniform recursive tree, and c = (2γ)^?1, where γe^1+γ = 1, for the ordered recursive tree. An analogous reduction provides a short proof of Devroye's limit law for the height of a random m-ary search tree. We show finally a close connection between another Devroye's result, on the height of a random union-find tree, and our theorem on the height of the uniform recursive tree. © 1994 John Wiley & Sons, Inc.     

A complementary universal conjugate Banach space and its relation to the approximation problem

LetC ₁=(ΣG _n ) _{l 1}, where (G _n ) is a sequence which is dense (in the Banach-Mazur sense) in the class of all finite dimensional Banach spaces. IfX is a separable Banach space, thenX ^* is isometric to a subspace ofC ₁ ^* =(ΣG _n ^* ) _m which is the range of a contractive projection onC ₁ ^* . Separable Banach spaces whose conjugates are isomorphic toC ₁ ^* are classified as those spaces which contain complemented copies of C₁. Applications are that every Banach space has the [metric] approximation property ([m.] a.p., in short) iff (ΣG _n ^* ) _m does, and if there is a space failing the m.a.p., thenC ₁ can be equivalently normed to fail the m.a.p. The author was supported in part by NSF GP 28719.     

On singularities of solution of Maxwell's equations in axisymmetric domains with conical points

Boundary value problems (BVP) in three‐dimensional axisymmetric domains can be treated more efficiently by partial Fourier analysis. Partial Fourier analysis is applied to time‐harmonic Maxwell's equations in three‐dimensional axisymmetric domains with conical points on the rotation axis thereby reducing the three dimensional BVP to an infinite sequence of 2D BVPs on the plane meridian domain Ω_a?? of . The regularity of the solutions u _n (n∈?₀:={0, 1, 2,…}) of the two dimensional BVPs is investigated and it is proved that the asymptotic behaviour of the solutions u _n near an angular point on the rotation axis can be characterized by singularity functions related to the solutions of some associated Legendre equations. By means of numerical experiments, it is shown that the solutions u _n for n∈?₀\{1} belong to the Sobolev space H² irrespective of the size of the solid angle at the conical point. However, the regularity of the coefficient u ₁ depends on the size of the solid angle at the conical point. The singular solutions of the three dimensional BVP are obtained by Fourier synthesis. Copyright © 2006 John Wiley & Sons, Ltd.     

On-line covering a cube by a sequence of cubes

A procedure for packing or covering a given convex bodyK with a sequence of convex bodies {C _i} is anon-line method if the setC _i are given in sequence. andC _i+1 is presented only afterC _i has been put in place, without the option of changing the placement afterward. The “one-line” idea was introduced by Lassak and Zhang [6] who found an asymptotic volume bound for the problem of on-line packing a cube with a sequence of convex bodies. In this note a problem of Lassak is solved, concerning on-line covering a cube with a sequence of cubes, by proving that every sequence of cubes in the Euclidean spaceE ^d whose total volume is greater than 4 ^d admits an on-line covering of the unit cube. Without the “on-line” restriction, the best possible volume bound is known to be 2 ^d −1, obtained by Groemer [2] and, independently, by Bezdek and Bezdek [1]. The on-line covering method described in this note is based on a suitable cube-filling Peano curve.     

Integrability of differential-difference equations with discrete kinks

We discuss a series of models introduced by Barashenkov, Oxtoby, and Pelinovsky to describe some discrete approximations of the Φ ⁴ theory that preserve traveling kink solutions. Using the multiple scale test, we show that they have some integrability properties because they pass the A ₁ and A ₂ conditions, but they are nonintegrable because they fail the A ₃ conditions.     

On the Partial Sums of the Rearrangements of a Complex Series

Let {z_j} be a set of complex numbers, all with magnitude ? 1, which sum to a real number ε?1. Then the z_j's can be rearranged so that all partial sums are no greater in magnitude than (ε² + 1)^1/2, and this bound is best possible. Bergström showed that if , the best bound is .     

On the instability of resonances in parallel-plane waveguides

It has been observed¹³ that the propagation of acoustic waves in the region Ω₀= ?² × (0, 1), which are generated by a time-harmonic force density with compact support, leads to logarithmic resonances at the frequencies ω = 1, 2,… As we have shown⁹ in the case of Dirichlet's boundary condition U = 0 on ?Ω, the resonance at the smallest frequency ω = 1 is unstable and can be removed by a suitable small perturbation of the region. This paper contains similar instability results for all resonance frequencies ω = 1, 2,… under more restrictive assumptions on the perturbations Ω of Ω₀. By using integral equation methods, we prove that absence of admissible standing waves in the sense of Reference 7 implies the validity of the principle of limit amplitude for every frequency ω ≥ 0 in the region Ω =Ω₀ ?B, where B is a smooth bounded domain with B??Ω₀. In particular, it follows from Reference 7 in the case of Dirichlet's boundary condition that the principle of limit amplitude holds for every frequency ω ≥ 0 if n · x ′ ? 0 on ? B, where x ′ = (x₁, x₂, 0) and n is the normal unit vector pointing into the interior B of ? B. In the case of Neumann's boundary condition, the logarithmic resonance at ω = 0 is stable under the perturbations considered in this paper. The asymptotic behaviour of the solution for arbitary local perturbations of Ω₀ will be discussed in a subsequent paper.     

The analysis of structured qualitative data

The aim of this paper is to give an overview of the methodological contribution given by Italian researchers in introducing a priori information into multidimensional data analysis techniques, paying special attention to categorical variables. The basic method is Non‐Symmetrical Correspondence Analysis, which enables the analysis of a contingency table when the behaviour of one variable is supposed to be dependent on the other cross‐classified variable. As usual correspondence analysis decomposes an association index (Pearson's Φ²), in a principal component sense, the proposed method is based on a decomposition of a predictability index (Goodman and Kruskal's τ_b). Non‐symmetrical correspondence analysis has been extended to more than one dependent/explanatory variable(s), by means of proper flattening procedures, i.e. by the use of multiple tables, and the decomposition of Gray and Williams' multiple and partial τ_b's. In doing so multiple and partial versions have been proposed. A forward selection procedure for choosing the variables with higher predictive power is presented. After a brief review of non‐symmetrical correspondence analysis confirmatory approach, the problem of validating results in terms of analytical stability and replication stability is faced by means of influence functions and resampling techniques. Copyright © 1999 John Wiley & Sons, Ltd.     

The Evolution of the Weyl and Maxwell Fields in Curved Space—Times

The covariant Weyl (spin s = 1/2) and Maxwell (s = 1) equations in certain local charts (u, φ) of a space-time (M, g) are considered. It is shown that the condition g⁰⁰(x) > 0 for all x ε u is necessary and sufficient to rewrite them in a unified manner as evolution equations δ_tφ = L_(s)φ. Here L_(s) is a linear first order differential operator on the pre—Hilbert space (C (U_t, ^2s+1). (…)), where U_t ? IR³ is the image of the coordinate map of the spacelike hyper-surface t = const, and (φ, C) = ?U_t ? *Q d⁽³⁾x with a suitable Hermitian n × n- matrix Q = Q(t,x). The total energy of the spinor field ? with respect to U_t is then simply given by E = 〈?,?〉. In this way inequalities for the energy change rate with respect to time, δ_t|?|² = 2Re (?, L_(s)?) are obtained. As an application, the Kerr—Newman black hole is studied, yielding quantitative estimates for the energy change rate. These estimates especially confirm the energy conservation of the Weyl field and the well—known superradiance of electromagnetic waves.     

A note on skew differential operators on commutative rings

Let A be a commutative integral domain that is a finitely generated algebra over a field k of characteristic 0 and let ø be a k-algebra automorphism of A of finite order m. In this note we study the ring D(A;ø of differential operators introduced by A.D. Bell. We prove that if A is a free module over the fixed sub-ring A ^ø, with a basis containing 1, then D(A;ø) is isomorphic to the matrix ring M_m(D(A ^ø). It follows from Grothendieck's Generic Flatness Theorem that for an arbitrary A there is an element c?Asuch that D(A[c^-1];ø)?M _m(D(A[c^-1]^ø)). As an application, we consider the structure of D(A;ø)when A is a polynomial or Laurent polynomial ring over k and ø is a diagonalizable linear automorphism.     

A Four-filtrated may spectral sequence and its applications

In this paper, we introduce a four-filtrated version of the May spectral sequence (MSS), from which we study the general properties of the spectral sequence and give a collapse theorem. We also give an efficient method to detect generators of May E ₁-term E ₁ ^s,t,b,* for a given (s, t, b, *). As an application, we give a method to prove the non-triviality of some compositions of the known homotopy elements in the classical Adams spectral sequence (ASS). This research is partially supported by the National Natural Science Foundation of China (Nos. 10501045, 10771105) and the Fund of the Personnel Division of Nankai University     

An existence theorem for the unmodified Vlasov Equation

The initial value problem for the modified Vlasov equation with a mollification parameter δ > 0, as introduced by Batt, has a unique global solution in the weak sense whenever f₀ ε L¹ and f₀ ≧ 0 λ-a.e. Assuming boundedness of f₀ and boundedness of the kinetic energy, it is shown that, as δ → 0, there are subsequences δ_n → 0 such that the corresponding solutions converge weakly in the measure-theoretical sense. The limits are shown to be global weak solutions of the initial value problem for Vlasov's equation, and these solutions are seen to be weakly continuous with respect to t. For the plasma physical case, boundedness of the kinetic energy is a consequence of energy conservation.     

A Relationship Among Gentzen's Proof-Reduction,Kirby-Paris' Hydra Game and Buchholz's Hydra Game

We first note that Gentzen's proof-reduction for his consistency proof of PA can be directly interpreted as moves of Kirby-Paris' Hydra Game, which implies a direct independence proof of the game (Section 1 and Appendix). Buchholz's Hydra Game for labeled hydras is known to be much stronger than PA. However, we show that the one-dimensional version of Buchholz's Game can be exactly identified to Kirby-Paris' Game (which is two-dimensional but without labels), by a simple and natural interpretation (Section 2). Jervell proposed another type of a combinatorial game, by abstracting Gentzen's proof-reductions and showed that his game is independent of PA. We show (Section 3) that this Jervell's game is actually much stronger than PA, by showing that the critical ordinal of Jervell's game is φ_ω (0) (while that of PA or of Kirby-Paris' Game is φ₁ (0) = ?₀) in the Veblen hierarchy of ordinals.     

Order and chaos in Hofstadter's Q(n) sequence

A number of observations are made on Hofstadter's integer sequence defined by Q(n) = Q(n − Q(n − 1)) + Q(n − Q(n − 2)), for n > 2, and Q(1) = Q(2) = 1. On short scales, the sequence looks chaotic. It turns out, however, that the Q(n) can be grouped into a sequence of generations. The k‐th generation has 2^k members that have “parents” mostly in generation k − 1 and a few from generation k − 2. In this sense, the sequence becomes Fibonacci type on a logarithmic scale. The variance of S(n) = Q(n) − n/2, averaged over generations, is ≅2^αk, with exponent α = 0.88(1). The probability distribution p*(x) of x = R(n) = S(n)/n^α, n ≫ 1, is well defined and strongly non‐Gaussian, with tails well described by the error function erfc. The probability distribution of x_m = R(n) − R(n − m) is given by p_m(x_m) = λ_m p*(x_m/λ_m), with λ_m → √2 for large m. © 1999 John Wiley & Sons, Inc.     

Equivalence of weak Dirichlet's principle,the method of weak solutions and Perron's method towards classical solutions of Dirichlet's problem for harmonic functions

For boundary data ? ∈ W ^1,2(G ) (where G ? ?^N is a bounded domain) it is an easy exercise to prove the existence of weak L ²‐solutions to the Dirichlet problem “Δu = 0 in G, u |_?G = ? |_?G ”. By means of Weyl's Lemma it is readily seen that there is ? ∈ C ^∞(G ), Δ? = 0 and ? = u a.e. in G . On the contrary it seems to be a complicated task even for this simple equation to prove continuity of ? up to the boundary in a suitable domain if ? ∈ W ^1,2(G ) ∩ C ⁰( ). The purpose of this paper is to present an elementary proof of that fact in (classical) Dirichlet domains. Here the method of weak solutions (resp. Dirichlet's principle) is equivalent to the classical approaches (Poincaré's “sweeping‐out method”, Perron's method). (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Good points for diophantine approximation

Given a sequence (x _n ) _n=1^∞ of real numbers in the interval [0, 1) and a sequence (δ _n ) _n=1^∞ of positive numbers tending to zero, we consider the size of the set of numbers in [0, 1] which can be ‘well approximated’ by terms of the first sequence, namely, those y ∈ [0, 1] for which the inequality |y − x _n | < δ _n holds for infinitely many positive integers n. We show that the set of ‘well approximable’ points by a sequence (x _n ) _n=1^∞, which is dense in [0, 1], is ‘quite large’ no matter how fast the sequence (δ _n ) _n=1^∞ converges to zero. On the other hand, for any sequence of positive numbers (δ _n ) _n=1^∞ tending to zero, there is a well distributed sequence (x _n ) _n=1^∞ in the interval [0, 1] such that the set of ‘well approximable’ points y is ‘quite small’.     

Preconditioned HSS methods for the solution of non-Hermitian positive definite linear systems and applications to the discrete convection-diffusion equation

Summary. We study the role of preconditioning strategies recently developed for coercive problems in connection with a two-step iterative method, based on the Hermitian skew-Hermitian splitting (HSS) of the coefficient matrix, proposed by Bai, Golub and Ng for the solution of nonsymmetric linear systems whose real part is coercive. As a model problem we consider Finite Differences (FD) matrix sequences {A_n(a,p)}_n discretizing the elliptic (convection-diffusion) problem with being a plurirectangle of R^d with a(x) being a uniformly positive function and p(x) denoting the Reynolds function: here for plurirectangle we mean a connected union of rectangles in d dimensions with edges parallel to the axes. More precisely, in connection with preconditioned HSS/GMRES like methods, we consider the preconditioning sequence {P_n(a)}_n, P_n(a):= D_n^1/2(a)A_n(1,0) D_n^1/2(a) where D_n(a) is the suitably scaled main diagonal of A_n(a,0). If a(x) is positive and regular enough, then the preconditioned sequence shows a strong clustering at unity so that the sequence {P_n(a)}_n turns out to be a superlinear preconditioning sequence for {A_n(a,0)}_n where A_n(a,0) represents a good approximation of Re(A_n(a,p)) namely the real part of A_n(a,p). The computational interest is due to the fact that the preconditioned HSS method has a convergence behavior depending on the spectral properties of {P_n^-1(a)Re(A_n(a,p))}_n {P_n^-1(a)A_n(a,0)}_n: therefore the solution of a linear system with coefficient matrix A_n(a,p) is reduced to computations involving diagonals and to the use of fast Poisson solvers for {A_n(1,0)}_n.Some numerical experimentations confirm the optimality of the discussed proposal and its superiority with respect to existing techniques.Mathematics Subject Classification (1991): 65F10, 65N22, 15A18, 15A12, 47B65     

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.     

Approximation von extremalflächenstücken (hyperbolischen typs) durch charakteristische räumliche vierecke

We consider solutions z of the Cauchy-problem for hyperbolic Euler-Lagrange equations derived from a general Lagrangian f(x, y, z; z_x, z_y) in two independent variables x, y. z is supposed to be an extremal of the corresponding variational problem. Visualizing z as a surface in R ³ we give a geometric interpretation of Lewy's well-known characteristic approximation scheme for the numerical solution of second order hyperbolic equations by approximating z via a polyhedral construction built up from subunits which consist of two characteristic triangles having one side in common but lying on different planes in R ³. Utilizing ideas from Cartan-geometry one can (in an appropriate sense) introduce the “mean curvature” of these subunits and it is seen that this curvature vanishes (up to terms of higher order). That is a highly plausible result for the polyhedral approximation of “minimal surfaces”.     

A bounded N-tuplewise independent and identically distributed counterexample to the CLT

Summary. A sequence of random variables X ₁,X ₂,X ₃,… is said to be N-tuplewise independent if X i ₁,X i ₂,…,X i _N are independent whenever (i ₁,i ₂,…,i _N ) is an N-tuple of distinct positive integers. For any fixed N∈ℤ⁺, we construct a sequence of bounded identically distributed N-tuplewise independent random variables which fail to satisfy the central limit theorem. Received: 17 May 1996 / In revised form: 28 January 1998