Structure of <Emphasis Type="Italic">K</Emphasis>-interval exchange transformations: Induction,trajectories, and distance theorems

We define a new induction algorithm for k-interval exchange transformations associated to the “symmetric” permutation i ↦ k − i + 1. Acting as a multi-dimensional continued fraction algorithm, it defines a sequence of generalized partial quotients given by an infinite path in a graph whose vertices, or states, are certain trees we call trees of relations. This induction is self-dual for the duality between the usual Rauzy induction and the da Rocha induction. We use it to describe those words obtained by coding orbits of points under a symmetric interval exchange, in terms of the generalized partial quotients associated with the vector of lengths of the k intervals. As a consequence, we improve a bound of Boshernitzan in a generalization of the three-distances theorem for rotations. However, a variant of our algorithm, applied to a class of interval exchange transformations with a different permutation, shows that the former bound is optimal outside the hyperelliptic class of permutations.     

Covering numbers: Arithmetics and dynamics for rotations and interval exchanges

We study a particular case of the two-dimensional Steinhaus theorem, giving estimates of the possible distances between points of the formkα andkα+β on the unit circle, through an approximation algorithm of β by the pointskα. This allows us to compute covering numbers (maximal measures of Rokhlin stacks having certain prescribed regularity properties) for the symbolic dynamical systems associated to the rotation of argument α, acting on the partition of the circle by the points 0, β. We can the compute topological and measure-theoretic covering numbers for exchange of three intervals; in this way, we prove that every ergodic exchange of three intervals has simple spectrum and build a new class of three-interval exchanges which are not of rank one.     

The discontinuous flat top tent map and the nested period incrementing bifurcation structure

In this work we report the recently discovered nested period incrementing bifurcation scenario. The investigated piecewise linear map is defined on three partitions of the unit interval, constant in the middle partition and therefore displays a rich variety of superstable orbits. These orbits are arranged according to an infinite binary tree of the corresponding symbolic sequences, which can be generated by a simple set of rules. The system also allows for straightforward computation of the respective regions of existence. One of the most striking results of our investigations is that the famous U-sequence is inevitably embedded in the nested period incrementing scenario.     

Periodicity and Correlation Properties of d-FCSR Sequences

A d-feedback-with-carry shift register (d-FCSR) is a finite state machine, similar to a linear feedback shift register (LFSR), in which a small amount of memory and a delay (by d-clock cycles) is used in the feedback algorithm (see Goresky and Klapper [4,5]). The output sequences of these simple devices may be described using arithmetic in a ramified extension field of the rational numbers. In this paper we show how many of these sequences may also be described using simple integer arithmetic, and consequently how to find such sequences with large periods. We also analyze the arithmetic cross-correlation between pairs of these sequences and show that it often vanishes identically.     

22号初等元胞自动机的演化复杂性

Cellular automata are the discrete dynamical systems of simple construction but with complex and varied behaviors. In this paper, the elementary cellular automaton of rule 22 is studied by the tools of formal language theory and symbolic dynamics. Its temporal evolution orbits are coarse-grained into evolution sequences and the evolution languages are defined. It is proved that for every n≥2 its width n evolution language is not regular.     

The n-centre problem of celestial mechanics for large energies

We consider the classical three-dimensional motion in a potential which is the sum of n attracting or repelling Coulombic potentials. Assuming a non-collinear configuration of the n centres, we find a universal behaviour for all energies E above a positive threshold. Whereas for n=1 there are no bounded orbits, and for n=2 there is just one closed orbit, for n≥3 the bounded orbits form a Cantor set. We analyze the symbolic dynamics and estimate Hausdorff dimension and topological entropy of this hyperbolic set. Then we set up scattering theory, including symbolic dynamics of the scattering orbits and differential cross section estimates. The theory includes the n–centre problem of celestial mechanics, and prepares for a geometric understanding of a class of restricted n-body problems. To allow for applications in semiclassical molecular scattering, we include an additional smooth (electronic) potential which is arbitrary except its Coulombic decay at infinity. Up to a (optimal) relative error of order 1/E, all estimates are independent of that potential but only depend on the relative positions and strengths of the centres. Finally we show that different, non-universal, phenomena occur for collinear configurations. Received October 16, 2000 / final version received June 18, 2001?Published online August 15, 2001     

The algebraic degree of geometric optimization problems

In this paper we apply Galois methods to certain fundamentalgeometric optimization problems whose exact computational complexity has been an open problem for a long time. In particular we show that the classic Weber problem, along with theline-restricted Weber problem and itsthree-dimensional version are in general not solvable by radicals over the field of rationals. One direct consequence of these results is that for these geometric optimization problems there existsno exact algorithm under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction ofkth roots. This leaves only numerical or symbolic approximations to the solutions, where the complexity of the approximations is shown to be primarily a function of the algebraic degree of the optimum solution point.     

