# An alternative approach to the discrete Shnirelman’s inequality

Martina Zizza, 111Max Planck Institute for Mathematics in the Sciences
<EMAIL_ADDRESS>
(12 July 2024)

###### Abstract

In this paper we examine the discrete Shnirelman’s inequality [8], which
relates the $L^{2}$-distance of two discrete configurations of a fluid to the
$L^{1}_{t}L^{2}_{x}$-norm of the vector field connecting them. Our proof is
inspired by [8], where it was obtained $\alpha=\frac{1}{64}$ in dimension
$\nu=2$, while here we get $\alpha\geq\frac{2}{7}$. Moreover we prove that
$\alpha\geq\frac{1}{\nu+1}$ for any dimension $\nu\geq 3$. We point out that,
even if this does not improve the bound in the continuous version, where it
was proved that $\alpha\geq\frac{2}{4+\nu}$, with $\nu\geq 3$, our bound is
the best one achieved for the $2$-dimensional case. Our method uses an
alternative approach based on volume estimates of permutations, which count
the number of maximum cubes that are moved by a permutation $P$.

Key words: fluid flows, group of volume-preserving diffeomorphisms, action
functional.

MSC2020: 76B75.

##  1 Introduction

We consider the motion of an ideal incompressible fluid in a vessel $M$, which
is a bounded region of $\mathbb{R}^{\nu}$ (with Euclidean volume element
$dx$). A configuration of the fluid at time $t\in\mathbb{R}$ is a volume-
preserving diffeomorphism $\xi_{t}:M\rightarrow M$: for each particle $x\in
M$, $\xi_{t}(x)\in M$ denotes the position reached by the particle $x\in M$ at
time $t$ and $t\rightarrow\xi_{t}(x)$ is the _trajectory_ of the fluid
particle. Observe that each two configurations differ by some _permutation_ of
fluid particles. The configuration space of an ideal incompressible fluid is
the set of all configurations of the fluid particles: namely, the group (under
composition) of the volume-preserving diffeomorphisms, that we will denote by
$\mathcal{D}(M)$ (in the literature this is also denoted by
$\text{Sdiff}(M)$). We introduce a metric on the group $\mathcal{D}(M)$ as
follows: we consider a piecewise smooth path $t\rightarrow\xi_{t}$ in
$\mathcal{D}(M)$, and for $t_{1}\leq t\leq t_{2}$ we associate to the path its
_length_

$\mathcal{\ell}\\{\xi_{t}\\}_{t_{1}}^{t_{2}}=\int_{t_{1}}^{t_{2}}\|\dot{\xi}_{t}\|_{L^{2}(M)}dt.$
(1.1)

For every two configurations $f,g\in\mathcal{D}(M)$ we can define a _distance_
between them on $\mathcal{D}(M)$ as the infimum of the lengths of all paths
connecting $f,g$, that is:

$\text{dist}_{\mathcal{D}(M)}(f,g)=\underset{\xi_{t_{1}}=f,\xi_{t_{2}}=g}{\inf_{\\{\xi_{t}\\}\subset\mathcal{D}(M),}}\ell\\{\xi_{t}\\}_{0}^{1}.$
(1.2)

The space $\mathcal{D}(M)$ endowed with the metric
$\text{dist}_{\mathcal{D}(M)}$ is a metric space. In what follows, we will
study the case $M=[0,1]^{\nu}$ avoiding topological issues of the set $M$.

The first observation is that the space $\mathcal{D}(M)$ is naturally embedded
in the space $L^{2}(M,\mathbb{R}^{\nu})$ of vector functions on $M$.
Therefore, for every two configurations $f,g\in\mathcal{D}(M)$ we can consider
the distance $\|f-g\|_{L^{2}(M)}$ and study the comparison of the metric
$\|\cdot\|_{L^{2}}$ with $\text{dist}_{\mathcal{D}(M)}$. It is immediate to
see that

$\|f-g\|_{L^{2}(M)}\leq\text{dist}_{\mathcal{D}(M)}(f,g),$

therefore, the natural question arising in this context is if it possible to
estimate $\text{dist}_{\mathcal{D}(M)}$ with the $L^{2}$-distance. In [9] the
following theorem is proved.

######  Theorem 1.1 (Shnirelman’s inequality [9]).

Let us fix $\nu\geq 3$ and $M=[0,1]^{\nu}$, then there exists $C>0$ and
$\alpha\geq\frac{2}{\nu+4}$ such that, for every $f,g\in\mathcal{D}(M)$,

$\text{dist}_{\mathcal{D}(M)}(f,g)\leq C\|f-g\|_{L^{2}(M)}^{\alpha}.$ (1.3)

This has been obtained via the concept of Generalized Flows (see also [5]).
The theorem is valid in $\nu\geq 3$, but no such inequality can be obtained in
dimension $\nu=2$ due to topological issues. In particular, it can be proved
that for every pair of positive constants $c,C$ there exists a diffeomorphism
$g\in\mathcal{D}([0,1]^{2})$ such that
$dist_{\mathcal{D}([0,1]^{2})}(g,Id)>C$, but $\|g-Id\|_{2}\leq c$ (see as a
reference [2]).

In [8] an alternative proof to Theorem 1.1 was given, in the discrete setting
of permutations. Fix $N\in\mathbb{N}$ and consider a tiling $\mathcal{R}_{N}$
of the cube $[0,1]^{\nu}$ into $N^{\nu}$ cubes of the same size. The discrete
approach is based onto the following well-known fact: the permutations of
cubes on a tiling $\mathcal{R}_{N}$ of $[0,1]^{\nu}$ (i.e. a subdivision of
$[0,1]^{\nu}$ into $N^{\nu}$ identical subcubes) approximate every element of
$\mathcal{D}([0,1]^{\nu})$ with respect to the $L^{2}$-norm (see for example
[7]).

Then Shnirelman proved that:

######  Theorem 1.2 (Discrete Shnirelman’s inequality).

Let $\nu=2$, then there exists a positive constant $C>0$ and
$\alpha\geq\frac{1}{64}$ such that, for every $N\in\mathbb{N}$, for every
$P,Q$ permutations of the tiling $\mathcal{R}_{N}$, it holds

$\text{dist}_{\mathcal{D}_{N}}(P,Q)\leq C\|P-Q\|_{2}^{\alpha}.$ (1.4)

We will see in a while that $\text{dist}_{\mathcal{D}_{N}}$ is the discrete
version of (1.2), and it is related to the swap distance of permutations [10].
In the present paper we will focus on the discrete Shnirelman inequality,
improving the bound in dimension $\nu=2$ and obtaining the bound for any
dimension. Our result reads as follows:

######  Theorem 1.3 (Improved discrete Shnirelman’s inequality).

Let $\nu\geq 3$, then there exists a positive constant $C=C(\nu)>0$, and
$\alpha\geq\frac{1}{1+\nu}$ such that, for every $N\in\mathbb{N}$, for every
$P,Q$ permutations of some tiling $\mathcal{R}_{N}$ of $[0,1]^{\nu}$, it holds

$\text{dist}_{\mathcal{D}_{N}}(P,Q)\leq C\|P-Q\|_{2}^{\alpha}.$ (1.5)

Moreover, if $\nu=2$, $\alpha$ can be chosen to be $\alpha\geq\frac{2}{7}.$

We point out that, while a good bound of $\alpha$ in the discrete setting
implies the same bound in the continuous one (for dimension greater than $3$,
see also [2]), we do not know if the converse holds true, thus the role of the
present paper is to approach the bound of the continuous case in the discrete
context. Moreover, the discretized setting has an independent interest, since
it is related to the theory of Cayley Graphs associated to transposition trees
[6].

###  1.1 The discrete setting

Here we introduce the discretized setting and the notion of discrete flows,
first in the formulation of [8]. We denote by $\mathcal{D}_{N}$ the group of
permutations of the tiling $\mathcal{R}_{N}$. We present Shnirelman’s notion
of elementary movements (that we will call here $S$-elementary movements)
together with the definition of the discrete length functional, then we will
point out the difference with our approach.

######  Definition 1.4 (Swap).

Let $\kappa_{1},\kappa_{2}\in R_{N}$ be two adjacent subcubes of the tiling
$\mathcal{R}_{N}$ and denote by $x_{1}=c(\kappa_{1}),x_{2}=c(\kappa_{2})$
their respective centers. A swap between $\kappa_{1},\kappa_{2}$ is a map
$T:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ defined as follows:

$T(x)=\begin{cases}x+x_{2}-x_{1}\quad\text{ if }x\in\text{int}(\kappa_{1}),\\\
x+x_{1}-x_{2}\quad\text{ if }x\in\text{int}(\kappa_{2}),\\\
x\quad\text{otherwise}.\end{cases}$ (1.6)

See Figure LABEL:fig:trasp.

######  Definition 1.5 (S-elementary movement).

A S-elementary movement is a measure-preserving map
$S:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ with the following property: there exist
$T_{1},\dots,T_{j}$ swaps, respectively of the couples of adjacent subcubes
$(\kappa^{1}_{1},\kappa^{1}_{2}),\dots,(\kappa^{j}_{1},\kappa^{j}_{2})$, with

$\text{int}(\kappa^{h}_{1}\cup\kappa^{h}_{2})\cap\text{int}(\kappa^{k}_{1}\cup\kappa^{k}_{2})=\emptyset,\quad
h\not=k,$

and

$S=T_{j}\circ T_{j-1}\circ\dots T_{2}\circ T_{1}.$

In particular, a $S$-elementary movement is a map that swaps simultaneously
couples of adjacent cubes. Given a $S$-elementary movement with
$S=T_{j}\circ\dots T_{1}$, we denote the number of simultaneous swaps of $S$
(that is, the number of couples that are swapped simultaneously) by
$\text{swap}(S)=j$.

Here, a _$S$ -discrete flow_ (sometimes they are called discrete flows in
literature, but we will use this notation to distinguish them from the ones we
will use later) is a finite sequence $\\{S_{k}\\}_{k=1}^{\mathcal{T}}$ with
$S_{k}$ $S$-elementary movement for every $k=1,2,\dots,\mathcal{T}$. Let
$P,Q:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ be two permutations (Definition 2.2).
We say that $P$ is sent into $Q$ by the discrete flow
$\\{S_{k}\\}_{k=1}^{\mathcal{T}}$ if

$S_{\mathcal{T}}\circ S_{\mathcal{T}-1}\circ\dots S_{2}\circ S_{1}\circ P=Q.$

In this case we say that the discrete flow $\\{S_{j}\\}_{j=1}^{\mathcal{T}}$
_connects_ the two permutations $P,Q$. In particular, the _discretised length
functional_ (which is the discrete counterpart of (1.1)), that quantifies the
cost for connecting $P$ to $Q$, is

$L_{S}(P,Q)=L_{S}\\{{S_{j}}\\}_{j=1}^{\mathcal{T}}=\sum_{j=1}^{\mathcal{T}}N^{-1-\frac{\nu}{2}}\sqrt{\text{swap}(S_{j})}.$
(1.7)

Finally, we define the _discrete distance_ on the space $\mathcal{D}_{N}$ as

$\text{dist}^{S}_{\mathcal{D}_{N}}(P,Q)=\underset{\text{connecting }P\text{ to
}Q}{\min_{\\{S_{j}\\}_{j=1}^{\mathcal{T}}}}L_{S}\\{S_{j}\\}_{j=1}^{\mathcal{T}}.$
(1.8)

The reason for such definition of the length is transparent: a vector field
that swaps two adjacent cubes has magnitude $\sim N^{-1}$ (sidelength of the
cubes) and it is supported on a volume $\sim N^{-\nu}$ (see for more details
Subsection 2.2).

Our strategy proposes the definition of a new length functional, together with
new elementary movements and discrete flow. We try to explain the heuristics
of our approach and to show that the new distance function we obtain is
equivalent to the one chosen in [8], nonetheless it allows for more
straightforward computations and concrete improvements in the inequality
(1.3), at least in the discretized context. We remark that, for the sake of
brevity, we are not putting the definitions of all objects in the
introduction, since they can be found in Section 2.

######  Definition 1.6.

Let $A=[\kappa_{1}\kappa_{2}\dots\kappa_{\ell(A)}]\subset\mathcal{R}_{N}$ be
an array of length $\ell(A)$, and let $P\in\mathcal{D}_{N}$ be a permutation
of the array $A$. Let $\kappa_{i_{1}}$, $\kappa_{j_{1}}$, with $j_{1}\leq
i_{1}\leq\ell(A)$, be two subcubes of the array. We say that
$(\kappa_{i_{1}},\kappa_{j_{1}})$ is a _swapping couple_ for the permutation
$P$ if

$P(x)=\begin{cases}x+c(\kappa_{i_{1}})-c(\kappa_{j_{1}}),\quad
x\in\text{int}(\kappa_{j_{1}}),\\\ x+c(\kappa_{j_{1}})-c(\kappa_{i_{1}}),\quad
x\in\text{int}(\kappa_{i_{1}}),\\\ x\quad\text{otherwise},\end{cases}$

where $c(\kappa)$ denotes the center of the cube $\kappa$.

Here we point out that an array $A$ is a collection of $\ell(A)$ cubes along a
line. The notion of swapping couples extends the notion of adjacent cubes, so
that we can consider swaps of distant cubes (in this case, the permutation $P$
of the previous definition).

######  Definition 1.7.

Let $A=[\kappa_{1}\kappa_{2}\dots\kappa_{\ell(A)}]\subset\mathcal{R}_{N}$ be
an array of length $\ell(A)$. A _sequence of swapping couples_ in $A$ is a
subset $\\{\kappa_{i_{j}}\\}\subset A$ with $j=1,\dots,2M\leq\ell(A)$, and

$i_{1}\leq i_{2}\leq\dots\leq i_{2M},$
$(\kappa_{i_{j}},\kappa_{i_{2M-j+1}})\qquad\text{swapping couple},\quad\forall
j=1,\dots,M.$

######  Definition 1.8 (Elementary Movement).

An elementary movement is a map $Z:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ such
that there exist $A_{1},\dots,A_{m}$ disjoint arrays with the following
properties: for every $1\leq i\leq m$, if
$(\kappa_{i_{1}},\kappa_{j_{1}}),\dots,(\kappa_{i_{h(i)}},\kappa_{j_{h(i)}})$
denote a sequence of swapping couples of the array $A_{i}$ (Definition 2.18),
then

$Z(x)=\begin{cases}x+c(\kappa_{i_{\ell}})-c(\kappa_{j_{\ell}}),\quad\forall
x\in\text{int}(\kappa_{j_{\ell}}),\quad\forall i,\quad\forall 1\leq\ell\leq
h(i),\\\ x+c(\kappa_{j_{\ell}})-c(\kappa_{i_{\ell}}),\quad\forall
x\in\text{int}(\kappa_{i_{\ell}}),\quad\forall i,\quad\forall 1\leq\ell\leq
h(i),\\\ x\quad\text{otherwise},\end{cases}$

where $c(\kappa)$ denotes the center of the cube $\kappa$.

If $Z$ is an elementary movement and $A_{1},\dots,A_{m}$ are the arrays of the
previous definition, then its cost
$L:\mathcal{Z}_{N}\rightarrow\mathbb{R}_{+}$ can be computed as follows:

$L(Z)=\max_{i}\ell(A_{i})N^{-1-\frac{\nu}{2}}\sqrt{\sum_{i=1}^{m}h(i)},$ (1.9)

where we recall that $\ell(A_{i})$ is the length of the array $A_{i}$, for
every $i$.

Finally, one proceeds as before in the definition of the discrete distance. In
Subsection 2.2 we prove that the two distances are equivalent. The advantage
of this definition is that this distance quantifies that the real cost depends
only on the amount of couples that have to be swapped, times the size of the
array. The cubes that should not be swapped do not count. In some sense this
functional quantifies the fact that a cube can travel along the array without
affecting the other cubes: see Figure 1.

