# Degree of recurrence of generic diffeomorphisms

Pierre-Antoine Guih neuf  Université Paris-Sud
Universidade Federal Fluminense, Niter i
IMJ-PRG<EMAIL_ADDRESS>
###### Abstract.

We study the spatial discretizations of dynamical systems: can we recover some
dynamical features of a system from numerical simulations? Here, we tackle
this issue for the simplest algorithm possible: we compute long segments of
orbits with a fixed number of digits. We show that for every $r>1$, the
dynamics of the discretizations of a $C^{r}$ generic conservative
diffeomorphism of the torus is very different from that observed in the
$C^{0}$ regularity. The proof of our results involves in particular a local-
global formula for discretizations, as well as a study of the corresponding
linear case, which uses ideas from the theory of quasicrystals.

###### 1991 Mathematics Subject Classification:

37M05, 37A05, 37A45, 37C20, 52C23

###### Contents

  1. 1 Introduction
  2. 2 Discretizations of sequences of linear maps
  3. 3 A local-global formula
  4. 4 Asymptotic rate of injectivity for a generic conservative diffeomorphism
  5. 5 Asymptotic rate of injectivity for a generic dissipative diffeomorphism
  6. 6 Asymptotic rate of injectivity of a generic expanding map
  7. 7 Numerical simulations
  8. A A more general setting where the theorems are still true

##  1\. Introduction

This paper is concerned with the issue of numerical experiments on dynamical
systems. More precisely, consider a discrete-time dynamical system $f$ on the
torus $\mathbf{T}^{n}=\mathbf{R}^{n}/\mathbf{Z}^{n}$ endowed with Lebesgue
measure111We will see in Appendix A a more general framework where our results
remain true., and define some spatial discretizations of this system in the
following way: consider the collection $(E_{N})_{N\in\mathbf{N}}$ of uniform
grids on $\mathbf{T}^{n}$

$E_{N}=\left\\{\left(\frac{i_{1}}{N},\cdots,\frac{i_{n}}{N}\right)\in\mathbf{R}^{n}/\mathbf{Z}^{n}\middle|\
1\leq i_{1},\cdots,i_{n}\leq N\right\\},$

and define a Euclidean projection $P_{N}$ on the nearest point of $E_{N}$; in
other words $P_{N}(x)$ is (one of) the point(s) of $E_{N}$ which is the
closest from $x$. This projection allows to define the discretizations of $f$.

######  Definition 1.

The _discretization_ $f_{N}:E_{N}\to E_{N}$ of $f$ on the grid $E_{N}$ is the
map $f_{N}=P_{N}\circ f_{|E_{N}}$.

Such discretizations $f_{N}$ are supposed to reflect what happens when
segments of orbits of the system $f$ are computed with a computer: in
particular, if we take $N=10^{k}$, the discretization models computations made
with $k$ decimal places. The question we are interested in is then the
following: can the dynamics of the system $f$ be inferred from the dynamics of
(some of) its discretizations $f_{N}$?

Here, we will focus on a number associated to the combinatorics of the
discretizations, called the degree of recurrence. As every discretization is a
finite map $f_{N}:E_{N}\to E_{N}$, each of its orbits is eventually periodic.
Thus, the sequence of sets $(f_{N}^{k}(E_{N}))_{k\in\mathbf{N}}$ (the order of
discretization $N$ being fixed) is eventually constant, equal to a set
$\Omega(f_{N})$ called the _recurrent set_ 222Note that a priori,
$(f_{N})^{k}\neq(f^{k})_{N}$.. This set coincides with the union of the
periodic orbits of $f_{N}$; it is the biggest subset of $E_{N}$ on which the
restriction of $f_{N}$ is a bijection. Then, the _degree of recurrence_ of
$f_{N}$, denoted by $D(f_{N})$, is the ratio between the cardinality of
$\Omega(f_{N})$ and the cardinality of the grid $E_{N}$.

######  Definition 2.

Let $E$ be a finite set and $\sigma:E\to E$ be a finite map on $E$. The
_recurrent set_ of $\sigma$ is the union $\Omega(\sigma)$ of the periodic
orbits of $\sigma$. The _degree of recurrence_ of the finite map $\sigma$ is
the ratio

$D(\sigma)=\frac{\operatorname{Card}\big{(}\Omega(\sigma)\big{)}}{\operatorname{Card}(E)}.$

This degree of recurrence $D(f_{N})\in[0,1]$ represents the loss of
information induced by the iteration of the discretization $f_{N}$. For
example if $D(f_{N})=1$, then $f_{N}$ is a bijection. Also, a finite map with
a degree of recurrence equal to 1 preserves the uniform measure on $E_{N}$,
and thus can be considered as _conservative_.

The goal of this paper is to study the behaviour of the degree of recurrence
$D(f_{N})$ as $N$ goes to infinity and for a _generic_ dynamics $f$ of the
torus $\mathbf{T}^{n}$, $n\geq 2$. More precisely, on every Baire space
$\mathcal{B}$ it is possible to define a good notion of genericity: a property
on elements of $\mathcal{B}$ will be said _generic_ if satisfied on at least a
countable intersection of open and dense subsets of $\mathcal{B}$.

For our purpose, the spaces $\operatorname{Diff}^{r}(\mathbf{T}^{n})$ and
$\operatorname{Diff}^{r}(\mathbf{T}^{n},\operatorname{Leb})$ of respectively
$C^{r}$-diffeomorphisms and Lebesgue measure preserving
$C^{r}$-diffeomorphisms of $\mathbf{T}^{n}$ are Baire spaces for every
$r\in[0,+\infty]$, when endowed with the classical metric on
$C^{r}$-diffeomorphisms333For example,
$d_{C^{1}}(f,g)=\sup_{x\in\mathbf{T}^{n}}d(f(x),g(x))+\sup_{x\in\mathbf{T}^{n}}\|Df_{x}-Dg_{x}\|$..
Elements of $\operatorname{Diff}^{r}(\mathbf{T}^{n})$ will be called
_dissipative_ and elements of
$\operatorname{Diff}^{r}(\mathbf{T}^{n},\operatorname{Leb})$ _conservative_.
Also, the spaces $\operatorname{Diff}^{0}(\mathbf{T}^{n})$ and
$\operatorname{Diff}^{0}(\mathbf{T}^{n},\operatorname{Leb})$ of homeomorphisms
will be denoted by respectively $\operatorname{Homeo}(\mathbf{T}^{n})$ and
$\operatorname{Homeo}(\mathbf{T}^{n},\operatorname{Leb})$.

We will also consider the case of generic expanding maps of the circle.
Indeed, for any $r\in[1,+\infty]$, the space $\mathcal{D}^{r}(\mathbf{S}^{1})$
of $C^{r}$ expanding maps444Recall that a $C^{1}$ map $f$ is _expanding_ if
for every $x\in\mathbf{S}^{1}$, $|f^{\prime}(x)|>1$. of the circle
$\mathbf{S}^{1}$, endowed with the classical $C^{r}$ topology, is a Baire
space.

The study of generic dynamics is motivated by the phenomenon of resonance that
appears on some very specific examples like that of the linear automorphism of
the torus $(x,y)\mapsto(2x+y,x+y)$: as noticed by É. Ghys in [Ghy94], the fact
hat this map is linear with integer coefficients forces the discretizations on
the uniform grids to be bijections with a (very) small order (see also [DF92]
or the introduction of [Gui15a]). One can hope that this behaviour is
exceptional; to avoid them, É. Ghys proposes to study the case of generic
maps.

To begin with, let us recall what happens for generic homeomorphisms. The
following result can be found in Section 5.2 of [Gui15b].

######  Theorem 3 (Guihéneuf).

Let $f\in\operatorname{Homeo}(\mathbf{T}^{n})$ be a generic dissipative
homeomorphism. Then $D(f_{N})\underset{N\to+\infty}{\longrightarrow}0$.

This theorem expresses that there is a total loss of information when a
discretization of a generic homeomorphism is iterated. This is not surprising,
as a generic dissipative homeomorphism has an “attractor dynamics” (see for
example [AA13]). The following result is the Corollary 5.24 of [Gui15a] (see
also Section 4.3 of [Gui15b] and Proposition 2.2.2 of [Mie05]).

######  Theorem 4 (Guihéneuf, Miernowski).

Let $f\in\operatorname{Homeo}(\mathbf{T}^{n},\operatorname{Leb})$ be a generic
conservative homeomorphism. Then the sequence $(D(f_{N}))_{N\in\mathbf{N}}$
accumulates on the whole segment $[0,1]$.

Thus, the degree of recurrence of a generic _conservative_ homeomorphism
accumulates on the biggest set on which it can a priori accumulate. Then, the
behaviour of this combinatorial quantity depends a lot on the order $N$ of the
discretization and not at all on the dynamics of the homeomorphism $f$.
Moreover, as there exists a subsequence $(N_{k})_{k\in\mathbf{N}}$ such that
$D(f_{N})\underset{N\to+\infty}{\longrightarrow}0$, there exists “a lot” of
discretizations that do not reflect the conservative character of the
homeomorphism.

In this paper, we study the asymptotic behaviour of the degree of recurrence
in higher regularity. Our results can be summarized in the following theorem
(see Corollary 42, Theorem 39 and Corollary 49).

######  Theorem A.

Let $r\in[1,+\infty]$ and $f$ be either

  * •

a generic dissipative $C^{1}$-diffeomorphism of $\mathbf{T}^{n}$;

  * •

a generic conservative $C^{r}$-diffeomorphism of $\mathbf{T}^{n}$;

  * •

a generic $C^{r}$ expanding map555This point was previously announced by P.P.
Flockerman and O. E. Lanford, but remained unpublished, see [Flo02]. of the
circle $\mathbf{S}^{1}$;

Then

$D(f_{N})\underset{N\to+\infty}{\longrightarrow}0.$

We must admit that the degree of recurrence gives only little information
about the dynamics of the discretizations. Theorem A becomes interesting when
compared to the corresponding case in $C^{0}$ regularity: in the conservative
setting, it indicates that the bad behaviours observed for generic
conservative homeomorphisms should disappear in any higher regularity: the
behaviour of the rate of injectivity is less irregular for generic
conservative $C^{r}$ diffeomorphisms than for generic conservative
homeomorphisms (compare Theorems 4 and A). This big difference suggests that
the wild behaviours of the global dynamics of discretizations of generic
conservative homeomorphisms observed in [Gui15b] may not appear for higher
regularities. For example, we can hope that — contrary to what happens for
generic conservative homeomorphisms — it is possible to recover the physical
measures of a generic $C^{1}$ conservative diffeomorphism by looking at some
well-chosen invariant measures of the discretizations, as suggested by some
numerical experiments (see also [Gui15d]).

Despite this, Theorem A shows that when we iterate the discretizations of a
generic conservative diffeomorphism, we lose a great amount of information.
Moreover, although $f$ is conservative, its discretizations tend to behave
like dissipative maps. This can be compared with the work of P. Lax [Lax71]
(see also lemma 15 of [OU41]): for any conservative homeomorphism $f$, there
is a bijective finite map arbitrarily close to $f$. Theorem A states that for
a generic conservative $C^{r}$ diffeomorphism, the discretizations never
possess this property.

But the main interest of Theorem A may lie in the techniques used to prove it:
we will link the global and local behaviours of the discretizations, thus
reduce the proof to that of a linear statement.

Firstly, as it can be obtained as the decreasing limit of finite time
quantities, the degree of recurrence is maybe the easiest combinatorial
invariant to study: we will deduce its behaviour from that of the rate of
injectivity.

######  Definition 5.

Let $n\geq 1$, $f:\mathbf{T}^{n}\to\mathbf{T}^{n}$ an endomorphism of the
torus and $t\in\mathbf{N}$. The _rate of injectivity_ in time $t$ and for the
order $N$ is the quantity

$\tau^{t}(f_{N})=\frac{\operatorname{Card}\big{(}(f_{N})^{t}(E_{N})\big{)}}{\operatorname{Card}(E_{N})}.$

Then, the _upper rate of injectivity_ of $f$ in time $t$ is defined as

$\tau^{t}(f)=\limsup_{N\to+\infty}\tau^{t}(f_{N}),$ (1)

and the _asymptotic rate of injectivity_ of $f$ is

$\tau^{\infty}(f)=\lim_{t\to+\infty}\tau^{t}(f)$

(as the sequence $(\tau^{t}(f))_{t}$ is decreasing, the limit is well
defined).

The link between the degree of recurrence and the rates of injectivity is made
by the trivial formula:

$D(f_{N})=\lim_{t\to+\infty}\tau^{t}(f_{N}).$

Furthermore, when $N$ is fixed, the sequence $(\tau^{t}(f_{N}))_{t}$ is
decreasing in $t$, so $D(f_{N})\leq\tau^{t}(f_{N})$ for every
$t\in\mathbf{N}$. Taking the upper limit in $N$, we get

$\limsup_{N\to+\infty}D(f_{N})\leq\tau^{t}(f)$

for every $t\in\mathbf{N}$, so considering the limit $t\to+\infty$, we get

$\limsup_{N\to+\infty}D(f_{N})\leq\lim_{t\to+\infty}\tau^{t}(f)=\tau^{\infty}(f).$
(2)

In particular, if we have an upper bound on $\tau^{\infty}(f)$, this will give
a bound on $\limsup_{N\to+\infty}D(f_{N})$. This reduces the proof of Theorem
A to the study of the asymptotic rate of injectivity $\tau^{\infty}(f)$.

For generic dissipative $C^{1}$-diffeomorphisms, the fact that the sequence
$(D(f_{N}))_{N}$ converges to 0 (Theorem A) is an easy consequence of Equation
(2) and of a theorem of A. Avila and J. Bochi (Theorem 40, see also [AB06]).

For conservative diffeomorphisms and expanding maps, the study of the rates of
injectivity will be the opportunity to understand the local behaviour of the
discretizations: we will “linearize” the problem and reduce it to a statement
about generic sequences of linear maps.

Let us first define the corresponding quantities for linear maps: as in
general a linear map does not send $\mathbf{Z}^{n}$ into $\mathbf{Z}^{n}$, we
will approach it by a discretization. For any $A\in GL_{n}(\mathbf{R})$ and
any $x\in\mathbf{Z}^{n}$, $\widehat{A}(x)$ is defined as the point of
$\mathbf{Z}^{n}$ which is the closest from $A(x)$. Then, for any sequence
$(A_{k})_{k}$ of linear maps, the _rate of injectivity_
$\tau^{k}(A_{1},\cdots,A_{k})$ is defined as the density of the set
$(\widehat{A}_{k}\circ\cdots\circ\widehat{A}_{1})(\mathbf{Z}^{n})$ (see
Definition 7):

$\tau^{k}(A_{1},\cdots,A_{k})=\limsup_{R\to+\infty}\frac{\operatorname{Card}\big{(}(\widehat{A_{k}}\circ\cdots\circ\widehat{A_{1}})(\mathbf{Z}^{n})\cap
B(0,R)\big{)}}{\operatorname{Card}\big{(}\mathbf{Z}^{n}\cap
B(0,R)\big{)}}\in]0,1],$

and the _asymptotic rate of injectivity_ $\tau^{\infty}((A_{k})_{k})$ is the
limit of $\tau^{k}(A_{1},\cdots,A_{k})$ as $k$ tends to infinity. These
definitions are made to mimic the corresponding definitions for
diffeomorphisms. Then, the following statement asserts that that the rates of
injectivity of a generic map are obtained by averaging the corresponding
quantities for the differentials of the diffeomorphism, and thus makes the
link between local and global behaviours of the discretizations (Theorem 28).

######  Theorem B.

Let $r\in[1,+\infty]$, and $f\in\operatorname{Diff}^{r}(\mathbf{T}^{n})$ (or
$f\in\operatorname{Diff}^{r}(\mathbf{T}^{n},\operatorname{Leb})$) be a generic
diffeomorphism. Then $\tau^{k}(f)$ is well defined (that is, the limit
superior in (1) is a limit) and satisfies:

$\tau^{k}(f)=\int_{\mathbf{T}^{n}}\tau^{k}\left(Df_{x},\cdots,Df_{f^{k-1}(x)}\right)\,\operatorname{d}\operatorname{Leb}(x).$

The same kind of result holds for generic expanding maps (see Theorem 33).

For conservative diffeomorphisms, the core of the proof of Theorem A is the
study of the rate of injectivity of generic sequences of matrices with
determinant 1, that we will conduct in Section 2. Indeed, applying Theorem B
wich links the local and global behaviours of the diffeomorphism, together
with a transversality result (Lemma 37), we reduce the proof of Theorem A to
the main result of Section 2 (see Theorem 20 for the statement we actually
need to prove Theorem A).

######  Theorem C.

For a generic sequence of matrices $(A_{k})_{k\geq 1}$ of
$\ell^{\infty}(SL_{n}(\mathbf{R}))$, we have

$\tau^{\infty}\big{(}(A_{k})_{k\geq 1}\big{)}=0.$

This linear statement has also nice applications to image processing. For
example — the result remains true for a generic sequence of _isometries_ —, it
says that if we apply a naive algorithm, the quality of a numerical image will
be necessarily deteriorated by rotating this image many times by a generic
sequence of angles (see [Gui16]). Theorem C is also the central technical
result of [Gui15d], wich study the physical measures of discretizations of
generic conservative $C^{1}$-diffeomorphisms.

The proof of Theorem C (which is the most difficult and most original part of
the proof of Theorem A) uses the nice formalism of model sets, developed
initially for the study of quasicrystals. Using an equidistribution property,
this allows to get a geometric formula for the computation of the rate of
injectivity of a generic sequence of matrices (Proposition 9): the rate of
injectivity of a generic sequence $A_{1},\cdots,A_{k}$ of matrices of
$SL_{n}(\mathbf{R})$ can be expressed in terms of areas of intersections of
cubes in $\mathbf{R}^{nk}$. This formula, by averaging what happens in the
image sets $(\widehat{A}_{k}\circ\cdots\circ\widehat{A}_{1})(\mathbf{Z}^{n})$,
reflects the global behaviour of these sets. Also, it transforms the iteration
into a passage in high dimension. This allows to prove Theorem C, using
geometric considerations about the volume of intersections of cubes, without
having to make “clever” perturbations of the sequence of matrices (that is,
the perturbations made a each iteration are chosen independently from that
made in the past or in the future).

The end of this paper is devoted to the results of the simulations we have
conducted about the degree of recurrence of $C^{1}$-diffeomorphisms and
expanding maps; it shows that in practice, the degree of recurrence tends to
0, at least for the examples of diffeomorphisms we have tested.

