PaperlayerView exact revision on arXiv

Source-linked AI summary

Constellations for Lyapunov exponents

Nima Alibabaei

arXiv:2610.34306v1math.DScs.NAmath.NA

TL;DR

Explicit calculation of Lyapunov exponents for random matrix products is a longstanding challenge. The paper uses signed finite-support measures to approximate stationarity and gives a polynomial-arithmetic method for positive matrices.

  • Problem

    Explicit calculation of Lyapunov exponents for random matrix products has remained challenging, even in seemingly simple cases.

    Source: §1.1 · p. 2

  • Method

    The paper uses signed measures to approximate stationarity and establishes a clock inequality relating stationary defect to Lyapunov-exponent accuracy.

    Source: §1.3 · pp. 3–4

  • Results

    For positive matrices, the paper gives a method to calculate the Lyapunov exponent with arithmetic work polynomial in the number of requested digits.

    Source: §1 · p. 1

  • Takeaways & Limitations

    A finitely supported signed measure that is nearly invariant under one step can accurately predict the infinite-time Lyapunov exponent.

    Source: §1.3 · p. 4

    The polynomial-complexity calculation is stated for positive matrices; the general framework assumes nonnegative matrices with no zero rows.

    Source: §1 · p. 1, §1.2 · p. 3

Abstract

from arXiv · show

We study the maximal Lyapunov exponent of random products of positive matrices, and prove that it can be calculated to arbitrary precision with arithmetic work polynomial in the number of requested digits. In nondegenerate settings, the complexity of our method depends on the intrinsic complexity of the dynamics---which we characterize---and not on the Euclidean dimension of the ambient space in which the dynamics live. As numerical applications, we determine the Hausdorff dimension of random intersections of Sierpi\'nski gaskets, and Viswanath's constant---the growth rate of the random Fibonacci sequence. We first establish a general inequality for nonnegative matrix families showing that, if a signed measure with finite support is sufficiently close to being stationary, then it predicts the Lyapunov exponent accurately. This framework also encompasses Pollicott's Fredholm determinant approximation. We then show that, just like drawing a constellation by picking bright stars, one can construct a sequence of signed measures approximating stationarity by picking informative orbits of the projective dynamics. Furthermore, we prove that our construction uses an asymptotically optimal number of atoms, which is governed by an intrinsic quantity we call constellation dimension.

1 Introduction

The paper develops a polynomial-complexity method for calculating Lyapunov exponents of positive matrix products, using signed measures that approximate stationarity. It also characterizes when constellations achieve optimal approximation rates and applies the method to random Sierpiński-gasket intersections.

1 Introduction

  • For positive matrices, the paper gives a method to calculate the Lyapunov exponent with arithmetic work polynomial in the number of requested digits and applies it to random Sierpiński-gasket intersections.The introduction reports a Hausdorff-dimension determination for typical random intersections, but the supplied result passages do not include its value.Source: §1 · p. 1

1.1 Preliminaries

  • Explicit Lyapunov-exponent calculation has remained challenging, while earlier approaches have complexity or dimensional limitations that motivate a method for positive matrices of arbitrary dimension.The paper presents its approach as the first polynomial-complexity method for general families with d ≥ 2, to the author’s knowledge.Source: §1.1 · p. 2

1.2 Stationary measures

  • Stationarity describes measures invariant under the transfer operator, and the paper’s setup allows nonnegative matrices provided none has a zero row.A probability measure is stationary when L∗ν = ν.Source: §1.2 · p. 3

1.3 Main results I

  • The clock inequality shows that a finitely supported signed measure with small stationary defect can accurately predict the Lyapunov exponent.The defect is measured in the explicitly calculable K_a norm; the method selects informative orbits to reduce it and constructs constellations deterministically.Source: §1.3 · p. 4
  • The framework also recovers Pollicott’s convergence rate with an explicit error bound, while selecting informative orbits can yield more precision per point in tested examples.The comparison is with constellations supported on all periodic orbits of period at most N.Source: §1.3 · pp. 4–5