Figure 1: A particle follows the red trajectory to reach the distant cube,
travelling along pipes, and its flow does not affect all the intermediate
cubes.

This observation allows to implement a different scheme in order to quantify
the cost functional. We point out that the discrete flow we propose here has
also a velocity field counterpart, and its construction is given in the
appendix for completeness, at least for a single swapping couple, but it is
not relevant for the present work.

With this tool at hand, we take inspiration from the proof of [8]. Clearly,
since our method is based on the quantification of cubes that need to be
swapped at each time step, our proof is based on volume estimates (under the
constraint of the $L^{2}$-norm).

####  1.1.1 Proof of discrete Shnirelman’s inequality.

Here we give a brief summary of the proof of the improved discrete
Shnirelman’s inequality. The proof is based onto three steps (Proposition 3.6,
Theorem 3.9, Theorem 3.14). Our proof is inspired by the one in [8], but
proposes alternative versions of the steps (the main differences are in
Theorem 3.9) where a different analysis was required) that fit with the new
definition of the discrete length functional. Moreover, all our constructions
are explicit.

Given a permutation $P$ of the tiling $\mathcal{R}_{N}$ of the
$\nu$-dimensional unit cube, we assume that $P$ is _$\delta$ -close_ to $Id$
in the $L^{2}$-norm, namely $\|P-Id\|_{2}\leq\delta$, where $\delta<<1$. Fix
$0<\epsilon\leq\frac{2}{2+\nu}$ (it will be clear in Section 3 why we ask for
such a condition).

  * Step 1)

Call white those cubes such that $|P(\kappa)-\kappa|\leq\delta^{\epsilon}$,
and black the other ones. Since $\|P-Id\|_{2}\leq\delta$, we can quantify the
maximum amount of black cubes (first volume estimate). Then we perform a flow
that moves the black cubes to their original position. As a result we get

######  Proposition 1.9.

Let $P\in\mathcal{D}_{N}$ chosen as above. Then there exist two positive
constants $C=C(\nu)>0,D=D(\nu)>0$ and a permutation
$\tilde{P}\in\mathcal{D}_{N}$ such that:

    * –

$\|\tilde{P}-Id\|_{2}\leq C\delta^{1-\frac{\epsilon}{2}}$;

    * –

for every $\kappa\in\mathcal{R}_{N}$, $|\tilde{P}(\kappa)-\kappa|\leq
D{\delta}^{\epsilon}$.

Moreover, the cost for connecting $P$ to $\tilde{P}$ is estimated by

$L(P,\tilde{P})\lesssim\delta^{1-\epsilon}.$ (1.10)

We point out that the cost is given up to a positive constant depending only
on the dimension $\nu$. Moreover, we have that it is possible to give a
concrete estimate of the $L^{2}$-norm of the new permutation $\tilde{P}$,
since at each step we can estimate the number of white cubes that are affected
by the motion of black cubes. We point out one weakness of this method: the
$L^{2}$-norm of the new permutation might be increased, while we should expect
that if we move back the cubes to their original position the $L^{2}$-norm
would decrease.

  * Step 2)

In the previous step we proved that, up to some positive constant, it holds
$|P(\kappa)-\kappa|\leq\delta^{\epsilon}$. We need to prove that it is
possible to find a permutation $\tilde{P}$, close to our previous permutation,
such that it is constant on the tiling $\mathcal{R}_{\delta^{\epsilon}}$, in
the sense that every subcube $\kappa$ contained in a cube $K$ of the tiling
$\mathcal{R}_{\delta^{\epsilon}}$ is sent to the same subcube $K$.

This is the more expensive step in terms of the cost, and it requires a
different analysis from the one proposed in [8], where it is not given an
explicit construction of the flow. One of the main ideas here is that, in
order to achieve a good volume estimate, we should analyze the number of long
trajectories of cubes, thus we propose a counting argument based on
trajectories. This is the content of Section 3.2.2.

Our result is the following:

######  Theorem 1.10.

Let $P\in\mathcal{D}_{N}$ such that
$\|P-Id\|_{2}\leq\delta^{1-\frac{\epsilon}{2}}$, and that
$|P(\kappa)-\kappa|\leq\delta^{\epsilon}$ for some
$\epsilon\in(0,\frac{2}{2+\nu})$, for all $\kappa\subset\mathcal{R}_{N}$. Then
there exists a permutation $\tilde{P}\in\mathcal{D}_{N}$ constant on the
tiling $\mathcal{R}_{\delta^{\epsilon}}$ such that

$L(P,\tilde{P})\lesssim\max\\{\delta^{\frac{1}{2}-\frac{3\epsilon}{4}},\delta^{\frac{1}{6}+\epsilon\frac{7}{12}}\\}.$
(1.11)

We are strongly convinced that this step could be performed at an inferior
cost, but the main obstacle to our proof, for which we aimed to reach the
bound $\alpha\geq\frac{2}{2+\nu}$ in Theorem 2.11, is in the Assumption A of
Corollary 3.12. Indeed, in order to guarantee the constraint
$|P(\kappa)-\kappa|\leq\delta^{\epsilon}$, we needed to assume that the volume
of moving cubes was small.

  * Step 3)

The third step reads as follows.

######  Theorem 1.11.

Let $P\in\mathcal{D}_{N}$ be a permutation constant the tiling
$\mathcal{R}_{\delta^{\epsilon}}$. Then there exists a positive constant
$C=C(\nu)>0$ such that $\text{dist}(P,Id)\leq C(\nu)\delta^{\epsilon}.$

We point out that this Theorem cannot be optimal, since the proof relies on
the assumption that in each cube of the tiling
$\mathcal{R}_{\delta^{\epsilon}}$ we are performing a permutation with maximum
cost, ignoring completely the bound $\|P-Id\|_{2}$.

Finally, the proof of the main theorem follows by the previous three steps.

####  1.1.2 Comments on the proof.

To summarize, we do not expect this proof to be sharp. As underlined, one
major obstruction to improved estimates (which could be also relevant for the
continuous case) was the volume constraint of Assumption A (see Corollary
3.12). We conjecture that it should be possible to get the bound

$\alpha\geq\frac{2}{2+\nu},$

at least for $\nu>>1$ in the discretized context. Since it is clear from the
discrete construction that if a cube reach its original position $P(\kappa)$
the $L^{2}$-distance with the identity should decrease instead of increasing,
we conjecture that in the continuous case it should be possible to reach the
$\alpha=1$ exponent. In particular we expect that:

######  Conjecture 1.12 (Sharp Shnirelman’s inequality).

Let $\nu\geq 3$, then

$\text{dist}_{\mathcal{D}([0,1]^{\nu})}(f,g)\leq
C\|f-g\|_{L^{2}([0,1]^{\nu})},$

for every $f,g\in\mathcal{D}([0,1]^{\nu})$ volume-preserving diffeomorphisms.

We also think that our method could be a starting point towards an improvement
of the $\alpha$ exponent of the inequality, since it presents some
flexibility, while it seems out of reach the proof of 1.12 using these ideas
because of the previous considerations. It is an interesting open problem to
determine if in the discretized context it is possible to have the same bounds
as in the continuous one.

Moreover, a key difference with the continuous case is in the $2$-dimensional
case, where we can not have the estimate of the continuous version of the
inequality. We leave it as an open question

Open Problem $1$. Find $\alpha$ sharp for the discrete inequality in the case
$\nu=2$.

In the rest of the introduction we point out some open problems related to the
optimal Shnirelman’s inequality and connections to other fields.

####  1.1.3 Computational aspects

The discretized context is interesting also from a computational viewpoint. In
[4] Brenier proposed a discretized scheme in order to construct the optimal
flow connecting two permutations. Indeed, what is missing in our proof is the
search for the optimal discrete flow connecting $P$ to $Q$, since we do not
know a priori what is the geometry of the permutations involved. We point out
that Brenier proposed a discretized version of the action functional

$\mathcal{A}\\{\xi_{t}\\}_{t_{1}}^{t_{2}}=\int_{t_{1}}^{t_{2}}\|\dot{\xi}_{t}\|^{2}_{L^{2}(M)}dt,$

namely

$\min\sum_{j}\|\sigma_{j+1}-\sigma_{j}\|^{2}_{2},$

where the minimum is taken among all sequence of permutations connecting $P$
to $Q$. It would be interesting to implement the proof we presented in
connection to this functional.

####  1.1.4 Combinatorial aspects

The problem of finding the path (discrete flow) of minimum length connecting
two permutations is an interesting field of research in the theory of Cayley
Graphs associated to transposition trees (see [6] for a survey on the topic).
We point out that our problem on the unit cube is indeed related to a
transposition tree which is a $\nu$-dimensional lattice. Estimating the size
of the diameter of the Cayley Graph enters in the proof of Theorem 3.14, where
we used a rough estimate on the diameter. The problem of estimating the
diameter of Cayley graphs associated to transposition trees is in general
hard. Though there are transposition trees with particular geometry for which
this bound is sharp (see again [6]), finding sharp bounds on the diameter of
Cayley graph associated to $\nu$-dimensional lattices is an open question. On
the other side, since Inequality (1.3) could be obtained in a continuous
setting with a totally different approach, it could be interesting to
investigate if it is possible to improve the known bounds on graphs (also for
different topologies) through Shnirelman’s inequality.

####  1.1.5 Plan of the paper

In Section 2 we set the framework for the discrete configurations. We first
introduce formally the Regular Lagrangian Flows 2.1, since we will ask the
vector fields to possess $\operatorname{BV}$ regularity (the construction of
the vector fields will be given in the Appendix A). In subsection 2.2 we
define rectangles and arrays, together with the concept of discrete
configurations and colorings. In Subsection 2.2.1 we define the $S$-elementary
movement and Shnirelman’s discrete flow, together with the discrete length
functional introduced in [8]. In Subsection 2.3 we introduce the new length
functional together with the new definition of elementary movements and
discrete flow. In Theorem 2.23 we prove the equivalence of the two distances.
The formal justification to this section is the content of the Appendix A,
though it is not relevant for the computation of Shnirelman’s inequality. In
Section 3 we prove the improved version of Shnirelman’s inequality. In
Subsection 3.1 we estimate the cost of connecting two colorings. In Subsection
3.2 we finally give the proof of our main theorem. This is divided mainly into
Subsection 3.2.1, 3.2.2, where we perform the Step $1$ and $2$, while Step $3$
and the proof of the main theorem are at the end of the section. In the
Appendix A we give an explicit construction of a vector field swapping two
distant cubes.

Acknowledgements The author thanks Stefan Schiffer for many useful and
stimulating discussions on this topic.

##  2 Preliminaries and Notation

  * •

If $B$ is any Borel set, $B^{c}$ denotes the complementary;

  * •

$\text{int}(A)$ will denote the interior of the set $A$;

  * •

the inequality $f\lesssim g$ means $f\leq C(\nu)g$, where $C(\nu)$ is a
positive constant depending only on the dimension;

  * •

given $[0,1]^{\nu}$ the $\nu$-dimensional unit cube, we denote by
$\mathcal{R}_{N}$ the tiling of cubes of side $N^{-1}$, with $N\in\mathbb{N}$;

  * •

$R\subset\mathcal{R}_{N}$ is a $\nu$-rectangle, or simply a rectangle, and
$A\subset\mathcal{R}_{N}$ a $\nu$-array or simply an array;

  * •

given an array $A$, we will denote by $\ell(A)$ the length of $A$ and we will
use the notation $A=[\kappa_{1},\kappa_{2},\dots,\kappa_{\ell(A)}]$;

  * •

$\mathbf{v}_{R}$ is the vector field that in time $t=2$ rotates the rectangle
$R$;

  * •

a cube is $\kappa\in\mathcal{R}_{N}$, and $c(\kappa)$ denotes the center of
the cube;

  * •

$\mathcal{E}_{N^{\nu}}$ is the set of discrete configurations;

  * •

$\mathfrak{S}_{N^{\nu}}$ is the symmetric group on the set
$\\{1,2,\dots,N^{\nu}\\}$;

  * •

$\mathcal{D}_{N}$ is the group of permutations
$P:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$.

###  2.1 Regular Lagrangian Flows

Throughout the paper we will consider divergence-free vector fields
$\mathbf{v}:[0,1]\times[0,1]^{\nu}\rightarrow\mathbb{R}^{\nu}$ in the space
$L^{1}([0,1];\text{BV}([0,1]^{\nu}))\cap L^{1}([0,1];L^{2}([0,1]^{\nu}))$ (in
short $\mathbf{v}\in L^{1}_{t}\text{BV}_{x}\cap L^{1}_{t}L^{2}_{x}$). We will
use them to formally justify the definition of the discrete Length functional
2.9. We point out that all the vector fields under considerations could be
possibly made smooth in the interior of cubes or tube structures (see Appendix
A), but we prefer to keep the $\operatorname{BV}$ regularity to make the
constructions easier. We simply recall that, under this regularity assumption,
it is still possible to give a notion of flow (the _Regular Lagrangian Flow_)
[1]. More in detail, we give the following

######  Definition 2.1.

Let $\mathbf{v}\in L^{1}([0,1]\times\mathbb{R}^{\nu};\mathbb{R}^{\nu})$ be a
divergence-free vector field. A map
$X:[0,1]\times\mathbb{R}^{\nu}\rightarrow\mathbb{R}^{\nu}$ is a _Regular
Lagrangian Flow_ (RLF) for the vector field $\mathbf{v}$ if

  1. 1.

for a.e. $x\in\mathbb{R}^{2}$ the map $t\rightarrow X_{t}(x)$ is an absolutely
continuous integral solution of

$\begin{cases}\frac{d}{dt}x(t)=\mathbf{v}(t,x(t));&\\\ x(0)=x.\end{cases}$

  2. 2.

$\mathcal{L}^{2}(X_{t}^{-1}(A))=\mathcal{L}^{2}(A),\quad\forall
A\in\mathcal{B}(\mathbb{R}^{2}),\quad\forall t\in[0,1].$

We will often call _time-1 map_ the RLF $X_{t=1}$ of the vector field
$\mathbf{v}$ when evaluated at time $t=1$. Existence, uniqueness and stability
of RLFs for $\operatorname{BV}$ vector fields has been established in [1].
Regular Lagrangian flows have the advantage to allow rigid translations of
subsets of $[0,1]^{\nu}$, like permutations of subcubes of some tiling
$\mathcal{R}_{N}$, $N\in\mathbb{N}$ of $[0,1]^{\nu}$, since they do not
preserve the property of a set to be connected along the time evolution, thus
they constitute the right framework for the problem.

In the appendix and throughout the paper we will extensively use flows
rotating rectangles in order to swap adjacent cubes (Figure LABEL:fig:trasp).
Since the extension to higher dimension is straightforward, we will present
the results of this paragraph in dimension $\nu=2$. We define the _rotation
flow_ $r_{t}:[0,1]^{2}\rightarrow[0,1]^{2}$ for $t\in[0,1]$ in the following
way: call

$V(x)=\max\left\\{\left|x_{1}-\frac{1}{2}\right|,\left|x_{2}-\frac{1}{2}\right|\right\\}^{2},\quad
x=(x_{1},x_{2})\in[0,1]^{2}.$

Then the _rotation field_ is the divergence-free vector field
$r:[0,1]^{2}\rightarrow\mathbb{R}^{2}$ satisfying

${\mathbf{r}}(x)=\nabla^{\perp}V(x),$ (2.1)

where $\nabla^{\perp}=(-\partial_{x_{2}},\partial_{x_{1}})$ denotes the
orthogonal gradient. Finally the rotation flow $r_{t}$ is the flow of the
vector field $r$, i.e. the unique solution to the following ODE system:

$\begin{cases}\dot{r}_{t}(x)={\mathbf{r}}(r_{t}(x)),\\\
r_{0}(x)=x.\end{cases}$ (2.2)