An uncertainty principle for function fields

In a recent paper, Granville and Soundararajan (2007) [5] proved an “uncertainty principle” for arithmetic sequences, which limits the extent to which such sequences can be well-distributed in both short intervals and arithmetic progressions. In the present paper we follow the methods of Granville and Soundararajan (2007) [5] and prove that a similar phenomenon holds in Fq[t].     

Local-global principles for representations of quadratic forms

We prove a local-global principle for the problem of representations of quadratic forms by quadratic forms over ℤ, in codimension ≥5. The proof uses the ergodic theory of p-adic groups, together with a fairly general observation on the structure of orbits of an arithmetic group acting on integral points of a variety.     

Software to support numerical analysis teaching

This paper describes a Fortran90 library designed to support the teaching of numerical analysis and its applications. As well as covering traditional material it introduces recent and important ideas in numerical computation such as interval arithmetic and automatic differentiation. The library rests on a module realpac which provides real arithmetic in a range of precisions with a choice of rounding strategies. This, in turn, supports the implementation of an interval arithmetic module intpac. Derived data types and overloaded operations help inexperienced users to interface with unfamiliar data types such as intervals. The library also includes more conventional modules such as lepac for solving linear systems and minpac for nonlinear optimization. These, however, can be enhanced by being linked to more sophisticated tools for sparse matrix handling and automatic differentiation. As well as showing the main structure and scope of the software, the paper mentions some exercises that have successfully been performed by students.     

On Nilpotent Orbits of SL<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> and Sp<Subscript>2<Emphasis Type="Italic">n</Emphasis></Subscript> over a Local Non-Archimedean Field

We relate the partition-type parametrization of rational (arithmetic) nilpotent adjoint orbits of the classical groups SL _n and Sp_2n over local non-Archimedean fields with a parametrization, introduced by DeBacker in 2002, which uses the associated Bruhat-Tits building to relate the question to one over the residue field.     

Deformation Techniques for Sparse Systems

We exhibit a probabilistic symbolic algorithm for solving zero-dimensional sparse systems. Our algorithm combines a symbolic homotopy procedure, based on a flat deformation of a certain morphism of affine varieties, with the polyhedral deformation of Huber and Sturmfels. The complexity of our algorithm is cubic in the size of the combinatorial structure of the input system. This size is mainly represented by the cardinality and mixed volume of Newton polytopes of the input polynomials and an arithmetic analogue of the mixed volume associated to the deformations under consideration. Research was partially supported by the following grants: UBACyT X112 (2004–2007), UBACyT X847 (2006–2009), PIP CONICET 2461, PIP CONICET 5852/05, ANPCyT PICT 2005 17-33018, UNGS 30/3005, MTM2004-01167 (2004–2007), MTM2007-62799 and CIC 2007–2008.     

Computation of periodic orbits in three‐dimensional Lotka‐Volterra systems

This paper deals with an adaptation of the Poincaré‐Lindstedt method for the determination of periodic orbits in three‐dimensional nonlinear differential systems. We describe here a general symbolic algorithm to implement the method and apply it to compute periodic solutions in a three‐dimensional Lotka‐Volterra system modeling a chain food interaction. The sufficient conditions to make secular terms disappear from the approximate series solution are given in the paper.     

Direct Renormalizations of the One-Dimensional Torus

Renormalization formulas connecting the points of the orbits O ₀ ^± , i.e., the sequences generated by an irrational shift on the half-open interval [0, 1) or (0, 1], and the points of the orbits' derivatives d^mO ₀ ^± , i.e., the sequences obtained by restricting O ₀ ^± to half-open intervals of smaller length, are obtained. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 314, 2004, pp. 142–154.     

Computational existence proofs for spherical <Emphasis Type="Italic">t</Emphasis>-designs

Spherical t-designs provide quadrature rules for the sphere which are exact for polynomials up to degree t. In this paper, we propose a computational algorithm based on interval arithmetic which, for given t, upon successful completion will have proved the existence of a t-design with (t + 1)² nodes on the unit sphere S² ì \mathbbR³{S^2 \subset \mathbb{R}^3} and will have computed narrow interval enclosures which are known to contain these nodes with mathematical certainty. Since there is no theoretical result which proves the existence of a t-design with (t + 1)² nodes for arbitrary t, our method contributes to the theory because it was tested successfully for t = 1, 2, . . . , 100. The t-design is usually not unique; our method aims at finding a well-conditioned one. The method relies on computing an interval enclosure for the zero of a highly nonlinear system of dimension (t + 1)². We therefore develop several special approaches which allow us to use interval arithmetic efficiently in this particular situation. The computations were all done using the MATLAB toolbox INTLAB.     