Recall that we will see in Appendix A that the quite restrictive framework of
the torus $\mathbf{T}^{n}$ equipped with the uniform grids can be generalized
to arbitrary manifolds, provided that the discretizations grids behave locally
(and almost everywhere) like the canonical grids on the torus.

To finish, we state some questions related to Theorem A that remain open.

  * •

What is the behaviour of the degree of recurrence of discretizations of
generic $C^{r}$-expanding maps of the torus $\mathbf{T}^{n}$, for $n\geq 2$
and $r>1$? In the view of Theorem A, we can conjecture that this degree of
recurrence tends to 0. To prove it we would need a generalization of Lemma 46
to higher dimensions.

  * •

What is the behaviour of the degree of recurrence of discretizations of
generic dissipative $C^{r}$-diffeomorphisms of the torus $\mathbf{T}^{n}$ for
$r>1$? This question could reveal quite hard, as it may require some
perturbation results in the $C^{r}$ topology for $r>1$.

### Acknowledgments

Je tiens à remercier tous ceux qui m’ont aidé, de près ou de loin, pendant ces
recherches, et en particulier Yves Meyer, qui m’a fait découvrir les ensembles
modèle, ainsi que François Béguin, pour son soutien constant, ses innombrables
relectures et ses conseils éclairés.

##  2\. Discretizations of sequences of linear maps

We begin by the study of the linear case, corresponding to the “local
behaviour” of $C^{1}$ maps. We first define the linear counterpart of the
discretization.

######  Definition 6.

The map $P:\mathbf{R}\to\mathbf{Z}$ is defined as a projection from
$\mathbf{R}$ onto $\mathbf{Z}$. More precisely, for $x\in\mathbf{R}$, $P(x)$
is the unique666Remark that the choice of where the inequality is strict and
where it is not is arbitrary. integer $k\in\mathbf{Z}$ such that $k-1/2<x\leq
k+1/2$. This projection induces the map

$\begin{array}[]{rrcl}\pi:&\mathbf{R}^{n}&\longmapsto&\mathbf{Z}^{n}\\\
&(x_{i})_{1\leq i\leq n}&\longmapsto&\big{(}P(x_{i})\big{)}_{1\leq i\leq
n}\end{array}$

which is an Euclidean projection on the lattice $\mathbf{Z}^{n}$. For $A\in
M_{n}(\mathbf{R})$, we denote by $\widehat{A}$ the _discretization_ of $A$,
defined by

$\begin{array}[]{rrcl}\widehat{A}:&\mathbf{Z}^{n}&\longrightarrow&\mathbf{Z}^{n}\\\
&x&\longmapsto&\pi(Ax).\end{array}$

This definition allows us to define the rate of injectivity for sequences of
linear maps.

######  Definition 7.

Let $A_{1},\cdots,A_{k}\in GL_{n}(\mathbf{R})$. The _rate of injectivity_ of
$A_{1},\cdots,A_{k}$ is the quantity777By definition,
$B_{R}=B_{\infty}(0,R)$.888In the sequel we will see that the $\limsup$ is in
fact a limit for a generic sequence of matrices. It can also easily shown that
it is a limit in the general case.

$\tau^{k}(A_{1},\cdots,A_{k})=\limsup_{R\to+\infty}\frac{\operatorname{Card}\big{(}(\widehat{A_{k}}\circ\cdots\circ\widehat{A_{1}})(\mathbf{Z}^{n})\cap
B_{R})\big{)}}{\operatorname{Card}\big{(}\mathbf{Z}^{n}\cap
B_{R}\big{)}}\in]0,1],$

and for an infinite sequence $(A_{k})_{k\geq 1}$ of invertible matrices, as
the previous quantity is decreasing in $k$, we can define the _asymptotic rate
of injectivity_

$\tau^{\infty}\big{(}(A_{k})_{k\geq
1}\big{)}=\lim_{k\to+\infty}\tau^{k}(A_{1},\cdots,A_{k})\in[0,1].$

Figure 1. Successive images of $\mathbf{Z}^{2}$ by discretizations of random
matrices in $SL_{2}(\mathbf{R})$, a point is black if it belongs to
$(\widehat{A_{k}}\circ\cdots\circ\widehat{A_{1}})(\mathbf{Z}^{2})$. The
$A_{i}$ are chosen randomly, using the singular value decomposition: they are
chosen among the matrices of the form $R_{\theta}D_{t}R_{\theta^{\prime}}$,
with $R_{\theta}$ the rotation of angle $\theta$ and $D_{t}$ the diagonal
matrix $\operatorname{Diag}(e^{t},e^{-t})$, the $\theta$, $\theta^{\prime}$
being chosen uniformly in $[0,2\pi]$ and $t$ uniformly in $[-1/2,1/2]$. From
left to right and top to bottom, $k=1,\,3,\,20$.

For a typical example of the sets
$(\widehat{A_{k}}\circ\cdots\circ\widehat{A_{1}})(\mathbf{Z}^{2})$, see Figure
1. Finally, we define a topology on the set of sequences of linear maps.

######  Definition 8.

We fix once for all a norm $\|\cdot\|$ on $M_{n}(\mathbf{R})$. For a bounded
sequence $(A_{k})_{k\geq 1}$ of matrices of $SL_{n}(\mathbf{R})$, we set

$\|(A_{k})_{k}\|_{\infty}=\sup_{k\geq 1}\|A_{k}\|.$

In other words, we consider the space $\ell^{\infty}(SL_{n}(\mathbf{R}))$ of
uniformly bounded sequences of matrices of determinant 1 endowed with this
natural metric.

Let us explain the main steps of the proof of Theorem C.

We take advantage of the rational independence between the matrices of a
generic sequence to obtain geometric formulas for the computation of the rate
of injectivity. The tool used to do that is the formalism of _model sets_
999Also called _cut-and-project_ sets. (see for example [Moo00] or [Mey12] for
surveys about model sets, see also [Gui15c] for the application to the
specific case of discretizations of linear maps).

Let us summarize the different notations we will use throughout this section.
We will denote by $0^{k}$ the origin of the space $\mathbf{R}^{k}$, and
$W^{k}=]-1/2,1/2]^{nk}$ (unless otherwise stated). In this section, we will
denote $B_{R}=B_{\infty}(0,R)$ and $D_{c}(E)$ the density of a “continuous”
set $E\subset\mathbf{R}^{n}$, defined as (when the limit exists)

$D_{c}(E)=\lim_{R\to+\infty}\frac{\operatorname{Leb}(B_{R}\cap
E)}{\operatorname{Leb}(B_{R})},$

while for a discrete set $E\subset\mathbf{R}^{n}$, the notation $D_{d}(E)$
will indicate the discrete density of $E$, defined as (when the limit exists)

$D_{d}(E)=\lim_{R\to+\infty}\frac{\operatorname{Card}(B_{R}\cap
E)}{\operatorname{Card}(B_{R}\cap\mathbf{Z}^{n})},$

We will consider $(A_{k})_{k\geq 1}$ a sequence of matrices of
$SL_{n}(\mathbf{R})$, and denote

$\Gamma_{k}=(\widehat{A_{k}}\circ\dots\circ\widehat{A_{1}})(\mathbf{Z}^{n}).$

Also, $\Lambda_{k}$ will be the lattice
$M_{A_{1},\cdots,A_{k}}\mathbf{Z}^{n(k+1)}$, with

$M_{A_{1},\cdots,A_{k}}=\left(\begin{array}[]{ccccc}A_{1}&-\operatorname{Id}&&&\\\
&A_{2}&-\operatorname{Id}&&\\\ &&\ddots&\ddots&\\\
&&&A_{k}&-\operatorname{Id}\\\ &&&&\operatorname{Id}\end{array}\right)\in
M_{n(k+1)}(\mathbf{R}),$ (3)

and $\widetilde{\Lambda}_{k}$ will be the lattice
$\widetilde{M}_{A_{1},\cdots,A_{k}}\mathbf{Z}^{nk}$, with

$\widetilde{M}_{A_{1},\cdots,A_{k}}=\left(\begin{array}[]{ccccc}A_{1}&-\operatorname{Id}&&&\\\
&A_{2}&-\operatorname{Id}&&\\\ &&\ddots&\ddots&\\\
&&&A_{k-1}&-\operatorname{Id}\\\ &&&&A_{k}\end{array}\right)\in
M_{nk}(\mathbf{R}).$

Finally, we will denote

$\overline{\tau}^{k}(A_{1},\cdots,A_{k})=D_{c}\left(W^{k+1}+\Lambda_{k}\right)$
(4)

the _mean rate of injectivity in time $k$_ of $A_{1},\cdots,A_{k}$.

###  2.1. A geometric viewpoint to compute the rate of injectivity in
arbitrary times

We begin by motivating the introduction of model sets by giving an alternative
construction of the image sets
$(\widehat{A_{k}}\circ\dots\circ\widehat{A_{1}})(\mathbf{Z}^{n})$ using this
formalism.

Let $A_{1},\cdots,A_{k}\in GL_{n}(\mathbf{R})$, then

$\displaystyle\Gamma_{k}$
$\displaystyle=(\widehat{A_{k}}\circ\dots\circ\widehat{A_{1}})(\mathbf{Z}^{n})$
$\displaystyle=\big{\\{}p_{2}(\lambda)\mid\lambda_{k}\in\Lambda_{k},\,p_{1}(\lambda)\in
W^{k}\big{\\}}$
$\displaystyle=p_{2}\Big{(}\Lambda_{k}\cap\big{(}p_{1}^{-1}(W^{k})\big{)}\Big{)},$
(5)

with $p_{1}$ the projection on the $nk$ first coordinates and $p_{2}$ the
projection on the $n$ last coordinates. This allows us to see the set
$\Gamma_{k}$ as a model set.

Here, we suppose that the set $p_{1}(\Lambda_{k})$ is dense (thus,
equidistributed) in the image set $\operatorname{im}p_{1}$ (note that this
condition is generic among the sequences of invertible linear maps). In
particular, the set $\\{p_{2}(\lambda)\mid\lambda\in\Lambda_{k}\\}$ is
equidistributed in the window $W^{k}$.

$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$$\bullet$
Figure 2. Geometric construction to compute the rate of injectivity: the green
points are the elements of $\Lambda$, the blue parallelogram is a fundamental
domain of $\Lambda$ and the grey squares are centred on the points of
$\Lambda$ and have radii $1/2$. The rate of injectivity is equal to the area
of the intersection between the union of the grey squares and the blue
parallelogram.

The following property makes the link between the density of $\Gamma_{k}$ —
that is, the rate of injectivity of $A_{1},\cdots,A_{k}$ — and the density of
the union of unit cubes centred on the points of the lattice $\Lambda_{k}$
(see Figure 2). This formula seems to be very specific to the model sets
defined by the matrix $M_{A_{1},\cdots,A_{k}}$ and the window $W^{k}$, it is
unlikely that it can be generalized to other model sets.

######  Proposition 9.

For a generic sequence of matrices $(A_{k})_{k}$ of $SL_{n}(\mathbf{R})$, we
have

$D_{d}(\Gamma_{k})=D_{c}\left(W^{k}+\widetilde{\Lambda}_{k}\right)=\overline{\tau}^{k}(A_{1},\cdots,A_{k}).$

######  Remark 10.

The density on the left of the equality is the density of a discrete set (that
is, with respect to counting measure), whereas the density on the right of the
equality is that of a continuous set (that is, with respect to Lebesgue
measure). The two notions coincide when we consider discrete sets as sums of
Dirac masses.

######  Corollary 11.

For a generic sequence of matrices, the rate of injectivity $\tau^{k}$ in time
$k$ coincides with the mean rate of injectivity $\overline{\tau}^{k}$, which
is continuous and piecewise polynomial of degree $\leq nk$ in the coefficients
of the matrix.

######  Remark 12.

The formula of Proposition 9 could be used to compute numerically the mean
rate of injectivity in time $k$ of a sequence of matrices: it is much faster
to compute the volume of a finite number of intersections of cubes (in fact, a
small number) than to compute the cardinalities of the images of a big set
$[-R,R]^{n}\cap\mathbf{Z}^{n}$.

###### Proof of Proposition 9.

We want to determine the density of $\Gamma_{k}$. By Equation (5), we have

$x\in\Gamma_{k}\iff x\in\mathbf{Z}^{n}\ \text{and}\
\exists\lambda\in\Lambda_{k}:x=p_{2}(\lambda),\,p_{1}(\lambda)\in W^{k}.$

But if $x=p_{2}(\lambda)$, then we can write
$\lambda=(\widetilde{\lambda},0^{n})+(0^{(k-1)n},-x,x)$ with
$\widetilde{\lambda}\in\widetilde{\Lambda}_{k}$. Thus,

$\displaystyle x\in\Gamma_{k}$ $\displaystyle\iff x\in\mathbf{Z}^{n}\
\text{and}\
\exists\widetilde{\lambda}\in\widetilde{\Lambda}_{k}:(0^{(k-1)n},-x)-\widetilde{\lambda}\in
W^{k}$ $\displaystyle\iff x\in\mathbf{Z}^{n}\ \text{and}\
(0^{(k-1)n},x)\in\bigcup_{\widetilde{\lambda}\in\widetilde{\Lambda}_{k}}\widetilde{\lambda}-W^{k}.$

Thus, $x\in\Gamma_{k}$ if and only if the projection of $(0^{(k-1)n},x)$ on
$\mathbf{R}^{nk}/\widetilde{\Lambda}_{k}$ belongs to
$\widetilde{\Lambda}_{k}-W^{k}$. Then, the proposition follows directly from
the fact that the points of the form $(0^{(k-1)n},x)$, with
$x\in\mathbf{Z}^{n}$, are equidistributed in
$\mathbf{R}^{nk}/\widetilde{\Lambda}_{k}$.

To prove this equidistribution, we compute the inverse matrix of
$\widetilde{M}_{A_{1},\cdots,A_{k}}$:

${\widetilde{M}_{A_{1},\cdots,A_{k}}}^{-1}=\begin{pmatrix}A_{1}^{-1}&A_{1}^{-1}A_{2}^{-1}&A_{1}^{-1}A_{2}^{-1}A_{3}^{-1}&\cdots&A_{1}^{-1}\cdots
A_{k}^{-1}\\\ &A_{2}^{-1}&A_{2}^{-1}A_{3}^{-1}&\cdots&A_{2}^{-1}\cdots
A_{k}^{-1}\\\ &&\ddots&\ddots&\vdots\\\
&&&A_{k-1}^{-1}&A_{k-1}^{-1}A_{k}^{-1}\\\ &&&&A_{k}^{-1}\end{pmatrix}.$

Thus, the set of points of the form $(0^{(k-1)n},x)$ in
$\mathbf{R}^{nk}/\widetilde{\Lambda}_{k}$ corresponds to the image of the
action

$\mathbf{Z}^{n}\ni x\longmapsto\begin{pmatrix}A_{1}^{-1}\cdots A_{k}^{-1}\\\
A_{2}^{-1}\cdots A_{k}^{-1}\\\ \vdots\\\ A_{k-1}^{-1}A_{k}^{-1}\\\
A_{k}^{-1}\end{pmatrix}x$

of $\mathbf{Z}^{n}$ on the canonical torus $\mathbf{R}^{nk}/\mathbf{Z}^{nk}$.
But this action is ergodic (even in restriction to the first coordinate) when
the sequence of matrices is generic. ∎

Recall the problem raised by Theorem C: we want to make $\tau^{k}$ tend to 0
as $k$ tends to infinity. By an argument of equidistribution stated by
Proposition 9, generically, it is equivalent to make the mean rate of
injectivity $\overline{\tau}^{k}$ tend to 0 when $k$ goes to infinity, by
perturbing every matrix in $SL_{n}(\mathbf{R})$ of at most $\delta>0$ (fixed
once for all). The conclusion of Theorem C is motivated by the phenomenon of
concentration of the measure on a neighbourhood of the boundary of the cubes
in high dimension.

######  Proposition 13.

Let $W^{k}$ be the infinite ball of radius $1/2$ in $\mathbf{R}^{k}$ and
$v^{k}$ the vector $(1,\cdots,1)\in\mathbf{R}^{k}$. Then, for every
$\varepsilon,\delta>0$, there exists $k_{0}\in\mathbf{N}^{*}$ such that for
every $k\geq k_{0}$, we have $\operatorname{Leb}\big{(}W^{k}\cap(W^{k}+\delta
v^{k})\big{)}<\varepsilon$.

The case of equality $\overline{\tau}^{k}=1$ is given by Hajós theorem.

######  Theorem 14 (Hajós, [Haj41]).

Let $\Lambda$ be a lattice of $\mathbf{R}^{n}$. Then the collection of squares
$\\{B_{\infty}(\lambda,1/2)\\}_{\lambda\in\Lambda}$ tiles $\mathbf{R}^{n}$ if
and only if in a canonical basis of $\mathbf{R}^{n}$ (that is, permuting
coordinates if necessary), $\Lambda$ admits a generating matrix which is upper
triangular with ones on the diagonal.

######  Remark 15.

The kind of questions addressed by Hajós theorem are in general quite
delicate. For example, we can wonder what happens if we do not suppose that
the centres of the cubes form a lattice of $\mathbf{R}^{n}$. O. H. Keller
conjectured in [Kel30] that the conclusion of Hajós theorem is still true
under this weaker hypothesis. This conjecture was proven to be true for $n\leq
6$ by O. Perron in [Per40a, Per40b], but remained open in higher dimension
until 1992, when J. C. Lagarias and P. W. Shor proved in [LS92] that Keller’s
conjecture is false for $n\geq 10$ (this result was later improved by [Mac02]
which shows that it is false as soon as $n\geq 8$; the case $n=7$ is to our
knowledge still open).

Combining Hajós theorem with Proposition 9, we obtain that the equality
$\overline{\tau}^{k}=1$ occurs if and only if the lattice given by the matrix
$M_{A_{1},\cdots,A_{k}}$ satisfies the conclusions of Hajós theorem101010Of
course, this property can be obtained directly by saying that the density is
equal to 1 if and only if the rate of injectivity of every matrix of the
sequence is equal to 1.. The heuristic suggested by the phenomenon of
concentration of the measure is that if we perturb “randomly” any sequence of
matrices, we will go “far away” from the lattices satisfying Hajós theorem and
then the rate of injectivity will be close to 0.