We remark that this flow rotates the unit square $[0,1]^{2}$ counterclockwise
of an angle $\frac{\pi}{2}$ in a unit interval of time. In particular, to
rotate the rectangle $R=[0,a]\times[0,b]\subset\mathbb{R}^{2}$ with $a,b>0$,
then we first consider the rotation flow

$R_{t}=\chi^{-1}\circ r_{t}\circ\chi,$

where $\chi:R\rightarrow[0,1]^{2}$ is the affine map sending $R$ into the unit
cube and $r_{t}$ is the rotation flow defined in (2.2). Then if we denote by
$\mathbf{v}_{R}$ the divergence-free vector field associated with $R_{t}$, it
is defined as

$\mathbf{v}_{R}(x)=\nabla^{\perp}V_{a,b}=\begin{cases}\big{(}0,\frac{2b}{a}\big{(}x_{1}-\frac{a}{2}\big{)}\big{)}&|x_{1}|\geq\frac{b}{a}|x_{2}|,0\leq
x_{1}\leq a,\\\
\big{(}-\frac{2a}{b}\big{(}x_{2}-\frac{b}{2}\big{)},0\big{)}&|x_{1}|<\frac{b}{a}|x_{2}|,0\leq
x_{2}\leq b.\end{cases}$ (2.3)

Here, the potential $V_{a,b}$ is the function

$V_{a,b}(x)=\max\bigg{\\{}\frac{b}{a}\bigg{(}x_{1}-\frac{a}{2}\bigg{)}^{2},\frac{a}{b}\bigg{(}x_{2}-\frac{b}{2}\bigg{)}^{2}\bigg{\\}}.$

Observe that we can easily estimate the $L^{1}_{t}L^{2}_{x}$-norm of the
vector field $\mathbf{v}_{R}$ as

$\|\mathbf{v}_{R}\|^{2}_{L^{1}_{t}L^{2}_{x}(R)}\leq C|R|\max{\\{a,b\\}}^{2},$

where $C$ is a positive constant depending on the dimension $\nu$ and $|R|$
denotes the area of $R$. We point out that it can be proved that the total
variation of the previous vector field is bounded, as done in [3], so that the
vector field possesses a RLF. In the appendix there will be given the formal
definition of the divergence-free vector fields that will justify all the
subsequent computations.

###  2.2 Space of discrete configurations and Shnirelman’s length functional

In this section we will introduce the discrete setting.

A tiling $R_{N}$ of $[0,1]^{\nu}$ of size $N\in\mathbb{N}$ is a partition of
$[0,1]^{\nu}$ into $N^{\nu}$ identical subcubes $\kappa_{i_{1}i_{2}\dots
i_{\nu}}=\left[\frac{i_{1}-1}{N},\frac{i_{1}}{N}\right]\times\dots\times\left[\frac{i_{\nu}-1}{N},\frac{i_{\nu}}{N}\right]$,
with $i_{j}\in\\{1,2,\dots,N\\}$. We will omit the multi-index notations for
the subcubes simply denoting them by $\kappa$ if their position is not
relevant, and we will write $\kappa\in\mathcal{R}_{N}$ to denote that the cube
is in the tiling $\mathcal{R}_{N}$. We will denote by $c(\kappa)$ the center
of the cube $\kappa$. Finally, two subcubes $\kappa,\kappa^{\prime}\in R_{N}$
are _adjacent_ if they share a $(\nu-1)$-dimensional face.

A $\nu$-rectangle $R\subset[0,1]^{\nu}$ is a set of the following form

$\left[\frac{h_{1}}{N},\frac{\tilde{h}_{1}}{N}\right]\times\dots\times\left[\frac{h_{\nu}}{N},\frac{\tilde{h}_{\nu}}{N}\right],$

where $h_{j},\tilde{h}_{j}\in\\{1,\dots,N\\}$ and $h_{j}<\tilde{h}_{j}$.
Observe that any $\nu$-rectangle $R$ is union of subcubes of the tiling, thus
we will write $R\subset\mathcal{R}_{N}$. If the dimension needs not to be
specified, we will call the $\nu$-rectangles simply _rectangles_. Two
rectangles $R,\tilde{R}$ are _disjoint_ if
$\text{int}(R)\cap\text{int}(\tilde{R})=\emptyset.$

A _array_ $A$ is a rectangle such that there exists unique
$j\in\\{1,\dots,\nu\\}$ with $\tilde{h}_{k}-h_{k}=1$ for every $k\not=j$. The
_length_ of an array $A$ is the number $\ell(A)$ of subcubes $\kappa\subset
A$. We will often denote an array as
$[\kappa_{1},\kappa_{2},\dots,\kappa_{\ell(A)}].$

A (discrete) _configuration_ in $\mathcal{R}_{N}$ is a bijection
$i:\mathcal{R}_{N}\rightarrow\\{1,2,\dots,N^{\nu}\\}$. By writing
$i:\mathcal{R}_{N}\rightarrow\\{1,2,\dots,N^{\nu}\\}$ we mean that the
function is defined on $[0,1]^{\nu}$ and it is constant on the elements of the
tiling $\mathcal{R}_{N}$. We will denote the set of all discrete
configurations by $\mathcal{E}_{N^{\nu}}$: clearly
$|\mathcal{E}_{N^{\nu}}|=N^{\nu}!$. Let $\mathfrak{S}_{N^{\nu}}$ be the
symmetric group, then for every $\sigma\in\mathfrak{S}_{N^{\nu}}$, for every
$i\in\mathcal{E}_{N^{\nu}}$, it holds $\sigma\circ i\in\mathcal{E}_{N^{\nu}}$.
Similarly, we can define configurations on arrays as bijections, indeed given
an array $A$ we can define a bijection
$i_{A}:A\rightarrow\\{1,2,\dots,N^{\nu}\\}$. For an array $A$ of length
$\ell(A)$, we will denote the _canonical configuration_ as
$[\kappa_{1},\kappa_{2},\dots,\kappa_{\ell(A)}]$ and the _reverse
configuration_ as
$[\kappa_{\ell(A)},\kappa_{\ell(A)-1},\dots,\kappa_{2},\kappa_{1}]$.

In the following, we will not distinguish between permutations of cubes and
configurations. More precisely,

######  Definition 2.2 (Permutation of cubes).

A permutation $P$ of cubes of $\mathcal{R}_{N}$ is a measure-preserving map
$P:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ with the following property: there
exists $\sigma\in\mathfrak{S}_{N^{\nu}}$ such that
$i(P(\kappa))=\sigma(i(\kappa))$, for all $i\in\mathcal{E}_{N^{\nu}}$, for all
$\kappa\in\mathcal{R}_{N}$. Moreover,
$P(\kappa)=\kappa+c(P(\kappa))-c(\kappa)$ for all $\kappa\in\mathcal{R}_{N}$,
that is the permutation $P$ translates the cubes.

We will call the group of permutations $P$ defined above $\mathcal{D}_{N}$.
Similarly as in the previous definition, one can simply consider permutation
of subcubes of a rectangle $R$ oran array $A$. The definition is
straightforward ($P(\kappa)\subset A$, $\forall\kappa\subset A$).

Since in the proof of inequality (1.3) presented in [8] colorings of the
tiling $\mathcal{R}_{N}$ are useful for the study of permutations, we will
give the definition of a coloring.

######  Definition 2.3 (Coloring).

Let $R\subset\mathcal{R}_{N}$ be a rectangle. A coloring of $R$ into $m$
colors w.r.t. the tiling $\mathcal{R}_{N}$ is a map

$\Pi:R\rightarrow\\{{0,1,\dots,m-1}\\}$

such that $\Pi(\kappa)=j$, for every $\kappa\subset R$, with
$j\in\\{0,1,\dots,m-1\\}$.

Colorings of the tiling $\mathcal{R}_{N}$ are constant maps on the cubes of
the tiling. We can think to them as a specific color given to each subcube
$\kappa$. If $m=2$ we will also say that the coloring is into _black and white
cubes_ , where the white cubes satisfy $\Pi(\kappa)=0$. More generally, we
will often call _whites_ those cubes of the tiling for which $\Pi(\kappa)=0$;
we will call _colored_ the other ones.

######  Definition 2.4 (Canonical coloring).

Let $A$ bean array of length $\ell(A)$, and let $\Pi$ be a coloring of $A$
into black and white cubes. We say that $\Pi$ is the canonical coloring of
$A=[\kappa_{1},\dots,\kappa_{\ell(A)}]$ if there exists
$w\in\\{1,2,\dots,\ell(A)\\}$ such that $\Pi(\kappa_{j})=0$ for every $j\leq
w$ and $\Pi(\kappa_{j})=1$ for every $j\geq w+1$.

After introducing the discrete framework of arrays, configurations and
colorings, we start considering those permutations that can be realized as
time-1 map of the flow of some vector field.

We recall the definition of _swap_ of adjacent cubes (see Figure
LABEL:fig:trasp).

######  Definition 2.5 (Swap).

Let $\kappa_{1},\kappa_{2}\in R_{N}$ be two adjacent subcubes and denote by
$x_{1}=c(\kappa_{1}),x_{2}=c(\kappa_{2})$ their respective centers. A swap
between $\kappa_{1},\kappa_{2}$ is a map $T:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$
defined as follows:

$T(x)=\begin{cases}x+x_{2}-x_{1}\quad\text{ if }x\in\text{int}(\kappa_{1}),\\\
x+x_{1}-x_{2}\quad\text{ if }x\in\text{int}(\kappa_{2}),\\\
x\quad\text{otherwise}.\end{cases}$ (2.4)

######  Remark 2.6.

Observe that if $T$ is a swap of two adjacent subcubes, then for every
$i\in\mathcal{E}_{N^{\nu}}$ there exists $\sigma\in\mathfrak{S}_{N^{\nu}}$
transposition such that $\sigma\circ i=i\circ T$, for every
$i\in\mathcal{E}_{N^{\nu}}$ in particular $\sigma=i\circ T\circ i^{-1}$.

By definition of swap, two _adjacent_ cubes can be _connected_ by a
transposition, which can be defined simply as an exchange between the two
cubes: let $\kappa_{1},\kappa_{2}$ two adjacent cubes of side $\frac{1}{N}$
and let $R=\kappa_{1}\cup\kappa_{2}$, then the _transposition flow_ between
$\kappa_{1},\kappa_{2}$ is
$T_{t}(\kappa_{1},\kappa_{2}):[0,1]\times[0,1]^{\nu}\rightarrow[0,1]^{\nu}$
defined as

$T_{t}(\kappa_{1},\kappa_{2})=\begin{cases}\chi^{-1}\circ
r_{4t}\circ\chi&x\in\mathring{R},\ t\in\left[0,\frac{1}{2}\right],\\\
\chi_{1}^{-1}\circ r_{4t}\circ\chi_{1}&x\in\mathring{\kappa}_{1},\
t\in\left[\frac{1}{2},1\right],\\\ \chi_{2}^{-1}\circ
r_{4t}\circ\chi_{2}&x\in\mathring{\kappa}_{2},\
t\in\left[\frac{1}{2},1\right],\\\ x&\text{otherwise},\end{cases}$ (2.5)

where the map $\chi:R\rightarrow K$ is the affine map sending the
parallelepiped $R$ into the unit cube $[0,1]^{\nu}$, $\chi_{1},\chi_{2}$ are
the affine maps sending $\kappa_{1},\kappa_{2}$ into the unit cube
$[0,1]^{\nu}$ and $r$ is the rotation flow (2.2), when defined for a generic
dimension $\nu$. This invertible measure-preserving flow has the property to
exchange the two cubes in the unit time interval, and was introduced in [3],
where a simple computation gives also the correct $\operatorname{BV}$
regularity.

####  2.2.1 Shnirelman discrete length

In this subsection we use the framework introduced above and we define the
discrete Length functional defined in [8], that we will compare to the one of
next section. Before, we introduce the elementary movements, that here we call
$S$-elementary movements to distinguish them from those ones of the next
section.

######  Definition 2.7 (S-elementary movement).

A S-elementary movement is a measure-preserving map
$S:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ with the following property: there exist
$T_{1},\dots,T_{j}$ swaps, respectively of the couples of adjacent subcubes
$(\kappa^{1}_{1},\kappa^{1}_{2}),\dots,(\kappa^{j}_{1},\kappa^{j}_{2})$, with

$\text{int}(\kappa^{h}_{1}\cup\kappa^{h}_{2})\cap\text{int}(\kappa^{k}_{1}\cup\kappa^{k}_{2})=\emptyset,\quad
h\not=k,$

and

$S=T_{j}\circ T_{j-1}\circ\dots T_{2}\circ T_{1}.$

In particular, a $S$-elementary movement is a map that swaps simultaneously
couples of adjacent cubes. Given a $S$-elementary movement with
$S=T_{j}\circ\dots T_{1}$, we denote the number of simultaneous swaps of $S$
(that is, the number of couples that are swapped simultaneously) by
$\text{swap}(S)=j$.

######  Remark 2.8.

We remark that, for each $S$ $S$-elementary movement, $\text{swap}(S)\lesssim
N^{1+\nu}$, where the inequality holds up to some constant depending on the
dimension $\nu$.

######  Remark 2.9.

Each $S$-elementary movement can be trivially realized as the time-1 map of a
divergence-free vector field using the transposition flow (2.5).

We are ready to give the definition of discrete flow, that is

######  Definition 2.10 (S-discrete flow).

A S-discrete flow is a finite sequence $\\{S_{k}\\}_{k=1}^{T}$ with $S_{k}$
S-elementary movement for every $k=1,2,\dots,T$. The parameter $T$ is called
the _duration_ of the flow.

Let $P,Q:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ be two permutations (Definition
2.2). We say that $P$ is sent into $Q$ by the discrete flow
$\\{S_{k}\\}_{k=1}^{T}$ if

$S_{T}\circ S_{T-1}\circ\dots S_{2}\circ S_{1}\circ P=Q.$

In this case we say that the discrete flow $\\{S_{j}\\}_{j=1}^{T}$ _connects_
the two permutations $P,Q$. In particular, the _discretized length functional_
(which is the discrete counterpart of (1.1)), that quantifies the cost for
connecting $P$ to $Q$ is

$L_{S}(P,Q)=L_{S}\\{{S_{j}}\\}_{j=1}^{T}=\sum_{j=1}^{T}N^{-1-\frac{\nu}{2}}\sqrt{\text{swap}(S_{j})}.$
(2.6)

Finally, we define the _discrete distance_ on the space $\mathcal{D}_{N}$ as

$\text{dist}^{S}_{\mathcal{D}_{N}}(P,Q)=\underset{\text{connecting }P\text{ to
}Q}{\min_{\\{S_{j}\\}_{j=1}^{T}}}L_{S}\\{S_{j}\\}_{j=1}^{T}.$ (2.7)

In [8], it is proved the following

######  Theorem 2.11.

Let $\nu=2$, then there exists $C>0$ such that, for every $N\in\mathbb{N}$,
for every $P,Q\in\mathcal{D}_{N}$,

$\text{dist}^{S}_{\mathcal{D}_{N}}(P,Q)\leq\|P-Q\|_{2}^{\frac{1}{64}}.$

######  Remark 2.12.

We remark that, though the proof of Shnirelman’s inequality is valid in any
dimension $\nu$, in the paper [8] it is not given an explicit expression for
the exponent $\alpha$ of the $L^{2}$-norm depending on $\nu$.

######  Remark 2.13.

In order to minimize the cost functional $L(P,Q)$, notice that it is
convenient doing the maximum amount of simultaneous swapping at each time
step. This gives the connection with combinatorics and the theory of Cayley
Graphs.

The following theorem will be of key importance in the proof of the third step
of Shnirelman’s inequality. This theorem is proved in [8] and used for similar
purposes there.

######  Theorem 2.14 (Duration, [8]).