1.4 Main results II

  • Constellation dimensions characterize optimal approximation rates and are independent of the reference point; lower and upper dimensions may be fractional or unequal.An invertible subfamily imposes a lower bound through the algebraic dimension of its attractor.Source: §1.4 · p. 6
  • When the anchor lies in the attractor, the constructed constellations are asymptotically optimal in atom-count growth, and the paper relates this count to minimal model size.For a fully invertible family, the lower constellation dimension is a nonnegative integer.Source: §1.4 · pp. 6–7

1.5 Roadmap

  • The roadmap proceeds from the clock-based kernel and constellation construction to convergence and complexity proofs, then to dimension and optimality results.It also identifies appendices for the Fredholm-determinant connection, numerical comparison, and examples.Source: §1.5 · p. 7

2 Examples

The examples apply the method to random Sierpiński-gasket intersections and the random Fibonacci growth rate. They report certified precision for both applications and describe settings where existing conclusions or methods have limits.

Random Fibonacci sequence

  • The paper displays Viswanath’s constant to 128 decimal places, using its method on a nonnegative family that is not positive-conjugate.The printed number continues in the following passage.Source: §2 · p. 8
  • The Viswanath-constant computation used a 587-constellation with 623 distinct support points and took about five minutes on the author’s laptop.Source: §2 · p. 8

Sierpiński-gasket intersections

  • The method certifies the first 24 decimal places of the Hausdorff dimension for almost every gasket shift, improving on the reported bound 0.97 < dimH < 1.166.The passage does not include the certified decimal value.Source: §2 · p. 9
  • Pollicott’s Fredholm determinant method cannot be applied directly to the gasket example because one matrix has a nonsimple leading eigenvalue, invalidating the trace formula.For A2, det(xI − A2) = x^3(x − 1)^5.Source: §2 · p. 9

Liouville reset

  • The paper gives a Liouville-number example where the conclusion of Corollary 1.10 can fail for a positive 2×2 family with one singular matrix.Source: §2 · p. 10

3 Exponential clock and stationarity

The section introduces an exponential-clock experiment to represent the observables used in the Lyapunov-exponent estimate. It then connects the stationary defect of a constellation to control of the exponent and proves the clock inequality.

3.2 Proof of Theorem 1.3

  • For a constellation η, the proof studies its signed stationarity defect σ = η − L*η; averaged observables converge to λ for every interior x.The proof also uses boundedness to pass from almost-sure convergence to L1 convergence.Source: §3.1 · p. 10, §3.2 · p. 14

3.1 Exponential clock

  • The exponential-clock representation separates the point x from the product-dependent quantity p, compressing long-term matrix evolution into Gp,a.Source: §3.1 · pp. 10–11

4 Construction of constellations

The construction builds finite signed measures by adding projective point pairs chosen to reduce the stationarity defect. Its score search terminates, and the stationary equations determining each constellation have a unique solution.

4.1 Construction

  • The construction starts from an anchor and repeatedly enlarges an n-constellation by adding a selected non-diagonal pair, stopping when the error is zero.Source: §4.1 · pp. 14–15

4.2 Intuition behind the construction

  • The pair score balances potential future contributions qn against geometric separation ρ, while the stationary defect Dn measures the pair’s immediate usefulness.Source: §4.2 · p. 16

4.3 Proof of solvability

  • The stationary equations have a unique solution for their coefficients, and positive matrices contract the Hilbert-metric separation by a factor κ < 1.Source: §4.3 · p. 18

4.4 Proof of termination

  • When En > 0, the score search terminates after finitely many updates of the initial pair.Source: §4.4 · p. 20

5 Polynomial complexity

The section establishes that constellation error decreases exponentially in a fractional power of the number of atoms. It derives this rate by relating approximation spaces to volume, then counts the arithmetic work required by the construction.

5.5 Proof of Theorem 1.4

  • The constellation error En is exponentially small in n^(1/d), yielding the section’s convergence rate.Source: §5.1 · p. 21, §5.5 · p. 26