###  2.2. A first step: proof that the asymptotic rate of injectivity is
generically smaller than $1/2$

As a first step, we prove that rate of injectivity of a generic sequence of
$\ell^{\infty}(SL_{n}(\mathbf{R}))$ is smaller than $1/2$.

######  Proposition 16.

Let $(A_{k})_{k\geq 1}$ be a generic sequence of matrices of
$SL_{n}(\mathbf{R})$. Then there exists a parameter $\lambda\in]0,1[$ such
that for every $k\geq 1$, we have
$\tau^{k}(A_{1},\cdots,A_{k})\leq(\lambda^{k}+1)/2$. In particular,
$\tau^{\infty}((A_{k})_{k})\leq 1/2$.

To begin with, we give a lemma estimating the sizes of intersections of cubes
when the mean rate of injectivity $\overline{\tau}^{k}$ is bigger than $1/2$.

######  Lemma 17.

Let $W^{k}=]-1/2,1/2]^{k}$ and $\Lambda\subset\mathbf{R}^{k}$ be a lattice
with covolume 1 such that $D_{c}(W^{k}+\Lambda)\geq 1/2$. Then, for every
$v\in\mathbf{R}^{k}$, we have

$D_{c}\big{(}(W^{k}+\Lambda+v)\cap(W^{k}+\Lambda)\big{)}\geq
2D_{c}(W^{k}+\Lambda)-1.$

###### Proof of Lemma 17.

We first remark that $D_{c}(\Lambda+W^{k})$ is equal to the volume of the
projection of $W^{k}$ on the quotient space $\mathbf{R}^{k}/\Lambda$. For
every $v\in\mathbf{R}^{k}$, the projection of $W^{k}+v$ on
$\mathbf{R}^{k}/\Lambda$ has the same volume; as this volume is greater than
$1/2$, and as the covolume of $\Lambda$ is 1, the projections of $W^{k}$ and
$W^{k}+v$ overlap, and the volume of the intersection is bigger than
$2D_{c}(W^{k}+\Lambda)-1$. Returning to the whole space $\mathbf{R}^{k}$, we
get the conclusion of the lemma. ∎

A simple counting argument leads to the proof of the following lemma.

######  Lemma 18.

Let $\Lambda_{1}$ be a subgroup of $\mathbf{R}^{m}$, $\Lambda_{2}$ be such
that $\Lambda_{1}\oplus\Lambda_{2}$ is a lattice of covolume 1 of
$\mathbf{R}^{m}$, and $C$ be a compact subset of $\mathbf{R}^{m}$. Let $C_{1}$
be the projection of $C$ on the quotient $\mathbf{R}^{m}/\Lambda_{1}$, and
$C_{2}$ the projection of $C$ on the quotient
$\mathbf{R}^{m}/(\Lambda_{1}\oplus\Lambda_{2})$. We denote by

$a_{i}=\operatorname{Leb}\big{\\{}x\in
C_{1}\mid\operatorname{Card}\\{\lambda_{2}\in\Lambda_{2}\mid x\in
C_{1}+\lambda_{2}\\}=i\big{\\}}$

(in particular, $\sum_{i\geq 1}a_{i}=\operatorname{Leb}(C_{1})$). Then,

$\operatorname{Leb}(C_{2})=\sum_{i\geq 1}\frac{a_{i}}{i}.$

In particular, the area of $C_{2}$ (the projection on the quotient by
$\Lambda_{1}\oplus\Lambda_{2}$) is smaller than (or equal to) that of $C_{1}$
(the projection on the quotient by $\Lambda_{1}$). The loss of area is given
by the following corollary.

######  Corollary 19.

With the same notations as for Lemma 18, if we denote by

$D_{1}=\operatorname{Leb}\big{\\{}x\in
C_{1}\mid\operatorname{Card}\\{\lambda_{2}\in\Lambda_{2}\mid x\in
C_{1}+\lambda_{2}\\}\geq 2\big{\\}},$

then,

$\operatorname{Leb}(C_{2})\leq\operatorname{Leb}(C_{1})-\frac{D_{1}}{2}.$

###### Proof of Proposition 16.

Let $(A_{k})_{k\geq 1}$ be a bounded sequence of matrices of
$SL_{n}(\mathbf{R})$ and $\delta>0$. We proceed by induction on $k$ and
suppose that the proposition is proved for a rank $k\in\mathbf{N}^{*}$. Let
$\widetilde{\Lambda}_{k}$ be the lattice spanned by the matrix
$\widetilde{M}_{B_{1},\cdots,B_{k}}$ and $W^{k}=]-1/2,1/2]^{nk}$ be the window
corresponding to the model set $\Gamma_{k}$ modelled on $\Lambda_{k}$ (the
lattice spanned by the matrix $M_{B_{1},\cdots,B_{k}}$, see Equation (3)). By
Proposition 9, if the sequence $(A_{k})_{k}$ is generic, then we have

$\tau^{k}(B_{1},\cdots,B_{k})=D_{c}\left(W^{k}+\widetilde{\Lambda}_{k}\right).$

We now choose a matrix $B_{k+1}$ satisfying $\|A_{k+1}-B_{k+1}\|\leq\delta$,
such that there exists $x_{1}\in\mathbf{Z}^{n}\setminus\\{0\\}$ such that
$\|B_{k+1}x_{1}\|_{\infty}\leq 1-\varepsilon$, with $\varepsilon>0$ depending
only on $\delta$ and $\|(A_{k})_{k}\|$ (and $n$): indeed, for every matrix
$B\in SL_{n}(\mathbf{R})$, Minkowski theorem implies that there exists
$x_{1}\in\mathbf{Z}^{n}\setminus\\{0\\}$ such that $\|Bx_{1}\|_{\infty}\leq
1$; it then suffices to modify slightly $B$ to decrease $\|Bx_{1}\|_{\infty}$.
We can also suppose that the sequence of matrices $B_{1},\cdots,B_{k+1}$ is
generic. Again, Proposition 9 reduces the calculation of the rate on
injectivity $\tau^{k+1}(B_{1},\cdots,B_{k+1})$ to that of the density of
$W^{k+1}+\widetilde{\Lambda}_{k+1}$. By the form of the matrix
$\widetilde{M}_{B_{1},\cdots,B_{k}}$, this set can be decomposed into

$W^{k+1}+\widetilde{\Lambda}_{k+1}=W^{k+1}+\begin{pmatrix}\widetilde{\Lambda}_{k}\\\
0^{n}\end{pmatrix}+\begin{pmatrix}0^{n(k-1)}\\\ -\operatorname{Id}\\\
B_{k+1}\end{pmatrix}\mathbf{Z}^{n}.$

In particular, as $|\det(B_{k+1})|=1$, this easily implies that
$D_{c}\left(W^{k+1}+\widetilde{\Lambda}_{k+1}\right)\leq
D_{c}\left(W^{k}+\widetilde{\Lambda}_{k}\right)$.

_How to read these figures :_ The top of the figure represents the set
$W^{k}+\widetilde{\Lambda}_{k}$ by the 1-dimensional set
$[-1/2,1/2]+\nu\mathbf{Z}$ (in dark blue), for a number $\nu>1$. The bottom of
the figure represents the set $W^{k+1}+\widetilde{\Lambda}_{k+1}$ by the set
$[-1/2,1/2]^{2}+\Lambda$, where $\Lambda$ is the lattice spanned by the
vectors $(0,\nu)$ and $(1,1-\varepsilon)$ for a parameter $\varepsilon>0$
close to 0. The dark blue cubes represent the “old” cubes, that is, the
thickening in dimension 2 of the set $W^{k}+\widetilde{\Lambda}_{k}$, and the
light blue cubes represent the “added” cubes, that is, the rest of the set
$W^{k+1}+\widetilde{\Lambda}_{k+1}$.

Figure 3. In the case where the rate is bigger than $1/2$, some intersections
of cubes appear automatically between times $k$ and $k+1$.

Figure 4. In the case where the rate is smaller than $1/2$, there is not
necessarily new intersections between times $k$ and $k+1$.

What we need is a more precise bound. We apply Corollary 19 to

$\Lambda_{1}=\big{(}\widetilde{\Lambda}_{k},0^{n}\big{)},\qquad\Lambda_{2}=\begin{pmatrix}0^{n(k-1)}\\\
-\operatorname{Id}\\\ B_{k+1}\end{pmatrix}\mathbf{Z}^{n}\qquad\text{and}\qquad
C=W^{k+1}.$

Then, the decreasing of the rate of injectivity between times $k$ and $k+1$ is
bigger than the $D_{1}$ defined in Corollary 19: using Lemma 17, we have

$D_{c}\left(\Big{(}W^{k}+\widetilde{\Lambda}_{k}\Big{)}\cap\Big{(}W^{k}+\widetilde{\Lambda}_{k}+\big{(}0^{n(k-1)},-x_{1}\big{)}\Big{)}\right)\geq
2D_{d}(\Gamma_{k})-1;$

thus, as $\|x_{1}\|_{\infty}<1-\varepsilon$ (see Figure 4),

$D_{1}\geq\varepsilon^{n}\big{(}2D_{d}(\Gamma_{k})-1\big{)}.$

From Corollary 19 we deduce that

$\displaystyle D_{d}(\Gamma_{k+1})$
$\displaystyle=D_{c}\left(W^{k+1}+\widetilde{\Lambda}_{k+1}\right)$
$\displaystyle\leq
D_{c}\left(W^{k}+\widetilde{\Lambda}_{k}\right)-\frac{1}{2}D_{1}$
$\displaystyle\leq
D_{d}(\Gamma_{k})-\frac{1}{2}\varepsilon^{n}\big{(}2D_{d}(\Gamma_{k})-1\big{)}.$

This proves the theorem for the rank $k+1$. ∎

###  2.3. Proof of Theorem C: generically, the asymptotic rate is zero

We now come to the proof of Theorem C. The strategy of proof is identical to
that we used in the previous section to state that generically, the asymptotic
rate is smaller than $1/2$ (Proposition 16): we will use an induction to
decrease the rate step by step. Recall that
$\overline{\tau}^{k}(A_{1},\cdots,A_{k})$ indicates the density of the set
$W^{k+1}+\widetilde{\Lambda}_{k}$.

Unfortunately, if the density of $W^{k}+\widetilde{\Lambda}_{k}$ — which is
generically equal to the density of the $k$-th image
$\big{(}\widehat{A}_{k}\circ\cdots\circ\widehat{A}_{1}\big{)}(\mathbf{Z}^{n})$
— is smaller than $1/2$, then we can not apply exactly the strategy of proof
of the previous section (see Figure 4). For example, if we take

$A_{1}=\operatorname{diag}(100,1/100)\quad\text{and}\quad
A_{2}=\operatorname{diag}(1/10,10),$

then
$\big{(}\widehat{A_{2}}\circ\widehat{A_{1}}\big{)}(\mathbf{Z}^{2})=(2\mathbf{Z})^{2}$,
and for every $B_{3}$ close to the identity, we have
$\tau^{3}(A_{1},A_{2},B_{3})=\tau^{2}(A_{1},A_{2})=1/100$. This example tells
us that there exists an open set of $\ell^{\infty}(SL_{n}(\mathbf{R}))$ on
which the sequence $\tau^{k}$ is not strictly decreasing.

Moreover, if we set $A_{k}=\operatorname{Id}$ for every $k\geq 2$, then we can
set $B_{1}=A_{1}$, $B_{2}=A_{2}$ and for each $k\geq 2$ perturb each matrix
$A_{k}$ into the matrix $B_{k}=\operatorname{diag}(1+\delta,1/(1+\delta))$,
with $\delta>0$ small. In this case, there exists a time $k_{0}$ (minimal)
such that $\tau^{k_{0}}(B_{1},\cdots,B_{k_{0}})<1/100$. But if instead of
$A_{k_{0}}=\operatorname{Id}$, we have $A_{k_{0}}=\operatorname{diag}(1/5,5)$,
this construction does not work anymore: we should have set
$B_{k}=\operatorname{diag}(1/(1+\delta),1+\delta)$. This suggests that we
should take into account the next terms of the sequence $(A_{k})_{k}$ to
perform the perturbations. And things seems even more complicated when the
matrices are no longer diagonal…

To overcome this difficulty, we use the same strategy of proof than in the
case where $\overline{\tau}\geq 1/2$, provided that we wait for long enough
time: for a generic sequence $(A_{k})_{k\geq 1}$, if
$\overline{\tau}^{k}(A_{1},\cdots,A_{k})>1/\ell$, then
$\overline{\tau}^{k+\ell-1}(A_{1},\cdots,A_{k+\ell-1})$ is strictly smaller
than $\overline{\tau}^{k}(A_{1},\cdots,A_{k})$. More precisely, we consider
the maximal number of disjoint translates of $W^{k}+\widetilde{\Lambda}_{k}$
in $\mathbf{R}^{nk}$: we easily see that if the density of
$W^{k}+\widetilde{\Lambda}_{k}$ is bigger than $1/\ell$, then there can not be
more than $\ell$ disjoint translates of $W^{k}+\widetilde{\Lambda}_{k}$ in
$\mathbf{R}^{nk}$(Lemma 24). At this point, Lemma 25 states that if the
sequence of matrices is generic, then either the density of
$W^{k+1}+\widetilde{\Lambda}_{k+1}$ is smaller than that of
$W^{k}+\widetilde{\Lambda}_{k}$ (Figure 6), or there can not be more than
$\ell-1$ disjoint translates of $W^{k+1}+\widetilde{\Lambda}_{k+1}$ in
$\mathbf{R}^{n(k+1)}$(see Figure 6). Applying this reasoning (at most)
$\ell-1$ times, we obtain that the density of
$W^{k+\ell-1}+\widetilde{\Lambda}_{k+\ell-1}$ is smaller than that of
$W^{k}+\widetilde{\Lambda}_{k}$. For example if
$D_{c}\big{(}W^{k}+\widetilde{\Lambda}_{k}\big{)}>1/3$, then
$D_{c}\big{(}W^{k+2}+\widetilde{\Lambda}_{k+2}\big{)}<D\big{(}W^{k}+\widetilde{\Lambda}_{k}\big{)}$
(see Figure 7). To apply this strategy in practice, we have to obtain
quantitative estimates about the loss of density we get between times $k$ and
$k+\ell-1$.

Remark that with this strategy we do not need to make “clever” perturbations
of the matrices: provided that the coefficients of the matrices are rationally
independent, the perturbation of each matrix is made independently from that
of the others. However, this reasoning does not tell when exactly the rate of
injectivity decreases (likely, in most of cases, the speed of decreasing of
the rate of injectivity is much faster than the one obtained by this method),
and does not say either where exactly the loss of injectivity occurs in the
image sets.

We will indeed prove a more precise statement of Theorem C.

######  Theorem 20.

For a generic sequence of matrices $(A_{k})_{k\geq 1}$ of
$\ell^{\infty}(SL_{n}(\mathbf{R}))$, for every $\ell\in\mathbf{N}$, there
exists $\lambda_{\ell}\in]0,1[$ such that for every $k\in\mathbf{N}$,

$\tau^{\ell k}(A_{1},\cdots,A_{\ell k})\leq\lambda_{\ell}^{k}+\frac{1}{\ell}.$
(6)

Thus, for every $\nu<1$, we have

$\tau^{k}(A_{1},\cdots,A_{k})=o\big{(}\ln(k)^{-\nu}\big{)}.$ (7)

In particular, $\tau^{\infty}\big{(}(A_{k})_{k\geq 1}\big{)}=0$, and for every
$\varepsilon>0$, the set of $(A_{k})_{k\geq
1}\in\ell^{\infty}(SL_{n}(\mathbf{R}))$ such that
$\tau^{\infty}\big{(}(A_{k})_{k\geq 1}\big{)}<\varepsilon$ is open and dense.

Moreover, there exists a locally finite number of positive codimension
submanifolds $V_{q}$ of $SL_{n}(\mathbf{R})$ such that for any $\varepsilon>0$
and for any $\delta>0$, if $(A_{k})_{k\geq
1}\in\ell^{\infty}(SL_{n}(\mathbf{R}))$ is such that
$d\big{(}A_{k},\bigcup_{q}V_{q}\big{)}>\delta$ for a positive asymptotic
density of integers $k$, then $\tau^{\infty}\big{(}(A_{k})_{k\geq
1}\big{)}\leq\varepsilon$.

######  Remark 21.

The existence of open and dense sets of sequences on which $\tau^{\infty}$ is
smaller than $\varepsilon$ is easily deduced from the first part of the
theorem by applying the continuity of $\tau^{k}$ on a generic subset
(Corollary 11).

######  Remark 22.

We can easily prove that the intersection of the submanifold $V_{q}$ with
$O_{n}(\mathbf{R})$ is again a positive codimension submanifold of
$O_{n}(\mathbf{R})$. From this fact we deduce the fact announced in the
introduction that Theorem 20 remains true for generic sequences of isometries
(see also [Gui16] for an alternative proof).

From the second part of this theorem one easily deduce the following
consequence for sequence of random iid matrices.

######  Corollary 23.

Let $\mu$ be a measure on $SL_{n}(\mathbf{R})$ with nonempty interior support.
Then, for almost every sequence $(A_{k})_{k\geq 1}$ of independent identically
distributed matrices with distribution $\mu$, we have
$\tau^{\infty}\big{(}(A_{k})_{k\geq 1}\big{)}=0$.

We now come to the proof of Theorem 20. The following lemma is a
generalization of Lemma 17. It expresses that if the density of
$W^{k}+\widetilde{\Lambda}_{k}$ is bigger than $1/\ell$, then there can not be
more than $\ell$ disjoint translates of $W^{k}+\widetilde{\Lambda}_{k}$, and
gives an estimation on the size of these intersections.

######  Lemma 24.

Let $W^{k}=]-1/2,1/2]^{k}$ and $\Lambda\subset\mathbf{R}^{k}$ be a lattice
with covolume 1 such that $D_{c}(W^{k}+\Lambda)\geq 1/\ell$. Then, for every
collection $v_{1},\cdots,v_{\ell}\in\mathbf{R}^{k}$, there exists $i\neq
i^{\prime}\in\llbracket 1,\ell\rrbracket$ such that

$D_{c}\big{(}(W^{k}+\Lambda+v_{i})\cap(W^{k}+\Lambda+v_{i^{\prime}})\big{)}\geq
2\frac{\ell D_{c}(W^{k}+\Lambda)-1}{\ell(\ell-1)}.$

###### Proof of Lemma 24.