There exists a positive constant $C>0$ depending only on the dimension $\nu$
such that, for every $R\subset\mathcal{R}_{N}$ rectangle of sides
$\frac{M_{1}}{N},\dots,\frac{M_{\nu}}{N}$, and for every
$P,Q\in\mathcal{D}_{N}$ permutations of $R$, such that there exists a
$S$-discrete flow connecting $P$ to $Q$ whose duration does not exceed
$C\max\\{M_{1},\dots,M_{\nu}\\}.$

In particular, this theorem states that, the maximum amount of time to send a
permutation $P$ into another one is $N$, which is the inverse of the side of
the cubes of the tiling.

######  Remark 2.15.

Shnirelman’s original proof in [8] is built using estimates on the maximum
amount of time needed for doing the steps. The duration only partially uses
the information of $L^{2}$-norm, and this is the reason why with this approach
the $\alpha$ obtained by Shnirelman is very low.

We use this theorem to prove a useful corollary. First, we define the cost for
connecting a coloring $\Pi$ into white and black cubes to a coloring
$\tilde{\Pi}$ (with the same amount of white and black cubes) through a
$S$-discrete flow. Let $R$ be a rectangle and let
$\Pi,\tilde{\Pi}:R\rightarrow\\{0,1\\}$ be two colorings into black and white
cubes such that $b=\sharp\\{\kappa\subset
R:\Pi(\kappa)=1\\}=\sharp\\{\kappa\subset R:\tilde{\Pi}(\kappa)=1\\}.$

With abuse of notation, we say that $\Pi$ is sent into $\tilde{\Pi}$ by the
discrete flow $\\{S_{k}\\}_{k=1}^{T}$ if

$\Pi(\kappa)=\tilde{\Pi}\circ S_{T}\circ S_{T-1}\circ\dots S_{2}\circ
S_{1}(\kappa),\forall\kappa\subset R.$

In this case we say that the discrete flow $\\{S_{j}\\}_{j=1}^{T}$ _connects_
the two colorings $\Pi,\tilde{\Pi}$. Clearly, the cost of the coloring is
$L_{S}(\Pi,\tilde{\Pi})=L_{S}\\{S_{j}\\}_{j=1}^{T}.$

######  Corollary 2.16 (Cost of coloring arrays).

Let $A\subset\mathcal{R}_{N}$ be an array and let
$\Pi,\tilde{\Pi}:A\rightarrow\\{0,1\\}$ be two colorings in black and white
cubes such that, if $b$ denotes the number of black cubes then
$b=\sharp\\{\kappa\subset R:\Pi(\kappa)=1\\}=\sharp\\{\kappa\subset
R:\tilde{\Pi}(\kappa)=1\\}$. Then
$L(\Pi,\tilde{\Pi})\lesssim\ell(A)N^{-1-\frac{\nu}{2}}\min\\{\sqrt{b},\sqrt{\ell(A)-b}\\}$.

###### Proof.

Without loss of generality we can assume that $\tilde{\Pi}$ is the canonical
coloring 2.4. Moreover, we can assume that $b\leq\ell(A)-b$. The proof is a
consequence of Theorem 2.14. Take $\\{S_{j}\\}_{j=1}^{T}$ the $S$-discrete
flow given by Theorem 2.14. Then at each step any elementary movement $S_{j}$
moves at most $2b$ subcubes (in particular, only the couples of adjacent cubes
with the left one black and the right one white). Since the duration is
$T\leq\ell(A)$ by the previous theorem, we have the result. ∎

###  2.3 New length functional

The previous corollary 2.16 is almost immediate but highlights that the real
cost for connecting one coloring to another one is given by the number of
’black cubes’. This is the key idea of our work that allows us to introduce a
new Length functional. Its definition and the definition of a new discrete
flow is motivated by the results contained in the appendix, where we give an
explicit construction of the vector fields involved, which is not strictly
relevant to the computation of Shnirelman’s length functional.

######  Definition 2.17.

Let $A=[\kappa_{1}\kappa_{2}\dots\kappa_{\ell(A)}]\subset\mathcal{R}_{N}$ be
an array of length $\ell(A)$, and let $P\in\mathcal{D}_{N}$ be a permutation
of the array $A$. Let $\kappa_{i_{1}}$, $\kappa_{j_{1}}$, with $j_{1}\leq
i_{1}\leq\ell(A)$, be two subcubes of the array. We say that
$(\kappa_{i_{1}},\kappa_{j_{1}})$ is a _swapping couple_ for the permutation
$P$ if

$P(x)=\begin{cases}x+c(\kappa_{i_{1}})-c(\kappa_{j_{1}}),\quad
x\in\text{int}(\kappa_{j_{1}}),\\\ x+c(\kappa_{j_{1}})-c(\kappa_{i_{1}}),\quad
x\in\text{int}(\kappa_{i_{1}}),\\\ x\quad\text{otherwise},\end{cases}$

where $c(\kappa)$ denotes the center of the cube $\kappa$.

The notion of swapping couples extends the notion of adjacent cubes, so that
we can consider swaps of distant cubes (in this case, the permutation $P$ of
the previous definition).

######  Definition 2.18.

Let $A=[\kappa_{1}\kappa_{2}\dots\kappa_{\ell(A)}]\subset\mathcal{R}_{N}$ be
an array of length $\ell(A)$. A _sequence of swapping couples_ in $A$ is a
subset $\\{\kappa_{i_{j}}\\}\subset A$ with $j=1,\dots,2M\leq\ell(A)$, and

$i_{1}\leq i_{2}\leq\dots\leq i_{2M},$
$(\kappa_{i_{j}},\kappa_{i_{2M-j+1}})\qquad\text{swapping couple},\quad\forall
j=1,\dots,M.$

For simplicity, we will use the notation
$\\{(\kappa_{i_{h}},\kappa_{j_{h}})\\}$ for the sequence of swapping couples.

######  Definition 2.19 (Elementary Movement).

An elementary movement is a map $Z:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ such
that there exist $A_{1},\dots,A_{m}$ disjoint arrays with the following
properties: for every $1\leq i\leq m$, if
$(\kappa_{i_{1}},\kappa_{j_{1}}),\dots,(\kappa_{i_{h(i)}},\kappa_{j_{h(i)}})$
denote a sequence of swapping couples of the array $A_{i}$ (Definition 2.18),
then

$Z(x)=\begin{cases}x+c(\kappa_{i_{\ell}})-c(\kappa_{j_{\ell}}),\quad\forall
x\in\text{int}(\kappa_{j_{\ell}}),\quad\forall i,\quad\forall 1\leq\ell\leq
h(i),\\\ x+c(\kappa_{j_{\ell}})-c(\kappa_{i_{\ell}}),\quad\forall
x\in\text{int}(\kappa_{i_{\ell}}),\quad\forall i,\quad\forall 1\leq\ell\leq
h(i),\\\ x\quad\text{otherwise},\end{cases}$

where $c(\kappa)$ denotes the center of the cube $\kappa$.

We denote by $\mathcal{Z}_{N}$ the set of elementary movements. We remark that
also in this case elementary movements are permutations of subcubes of the
tiling $\mathcal{R}_{N}$.

Let $Z\in\mathcal{Z}_{N}$ be an elementary movement and let
$A_{1},\dots,A_{m}$ be the arrays of the previous definition. We assign to $Z$
a cost functional, namely $L:\mathcal{Z}_{N}\rightarrow\mathbb{R}_{+}$ as
follows:

$L(Z)=\max_{i}\ell(A_{i})N^{-1-\frac{\nu}{2}}\sqrt{\sum_{i=1}^{m}h(i)},$ (2.8)

where we recall that $\ell(A_{i})$ is the length of the array $A_{i}$, for
every $i$. The cost of an elementary movement is motivated by Corollary 2.16.

######  Remark 2.20.

We point out that, given an array $A$ and $\Pi:A\rightarrow\\{0,1\\}$ a
coloring into black and white cubes, there exists always a sequence of
swapping couples $\\{(\kappa_{i_{h}},\kappa_{j_{h}})\\}$ with $h=1,\dots,M$
with $2M\leq\ell(A)$ and $Z$ elementary movement swapping the sequence
(Definition 2.19), such that $Z\circ\Pi$ is the canonical coloring.

######  Definition 2.21 (Discrete flow).

A discrete flow is a finite sequence $\\{Z_{k}\\}_{k=1}^{T}$ with $Z_{k}$
elementary movement. $T$ is called the _duration_ of the flow.

Again, Let $P,Q:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ be two permutations. We say
that $P$ is sent into $Q$ by the discrete flow $\\{Z_{k}\\}_{k=1}^{T}$ if

$Z_{T}\circ Z_{T-1}\circ\dots Z_{2}\circ Z_{1}\circ P=Q.$

In this case we say that the discrete flow $\\{Z_{j}\\}_{j=1}^{T}$ _connects_
the two permutations $P,Q$.

We define the new length functional as

$L\\{Z_{j}\\}_{j=1}^{T}=\sum_{j=1}^{T}L(Z_{j}),$ (2.9)

and finally

$\text{dist}_{\mathcal{D}_{N}}(P,Q)=\underset{\text{connecting }P\text{ to
}Q}{\min_{\\{Z_{j}\\}_{j=1}^{T}}}L\\{Z_{j}\\}_{j=1}^{T}.$ (2.10)

######  Remark 2.22.

Also in this framework we can compute the cost of colorings.

Observe that, given $S$ $S$-elementary movement, then it is a elementary
movement, where the arrays are the couples of adjacent cubes that need to be
swapped. In particular,

$L(S)=2N^{-1-\frac{\nu}{2}}\sqrt{\sum_{i=1}^{\text{swap}(S)}1}=2N^{-1-\frac{\nu}{2}}\sqrt{\text{swap}(S)}.$

(The second equality is because $h(i)=1$ and $\ell(A_{i})=2$). Thanks to this
observation, we have that immediately

$\text{dist}_{\mathcal{D}_{N}}(P,Q)\leq
2\text{dist}^{S}_{\mathcal{D}_{N}}(P,Q).$

In the following theorem, we prove the equivalence of the two distances.

######  Theorem 2.23.

There exists a positive constant $C>0$ such that

$\text{dist}^{S}_{\mathcal{D}_{N}}(P,Q)\leq
C\text{dist}_{\mathcal{D}_{N}}(P,Q),\quad\forall P,Q\in\mathcal{D}_{N}.$

Before giving the proof of the theorem, we will prove the following

######  Lemma 2.24.

Let us fix an array $A$ of length $\ell(A)$ and consider the following two
configurations $i,i^{\prime}$ on the array $A$:

$i_{A}=[1,2,\dots,M,M+1,\dots,\ell(A)-M,\ell(A)-M+1,\dots,\ell(A)-1,\ell(A)]$
$i^{\prime}_{A}=[\ell(A),\ell(A)-1,\dots,\ell(A)-M+1,M+1,M+2,\dots,M,M-1\dots,1].$

Then there exists a sequence $\\{S_{j}\\}_{j=1}^{T}$ of $S$-elementary
movements with $i=i^{\prime}\circ S_{T}\circ S_{T-1}\circ\dots\circ S_{1}$ and
a positive constant $C$ depending only on the dimension such that
$L_{S}\\{S_{j}\\}_{j=1}^{T}\leq\sqrt{2}\ell(A)\sqrt{M}N^{-1-\frac{\nu}{2}}$.

###### Proof.

Similarly to the proof of Corollary 2.16, by Theorem 2.14, we know that the
duration of $\\{S_{j}\\}_{j=1}^{T}$ does not exceed $\ell(A)$. Moreover, at
each step, the maximum amount of simultaneous swapping that can be performed
is $\text{swap}(S_{j})\leq 2M$ (since we need to swap only the cubes that are
labelled in the statement). ∎

###### Proof of Theorem 2.23.

Let $Z$ be any elementary movement and let $(\kappa_{i_{h}},\kappa_{j_{h}})$
$h=1,\dots,M$ be a sequence of swapping couples, that are swapped by $Z$. We
need to prove that there exists a discrete $S$-flow $\\{S_{j}\\}_{j=1}^{T}$
such that $Z\circ\sigma=S_{T}\circ S_{T-1}\circ\dots\circ S_{1}\circ\sigma$
and $L_{S}\\{S_{j}\\}_{j=1}^{T}\leq CL\\{Z\\}$. Then the proof is an easy
consequence of Lemma 2.24 in the case $Z$ swaps the couples in a single array
$A$. The proof is similar in the case of multiple arrays. ∎

The introduction of this equivalent distance establishes the setting under
which we can improve the $\alpha$-exponent in Shnirelman’s inequality. We
point out that, though it is not necessary for the computations of next
section, the formal justification for the use of this distance (which is
equivalent to the one of Shnirelman) lies in the idea that distant cubes can
be swapped through tube structures (see Appendix A).

##  3 Improved Shnirelman’s Inequality

In the previous section we presented the setting under which we will achieve
our main result. We point out that our proof draws inspiration from that one
in [8] (differently from the one proposed in [9] via generalized flows),
though some steps are performed differently. Moreover, the introduction of the
new length functional 2.9 allows to obtain better estimates.

The aim of this section is to prove the following

######  Theorem 3.1 (Improved Shnirelman’s discrete inequality).

Let $\nu\geq 3$, then there exists a positive constant $C=C(\nu)>0$, and
$\alpha\geq\frac{1}{1+\nu}$ such that, for every $N\in\mathbb{N}$, for every
$P,Q$ permutations of some tiling $\mathcal{R}_{N}$ of $[0,1]^{\nu}$, it holds

$\text{dist}_{\mathcal{D}_{N}}(P,Q)\leq C\|P-Q\|_{2}^{\alpha}.$ (3.1)

Moreover, if $\nu=2$, $\alpha$ can be chosen to be $\alpha\geq\frac{2}{7}.$

First, we observe that in the proof of the theorem we can assume $Q=Id$, since
$\text{dist}_{\mathcal{D}_{N}}(P,Q)=\text{dist}_{\mathcal{D}_{N}}(P\circ
Q^{-1},Id)$. Next, we can assume (as done in [8],[9]) that
$\|P-Id\|_{L^{2}}\leq\delta$, where $\delta<<1$ and fixed at the beginning.
Moreover, we fix $\epsilon>0$ and $\epsilon<<1$ to be chosen later. We will
use $\epsilon$ since we will work with a less finer tiling
$\mathcal{R}_{\delta^{-\epsilon}}$. We will denote by $K$ the bigger subcubes
of this new tiling.

######  Remark 3.2.

Observe that, once we have inequality $\|P-Id\|_{2}^{2}\leq\delta^{2}$, then
we use that

$N^{-2}N^{-\nu}\lesssim\|P-Id\|_{2}^{2}\leq\delta^{2},$

since, if $P$ is not the identity (in that case Shnirelman’s inequality would
be trivial), then it must be at least a transposition of adjacent cubes. In
particular, we can use the tiling $\mathcal{R}_{\delta^{-\epsilon}}$ if
$\delta^{\epsilon}\geq N^{-1}$, that is
$N^{-\epsilon\left(1+\frac{\nu}{2}\right)}\geq N^{-1}$, which yields
$\epsilon\leq\frac{2}{2+\nu}$. We will see that this bound will be of key
importance also in the following steps of the proof.

In particular, if we fix $\epsilon>0$ at the beginning, chosen accordingly to
the bounds of the previous remark, we can assume that
$2^{m+1}N^{-1}>\delta^{\epsilon}>{2^{m}}N^{-1}$ with $m\in\mathbb{N}$.
Similarly, since $\|P-Id\|_{L^{2}}\leq\delta^{\prime}$ for every
$\delta^{\prime}>\delta$, we can also assume that
$(\delta^{\prime})^{\epsilon}=2^{m+1}N^{-1}.$ With these considerations, we
are justified in taking a tiling $\mathcal{R}_{\delta^{-\epsilon}}$ with the
property that $\delta^{\epsilon}N=2^{m}$. Since we can also assume $N=2^{n}$
for some $n\in\mathbb{N}$, we can have that $\delta^{-\epsilon}\in\mathbb{N}$.

