Convergence acceleration of limit periodic continued fractions under asymptotic side conditions

Summary We present a method of convergence acceleration for limitk-periodic continued fractionsK(a _n /1) orK(1/b _n ) satisfying certain asymptotic side conditions. The method represents an improvement of the fixed point modification considered by Thron and Waadeland [8], under these conditions. The regularC-fraction expansions of hypergeometric functions₂ F ₁(a, 1;c; z) and₂ F ₁(a, b; c; z)/₂ F ₁(a, b+1;c+1;z) are examples of continued fractions satisfying these conditions.     

A survey of truncation error analysis for Padé and continued fraction approximants

To compute the value of a functionf(z) in the complex domain by means of a converging sequence of rational approximants {f _n(z)} of a continued fraction and/or Padé table, it is essential to have sharp estimates of the truncation error ¦f(z)–f _n(z)¦. This paper is an expository survey of constructive methods for obtaining such truncation error bounds. For most cases dealt with, {f _n(z)} is the sequence of approximants of a continued fractoin, and eachf _n(z) is a (1-point or 2-point) Padé approximant. To provide a common framework that applies to rational approximantf _n(z) that may or may not be successive approximants of a continued fraction, we introduce linear fractional approximant sequences (LFASs). Truncation error bounds are included for a large number of classes of LFASs, most of which contain representations of important functions and constants used in mathematics, statistics, engineering and the physical sciences. An extensive bibliography is given at the end of the paper.Research supported in part by the U.S. National Science Foundation under Grants INT-9113400 and DMS-9302584.     

Ideas from Continued Fraction Theory Extended to Padé Approximation and Generalized Iteration

This is a survey of some basic ideas in the convergence theory for continued fractions, in particular value sets, general convergence and the use of modified approximants to obtain convergence acceleration and analytic continuation. The purpose is to show how these ideas apply to some other areas of mathematics. In particular, we introduce {w _k }-modifications and general convergence for sequences of Padé approximants.     

Cross-monotone subsequences

Two finite real sequences (a ₁,...,a _k ) and (b ₁,...,b _k ) are cross-monotone if each is nondecreasing anda _i+1–a _i b _i+1–b _i for alli. A sequence (₁,..., _n ) of nondecreasing reals is in class CM(k) if it has disjointk-term subsequences that are cross-monotone. The paper shows thatf(k), the smallestn such that every nondecreasing (₁,..., _n ) is in CM(k), is bounded between aboutk ²/4 andk ₂/2. It also shows thatg(k), the smallestn for which all (₁,..., _n ) are in CM(k)and eithera _k b ₁ orb _k a ₁, equalsk(k–1)+2, and thath(k), the smallestn for which all (₁,..., _n ) are in CM(_k)and eithera ₁b ₁...a _k b _k orb ₁a ₁...b _k a _k , equals 2(k–1)²+2.The results forf andg rely on new theorems for regular patterns in (0, 1)-matrices that are of interest in their own right. An example is: Every upper-triangulark ²×k ² (0, 1)-matrix has eitherk 1's in consecutive columns, each below its predecessor, ork 0's in consecutive rows, each to the right of its predecessor, and the same conclusion is false whenk ² is replaced byk ²–1.     

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.     

On the transcendence and algebraic independence of certain continued fractions

The transcendence of continued fractions =[a ₀;a ₁,a ₂,...] is proved under growth conditions involving the denominatorsq _n of the convergents and shifted partial quotientsa _n+k . Extending this idea, conditions for the algebraic independence of several continued fractions are given. The proofs use the approximation properties of continued fractions in combination with the Thue-Siegel-Roth Theorem or a criterion for algebraic independence of Bundschuh.     

Construction of hamiltonian cycles with a given spectrum of edge directions in an <Emphasis Type="Italic">n</Emphasis>-dimensional Boolean cube

The spectrum of a Hamiltonian cycle (of a Gray code) in an n-dimensional Boolean cube is the series a = (a ₁, ..., a _n ), where a _i is the number of edges of the ith direction in the cycle. The necessary conditions for the existence of a Gray code with the spectrum a are available: the numbers a _i are even and, for k = 1, ..., n, the sum of k arbitrary components of a is at least 2 ^k . We prove that there is some dimension N such that if the necessary condition on the spectrum is also sufficient for the existence of a Hamiltonian cycle with the spectrum in an N-dimensional Boolean cube then the conditions are sufficient for all dimensions n.     