For every $v\in\mathbf{R}^{k}$, the density $D_{c}(W^{k}+\Lambda+v)$ is equal
to the volume of the projection of $W^{k}$ on the quotient space
$\mathbf{R}^{k}/\Lambda$. As this volume is greater than $1/\ell$, and as the
covolume of $\Lambda$ is 1, the projections of the $W^{k}+v_{i}$ overlap, and
the volume of the points belonging to at least two different sets is bigger
than $\ell D_{c}(W^{k}+\Lambda)-1$. As there are $\ell(\ell-1)/2$
possibilities of intersection, there exists $i\neq i^{\prime}$ such that the
volume of the intersection between the projections of $W^{k}+v_{i}$ and
$W^{k}+v_{i^{\prime}}$ is bigger than $2(\ell
D_{c}(W^{k}+\Lambda)-1)/(\ell(\ell-1))$. Returning to the whole space
$\mathbf{R}^{k}$, we get the conclusion of the lemma. ∎

Recall that we denote $\widetilde{\Lambda}_{k}$ the lattice spanned by the
matrix

$\widetilde{M}_{A_{1},\cdots,A_{k}}=\left(\begin{array}[]{ccccc}A_{1}&-\operatorname{Id}&&&\\\
&A_{2}&-\operatorname{Id}&&\\\ &&\ddots&\ddots&\\\
&&&A_{k-1}&-\operatorname{Id}\\\ &&&&A_{k}\end{array}\right)\in
M_{nk}(\mathbf{R}),$

and $W^{k}$ the cube $]-1/2,1/2]^{nk}$. The proof of Theorem 20 will reduce to
the following technical lemma.

######  Lemma 25.

There exists a locally finite collection $(V_{q})_{q}$ of positive codimension
submanifolds of $SL_{n}(\mathbf{R})$ such that for every $\delta>0$, every
$M>0$ and every $\ell\geq 2$, there exists $\varepsilon>0$ satisfying: if
$D_{0}>0$ is such that for every collection of vectors
$v_{1},\cdots,v_{\ell}\in\mathbf{R}^{n}$, there exists $j\neq
j^{\prime}\in\llbracket 1,\ell\rrbracket$ such that

$D_{c}\bigg{(}\Big{(}W^{k}+\widetilde{\Lambda}_{k}+(0^{(k-1)n},v_{j})\Big{)}\cap\Big{(}W^{k}+\widetilde{\Lambda}_{k}+(0^{(k-1)n},v_{j^{\prime}})\Big{)}\bigg{)}\geq
D_{0},$

then for every matrix $B\in SL_{n}(\mathbf{R})$ of norm smaller than $M$ such
that $d(B,V_{q})>\delta$ for every $q$, if we denote by
$\widetilde{\Lambda}_{k+1}$ the lattice spanned by the matrix
$\widetilde{M}_{A_{1},\cdots,A_{k},B}$,

  1. (1)

either $D_{c}(W^{k+1}+\widetilde{\Lambda}_{k+1})\leq
D_{c}(W^{k}+\widetilde{\Lambda}_{k})-\varepsilon D_{0}$;

  2. (2)

or for every collection of vectors $w_{1},\cdots,w_{\ell-1}\in\mathbf{R}^{n}$,
there exists $i\neq i^{\prime}\in\llbracket 1,\ell-1\rrbracket$ such that

$D_{c}\bigg{(}\Big{(}W^{k+1}+\widetilde{\Lambda}_{k+1}+(0^{kn},w_{i})\Big{)}\cap\Big{(}W^{k+1}+\widetilde{\Lambda}_{k+1}+(0^{kn},w_{i^{\prime}})\Big{)}\bigg{)}\geq\varepsilon
D_{0}.$

######  Remark 26.

If $\ell=2$, then we have automatically the conclusion (1) of the lemma; that
easily implies Proposition 16.

Conclusion (1) says that the rate of injectivity decreases between times $k$
and $k+1$, and conclusion (2) expresses that the number of possible disjoint
translates of $W^{k}+\widetilde{\Lambda}_{k}$ decreases between times $k$ and
$k+1$. In a certain sense, conclusion (1) corresponds to an hyperbolic
behaviour, and conclusion (2) to a diffusion between times $k$ and $k+1$. The
same strategy of proof leads to the following variation of the lemma, which is
true without condition on the matrix $B$.

######  Lemma 27.

Fix $M>0$ and $\ell\geq 2$. Then there exists $\varepsilon>0$ such that if
$D_{0}>0$ is such that for every collection of vectors
$v_{1},\cdots,v_{\ell}\in\mathbf{R}^{n}$, there exists
$j,j^{\prime}\in\llbracket 1,\ell\rrbracket$ such that

$D_{c}\bigg{(}\Big{(}W^{k}+\widetilde{\Lambda}_{k}+(0^{(k-1)n},v_{j})\Big{)}\cap\Big{(}W^{k}+\widetilde{\Lambda}_{k}+(0^{(k-1)n},v_{j^{\prime}})\Big{)}\bigg{)}\geq
D_{0},$

then for every matrix $B\in SL_{n}(\mathbf{R})$ of norm smaller than $M$, if
we denote by $\widetilde{\Lambda}_{k+1}$ the lattice spanned by the matrix
$\widetilde{M}_{A_{1},\cdots,A_{k},B}$, then for every collection of vectors
$w_{1},\cdots,w_{\ell}\in\mathbf{R}^{n}$, there exists $i\neq
i^{\prime}\in\llbracket 1,\ell\rrbracket$ such that

$D_{c}\bigg{(}\Big{(}W^{k+1}+\widetilde{\Lambda}_{k+1}+(0^{kn},w_{i})\Big{)}\cap\Big{(}W^{k+1}+\widetilde{\Lambda}_{k+1}+(0^{kn},w_{i^{\prime}})\Big{)}\bigg{)}\geq\varepsilon
D_{0}.$

###### Proof of Lemma 25.

We begin by defining the sets $V_{q}$. A collection of cubes of
$\mathbf{R}^{n}$ is called a _$k$ -fold tiling_111111See also Furtwängler
conjecture [Fur36], proved false by G. Hajós. R. Robinson gave a
characterization of such $k$-fold tilings in some cases, see [Rob79] or [SS94,
p. 29]. if any point of $\mathbf{R}^{n}$ belongs to exactly $k$ different
cubes, except from those belonging to the boundary of one cube.

Fact: Take a matrix $B\in SL_{n}(\mathbf{R})$ and consider the collection
$(Bv+W^{1})_{v\in\mathbf{Z}^{n}}$ of translates of the unit cube by the
lattice spanned by $B$. Now, take $\ell-1$ vectors
$w_{1},\cdots,w_{\ell-1}\in\mathbf{R}^{n}$ and consider the collection

$(Bv+w_{i}+W^{1})_{v\in\mathbf{Z}^{n},\,1\leq i\leq\ell-1}$ (8)

of translates of the first collection by the vectors $w_{i}$. Then, the set of
matrices $B\in SL_{n}(\mathbf{R})$ of norm $\leq M$ such that the collection
(8) forms a $\ell-1$-fold tiling is contained in a finite union of positive
codimension submanifolds of $SL_{n}(\mathbf{R})$, which we denote by $V_{q}$.

$W_{0}$$W_{1}$$W_{2}$$W_{3}$$\times$$\times$$\times$$\times$$+$

Indeed, consider a matrix $B$ and $w_{1},\cdots,w_{\ell-1}\in\mathbf{R}^{n}$
such that the collection (8) forms a $\ell-1$-fold tiling. Translating the
whole family if necessary, one can suppose that $w_{1}=0$. Then, easy
geometrical arguments show that for every $i$, there exists a cube $W_{i}$ of
the collection (8) such that $(-1/2+i,0,0,\dots)\in\mathbf{R}^{n}$ belongs to
the left face of $W_{i}$ (with the convention $W_{0}=W^{1}$). By the
pigeonhole principle, two cubes belong to the same translated family of cubes:
there exists $i_{0}\in\llbracket 1,\ell-1\rrbracket$,
$v,v^{\prime}\in\mathbf{Z}^{n}$ and $i\neq j\in\llbracket 0,\ell-1\rrbracket$
such that $W_{i}=Bv+w_{i_{0}}+W^{1}$ and $W_{j}=Bv^{\prime}+w_{i_{0}}+W^{1}$.
But $W_{i}$ and $W_{j}$ differ of a translation of the form $(j-i,*,*,\dots)$,
thus the first coordinate of $B(v-v^{\prime})$ has to be an integer smaller
than $\ell$. In any bounded subset of $SL_{n}(\mathbf{R})$, this condition is
satisfied only on a finite union of positive codimension submanifolds.

Let $\mathcal{O}_{\varepsilon}$ be the set of the matrices $B\in
SL_{n}(\mathbf{R})$ satisfying: for any
$w_{1},\cdots,w_{\ell-1}\in\mathbf{R}^{n}$, there exists a set
$U\subset\mathbf{R}^{n}/B\mathbf{Z}^{n}$ of measure $>\varepsilon$ such that
every point of $U$ belongs to at least $\ell$ different cubes of the
collection (8). In other words, every $x\in\mathbf{R}^{n}$ whose projection
$\overline{x}$ on $\mathbf{R}^{n}/B\mathbf{Z}^{n}$ belongs to $U$ satisfies

$\sum_{i=1}^{\ell-1}\sum_{v\in\mathbf{Z}^{n}}\mathbf{1}_{x\in
Bv+w_{i}+W^{1}}\geq\ell.$ (9)

By definition, the (monotonic) union of $\mathcal{O}_{\varepsilon}$ over
$\varepsilon>0$ is the complementary of the union of the submanifolds $V_{q}$.
Thus, if we are given $\delta>0$, $\ell\in\mathbf{N}$ and $M>0$, there exists
$\varepsilon>0$ such that $\mathcal{O}=\mathcal{O}_{\varepsilon}$ is contained
in the complementary of the union over $q$ of the $\delta$-neighbourhoods of
$V_{q}$.

We then choose $B\in\mathcal{O}$ and a collection of vectors
$w_{1},\cdots,w_{\ell-1}\in\mathbf{R}^{n}$. Let $x\in\mathbf{R}^{n}$ be such
that $\overline{x}\in U$. By hypothesis on the matrix $B$, $x$ satisfies
Equation (9), so there exists $\ell+1$ integer vectors $v_{1},\cdots,v_{\ell}$
and $\ell$ indices $i_{1},\cdots,i_{\ell}$ such that the couples
$(v_{j},i_{j})$ are pairwise distinct and that

$\forall j\in\llbracket 1,\ell\rrbracket,\quad x\in Bv_{j}+w_{i_{j}}+W^{1}.$
(10)

$x$$y$ Figure 5. First case of Lemma 25, in the case $\ell=3$: the set
$W^{k+1}+\widetilde{\Lambda}_{k+1}$ auto-intersects.

$x$$y$ Figure 6. Second case of Lemma 25, in the case $\ell=3$: two distinct
vertical translates of $W^{k+1}+\widetilde{\Lambda}_{k+1}$ intersect (the
first translate contains the dark blue thickening of
$W^{k}+\widetilde{\Lambda}_{k}$, the second is represented in grey).

The following formula makes the link between what happens in the $n$ last and
in the $n$ penultimates coordinates of $\mathbf{R}^{n(k+1)}$:

$W^{k+1}+\widetilde{\Lambda}_{k+1}+\big{(}0^{(k-1)n},0^{n},w_{i_{j}}\big{)}=W^{k+1}+\widetilde{\Lambda}_{k+1}+\big{(}0^{(k-1)n},-v_{j},w_{i_{j}}+Bv_{j}\big{)},$
(11)

(we add a vector belonging to $\widetilde{\Lambda}_{k+1}$).

We now apply the hypothesis of the lemma to the vectors
$-v_{1},\cdots,-v_{\ell+1}$: there exists $j\neq j^{\prime}\in\llbracket
1,\ell\rrbracket$ such that

$D_{c}\bigg{(}\Big{(}W^{k}+\widetilde{\Lambda}_{k}+(0^{(k-1)n},-v_{j})\Big{)}\cap\Big{(}W^{k}+\widetilde{\Lambda}_{k}+(0^{(k-1)n},-v_{j^{\prime}})\Big{)}\bigg{)}\geq
D_{0}.$ (12)

Let $y$ be a point belonging to this intersection. Applying Equations (10) and
(12), we get that

$(y,x)\in
W^{k+1}+\big{(}\widetilde{\Lambda}_{k},0^{n}\big{)}+\big{(}0^{(k-1)n},-v_{j},w_{i_{j}}+Bv_{j}\big{)}$
(13)

and the same for $j^{\prime}$.

Two different cases can occur.

  1. (i)

Either $i_{j}=i_{j^{\prime}}$ (that is, the translation vectors $w_{i_{j}}$
and $w_{i_{j^{\prime}}}$ are equal). As a consequence, applying Equation (13),
we have

$\displaystyle(y,x)+\big{(}0^{(k-1)n},v_{j},-Bv_{j}-w_{i_{j}}\big{)}\in$
$\displaystyle\Big{(}W^{k+1}+\big{(}\widetilde{\Lambda}_{k},0^{n}\big{)}\Big{)}\cap$
$\displaystyle\Big{(}W^{k+1}+\big{(}\widetilde{\Lambda}_{k},0^{n}\big{)}+v^{\prime}\Big{)},$

with

$v^{\prime}=\big{(}0^{(k-1)n},-(v_{j^{\prime}}-v_{j}),B(v_{j^{\prime}}-v_{j})\big{)}\in\widetilde{\Lambda}_{k+1}\setminus\widetilde{\Lambda}_{k}.$

This implies that the set $W^{k+1}+\widetilde{\Lambda}_{k+1}$ auto-intersects
(see Figure 6).

  2. (ii)

Or $i_{j}\neq i_{j^{\prime}}$ (that is, $w_{i_{j}}\neq w_{i_{j^{\prime}}}$).
Combining Equations (13) and (11) (note that
$\big{(}\widetilde{\Lambda}_{k},0^{n}\big{)}\subset\widetilde{\Lambda}_{k+1}$),
we get

$(y,x)\in\Big{(}W^{k+1}+\widetilde{\Lambda}_{k+1}+\big{(}0^{kn},w_{i_{j}}\big{)}\Big{)}\cap\Big{(}W^{k+1}+\widetilde{\Lambda}_{k+1}+\big{(}0^{kn},w_{i_{j^{\prime}}}\big{)}\Big{)}.$

This implies that two distinct vertical translates of
$W^{k+1}+\widetilde{\Lambda}_{k+1}$ intersect (see Figure 6).

We now look at the global behaviour of all the $x$ such that $\overline{x}\in
U$. Again, we have two cases.

  1. (1)

Either for more than the half of such $\overline{x}$ (for Lebesgue measure),
we are in the case (i). To each of such $\overline{x}$ corresponds a
translation vector $w_{i}$. We choose $w_{i}$ such that the set of
corresponding $\overline{x}$ has the biggest measure; this measure is bigger
than $\varepsilon/\big{(}2(\ell-1)\big{)}\geq\varepsilon/(2\ell)$. Reasoning
as in the proof of Proposition 16, and in particular using the notations of
Corollary 19, we get that the density $D_{1}$ of the auto-intersection of
$W^{k+1}+\widetilde{\Lambda}_{k+1}+(0,w_{i})$ is bigger than
$D_{0}\varepsilon/(2\ell)$. This leads to (using Corollary 19)

$D_{c}(W^{k+1}+\widetilde{\Lambda}_{k+1})<D_{c}(W^{k}+\widetilde{\Lambda}_{k})-\frac{D_{0}\varepsilon}{4\ell}.$

In this case, we get the conclusion (1) of the lemma.

  2. (2)

Or for more than the half of such $\overline{x}$, we are in the case (ii).
Choosing the couple $(w_{i},w_{i^{\prime}})$ such that the measure of the set
of corresponding $\overline{x}$ is the greatest, we get

$D_{c}\bigg{(}\Big{(}W^{k+1}+\widetilde{\Lambda}_{k+1}+(0^{kn},w_{i})\Big{)}\cap\Big{(}W^{k+1}+\widetilde{\Lambda}_{k+1}+(0^{kn},w_{i^{\prime}})\Big{)}\bigg{)}\geq\frac{D_{0}\varepsilon}{(\ell-1)(\ell-2)}.$

In this case, we get the conclusion (2) of the lemma.

∎

Figure 7. Intersection of cubes in the case where the rate is bigger than
$1/3$. The thickening of the cubes of $W^{k}+\widetilde{\Lambda}_{k}$ is
represented in dark blue and the thickening of the rest of the cubes of
$W^{k+1}+\widetilde{\Lambda}_{k+1}$ is represented in light blue; we have also
represented another cube of $W^{k+2}+\widetilde{\Lambda}_{k+2}$ in yellow. We
see that if the projection on the $z$-axis of the centre of the yellow cube is
smaller than 1, then there is automatically an intersection between this cube
and one of the blue cubes.

We can now prove Theorem 20.

###### Proof of Theorem 20.

As in the proof of Proposition 16, we proceed by induction on $k$. Suppose
that $\widetilde{\Lambda}_{k}$ is such that
$D_{c}(W^{k}+\widetilde{\Lambda}_{k})>1/\ell$. Then, Lemma 24 ensures that it
is not possible to have $\ell$ disjoint translates of
$W^{k}+\widetilde{\Lambda}_{k}$. Applying Lemma 25, we obtain that either
$D_{c}(W^{k+1}+\widetilde{\Lambda}_{k+1})<D_{c}(W^{k}+\widetilde{\Lambda}_{k})$,
or it is not possible to have $\ell-1$ disjoint translates of
$W^{k+1}+\widetilde{\Lambda}_{k+1}$. And so on, applying Lemma 25 at most
$\ell-1$ times, there exists $k^{\prime}\in\llbracket k+1,k+\ell-1\rrbracket$
such that $W^{k^{\prime}}+\widetilde{\Lambda}_{k^{\prime}}$ has additional
auto-intersections. Quantitatively, combining Lemmas 24 and 25, we get

$D_{c}\big{(}W^{k+\ell-1}+\widetilde{\Lambda}_{k+\ell-1}\big{)}\leq
D\big{(}W^{k}+\widetilde{\Lambda}_{k}\big{)}-\varepsilon\varepsilon^{\ell-1}2\frac{\ell
D_{c}(W^{k}+\widetilde{\Lambda}_{k})-1}{\ell(\ell-1)},$

thus