Before giving the proof of the theorem, we state and prove some preliminary
results.

###  3.1 Cost of Colorings

In the next theorem, we prove that, given two colorings $\Pi,\tilde{\Pi}$
w.r.t. the tiling $\mathcal{R}_{N}$ in black and white cubes (Definition 2.3)
of a cube of side $\delta^{\epsilon}$, with the property that the number of
black cubes of the two colorings is the same, then the cost for moving one
coloring into the other one is
$L(\Pi,\tilde{\Pi})\sim\sqrt{\min({b,\delta^{\epsilon\nu}N^{\nu}}-b)N^{-\nu}}\delta^{\epsilon}$,
that is given, up to some constant depending on the dimension of the space, by
the squared volume of the total black cubes (or the white cubes, depending
which cubes represent the majority) times the size of the cube where the
colorings are defined (in this case $\delta^{\epsilon})$.

More precisely,

######  Theorem 3.3.

Let $K$ be a cube of the tiling $\mathcal{R}_{\delta^{-\epsilon}}$ and assume
to have $\Pi,\tilde{\Pi}:K\rightarrow\\{0,1\\}$ two colorings in black and
white cubes such that $b=\sharp\\{\kappa\subset
K,\kappa\in\mathcal{R}_{N}:\Pi(\kappa)=1\\}=\\{\kappa\subset
K,\kappa\in\mathcal{R}_{N}:\tilde{\Pi}(\kappa)=1\\}$. Then there exists a
positive constant $C=C(\nu)>0$, not depending on $\Pi,\tilde{\Pi},N,K$, such
that

$L(\Pi,\tilde{\Pi})\leq
C(\nu)\sqrt{\min({b,\delta^{\epsilon\nu}N^{\nu}}-b)}\delta^{\epsilon}.$

######  Remark 3.4.

This theorem is the multi-dimensional version of Corollary 2.16.

###### Proof.

This proof in inspired by [8]. We give the proof for $\nu=2$ being the
extension to higher dimension straightforward. Without loss of generality we
can assume that the number of black cubes is less than the number of white
cubes. Partition the cube $K$ into $\delta^{\epsilon}N$ horizontal stripes
$H_{i}$ and into $\delta^{\epsilon}N$ vertical stripes $V_{j}$. Let $n_{j}$ be
the number of black subcubes in the stripe $V_{j}$.

Step 1 We first give the proof assuming that $b<N\delta^{\epsilon}$. It is
easy to prove that there exists a coloring $\Pi^{\prime}$ with the same amount
of black and white cubes as $\Pi$ such that the number $n_{j}$ of black cubes
into the stripes $V_{j}$ is the same, but in each horizontal stripe $H_{i}$
the number of black cubes is less or equal then $1$. The cost for performing
this elementary movement (that we will call for simplicity $Z_{1}$) is

$L(Z_{1})\lesssim N^{-2}\sqrt{b}\delta^{\epsilon}.$

This flow acts simultaneously and independently on each vertical stripe
$V_{j}$ (see Figure 2).

Figure 2: The elementary movements act simultaneously and independently on the
stripes $V_{j}$ first and then on the stripes $H_{i}$.

Then we send $\Pi^{\prime}$ into $\Pi^{\prime\prime}$ where all the black
subcubes are moved to the right through the elementary movement $Z_{2}$. The
cost here is again

$L(Z_{2})\lesssim N^{-2}\sqrt{b}\delta^{\epsilon}.$

At the end only the last vertical stripe $V_{\delta^{\epsilon}N}$ contains
black cubes. We apply the same procedure to $\tilde{\Pi}$ and then we find an
elementary movement $Z_{3}$ acting only on the last vertical stripe
$V_{\delta^{\epsilon}N}.$ Therefore,

$L(\Pi,\tilde{\Pi})\lesssim N^{-2}\sqrt{b}\delta^{\epsilon}.$

Step 2. For the general case we consider the number

$M=\frac{b}{N\delta^{\epsilon}}.$

We first assume that this number is integer, and then we will see how to
perform the proof in the case it is not.

Case $M\in\mathbb{N}$. As before, it is easy to see that, given $\Pi$, there
exists a coloring $\Pi^{\prime}$ (with the same amount of black and white
cubes) such that $n_{j}$ is the same in each vertical stripe $V_{j}$ but in
each horizontal stripe $H_{i}$ there is the same amount of black subcubes $M$.
The conclusion holds exactly as before and clearly it holds that
$L(\Pi,\tilde{\Pi})\lesssim N^{-2}\sqrt{b}\delta^{\epsilon}$.

Case $M\not\in\mathbb{N}$. This is a more delicate case, although the
reasoning is almost identical to the previous one. We choose $y$ yellow
squares among the white ones with

$y=N\delta^{\epsilon}\left(\biggl{\lfloor}\frac{b}{N\delta^{\epsilon}}\biggr{\rfloor}+1\right)-b,$

where we have denoted by $\lfloor\cdot\rfloor$ the integer part. Clearly if
$b<y$ we are in the situation of Step 1, so that we can assume the converse.
We take $\Pi$ in the coloring $\Pi^{\prime}$ as before considering, for this
step, the yellow cubes as black cubes. Then we send $\Pi^{\prime}$ into
$\Pi^{\prime\prime}$ where all the colored subcubes (black and yellow) are
moved to the right (see for clarity Figure 3). Call $R(\epsilon)$ the
rectangle of colored subcubes and we observe that if we do the same with
$\tilde{\Pi}$ we arrive to the same rectangle $\tilde{R}(\epsilon)$. So we can
consider $R(\epsilon)$ and $\tilde{R}(\epsilon)$ as two new colorings into
black and yellow subcubes with the number of yellow cubes given by $y$. In
this case $y<N\delta^{\epsilon}$ and we apply the first step of the proof on
the rectangle $R(\epsilon)$, since the length of the vertical stripes is
$\delta^{\epsilon}$. Clearly, the cost functional is computed similarly as
$L(\Pi,\tilde{\Pi})\lesssim N^{-2}\sqrt{b}\delta^{\epsilon}$.

Figure 3: The case $M\not\in N$

We point out that in the $\nu$-dimensional case the cost is computed as
$L(\Pi,\tilde{\Pi})\lesssim N^{-1-\frac{\nu}{2}}\sqrt{b}\delta^{\epsilon}$. ∎

In particular, if we need to compute the cost of coloring for more general
rectangles, it immediately follows that

######  Corollary 3.5.

Let $R$ be a rectangle of sides
$\frac{M_{1}}{N},\frac{M_{2}}{N},\dots,\frac{M_{\nu}}{N}$, and let
$\Pi,\tilde{\Pi}:R\rightarrow\\{{0,1}\\}$ be two colorings of $R$ into black
and white cubes such that $b=\sharp\\{\kappa\subset
R,\kappa\in\mathcal{R}_{a}:\Pi(\kappa)=1\\}=\\{\kappa\subset
R,\kappa\in\mathcal{R}_{a}:\tilde{\Pi}(\kappa)=1\\}$. Then

$L(\Pi,\tilde{\Pi})\lesssim\sqrt{\min({b,\delta^{\epsilon\nu}N^{\nu}}-b)}\max\left\\{\frac{M_{1}}{N},\frac{M_{2}}{N},\dots,\frac{M_{\nu}}{N}\right\\}.$

Here we prove another important result, that will be useful in the following.

###  3.2 Proof of Theorem 2.11

In this subsection we give the proof of the main theorem. We divide the proof
into several steps, before giving the last statement. As pointed out in the
introduction, the idea is to simplify the starting permutation $P$ in such a
way that it is constant on the less finer tiling
$\mathcal{R}_{\delta^{-\epsilon}}$ (content of Proposition 3.6 and Theorem
3.9). We also remark that the proofs are carried out in dimension $\nu=2$,
since the extension to higher dimension is straightforward. In any case, the
computation of the cost for performing the various steps will be given in any
dimension $\nu$.

From now on we will fix a permutation $P$ of some tiling $\mathcal{R}_{N}$
with $N\in\mathbb{N}$ with the property that $\|P-Id\|_{2}\leq\delta$, with
$\delta<<1$. We choose $\epsilon>0$ accordingly, as seen in the introduction
to the section.

####  3.2.1 Proof of Step $1$.

We start with the following proposition, that reduces the problem to a
permutation $\tilde{P}$ with the property that it is still close to the
identity in the $L^{2}$-norm, but all the subcubes of the tiling
$\mathcal{R}_{N}$ do not move more that $C\delta^{\epsilon}$, for some
positive constant $C$. We point out that the statement and the proof of the
proposition are inspired by those ones in [8].

######  Proposition 3.6.

Let $P\in\mathcal{D}_{N}$ chosen ad above. Then there exist two positive
constants $C=C(\nu)>0,D=D(\nu)>0$ and a permutation
$\tilde{P}\in\mathcal{D}_{N}$ such that:

  * •

$\|\tilde{P}-Id\|_{2}\leq C\delta^{1-\frac{\epsilon}{2}}$;

  * •

for every $\kappa\in\mathcal{R}_{N}$, $|\tilde{P}(\kappa)-\kappa|\leq
D{\delta}^{\epsilon}$.

Moreover, the cost for connecting $P$ to $\tilde{P}$ is computed as

$L(P,\tilde{P})\lesssim\delta^{1-\epsilon}.$ (3.2)

######  Remark 3.7.

We remark that all the constants involved in the computations of cost depend
only on the dimension $\nu$.

###### Proof.

We prove the proposition in dimension $\nu=2$ since the extension to higher
dimension is straightforward. We denote the cubes of the less finer tiling
$\mathcal{R}_{\delta^{-\epsilon}}$ via the multi-index notation $K_{ij}$, with
$i,j\in\\{1,2,\dots,\delta^{-\epsilon}\\}.$

We consider the following coloring $\Pi$ of the tiling $\mathcal{R}_{N}$ into
white and colored subcubes defined as follows:

$\Pi(\kappa)=\begin{cases}0\quad\text{ if
}|P(\kappa)-\kappa|\leq\delta^{\epsilon},\\\ j\text{ if
}|P(\kappa)-\kappa|>\delta^{\epsilon},\text{ and }P(\kappa)\in K_{ij},\\\
\end{cases}$

for every $\kappa\in\mathcal{R}_{N}$. In particular we will call white those
cubes for which $\Pi(\kappa)=0$ and colored those ones for which
$\Pi(\kappa)\not=0$. We observe that

  * •

the number of colors is $\delta^{-\epsilon}+1$, (where $+1$ refers to the
color white);

  * •

by the constraint on the $L^{2}$-norm on the permutation $P$ one finds that
the number of colored subcubes (that we will denote by $N(C)$) is

$N(C)\leq\delta^{2-2\epsilon}N^{2},$

and in case of any dimension it is

$N(C)\leq\delta^{2-2\epsilon}N^{\nu}.$

Indeed, it holds

$\displaystyle\delta^{2}\geq\|P-Id\|_{2}^{2}=\sum_{\kappa\in\mathcal{R}_{N}}N^{-\nu}|P(\kappa)-\kappa|^{2}\geq\sum_{\kappa:\Pi(\kappa)\not=0}N^{-\nu}|P(\kappa)-\kappa|^{2}>N(C)N^{-\nu}\delta^{2\epsilon}.$

Observe that the number of colored subcubes is
$N(C)\leq\delta^{\nu\epsilon}N^{\nu}$ in the assumption
$\epsilon\leq\frac{2}{2+\nu}$ which implies that the colored subcubes can all
be contained inside a single subcube of the bigger tiling
$\mathcal{R}_{\delta^{-\epsilon}}$. The bound on $\epsilon$ is consistent with
Remark 3.2.

We divide the proof of the proposition in several steps: the main idea is that
we move only the colored subcubes into their original position $P(\kappa)$
with the constraint that the white subcubes do not move more than
$D\delta^{\epsilon}$, for some constant $D$, in order to prove the statement.

Step 1. We call $H_{i}$ with $i=1,2,\dots,\delta^{-\epsilon}$ the horizontal
stripes of the tiling $\mathcal{R}_{\delta^{\epsilon}}$ and we call
$K_{i1},K_{i2},\dots,K_{i\delta^{-\epsilon}}\in\mathcal{R}_{\delta^{\epsilon}}$
the subcubes of the stripe $H_{i}$ enumerated starting from the left side of
the cube. By means of Theorem 3.3 together with Corollary 3.5, we can perform
a flow in each subcube $K_{ij}$ simultaneously and independently in order to
obtain any coloring $\Pi^{\prime}$ of the tiling $\mathcal{R}_{N}$ with the
property that the number of colored subcubes in each $K_{ij}$ remains
constant. More precisely, there exists a coloring $\Pi^{\prime}$ of
$\mathcal{R}_{N}$ into white and colored cubes with the following property: if
we denote by $A_{ij}=\\{\kappa\in\mathcal{R}_{N}\cap
K_{ij}:\Pi^{\prime}(\kappa)\not=0\\}$ the set of colored subcubes of $K_{ij}$
under the new coloring, then

$\left(\text{int}(A_{i1})+\delta^{\epsilon}\right)\cap\text{int}(A_{i2})=\emptyset,$

where we denoted by $\text{int}(A_{i1})+\delta^{\epsilon}$ the translation of
the set $\text{int}(A_{i1})$. Moreover, it holds

$\left(\left(\text{int}(A_{i1})+(j-1)\delta^{\epsilon}\right)\cup\dots\cup\left(\text{int}(A_{i(j-1)})+\delta^{\epsilon}\right)\right)\cap\text{int}(A_{ij})=\emptyset.$
(3.3)

In particular, there exists a discrete flow $\\{Z_{j}\\}$ acting
simultaneously and independently on each cube $K_{ij}$ sending $\Pi$ into
$\Pi^{\prime}$ with cost computed as

$L(\Pi,\Pi^{\prime})\lesssim\sqrt{N(C)N^{-2}}\delta^{\epsilon}=\delta,$

(which in case of any dimension is still
$L(\Pi,\Pi^{\prime})\lesssim\sqrt{N(C)N^{-\nu}}\delta^{\epsilon}=\delta$).
Observe that at this stage the flow has moved the white cubes within each cube
$K_{ij}$, so that each white subcube is moved no more that
$\sqrt{2}\delta^{\epsilon}$ (see Figure 4).

Figure 4: There exists a coloring $\Pi^{\prime}$ (second line) such that
Condition (3.3) holds. The discrete flow acts independently and simultaneously
on each $K_{ij}$ first, then it swaps the colored subcubes of $K_{ij}$ with
the corresponding white in $K_{i(j+1)}$ (third line).

Step 2. By the properties of the new coloring $\Pi^{\prime}$ the idea in this
step is that we can move all the colored subcubes into the last cube
$K_{i\delta^{-\epsilon}}$, moving the white cubes of at most
$2\delta^{\epsilon}$. In particular, we construct the following elementary
movements: $Z_{1},Z_{2},\dots,Z_{\delta^{-\epsilon}-1}$ acting as follows:

  * •

the elementary movement $Z_{1}$ acts on the cubes $K_{i1}$ simultaneously and
independently swapping the colored subcubes of $K_{i1}$ (for every $i$) with
the same amount of white subcubes in the subcube $K_{i2}$. Call $c_{i}(1)$ the
number of colored subcubes in $K_{i1}$ and $c_{i}(2)$ the number of colored
subcubes in $K_{i2}$. The result of this movement is that in the cube $K_{i1}$
there are left only white cubes while in the cube $K_{i2}$ the number of
colored subcubes is given by the sum $c_{i}(1)+c_{i}(2)$. The cost is clearly

