Successive Minima and Best Simultaneous Diophantine Approximations

We study the problem of best approximations of a vector by rational vectors of a lattice whose common denominator is bounded. To this end we introduce successive minima for a periodic lattice structure and extend some classical results from geometry of numbers to this structure. This leads to bounds for the best approximation problem which generalize and improve former results.     

On Optimal Constants for Best Two-Dimensional Simultaneous Diophantine Approximations

 The main results of this paper state optimal constants for estimates of so-called successive minima in two dimensions under a constraint on the denominator. While these inequalities are known for every dimension, best possible constants within these estimates are, of course, notknown for any dimension larger than one and remain unknown for all dimensions larger than two. (Received 29 April 1998; in revised form 23 November 1998)     

Method of Best Successive Approximations for Nonlinear Operators

We present a new approach to the approximation of nonlinear operators in probability spaces. The approach is based on a combination of the specific iterative procedure and the best approximation problem solution with a quadratic approximant. We show that the combination of these new techniques allow us to build a computationally efficient and flexible method. The algorithm of the method and its application to the optimal filtering of stochastic signals are given.     

Computation of Best Simultaneous Approximations with a Singularity

Simultaneous approximation errors are generally discontinuous when the function to be approximated contains a zero in its domain of definition. In this article we indicate how the presence of such a zero (or, equivalently, the resulting singularity in the error expression) affects the computational schemata for finding all the best approximations. In particular, we develop an algorithm and show that its convergence rate is “best possible expected” in the sense that it is quadratic, as in the case for continuous errors. Numerical examples are provided.     

Diophantine Approximations on Fractals

We exploit dynamical properties of diagonal actions to derive results in Diophantine approximations. In particular, we prove that the continued fraction expansion of almost any point on the middle third Cantor set (with respect to the natural measure) contains all finite patterns (hence is well approximable). Similarly, we show that for a variety of fractals in [0, 1]², possessing some symmetry, almost any point is not Dirichlet improvable (hence is well approximable) and has property C (after Cassels). We then settle by similar methods a conjecture of M. Boshernitzan saying that there are no irrational numbers x in the unit interval such that the continued fraction expansions of {nx mod 1}_{n ? \mathbb N}{\{nx\,{\rm mod}\,1\}_{n \in {\mathbb N}}} are uniformly eventually bounded.     

Central Limit Theorem and Diophantine Approximations

Let \(F_n\) denote the distribution function of the normalized sum \(Z_n = (X_1 + \cdots + X_n)/(\sigma \sqrt{n})\) of i.i.d. random variables with finite fourth absolute moment. In this paper, polynomial rates of convergence of \(F_n\) to the normal law with respect to the Kolmogorov distance, as well as polynomial approximations of \(F_n\) by the Edgeworth corrections (modulo logarithmically growing factors in n), are given in terms of the characteristic function of \(X_1\). Particular cases of the problem are discussed in connection with Diophantine approximations.     

Diophantine Approximations and Integer Points of Cones

The purpose of this note is to present a relation between directed best approximations of a rational vector and the elements of the minimal Hilbert basis of certain rational pointed cones. Furthermore, we show that for a special class of these cones the integer Carathéodory property holds true. Received May 6, 1998 RID="*" ID="*" Supported by a "Leibniz Preis" of the German Science Foundation (DFG) awarded to M. Gr?tschel. RID="†" ID="†" Supported by a "Gerhard-Hess-Forschungsf?rderpreis" of the German Science Foundation (DFG).     

Mumford's Degree of Contact and Diophantine Approximations

The purpose of this note is to present a somewhat unexpected relation between diophantine approximations and the geometric invariant theory. The link is given by Mumford's degree of contact. We show that destabilizing flags of Chow-unstable projective varieties provide systems of diophantine approximations which are better than those given by Schmidt's subspace theorem, and we give examples of these systems.     

Lattice Points in Large Borel Sets and Successive Minima

Let B be a Borel set in E^d with volume V(B) = ∞. It is shown that almost all lattices L in E^d contain infinitely many pairwise disjoint d-tuples, that is sets of d linearly independent points in B. A consequence of this result is the following: let S be a star body in E^d with V(S ) = ∞. Then for almost all lattices L in E^d the successive minima λ₁(S,L),..., λ_d(S,L) of S with respect to L are 0. A corresponding result holds for most lattices in the Baire category sense. A tool for the latter result is the semi-continuity of the successive minima.     

Finding Range Minima in the Middle: Approximations and Applications