$D_{c}\big{(}W^{k+\ell-1}+\widetilde{\Lambda}_{k+\ell-1}\big{)}-1/\ell\leq\left(1-\frac{2\varepsilon^{\ell}}{\ell-1}\right)\Big{(}D_{c}\big{(}W^{k}+\widetilde{\Lambda}_{k}\big{)}-1/\ell\Big{)},$

in other words, if we denote
$\overline{\tau}^{k}=\overline{\tau}^{k}(B_{1},\cdots,B_{k})$ and
$\lambda_{\ell}=1-\frac{2\varepsilon^{\ell}}{\ell-1}$,

$\overline{\tau}^{k+\ell-1}-1/\ell\leq\lambda_{\ell}\Big{(}\overline{\tau}^{k}-1/\ell\Big{)}.$
(14)

This implies that for every $\ell>0$, the sequence of rates
$\overline{\tau}^{k}$ is smaller than a sequence converging exponentially fast
to $1/\ell$: we get Equation (6). In particular, the asymptotic rate of
injectivity is generically equal to zero.

We now prove the estimation of Equation (7). Suppose that
$\overline{\tau}^{k}\in[1/(\ell-2),1/(\ell-1)]$, we compute how long it takes
for the rate to be smaller than $1/(\ell-1)$. We apply Equation (14) $j$ times
to $\ell$ and get

$\overline{\tau}^{k+j\ell}-1/\ell\leq\lambda_{\ell}^{j}(\overline{\tau}^{k}-1/\ell),$

with $\lambda=1-\left(\frac{\varepsilon}{\ell^{2}}\right)^{\ell}$. In the
worst case, we have $\overline{\tau}^{k}=1/(\ell-2)$, thus if $j^{\prime}$
satisfies

$\frac{1}{\ell-1}-\frac{1}{\ell}=\lambda_{\ell}^{j^{\prime}}\left(\frac{1}{\ell-2}-\frac{1}{\ell}\right),$
(15)

then $j=\lceil j^{\prime}\rceil$ is such that $\overline{\tau}^{k+j\ell}\leq
1/(\ell-1)$. Equation (15) is equivalent to

$j^{\prime}=\frac{-1}{\log\lambda_{\ell}}\left(\log
2-\log\left(1-\frac{1}{\ell-1}\right)\right).$

And for $\ell$ very big, we have the equivalent (recall that
$\lambda_{\ell}=1-\frac{1}{2}\left(\frac{\varepsilon}{\ell^{2}}\right)^{\ell}$)

$j^{\prime}\sim\left(\frac{\ell^{2}}{\varepsilon}\right)^{\ell}2\log 2.$

Thus, when $\ell$ is large enough, the time it takes for the rate to decrease
from $1/(\ell-2)$ to $1/(\ell-1)$ is smaller than
$\ell^{2(\ell+1)}=e^{2(\ell+1)\log\ell}$.

On the other hand, if we set $f(k)=(\log k)^{-\nu}$, the time it takes for $f$
to go from $1/(\ell-2)$ to $1/(\ell-1)$ is equal to

$e^{(\ell-1)^{1/\nu}}-e^{(\ell-2)^{1/\nu}}=e^{(\ell-1)^{1/\nu}}\left(1-e^{(\ell-2)^{1/\nu}-(\ell-1)^{1/\nu}}\right)\sim
e^{(\ell-1)^{1/\nu}}$

when $l$ goes to infinity, thus smaller than $e^{(\ell-1)^{1/\nu}+1}$ when
$\ell$ is large enough. But we have
$2(\ell+1)\log\ell=o\big{(}(\ell-1)^{1/\nu}+1\big{)}$. So, when $\ell$ is
large enough, it takes arbitrarily much more time for $\overline{\tau}^{k}$ to
decrease from $1/(\ell-2)$ to $1/(\ell-1)$ than for $f$ to decrease from
$1/(\ell-2)$ to $1/(\ell-1)$. As a consequence, $\overline{\tau}(k)=o(f(k))$.

Finally, we quickly explain how to adapt these arguments to get the final part
of the theorem. As $d\big{(}A_{k},\bigcup_{q}V_{q}\big{)}>\delta$ for a
positive asymptotic density $d$ of integers $k$, for any $k_{0}\in\mathbf{N}$,
there exists an integer $m\in\mathbf{N}$ such that the proportion of integers
$i\in\mathbf{N}$ between $m$ and $m+k_{0}$ such that
$d\big{(}A_{i},\bigcup_{q}V_{q}\big{)}>\delta$ is bigger than $d/2$. We get
the conclusion by following the first part of the proof of the theorem, by
using additionally Lemma 27 for the integers $i$ such that
$d\big{(}A_{i},\bigcup_{q}V_{q}\big{)}\leq\delta$. ∎

##  3\. A local-global formula for generic expanding maps and generic
diffeomorphisms

The goal of this section is to study the rate of injectivity of generic
$C^{r}$-expanding maps and $C^{r}$-generic diffeomorphisms of the torus
$\mathbf{T}^{n}$. Here, the term expanding map is taken from the point of view
of discretizations: we say that a linear map $A$ is expanding if there does
not exist two distinct integer points $x,y\in\mathbf{Z}^{n}$ such that
$\widehat{A}(x)=\widehat{A}(y)$. This condition is satisfied in particular if
for every $x\neq 0$, we have $\|Ax\|_{\infty}\leq\|x\|_{\infty}$; thus when
$n=1$ this definition coincides with the classical definition of expanding
map.

The main result of this section is that the rate of injectivity of both
generic $C^{1}$-diffeomorphisms and generic $C^{r}$-expanding maps of the
torus $\mathbf{T}^{n}$ is obtained from a local-global formula (Theorems 28
and 33). Let us begin by explaining the case of diffeomorphisms.

######  Theorem 28.

Let $r\geq 1$, and $f\in\operatorname{Diff}^{r}(\mathbf{T}^{n})$ (or
$f\in\operatorname{Diff}^{r}(\mathbf{T}^{n},\operatorname{Leb})$) be a generic
diffeomorphism. Then $\tau^{k}(f)$ is well defined (that is, the limit
superior in (1) is a limit) and satisfies:

$\displaystyle\tau^{k}(f)$
$\displaystyle=\int_{\mathbf{T}^{n}}\tau^{k}\left(Df_{x},\cdots,Df_{f^{k-1}(x)}\right)\,\operatorname{d}\operatorname{Leb}(x)$
$\displaystyle=\int_{\mathbf{T}^{n}}\overline{\tau}^{k}\left(Df_{x},\cdots,Df_{f^{k-1}(x)}\right)\,\operatorname{d}\operatorname{Leb}(x)$

(with $\overline{\tau}$ defined by Equation (4) page 4). Moreover, the
function $\tau^{k}$ is continuous in $f$.

The idea of the proof of this theorem is very simple: locally, the
diffeomorphism is almost equal to a linear map. This introduces an
intermediate _mesoscopic_ scale on the torus:

  * •

at the macroscopic scale, the discretization of $f$ acts as $f$;

  * •

at the intermediate mesoscopic scale, the discretization of $f$ acts as a
linear map;

  * •

at the microscopic scale, we are able to see that the discretization is a
finite map and we see that the phase space is discrete.

This remark is formalized by Taylor’s formula: for every $\varepsilon>0$ and
every $x\in\mathbf{T}^{n}$, there exists $\rho>0$ such that $f$ and its Taylor
expansion at order 1 are $\varepsilon$-close on $B(x,\rho)$. We then suppose
that the derivative $Df_{x}$ is “good”: the rate of injectivity of any of its
$C^{1}$-small perturbations can be seen on a ball $B_{R}$ of $\mathbf{R}^{n}$
(with $R$ uniform in $x$). Then, the proof of the local-global formula is made
in two steps.

  * •

Prove that “a lot” of maps of $SL_{n}(\mathbf{R})$ are “good”. This is
formalized by Lemma 34, which gives estimations of the size of the
perturbations of the linear map allowed, and of the size of the ball $B_{R}$.
Its proof is quite technical and uses crucially the formalism of model sets,
and an improvement of Weyl’s criterion.

  * •

Prove that for a generic diffeomorphism, the derivative satisfies the
conditions of Lemma 34 at almost every point. This follows easily from Thom’s
transversality theorem.

As the case of expanding maps is more complicated but similar, we will prove
the local-global formula only for expanding maps; the adaptation of it for
diffeomorphisms is straightforward.

Remark that the hypothesis of genericity is necessary to get Theorem 28. For
example, it can be seen that if we set

$f_{0}=\left(\begin{matrix}\frac{1}{2}&-1\\\
\frac{1}{2}&1\end{matrix}\right),$

then $\tau(f_{0})=1/2$ whereas $\tau(f_{0}+(1/4,3/4))=3/4$. Thus, if $g$ is a
diffeomorphism of the torus which is equal to $f_{0}+v$ on an open subset of
$\mathbf{T}^{2}$, with $v$ a suitable translation vector, then the conclusions
of Theorem 28 does not hold (see Example 11.4 of [Gui15a] for more
explanations).

The definition of the linear analogue of the rate of injectivity of an
expanding map in time $k$ is more complicated than for diffeomorphisms: in
this case, the set of preimages has a structure of $d$-ary tree. We define the
rate of injectivity of a tree — with edges decorated by linear expanding maps
— as the probability of percolation of a random graph associated to this
decorated tree (see Definition 31). In particular, if all the expanding maps
were equal, then the connected component of the root of this random graph is a
Galton-Watson tree. We begin by the definition of the set of expanding maps.

######  Definition 29.

For $r\geq 1$ and $d\geq 2$, we denote by $\mathcal{D}^{r}(\mathbf{T}^{n})$
the set of $C^{r}$ “$\mathbf{Z}^{n}$-expanding maps” of $\mathbf{T}^{n}$ for
the infinite norm. More precisely, $\mathcal{D}^{r}(\mathbf{T}^{n})$ is the
set of maps $f:\mathbf{T}^{n}\to\mathbf{T}^{n}$, which are local
diffeomorphisms, such that the derivative $f^{(\lfloor r\rfloor)}$ is well
defined and belongs to $C^{r-\lfloor r\rfloor}(\mathbf{T}^{n})$ and such that
for every $x\in\mathbf{T}^{n}$ and every $v\in\mathbf{Z}^{n}\setminus\\{0\\}$,
we have $\|Df_{x}v\|_{\infty}\geq 1$.

In particular, for $f\in\mathcal{D}^{r}(\mathbf{T}^{n})$, the number of
preimages of any point of $\mathbf{T}^{n}$ is equal to a constant, that we
denote by $d$.

Remark that in dimension $n=1$, the set $\mathcal{D}^{r}(\mathbf{S}^{1})$
coincides with the classical set of expanding maps:
$f\in\mathcal{D}^{r}(\mathbf{S}^{1})$ if and only if it belongs to
$C^{r}(\mathbf{S}^{1})$ and $f^{\prime}(x)\geq 1$ for every
$x\in\mathbf{S}^{1}$.

We now define the linear setting corresponding to a map
$f\in\mathcal{D}(\mathbf{T}^{n})$.

######  Definition 30.

We set (see also Figure 9)

$I_{k}=\bigsqcup_{m=1}^{k}\llbracket 1,d\rrbracket^{m}$

the set of $m$-tuples of integers of $\llbracket 1,d\rrbracket$, for $1\leq
m\leq k$.

For ${\boldsymbol{i}}=(i_{1},\cdots,i_{m})\in\llbracket 1,d\rrbracket^{m}$, we
set $\operatorname{length}({\boldsymbol{i}})=m$ and
$\operatorname{father}({\boldsymbol{i}})=(i_{1},\cdots,i_{m-1})\in\llbracket
1,d\rrbracket^{m-1}$ (with the convention
$\operatorname{father}(i_{1})=\emptyset$).

$\emptyset$$(1)$$(2)$$(1,1)$$(1,2)$$(2,1)$$(2,2)$ Figure 8. The tree $T_{2}$
for $d=2$.

$y$$x_{(1)}$$x_{(2)}$$x_{(1,1)}$$x_{(1,2)}$$x_{(2,1)}$$x_{(2,2)}$$\det
Df_{x_{(1)}}^{-1}$$\det Df_{x_{(1,1)}}^{-1}$$\det Df_{x_{(1,2)}}^{-1}$$\det
Df_{x_{(2)}}^{-1}$$\det Df_{x_{(2,1)}}^{-1}$$\det Df_{x_{(2,2)}}^{-1}$ Figure
9. The probability tree associated to the preimages of $y$, for $k=2$ and
$d=2$. We have $f(x_{(1,1)})=f(x_{(1,2)})=x_{(1)}$, etc.

The set $I_{k}$ is the linear counterpart of the set
$\bigsqcup_{m=1}^{k}f^{-m}(y)$. Its cardinal is equal to $d(1-d^{k})/(1-d)$.

######  Definition 31.

Let $k\in\mathbf{N}$. The _complete tree of order $k$_ is the rooted $d$-ary
tree $T_{k}$ whose vertices are the elements of $I_{k}$ together with the
root, denoted by $\emptyset$, and whose edges are of the form
$(\operatorname{father}({\boldsymbol{i}}),{\boldsymbol{i}})_{{\boldsymbol{i}}\in
I_{k}}$ (see Figure 9).

Let $(p_{\boldsymbol{i}})_{{\boldsymbol{i}}\in I_{k}}$ be a family of numbers
belonging to $[0,1]$. These probabilities will be seen as decorations of the
edges of the tree $T_{k}$. We will call _random graph associated to
$(p_{\boldsymbol{i}})_{{\boldsymbol{i}}\in I_{k}}$_ the random subgraph
$G_{(p_{\boldsymbol{i}})_{\boldsymbol{i}}}$ of $T_{k}$, such that the laws of
appearance the edges
$(\operatorname{father}({\boldsymbol{i}}),{\boldsymbol{i}})$ of
$G_{(p_{\boldsymbol{i}})_{\boldsymbol{i}}}$ are independent Bernoulli laws of
parameter $p_{\boldsymbol{i}}$. In other words,
$G_{(p_{\boldsymbol{i}})_{\boldsymbol{i}}}$ is obtained from $T_{k}$ by
erasing independently each vertex of $T_{k}$ with probability
$1-p_{\boldsymbol{i}}$.

We define the _mean density_
$\overline{D}((p_{\boldsymbol{i}})_{\boldsymbol{i}})$ of
$(p_{\boldsymbol{i}})_{{\boldsymbol{i}}\in I_{k}}$ as the probability that in
$G_{(p_{\boldsymbol{i}})_{\boldsymbol{i}}}$, there is at least one path
linking the root to a leaf.

Remark that if the probabilities $p_{\boldsymbol{i}}$ are constant equal to
$p$, the random graph $G_{(p_{\boldsymbol{i}})_{\boldsymbol{i}}}$ is a Galton-
Watson tree, where the probability for a vertex to have $i$ children is equal
to $\binom{d}{i}p^{i}(1-p)^{d-i}$.

######  Definition 32.

By the notation $\overline{D}((\det Df_{x}^{-1})_{x\in f^{-m}(y),\,1\leq m\leq
k})$, we will mean that the mean density isthe taken with respect to the
random graph $G_{f,y}$ associated to the decorated tree whose vertices are the
$f^{-m}(y)$ for $0\leq m\leq k$, and whose edges are of the form $(f(x),x)$
for $x\in f^{-m}(y)$ with $1\leq m\leq k$, each one being decorated by the
number $\det Df_{x}^{-1}$ (see Figure 9).

Recall that the rates of injectivity are defined by (see also Definition 5)

$\tau^{k}(f_{N})=\frac{\operatorname{Card}\big{(}(f_{N})^{k}(E_{N})\big{)}}{\operatorname{Card}(E_{N})}\qquad\text{and}\qquad\tau^{k}(f)=\limsup_{N\to+\infty}\tau^{k}(f_{N}).$

######  Theorem 33.

Let $r\geq 1$, $f$ a generic element of $\mathcal{D}^{r}(\mathbf{T}^{n})$ and
$k\in\mathbf{N}$. Then, $\tau^{k}(f)$ is a limit (that is, the sequence
$(\tau^{k}(f_{N}))_{N}$ converges), and we have

$\tau^{k}(f)=\int_{\mathbf{T}^{n}}\overline{D}\big{(}(\det
Df_{x}^{-1})_{\begin{subarray}{l}1\leq m\leq k\\\ x\in
f^{-m}(y)\end{subarray}}\big{)}\,\operatorname{d}\operatorname{Leb}(y).$ (16)

Moreover, the map $f\mapsto\tau^{k}(f)$ is continuous in $f$.

The proof of Theorem 33 is mainly based on the following lemma, which treats
the linear corresponding case. Its statement is divided into two parts, the
second one being a quantitative version of the first.

######  Lemma 34.

Let $k\in\mathbf{N}$, and a family $(A_{\boldsymbol{i}})_{{\boldsymbol{i}}\in
I_{k}}$ of invertible matrices, such that for any ${\boldsymbol{i}}\in I_{k}$
and any $v\in\mathbf{Z}^{n}\setminus\\{0\\}$, we have
$\|A_{\boldsymbol{i}}v\|_{\infty}\geq 1$.

If the image of the map

$\mathbf{Z}^{n}\ni x\mapsto\bigoplus_{{\boldsymbol{i}}\in
I_{k}}A_{\boldsymbol{i}}^{-1}A_{\operatorname{father}({\boldsymbol{i}})}^{-1}\cdots
A_{\operatorname{father}^{\operatorname{length}({\boldsymbol{i}})}({\boldsymbol{i}})}^{-1}x$

projects on a dense subset of the torus
$\mathbf{R}^{n\operatorname{Card}I_{k}}/\mathbf{Z}^{n\operatorname{Card}I_{k}}$,
then we have

$D\left(\bigcup_{{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}}\big{(}\widehat{A}_{\operatorname{father}^{k-1}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})\right)=\overline{D}\big{(}(\det
A_{\boldsymbol{i}}^{-1})_{\boldsymbol{i}}\big{)}.$

More precisely, for every $\ell^{\prime},c\in\mathbf{N}$, there exists a
locally finite union of positive codimension submanifolds $V_{q}$ of
$(GL_{n}(\mathbf{R}))^{\operatorname{Card}I_{k}}$ such that for every
$\eta^{\prime}>0$, there exists a radius $R_{0}>0$ such that if
$(A_{\boldsymbol{i}})_{{\boldsymbol{i}}\in I_{k}}$ satisfies
$d((A_{\boldsymbol{i}})_{\boldsymbol{i}},V_{q})>\eta^{\prime}$ for every $q$,
then for every $R\geq R_{0}$, and every family
$(v_{\boldsymbol{i}})_{{\boldsymbol{i}}\in I_{k}}$ of vectors of
$\mathbf{R}^{n}$, we have121212The map $\pi(A+v)$ is the discretization of the
affine map $A+v$.