$L(Z_{1})\lesssim\sqrt{N(C)N^{-2}}\delta^{\epsilon}\leq\delta,$

(and the same estimate holds in any dimension), and the white subcubes are
moved of at most a quantity $\leq 2\delta^{\epsilon}$.

  * •

Inductively the movement $Z_{j}$ acts on the cubes $K_{ij}$ simultaneously and
independently swapping the colored subcubes of $K_{ij}$ (for every $i$) with
the same amount of white subcubes in the subcube $K_{i(j+1)}$. Again if
$c_{i}(j)$ the number of colored subcubes in $K_{ij}$, after the movement
$Z_{j}$ in the cube $K_{ij}$ there will be only white cubes while in the cube
$K_{i(j+1)}$ the number of colored subcubes will be given by the sum
$\sum_{k=1}^{j+1}c_{i}(k)$. The cost is clearly

$L(Z_{j})\lesssim\sqrt{N(C)N^{-2}}\delta^{\epsilon}\leq\delta,$

(and the same estimate holds in any dimension). Again the white subcubes are
moved of at most a quantity $\leq 2\delta^{\epsilon}$.

The whole procedure stops when all the colored subcubes are moved into the
last cube $K_{i\delta^{-\epsilon}}$ (see Figure 4). Since the number of
movements here is $\delta^{-\epsilon}$, the total cost can be computed as

$L\\{{Z_{j}}\\}_{j=1}^{\delta^{-\epsilon}-1}\lesssim\delta\delta^{-\epsilon}\lesssim\delta^{1-\epsilon}.$

Acting similarly in the vertical columns of the tiling
$\mathcal{R}_{\delta^{\epsilon}}$ we can move all the colored subcubes into
the cube $K_{1\delta^{-\epsilon}}$. All the procedures are guaranteed by the
fact that the total amount of black subcubes is less or equal than the amount
of subcubes contained in a cube $K$ of the less finer tiling
$\mathcal{R}_{\delta^{-\epsilon}}$.

This step in particular proves that there exists a coloring $\tilde{\Pi}$ such
that $\tilde{\Pi}(\kappa)=0$ for every $\kappa\not\in
K_{1\delta^{-\epsilon}}$, where $\kappa\in\mathcal{R}_{N}$. Moreover, this
flow has moved all the white cubes of an amount $\leq D\delta^{\epsilon}$ for
some positive constant $D>0$.

Step 3. We have reduced the problem to the one where all the colored subcubes
are contained inside one single cube $K_{1\delta^{-\epsilon}}$ of the less
finer tiling $R_{\delta^{-\epsilon}}$. We call $V_{j}$ with
$j=1,2,\dots,\delta^{-\epsilon}$ the vertical stripes of this tiling. The main
idea of the procedure is illustrated in Figure 5. We first move the colors
along the first row $H_{1}$ of the tiling (here, the cost will be computed as
$\sim\delta^{1-\epsilon}$) in such a way that if $P(\kappa)\in V_{j}$ then
$\kappa$ is moved in $K_{1j}$ of the tiling $R_{\delta^{-\epsilon}}.$ Remember
that we can swap only subcubes that live in adjacent cubes $K_{1j}$,
$K_{1(j+1)}$ in order to verify the constraint that the white cubes do not
move more that $D\delta^{\epsilon}$. We give the inductive procedure:

  * •

base step: we swap the colored cubes of colors
$1,2,\dots,\delta^{-\epsilon}-1$ in the cube $K_{1\delta^{-\epsilon}}$ with
the same amount of white cubes in $K_{1(\delta^{-\epsilon}-1)}$ through an
elementary movement $T_{1}$ with cost

$L(T_{1})\lesssim\sqrt{N(C)N^{-2}}\delta^{\epsilon}\leq\delta,$

(and again the same amount holds in any dimension);

  * •

inductive step: we swap the colored cubes of colors $1,2,\dots,j$ contained in
the cube $K_{1j}$ with the same amount of white cubes in $K_{1(j-1)}$ through
an elementary movement $T_{\delta^{-\epsilon}-j}$ with cost

$L(T_{\delta^{-\epsilon}-j})\lesssim\sqrt{N(C)N^{-2}}\delta^{\epsilon}\leq\delta;$

(and again the same amount holds in any dimension).

The procedure guarantees that the white cubes are moved no more than
$2\delta^{\epsilon}$ and stops when each color has reached the right column.
In particular,

$L(T_{\delta^{-\epsilon}-1}\dots
T_{2}T_{1})=\sum_{j=1}^{\delta^{-\epsilon}}L(T_{j})\leq\delta^{-\epsilon}\sqrt{2}\delta\lesssim\delta^{1-\epsilon}.$

Figure 5: Explanation of Step $3$ of the proof of Proposition 3.6

Step 4 In this last step we move the colored subcubes of the previous step in
their right position, namely if $\kappa\in K_{1j}$ and we know that
$P(\kappa)\in K_{i,j}$ for some index $i$, we move the cube in its original
position. This step is performed as Step $3$. Indeed, we can act again
independently and simultaneously in each column $V_{j}$ and the cost is
computed as the previous steps.

All this step give a new permutation $\tilde{P}$ of the tiling
$\mathcal{R_{N}}$ satisfying the following property: for each
$\kappa\in\mathcal{R}_{N}$ it holds $|\tilde{P}(\kappa)-\kappa|\leq
D(\nu)\delta^{\epsilon}$. The cost
$L(P,\tilde{P})\lesssim\delta^{1-\epsilon}$, for some constant $D(\nu)$
depending only on the dimension, as a result of the previous steps. We need
only to prove that $\tilde{P}$ is still close to $Id$ in the $L^{2}$-norm.

Observe that in the whole procedure we have moved an amount of white cubes
$\sim\delta^{-\epsilon}N(C)$ for some constant $M>0$, since we moved them only
when we had to swap the colored cubes. In particular, if we call
$\\{Z_{j}\\}_{j=1}^{T}$ the discrete flow we constructed in the previous $4$
steps, and if we call $A=\\{\kappa:\Pi(\kappa)=0,Z_{T}\circ\dots\circ
Z_{1}(\kappa)=\kappa\\}$, that is, the set of white cubes that did not move
during the four previous steps, then $\sharp A^{c}=MN(C)$ and

$\displaystyle\|\tilde{P}-Id\|^{2}_{2}$
$\displaystyle=\sum_{\kappa\in\mathcal{R}_{N}}N^{-\nu}|\tilde{P}(\kappa)-\kappa|^{2}=\sum_{\kappa:\Pi(\kappa)=0}N^{-\nu}|\tilde{P}(\kappa)-\kappa|^{2}+\sum_{\kappa:\Pi(\kappa)\not=0}N^{-\nu}|\tilde{P}(\kappa)-\kappa|^{2}$
$\displaystyle\leq\sum_{\kappa:\Pi(\kappa)=0}N^{-\nu}|\tilde{P}(\kappa)-\kappa|^{2}+\sum_{\kappa:\Pi(\kappa)\not=0}N^{-\nu}|P(\kappa)-\kappa|^{2}$
$\displaystyle=\sum_{\kappa\in
A}N^{-\nu}|P(\kappa)-\kappa|^{2}+\sum_{\kappa:\Pi(\kappa)\not=0}N^{-\nu}|P(\kappa)-\kappa|^{2}+\sum_{\kappa\in
A^{c}}N^{-\nu}|\tilde{P}(\kappa)-\kappa|^{2}$
$\displaystyle\leq\|P-Id\|^{2}_{2}+MN(C)N^{-\nu}\delta^{2\epsilon}\leq\delta^{2-\epsilon},$

which concludes the proof. ∎

######  Remark 3.8.

We remark that in the previous proof we could not apply directly Corollary
3.5, since we should have guaranteed that white cubes did not move more than
$D(\nu)\delta^{\epsilon}$. But the previous computations actually show that,
in terms of the cost, applying the corollary or consider the motion in multi-
steps as done in the previous proof gives the same cost
$\sim\delta^{1-\epsilon}$ (what changes is the constant, but still depends
only on the dimension $\nu$).

In other words, we have proved that up to spending some cost of the order
$\delta^{1-\epsilon}$, we can assume to start with a permutation $P$ of the
tiling $\mathcal{R}_{N}$ whose property is that
$|P(\kappa)-\kappa|\leq\delta^{\epsilon}$, which is still close to $Id$ in the
$L^{2}$-norm.

####  3.2.2 Proof of Step $2$.

The next idea is to find another permutation $\tilde{P}$ close to the identity
such that it is constant on an appropriate partition of the space. This is
given in the proof of the next theorem (the second step), which requires a bit
more effort. While the previous proof was inspired by the ideas in [8], we
perform this step differently, since in [8] no example of discrete flow is
exhibited. We always exploit the idea that the cost can be computed via an
estimate of the volume of the cubes that are moved by the permutation. Again,
this estimate is based on the constraint given by the $L^{2}$-norm satisfied
by the permutation $\tilde{P}$. But we will see that, in order to compute the
volume constraint, we need to count the number of trajectories of colored
cubes. We will prove the following:

######  Theorem 3.9.

Let $P\in\mathcal{D}_{N}$ such that
$\|P-Id\|_{2}\leq\delta^{1-\frac{\epsilon}{2}}$, and that
$|P(\kappa)-\kappa|\leq\delta^{\epsilon}$ for some
$\epsilon\in(0,\frac{2}{2+\nu})$, for all $\kappa\subset\mathcal{R}_{N}$. Then
there exists a permutation $\tilde{P}\in\mathcal{D}_{N}$ constant on the
tiling $\mathcal{R}_{\delta^{\epsilon}}$ such that

$L(P,\tilde{P})\lesssim\max\\{\delta^{\frac{1}{2}-\frac{3\epsilon}{4}},\delta^{\frac{1}{6}+\epsilon\frac{7}{12}}\\}.$
(3.4)

Before giving the proof of the theorem, we consider the following subdivision
of the unit cube into $M$ slices, where we have denoted by
$M=\delta^{-\epsilon}$ and by $H_{1},H_{2}\dots,H_{M}$ the horizontal slices.

$H_{i}=[0,1]\times\left[\frac{i-1}{M},\frac{i}{M}\right]\times[0,1]^{\nu-2},\quad
i\in\\{1,2,\dots,M\\}.$

Consider now the following coloring of the tiling $\mathcal{R}_{N}$ in white,
black and red cubes:

$\Pi(\kappa)=\begin{cases}0\quad\text{if }P(\kappa)\in H_{i},\\\
1\quad\text{if }P(\kappa)\in H_{i-1},\\\ 2\quad\text{if }P(\kappa)\in
H_{i+1},\end{cases}\kappa\subset H_{i}.$ (3.5)

We start by observing that, since $|P(\kappa)-\kappa|\leq\delta^{\epsilon}$,
then

$P(H_{i})\subset H_{i-1}\cup H_{i}\cup H_{i+1},$

where we have denoted by $H_{0}=H_{M+1}=\emptyset$. By induction, we have that

$\sharp\\{\kappa\in H_{i}:\Pi(\kappa)=1\\}=\\{\kappa\in
H_{i-1}:\Pi(\kappa)=2\\}.$ (3.6)

Thus we will call black those cubes for which $\Pi(\kappa)=1$, red those ones
for which $\Pi(\kappa)=2$. If we do not need to distinguish red and black
cubes, we will call them colored cubes. We rename the slices as follows:
$U_{1}=H_{2}$, $L_{1}=H_{3}$, $U_{2}=H_{4}$, $L_{2}=H_{5}$, and more generally
$L_{j}=H_{2j+1}$ and $U_{j}=H_{2j}$. Equation (3.9) in particular tells us
that the number of red cubes in $U_{j}$ is equal to the number of black cubes
in $L_{j}$, for all $j$.

The key idea in this step is that, if the colored cubes are distant, if we
follow the trajectory of a red cube, then it will be ’long’. We will see in a
while that this allows to get good volume estimates on the amount of colored
cubes, while the price to pay is the new constraint on the $L^{2}$-norm, as in
Proposition 3.6. This represents one of the major obstructions of this method,
as pointed out in the introduction.

More precisely: let us fix a red cube $\kappa\subset U_{j}$ with
$\Pi(\kappa)=2$ for some $j$. We define the _orbit_ of $\kappa$ as
$\\{P^{n}(\kappa)\\}$, with $n=0,1,2,\dots$. Clearly, for every red cube
$\kappa$, there exists $\bar{n}\geq 2$ such that $\Pi(P^{\bar{n}}(\kappa))=1$
and $P^{\bar{n}}(\kappa)\subset L_{j}$ (Figure 6). Moreover, without loss of
generality we can assume that all the cubes in the orbit $P^{j}(\kappa)$ for
$j=1,2,\dots,n$ live in the stripe $L_{j}$ (if not, we can simply cancel them
from the orbit: in this case we can refer to the new orbit as _reduced
orbit_). In particular this allows for the choice of $\bar{n}$ such that
$\Pi(P^{n}(\kappa))=0$ for $n=1,2,\dots,\bar{n}-1$. Since $\bar{n}$ depends on
$\kappa$, we will denote it by $\bar{n}(\kappa)$. We point out that, though
the main constructions are performed in $\nu=2$, the estimates will be
computed for a general dimension $\nu$.

Then we have the following

######  Lemma 3.10.

Let $P\in\mathcal{D}_{N}$ as in the statement of Theorem 3.9. Then

$\mathcal{L}^{\nu}\left\\{\bigcup_{j}\\{\kappa\subset
U_{j}:\Pi(\kappa)=2,|\kappa-P^{\bar{n}(\kappa)}(\kappa)|>\delta^{\epsilon}\\}\right\\}<\delta^{1-\frac{3}{2}\epsilon}.$
(3.7)

###### Proof.

We call $\ell_{n}(\kappa)=|P^{n}(\kappa)-P^{n-1}(\kappa)|$, where we recall
that $|\cdot|$ denotes the Euclidean distance. By the definition of the set
(3.7),

$\sum_{n=1}^{\bar{n}(\kappa)}\ell_{n}(\kappa)>\delta^{\epsilon},$

which holds by the triangular inequality.

We will denote by $\mathcal{O}_{j}$ the set of (reduced) orbits in $L_{j}$,
that is

$\mathcal{O}_{j}=\underset{\kappa\subset
U_{j},\Pi(\kappa)=2}{\bigcup}\cup_{n=1}^{\bar{n}(\kappa)}\\{P^{n}(\kappa)\\}=\underset{\kappa\subset
U_{j},\Pi(\kappa)=2}{\bigcup}O(\kappa),$

where we have called
$O(\kappa)=\cup_{n=1}^{\bar{n}(\kappa)}\\{P^{n}(\kappa)\\}$.

Finally, we define the set of orbits as

$\mathcal{O}=\cup_{j}\mathcal{O}_{j}.$

Clearly, by the assumption that the trajectories live in the stripe $L_{j}$,
we have that $\sharp\mathcal{O}_{j}=\sharp\\{\kappa\subset
U_{j}:\Pi(\kappa)=2\\}$. In particular, there is a one-to-one correspondence
between red cubes and reduced orbits $\kappa\leftrightarrow O(\kappa).$

We use the constraint on the $L^{2}$-norm to improve the estimate on the
volume of colored cubes by counting their orbits. We have that:

$\sqrt{\sum_{j}\sum_{\mathcal{O}_{j}}N^{-\nu}\sum_{n=1}^{\bar{n}(\kappa)}{\ell_{n}}^{2}(\kappa)}\leq\delta^{1-\frac{\epsilon}{2}}.$

By Jensen’s inequality, we have that, for every $O(\kappa)$, it holds

$\sum_{n=1}^{\bar{n}(\kappa)}\ell_{n}^{2}(\kappa)\geq\frac{\delta^{2\epsilon}}{\bar{n}(\kappa)}.$

In particular,