Approximants of Śleszyński–Pringsheim continued fractions

We characterize the sequences {z_n} of complex numbers which are sequences of approximants of continued fractions K(a_n/b_n) with |a_n|+1⩽|b_n|, and study some of their properties. In particular we give truncation error bounds for such continued fractions.     

Lebesgue measure and Hausdorff dimension of special sets of real numbers from (0,1)

We estimate the Hausdorff dimension and the Lebesgue measure of sets of continued fractions of the type a=[a ₁,a ₂,…] where a _n belongs to a set S _n ⊂ℕ for every n∈ℕ. An upper bound for the Hausdorff dimension of the set of numbers with continued fraction expansions which fulfill some properties of asymptotic densities is also included.     

On B(n,k) 2-groups

A finite group G is said to be a B(n, k) group if for any n-element subset {a ₁,…, a _n } of G, |{a _i a _j |1 ≤ i, j ≤ n}| ≤k. In this article, we give characterizations of the B(5, 19) 2-groups, and the B(6, k) 2-groups for 21 ≤ k ≤ 28.     

Uniform in bandwidth consistency of kernel estimators of the tail index

We consider a class of kernel estimators [^(t)]_n,h\hat{\tau}_{n,h} of the tail index of a Pareto-type distribution, which generalizes and includes the classical Hill estimator [^(a)]_n,k\hat{a}_{n,k}. It is well-known that [^(a)]_n,k\hat{a}_{n,k} is a consistent estimator of the tail index if and only if k→ ∞ and k/n→0. Under suitable assumptions on the kernel, [^(t)] _n,h\hat{\tau} _{n,h} is consistent whenever the bandwidth is taken to be a sequence of non-random numbers satisfying h _n →0 and nh _n → ∞. We extend this result and prove the consistency uniformly over a certain range of bandwidths. This permits the treatment of estimators of the tail index based upon data-dependent bandwidths, which are often used in practice. In the process, we establish a uniform in bandwidth result for kernel-type regression estimators with a fixed design, which will likely be of separate interest.     

The Minimum Rank of a 3 × 3 Partial Block Matrix

After recalling the definition and some basic properties of finite hypergroups—a notion introduced in a recent paper by one of the authors—several non-trivial examples of such hypergroups are constructed. The examples typically consist of n n×n matrices, each of which is an appropriate polynomial in a certain tri-diagonal matrix. The crucial result required in the construction is the following: ‘let A be the matrix with ones on the super-and sub-diagonals, and with main diagonal given by a ₁…a _n which are non-negative integers that form either a non-decreasing or a symmetric unimodal sequence; then A_k =P_k (A) is a non-negative matrix, where p_k denotes the characteristic polynomial of the top k× k principal submatrix of A, for k=1,…,n. The matrices A_k as well as the eigenvalues of A, are explicitly described in some special cases, such as (i) a_i =0 for all ior (ii) a_i =0 for i<n and a_n =1. Characters ot finite abelian hypergroups are defined, and that naturally leads to harmonic analysis on such hypergroups.     

Rado Numbers fora(x+y)=bz

In the case of existence the smallest numberN=Ra_kis called a Rado number if it is guaranteed that anyk-coloring of the numbers 1, 2, …, Ncontains a monochromatic solution of a given system of linear equations. We will determine Ra_k(a, b) for the equationa(x+y)=bzifb=2 andb=a+1. Also, the case of monochromatic sequences {x_n} generated bya(x_n+x_n+1)=bx_n+2 is discussed.     

On the Law of The Iterated Logarithm for Rapidly Increasing Subsequences

The usual law of the iterated logarithm states that the partial sums S_n of independent and identically distributed random variables can be normalized by the sequence a_n = √nlog log n, such that limsup_n→∞ S_n/a_n = √2 a.s. As has been pointed out by Gut (1986) the law fails if one considers the limsup along subsequences which increase faster than exponentially. In particular, for very rapidly increasing subsequences {n_k≥1} one has limsup_k→∞ S_nk/a_nk = 0 a.s. In these cases the normalizing constants a_nk have to be replaced by √nk log k to obtain a non-trivial limiting behaviour: limsup_k→∞ S_nk/ √nk log k = √2 a.s. We will present an intelligible argument for this structural change and apply it to related results.     