5.1 Overview

  • A large remaining error forces each newly accepted direction to add height, which bounds the squared volume, or Gram determinant, from below.Source: §5.1 · p. 21, §5.2 · p. 21

5.3 Exponentially small Kolmogorov width imposes small volume

  • The kernel family kx admits exponentially accurate approximation by a subspace with O(N^d) dimensions.Source: §5.3 · p. 22

5.4 From approximation space to the error bound

  • If a q-dimensional space approximates every kx in a forward-invariant set containing the anchor within γ, then E_(2(d+1)q)^(2(d+1)) ≤ Cγ^(1/4).Source: §5.4 · p. 25

5.5 Proof of Theorem 1.4

  • Updating and solving the stationary-equation factorization after adding a row and column costs O((n+1)^2) operations at step n.Source: §5.5 · p. 26

6 Constellation dimension

The section develops the operator and approximation-space tools used to define constellation dimension. It shows that the dimension is independent of a reference point and bounded above by the algebraic dimension of the stationary set’s support.

6 Constellation dimension

  • The covariance operator C_a is positive and trace class for every reference point a.The operator is defined from the map T_a between the reproducing-kernel Hilbert space H_a and L2(ν).Source: §6.1 · pp. 26–27

6.1 Constellation dimension is independent of the reference point

  • The spaces H_a coincide as sets of functions for all interior reference points, so both constellation dimensions are reference-point independent.The comparison of the associated norms yields independence of the lower and upper dimensions.Source: §6.1 · pp. 28–29

6.2 Algebraic dimension bounds the constellation dimension

  • Restrictions to K of degree-at-most-N polynomials have dimension growing polynomially with degree r, where r is the complex dimension of K’s Zariski closure.This follows by identifying the restricted polynomial space with the affine Hilbert function of the ideal of K.Source: §6.2 · pp. 29–30
  • The upper constellation dimension d* is at most r, the complex dimension of K’s Zariski closure.The proof uses polynomial approximations on K and a bound on the dimensions of their restricted spaces.Source: §6.2 · p. 31

7 Constellation dimension and minimality

This section shows that constellation dimension governs the asymptotic number of atoms needed for an accurate constellation. The lower and upper asymptotic exponents of minimal model size equal the corresponding constellation dimensions, and the paper’s construction attains those exponents.

7.1 Overview

  • The upper bound uses spectral approximation spaces, while the lower bound tests constellations with functions vanishing on their supports and replaces eigenfunctions when their Poisson solutions lack controlled Hilbert norms.The lower-bound strategy exploits the gap between what the stationary measure sees and what a finite-support constellation misses.Source: §7.1 · pp. 31–32

7.2 Stationary defect bounds the supremum

  • A stationary-defect inequality controls the supremum norm of mean-zero functions and yields an upper bound on the constellation size needed to achieve error ε when b∈K.The inequality links the supremum norm to the L2(ν) norm of u−Lu; the resulting size bound applies to n(ε), the least n with E_n≤ε.Source: §7.2 · pp. 33–34

7.3 Fractional kernel construction

  • For the lower exponent, a small power of the kernel yields a function whose square retains part of its stationary average and has a Poisson solution with bounded Hilbert norm.Source: §7.3 · p. 34

7.4 Connection to the Hardy kernel

  • The reproducing kernel is a restriction of the Hardy kernel through the coordinatewise Cayley transform, identifying H_a isometrically with a real Hilbert subspace.This Hardy-space viewpoint is used in the subsequent Poisson-equation arguments.Source: §7.4 · p. 36

7.5 Poisson equation with bounded norm

  • For each g with ν(g^2)=1, the construction yields a Poisson solution h_g∈H_a whose norm is bounded independently of g.It sums terms G_n with geometrically decaying H_a norms to obtain the solution.Source: §7.5 · pp. 36, 38, 40
  • The proof completes the Poisson equation by passing to the limit in equation (7.21), obtaining equation (7.11).The series converges at the relevant point and at each of the finitely many support points.Source: §7.5 · p. 41