$\sqrt{\sum_{j}\sum_{\mathcal{O}_{j}}N^{-\nu}\frac{1}{\bar{n}(\kappa)}}\lesssim\delta^{1-\frac{3}{2}\epsilon}.$

We use again Jensen’s inequality, which yields

$\sum_{O(\kappa)\in
O_{j}}\bar{n}^{-1}(\kappa)\geq(\sharp\mathcal{O}_{j})^{2}\left(\sum_{O(\kappa)\in
O_{j}}\bar{n}(\kappa)\right)^{-1}\geq(\sharp\mathcal{O}_{j})^{2}(\delta^{\epsilon}N^{\nu})^{-1},$

where the last inequality follows by observing that the maximum amount of
cubes in the trajectory, over all trajectories, is less than the number of
total cubes in the stripes $U_{j}\cup L_{j}$ (again, everything holds up to
some constant depending only on the dimension). We conclude applying for the
third time Jensen’s inequality to the number of $j$ (recall that
$j\in\\{1,2,\dots,\frac{M}{2}\\}$), so that

$\delta^{1-\frac{3}{2}\epsilon}\geq\sqrt{\sum_{j}\sum_{\mathcal{O}_{j}}N^{-\nu}\frac{1}{\bar{n}(\kappa)}}\geq\sqrt{\sum_{j}\delta^{-\epsilon}N^{-2\nu}(\sharp\mathcal{\mathcal{missing}}{O}_{j})^{2}}\geq
N^{-\nu}\sharp\mathcal{O}.$ (3.8)

This inequality tells us that the number of colored cubes is, up to some
constant,

$\sharp\\{\kappa:\Pi(\kappa)\not=0\\}\leq\delta^{1-\frac{3}{2}\epsilon}N^{\nu}.$

∎

######  Remark 3.11.

From the computations of the previous corollary, we have immediately that
$\sharp O_{j}\lesssim\delta^{1-\epsilon}N^{\nu}$.

Figure 6: Every trajectory starting from a red cube in the slice $U_{\bar{j}}$
hits a black cube in the slice $L_{\bar{j}}$. This observation, together with
the constraint on the $L^{2}$-norm of the permutation, gives a reduced amount
of black and red cubes. Indeed we have that, before the black cube is reached,
a considerable amount of intermediate white cubes has to be moved by the
permutation itself.

As a corollary of the previous lemma, we get that

######  Corollary 3.12.

Let $P\in\mathcal{D}_{N}$ be as in the statement of Theorem 3.9 and let
$\epsilon\leq\frac{1}{\nu+1}$. Then there exists $\tilde{P}\in\mathcal{D}_{N}$
such that

  * •

The set

$\bigcup_{j}\\{\kappa\subset
U_{j}:\Pi(\kappa)=2,|\kappa-\tilde{P}^{n(\kappa)}(\kappa)|>\delta^{\epsilon}\\}=\emptyset;$

  * •

$L(P,\tilde{P})\lesssim\delta^{\frac{1}{2}-\frac{3\epsilon}{4}};$

  * •

$\|\tilde{P}-Id\|_{2}\lesssim\delta^{\frac{1}{2}-\frac{\epsilon}{4}}.$

###### Proof.

For simplicity we will assume that those red cubes for which
$P^{\bar{n}(\kappa)}(\kappa)$ is such that
$|P^{\bar{n}(\kappa)}(\kappa)-\kappa|\leq\delta^{\epsilon}$ are white. We will
get rid of them in the next results.

By the volume estimate obtained in the previous lemma, we have that the number
of colored subcubes is estimated by $\delta^{1-\frac{3}{2}\epsilon}N^{\nu}$.
With this observation at hand, we perform a discrete flow
$\\{\tilde{Z}_{j}\\}$ that acts simultaneously and independently in the
couples $U_{j}\cup L_{j}$, swapping red cubes with black cubes (first we
arrange red cubes in $U_{j}$ and respectively the black cubes in $L_{j}$, then
we swap them). Here, by definition of the discrete length functional (2.6),
and Corollary 3.5, the cost is computed by the square root of the volume of
colored cubes, which is the estimate above, times the size of the rectangle
where the flow is acting, in this case $1$, since the flow moves cubes in
$U_{j}\cup L_{j}$. This is clearly given by

$L\\{\tilde{Z}_{j}\\}\lesssim\delta^{\frac{1}{2}-\frac{3\epsilon}{4}}.$

After this step, in each stripe $U_{j}$ (resp. $L_{j}$) there are only white
cubes. Since we need to guarantee that $|\tilde{P}(\kappa)-\kappa|\leq
C\delta^{\epsilon}$, which is the main difficulty of this corollary, we make
the following

Assumption A : The volume of the colored subcubes such that
$|P(\kappa)-\kappa|>\delta^{\epsilon}$ in a stripe $U_{j}\cup L_{j}$ (given by
$\sharp\mathcal{O}_{j}$, see Remark 3.11) is less than the volume of a single
cube $\delta^{\epsilon\nu}$. In particular, the assumption can be read as
$\delta^{1-\epsilon}\leq\delta^{\epsilon\nu}$ which yields the bound
$\epsilon\leq\frac{1}{\nu+1}$.

We want to show that, thanks to the volume constraint in the above assumption
it is possible to guarantee that the white cubes do not move more than
$C\delta^{\epsilon}$ when we want these cubes to reach their original
position. Since this follow from a the same procedure presented in Proposition
3.6, we omit the details. Clearly, the cost here is given by

$\sim\delta^{\frac{1}{2}-\frac{3\epsilon}{4}}.$

Estimate on the $L^{2}$-norm. Also in this case, for the new permutation
$\tilde{P}$ the amount of cubes that we are moving is of the order of the
amount of black cubes $\delta^{1-\frac{3\epsilon}{2}}$ times
$\delta^{-\epsilon}$ (see Proposition 3.6). Thus the estimate on the
$L^{2}$-norm reads as

$\|\tilde{P}-Id\|^{2}_{2}\lesssim\delta^{1-\frac{\epsilon}{2}}.$

∎

######  Lemma 3.13.

Let $P\in\mathcal{D}_{N}$ be a permutation of the tiling $\mathcal{R}_{N}$ and
assume that $\|P-Id\|_{2}\leq\delta^{\frac{1}{2}-\frac{\epsilon}{4}}$ and that
$|P(\kappa)-\kappa|\leq\delta^{\epsilon}$ for every
$\kappa\subset\mathcal{R}_{N}$, where $\epsilon$ is the parameter chosen at
the beginning. Let $\Pi$ be the coloring defined in Equation (3.5). Then the
volume of colored subcubes can be estimated as

$|\\{\kappa:\Pi(\kappa)\not=0\\}|=N^{-\nu}\sharp\\{\kappa:\Pi(\kappa)\not=0\\}\lesssim\delta^{\frac{1}{3}-\frac{5\epsilon}{6}},$

where the inequality holds up to some positive constant depending only the
dimension.

###### Proof.

We start by observing that, since $|P(\kappa)-\kappa|\leq\delta^{\epsilon}$,
then

$P(H_{i})\subset H_{i-1}\cup H_{i}\cup H_{i+1},$

where we have denoted by $H_{0}=H_{M+1}=\emptyset$. By induction, we have that

$\sharp\\{\kappa\in H_{i}:\Pi(\kappa)=1\\}=\\{\kappa\in
H_{i-1}:\Pi(\kappa)=2\\}.$ (3.9)

Since the volume constraint is given up to a constant depending on the
dimension, we can assume to consider only red cubes in $H_{i}$ with $i$ odd
and black ones in $H_{i}$ with $i$ even (Figure 7). By the constraint on the
$L^{2}$-norm we observe that the maximum amount of colored subcubes is
realized by the permutation that gives rise to the coloring in Figure 7, where
the colored cubes accumulate around $H_{i}\cap H_{i+1}$, with
$i\in\\{1,2,\dots,M\\}$ odd. Indeed, observe that each slice $H_{i}$ is the
union of $M$ parallel slices $H_{j,i}$ with $j\in\\{1,2,\dots,M\\}$ whose
vertical side has size $N^{-1}$. Call therefore $R_{j}^{i}$, with $i$ odd, the
number of red cubes in the slice $H_{j,i}$. Our problem is to find the
configuration such that the number of colored cubes is maximum. Then, up to
some fixed constant, the constraint on the $L^{2}$ norm yields the following
estimates:

$\displaystyle\delta^{\frac{1}{2}-\frac{\epsilon}{4}}$
$\displaystyle\geq\sqrt{\sum_{i=1}^{M}N^{-\nu}N^{-2}(R^{i}_{1}+4R^{i}_{2}+9R^{i}_{3}+\dots+M^{2}R^{i}_{M})}$
$\displaystyle=\sqrt{N^{-\nu}N^{-2}(\sum_{i=1}^{M}R^{i}_{1}+4\sum_{i=1}^{M}R^{i}_{2}+9\sum_{i=1}^{M}R^{i}_{3}+\dots+M^{2}\sum_{i=1}^{M}R^{i}_{M})}$
$\displaystyle=\sqrt{N^{-\nu}N^{-2}(R_{1}+4R_{2}+9R_{3}+\dots+M^{2}R_{M})},$

where $R_{j}$ denotes the same of colored subcubes of the $j$-th slice of all
$H_{i}$. The maximum amount of the sum of colored subcubes, which is
$=\sum_{j=1}^{M}R_{j}$, is then trivially computed in the assumption $R_{j}$
is maximum for $j=1,\dots,\ell$, where $\ell$ has to be estimated thanks to
the constraint on the $L^{2}$-norm. We will call the number $\ell$ the
_height_ of this configuration. In particular, since each $R_{j}\leq
N^{\nu-1}M$, where we recall that $M=\delta^{-\epsilon}$, we have

$\sqrt{N^{-\nu-2}N^{\nu-1}\delta^{-\epsilon}(1+4+\dots+\ell^{2})}\leq\delta^{\frac{1}{2}-\frac{\epsilon}{4}}.$

Since

$1+4+9+\dots+\ell^{2}\sim\ell^{3},$

(where the asymptotics is up to a positive constant), we conclude that there
exists a positive constant, depending only on the dimension, such that

$\sqrt{N^{-3}\ell^{3}\delta^{-\epsilon}}\lesssim\delta^{\frac{1}{2}-\frac{\epsilon}{4}},$

so that

$\ell\leq\delta^{\frac{1}{3}+\frac{\epsilon}{6}}N.$ (3.10)

In particular, the total volume of the colored subcubes can be estimated
trivially as

$\ell
N^{-1}\delta^{-\epsilon}\lesssim\delta^{\frac{1}{3}-\frac{5\epsilon}{6}},$

which concludes the proof.

Figure 7: This figure represents the permutation that maximizes the amount of
colored subcubes.

∎

We are finally ready to give the proof of Theorem 3.9, where we will make use
of the previous estimate on the amount of maximum colored cubes. This proof
will combine Lemma 3.10, Corollary 3.12 and Lemma 3.13. Indeed, we first get
rid of distant cubes, then we arrange the close ones.

###### Proof of Theorem 3.9..

We divide $[0,1]^{\nu}$ into the horizontal slices $H_{1},H_{2}\dots,H_{M}$
defined above, where $M=\delta^{-\epsilon}$. Again, we remark that this proof
can be easily extended to higher dimension, but in order to avoid
technicalities we present it in dimension $\nu=2$. As before, we observe that,
since $|P(\kappa)-\kappa|\leq\delta^{\epsilon}$, then

$P(H_{i})\subset H_{i-1}\cup H_{i}\cup H_{i+1}.$

We consider the coloring $\Pi$ defined in Equation (3.5). We observed above
that, by induction, we have that

$\sharp\\{\kappa\in H_{i}:\Pi(\kappa)=1\\}=\\{\kappa\in
H_{i-1}:\Pi(\kappa)=2\\}.$

In particular, the number of red cubes in $U_{j}$ is equal to the number of
black cubes in $L_{j}$, for all $j$. By Corollary 3.12 we can assume that, up
to the cost of order $\delta^{\frac{1}{2}-\frac{3\epsilon}{4}}$, for every
slice $U_{j}$, for every red cube $\kappa$ in $U_{j}$ there is a black cube
$\kappa^{\prime}$ in $L_{j}$ such that
$|\kappa-\kappa^{\prime}|\leq\delta^{\epsilon}.$ We can apply Lemma 3.13,
which gives the maximum volume of colored cubes, since the vertical distance,
that is $|P(\kappa)_{2}-\kappa_{2}|\leq\delta^{\epsilon}$. Now we need to swap
red and black cubes. We construct the flow as illustrated below.

We fix some index $\bar{j}$ and a couple $U_{\bar{j}},L_{\bar{j}}$ pointing
out that the flow constructed in $U_{\bar{j}}\cup L_{\bar{j}}$ will be
performed simultaneously and independently on all the couples $U_{j},L_{j}$.
Our aim is to compute the cost for moving the red cubes in $U_{\bar{j}}$ into
the black cubes in $L_{\bar{j}}$, in such a way that the white cubes remain
white (that is, if $\kappa\subset U_{\bar{j}}$ with $\tilde{P}(\kappa)=0$,
then the resulting permutation $\tilde{\Pi}$ is such that
$\tilde{P}(\kappa)\in U_{\bar{j}}$). Moreover we want the white cubes not to
move during the process.

  * •

Consider the cubes $K_{1},K_{2},\dots K_{M}\in\mathcal{R}_{\delta^{\epsilon}}$
in the stripe $U_{\bar{j}}$, with $M=\delta^{-\epsilon}$ and
$\tilde{K}_{1},\tilde{K}_{2},\dots\tilde{K}_{M}\in\mathcal{R}_{\delta^{\epsilon}}$
those ones in the stripe $L_{\bar{j}}$, with
$\tilde{K}_{h}=K_{h}+\delta^{\epsilon}\mathbf{e}_{2}$. Fix
$h\in\\{1,2,\dots,M\\}$. Observe that we can design an elementary movement $Z$
that acts simultaneously and independently on each couple
$K_{h},\tilde{K}_{h}$ which swaps all red subcubes in $K_{h}$ for which there
exists a black cube in $\tilde{K}_{h}$ along its trajectory (see Lemma 3.10
together with Corollary 3.12), at a cost given by

$L(Z)\lesssim\sqrt{\delta^{\frac{1}{3}-\frac{5\epsilon}{6}}\delta^{2\epsilon}}=\delta^{\frac{1}{6}+\epsilon\frac{7}{12}}.$

This follows by Theorem 3.3 and Corollary 2.16, together with the estimate on
the $L^{2}$-norm found in the previous lemma and the simple definition of the
discrete Length functional (2.6). Observe that the white cubes contained in
$K_{h}$ (resp. $\tilde{K}_{h}$) remain confined in the cube $K_{h}$ (resp.
$\tilde{K}_{h}$), since each flow arrange the colored cubes in each
$K_{h}/\tilde{K}_{h}$ and then swap only colored cubes, leaving the white
cubes fixed. We can also assume the white cubes do not move (after the
swapping, we rearrange the white cubes as they were before it). See Figure 8.
The total cost then is given by

$L(Z)\lesssim\delta^{\frac{1}{6}+\frac{7\epsilon}{12}}.$

At the end of this procedure we do not have anymore red and black cubes, but
only white cubes. Moreover, $|P(\kappa)-\kappa|\leq\delta^{\epsilon}$. It is
clear that, in the case of any dimension, we have the same estimate.

Figure 8: The first step of the proof of Theorem 3.9 ensures that we can
perform a discrete flow in the arrays of
$K_{h}\cup\tilde{K}_{h}\cup\tilde{K}_{h+1}$, leaving the white cubes in
$\tilde{K}_{h}$ fixed.

Vertical Subdivision. It is clear that if we partition the stripes $U_{j}$,
$L_{j}$ into the cubes of the tiling $\mathcal{R}_{\delta^{\epsilon}}$ and we
apply the same considerations as before acting on those cubes that move from a
cube $K$ to a neighboring cube (see Figure 9), then the cost is computed in
the same way.