Parallel Implementation of Stability Analysis of Difference Schemes with MATHEMATICA

We consider a parallel algorithm for investigating the stability of the schemes of the finite-difference and finite-volume methods that approximate the two-dimensional Euler equations of compressible fluid on a curvilinear grid. The algorithm is implemented with the aid of the computer algebra system Mathematica 3.0. We apply a two-level parallelization process. At the first level, the symbolic computation of the amplification matrix is parallelized by a parallel computation of the matrix rows on different processors. At the second level, the values of the coordinates of points of the stability-region boundary are computed numerically. For the communication between the workstations, we apply a special program, LaunchSlave, which uses the MathLink communication protocol. Examples of application of the proposed parallel symbolic/numerical algorithm are presented. Bibliography: 15 titles.     

The ERES method for computing the approximate GCD of several polynomials

The computation of the greatest common divisor (GCD) of a set of polynomials has interested the mathematicians for a long time and has attracted a lot of attention in recent years. A challenging problem that arises from several applications, such as control or image and signal processing, is to develop a numerical GCD method that inherently has the potential to work efficiently with sets of several polynomials with inexactly known coefficients. The presented work focuses on: (i) the use of the basic principles of the ERES methodology for calculating the GCD of a set of several polynomials and defining approximate solutions by developing the hybrid implementation of this methodology. (ii) the use of the developed framework for defining the approximate notions for the GCD as a distance problem in a projective space to develop an optimization algorithm for evaluating the strength of different ad-hoc approximations derived from different algorithms. The presented new implementation of ERES is based on the effective combination of symbolic–numeric arithmetic (hybrid arithmetic) and shows interesting computational properties for the approximate GCD problem. Additionally, an efficient implementation of the strength of an approximate GCD is given by exploiting some of the special aspects of the respective distance problem. Finally, the overall performance of the ERES algorithm for computing approximate solutions is discussed.     

On pricing arithmetic average reset options with multiple reset dates in a lattice framework

We develop a straightforward algorithm to price arithmetic average reset options with multiple reset dates in a Cox et al. (CRR) (1979) [10] framework. The use of a lattice approach is due to its adaptability and flexibility in managing arithmetic average reset options, as already evidenced by Kim et al. (2003) [9]. Their model is based on the Hull and White (1993) [5] bucketing algorithm and uses an exogenous exponential function to manage the averaging feature, but their choice of fictitious values does not guarantee the algorithm’s convergence (cfr., Forsyth et al. (2002) [11]). We propose to overcome this drawback by selecting a limited number of trajectories among the ones reaching each node of the lattice, where we compute effective averages. In this way, the computational cost of the pricing problem is reduced, and the convergence of the discrete time model to the corresponding continuous time one is guaranteed.     

Cutting sequences on square-tiled surfaces

We characterize cutting sequences of infinite geodesics on square-tiled surfaces by considering interval exchanges on specially chosen intervals on the surface. These interval exchanges can be thought of as skew products over a rotation, and we convert cutting sequences to symbolic trajectories of these interval exchanges to show that special types of combinatorial lifts of Sturmian sequences completely describe all cutting sequences on a square-tiled surface. Our results extend the list of families of surfaces where cutting sequences are understood to a dense subset of the moduli space of all translation surfaces.     

Entropy structure

Investigating the emergence of entropy on different scales, we propose an “entropy structure” as a kind of master invariant for the entropy theory of topological dynamical systems. An entropy structure is a sequence of functionsh _k on the simplex of invariant measures which converges to the entropy functionh and which falls into a distinguished equivalence class defined by a natural equivalence relation capturing the “type of nonuniformity in convergence”. An entropy structure recovers several existing invariants, including the symbolic extension entropy h_sex and the Misiurewicz parameter h^*. Entropy theories of Misiurewicz, Katok, Brin—Katok, Newhouse, Romagnoli, Ornstein—Weiss and others all yield candidate sequences (h _k); we determine which of these exhibit the correct type of convergence and hence become entropy structures. One of the satisfactory sequences arises from a new treatment of entropy theory strictly in terms of continuous functions (in place of partitions or covers). The results allow the computation of symbolic extension entropy without reference to zero dimensional extensions. New light is shed on the property of asymptotich-expansiveness. Supported by the KBN grant 2 P03 A 04622.