7.6 Exponents for minimal model size

  • Proposition 7.10 bounds the stationary defect of every constellation with at most r support points from below using the eigenvalues.The proof selects a nonzero combination of r + 1 eigenfunctions whose kernel average vanishes on the constellation’s support, then compares eigenvalue and Poisson-solution bounds.Source: §7.6 · p. 41
  • For sufficiently small ε and fixed 0 < c < 1/4, any constellation with stationary defect at most ε has at least N_a(c log(1/ε)) − 1 support points.The bound follows by relating the defect to the eigenvalue tail and counting eigenvalues at least e^−t.Source: §7.6 · p. 42
  • For fixed b ∈ K and all sufficiently small ε > 0, the constellation η(ε) in Theorem 1.11 is η_n(ε), where n(ε) is the least nonnegative integer with E_n(ε) ≤ ε.Source: §7.6 · p. 42

8 Invertibility and algebraic dimension

The section uses invertibility to build polynomial subspaces whose functions resist cancellation, then relates their dimensions to the algebraic dimension of the projective attractor. This yields a lower bound on the constellation dimension and, with the earlier upper bound, characterizes it in the stated setting.

8.1 Overview

  • Invertibility enables localized polynomial bump functions that keep each generator visible on its own copy of K0 and suppress cancellation from the others.Pullbacks compress polynomials onto small copies, while Lagrange-interpolation analogues suppress their values on other selected copies.Source: §8.1 · p. 43, §8.3 · p. 45

8.2 Polynomial observations in the Hilbert space

  • Multiplying a polynomial P by ω_n places ω_nP in H_a with norm at most the polynomial’s supremum norm on the complex closed polydisk.On the simplex, the multiplier also satisfies e^-n ≤ ω_n(x) ≤ 1.Source: §8.2 · p. 44

8.3 Preventing cancellation

  • For every s below dim_C K0^Zar, the construction supplies polynomial spaces E_ℓ with dimension q^ℓ and parameters q > Λ^s.These spaces are built inductively using compressed polynomials and bump-like factors that separate selected copies.Source: §8.3 · pp. 44–46

8.4 Completion of the proofs of the main theorems

  • For invertible families with an attractor of positive algebraic dimension, the lower constellation dimension is at least every s below that dimension.The proof constructs increasingly large subspaces and applies the Min–Max principle to bound their stationary defects from below.Source: §8.4 · pp. 46–47
  • With two invertible matrices having distinct Perron–Frobenius vectors, the attractor is infinite and the lower constellation dimension is at least one.A finite attractor would be permuted by the injective projective maps, and contraction would force it to be a singleton, contradicting the distinct vectors.Source: §8.4 · p. 47

A Reduction of the random Fibonacci sequence

The appendix reduces the random Fibonacci sequence to an i.i.d. representation using four matrices. It encodes the original choices as steps in a free product after applying matrix cancellations.

A.1 Background

  • Matrix cancellations reduce the random Fibonacci choices to steps b and ab in a free product, represented by generators of orders three and two.The order-three generator is represented by B−, and the order-two generator by B+B2−.Source: §A.1 · p. 47
  • The explicit traffic-equation solution for random walks on free products supplied the initial four-matrix i.i.d. representation.The direct proof was developed after the representation was obtained.Source: §A.1 · p. 47

A.2 Proof √

The two-step process Y is related to the original matrix family by transferring a stationary measure from Y to one for the original family. The reflection symmetry makes the logarithmic growth averages agree, giving Y Lyapunov exponent λred/2.

A.2 Proof √

  • Y has Lyapunov exponent λred/2 because its two-step choices have probabilities q4, q3, q3, q2, matching π0, π1, π2, π3.The passage states that a stationary measure for Y can be used to construct one for the original family.Source: §A.2 · p. 48
  • A stationary measure μ for Y supported on the nonnegative cone yields a stationary measure ν for the original family.The transfer identity is L*μ = ν, and reflection symmetry gives stationarity of ν.Source: §A.2 · p. 48
  • The reflection DB+ = −B− and DB− = −B+ interchanges the logarithmic averages, so the two choices in Y have the same growth.The averages are evaluated using stationarity of μ and the stationary-measure formula for ν.Source: §A.2 · pp. 48–49