A Range Minimum Query asks for the position of a minimal element between two specified array-indices. We consider a natural extension of this, where our further constraint is that if the minimum in a query interval is not unique, then the query should return an approximation of the median position among all positions that attain this minimum. We present a succinct preprocessing scheme using Dn + o(n) bits in addition to the static input array (small constant D), such that subsequent “range median of minima queries” can be answered in constant time. This data structure can be built in linear time, with little extra space needed at construction time. We introduce several new combinatorial concepts such as Super-Cartesian Trees and Super-Ballot Numbers. We give applications of our preprocessing scheme in text indexes such as (compressed) suffix arrays and trees.     

Geometry and Topology of Continuous Best and Near Best Approximations

The existence of a continuous best approximation or of near best approximations of a strictly convex space by a subset is shown to imply uniqueness of the best approximation under various assumptions on the approximating subset. For more general spaces, when continuous best or near best approximations exist, the set of best approximants to any given element is shown to satisfy connectivity and radius constraints.     

Factorised Preconditionings of Successive Approximations in Finite Precision

This paper examines the possibility of using the method of successive approximations for the approximate solution of a large system of linear equations with a dense, noncontraction, and ill-conditioned matrix. Using Krasnosel'skii's method of transformation of linear operator equations and functional calculi, the procedure of factorised preconditionings of successive approximations is developed and analysed in the finite precision arithmetic. Numerical results of computational experiments are presented to demonstrate the practicability of the proposed approach.This revised version was published online in October 2005 with corrections to the Cover Date.     

On the Central Limit Theorem for Non-Archimedean Diophantine Approximations

We consider a Diophantine inequality:on the set of formal Laurent series of negative degree. We show that under these two conditions: (i) qⁿ(n) is a monotone non-increasing and (ii) _nqⁿ(n)=, a central limit theorem holds for the number of solutions. The proof is based on the construction of a non-stationary one dependent process associated with the Diophantine inequality.Mathematics Subject Classification (2000): 11J61, 11K60     

On the Superlinear Convergence of the Successive Approximations Method

The Ostrowski theorem is a classical result which ensures the attraction of all the successive approximations x _k+1 = G(x _k ) near a fixed point x*. Different conditions [ultimately on the magnitude of G(x*)] provide lower bounds for the convergence order of the process as a whole. In this paper, we consider only one such sequence and we characterize its high convergence orders in terms of some spectral elements of G(x*); we obtain that the set of trajectories with high convergence orders is restricted to some affine subspaces, regardless of the nonlinearity of G. We analyze also the stability of the successive approximations under perturbation assumptions.     

On Best Polynomial Approximations in L 2

For the τ-moduli of smoothness of mth order, we calculate exact constants in Jackson-type inequalities. We also obtain the exact values of the n-widths of classes of functions whose rth derivatives are characterized by τ-moduli of smoothness majorized by functions satisfying certain constraints. We present an example of the majorant for which all the stated requirements are satisfied.     

Hausdorff Dimension and Generalized Simultaneous Diophantine Approximation

Suppose that m is a positive integer, is a vector of strictly positive numbers, and Qis an infinite set of positive integers. Let W_Q(m; ) be theset [formula] In this paper we obtain the Hausdorff dimension of this set.We also consider a generalization of the set W_Q(m; ), wherethe error terms in the inequalities are replaced by _i(q), for general functions _i satisfying a certaincondition at infinity. 1991 Mathematics Subject Classification11J83, 28A78.     

On Diophantine Approximations of Dependent Quantities in the p-adic Case

In the present paper, we prove an analog of Khinchin's metric theorem in the case of linear Diophantine approximations of plane curves defined over the ring of $p$ -adic integers by means of (Mahler) normal functions. We also prove some general assertions needed to generalize this result to the case of spaces of higher dimension.     

On Diophantine Approximations of Mock Theta Functions of Third Order

The paper gives bounds for the approximation of the values of Ramanujan's Mock Theta functions of third order and more generally of some q-hypergeometric functions by the elements of an algebraic number field. Simultaneous approximations for the values of q-exponential function are also obtained. All the results are given both in the archimedean and p-adic case.     

On a Monotony-preserving Accelerator Process for the Successive Approximations Method

This paper presents a theoretical and numerical study of anaccelerative process for speeding up the successive-approximationsmethod applied to linear systems in the case of monotonic convergence.     

Finite-Time Optimal Control of Polynomial Systems Using Successive Suboptimal Approximations

It is shown in this paper that the finite-time optimal control of polynomial systems can be obtained by solving a sequence of optimal control problems for the linearized problem. The paper provides proof of convergence as well as illustration of the procedure by two examples.