∎

####  3.2.3 Final Step.

Before proving the last theorem, we need to prove the last step.

######  Theorem 3.14.

Let $P\in\mathcal{D}_{N}$ be a permutation constant the tiling
$\mathcal{R}_{\delta^{\epsilon}}$. Then there exists a positive constant
$C=C(\nu)>0$ such that $\text{dist}(P,Id)\leq C(\nu)\delta^{\epsilon}.$

###### Proof.

For the proof of this result we use Shnirelman’s discrete distance with the
$S$-elementary movements (being equivalent to our distance, see Theorem 2.23).
We immediately have that

$\displaystyle\text{dist}^{S}_{\mathcal{D}_{N}}(P,Id)$
$\displaystyle\leq\sum_{j=1}^{T}\sqrt{\text{swap}(S_{j})}N^{-1-\frac{\nu}{2}}$
$\displaystyle{\lesssim}N^{\frac{\nu}{2}}N^{-1-\frac{\nu}{2}}T\lesssim(\delta^{\epsilon}N)N^{\frac{\nu}{2}}N^{-1-\frac{\nu}{2}}\lesssim\delta^{\epsilon}.$

Here, we have used Theorem 2.14 together with the remark that the permutation
is constant on the tiling. We have also used that the maximum number of swap
that can be performed simultaneously at each time step is $\sim N^{\nu}$.

∎

Figure 9: If we consider as red cubes those that are sent into the neighboring
cube $K_{(l+1)h}$, for each one of them there exists a black cube in the orbit
living in $K_{(l+1)h}$, thus we can swap them.

####  3.2.4 Proof of the main theorem

We finally collect all previous results in the proof of our main theorem, that
is

###### Proof of Theorem 3.1.

We fix our permutation $P$, then the cost is given by Step 1 (Proposition
3.6), Step $2$ (Theorem 3.9 and Step $3$ (Theorem 3.14), namely

$L(P,Id)\lesssim\max\left\\{\delta^{1-\epsilon},\delta^{\frac{1}{2}-\frac{3\epsilon}{4}},\delta^{\frac{1}{6}+\epsilon\frac{7}{12}},\delta^{\epsilon}\right\\},$

where $\epsilon\leq\frac{1}{1+\nu}$, because of Assumption $A$ in Corollary
3.12. In the case of dimension $\nu=2$ we have that the best choice is
$\epsilon=\frac{2}{7}$. We observe that for $\nu\geq 3$ the choice is
$\epsilon=\frac{1}{\nu+1}$.

∎

##  Appendix A Appendix

We consider an array $A$ of cubes of the tiling $\mathcal{R}_{N}$ and we are
interested in swapping distant cubes. As suggested by Shnirelman’s discrete
length functional, we expect that the cost for performing this swapping is
$\sim\sqrt{2N^{-\nu}(\ell(A)^{2}N^{-2})}$, where we recall that $\ell(A)$ is
the length of the array $A$. That is, the cost of the swapping is the square
root of the total volume of the two cubes times their distance squared. We
formalize this fact in the following lemma, where we prove that the swap of
two _distant_ cubes can be realized as the time-1 map of a divergence-free
vector field in $L^{1}_{t}L^{2}_{x}$.

The main observation here is that the cost for swapping the two cubes depends
only on their volume and on their mutual distance, not on the volume of the
intermediate cubes. With reference to Figure 10

Figure 10: Swapping of distant cubes

the flow particles travel along pipes, leaving the particles of the
intermediate cubes in their original position. We remark that, though all the
proofs are given in dimension $\nu=2$ to avoid technicalities, the statement
will be given for any dimension $\nu$.

######  Lemma A.1.

Let us fix an array $A\subset\mathcal{R}_{N}$ of length $\ell(A)=M$ with
$M\geq 1$. If we denote $A=[\kappa_{1},\dots,\kappa_{M}]$, then there exists a
divergence-free vector field $\mathbf{v}\in
L^{1}([0,1],L^{2}([0,1]^{\nu}))\cap
L^{1}([0,1],\operatorname{BV}([0,1]^{\nu}))$ with the following property: if
$X:[0,1]^{\nu}\rightarrow[0,1]^{\nu}$ denotes the time-1 map of the vector
field $\mathbf{v}$, then there exists a positive constant $C>0$, independent
of $M,N$ such that

  1. 1.

$\|\mathbf{v}\|_{L^{1}_{t}L^{2}_{x}}\leq C\sqrt{N^{-\nu-2}M^{2}}$;

  2. 2.

the map $X$ translates $\kappa_{1}$ into $\kappa_{M}$ (and viceversa), namely

$X(x)=\begin{cases}(x_{1}+MN^{-1}-N^{-1},\dots,x_{\nu-1},x_{\nu}),\quad
x\in\text{int}(\kappa_{1}),\\\
(x_{1}+N^{-1}-MN^{-1},\dots,x_{\nu-1},x_{\nu})\quad
x\in\text{int}(\kappa_{M}),\\\ x\quad\text{otherwise}.\end{cases}$

###### Proof.

We give the proof for $\nu=2$, the extension to higher dimension being
straightforward. Fix $\epsilon>0$ to be chosen later in order to impose the
incompressibility condition on the vector field $\mathbf{v}$. Call

$a=\frac{\epsilon}{\epsilon+N^{-1}},\qquad b=aMN^{-1},\qquad c=N^{-1}-b;$

then define the following four sets:

$A_{\epsilon}=\left\\{(x,y)\in\mathbb{R}^{2}:0\leq
y\leq\epsilon,\quad\frac{y}{a}\leq x\leq\frac{y-b}{-a}\right\\},$
$B_{\epsilon}=\left\\{(x,y)\in\mathbb{R}^{2}:MN^{-1}-N^{-1}-\epsilon\leq x\leq
MN^{-1},\quad-ax+b\leq y\leq ax+N^{-1}-b\right\\},$
$C_{\epsilon}=\left\\{(x,y)\in\mathbb{R}^{2}:N^{-1}-\epsilon\leq y\leq
N^{-1},\quad-\frac{y-N^{-1}}{a}\leq x\leq\frac{y-c}{a}\right\\},$
$D_{\epsilon}=\left\\{(x,y)\in\mathbb{R}^{2}:0\leq x\leq N^{-1}+\epsilon,\quad
ax\leq y\leq-ax+N^{-1}\right\\}.$

In each one of these sets we define a shear vector field:

${\mathbf{v}_{1}}(x,y)=\begin{cases}\left(-\frac{2}{a}y+\frac{b}{a},0\right),\quad(x,y)\in\text{int}(A_{\epsilon}),\\\
\\\ \left(0,2ax+N^{-1}-2b\right),\quad(x,y)\in\text{int}(B_{\epsilon}),\\\ \\\
\left(-2\frac{y}{a}+\frac{N^{-1}}{a}+\frac{c}{a},0\right),\quad(x,y)\in\text{int}(C_{\epsilon}),\\\
\\\
\left(0,2ax-N^{-1}\right),\quad(x,y)\in\text{int}(D_{\epsilon}).\end{cases}$
(A.1)

It can be proved that, with the choice of

$\epsilon=\frac{N^{-1}}{M-1},$

the vector field is incompressible. In particular, we remark that $\epsilon$
decreases as the distance between the two cubes increases.

Step 1. Since we need to construct the flow that swaps the first and the last
cube of the array, we consider $F=A_{\epsilon}\cup B_{\epsilon}\cup
C_{\epsilon}\cup D_{\epsilon}\setminus F^{\prime}$, where $F^{\prime}$ is the
blue set of Figure 11.

Figure 11: The flow is performed inside the set $A_{\epsilon}\cup
B_{\epsilon}\cup C_{\epsilon}\cup D_{\epsilon}\setminus F^{\prime},$ where
$F^{\prime}$ denotes the blue frame.

We consider the flow associated to the vector field defined above, restricted
to the set $F$, that is the solution to the Cauchy Problem

$\begin{cases}\dot{X}(t,(x,y))=\mathbf{v_{1}}(X(t,(x,y))),\\\
X(0,(x,y))=(x,y),\end{cases}(x,y)\in F.$

We observe that in the time interval $t\in[0,2]$ the flow map $X_{t=2}$ has
rotated counterclockwise the set $F$ of an angle $\pi$, leaving the
intermediate region $A\setminus F$ fixed (see Figure 12). We estimate the
$L^{2}$-norm of the vector field as follows

$\|\mathbf{v_{1}}\|^{2}_{L^{2}_{x}}\leq\|\mathbf{v}_{1}\|_{\infty}^{2}|F|\leq(4M^{2}N^{-2})4N^{-2},$

where we have used that $|F|=2|\kappa_{1}|+2\frac{N^{-1}}{M}((M-2)N^{-1}).$

Figure 12: In the time interval $t\in[0,2]$ the flow has rotated
counterclockwise the set $F$ of an angle $\pi$. In order to recover the
original permutation we have to counter-rotate the set $F$.

Step 2. Here we define the counter rotation vector field. We call

$A^{\prime}_{\epsilon}=A_{\epsilon}\setminus(F^{\prime}\cup(\kappa_{1}\cup\kappa_{M}))=[N^{-1},MN^{-1}-N^{-1}]\times\left[0,\frac{N^{-1}}{M}\right],$
$C^{\prime}_{\epsilon}=C_{\epsilon}\setminus(F^{\prime}\cup(\kappa_{1}\cup\kappa_{M}))=[N^{-1},MN^{-1}-N^{-1}]\times\left[N^{-1}-\frac{N^{-1}}{M},N^{-1}\right].$

We consider the vector field

$\mathbf{v_{2}}=\mathbf{v}_{\kappa_{1}}+\mathbf{v}_{\kappa_{M}}+\mathbf{v}_{A^{\prime}_{\epsilon}}+\mathbf{v}_{C^{\prime}_{\epsilon}},$

where we have used the rotation vector field (Equation (2.3)) in the interior
of each one of the four sets
$\kappa_{1},\kappa_{M},A^{\prime}_{\epsilon},C^{\prime}_{\epsilon}.$ This
vector field rotates, in a interval of time $\Delta t=2$, the four sets
counterclockwise of an angle $\pi$, as illustrated in Figure. If we estimate
the $L^{2}$-norm of this vector field we find that

$\|\mathbf{v_{2}}\|^{2}_{L^{2}_{x}}\leq
2\|\mathbf{v}_{\kappa_{1}}\|^{2}_{\infty}N^{-2}+2\|\mathbf{v}_{A^{\prime}_{\epsilon}}\|_{\infty}^{2}|A^{\prime}_{\epsilon}|\leq
4M^{2}N^{-4}.$

We collect Step 1 and Step 2 defining the vector field of the statement, that
is

$\mathbf{v}(t,x,y)=\begin{cases}8\mathbf{v_{1}}(x,y),\quad
t\in\left[0,\frac{1}{4}\right),\\\ 8\mathbf{v_{2}}(x,y),\quad
t\in\left[\frac{1}{4},\frac{1}{2}\right).\end{cases}$

We could stop the procedure here, since the flow map $T=X_{t=\frac{1}{2}}$
associated to vector field $\mathbf{v}$ has the following properties:

  * •

$T(\kappa_{1})=\kappa_{M}$ and $T(\kappa_{M})=\kappa_{1}$ and
$T\llcorner_{\kappa_{i}}$ with $i=1,M$ is a translation;

  * •

$T(\kappa_{j})=\kappa_{j}$ for $j\not=1,M$.

So that the map $T$ is a permutation of the cubes of the array. We point out
that $T\llcorner_{\kappa_{j}}$ with $j\not=1,M$ is not the identity. In steps
$3$ and $4$ we show how to overcome this issue. Step 3. In this step and the
following we correct the map $T$ of the previous two steps such that

$T\llcorner_{\kappa_{j}}=Id,\quad\text{a.e. }x,\quad j\not=1,M.$

Accordingly to the reference figure, we define

$\mathbf{v_{3}}=\sum_{j=2}^{M-1}\mathbf{v}_{\kappa_{j}}.$

Here the estimate of the $L^{2}$-norm reads as follows:

$\|\mathbf{v_{3}}\|^{2}_{L^{2}_{x}}\leq(M-2)\|v_{\kappa_{j}}\|^{2}_{\infty}|\kappa_{j}|\leq
M^{2}N^{-4}.$

Step 4. For this last step we define

$\kappa_{j}^{A}=\kappa_{j}\cap
A^{\prime}_{\epsilon},\qquad\kappa_{j}^{C}=\kappa_{j}\cap
C^{\prime}_{\epsilon},$

and finally

$\mathbf{v_{4}}=\sum_{j=2}^{M-1}\left(\mathbf{v}_{\kappa_{j}^{A}}+\mathbf{v}_{\kappa_{j}^{C}}+\mathbf{v}_{\kappa_{j}\setminus(\kappa_{j}^{A}\cup\kappa_{j}^{c})}\right).$

Here, the computation of the $L^{2}$-norm is the same as in Step 3.

Finally the vector field of the statement is defined as

$\mathbf{v}(t,x,y)=\begin{cases}8\mathbf{v_{1}}(x,y),\quad
t\in\left[0,\frac{1}{4}\right),\\\ 8\mathbf{v_{2}}(x,y),\quad
t\in\left[\frac{1}{4},\frac{1}{2}\right),\\\ 8\mathbf{v_{3}}(x,y),\quad
t\in\left[\frac{1}{2},\frac{3}{4}\right),\\\ 8\mathbf{v_{4}}(x,y),\quad
t\in\left[\frac{3}{4},1\right).\\\ \end{cases}$

This vector field is clearly $\operatorname{BV}$, divergence-free and
satisfies the assumptions of the statement. Moreover, we have that

$\displaystyle\|\mathbf{v}\|_{L^{1}_{t}L^{2}_{x}}\leq
2\sum_{h=1}^{4}\|\mathbf{v_{h}}\|_{L^{2}_{x}},$

which, together with the estimates obtained for
$\|\mathbf{v_{h}}\|_{L^{2}_{x}}$, gives the statement with constant $C=20$,
that clearly depends only on the dimension $\nu=2$. ∎

## References

  * [1] Ambrosio L.  Transport equation and Cauchy problem for BV vector fields.  Inventiones Mathematicae, (158):227–260, 2004.
  * [2] Arnold V.I., Khesin B. A.  Topological methods in hydrodynamics.  1998,2021.
  * [3] Bianchini S., Zizza M.  Properties of Mixing $\operatorname{BV}$ vector fields.  Communications in Mathematical Physics, 402:1953–2009, 2023.
  * [4] Brenier Y.  Various formulations and approximations of incompressible fluid motions in porous media.  Annales mathématiques du Québec, 46:195–206.
  * [5] Brenier Y.  The least action principle and therelated concept of generalized flows for incompressible perfect fluids.  Journal of the American Mathematical Society, 2(2), 1989.
  * [6] Kim D.  Sorting on graphs by adjacent swaps using permutation groups.  Computer Science Review, 22, 2016.
  * [7] Lax, P.D.  Approximation of measure preserving transformations.  Communications on Pure and Applied Mathematics, 24:133–135, 1971.
  * [8] Shnirelman A.  The geometry of the group of diffeomorphisms and the dynamics of an ideal incompressible fluid.  Math. USSR Sb., 56:82–109, 1985.
  * [9] Shnirelman A.  Generalized fluid flows, their approximation and applications.  Geom. and Funct. Analysis, pages 586–620, 1994.
  * [10] Zaefferer, M., Stork J, Bartz-Beielstein, T.  Distance Measures for Permutations in Combinatorial Efficient Global Optimization.  Bartz-Beielstein, T., Branke, J., Filipič, B., Smith, J. (eds) Parallel Problem Solving from Nature – PPSN XIII. PPSN 2014. Lecture Notes in Computer Science, 8672, 2014.