$\left|D_{R}^{+}\left(\bigcup_{{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}}\big{(}\pi(A_{\operatorname{father}^{k-1}({\boldsymbol{i}})}+v_{\operatorname{father}^{k-1}({\boldsymbol{i}})})\circ\cdots\circ\pi(A_{\boldsymbol{i}}+v_{\boldsymbol{i}})\big{)}(\mathbf{Z}^{n})\right)-\overline{D}\big{(}(\det
A_{\boldsymbol{i}}^{-1})_{\boldsymbol{i}}\big{)}\right|<\frac{1}{\ell^{\prime}}$
(17)

(the density of the image set is “almost invariant” under perturbations by
translations), and for every $m\leq k$ and every
${\boldsymbol{i}}\in\llbracket 1,d\rrbracket^{k}$, we have131313Where
$(\mathbf{Z}^{n})^{\prime}$ stands for the set of points of $\mathbf{R}^{n}$
at least one coordinate of which belongs to $\mathbf{Z}+1/2$.

$D_{R}^{+}\left\\{x\in\big{(}A_{\operatorname{father}^{m}({\boldsymbol{i}})}+v_{\operatorname{father}^{m}({\boldsymbol{i}})}\big{)}(\mathbf{Z}^{n})\
\middle|\
d\big{(}x,(\mathbf{Z}^{n})^{\prime}\big{)}<\frac{1}{{c}\ell^{\prime}(2n+1)}\right\\}<\frac{1}{{c}\ell^{\prime}}$
(18)

(there is only a small proportion of the points of the image sets which are
obtained by discretizing points close to $(\mathbf{Z}^{n})^{\prime}$).

The local-global formula (16) will later follow from this lemma, an
appropriate application of Taylor’s theorem and Thom’s transversality theorem
(Lemma 37).

The next lemma uses the strategy of proof of Weyl’s criterion to get a uniform
convergence in Birkhoff’s theorem for rotations of the torus $\mathbf{T}^{n}$
whose rotation vectors are outside of a neighbourhood of a finite union of
hyperplanes.

######  Lemma 35 (Weyl).

Let $\operatorname{dist}$ be a distance generating the weak-* topology on
$\mathcal{P}$ the space of Borel probability measures on $\mathbf{T}^{n}$.
Then, for every $\varepsilon>0$, there exists a locally finite family of
affine hyperplanes $H_{i}\subset\mathbf{R}^{n}$, such that for every $\eta>0$,
there exists $M_{0}\in\mathbf{N}$, such that for every
$\boldsymbol{\lambda}\in\mathbf{R}^{n}$ satisfying
$d(\boldsymbol{\lambda},H_{q})>\eta$ for every $q$, and for every $M\geq
M_{0}$, we have

$\operatorname{dist}\left(\frac{1}{M}\sum_{m=0}^{M-1}\bar{\delta}_{m\boldsymbol{\lambda}}\,,\
\operatorname{Leb}_{\mathbf{R}^{n}/\mathbf{Z}^{n}}\right)<\varepsilon,$

where $\bar{\delta}_{x}$ is the Dirac measure of the projection of $x$ on
$\mathbf{R}^{n}/\mathbf{Z}^{n}$.

###### Proof of Lemma 35.

As $\operatorname{dist}$ generates the weak-* topology on $\mathcal{P}$, it
can be replaced by any other distance also generating the weak-* topology on
$\mathcal{P}$. So we consider the distance $\operatorname{dist}_{W}$ defined
by:

$\operatorname{dist}_{W}(\mu,\nu)=\sum_{\boldsymbol{k}\in\mathbf{N}^{n}}\frac{1}{2^{k_{1}+\cdots+k_{n}}}\left|\int_{\mathbf{R}^{n}/\mathbf{Z}^{n}}e^{i2\pi\boldsymbol{k}\cdot
x}\,\operatorname{d}(\mu-\nu)(x)\right|;$

there exists $K>0$ and $\varepsilon^{\prime}>0$ such that if a measure
$\mu\in\mathcal{P}$ satisfies

$\forall\boldsymbol{k}\in\mathbf{N}^{n}:\,0<k_{1}+\cdots+k_{n}\leq
K,\quad\left|\int_{\mathbf{R}^{n}/\mathbf{Z}^{n}}e^{i2\pi\boldsymbol{k}\cdot
x}\,\operatorname{d}\mu(x)\right|<\varepsilon^{\prime},$ (19)

then $\operatorname{dist}(\mu,\operatorname{Leb})<\varepsilon$.

For every $\boldsymbol{k}\in\mathbf{N}^{n}\setminus\\{0\\}$ and
$j\in\mathbf{Z}$, we set

$H_{\boldsymbol{k}}^{j}=\\{\boldsymbol{\lambda}\in\mathbf{R}^{n}\mid\boldsymbol{k}\cdot\boldsymbol{\lambda}=j\\}.$

Remark that the family $\\{H_{\boldsymbol{k}}^{j}\\}$, with $j\in\mathbf{Z}$
and $\boldsymbol{k}$ such that $0<k_{1}+\cdots+k_{n}\leq K$, is locally
finite. We denote by $\\{H_{q}\\}_{q}$ this family, and choose
$\boldsymbol{\lambda}\in\mathbf{R}^{n}$ such that
$d(\boldsymbol{\lambda},H_{q})>\eta$ for every $q$. We also take

$M_{0}\geq\frac{2}{\varepsilon^{\prime}\left|1-e^{i2\pi\eta}\right|}.$ (20)

Thus, for every $\boldsymbol{k}\in\mathbf{N}^{n}$ such that
$k_{1}+\cdots+k_{n}\leq K$, and every $M\geq M_{0}$, the measure

$\mu=\frac{1}{M}\sum_{m=0}^{M-1}\bar{\delta}_{m\boldsymbol{\lambda}}.$

satisfies

$\left|\int_{\mathbf{R}^{n}/\mathbf{Z}^{n}}e^{i2\pi\boldsymbol{k}x}\,\operatorname{d}\mu(x)\right|=\frac{1}{M}\left|\frac{1-e^{i2\pi
M\boldsymbol{k}\cdot\boldsymbol{\lambda}}}{1-e^{i2\pi\boldsymbol{k}\cdot\boldsymbol{\lambda}}}\right|\leq\frac{2}{M_{0}}\frac{1}{\left|1-e^{i2\pi\boldsymbol{k}\cdot\boldsymbol{\lambda}}\right|}.$

By (20) and the fact that
$d(\boldsymbol{k}\cdot\boldsymbol{\lambda},\mathbf{Z})\geq\eta$, we deduce
that

$\left|\int_{\mathbf{R}^{n}/\mathbf{Z}^{n}}e^{i2\pi\boldsymbol{k}x}\,\operatorname{d}\mu(x)\right|\leq\varepsilon^{\prime}.$

Thus, the measure $\mu$ satisfies the criterion (19), which proves the lemma.
∎

###### Proof of Lemma 34.

To begin with, let us treat the case $d=1$. Let $A_{1},\cdots,A_{k}$ be $k$
invertible matrices. We want to compute the rate of injectivity of
$\widehat{A}_{k}\circ\cdots\circ\widehat{A}_{1}$. Recall that we set

$\widetilde{M}_{A_{1},\cdots,A_{k}}=\left(\begin{array}[]{ccccc}A_{1}&-\operatorname{Id}&&&\\\
&A_{2}&-\operatorname{Id}&&\\\ &&\ddots&\ddots&\\\
&&&A_{k-1}&-\operatorname{Id}\\\ &&&&A_{k}\end{array}\right)\in
M_{nk}(\mathbf{R}),$

$\widetilde{\Lambda}_{k}=\widetilde{M}_{\lambda_{1},\cdots,\lambda_{k}}\mathbf{Z}^{nk}$
and $W^{k}=]-1/2,1/2]^{nk}$. Resuming the proof of Proposition 9, we see that
$x\in\big{(}\widehat{A}_{k}\circ\cdots\circ\widehat{A}_{1}\big{)}(\mathbf{Z}^{n})$
if and only if $(0^{n(k-1)},x)\in W^{k}+\widetilde{\Lambda}_{k}$. This implies
the following statement.

######  Lemma 36.

We have

$\det(A_{k}\cdots
A_{1})D\big{(}\widehat{A}_{k}\circ\cdots\circ\widehat{A}_{1}\big{)}(\mathbf{Z}^{n})=\nu(\operatorname{pr}_{\mathbf{R}^{nk}/\widetilde{\Lambda}_{k}}(W^{k})),$
(21)

where $\nu$ is the uniform measure on the submodule
$\operatorname{pr}_{\mathbf{R}^{nk}/\widetilde{\Lambda}_{k}}(0^{n(k-1)},\mathbf{Z}^{n})$
of $\mathbf{R}^{nk}/\widetilde{\Lambda}_{k}$.

In particular, if the image of the map

$\mathbf{Z}^{n}\ni x\mapsto\bigoplus_{m=1}^{k}(A_{m})^{-1}\cdots(A_{k})^{-1}x$

projects on a dense subset of the torus $\mathbf{R}^{nk}/\mathbf{Z}^{nk}$,
then the quantity (21) is equal to the volume of the intersection between the
projection of $W^{k}$ on $\mathbf{R}^{nk}/\widetilde{\Lambda}_{k}$ and a
fundamental domain of $\widetilde{\Lambda}_{k}$ (see the end of the proof of
Proposition 9 and in particular the form of the matrix
$\widetilde{M}_{A_{1},\cdots,A_{k}}^{-1}$). By the hypothesis made on the
matrices $A_{m}$ — that is, for any $v\in\mathbf{Z}^{n}\setminus\\{0\\}$,
$\|A_{m}v\|_{\infty}\geq 1$ — this volume is equal to $1$ (simply because the
restriction to $W^{k}$ of the projection
$\mathbf{R}^{nk}\mapsto\mathbf{R}^{nk}/\widetilde{\Lambda}_{k}$ is injective).
Thus, the density of the set
$\big{(}\widehat{A}_{k}\circ\cdots\circ\widehat{A}_{1}\big{)}(\mathbf{Z}^{n})$
is equal to $1/(\det(A_{k}\cdots A_{1}))$ .