B Constellation dimension for the Sierpi´nski gasket family

For the Sierpiński gasket family, algebraic relations explain constellation dimension d*=4. In the Liouville reset example, the number of distinguishable orbit points depends on the resolution because rational approximations can make many points nearly identical.

B Constellation dimension for the Sierpi´nski gasket family

  • The Sierpiński gasket family has constellation dimension d*=4: algebraic relations give a lower bound of 4, while containment in finitely many affine spaces gives an upper bound of 4.The lower-bound argument uses copies of a fractal of algebraic dimension 3 on distinct hyperplanes; the upper-bound argument uses six spaces and a boundary estimate.Source: B Constellation dimension for the… · p. 49
  • The attractor contains countably many copies of a fractal of algebraic dimension 3, and repeated application of A2 supplies the additional dimension.The copies lie on distinct hyperplanes, with (x7 − x3)/x2 recording which copy contains a point.Source: B Constellation dimension for the… · p. 49

C Liouville reset example

  • In the Liouville reset example, unusually accurate rational approximations can make many orbit points nearly identical at some resolutions, while separate counts j and k remain distinguishable at others.The singular A0 acts as a reset in the projective dynamics.Source: C Liouville reset example · pp. 49–50

C.1 Lower bounds

The lower- and upper-bound arguments establish matching constellation-dimension bounds in two settings. The Fredholm determinant truncation also gives an explicit approximation to the Lyapunov exponent through a functional represented by orbit data.

C.1 Lower bounds

  • Separated orbit points with indices j+k ≤ h force σm ≥ e^(−2Cmh), yielding d* ≥ 2/3 in the Liouville argument.The proof applies the separation claim to q_n^2 orbit points and obtains σ_(q_n^2) ≥ e^(−6Cq_n^3).Source: §C.1 · pp. 50–51
  • The points a_(j,0) give σm ≥ e^(−4Cm^2) for every m, proving d* ≥ 1/2.Source: §C.1 · p. 50

C.2 Upper bounds

  • For the Liouville example, the upper-bound argument proves d* ≤ 2/3.It uses the orbit points with j+k ≤ h as interpolation points and obtains σ_(M+1) ≤ e^(−c′h^3).Source: §C.2 · p. 51
  • A second upper-bound argument proves d* ≤ 1/2 using a bound on the number of points near a reference.The passage gives N_a(c0M^2/q_n) ≤ M+1.Source: §C.2 · pp. 51–52

D.1 The Fredholm determinant and its truncation

  • Pollicott’s Fredholm determinant approximation can be expressed as a truncated determinant functional that approximates the Lyapunov exponent.The construction evaluates the functional using fixed points of cyclic word maps; the cited theorem gives an approximation bλN to λ.Source: D Fredholm determinants and… · p. 52, §D.1 · pp. 52–53

D.2 The resulting constellation exhibits decay in stationary defect

The determinant truncation defines a signed measure with real weights and mass one, hence a constellation. For an interior reference point, the resulting constellation exhibits decay in stationary defect.

D.2 The resulting constellation exhibits decay in stationary defect

  • The truncated determinant functional IN is integration against a signed measure with real weights and mass one, making it a constellation.Source: §D.2 · pp. 53–54
  • For every interior reference point a, Proposition D.3 establishes decay in the constellation’s stationary defect as the truncation order increases.The proof extends test functions holomorphically and applies determinant coefficient estimates.Source: §D.2 · pp. 54–55

E Comparison to the Fredholm determinant approach

On a nine-matrix positive invertible family, the section contrasts certified constellation and Fredholm approximations. The former has polynomial arithmetic complexity in log(1/ε), while the latter is subexponential.

E Comparison to the Fredholm determinant approach

Loading 2610.34306v1…