Non-<Emphasis Type="Italic">φ</Emphasis>-admissible normal subgroups of free burnside groups

In the present paper for arbitrary automorphism φ of the free Bunside group B(m, n) and for any odd number n ≥ 1003 a sufficient condition for existence of non-φ-admissible normal subgroup of B(m, n) was found. In particular, if automorphism φ is normal, then for any basis {a ₁, a ₂, …, a _m } of the group B(m, n) there is an integer k such that for each i the elements a _i and φ(a i) ^k are conjugates.     

Numerical results on the Goldbach conjecture

The number of Goldbach partitions has been computed for all even numbers 350,000 and compared to well-known theoretical estimates. The random fluctuations are slowly decreasing and less than ± 5 per cent at the upper end of the interval. The number of partitions is given explicitly for 2 ⁿ ,n=3(1)22. Further, if for a givenN the smallest prime in all partitions of 2N isa=a(2N) we have also determineda ₁(2N ₁)<a ₂(2N ₂)<... withN ₁<N ₂<... such thatn<N _k impliesa(2n)<a _k (2N _k ) up to 2n=40,000,000.     

Characterization of 2<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>-periodic binary sequences with fixed 2-error or 3-error linear complexity

The linear complexity of sequences is an important measure of the cryptographic strength of key streams used in stream ciphers. The instability of linear complexity caused by changing a few symbols of sequences can be measured using k-error linear complexity. In their SETA 2006 paper, Fu et al. (SETA, pp. 88–103, 2006) studied the linear complexity and the 1-error linear complexity of 2 ⁿ -periodic binary sequences to characterize such sequences with fixed 1-error linear complexity. In this paper we study the linear complexity and the k-error linear complexity of 2 ⁿ -periodic binary sequences in a more general setting using a combination of algebraic, combinatorial, and algorithmic methods. This approach allows us to characterize 2 ⁿ -periodic binary sequences with fixed 2- or 3-error linear complexity. Using this characterization we obtain the counting function for the number of 2 ⁿ -periodic binary sequences with fixed k-error linear complexity for k = 2 and 3.     

Ramanujan and extensions and contractions of continued fractions

If a continued fraction K _n=1^∞ a _n /b _n is known to converge but its limit is not easy to determine, it may be easier to use an extension of K _n=1^∞ a _n /b _n to find the limit. By an extension of K _n=1^∞ a _n /b _n we mean a continued fraction K _n=1^∞ c _n /d _n whose odd or even part is K _n=1^∞ a _n /b _n . One can then possibly find the limit in one of three ways:

On the acceleration of limit periodic continued fractions

Summary A continued fraction (c.f.)K(a _n /1) is called limit periodic if . Fora anda(–,–1/4],a0, Thron-Waadeland (1980) examined a modification of a limit periodic c.f. for accelerating the convergence. This acceleration remains modest if thea _n converge only logarithmically. Thus it is proposed to apply an Euler summability method to the series equivalent to the c.f. Properties of the equivalent function are derived. These properties are used for choosing appropriate parameters for the summability method such that a considerable acceleration can be expected even if thea _n converge logarithmically.Dedicated to Prof. F.L. Bauer on the occasion of his 60th birthday     

Truncation error bounds for limit-periodic continued fractionsK(a n /1) with lima n =0

Summary Truncation error bounds are developed for continued fractionsK(a _n /1) where |a _n |1/4 for alln sufficiently large. The bounds are particularly suited (some are shown to be best) for the limit-periodic case when lima _n =0. Among the principal results is the following: If |a _n |/n ^p for alln sufficiently large (with constants >0,p>0), then |f–f _m |C[D/(m+2)] ^p(m+2) for allm sufficiently large (for some constantsC>0,D>0). Heref denotes the limit (assumed finite) ofK(a _n /1) andf _m denotes itsmth approximant. Applications are given for continued fraction expansions of ratios of Kummer functions₁ F ₁ and of ratios of hypergeometric functions₀ F ₁. It is shown thatp=1 for₁ F ₁ andp=2 for₀ F ₁, wherep is the parameter determining the rate of convergence. Numerical examples indicate that the error bounds are indeed sharp.Research supported in part by the National Science Foundation under Grant MCS-8202230 and DMS-8401717