$\displaystyle D\left(\bigcup_{{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}}\\!\\!\\!\\!\big{(}\widehat{A}_{\operatorname{father}^{k-1}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})\right)$$\displaystyle
D\left(\bigcup_{\begin{subarray}{c}{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}\\\
\operatorname{father}^{k-1}({\boldsymbol{i}})=1\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\big{(}\widehat{A}_{\operatorname{father}^{k-2}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})\right)$$\displaystyle
D\left(\bigcup_{\begin{subarray}{c}{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}\\\
\operatorname{father}^{k-1}({\boldsymbol{i}})=2\end{subarray}}\\!\\!\\!\\!\\!\\!\\!\\!\\!\\!\big{(}\widehat{A}_{\operatorname{father}^{k-2}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})\right)$$\det
A_{(1)}^{-1}$$\det A_{(2)}^{-1}$ Figure 10. Calculus of the density of the
image set at the level $k$ according to the density of its sons.

We now consider the general case where $d$ is arbitrary. We take a family
$(A_{\boldsymbol{i}})_{{\boldsymbol{i}}\in I_{k}}$ of invertible matrices,
such that for any ${\boldsymbol{i}}\in I_{k}$ and any
$v\in\mathbf{Z}^{n}\setminus\\{0\\}$, we have
$\|A_{\boldsymbol{i}}v\|_{\infty}\geq 1$. A point $x\in\mathbf{Z}^{n}$ belongs
to

$\bigcup_{{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}}\big{(}\widehat{A}_{\operatorname{father}^{k-1}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})$

if and only if there exists ${\boldsymbol{i}}\in\llbracket 1,d\rrbracket^{k}$
such that $(0^{m-1},x)\in W^{k}+\widetilde{\Lambda}_{\boldsymbol{i}}$.
Equivalently, a point $x\in\mathbf{Z}^{n}$ does not belong to the set

$\big{(}\widehat{A}_{\operatorname{father}^{k-1}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})$

if and only if for every ${\boldsymbol{i}}\in\llbracket 1,d\rrbracket^{k}$, we
have $(0^{n(k-1)},x)\notin W^{k}+\widetilde{\Lambda}_{\boldsymbol{i}}$. Thus,
if the image of the map

$\mathbf{Z}^{n}\ni x\mapsto\bigoplus_{{\boldsymbol{i}}\in
I_{k}}A_{\boldsymbol{i}}^{-1}A_{\operatorname{father}({\boldsymbol{i}})}^{-1}\cdots
A_{\operatorname{father}^{\operatorname{length}({\boldsymbol{i}})}({\boldsymbol{i}})}^{-1}x$

projects on a dense subset of the torus
$\mathbf{R}^{n\operatorname{Card}I_{k}}/\mathbf{Z}^{n\operatorname{Card}I_{k}}$,
then the events $x\in S_{i}$, with

$S_{i}=\bigcup_{\begin{subarray}{c}{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}\\\
\operatorname{father}^{k-1}({\boldsymbol{i}})=i\end{subarray}}\big{(}\widehat{A}_{\operatorname{father}^{k-1}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})$

are independent (see Figure 10), meaning that for every $F\subset\llbracket
1,d\rrbracket$, we have

$D\left(\bigcap_{i\in F}S_{i}\right)=\prod_{i\in F}D\big{(}S_{i}\big{)}.$ (22)

Thus, by the inclusion-exclusion principle, we get

$D\left(\bigcup_{i\in\llbracket 1,d\rrbracket}S_{i}\right)=\sum_{\emptyset\neq
F\subset\llbracket 1,d\rrbracket}(-1)^{\operatorname{Card}(F)+1}\prod_{i\in
F}D\big{(}S_{i}\big{)}.$

Moreover, the fact that for any ${\boldsymbol{i}}\in I_{k}$ and any
$v\in\mathbf{Z}^{n}\setminus\\{0\\}$, we have
$\|A_{\boldsymbol{i}}v\|_{\infty}\geq 1$ leads to

$D(S_{i})=\det A_{\operatorname{father}^{k-1}({\boldsymbol{i}})}^{-1}\
D\left(\bigcup_{\begin{subarray}{c}{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}\\\
\operatorname{father}^{k-1}({\boldsymbol{i}})=i\end{subarray}}\big{(}\widehat{A}_{\operatorname{father}^{k-2}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})\right).$

These facts imply that the density we look for follows the same recurrence
relation as $\overline{D}\big{(}(\det
A_{\boldsymbol{i}}^{-1})_{\boldsymbol{i}}\big{)}$, thus

$D\left(\bigcup_{{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}}\big{(}\widehat{A}_{\operatorname{father}^{k-1}({\boldsymbol{i}})}\circ\cdots\circ\widehat{A}_{\boldsymbol{i}}\big{)}(\mathbf{Z}^{n})\right)=\overline{D}\big{(}(\det
A_{\boldsymbol{i}}^{-1})_{\boldsymbol{i}}\big{)}.$

The second part of the lemma is an effective improvement of the first one. To
obtain the bound (17), we combine Lemma 35 with Lemma 36 to get that for every
$\varepsilon>0$, there exists a locally finite collection of submanifolds
$V_{q}$ of $(GL_{n}(\mathbf{R}))^{\operatorname{Card}I_{k}}$ with positive
codimension, such that for every $\eta^{\prime}>0$, there exists $R_{0}>0$
such that if $d((A_{\boldsymbol{i}})_{\boldsymbol{i}},V_{q})>\eta^{\prime}$
for every $q$, then Equation (22) is true up to $\varepsilon$.

The other bound (18) is obtained independently from the rest of the proof by a
direct application of Lemma 35 and of Lemma 36 applied to $k=1$. ∎

######  Lemma 37 (Perturbations in $C^{r}$ topology).

Let $1\leq r\leq+\infty$ and $f$ a generic element of
$\mathcal{D}^{r}(\mathbf{T}^{n})$. Then, for every $k\in\mathbf{N}$, every
$\ell^{\prime}\in\mathbf{N}$ and every finite collection $(V_{q})$ of
submanifolds of positive codimension of $(GL_{n}(\mathbf{R}))^{dm}$, there
exists $\eta>0$ such that the set

$T_{\eta}=\left\\{y\in\mathbf{T}^{n}\ \middle|\ \forall
q,\,d\Big{(}\big{(}Df_{x}\big{)}_{\begin{subarray}{l}1\leq m\leq k\\\ x\in
f^{-m}(y)\end{subarray}}\,,\,V_{q}\Big{)}>\eta\right\\}$

contains a finite disjoint union of cubes141414here, a cube is just any ball
for the infinite norm., whose union has measure bigger than
$1-1/\ell^{\prime}$.

###### Proof of Lemma 37.

By Thom’s transversality theorem, for a generic map
$f\in\mathcal{D}^{r}(\mathbf{T}^{n})$, the set

$\left\\{y\in\mathbf{T}^{n}\ \middle|\ \exists
q,\,\big{(}Df_{x}\big{)}_{\begin{subarray}{l}1\leq m\leq k\\\ x\in
f^{-m}(y)\end{subarray}}\in V_{q}\right\\}$

is a locally finite union of positive codimension submanifolds. Thus, the sets
$T_{\eta}^{\scriptscriptstyle\complement}$ are compact sets and their
(decreasing) intersection over $\eta$ is a locally finite union of positive
codimension submanifolds. So, there exists $\eta>0$ such that
$T_{\eta}^{\scriptscriptstyle\complement}$ is close enough to this set for
Hausdorff topology to have the conclusions of the lemma. ∎

We can now begin the proof of Theorem 33.

###### Proof of Theorem 33.

Let $f\in\mathcal{D}^{r}(\mathbf{T}^{n})$. The idea is to cut the torus
$\mathbf{T}^{n}$ into small pieces on which $f$ is very close to its Taylor
expansion at order $1$.

Let $m\in\mathbf{N}$, and $\mathcal{U}_{\ell}$ ($\ell\in\mathbf{N}^{*}$) be
the set of maps $f\in\mathcal{D}^{r}(\mathbf{T}^{n})$ such that the set of
accumulation points of the sequence $(\tau^{m}_{N}(f))_{N}$ is included in the
ball of radius $1/\ell$ and centre

$\int_{\mathbf{T}^{n}}\overline{D}\big{(}(Df_{x})_{\begin{subarray}{l}1\leq
m\leq k\\\ x\in
f^{-m}(y)\end{subarray}}\big{)}\,\operatorname{d}\operatorname{Leb}(y).$

(that is, the right side of Equation (16)). We want to show that
$\mathcal{U}_{\ell}$ contains an open and dense subset of
$\mathcal{D}^{r}(\mathbf{T}^{n})$. In other words, we pick a map $f$, an
integer $\ell$ and $\delta>0$, and we want to find another map
$g\in\mathcal{D}^{r}(\mathbf{T}^{n})$ which is $\delta$-close to $f$ for the
$C^{r}$ distance, and which belongs to the interior of $\mathcal{U}_{\ell}$.

To do that, we first set $\ell^{\prime}=3\ell$ and
$c=d(1-d^{k})/(1-d)=\operatorname{Card}(I_{k})$, and use Lemma 34 to get a
locally finite union of positive codimension submanifolds $V_{q}$ of
$(GL_{n}(\mathbf{R}))^{\operatorname{Card}(I_{k})}$. We then apply Lemma 37 to
these submanifolds, to the $\delta$ we have fixed at the beginning of the
proof and to $\ell^{\prime}=4\ell$; this gives us a parameter $\eta>0$ and a
map $g\in\mathcal{D}^{r}(\mathbf{T}^{n})$ such that $d_{C^{r}}(f,g)<\delta$,
and such that the set

$\left\\{y\in\mathbf{T}^{n}\ \middle|\ \forall
q,\,d\Big{(}\big{(}Dg_{x}\big{)}_{\begin{subarray}{l}1\leq m\leq k\\\ x\in
g^{-m}(y)\end{subarray}}\,,\,V_{q}\Big{)}<\eta\right\\}$

is contained in a disjoint finite union $\mathcal{C}$ of cubes, whose union
has measure bigger than $1-1/(4\ell)$. Finally, we apply Lemma 34 to
$\eta^{\prime}=\eta/2$; this gives us a radius $R_{0}>0$ such that if
$(A_{\boldsymbol{i}})_{{\boldsymbol{i}}\in I_{k}}$ is a family of matrices of
$GL_{n}(\mathbf{R})$ satisfying
$d((A_{\boldsymbol{i}})_{\boldsymbol{i}},V_{q})>\eta/2$ for every $q$, then
for every $R\geq R_{0}$, and every family
$(v_{\boldsymbol{i}})_{{\boldsymbol{i}}\in I_{k}}$ of vectors of
$\mathbf{R}^{n}$, we have

$\left|D_{R}^{+}\left(\bigcup_{{\boldsymbol{i}}\in\llbracket
1,d\rrbracket^{k}}\big{(}\pi(A_{\operatorname{father}^{k-1}({\boldsymbol{i}})}+v_{\operatorname{father}^{k-1}({\boldsymbol{i}})})\circ\cdots\circ\pi(A_{\boldsymbol{i}}+v_{\boldsymbol{i}})\big{)}(\mathbf{Z}^{n})\right)-\overline{D}\big{(}(\det
A_{\boldsymbol{i}}^{-1})_{\boldsymbol{i}}\big{)}\right|<\frac{1}{3\ell},$ (23)

and for every $i,j$,

$D_{R}^{+}\left\\{x\in\big{(}A_{j^{m}({\boldsymbol{i}})}+v_{j^{m}({\boldsymbol{i}})}\big{)}(\mathbf{Z}^{n})\
\middle|\
d\big{(}x,(\mathbf{Z}^{n})^{\prime}\big{)}<\frac{1}{3\ell(2n+1)\operatorname{Card}I_{k}}\right\\}<\frac{1}{3\ell\operatorname{Card}I_{k}}.$
(24)

We now take a map $h\in\mathcal{D}^{r}(\mathbf{T}^{n})$ such that
$d_{C^{1}}(g,h)<\delta^{\prime}$, and prove that if $\delta^{\prime}$ is small
enough, then $h$ belongs to the interior of $\mathcal{U}_{\ell}$. First of
all, we remark that if $\delta^{\prime}$ is small enough, then the set

$\left\\{y\in\mathbf{T}^{n}\ \middle|\ \forall
q,\,d\Big{(}\big{(}Dh_{x}\big{)}_{\begin{subarray}{l}1\leq m\leq k\\\ x\in
h^{-m}(y)\end{subarray}}\,,\,V_{q}\Big{)}>\eta/2\right\\}$

contains a set $\mathcal{C}^{\prime}$, which is a finite union of cubes whose
union has measure bigger than $1-1/(3\ell)$.

Let $C$ be a cube of $\mathcal{C}^{\prime}$, $y\in C$ and $x\in f^{-m}(y)$,
with $1\leq m\leq k$. We write the Taylor expansion of order 1 of $h$ at the
neighbourhood of $x$; by compactness we obtain

$\sup\left\\{\frac{1}{\|z\|}\big{\|}h(x+z)-h(x)-Dh_{x}(z)\big{\|}\ \middle|\
x\in C,\,z\in B(0,\rho)\right\\}\underset{\rho\to 0}{\longrightarrow}0.$

Thus, for every $\varepsilon>0$, there exists $\rho>0$ such that for all $x\in
C$ and all $z\in B(0,\rho)$, we have

$\left\|h(x+z)-\big{(}h(x)+Dh_{x}(z)\big{)}\right\|<\varepsilon\|z\|\leq\varepsilon\rho.$
(25)

We now take $R\geq R_{0}$. We want to find an order of discretization $N$ such
that the error made by linearizing $h$ on $B(x,R/N)$ is small compared to $N$,
that is, for every $z\in B(0,R/N)$, we have

$\left\|h(x+z)-\big{(}h(x)+Dh_{x}(z)\big{)}\right\|<\frac{1}{3\ell(2n+1)\operatorname{Card}I_{k}}\cdot\frac{1}{N}.$

To do that, we apply Equation (25) to

$\varepsilon=\frac{1}{3R\ell(2n+1)\operatorname{Card}I_{k}},$

to get a radius $\rho>0$ (we can take $\rho$ as small as we want), and we set
$N=\lceil R/\rho\rceil$ (thus, we can take $N$ as big as we want). By (25),
for every $z\in B(0,R)$, we obtain the desired bound:

$\left\|h(x+z/N)-\big{(}h(x)+Dh_{x}(z/N)\big{)}\right\|<\frac{1}{3\ell(2n+1)\operatorname{Card}I_{k}}\cdot\frac{1}{N}.$

Combined with (24), this leads to

$\frac{\operatorname{Card}\Big{(}h_{N}\big{(}B(x,R/N)\big{)}\,\Delta\,P_{N}\big{(}h(x)+Dh_{x}(B(0,R/N))\big{)}\Big{)}}{\operatorname{Card}\big{(}B(x,R/N)\cap
E_{N}\big{)}}\leq\frac{1}{3\ell\operatorname{Card}I_{k}};$ (26)

in other words, on every ball of radius $R/N$, the image of $E_{N}$ by $h_{N}$
and the discretization of the linearization of $h$ are almost the same (that
is, up to a proportion $1/(3\ell\operatorname{Card}I_{k})$ of points).

We now set $R_{1}=R_{0}\|f^{\prime}\|_{\infty}^{m}$, and choose $R\geq R_{1}$,
to which is associated a number $\rho>0$ and an order $N=\lceil R/\rho\rceil$,
that we can choose large enough so that $2R/N\leq\|f^{\prime}\|_{\infty}$. We
also choose $y\in C$. As

$\operatorname{Card}\big{(}h_{N}^{m}(E_{N})\cap
B(y,R/N)\big{)}=\operatorname{Card}\left(\bigcup_{x\in
h^{-m}(y)}h_{N}^{m}\big{(}B(x,R/N)\cap E_{N}\big{)}\cap B(y,R/N)\right),$

and using the estimations (23) and (26), we get

$\left|\frac{\operatorname{Card}\big{(}h_{N}^{m}(E_{N})\cap
B(y,R/N)\big{)}}{\operatorname{Card}\big{(}B(y,R/N)\cap
E_{N}\big{)}}-\overline{D}\big{(}(\det Df_{x}^{-1})_{\begin{subarray}{l}1\leq
m\leq k\\\ x\in f^{-m}(y)\end{subarray}}\big{)}\right|<\frac{2}{3\ell}.$

As such an estimation holds on a subset of $\mathbf{T}^{n}$ of measure bigger
than $1-1/(3\ell)$, we get the conclusion of the theorem. ∎

We can easily adapt the proof of Lemma 34 to the case of sequences of
matrices, without the hypothesis of expansivity.

######  Lemma 38.

For every $k\in\mathbf{N}$ and every $\ell^{\prime},c\in\mathbf{N}$, there
exists a locally finite union of positive codimension submanifolds $V_{q}$ of
$(GL_{n}(\mathbf{R}))^{k}$ (respectively $(SL_{n}(\mathbf{R}))^{k}$) such that
for every $\eta^{\prime}>0$, there exists a radius $R_{0}>0$ such that if
$(A_{m})_{1\leq m\leq k}$ is a finite sequence of matrices of
$(GL_{n}(\mathbf{R}))^{k}$ (respectively $(SL_{n}(\mathbf{R}))^{k}$)
satisfying $d((A_{m})_{m},V_{q})>\eta^{\prime}$ for every $q$, then for every
$R\geq R_{0}$, and every family $(v_{m})_{1\leq m\leq k}$ of vectors of
$\mathbf{R}^{n}$, we have

$\left|D_{R}^{+}\left(\big{(}\widehat{A}_{k}\circ\cdots\circ\widehat{A}_{1}\big{)}(\mathbf{Z}^{n})\right)-\det(A_{k}^{-1}\cdots
A_{1}^{-1})\overline{\tau}^{k}(A_{1},\cdots,A_{k})\right|<\frac{1}{\ell^{\prime}}$

(the density of the image set is “almost invariant” under perturbations by
translations), and for every $m\leq k$, we have151515Recall that
$(\mathbf{Z}^{n})^{\prime}$ stands for the set of points of $\mathbf{R}^{n}$
at least one coordinate of which belongs to $\mathbf{Z}+1/2$.

$D_{R}^{+}\left\\{x\in\big{(}A_{m}+v_{m}\big{)}(\mathbf{Z}^{n})\ \middle|\
d\big{(}x,(\mathbf{Z}^{n})^{\prime}\big{)}<\frac{1}{{c}\ell^{\prime}(2n+1)}\right\\}<\frac{1}{{c}\ell^{\prime}}$

(there is only a small proportion of the points of the image sets which are
obtained by discretizing points close to $(\mathbf{Z}^{n})^{\prime}$).

With the same proof as Theorem 33, Lemma 38 leads to the local-global formula
for $C^{r}$-diffeomorphisms (Theorem 28).

##  4\. Asymptotic rate of injectivity for a generic conservative
diffeomorphism

The goal of this section is to prove that the degree of recurrence of a
generic conservative $C^{1}$-diffeomorphism is equal to 0.

######  Theorem 39.

Let $r\in[1,+\infty]$. For a generic conservative diffeomorphism
$f\in\operatorname{Diff}^{r}(\mathbf{T}^{n},\operatorname{Leb})$, we have

$\lim_{k\to\infty}\tau^{k}(f)=0;$

more precisely, for every $\varepsilon>0$, the set of diffeomorphisms
$f\in\operatorname{Diff}^{r}(\mathbf{T}^{n},\operatorname{Leb})$ such that
$\lim_{t\to+\infty}\tau^{k}(f)<\varepsilon$ is open and dense.

In particular161616Using Equation (2) page 2., we have
$\lim_{N\to+\infty}D(f_{N})=0$.

It will be obtained by using the local-global formula (Theorem 28) and the
result about the asymptotic rate of injectivity of a generic sequence of
matrices (Theorem 20). The application of the linear results will be made
through Thom transversality arguments (Lemma 37).

###### Proof of theorem 39.

Let $\varepsilon>0$, $r\in[0,+\infty]$ and consider a generic element $f$ of
$\operatorname{Diff}(\mathbf{T}^{n},\operatorname{Leb})$. Applying the second
part of Theorem 20, one gets a collection of submanifolds $V_{q}$ of
$SL_{n}(\mathbf{R})$, which allow to define the set

$T_{\eta}=\left\\{y\in\mathbf{T}^{n}\mid\forall
q,\,d\big{(}Df_{y},V_{q}\big{)}\geq\eta\right\\}.$

Then, Birkhoff theorem (non-ergodic version) implies that the set
$T_{\eta}^{\infty}$ of points $y\in\mathbf{T}^{n}$ such that

$\limsup_{m\to+\infty}\frac{1}{m}\sum_{k=0}^{m-1}\mathbf{1}_{T_{\eta}}(f^{k}(x))\geq\frac{1}{2}$

has Lebesgue measure greater than $1-2\varepsilon$.

Now, Lemma 37 implies that as $f$ is a generic element of
$\operatorname{Diff}(\mathbf{T}^{n},\operatorname{Leb})$, there exists
$\eta>0$ such that $\operatorname{Leb}(T_{\eta})>1-\varepsilon$, in particular
$\operatorname{Leb}(T_{\eta}^{\infty})>1-\varepsilon$. Then, applying the
second part of Theorem 20, we get that for all $y\in T_{\eta}^{\infty}$, we
have
$\overline{\tau}^{\infty}\big{(}(Df_{f^{k}(y})_{k}\big{)}\leq\varepsilon$. In
particular, there exists $k_{0}\in\mathbf{N}$ and $T^{\prime}\subset
T_{\eta}^{\infty}$, with $\operatorname{Leb}(T^{\prime})\geq 1-3\varepsilon$
such that for all $y\in T^{\prime}$, we have
$\overline{\tau}^{k_{0}}\big{(}(Df_{f^{k}(y})_{k}\big{)}\leq\varepsilon$ (as
the sets of points $y\in T_{\eta}^{\infty}$, such that
$\overline{\tau}^{k}\big{(}(Df_{f^{k}(y})_{k}\big{)}\leq\varepsilon$ have
their increasing union over $k$ equal to $T_{\eta}^{\infty}$). Applying
Theorem 28, one gets that

$\displaystyle\tau^{k}(f)$
$\displaystyle\leq\int_{T^{\prime}}\overline{\tau}^{k}\left(Df_{x},\cdots,Df_{f^{k-1}(x)}\right)\,\operatorname{d}\operatorname{Leb}(x)+\int_{{T^{\prime}}^{\complement}}1\,\operatorname{d}\operatorname{Leb}(x)$
$\displaystyle\leq\varepsilon+3\varepsilon=4\varepsilon.$

∎

##  5\. Asymptotic rate of injectivity for a generic dissipative
diffeomorphism

Here we tackle the issue of the asymptotic rate of injectivity of generic
dissipative diffeomorphisms. Again, we will consider the torus
$\mathbf{T}^{n}$ equipped with Lebesgue measure $\operatorname{Leb}$ and the
canonical measures $E_{N}$, see Section A for a more general setting where the
result is still true. The study of the rate of injectivity for generic
dissipative diffeomorphisms is based on the following theorem of A. Avila and
J. Bochi.

######  Theorem 40 (Avila, Bochi).

Let $f$ be a generic $C^{1}$ maps of $\mathbf{T}^{n}$. Then for every
$\varepsilon>0$, there exists a compact set $K\subset\mathbf{T}^{n}$ and an
integer $m\in\mathbf{N}$ such that

$\operatorname{Leb}(K)>1-\varepsilon\qquad\text{and}\qquad\operatorname{Leb}(f^{m}(K))<\varepsilon.$

This statement is obtained by combining Lemma 1 and Theorem 1 of [AB06].

######  Remark 41.

As $C^{1}$ expanding maps of $\mathbf{T}^{n}$ and $C^{1}$ diffeomorphisms of
$\mathbf{T}^{n}$ are open subsets of the set of $C^{1}$ maps of
$\mathbf{T}^{n}$, the same theorem holds for generic $C^{1}$ expanding maps
and $C^{1}$ diffeomorphisms of $\mathbf{T}^{n}$ (this had already been proved
in the case of $C^{1}$-expanding maps by A. Quas in [Qua99]).

This theorem can be used to compute the asymptotic rate of injectivity of a
generic diffeomorphism.

######  Corollary 42.

The asymptotic rate of injectivity of a generic dissipative diffeomorphism
$f\in\operatorname{Diff}^{1}(\mathbf{T}^{n})$ is equal to 0. In particular,
the degree of recurrence $D(f_{N})$ of a generic dissipative diffeomorphism
tends to 0 when $N$ goes to infinity.

######  Remark 43.

The same statement holds for generic $C^{1}$ expanding maps.

###### Proof of Corollary 42.

The proof of this corollary mainly consists in stating what good properties
can be supposed to possess the compact set $K$ of Theorem 40. Thus, for $f$ a
generic diffeomorphism and $\varepsilon>0$, there exists $m>0$ and a compact
set $K$ such that $\operatorname{Leb}(K)>1-\varepsilon$ and
$\operatorname{Leb}(f^{m}(K))<\varepsilon$.

First of all, it can be easily seen that Theorem 40 is still true when the
compact set $K$ is replaced by an open set $O$: simply consider an open set
$O^{\prime}\supset f^{m}(K)$ such that
$\operatorname{Leb}(O^{\prime})<\varepsilon$ (by regularity of the measure)
and set $O=f^{-m}(O^{\prime})\supset K$. We then approach the set $O$ by
unions of dyadic cubes of $\mathbf{T}^{n}$: we define the cubes of order
$2^{M}$ on $\mathbf{T}^{n}$

$C_{M,i}=\prod_{j=1}^{n}\left[\frac{i_{j}}{2^{M}},\frac{i_{j}+1}{2^{M}}\right],$

and set

$U_{M}=\operatorname{Int}\left(\overline{\bigcup_{C_{M,i}\subset
O}C_{M,i}}\right),$

where $\operatorname{Int}$ denotes the interior. Then, the union
$\bigcup_{M\in\mathbf{N}}U_{M}$ is increasing in $M$ and we have
$\bigcup_{M\in\mathbf{N}}U_{M}=O$. In particular, there exists
$M_{0}\in\mathbf{N}$ such that $\operatorname{Leb}(U_{M_{0}})>1-\varepsilon$,
and as $U_{M_{0}}\subset O$, we also have
$\operatorname{Leb}(f^{m}(U_{M_{0}}))<\varepsilon$. We denote $U=U_{M_{0}}$.
Finally, as $U$ is a finite union of cubes, and as $f$ is a diffeomorphism,
there exists $\delta>0$ such that the measure of the $\delta$-neighbourhood of
$f^{m}(U)$ is smaller than $\varepsilon$. We call $V$ this
$\delta$-neighbourhood.

As $U$ is a finite union of cubes, there exists $N_{0}\in\mathbf{N}$ such that
if $N\geq N_{0}$, then the proportion of points of $E_{N}$ which belong to $U$
is bigger than $1-2\varepsilon$, and the proportion of points of $E_{N}$ which
belong to $V$ is smaller than $2\varepsilon$. Moreover, if $N_{0}$ is large
enough, then for every $N\geq N_{0}$, and for every $x_{N}\in E_{N}\cap U$, we
have $f_{N}^{m}(x_{N})\in V$. This implies that

$\frac{\operatorname{Card}(f_{N}^{m}(E_{N}))}{\operatorname{Card}(E_{N})}\leq
4\varepsilon,$

which proves the corollary. ∎

##  6\. Asymptotic rate of injectivity of a generic expanding map

In this section, we prove that the asymptotic rate of injectivity of a generic
expanding map is equal to 0. Note that a local version of this result was
already obtained by P.P. Flockermann in his thesis (Corollary 2 page 69 and
Corollary 3 page 71 of [Flo02]), stating that for a generic $C^{1+\alpha}$
expanding map $f$ of the circle, the “local asymptotic rate of injectivity” is
equal to 0 almost everywhere. Some of his arguments will be used in this
section. Note also that in $C^{1}$ regularity, the equality
$\tau^{\infty}(f)=0$ for a generic $f$ is a consequence of Theorem 40 of A.
Avila and J. Bochi (see also Corollary 42); the same theorem even proves that
the asymptotic rate of injectivity of a generic $C^{1}$ endomorphism of the
circle is equal to 0.

######  Definition 44.

We define $Z_{m}$ as the number of children at the $m$-th generation in
$G_{f,y}$ (see Definition 32).

######  Proposition 45.

For every $r\in]1,+\infty]$, for every $f\in\mathcal{D}^{r}(\mathbf{S}^{1})$
and every $y\in\mathbf{S}^{1}$, we have

$\mathbf{P}(Z_{m}>0)\underset{m\to+\infty}{\longrightarrow}0.$

Equivalently,

$\overline{D}\big{(}(\det Df_{x}^{-1})_{\begin{subarray}{l}1\leq m\leq k\\\
x\in f^{-m}(y)\end{subarray}}\big{)}\underset{k\to+\infty}{\longrightarrow}0.$

######  Lemma 46.

The expectation of $Z_{m}$ satisfies

$\mathbf{E}(Z_{m})=(\mathcal{L}^{m}1)(y),$

where $\mathcal{L}$ is the Ruelle-Perron-Frobenius associated to $f$ and $1$
denotes the constant function equal to 1 on $\mathbf{S}^{1}$. In particular,
there exists a constant $\Sigma_{0}>0$ such that
$\mathbf{E}(Z_{m})\leq\Sigma_{0}$ for every $m\in\mathbf{N}$.

The second part of the lemma is deduced from the first one by applying the
theorem stating that for every $C^{r}$ expanding map $f$ of $\mathbf{S}^{1}$
($r>1$), the maps $\mathcal{L}^{m}1$ converge uniformly towards a Hölder map,
which is the density of the unique SRB measure of $f$ (see for example
[FJ03]). The first assertion of the lemma follows from the convergence of the
operators $f_{N}^{*}$ acting on $\mathcal{P}$ (the space of Borel probability
measures) towards the Ruelle-Perron-Frobenius operator.

######  Definition 47.

The _transfer operator_ associated to the map $f$ (usually called Ruelle-
Perron-Frobenius operator), which acts on densities of probability measures,
will be denoted by $\mathcal{L}_{f}$. It is defined by

$\mathcal{L}_{f}\phi(y)=\sum_{x\in f^{-1}(y)}\frac{\phi(x)}{f^{\prime}(x)}.$

Lemma 46 follows directly from the following lemma.

######  Lemma 48.

Denoting $\operatorname{Leb}_{N}$ the uniform measure on $E_{N}$, for every
$C^{1}$ expanding map of $\mathbf{S}^{1}$ and every $m\geq 0$, we have
convergence of the measures $(f_{N}^{*})^{m}(\lambda_{N})$ towards the measure
of density $\mathcal{L}_{f}^{m}1$ (where $1$ denotes the constant function
equal to 1).

The proof of this lemma is straightforward but quite long. We sketch here this
proof, the reader will find a complete proof using generating functions in
Section 3.4 of [Flo02] and a quantitative version of it in Section 12.2 of
[Gui15a].

###### Sketch of proof of Lemma 48.

As $f$ is $C^{1}$, by the mean value theorem, for every segment $I$ small
enough, we have

$\left|\operatorname{Leb}(I)-\frac{\operatorname{Leb}(f(I))}{f^{\prime}(x_{0})}\right|\leq\varepsilon.$

Moreover, for every interval $J$,

$\left|\operatorname{Leb}(J)-\frac{\operatorname{Card}(J\cap
E_{N})}{\operatorname{Card}(E_{N})}\right|\leq\frac{1}{N}.$

These two inequalities allows to prove the local convergence of the measures
$f_{N}^{*}(\lambda_{N})$ towards the measure with density $\mathcal{L}_{f}1$.
The same kind of arguments holds in arbitrary times, and allow to prove the
lemma. ∎

###### Proof of Proposition 45.

We fix $\varepsilon>0$, and set $K=\lceil\Sigma_{0}/\varepsilon\rceil$ (the
constant $\Sigma_{0}$ being given by Lemma 46) and

$a_{m}=\mathbf{P}(Z_{m}=0)\,,\quad b_{m}=\mathbf{P}(0<Z_{m}\leq K)\,,\quad
c_{m}=\mathbf{P}(Z_{m}>K).$

$c_{m}\leq\varepsilon$$b_{m}$$a_{m}$$\geq\alpha$ Figure 11. Transition graph
for $Z_{m}$: $a_{m}=\mathbf{P}(Z_{m}=0)$, $b_{m}=\mathbf{P}(0<Z_{m}\leq K)$,
$c_{m}=\mathbf{P}(Z_{m}>K)$.

We want to prove that the sequence $(a_{m})_{m\in\mathbf{N}}$ tends to 1.

Of course, $a_{m}+b_{m}+c_{m}=1$ for any $m$. We then remark that a generation
with less than $K$ children will give birth to zero child with positive
probability: we have the inequality

$\mathbf{P}(Z_{m+1}=0\mid 0<Z_{m}\leq
K)\geq\left(1-\frac{1}{\|f^{\prime}\|_{\infty}}\right)^{dK}.$

In other words, setting $\alpha=(1-\|f^{\prime}\|_{\infty}^{-1})^{dK}$, we get
$a_{m+1}\geq a_{m}+\alpha b_{m}$ (see also Figure 11).

Furthermore, by Markov inequality and Lemma 46, we have

$\mathbf{P}(Z_{m}\geq\Sigma_{0}/\varepsilon)\leq\varepsilon,$

so $c_{m}\leq\varepsilon$.

In summary, we have

$\left\\{\begin{array}[]{l}a_{m}+b_{m}+c_{m}=1\\\ c_{m}\leq\varepsilon\\\
a_{m+1}\geq a_{m}+\alpha b_{m}.\end{array}\right.$

An easy computation leads to
$a_{m+1}\geq(1-\alpha)a_{m}+\alpha(1-\varepsilon)$, which implies that
$\liminf a_{m}\geq 1-\varepsilon$. As this holds for any $\varepsilon>0$, we
get that $\lim a_{m}=1$. ∎

######  Corollary 49.

For a generic map $f\in\mathcal{D}^{r}(\mathbf{S}^{1})$, we have
$\tau^{\infty}(f)=0$. In particular, $\lim_{N\to+\infty}D(f_{N})=0$.

###### Proof of Corollary 49.

It is an easy consequence of the local-global formula (Theorem 33),
Proposition 45 and the dominated convergence theorem. ∎

##  7\. Numerical simulations

Figure 12. Simulation of the degree of recurrence $D(f_{N})$ of the
conservative diffeomorphism $f$, depending on $N$, on the grids $E_{N}$ with
$N=128k$, $k=1,\cdots,150$. Figure 13. Simulation of the degree of recurrence
$D(g_{N})$ of the expanding map $g$, depending on $N$, on the grids $E_{N}$
with $N=128k$, $k=1,\cdots,1\,000$.

We have computed numerically the degree of recurrence of a diffeomorphism $f$,
which is $C^{1}$-close to $\operatorname{Id}$. It is defined by $f=Q\circ P$,
with

$P(x,y)=\big{(}x,y+p(x)\big{)}\quad\text{and}\quad
Q(x,y)=\big{(}x+q(y),y\big{)},$ $p(x)=\frac{1}{209}\cos(2\pi\times
17x)+\frac{1}{271}\sin(2\pi\times 27x)-\frac{1}{703}\cos(2\pi\times 35x),$
$q(y)=\frac{1}{287}\cos(2\pi\times 15y)+\frac{1}{203}\sin(2\pi\times
27y)-\frac{1}{841}\sin(2\pi\times 38y).$

On Figure 12, we have represented graphically the quantity $D(f_{128k})$ for
$k$ from 1 to $150$. It appears that, as predicted by Theorem 39, this degree
of recurrence goes to 0. In fact, it is even decreasing, and converges quite
fast to 0: as soon as $N=128$, the degree of recurrence is smaller than $1/2$,
and if $N\gtrsim 1000$, then $D(f_{N})\leq 1/10$. Note that, contrary to what
is predicted by theory, this phenomenon was already observed for examples of
conservative homeomorphisms of the torus which have big enough derivatives not
to be considered as “typical from the $C^{1}$ case” (see [Gui15b]).

We also present the results of the numerical simulation we have conducted for
the degree of recurrence of the expanding map of the circle $g$, defined by

$g(x)=2x+\varepsilon_{1}\cos(2\pi x)+\varepsilon_{2}\sin(6\pi x),$

with $\varepsilon_{1}=0.127\,943\,563\,72$ and
$\varepsilon_{2}=0.008\,247\,359\,61$.

On Figure 13, we have represented the quantity $D(g_{128k})$ for $k$ from 1 to
$1\,000$. It appears that, as predicted by Corollary 49, this degree of
recurrence seems to tend to 0. In fact, it is even decreasing, and converges
quite fast to 0: as soon as $N=128$, the degree of recurrence is smaller than
$1/5$, and if $N\gtrsim 25\,000$, then $D(g_{N})\leq 1/50$.

##  Appendix A A more general setting where the theorems are still true

Here, we give weaker assumptions under which the theorems of this paper are
still true: the framework “torus $\mathbf{T}^{n}$ with grids $E_{N}$ and
Lebesgue measure” could be seen as a little too restrictive.

So, we take a compact smooth manifold $M$ (possibly with boundary) and choose
a partition $M_{1},\cdots,M_{k}$ of $M$ into closed sets171717That is,
$\bigcup_{i}M_{i}=M$, and for $i\neq j$, the intersection between the
interiors of $M_{i}$ and $M_{j}$ are empty. with smooth boundaries, such that
for every $i$, there exists a chart $\varphi_{i}:M_{i}\to\mathbf{R}^{n}$. We
endow $\mathbf{R}^{n}$ with the euclidean distance, which defines a distance
on $M$ _via_ the charts $\phi_{i}$ (this distance is not necessarily
continuous). From now, we study what happens on a single chart, as what
happens on the neighbourhoods of the boundaries of these charts “counts for
nothing” from the Lebesgue measure viewpoint.

Finally, we suppose that the uniform measures on the grids
$E_{N}=\bigcup_{i}E_{N,i}$ converge to a smooth measure $\lambda$ on $M$ when
$N$ goes to infinity.

This can be easily seen that these conditions are sufficient for Corollary 42
to be still true.

For the rest of the statements of this paper, we need that the grids behave
locally as the canonical grids on the torus.

For every $i$, we choose a sequence $(\kappa_{N,i})_{N}$ of positive real
numbers such that $\kappa_{N,i}\underset{N\to+\infty}{\longrightarrow}0$. This
defines a sequence $E_{N,i}$ of grids on the set $M_{i}$ by
$E_{N,i}=\varphi_{i}^{-1}(\kappa_{N,i}\mathbf{Z}^{n})$. Also, the canonical
projection $\pi:\mathbf{R}^{n}\to\mathbf{Z}^{n}$ (see Definition 6) allows to
define the projection $\pi_{N,i}$, defined as the projection on
$\kappa_{N,i}\mathbf{Z}^{n}$ in the coordinates given by $\varphi_{i}$:

$\begin{array}[]{rcl}\pi_{N,i}:&M_{i}&\longrightarrow E_{N,i}\\\
&x&\longmapsto\varphi_{i}^{-1}\Big{(}\kappa_{N,i}\pi\big{(}\kappa_{N,i}^{-1}\varphi_{i}(x)\big{)}\Big{)}.\end{array}$

We easily check that under these conditions, Theorems 28, 33 and 39 and
Corollary 49 are still true, that is if we replace the torus $\mathbf{T}^{n}$
by $M$, the uniform grids by the grids $E_{N}$, the canonical projections by
the projections $\pi_{N,i}$, and Lebesgue measure by the measure $\lambda$.

## References

  * [AA13] F. Abdenur et M. Andersson – “Ergodic theory of generic continuous maps”, _Comm. Math. Phys._ 318 (2013), no. 3, p. 831–855.
  * [AB06] A. Avila et J. Bochi – “A generic $C^{1}$ map has no absolutely continuous invariant probability measure”, _Nonlinearity_ 19 (2006), no. 11, p. 2717–2725.
  * [DF92] F. Dyson et H. Falk – “Period of a discrete cat mapping”, _Amer. Math. Monthly_ 99 (1992), no. 7, p. 603–614.
  * [FJ03] A. Fan et Y. Jiang – “Spectral theory of transfer operators”, Complex dynamics and related topics: lectures from the Morningside Center of Mathematics, New Stud. Adv. Math., vol. 5, Int. Press, Somerville, MA, 2003, p. 63–128.
  * [Flo02] P. P. Flockermann – “Discretizations of expanding maps”, Thèse, ETH (Zurich), 2002.
  * [Fur36] P. Furtwängler – “Über Gitter konstanter Dichte”, _Monatsh. Math. Phys._ 43 (1936), no. 1, p. 281–288.
  * [Ghy94] E. Ghys – “Variations autour du théorème de récurrence de Poincaré”, 1994, Republié en 2006 dans “L’héritage scientifique de Henri Poincaré”, Belin.
  * [Gui15a] P.-A. Guihéneuf – “Discrétisations spatiales de systèmes dynamiques génériques”, Thèse, Université Paris-Sud, 2015.
  * [Gui15b] by same author, “Dynamical properties of spatial discretizations of a generic homeomorphism”, _Ergodic Theory Dynam. Systems_ 35 (2015), no. 5, p. 1474–1523.
  * [Gui15c] by same author, “Model sets, almost periodic patterns, uniform density and linear maps”, to appear in Revista MatemÃ¡tica Iberoamericana, arXiv:1512.00650, 2015\.
  * [Gui15d] by same author, “Physical measures of discretizations of generic diffeomorphisms”, to appear in Ergodic Theory and Dynamical Systems, arXiv:1510.00720, 2015.
  * [Gui16] by same author, “Discretizations of isometries”, _Discrete Geometry for Computer Imagery: 19th IAPR International Conference, DGCI 2016, Nantes, France, April 18-20, 2016. Proceedings_ (N. Normand, J. Guédon et F. Autrusseau, éds.), Springer International Publishing, 2016, p. 71–92.
  * [Haj41] G. Hajós – “Über einfache und mehrfache Bedeckung des $n$-dimensionalen Raumes mit einem Würfelgitter”, _Math. Z._ 47 (1941), p. 427–467.
  * [Kel30] O. H. Keller – “Über die lückenlose Erfüllung des Raumes mit Würfeln.”, _J. Reine Angew. Math._ 163 (1930), p. 231–248 (German).
  * [Lax71] P. Lax – “Approximation of measure preserving transformations”, _Comm. Pure Appl. Math._ 24 (1971), p. 133–135.
  * [LS92] J. C. Lagarias et P. W. Shor – “Keller’s cube-tiling conjecture is false in high dimensions”, _Bull. Amer. Math. Soc. (N.S.)_ 27 (1992), no. 2, p. 279–283.
  * [Mac02] J. Mackey – “A cube tiling of dimension eight with no facesharing”, _Discrete Comput. Geom._ 28 (2002), no. 2, p. 275–279.
  * [Mey12] Y. Meyer – “Quasicrystals, almost periodic patterns, mean-periodic functions and irregular sampling”, _Afr. Diaspora J. Math._ 13 (2012), no. 1, p. 1–45.
  * [Mie05] T. Miernowski – “Dynamique discrï¿½tisï¿½e et stochastique, gï¿½omï¿½trie conforme”, Thèse, ÉNS de Lyon, 2005.
  * [Moo00] R. Moody – “Model sets: A survey”, _From Quasicrystals to More Complex Systems_ , vol. 13, Centre de Physique des Houches, 2000, p. 145–166.
  * [OU41] J. Oxtoby et S. Ulam – “Measure-preserving homeomorphisms and metrical transitivity”, _Ann. of Math._ 42 (1941), no. 2, p. 874–920.
  * [Per40a] O. Perron – “Über lückenlose Ausfüllung des $n$-dimensionalen Raumes durch kongruente Würfel”, _Math. Z._ 46 (1940), p. 1–26.
  * [Per40b] by same author, “Über lückenlose Ausfüllung des $n$-dimensionalen Raumes durch kongruente Würfel. II”, _Math. Z._ 46 (1940), p. 161–180.
  * [Qua99] A. Quas – “Most expanding maps have no absolutely continuous invariant measure”, _Studia Math._ 134 (1999), no. 1, p. 69–78.
  * [Rob79] R. M. Robinson – “Multiple tilings of $n$-dimensional space by unit cubes”, _Math. Z._ 166 (1979), no. 3, p. 225–264.
  * [SS94] S. K. Stein et S. Szabó – _Algebra and tiling_ , Carus Mathematical Monographs, vol. 25, Mathematical Association of America, Washington, DC, 1994, Homomorphisms in the service of geometry.