© 2014 London Mathematical Society.The lower spectral radius, or joint spectral subradius, of a set of real d \times d matrices is defined to be the smallest possible exponential growth rate of long products of matrices drawn from that set. The lower spectral radius arises naturally in connection with a number of topics including combinatorics on words, the stability of linear inclusions in control theory, and the study of random Cantor sets. In this article, we apply some ideas originating in the study of dominated splittings of linear cocycles over a dynamical system to characterize the points of continuity of the lower spectral radius on the set of all compact sets of invertible d \times d matrices. As an application, we exhibit open sets of pairs of 2 \times 2 matrices within which the analogue of the Lagarias-Wang finiteness property for the lower spectral radius fails on a residual set, and discuss some implications of this result for the computation of the lower spectral radius.
Abstract. Given a nite irreducible set of real d d matrices A1; : : : ;AM and a real parameter s > 0, there exists a unique shift-invariant equilibrium state on f1; : : : ;MgN associated to (A1; : : : ;AM; s). In this article we characterise the ergodic properties of such equilibrium states in terms of the algebraic properties of the semigroup generated by the associated matrices. We completely characterise when the equilibrium state has zero entropy, when it gives distinct Lyapunov exponents to the natural cocycle generated by A1; : : : ;AM, and when it is a Bernoulli measure. We also give a general su cient condition for the equilibrium state to be mixing, and give an example where the equilibrium state is ergodic but not totally ergodic. Connections with a class of measures investigated by S. Kusuoka are explored in an appendix.
© 2015, Hebrew University of Jerusalem.Furstenberg, Katznelson and Weiss proved in the early 1980s that every measurable subset of the plane with positive density at infinity has the property that all sufficiently large real numbers are realised as the Euclidean distance between points in that set. Their proof used ergodic theory to study translations on a space of Lipschitz functions corresponding to closed subsets of the plane, combined with a measure-theoretical argument. We consider an alternative dynamical approach in which the phase space is given by the set of measurable functions from ?d to [0, 1], which we view as a compact subspace of L?(?d) in the weak-* topology. The pointwise ergodic theorem for ?d-actions implies that with respect to any translation-invariant measure on this space, almost every function is asymptotically close to a constant function at large scales. This observation leads to a general sufficient condition for a configuration to occur in every set of positive upper Banach density at all sufficiently large scales. To illustrate the use of this criterion we apply it to prove a new result concerning three-point configurations in measurable subsets of the plane which form the vertices of a triangle with specified area and side length, yielding a new proof of a result related to work of R. Graham.
We investigate a formula of K. Falconer which describes the typical value of the generalised R´enyi dimension, or generalised q-dimension, of a selfaffine measure in terms of the linear components of the affinities. We show that in contrast to a related formula for the Hausdorff dimension of a typical self-affine set, the value of the generalised q-dimension predicted by Falconer?s formula varies discontinuously as the linear parts of the affinities are changed. Conditionally on a conjecture of J. Bochi and B. Fayad, we show that the value predicted by this formula for pairs of two-dimensional affine transformations is discontinuous on a set of positive Lebesgue measure. These discontinuities derive from discontinuities of the lower spectral radius which were previously observed by the author and J. Bochi.
We study the existence of solutions g to the functional inequality fdg T?g+², where f is a prescribed continuous function, T is a weakly expanding transformation of the circle having an indifferent fixed point, and ² is the maximum ergodic average of f. Using a method due to T. Bousch, we show that continuous solutions g always exist when the Hölder exponent of f is close to 1. In the converse direction, we construct explicit examples of continuous functions f with low Hölder exponent for which no continuous solution g exists. We give sharp estimates on the best possible Hölder regularity of a solution g given the Hölder regularity of f.
Using ergodic theory we prove two formulae describing the relationships between different notions of joint spectral radius for sets of bounded linear operators acting on a Banach space. The first formula was previously obtained by V.S. Shulman and Yu.V. Turovski- using operator-theoretic ideas. The second formula shows that the joint spectral radii corresponding to several standard measures of noncompactness share a common value when applied to a given precompact set of operators. This result may be seen as an extension of classical formulae for the essential spectral radius given by R. Nussbaum, A. Lebow and M. Schechter. Both results are obtained as a consequence of a more general theorem concerned with continuous operator cocycles defined over a compact dynamical system. As a byproduct of our method we answer a question of J.E. Cohen on the limiting behaviour of the spectral radius of a measurable matrix cocycle.
Morris ID (2015) A rigorous version of R.P. Brent?s model for the binary Euclidean algorithm, Advances in Mathematics 290 pp. 73-143 Elsevier
The binary Euclidean algorithm is a modification of the classical Euclidean algorithm for computation of greatest common divisors which avoids ordinary integer division in favour of division by powers of two only. The expectation of the number of steps taken by the binary Euclidean algorithm when applied to pairs of integers of bounded size was first investigated by R.P. Brent in 1976 via a heuristic model of the algorithm as a random dynamical system. Based on numerical investigations of the expectation of the associated Ruelle transfer operator, Brent obtained a conjectural asymptotic expression for the mean number of steps performed by the algorithm when processing pairs of odd integers whose size is bounded by a large integer. In 1998 B. Vallée modified Brent's model via an induction scheme to rigorously prove an asymptotic formula for the average number of steps performed by the algorithm; however, the relationship of this result with Brent's heuristics remains conjectural. In this article we establish previously conjectural properties of Brent's transfer operator, showing directly that it possesses a spectral gap and preserves a unique continuous density. This density is shown to extend holomorphically to the complex right half-plane and to have a logarithmic singularity at zero. By combining these results with methods from classical analytic number theory we prove the correctness of three conjectured formulae for the expected number of steps, resolving several open questions promoted by D.E. Knuth in The Art of Computer Programming.
The joint spectral radius of a bounded set of d × d real matrices is defined to be the maximum possible exponential growth rate of products of matrices drawn from that set. For a fixed set of matrices, a sequence of matrices drawn from that set is called extremal if the associated sequence of partial products achieves this maximal rate of growth. An influential conjecture of J. Lagarias and Y. Wang asked whether every finite set of matrices admits an extremal sequence which is periodic. This is equivalent to the assertion that every finite set of matrices admits an extremal sequence with bounded subword complexity. Counterexamples were subsequently constructed which have the property that every extremal sequence has at least linear subword complexity. In this paper we extend this result to show that for each integer p e 1, there exists a pair of square matrices of dimension 2p(2p+1-1) for which every extremal sequence has subword complexity at least 2 p2. © 2013 Cambridge Philosophical Society.
A fundamental problem in the dimension theory of self-affine sets is the construction of high-
dimensional measures which yield sharp lower bounds for the Hausdorff dimension of the set.
A natural strategy for the construction of such high-dimensional measures is to investigate
measures of maximal Lyapunov dimension; these measures can be alternatively interpreted as
equilibrium states of the singular value function introduced by Falconer. Whilst the existence
of these equilibrium states has been well-known for some years their structure has remained
elusive, particularly in dimensions higher than two. In this article we give a complete description
of the equilibrium states of the singular value function in the three-dimensional case, showing
in particular that all such equilibrium states must be fully supported. In higher dimensions we
also give a new sufficient condition for the uniqueness of these equilibrium states. As a corollary,
giving a solution to a folklore open question in dimension three, we prove that for a typical
self-affine set in R
3, removing one of the affine maps which defines the set results in a strict
reduction of the Hausdorff dimension.
We prove an a priori lower bound for the pressure, or p-norm joint spectral radius, of a measure on the set of d × d real matrices which parallels a result of J. Bochi for the joint spectral radius. We apply this lower bound to give new proofs of the continuity of the affinity dimension of a selfaffine set and of the continuity of the singular-value pressure for invertible matrices, both of which had been previously established by D.-J. Feng and P. Shmerkin using multiplicative ergodic theory and the subadditive variational principle. Unlike the previous proof, our lower bound yields algorithms to rigorously compute the pressure, singular value pressure and affinity dimension of a finite set of matrices to within an a priori prescribed accuracy in finitely many computational steps. We additionally deduce a related inequality for the singular value pressure for measures on the set of 2 × 2 real matrices, give a precise characterisation of the discontinuities of the singular value pressure function for two-dimensional matrices, and prove a general theorem relating the zero-temperature limit of the matrix pressure to the joint spectral radius.
The lower spectral radius of a set of d d matrices is de ned to be the minimum possible exponential growth rate of long products of matrices drawn from that set. When considered as a function of a nite set of matrices of xed cardinality it is known that the lower spectral radius can vary discontinuously as a function of the matrix entries. In a previous article the author and J. Bochi conjectured that when considered as a function on the set of all pairs of 2 2 real matrices, the lower spectral radius is discontinuous on a set of positive (eight-dimensional) Lebesgue measure, and related this result to an earlier conjecture of Bochi and Fayad. In this article we investigate the continuity of the lower spectral radius in a simpli ed context in which one of the two matrices is assumed to be of rank one. We show in particular that the set of discontinuities of the lower spectral radius on the set of pairs of 2 2 real matrices has positive seven-dimensional Lebesgue measure, and that among the pairs of matrices studied, the niteness property for the lower spectral radius is true on a set of full Lebesgue measure but false on a residual set.
Under mild conditions we show that the affinity dimension of a
planar self-affine set is equal to the supremum of the Lyapunov dimensions
of self-affine measures supported on self-affine proper subsets of the original
set. These self-affine subsets may be chosen so as to have stronger separation
properties and in such a way that the linear parts of their affinities are positive
matrices. Combining this result with some recent breakthroughs in the study
of self-affine measures and their associated Furstenberg measures, we obtain
new criteria under which the Hausdorff dimension of a self-affine set equals its
affinity dimension. For example, applying recent results of Barany, Hochman-
Solomyak and Rapaport, we provide many new explicit examples of self-affine
sets whose Hausdorff dimension equals its affinity dimension, and for which
the linear parts do not satisfy any positivity or domination assumptions.
Since the 1970s there has been a rich theory of equilibrium states
over shift spaces associated to Holder-continuous real-valued potentials. The
construction of equilibrium states associated to matrix-valued potentials is
much more recent, with a complete description of such equilibrium states being
achieved in 2011 by D.-J. Feng and A. Kaenmaki. In a recent article the author
investigated the ergodic-theoretic properties of these matrix equilibrium states,
attempting in particular to give necessary and sufficient conditions for mixing,
positive entropy, and the property of being a Bernoulli measure with respect
to the natural partition, in terms of the algebraic properties of the semigroup
generated by the matrices. Necessary and sufficient conditions were successfully
established for the latter two properties but only a sufficient condition for
mixing was given. The purpose of this note is to complete that investigation
by giving a necessary and sufficient condition for a matrix equilibrium state
to be mixing.
Motivated by recent investigations of ergodic optimisation for matrix cocycles, we study the measures of maximum top Lyapunov exponent for pairs of bounded weighted shift operators on a separable Hilbert space. We prove that for generic pairs of weighted shift operators the Lyapunovmaximising measure is unique, and show that there exist pairs of operators whose unique Lyapunov-maximising measure takes any prescribed value less than log 2 for its metric entropy. We also show that in contrast to the matrix case, the Lyapunov-maximising measures of pairs of bounded operators are in general not characterised by their supports: we construct explicitly a pair of operators, and a pair of ergodic measures on the 2-shift with identical supports, such that one of the two measures is Lyapunov-maximising for the pair of operators and the other measure is not. Our proofs make use of the Ornstein d-metric to estimate di erences in the top Lyapunov exponent of a pair of weighted shift operators as the underlying measure is varied.
We completely describe the equilibrium states of a class of
potentials over the full shift which includes Falconer's singular value
function for affine iterated function systems with invertible affinities.
We show that the number of distinct ergodic equilibrium states of such
a potential is bounded by a number depending only on the dimension,
answering a question of A. Käenmäki. We prove that all such equilibrium
states are fully supported and satisfy a Gibbs inequality with
respect to a suitable subadditive potential. We apply these results to
demonstrate that the affinity dimension of an iterated function system
with invertible affinities is always strictly reduced when any one of the
maps is removed, resolving a folklore open problem in the dimension
theory of self-affine fractals. We deduce a natural criterion under which
the Hausdorff dimension of the attractor has the same strict reduction
In this note we investigate some properties of equilibrium states of affine iterated function
systems, sometimes known as Kaenmaki measures. We give a simple sufficient condition for
Kaenmaki measures to have a gap between certain specific pairs of Lyapunov exponents, partially
answering a question of B. Barany, A. Kaenmaki and H. Koivusalo. We also give sharp bounds for
the number of ergodic Kaenmaki measures in dimensions up to 4, answering a question of J. Bochi
and the author within this range of dimensions. Finally, we pose an open problem on the Hausdorff
dimension of self-affine measures which may be reduced to a statement concerning semigroups of
matrices in which a particular weighted product of absolute eigenvalues is constant.
Versions of the Oseledets multiplicative ergodic theorem for cocycles acting on infinite-dimensional Banach spaces have been investigated since the pioneering work of Ruelle in 1982 and are a topic of continuing research interest. For a cocycle to induce a continuous splitting in which the growth in one subbundle exponentially dominates the growth in another requires additional assumptions; a necessary and sufficient condition for the existence of such a dominated splitting was recently given by J. Bochi and N. Gourmelon for invertible finite-dimensional cocycles in discrete time. We extend this result to cocycles of injective bounded linear maps acting on Banach spaces (in both discrete and continuous time) using an essentially geometric approach based on a notion of approximate singular value decomposition in Banach spaces. Our method is constructive, and in the finite-dimensional case yields explicit growth estimates on the dominated splitting which may be of independent interest.
In topics such as the thermodynamic formalism of linear cocycles, the dimension theory of self-affine sets, and the theory of random matrix products, it has often been found useful to assume positivity of the matrix entries in order to simplify or make feasible certain types of calculation. It is natural to ask how positivity may be relaxed or generalised in a way which enables similar calculations to be made in more general contexts. On the one hand one may generalise by considering almost additive or asymptotically additive potentials which mimic the properties enjoyed by the logarithm of the norm of a positive matrix cocycle; on the other hand one may consider matrix cocycles which are dominated, a condition which includes positive matrix cocycles but is more general. In this article we explore the relationship between almost additivity and domination for planar cocycles. We show in particular that a locally constant linear cocycle in the plane is almost additive if and only if it is either conjugate to a cocycle of isometries, or satisfies a property slightly weaker than domination which is introduced in this paper. Applications to matrix thermodynamic formalism are presented.
We study the top Lyapunov exponents of random products of positive 2×2 matrices and obtain an efficient algorithm for its computation. As in the earlier work of Pollicott, the algorithm is based on the Fredholm theory of determinants of trace-class linear operators. In this article we obtain a simpler expression for the approximations which only require calculation of the eigenvalues of finite matrix products and not the eigenvectors. Moreover, we obtain effective bounds on the error term in terms of two explicit constants: a constant which describes how far the set of matrices are from all being column stochastic, and a constant which measures the minimal amount of projective contraction of the positive quadrant under the action of the matrices.
The sub-additive pressure function P(s) for an a?ne iterated function system (IFS) and the a?nity dimension, de?ned as the unique solution s0 to P(s0) = 1, were introduced by K. Falconer in his seminal 1988 paper on self-a?ne fractals. The a?nity dimension prescribes a value for the Hausdor? dimension of a self-a?ne set which is known to be correct in generic cases and in an increasing range of explicit cases. It was shown by Feng and Shmerkin in 2014 that the a?nity dimension depends continuously on the IFS. In this article we prove that when the linear parts of the a?nities which de?ne the IFS are 2×2 matrices which strictly preserve a common cone, the sub-additive pressure is locally real analytic as a function of the matrix coe?cients of the linear parts of the a?nities. In this setting we also show that the sub-additive pressure is piecewise real analytic in s, implying that the a?nity dimension is locally analytic in the matrix coe?cients. Combining this with a recent result of B´ar´any, Hochman and Rapaport we obtain results concerning the analyticity of the Hausdor? dimension for certain families of planar self-a?ne sets.