# Quantitative Destruction of Lagrangian Torus

Lin Wang

3.5cm3.5cm2cm2cm

School of Mathematics and Statistics,

Beijing Institute of Technology, Beijing 100081, China.

E-mail address<EMAIL_ADDRESS>
> Abstract. Let $P_{N}$ be a trigonometric polynomial of degree $N$ and
> satisfy $\|P_{N}\|_{C^{r}}\leq\varepsilon$. If $P_{N}$ destroys the
> Lagrangian torus with the rotation vector $\omega$ of an integrable
> Hamiltonian system, then what are the relation among $\varepsilon$, $N$, $r$
> and the arithmetic property of $\omega$? By addressing this, we provide
> quantitatively higher dimensional generalizations of the remarkable results
> on destruction of invariant circles for the area-preserving twist map by
> Herman [21] in 1983 and Mather [28] in 1988.

> Key words. Lagrangian tori, Hamiltonian systems, Trigonometric polynomials

> AMS subject classifications (2020). 37J40, 37E40

## 1\. Introduction

In 2013, C.-Q. Cheng and the author [12] constructed an example to show that:
given an integrable Hamiltonian systems with $d$ degrees ($d\geq 2$) of
freedom, each invariant Lagrangian torus can be destroyed by an arbitrarily
small perturbation in the $C^{r}$ topology with $r<2d$.

That result is almost sharp due to the fact proved by Pöschel [32] (see also
Salamon [34]): the KAM torus is preserved under an arbitrarily small
perturbation in the $C^{r}$ topology with $r>2d$.

Loosely speaking, a KAM torus is a special kind of Lagrangian torus. To
distinguish the dynamics on the Lagrangian torus and the KAM torus, let us
recall their definitions. We use, once and for all, $\mathbb{T}^{d}$ to denote
a $d$-dimensional flat torus. Let
$H:\text{T}^{\ast}\mathbb{T}^{d}\to\mathbb{R}$ be a $C^{r}$ ($r\geq 2$)
Hamiltonian, and
$\Phi_{H}^{t}:\text{T}^{\ast}\mathbb{T}^{d}\to\text{T}^{\ast}\mathbb{T}^{d}$
be its flow.

######  Definition 1.1 (KAM torus)

$\bar{\mathcal{T}}^{d}$ is called a $d$-dimensional KAM torus if

  * •

$\bar{\mathcal{T}}^{d}$ is a graph over $\mathbb{T}^{d}$;

  * •

$\bar{\mathcal{T}}^{d}$ is invariant under the Hamiltonian flow
$\Phi_{H}^{t}$;

  * •

there exists a diffeomorphism $\phi:\
\mathbb{T}^{d}\rightarrow\bar{\mathcal{T}}^{d}$ such that
$\phi^{-1}\circ\Phi_{H}^{t}\circ\phi=R_{\omega}^{t}$ for any $t\in\mathbb{R}$,
where $R_{\omega}^{t}:\ x\mapsto x+\omega t$ and $\omega$ is called the
rotation vector of $\bar{\mathcal{T}}^{d}$.

The Lagrangian torus with the rotation vector $\omega$ is defined as follows.

######  Definition 1.2 (Lagrangian torus)

$\mathcal{T}^{d}$ is a called a $d$-dimensional Lagrangian torus with the
rotation vector $\omega$ if

  * •

$\mathcal{T}^{d}$ is a flow-invariant Lagrangian graph over $\mathbb{T}^{d}$;

  * •

each orbit on $\mathcal{T}^{d}$ has the rotation vector $\omega$.

###### Remark 1.3

From geometric point of view, a submanifold in a $2d$-dimensional symplectic
manifold is called a Lagrangian torus if it is homeomorphic to the torus
$\mathbb{T}^{d}$ and the symplectic form vanishes on it.

In general, the rotation vector of certain orbit on an invariant torus is not
well defined. See the remarkable example by Fürstenberg [19]. Even though the
rotation vector of each orbit exists, the rotation vector of the Lagrangian
torus is not always unique. For instance, the Lagrangian torus may contain
several orbits with different rotation vectors. Various invariant Lagrangian
graphs can be constructed easily by using Mañé’s Lagrangian.

###### Example 1.4

Let $\mathbb{T}^{d}$ be a flat torus. Denote the local coordinates of
$\mathrm{T}^{\ast}\mathbb{T}^{d}$ by
$(x,y)=(x_{1},\ldots,x_{d},y_{1},\ldots,y_{d})$. We consider the Hamiltonian
$H:\mathrm{T}^{*}\mathbb{T}^{d}\to\mathbb{R}$ given by

$H(x,y):=\frac{1}{2}\|y\|^{2}+\langle y,\chi(x)\rangle.$

Here we fix, once and for all, $\|\cdot\|$ to denote the norm in the tangent
and cotangent space induced by the flat metric on $\mathbb{T}^{d}$. This
example is inspired by Nemitsky and Stepanov [30]. The associated Lagrangian
is so called Mañé’s Lagrangian:

$L(x,\dot{x}):=\frac{1}{2}\|\dot{x}-\chi(x)\|^{2},$

where the vector field is constructed as follows:

$\chi(x):=\alpha\Psi(x),$

where $\alpha=(\alpha_{1},\ldots,\alpha_{d})$ is a non-resonant vector (see
Definition 1.5 below), and $\Psi(x)$ is a $C^{\infty}$ function satisfying

$\Psi(x_{0})=0,\ 0<\Psi(x)\leq 1,\ \forall
x\in\mathbb{T}^{d}\backslash\\{x_{0}\\},\
\int_{\mathbb{T}^{d}}\frac{dx}{\Psi(x)}=+\infty.$

By [30, Section 6.16], the invariant torus $\mathcal{T}^{d}$ coincides with
the closure of the recurrent points, but $\delta_{x_{0}}$ is the unique
ergodic measure.

Note that the constant function is a classical solution of $H(x,Du(x))=0$.
Then $\mathcal{T}^{d}$ coincides with 0-section of
$\mathrm{T}^{*}\mathbb{T}^{d}$, which implies it is a Lagrangian graph. In
fact, it is a $C^{\infty}$ graph based on the construction of $\chi(x)$. By
[31, Theorem 2.13], $\mathcal{T}^{d}$ is also the Aubry set in view of Aubry-
Mather and weak KAM theory.

In this note, we revisit the converse KAM result in [12] from a quantitative
point of view. More precisely, we consider the following question.

  * •

Question: Let $P_{N}$ be a trigonometric polynomial of degree $N$ and satisfy
$\|P_{N}\|_{C^{r}}\leq\varepsilon$. If $P_{N}$ destroys the Lagrangian torus
with the rotation vector $\omega$ of an integrable Hamiltonian system, then
what are the relation among $\varepsilon$, $N$, $r$ and the arithmetic
property of $\omega$?

To state an answer to this question precisely, we recall some arithmetic
properties of rotation vectors.

######  Definition 1.5 (resonant vector)

A vector $\omega\in\mathbb{R}^{d}$ is called resonant if there exists
$k\in\mathbb{Z}^{d}\backslash\\{0\\}$ such that $\langle\omega,k\rangle=0$.
Otherwise, it is called non-resonant.

For $k:=(k_{1},k_{2},\ldots,k_{d})$, we use $|\cdot|$ to denote Euclidean
norm, i.e. $|k|=(\sum_{j=1}^{d}k_{i}^{2})^{1/2}$. By the Dirichlet
approximation ([11, Lemma 2.1]), for any given vector
$\omega\in\mathbb{R}^{d}$ with $d\geq 2$, there is a sequence of integer
vectors $k_{n}\in\mathbb{Z}^{d}$ with $|k_{n}|\rightarrow\infty$ as
$n\rightarrow\infty$ such that

(1.1) $\left|\langle\omega,k_{n}\rangle\right|<\frac{C}{|k_{n}|^{d-1}},$

where $C$ is a constant independent of $n$. If $\omega$ is non-resonant, this
sequence contains infinitely many integer vectors.

By Herman [24, Proposition 3.2,Theorem 8.14], a KAM torus with non-resonant
rotation vector must be a Lagrangian torus, and a flow-invariant $C^{0}$
Lagrangian graph must be Lipschitz continuous. Here $\mathcal{T}^{d}$ is
called a $C^{0}$ Lagrangian graph if

$\mathcal{T}^{d}=(x,c+D\eta(x)),$

where $\eta:\mathbb{T}^{d}\to\mathbb{R}$ is a $C^{1}$ function,
$c\in\mathbb{R}^{d}$ is a constant vector and
$D\eta:=(\frac{\partial\eta}{\partial
x_{1}},\dots,\frac{\partial\eta}{\partial x_{d}})$. On the contrary, a flow-
invariant Lipschitz Lagrangian torus may not be a KAM torus. If the rotation
vector is a Liouvillean type (see Definition 1.6 below), those kinds of
Lagrangian tori can be constructed by the celebrated AbC (approximation by
conjugation) method (see [2, 16, 25, 26]). If the rotation vector is a
Diophantine type, one can refer to [4, 6] for the construction of non-
differentiable invariant circles for area-preserving twist maps. By using
similar idea of Example 1.4, one can obtain topological mixing Lagrangian
torus in light of [17, 27]. According to Definition 1.1, all of the Lagrangian
tori mentioned above are not KAM tori.

######  Definition 1.6 ($\tau$-well approximable vector)

A vector $\omega\in\mathbb{R}^{d}$ is called a $\tau$-well approximable if
there exists a positive constant $C$ as well infinitely many integer vectors
$k_{n}\in\mathbb{Z}^{d}$ such that

(1.2) $|\langle\omega,k_{n}\rangle|\leq\frac{C}{|k_{n}|^{d-1+\tau}}.$

A non-resonant $\omega$ is called a Liouvillean type if it is $\tau$-well
approximable for all $\tau>0$. Otherwise, it is called a Diophantine type.

It is known ([10]) that the set of $\tau$-well approximable $d$-dimensional
vector has the Hausdorff dimension $d-2+\frac{d}{d+\tau}$ for $d\geq 2$ and
$\tau>0$.

Given any $u\in C^{r}(\mathbb{T}^{d})$. Let us recall the $C^{r}$-norm:

$\|u\|_{C^{r}}:=\max_{|\alpha|\leq
r}\max_{x\in\mathbb{T}^{d}}|D^{\alpha}u(x)|,$

where $\alpha:=(\alpha_{1},\ldots,\alpha_{n})$,
$|\alpha|:=\alpha_{1}+\cdots+\alpha_{n}$. Given any $u\in
C^{\infty}(\mathbb{T}^{d})$, define

$\|u\|_{C^{\infty}}:=\sum_{k\in\mathbb{N}}\frac{\arctan(\|u\|_{k})}{2^{k}},$

which is not a norm. Endow the space $C^{\infty}(\mathbb{T}^{d})$ with the
translation invariant metric $\|u-v\|_{C^{\infty}}$. The $C^{r}$ (resp.
$C^{\infty}$) topology is induced by the $C^{r}$-norm (resp. the translation
invariant metric). For simplicity, we use $u\preceq v$ (resp. $u\succeq v$) to
denote $u\leq Cv$ (resp. $u\geq Cv$) for some positive constant $C$. We use
$u\sim v$ to denote $\frac{1}{C}v\leq u\leq Cv$ for some positive constant
$C$. The main result is stated as follows.

###### Theorem 1.7

Let $H_{0}:\mathrm{T}^{\ast}\mathbb{T}^{d}\to\mathbb{R}$ be an integrable
Hamiltonian system with $d$ degrees of freedom given by

$H_{0}(y):=\frac{1}{2}\|y\|^{2}.$

Given $0<\varepsilon\ll 1$, let $\omega$ be a $\tau$-well approximable
rotation vector. Then the Lagrangian torus with the rotation vector $\omega$
of the integrable system $H_{0}$ can be destroyed by a trigonometric
polynomial perturbation $P_{N}(x)$ satisfying $\|P_{N}\|_{C^{r}}\leq\epsilon$
with $r<2d+2\tau$. Moreover, given $r\in[{0},2d+2\tau)$, there exists $P_{N}$
of degree

$N=O\left(\epsilon^{-\frac{d+\tau+1}{2d+2\tau-r}}\right)$

with $\|P_{N}\|_{C^{r}}\sim\epsilon$ such that $H_{0}(y)+P_{N}(x)$ admits no
Lagrangian torus with $\omega$. In particular, if $\omega$ is a Liouvillean
type, the Lagrangian torus with $\omega$ can be destroyed by $P_{N}$ of degree
$N=O\left({{\epsilon}^{-1/2}}\right)$ satisfying
$\|P_{N}\|_{C^{\infty}}\preceq\epsilon$.

Theorem 1.7 is optimal for $d=2$ by Herman’s result [22] on the existence of
the invariant circle with constant type frequency. It is still open if the KAM
torus can be preserved under a small perturbation in the $C^{2d}$ topology for
$d>2$. Recently, Pöschel [33] obtained a KAM result with lower regularity for
perturbed (not Hamiltonian) vector fields. We also refer the reader to [1, 35]
for recent progress on Hamiltonian systems from KAM perspective.

In 1988, Mather [28] proved a remarkable result on destruction of the
invariant circle with Liouvillean frequency for area-preserving twist maps in
the $C^{\infty}$ topology. Theorem 1.7 provides a quantitatively higher
dimensional generalization of Mather’s result. Meanwhile, it also provides a
similar kind of generalization of Herman’s celebrated result [21] on
destruction of the invariant circle with Diophantine frequency in the $C^{r}$
($r<3$) topology. We refer the reader to [18] (resp. [8]) for the issue on
destruction of invariant circles (resp. Lagrangian tori) in the real-analytic
topology.

Inspired by Bessi [8], we use the variational method developed by Mather [29]
to prove Theorem 1.7. An autonomous Hamiltonian is called a Tonelli
Hamiltonian if it satisfies strictly convexity and superlinearity with respect
to momentum. Correspondingly, a Tonelli Lagrangian can be defined by the
Legendre transformation. For Tonelli Hamiltonian systems, if a flow-invariant
Lagrangian torus is Hamiltonianly isotopic to the zero-section, it is the
graph over $\mathbb{T}^{d}$ (see [3, 9]). It was also shown by [14] that the
KAM torus with a given non-resonant rotation vector is unique in this setting.

######  Definition 1.8 (action minimizing curve)

An absolutely continuous curve $\gamma\in
C^{ac}([t_{1},t_{2}],\mathbb{T}^{d})$ is called an action minimizing curve if

$\int_{t_{1}}^{t_{2}}L(\gamma(t),\dot{\gamma}(t))dt\leq\int_{t_{1}}^{t_{2}}L(\bar{\gamma}(t),\dot{\bar{\gamma}}(t))dt,$

for every $\bar{\gamma}\in C^{ac}([t_{1},t_{2}],\mathbb{T}^{d})$ satisfying

  * •

$\gamma(t_{1})=\bar{\gamma}(t_{1})$, $\gamma(t_{2})=\bar{\gamma}(t_{2})$;

  * •

$\gamma$ and $\bar{\gamma}$ are in the same homotopy class. Equivalently,
their lifts to $\mathbb{R}^{d}$ connect the same points.

Based on [29], the action minimizing curves always exist and satisfy the
Euler-Lagrange equation generated by $L$. For Tonelli Hamiltonians, a
classical result by Herman [24] asserts that each orbit on the invariant
Lipschitz Lagrangian graph is an action minimizing curve. The Lagrangian torus
with resonant rotation vector is too fragile to be preserved unless the system
is integrable (see [5]). Correspondingly, it is sufficient to consider how to
destroy the Lagrangian torus with the non-resonant rotation vector.

In this note, we only need that the Lagrangian torus with the non-resonant
rotation vector satisfies the following condition:

  * •

it is a flow-invariant Lagrangian graph over $\mathbb{T}^{d}$;

  * •

there exists a dense orbit with the rotation vector $\omega$.

Equivalently, it is a flow-invariant, topologically minimal Lagrangian graph
over $\mathbb{T}^{d}$. To destroy this kind of torus, it is sufficient to
prove that there exists a small neighborhood of certain point on the
Lagrangian torus such that no action minimizing curve passes through.

###### Remark 1.9

In the late 1980s, Herman announced a result on the non-existence of the
Lagrangian torus with a given rotation vector (see [23, Theorem 13.1]), where
the torus is required to support a uniquely ergodic invariant measure. That
condition implies each orbit on the torus has the same rotation vector. In
this note, we only require that the Lagrangian torus is topologically minimal,
which is weak than the measure theoretic condition (see [20, XIII, Proposition
1.3] for a constructive example).

The note is organized as follows. In Section 2, we introduce a change of
coordinates to reduce the Lagrangian torus with a general rotation vector
$\omega$ to certain torus with “controlled” first two components of $\omega$.
In Section 3, we give a construction of the trigonometric polynomial
perturbation by using an enhanced version of Jackson’s approximation. In
Section 4, we reduce Theorem 1.7 to Proposition 4.1, and recall some facts
about the estimates on the action of the pendulum and the speed of the action
minimizing orbit. In Section 5, we complete the proof of Proposition 4.1.
Compared to [12], an obvious new obstruction in this note is that one can not
localize the trigonometric polynomial perturbation, which behaves quite
different from the bump function. Accordingly, more careful analysis,
especially for the construction of the perturbation and the proof of
Proposition 4.1 below, is needed to achieve the optimal and quantitative
result.

## 2\. The change of coordinates

The system we consider consists of one pendulum, a rotator with $d-1$ degrees
of freedom and a perturbation coupling of them.

We are concerned with a sequence of Hamiltonian functions

(2.1) $H_{n}(x,y)=\frac{1}{2}\|y\|^{2}-P_{N}(x),$

where $N$ (depending on $n$) denotes the degree of the trigonometric
polynomial $P_{N}(x)$. Since $H_{n}$ is quadratic with respect to $y$, by the
Legendre transformation, the Lagrangian function associated to $H_{n}$ is

(2.2) $L_{n}(x,\dot{x})=\frac{1}{2}\|\dot{x}\|^{2}+P_{N}(x),$

where $\dot{x}=\frac{\partial H_{0}}{\partial y}$. The following Lemma was
proved in [12].

###### Lemma 2.1

For any $k_{n}\in\mathbb{Z}^{d}\backslash\\{0\\}$ satisfying (1.2), there
exists an integer vector $k^{\prime}_{n}\in\mathbb{Z}^{d}$ such that

(2.3) $\langle
k_{n},k^{\prime}_{n}\rangle=0,\quad|k^{\prime}_{n}|\sim|k_{n}|\quad\text{and}\quad|\langle
k^{\prime}_{n},\omega\rangle|\sim|k_{n}|.$

We choose two sequences of $\\{k_{n}\\}_{n\in\mathbb{N}}$ and
$\\{k^{\prime}_{n}\\}_{n\in\mathbb{N}}$ based on Lemma 2.1. In addition,
select $d-2$ integer vectors $l_{n3},\ldots,l_{nd}$ such that
$k_{n},k^{\prime}_{n},l_{n3},\ldots,l_{nd}$ are pairwise orthogonal. Let

(2.4) $K_{n}:=(k_{n},k^{\prime}_{n},l_{n3},\ldots,l_{nd})^{t}.$

We choose the change of the coordinates

(2.5) $q=K_{n}x.$

Let $p$ denote the dual coordinate of $q$ in the sense of Legendre
transformation, i.e. $p=\frac{\partial L}{\partial\dot{q}}$. It follows that
$y=K^{t}_{n}p$, where $K^{t}_{n}$ denotes the transpose of $K_{n}$. Let

$\Phi_{n}:=\begin{pmatrix}K_{n}&\ \\\ \ &K^{-t}_{n}\end{pmatrix},$

then $(q,p)^{t}=\Phi_{n}(x,y)^{t}$. Let

$J_{0}:=\begin{pmatrix}\textbf{0}&\textbf{1}\\\
-\textbf{1}&\textbf{0}\end{pmatrix},$

where 1 denotes a $d\times d$ unit matrix. It is easy to verify that
$\Phi_{n}^{t}J_{0}\Phi_{n}=J_{0}$. Hence, $\Phi_{n}$ is a symplectic
transformation in the phase space $\mathrm{T}^{*}\mathbb{T}^{d}$. In
particular, we have

(2.6) $\begin{cases}q_{1}=\langle k_{n},x\rangle,\\\ q_{2}=\langle
k^{\prime}_{n},x\rangle.\end{cases}$

In the new coordinates, the rotation vector corresponding to $\omega$ is given
by $\omega^{\prime}=K_{n}\omega$. From (1.2) and (2.3), it follows that

(2.7)
$|\omega^{\prime}_{1}|\preceq\frac{1}{|k_{n}|^{d+\tau-1}},\qquad|\omega^{\prime}_{2}|\sim|k_{n}|.$

For the simplicity of notations and without ambiguity, we will still write the
rotation vector by $\omega$ instead of $\omega^{\prime}$ in the new
coordinates. In addition, we will also use the same notation to denote the
rotation vector of the orbit on the torus and its lift to $\mathbb{R}^{d}$.

###### Lemma 2.2

If the Hamiltonian flow generated by $\check{H}_{n}(x,y)$ admits a Lagrangian
torus with the rotation vector $\omega$, then the Hamiltonian flow generated
by $\hat{H}_{n}(q,p)$ also admits a Lagrangian torus with the rotation vector
$K_{n}\omega$, where $(q,p)^{t}=\Phi_{n}(x,y)^{t}$.

Proof Let $\check{\mathcal{T}}^{d}$ be the Lagrangian torus admitted by
$\check{H}_{n}(x,y)$. Since $K_{n}$ consists of integer vectors, then
$\hat{\mathcal{T}}^{d}:=K_{n}\check{\mathcal{T}}^{d}$ is still a torus. Note
that $\Phi_{n}$ is a symplectic transformation, $\hat{\mathcal{T}}^{d}$ is a
Lagrangian torus. From Definition 1.2, there exists a dense orbit
$\check{\gamma}_{0}$ with the rotation vector $\omega$ on
$\check{\mathcal{T}}^{d}$. Let $\check{\gamma}(t)$ be the lift of
$\check{\gamma}_{0}$ to $\mathbb{R}^{d}$, it follows that

$\omega=\lim_{t\rightarrow\infty}\frac{\check{\gamma}(t)-\check{\gamma}(0)}{t}.$

Let $\hat{\gamma}(t):=K_{n}\check{\gamma}(t)$, we have

$\displaystyle\lim_{t\rightarrow\infty}\frac{\hat{\gamma}(t)-\hat{\gamma}(0)}{t}$
$\displaystyle=\lim_{t\rightarrow\infty}\frac{K_{n}\check{\gamma}(t)-K_{n}\check{\gamma}(0)}{t};$
$\displaystyle=K_{n}\lim_{t\rightarrow\infty}\frac{\check{\gamma}(t)-\check{\gamma}(0)}{t};$
$\displaystyle=K_{n}\omega.$

Let $\hat{\gamma}_{0}$ be the projected orbit of $\hat{\gamma}$ on
$\hat{\mathcal{T}}^{d}$. Note that

$\overline{\\{\hat{\gamma}_{0}(s)\ |\
s\in\mathbb{R}\\}}=K_{n}\overline{\\{\check{\gamma}_{0}(s)\ |\
s\in\mathbb{R}\\}}.$

It follows that $\hat{\gamma}_{0}$ is also dense on $\hat{\mathcal{T}}^{d}$.
This completes the proof.$\hfill{\Box}$

## 3\. Construction of the perturbation

The perturbation $P_{N}(x)$ consists of two parts as follows:

$P_{N}(x)=\frac{1}{|k_{n}|^{a+2}}(1-\cos\langle
k_{n},x\rangle)+\frac{1}{|k_{n}|^{2}}v_{n}(\langle k_{n},x\rangle,\langle
k^{\prime}_{n},x\rangle),$

where $k_{n}$, $k^{\prime}_{n}$ are $d$-dimensional vectors given by the first
two rows of $K_{n}$ defined as (2.4) and $a$ is a parameter given by

(3.1) $a:=2d+2\tau-2-\delta_{0},$

where $\delta_{0}$ (determined by (3.10) below) is a small positive constant
independent of $n$. Let $q=K_{n}x$. We have $q_{1}=\langle k_{n},x\rangle$ and
$q_{2}=\langle k^{\prime}_{n},x\rangle$. Then $v_{n}(q_{1},q_{2})$ is a
$2\pi$-periodic function with respect to $(q_{1},q_{2})$.

We construct $v_{n}(q_{1},q_{2})$ in the following. First of all, we choose a
$2\pi$-periodic $C^{\infty}$ function $\varphi_{n}$ defined on $\mathbb{R}$.
Within a fundamental domain $[-\pi,\pi]$, we require its maximum
$\varphi_{n}(0)=\sqrt{2}$, and it is supported on

$\left[-\frac{|\omega_{1}|}{|k_{n}|^{1+\delta_{0}}},\frac{|\omega_{1}|}{|k_{n}|^{1+\delta_{0}}}\right],$

where $\delta_{0}$ is the same as the one in (3.1). We also require

(3.2) $|\omega_{1}|\sim\left(\frac{1}{|k_{n}|}\right)^{d+\tau-1+\delta_{0}}.$

Let $\phi_{n}(q_{1},q_{2}):=\varphi_{n}(q_{1}-\pi)\cdot\varphi_{n}(q_{2})$.
For simplicity, we denote

$R_{n}:=\frac{|\omega_{1}|}{|k_{n}|^{1+\delta_{0}}}.$

Then

(3.3)
$\left\\{\begin{array}[]{ll}\phi_{n}(\pi,0)=\max\phi_{n}(q_{1},q_{2})=2,\\\
\text{supp}\phi_{n}=\left[\pi-
R_{n},\pi+R_{n}\right]\times\left[-R_{n},R_{n}\right],\\\
\|\phi_{n}\|_{C^{\kappa}}\sim R_{n}^{-\kappa}.\end{array}\right.$

Next, we use Jackson’s approximation ([36]) to obtain a trigonometric
polynomial $T_{M,n}(q_{1},q_{2})$. After the improvement by Favard [17], we
have

######  Theorem 3.1 (Jackson’s approximation)

Let $\phi(x)$ be a $\kappa$-times ($\kappa\geq 2$) differentiable
$2\pi$-periodic function on $\mathbb{R}$, then for every $M\in\mathbb{N}$,
there exists a trigonometric polynomial $f_{M}(x)$ of degree $M$ such that

$\max|f_{M}(x)-\phi(x)|\leq\frac{4C_{\kappa}}{\pi(M+1)^{\kappa}}||\phi(x)||_{C^{\kappa}},$

where
$C_{\kappa}=\Sigma_{i=1}^{\infty}\frac{(-1)^{i(\kappa-1)}}{(2i+1)^{\kappa+1}}$.

Note that $C_{\kappa}$ is an absolute constant independent of $\phi$ and
$f_{M}$. Hence, for $\varphi_{n}$ defined as above, there exists a
trigonometric polynomial $g_{M,n}(x)$ of degree $M$ such that

$\max|g_{M,n}(x)-\varphi_{n}(x)|\preceq
M^{-\kappa}||\varphi_{n}(x)||_{C^{\kappa}}.$

Let

$T_{M,n}(q_{1},q_{2}):=g_{M,n}(q_{1}-\pi)g_{M,n}(q_{2}).$

It follows that

$\max|T_{M,n}(q_{1},q_{2})-\phi_{n}(q_{1},q_{2})|\preceq
M^{-\kappa}||\phi_{n}||_{C^{\kappa}}.$

Based on the construction of $\phi_{n}$, there hold

(3.4) $\left\\{\begin{array}[]{ll}T_{M,n}(\pi,0)\geq 1,&\\\
T_{M,n}(q_{1},q_{2})\leq\mu_{n}\ll
1,&\forall(q_{1},q_{2})\in([0,2\pi]\times[-\pi,\pi])\backslash\text{supp}\phi_{n}.\end{array}\right.$

More precisely, we require

(3.5)
$\mu_{n}:=M^{-\kappa}||\phi_{n}||_{C^{\kappa}}\sim\left(\frac{1}{|k_{n}|}\right)^{\alpha},$

where $\kappa$ (determined by (3.10)) and $\alpha$ (determined by (5.10)) are
constants independent of $n$. Combining with (3.3), we have

(3.6) $M\sim|k_{n}|^{\frac{\alpha}{\kappa}+d+\tau+2\delta_{0}}.$

By Bernstein’s inequality and Leibniz’s rule, for any fixed $s\geq 0$, we have

$||T_{M,n}(q_{1},q_{2})||_{C^{s}}\preceq M^{s}\max|T_{M,n}(q_{1},q_{2})|.$

After normalization, we denote

$\bar{T}_{M,n}(q_{1},q_{2}):=M^{-2s_{0}}\left(\frac{T_{M,n}(q_{1},q_{2})}{\max
T_{M,n}(q_{1},q_{2})}\right)^{2},$

where $s_{0}:=2d+2\tau$. Finally, we construct $v_{n}$ as follows.

$v_{n}(q_{1},q_{2})=\frac{1}{|k_{n}|^{a}}(1-\cos
q_{1})\bar{T}_{M,n}(q_{1},q_{2}).$

Moreover, there hold

(3.7) $\left\\{\begin{array}[]{ll}v_{n}(q_{1},q_{2})\geq 0,\\\
\|v_{n}\|_{C^{r}}\preceq M^{-2(s_{0}-r)}\frac{1}{|k_{n}|^{a}},\quad\forall
r<s_{0},\\\ \max v_{n}\sim M^{-2s_{0}}\frac{1}{|k_{n}|^{a}},\\\
\|v_{n}\|_{C^{0}}\sim\mu_{n}^{2}M^{-2s_{0}}\frac{1}{|k_{n}|^{a}},\quad\forall(q_{1},q_{2})\in([0,2\pi]\times[-\pi,\pi])\backslash\text{supp}\phi_{n}.\end{array}\right.$

By the construction of $P_{N}(x)$, for $r<2d+2\tau-\delta_{0}$, we have

$\|P_{N}\|_{C^{r}}\sim\left(\frac{1}{|k_{n}|}\right)^{2d+2\tau-\delta_{0}-r}.$

Let $\bar{\delta}:=2\delta_{0}$. A direct calculation implies

(3.8)
$\|H_{n}(x,y)-H_{0}(y)\|_{C^{2d+2\tau-\bar{\delta}}}=\|P_{N}(x)\|_{C^{2d+2\tau-\bar{\delta}}}\sim\left(\frac{1}{|k_{n}|}\right)^{\delta_{0}}\rightarrow
0\quad\text{as}\ n\rightarrow\infty.$

Given $0<\varepsilon\ll 1$, we require $\|P_{N}\|_{C^{r}}\sim\varepsilon$,
then

$|k_{n}|\sim\varepsilon^{-\frac{1}{2d+2\tau-\delta_{0}-r}},$

which together with (3.6) implies

(3.9)
$M\sim\varepsilon^{-\frac{d+\tau+2\delta_{0}}{2d+2\tau-\delta_{0}-r}-\frac{\alpha}{\kappa(2d+2\tau-\delta_{0}-r)}}.$

Moreover, we choose

(3.10) $\delta_{0}=\varepsilon,\quad\kappa=\frac{\alpha}{\varepsilon}.$

Since $\varepsilon$ is small enough, (3.9) can be reduced to

$M\sim\varepsilon^{-\frac{d+\tau}{2d+2\tau-r}}.$

Note that the degree $N$ of $P_{N}$ is not greater than $(2M+1)|k_{n}|$. Then
we get

$N\preceq\varepsilon^{-\frac{d+\tau+1}{2d+2\tau-r}}.$

If $\omega$ is a Liouvillean type, by taking $r=\ln\tau$ for instance, then
the Lagrangian torus can be destroyed by $P_{N}$ of degree
$N\preceq{{\epsilon}^{-1/2}}$. It remains to verify
$\|P_{N}\|_{C^{\infty}}\preceq\epsilon$. In fact, for any $\tau>0$, it follows
from (3.8) that

$\|P_{N}\|_{C^{\ln\tau}}\sim\left(\frac{1}{|k_{n}|}\right)^{2d+2\tau-\delta_{0}-\ln\tau}\rightarrow
0\quad\text{as}\ n\rightarrow\infty.$

We require $\sup_{\tau>0}\|P_{N}\|_{C^{\ln\tau}}\sim\varepsilon$. Then

$\|P_{N}\|_{C^{\infty}}=\sum_{k\in\mathbb{N}}\frac{\arctan(\|P_{N}\|_{k})}{2^{k}}\leq\sup_{\tau>0}\|P_{N}\|_{C^{\ln\tau}}\sim\varepsilon.$

## 4\. Lagrangian formulatioin

According to (2.5), the Lagrangian corresponding to (2.2) is

(4.1)
$\begin{split}L_{n}(q,\dot{q})=&\frac{1}{|k_{n}|^{2}}\left(\frac{1}{2}\sum_{i=3}^{d}\frac{|k_{n}|^{2}}{|l_{ni}|^{2}}|\dot{q}_{i}|^{2}+\frac{1}{2}\frac{|k_{n}|^{2}}{|k^{\prime}_{n}|^{2}}|\dot{q}_{2}|^{2}\right.\\\
&\left.+\frac{1}{2}|\dot{q}_{1}|^{2}+\frac{1}{|k_{n}|^{a}}(1-\cos
q_{1})+v_{n}(q_{1},q_{2})\right),\end{split}$

where $a$ is given by (3.1). Let

(4.2)
$A_{n}(q_{1},\dot{q}_{1}):=\frac{1}{2}|\dot{q}_{1}|^{2}+\frac{1}{|k_{n}|^{a}}(1-\cos
q_{1});$ (4.3)
$B_{n}(q,\dot{q}):=\frac{1}{2}\sum_{i=3}^{d}\frac{|k_{n}|^{2}}{|l_{ni}|^{2}}|\dot{q}_{i}|^{2}+\frac{1}{2}\frac{|k_{n}|^{2}}{|k^{\prime}_{n}|^{2}}|\dot{q}_{2}|^{2}+v_{n}(q_{1},q_{2}).$

Then we have

(4.4) $L_{n}=\frac{1}{|k_{n}|^{2}}(A_{n}+B_{n}).$

In view of Lemma 2.2 and (2.7), in order to complete the proof of Theorem 1.7,
we only need to prove

###### Proposition 4.1

For $n$ large enough, the Lagrangian system generated by $L_{n}(q,\dot{q})$
defined as (4.1) does not admit the Lagrangian torus with the rotation vector
$\omega:=(\omega_{1},\omega_{2},\dots,\omega_{d})$ satisfying

(4.5)
$|\omega_{1}|\sim\left(\frac{1}{|k_{n}|}\right)^{d+\tau-1+\varepsilon},\quad{\omega_{2}}\sim|k_{n}|.$

As preparations, we recall some facts about the dynamics generated by $A_{n}$
and $B_{n}$ respectively. Let $q_{1}(t)$ be a solution of $A_{n}$ on
$(t_{0},t_{1})$ and $(t_{1},t_{2})$ with boundary conditions respectively

$\begin{cases}q_{1}(t_{0})=0,\\\
q_{1}(t_{1})=\pi,\end{cases}\begin{cases}q_{1}(t_{1})=\pi,\\\
q_{1}(t_{2})=2\pi.\end{cases}$

We consider the function $\mathbb{L}:[t_{0},t_{2}]\to\mathbb{R}$ defined by

$\displaystyle\mathbb{L}(s):=$
$\displaystyle\int_{t_{0}}^{s}A_{n}(q_{1},\dot{q}_{1})dt+\int_{s}^{t_{2}}A_{n}(q_{1},\dot{q}_{1})dt.$

By [12, Remark 2.5], there hold

###### Lemma 4.2

$\mathbb{L}(s)$ is decreasing for $s\in(t_{0},\frac{t_{0}+t_{2}}{2}]$ and
increasing for $s\in[\frac{t_{0}+t_{2}}{2},t_{2})$.

Another observation is that the actions along orbits in the neighborhood of
the separatix of the pendulum do not change too much with respect to a small
change in speed. To set up a precise statement, we introduce some notations.
Given $\bar{t}_{1},\tilde{t}_{1}\in[t_{0},t_{2}]$. Let $\bar{q}_{1}(t)$ be a
solution of $A_{n}$ on $(t_{0},\bar{t}_{1})$ and $(\bar{t}_{1},t_{2})$ with
boundary conditions respectively

$\begin{cases}\bar{q}_{1}(t_{0})=0,\\\
\bar{q}_{1}(\bar{t}_{1})=\pi,\end{cases}\begin{cases}\bar{q}_{1}(\bar{t}_{1})=\pi,\\\
\bar{q}_{1}(t_{2})=2\pi.\end{cases}\ $

Let $\tilde{q}_{1}(t)$ be a solution of $A_{n}$ on $(t_{0},\tilde{t}_{1})$ and
$(\tilde{t}_{1},t_{2})$ with boundary conditions respectively

$\begin{cases}\tilde{q}_{1}(t_{0})=0,\\\
\tilde{q}_{1}(\tilde{t}_{1})=\pi,\end{cases}\begin{cases}\tilde{q}_{1}(\tilde{t}_{1})=\pi,\\\
\tilde{q}_{1}(t_{2})=2\pi.\end{cases}$

Let $\bar{\omega}_{1}$ and $\bar{\omega}_{2}$ be the average speeds of
$\bar{q}_{1}$ on $(t_{0},\bar{t}_{1})$ and $(\bar{t}_{1},t_{2})$ respectively.
Let $\tilde{\omega}_{1}$ and $\tilde{\omega}_{2}$ be the average speed of
$\tilde{q}_{1}$ on $(t_{0},\tilde{t}_{1})$ and $(\tilde{t}_{1},t_{2})$
respectively. By [12, Lemma 2.4], there hold

###### Lemma 4.3

Let

$\omega_{1}:=\max\left\\{\bar{\omega}_{1},\bar{\omega}_{2},\tilde{\omega}_{1},\tilde{\omega}_{2}\right\\}.$

If

$\omega_{1}\preceq\left(\frac{1}{|k_{n}|}\right)^{d+\tau-1+\varepsilon},$

then

(4.6)
$\left|\int^{t_{2}}_{t_{0}}A_{n}(\bar{q}_{1},\dot{\bar{q}}_{1})dt-\int^{t_{2}}_{t_{0}}A_{n}(\tilde{q}_{1},\dot{\tilde{q}}_{1})dt\right|\preceq\frac{|\bar{t}_{1}-\tilde{t}_{1}|}{|k_{n}|^{a}}\exp\left(-C|k_{n}|^{\frac{3\varepsilon}{2}}\right),$

where $a$ is given by (3.1).

The last fact is about the speed of the action minimizing orbit of $L_{n}$.
Once the function $q_{1}(t)$ is fixed, we denote
$Q(t):=(q_{2}(t),\ldots,q_{d}(t))$ to be the solution of the Euler-Lagrange
equation with the non autonomous Lagrangian

(4.7)
$\hat{B}_{n}(Q(t),\dot{Q}(t),t)=\frac{1}{2}\sum_{i=3}^{d}\frac{|k_{n}|^{2}}{|l_{ni}|^{2}}|\dot{q}_{i}|^{2}+\frac{1}{2}\frac{|k_{n}|^{2}}{|k^{\prime}_{n}|^{2}}|\dot{q}_{2}|^{2}+v_{n}\left(q_{1}(t),q_{2}(t)\right),$

The first order derivative of $\hat{B}_{n}(Q(t),\dot{Q}(t),t)$ with respect to
$Q$ is as follows:

(4.8) $\frac{\partial\hat{B}_{n}}{\partial q_{2}}=\frac{\partial
v_{n}}{\partial
q_{2}}(q_{1}(t),q_{2}(t))\quad\text{and}\quad\frac{\partial\hat{B}_{n}}{\partial
q_{i}}=0\quad\text{for}\quad i=3,\ldots,d.$

From the construction of $v_{n}$ (see (3.7)), we have
$||v_{n}||_{C^{r}}\preceq\frac{1}{|k_{n}|^{a}}$ if $r<2d+2\tau$. Recalling
$a:=2d+2\tau-2-\varepsilon$, it follows from (4.8) that

$\left|\frac{\partial\hat{B}_{n}}{\partial
q_{i}}\right|\preceq\frac{1}{|k_{n}|^{a}}\quad\text{for}\quad i=2,\ldots,d..$

Note that $\hat{B}_{n}(Q(t),\dot{Q}(t),t)$ is periodic with respect to $Q(t)$,
and $a>1-\frac{\varepsilon}{2}$ for all $d\geq 2$ and $\tau\geq 0$. By [7,
Lemma 2], we have the following estimate.

###### Lemma 4.4

Let $(q_{1}(t),Q(t))$ be the action minimizing orbit of $L_{n}$ with the
rotation vector $\omega$ satisfying (4.5), then for any
$t^{\prime},t^{\prime\prime}\in\mathbb{R}$ and
$t\in[t^{\prime},t^{\prime\prime}]$ we have

(4.9)
$\left|\dot{Q}(t)-\frac{Q(t^{\prime\prime})-Q(t^{\prime})}{t^{\prime\prime}-t^{\prime}}\right|\preceq\frac{1}{|k_{n}|^{d+\tau-1-\frac{\varepsilon}{2}}}\preceq\frac{1}{\sqrt[3]{|k_{n}|}}.$

## 5\. Proof of Proposition 4.1

It is sufficient to prove the existence of the small neighborhood of some
point in $\mathbb{T}^{d}:=\mathbb{R}^{d}/2\pi\mathbb{Z}^{d}$ where no action
minimizing curve passes through. Let us recall

$\text{supp}\phi_{n}=\left[\pi-
R_{n},\pi+R_{n}\right]\times\left[-R_{n},R_{n}\right],$

where

$R_{n}:=\frac{|\omega_{1}|}{|k_{n}|^{1+\varepsilon}}.$

We denote

$S_{0}:=\left[\pi-\frac{1}{2}R_{n},\pi+\frac{1}{2}R_{n}\right]\times\left[-\frac{1}{2}R_{n},\frac{1}{2}R_{n}\right]$

In fact, we will show that the action minimizing orbit does not pass through

$S_{0}\times\mathbb{T}^{d-2}.$

By contradiction, we assume that there exists $\bar{t}_{1}$ such that

(5.1) $(q_{1}(\bar{t}_{1}),q_{2}(\bar{t}_{1}))\in S_{0}.$

Without loss of generality, we assume

$q_{1}(\bar{t}_{1})=\pi,\quad
q_{2}(\bar{t}_{1})=0,\quad\omega_{1}>0,\quad\omega_{2}>0,$

where $q(t):=(q_{1},q_{2},\ldots,q_{d})(t)$ is an action minimizing orbit in
the universal covering space $\mathbb{R}^{d}$. Moreover, there exist
$t_{0}<t_{2}$ such that

$q_{1}(t_{0})=0,\quad q_{1}(t_{2})=2\pi.$

Claim: $t_{2}-t_{0}\sim{{\omega_{1}}}^{-1}$.

Proof By contradiction, we assume $t_{2}-t_{0}\sim{\bar{\omega}_{1}}^{-1}$,
and (up to a subsequence) either ${\bar{\omega}_{1}}=o({\omega_{1}})$, or
${\omega_{1}}=o({\bar{\omega}_{1}})$. We only need to consider the case with
${\bar{\omega}_{1}}=o({\omega_{1}})$, since the other case can be excluded by
a similar argument. The aim is to construct another curve with smaller action
compared to the orbit $q(t)$. That contradicts the action minimizing property
of $q(t)$.

By the definition of the rotation vector, for any $\varepsilon>0$, there
exists $t_{N}>t_{2}$ such that

(5.2)
$\left|\frac{q_{1}(t_{N})-q_{1}(\bar{t}_{1})}{t_{N}-\bar{t}_{1}}-\omega_{1}\right|\leq\epsilon\quad\text{and}\quad
q_{1}(t_{N})=N\pi,$

where $N$ depends on $n$ and $N\gg 2$. Then we have

$t_{N}-\bar{t}_{1}\sim\frac{N\pi}{\omega_{1}}.$

We choose a sequence of times $t_{2}<\ldots<t_{N}$ satisfying
$q_{1}(t_{i})=i\pi$ for $i\in\\{2,\ldots,N\\}$. Moreover, it follows from the
pigeon hole principle that there exists $j\in\\{2,\ldots,N-1\\}$ such that

$t_{j+1}-t_{j}\preceq\frac{1}{\omega_{1}},$

where we consider the case $q_{1}(t_{j})\text{mod}2\pi=0$ and
$q_{1}(t_{j+1})\text{mod}2\pi=\pi$, the other case is similar. Let
$q_{1}(\bar{t}^{\prime}_{1})=\pi+2R_{n}$ and
$q_{1}(t^{\prime}_{j+1})=(j+1)\pi-2R_{n}$.

The remaining proof of this claim is divided into three steps. First of all,
we show $t_{2}-\bar{t}^{\prime}_{1}\sim{\bar{\omega}_{1}}^{-1}$. Denote the
average speeds of $q_{1}(t)$ passing through $[\pi,\pi+2R_{n}]$ and
$[\pi+2R_{n},2\pi]$ by $\omega^{\prime}_{1}$ and $\omega^{\prime\prime}_{1}$
respectively. Note that

(5.3)
$\frac{\pi}{\bar{\omega}_{1}}=\frac{2R_{n}}{\omega^{\prime}_{1}}+\frac{\pi-2R_{n}}{\omega^{\prime\prime}_{1}}.$

It follows that

$\omega^{\prime\prime}_{1}\geq\frac{\pi-2R_{n}}{\pi}\bar{\omega}_{1}.$

By the Euler-Lagrange equation generated by $L_{n}$, it is direct to see
$\omega^{\prime}_{1}>\omega^{\prime\prime}_{1}$. Then

$\bar{\omega}_{1}\preceq\omega^{\prime\prime}_{1}\leq\bar{\omega}_{1},$

which implies $t_{2}-\bar{t}^{\prime}_{1}\sim{\bar{\omega}_{1}}^{-1}$.

Second, we substitute $q_{1}(t)|_{[\bar{t}^{\prime}_{1},t_{2}]}$ and
$q_{1}(t)|_{[t_{j},t^{\prime}_{j+1}]}$ by the orbits
$\hat{q}_{1^{\prime}}(t)$, $\hat{q}_{1^{\prime\prime}}(t)$ of the pendulum
$A_{n}$ (see (4.2)) with more uniform motion and smaller action (see Fig. 1).

Figure 1: Construction of the curve with smaller action

In fact, by a similar argument as the first step, we have
$t^{\prime}_{j+1}-t_{j}\sim{\omega_{1}}^{-1}$. Since we assume
${\bar{\omega}_{1}}=o({\omega_{1}})$, the second step can be achieved by using
Lemma 4.2. More precisely, we denote

$T=\frac{1}{2}(t_{2}-\bar{t}^{\prime}_{1}+t^{\prime}_{j+1}-t_{j}).$

Let $s_{j}$ be the closest time to $t^{\prime}_{j+1}-T$ such that
$q_{2}(s_{j})-q_{2}(t_{j})=l$ where $l\in 2\pi\mathbb{Z}$. Since
${\omega_{2}}\sim|k_{n}|$, it follows from Lemma 4.4 that
$|t^{\prime}_{j+1}-T-s_{j}|\preceq|k_{n}|^{-1}$. Let
$s_{2}=s_{j}-(t_{j}-t_{2})$. Then $\hat{q}_{1^{\prime}}(t)$ and
$\hat{q}_{1^{\prime\prime}}(t)$ are the solutions of $A_{n}$ on
$(\bar{t}^{\prime}_{1},s_{2})$ and on $(s_{j},t^{\prime}_{j+1})$ with boundary
conditions respectively

$\begin{cases}\hat{q}_{1^{\prime}}(\bar{t}^{\prime}_{1})=q_{1}(\bar{t}^{\prime}_{1}),\\\
\hat{q}_{1^{\prime}}(s_{2})=q_{1}(t_{2})=2\pi,\end{cases}\quad\begin{cases}\hat{q}_{1^{\prime\prime}}(s_{j})=q_{1}(t_{j})=j\pi,\\\
\hat{q}_{1^{\prime\prime}}(t^{\prime}_{j+1})=q_{1}(t^{\prime}_{j+1}).\end{cases}$

Finally, we substitute $q_{2}(t)|_{[\bar{t}^{\prime}_{1},t_{2}]}$ and
$q_{2}(t)|_{[t_{j},t^{\prime}_{j+1}]}$ by the linear motions
$\hat{q}_{2^{\prime}}(t)$ and $\hat{q}_{2^{\prime\prime}}(t)$ respectively. On
the time interval $[\bar{t}^{\prime}_{1},t^{\prime}_{j+1}]$, we construct a
new curve as follows.

$\hat{q}_{1}:=\hat{q}_{1^{\prime}}(t)|_{[\bar{t}^{\prime}_{1},s_{2}]}\ast
q_{1}(t-s_{2}+t_{2})|_{[s_{2},s_{j}]}\ast\hat{q}_{1^{\prime\prime}}(t)|_{[s_{j},t^{\prime}_{j+1}]},$
$\hat{q}_{2}:=\hat{q}_{2^{\prime}}(t)|_{[\bar{t}^{\prime}_{1},s_{2}]}\ast\left(q_{2}(t-s_{2}+t_{2})|_{[s_{2},s_{j}]}-l\right)\ast\hat{q}_{2^{\prime\prime}}(t)|_{[s_{j},t^{\prime}_{j+1}]},$

where $\ast$ denotes the juxtaposition of curves. To complete the proof of
this claim, it suffices to verify

(5.4)
$\int_{\bar{t}^{\prime}_{1}}^{t^{\prime}_{j+1}}L_{n}(\hat{q}_{1},\hat{Q},\dot{\hat{q}}_{1},\dot{\hat{Q}})dt<\int_{\bar{t}^{\prime}_{1}}^{t^{\prime}_{j+1}}L_{n}(q_{1},Q,\dot{q}_{1},\dot{Q})dt,$

where $\hat{Q}:=(\hat{q}_{2},q_{3},\ldots,q_{d})$ and
$Q:=(q_{2},q_{3},\ldots,q_{d})$. Let us recall (see (4.4))

$L_{n}=\frac{1}{|k_{n}|^{2}}(A_{n}+B_{n}).$

Based on the second step, we only need to show

(5.5)
$\begin{split}&\int_{\bar{t}^{\prime}_{1}}^{t_{2}}B_{n}(\hat{q}_{1},\hat{Q},\dot{\hat{q}}_{1},\dot{\hat{Q}})dt+\int_{t_{j}}^{t^{\prime}_{j+1}}B_{n}(\hat{q}_{1},\hat{Q},\dot{\hat{q}}_{1},\dot{\hat{Q}})dt\\\
\leq&\int_{\bar{t}^{\prime}_{1}}^{t_{2}}B_{n}(q_{1},Q,\dot{q}_{1},\dot{Q})dt+\int_{t_{j}}^{t^{\prime}_{j+1}}B_{n}({q}_{1},{Q},\dot{{q}}_{1},\dot{{Q}})dt.\end{split}$

Denote

$d_{1}:=q_{2}(t_{2})-q_{2}(\bar{t}^{\prime}_{1}),\quad
d_{2}:=q_{2}(t^{\prime}_{j+1})-q_{2}(t_{j}).$

According to the construction of $v_{n}$, both actions of $q(t)$ and
$\hat{q}(t)$ could be approximated by the actions of linear motions. It
follows that

$\int_{\bar{t}^{\prime}_{1}}^{t_{2}}B_{n}(q_{1},Q,\dot{q}_{1},\dot{Q})dt+\int_{t_{j}}^{t^{\prime}_{j+1}}B_{n}({q}_{1},{Q},\dot{{q}}_{1},\dot{{Q}})dt\sim\frac{d_{1}^{2}}{t_{2}-\bar{t}^{\prime}_{1}}+\frac{d_{2}^{2}}{t^{\prime}_{j+1}-t_{j}}.$
$\int_{\bar{t}^{\prime}_{1}}^{t_{2}}B_{n}(\hat{q}_{1},\hat{Q},\dot{\hat{q}}_{1},\dot{\hat{Q}})dt+\int_{t_{j}}^{t^{\prime}_{j+1}}B_{n}(\hat{q}_{1},\hat{Q},\dot{\hat{q}}_{1},\dot{\hat{Q}})dt\sim\frac{(d_{1}-l)^{2}}{s_{2}-\bar{t}^{\prime}_{1}}+\frac{(d_{2}+l)^{2}}{t^{\prime}_{j+1}-s_{j}}.$

Note that $|t^{\prime}_{j+1}-T-s_{j}|\preceq|k_{n}|^{-1}$. The average speeds
of $\hat{q}_{1}^{\prime}$ and $\hat{q}_{1}^{\prime\prime}$ have the same
quantity order. Let $\hat{\omega}_{1}$ be the average speed of
$\hat{q}_{1}^{\prime}$ and $\hat{q}_{1}^{\prime\prime}$. Similar to (5.3), we
have

$\hat{\omega}_{1}\sim\min\\{\omega_{1},\bar{\omega}_{1}\\}=\bar{\omega}_{1},$

which yields

$s_{2}-\bar{t}^{\prime}_{1}\sim
t^{\prime}_{j+1}-s_{j}\sim\frac{1}{\hat{\omega}_{1}}.$

Combining with the following facts

$t_{2}-\bar{t}^{\prime}_{1}\sim\frac{1}{\bar{\omega}_{1}},\quad
t^{\prime}_{j+1}-t_{j}\preceq\frac{1}{{\omega}_{1}},\quad
d_{1}-l,d_{2}+l\in[d_{2},d_{1}],\quad\bar{\omega}_{1}=o(\omega_{1}),$

We have

(5.6)
$\begin{split}\frac{(d_{1}-l)^{2}}{s_{2}-\bar{t}^{\prime}_{1}}+\frac{(d_{2}+l)^{2}}{t^{\prime}_{j+1}-s_{j}}&\preceq\bar{\omega}_{1}(d_{1}^{2}+d_{2}^{2})=o\left(\bar{\omega}_{1}d_{1}^{2}+\omega_{2}d_{2}^{2}\right),\\\
\frac{d_{1}^{2}}{t_{2}-\bar{t}^{\prime}_{1}}+\frac{d_{2}^{2}}{t^{\prime}_{j+1}-t_{j}}&\succeq\bar{\omega}_{1}d_{1}^{2}+\omega_{2}d_{2}^{2}.\end{split}$

This completes the proof of the claim $t_{2}-t_{0}\sim{{\omega_{1}}}^{-1}$.
$\hfill{\Box}$

Let $\tilde{t}_{1}$ be the last time before $\bar{t}_{1}$ or the first time
after $\bar{t}_{1}$ such that

$|q_{2}(\tilde{t}_{1})-q_{2}(\bar{t}_{1})|=\pi.$

Consider a solution $\tilde{q}_{1}$ of $A_{n}$ on $(t_{0},\tilde{t}_{1})$ and
on $(\tilde{t}_{1},t_{2})$ with boundary conditions respectively

$\begin{cases}\tilde{q}_{1}(t_{0})=0,\\\
\tilde{q}_{1}(\tilde{t}_{1})=\pi,\end{cases}\quad\begin{cases}\tilde{q}_{1}(\tilde{t}_{1})=\pi,\\\
\tilde{q}_{1}(t_{2})=2\pi.\end{cases}$

Note that $q=(q_{1},q_{2},\ldots,q_{d})$ is assumed to be an action minimizing
curve. Let $Q:=(q_{2},\ldots,q_{d})$, we have

(5.7)
$\int_{t_{0}}^{t_{2}}L_{n}(\tilde{q}_{1},Q,\dot{\tilde{q}}_{1},\dot{Q})dt-\int_{t_{0}}^{t_{2}}L_{n}(q_{1},Q,\dot{q}_{1},\dot{Q})dt\geq
0.$

See Fig.2, where $x_{1}=(q_{1}(\bar{t}_{1}),q_{2}(\bar{t}_{1}))=(\pi,0)$,
$x_{0}=(q_{1}(t_{0}),q_{2}(t_{0}))=(0,q_{2}(t_{0}))$,
$x_{2}=(q_{1}(t_{2}),q_{2}(t_{2}))=(2\pi,q_{2}(t_{2}))$,
$\tilde{x}^{\prime}_{1}=(\pi,-\pi)$, $\tilde{x}^{\prime\prime}_{1}=(\pi,\pi)$.

Figure 2: The projections of the curves $(q_{1}(t),Q(t))$ and
$(\tilde{q}_{1}(t),Q(t))$ on $[0,2\pi]\times\mathbb{R}$

Note that $(\tilde{q}_{1}(t),q_{2}(t))$ passes through the point
$\tilde{x}^{\prime}_{1}$ or $\tilde{x}^{\prime\prime}_{1}$. Thus, by the
construction of $L_{n}$, it follows from (5.7) that

(5.8)
$\int_{t_{0}}^{t_{2}}A_{n}(\tilde{q}_{1},\dot{\tilde{q}}_{1})dt-\int_{t_{0}}^{t_{2}}A_{n}(q_{1},\dot{q_{1}})dt\geq\int_{t_{0}}^{t_{2}}v_{n}(q_{1},q_{2})dt-\int_{t_{0}}^{t_{2}}v_{n}(\tilde{q}_{1},q_{2})dt.$

Based on the construction of $v_{n}$ (see (3.7)), we have the following claim.

Claim: $\left(\tilde{q}_{1}(t),q_{2}(t)\right)\notin\text{supp}\phi_{n}$ for
any $t\in(t_{0},t_{2})$.

Proof By contradiction, we assume that there exists $\hat{t}\in(t_{0},t_{2})$
such that

(5.9) $(\tilde{q}_{1}(\hat{t}),q_{2}(\hat{t}))\in\text{supp}\phi_{n}.$

Without loss of generality, one can assume $\hat{t}>\tilde{t}_{1}$. Note that
${\omega_{2}}\sim|k_{n}|$. By Lemma 4.4, We obtain that for
$t\in[\tilde{t}_{1},\hat{t}]$,

$\dot{q}_{2}(t)\sim|k_{n}|.$

Hence, we have $\hat{t}-\tilde{t}_{1}\sim|k_{n}|^{-1}$.

Let $\tilde{\omega}^{\prime}_{1}$ and $\tilde{\omega}^{\prime\prime}_{1}$ be
the average speeds of $\tilde{q}_{1}$ on $(t_{0},\tilde{t}_{1})$ and
$(\tilde{t}_{1},t_{2})$ respectively, then

$\frac{2\pi}{{\omega_{1}}}=\frac{\pi}{\tilde{\omega}^{\prime}_{1}}+\frac{\pi}{\tilde{\omega}^{\prime\prime}_{1}}.$

Hence,

$\tilde{\omega}^{\prime}_{1}\geq\frac{1}{2}{\omega_{1}}\quad\text{and}\quad\tilde{\omega}^{\prime\prime}_{1}\geq\frac{1}{2}{\omega_{1}},$

which together with the Euler-Lagrange equation of $\tilde{q}_{1}(t)$ implies
that for any $t\in[\tilde{t}_{1},\hat{t}]$,

$\dot{\tilde{q}}_{1}(t)\succeq{\omega_{1}},$

Consequently, we have

$|\tilde{q}_{1}(\hat{t})-\tilde{q}_{1}(\tilde{t}_{1})|\succeq\frac{{\omega_{1}}}{|k_{n}|}.$

It follows that for $n$ large enough,

$|\tilde{q}_{1}(\hat{t})-\tilde{q}_{1}(\tilde{t}_{1})|\gg\frac{{\omega_{1}}}{|k_{n}|^{1+\varepsilon}}.$

Based on the construction of $\phi_{n}$ (see (3.3)), that contradicts the
assumption (5.9).$\hfill{\Box}$

Claim: There exists $\lambda>0$ independent of $n$ such that

$\int_{t_{0}}^{t_{2}}v_{n}(q_{1},q_{2})dt-\int_{t_{0}}^{t_{2}}v_{n}(\tilde{q}_{1},q_{2})dt\succeq\left(\frac{1}{|k_{n}|}\right)^{\lambda}.$

Proof Based on (3.7) and $t_{2}-t_{0}\sim{{\omega_{1}}^{-1}}$, we need to
estimate the lower bound of $\int_{t_{0}}^{t_{2}}v_{n}(q_{1},q_{2})dt$ and the
upper bound of $\int_{t_{0}}^{t_{2}}v_{n}(\tilde{q}_{1},q_{2})dt$.

By Lemma 4.4, We obtain that for $t\in[{t}_{0},{t}_{2}]$,

$\dot{q}_{2}(t)\sim|k_{n}|.$

Denote $\triangle t$ the time during which the action minimizing orbit $q(t)$
passes though

$S_{0}:=\left[\pi-\frac{1}{2}R_{n},\pi+\frac{1}{2}R_{n}\right]\times\left[-\frac{1}{2}R_{n},\frac{1}{2}R_{n}\right].$

It follows that

$\triangle t\sim\frac{R_{n}}{|k_{n}|}.$

Note that $v_{n}\geq 0$. By the mean value theorem, we have

$\int_{t_{0}}^{t_{2}}v_{n}(q_{1},q_{2})dt\succeq
N^{-2s_{0}}\frac{1}{|k_{n}|^{a}}\triangle t\sim
M^{-2s_{0}}\frac{{\omega_{1}}}{|k_{n}|^{a+2+\varepsilon}},$

where $s_{0}:=2d+2\tau$. Denote ${v}_{n}^{*}$ the maximum of $v_{n}$
restricted on $([0,2\pi]\times[-\pi,\pi])\backslash\text{supp}\phi_{n}$. Then

$\int_{t_{0}}^{t_{2}}v_{n}(\tilde{q}_{1},q_{2})dt\preceq\frac{{v}_{n}^{*}}{{\omega_{1}}}\sim
M^{-2s_{0}}\frac{1}{|k_{n}|^{a}}\frac{1}{{\omega_{1}}}\left(\frac{1}{|k_{n}|}\right)^{2\alpha}.$

Note that (see (3.6) and (4.5))

${\omega_{1}}\sim\left(\frac{1}{|k_{n}|}\right)^{d+\tau-1+\varepsilon},\quad
M\sim|k_{n}|^{\frac{\alpha}{\kappa}+d+\tau+2\varepsilon}.$

We can choose $\alpha$ large enough, for example

(5.10) $\alpha\geq d+\tau+1,$

for which the claim holds true with $\lambda\geq 4(d+\tau)^{2}+3(d+\tau)$.
$\hfill{\Box}$

It follows from (5.8) that

(5.11)
$\int_{t_{0}}^{t_{2}}A_{n}(\tilde{q}_{1},\dot{\tilde{q}}_{1})dt-\int_{t_{0}}^{t_{2}}A_{n}(q_{1},\dot{q}_{1})dt\succeq\left(\frac{1}{|k_{n}|}\right)^{\lambda}.$

On the other hand, we consider the solution $\bar{q}_{1}(t)$ of $A_{n}$ on
$(t_{0},\bar{t}_{1})$ and $(\bar{t}_{1},t_{2})$ with the boundary conditions
respectively

$\begin{cases}\bar{q}_{1}(t_{0})=0,\\\
\bar{q}_{1}(\bar{t}_{1})=\pi,\end{cases}\quad\begin{cases}\bar{q}_{1}(\bar{t}_{1})=\pi,\\\
\bar{q}_{1}(t_{2})=2\pi,\end{cases}$

where $\bar{t}_{1}$ is determined by (5.1). For $t\in(t_{0},\bar{t}_{1})$ and
$(\bar{t}_{1},t_{2})$ respectively, the action of $A_{n}$ achieves the minimum
along $\bar{q}_{1}(t)$. Thus, we have

$\int_{t_{0}}^{t_{2}}A_{n}(q_{1},\dot{q}_{1})dt\geq\int_{t_{0}}^{t_{2}}A_{n}(\bar{q}_{1},\dot{\bar{q}}_{1})dt.$

Based on the choices of $\tilde{t}_{1}$, we compare the action
$\int_{t_{0}}^{t_{2}}A_{n}(\tilde{q}_{1},\dot{\tilde{q}}_{1})dt$ with the
action $\int_{t_{0}}^{t_{2}}A_{n}(\bar{q}_{1},\dot{\bar{q}}_{1})dt$ in the
following dichotomy. Let us recall $\bar{t}:=\frac{t_{0}+t_{2}}{2}$.

Case 1: $|\bar{t}_{1}-\bar{t}|\preceq\frac{1}{|k_{n}|}$.

In this case, the average speeds of $\bar{q}_{1}$ on $(t_{0},\bar{t}_{1})$ and
$(\bar{t}_{1},t_{2})$ have the same quantity order as ${\omega_{1}}$. By
$|\tilde{t}_{1}-\bar{t}_{1}|\preceq\frac{1}{|k_{n}|}$, we have
$|\tilde{t}_{1}-\bar{t}|\preceq\frac{1}{|k_{n}|}$. Hence the average speeds of
$\tilde{q}_{1}$ on $(t_{0},\tilde{t}_{1})$ and $(\tilde{t}_{1},t_{2})$ have
also the same quantity order as ${\omega_{1}}$. Thus, Lemma 4.3 implies

(5.12)
$\begin{split}\int_{t_{0}}^{t_{2}}A_{n}(\tilde{q}_{1},\dot{\tilde{q}}_{1})dt-\int_{t_{0}}^{t_{2}}A_{n}(\bar{q}_{1},\dot{\bar{q}}_{1})dt&\preceq\frac{1}{|k_{n}|^{a+1}}\exp\left(-C|k_{n}|^{\frac{3\varepsilon}{2}}\right)\\\
&\sim\left(\frac{1}{|k_{n}|}\right)^{2d+2\tau-1-\varepsilon}\exp\left(-C|k_{n}|^{\frac{3\varepsilon}{2}}\right).\end{split}$

Case 2: $|\bar{t}_{1}-\bar{t}|>\frac{C}{|k_{n}|}$ for any positive constant
$C$ independent of $n$.

In this case, we take $\tilde{t}_{1}$ such that
$|\tilde{t}_{1}-\bar{t}|\leq|\bar{t}_{1}-\bar{t}|$, which can be achieved by
the suitable choice of the position of $\tilde{q}_{1}(\tilde{t}_{1})$. More
precisely,

  * (2a)

if $\bar{t}_{1}>\bar{t}+\frac{C}{|k_{n}|}$, we choose $\tilde{t}_{1}$ as the
last time before $\bar{t}_{1}$, corresponding to
$(\tilde{q}_{1}(\tilde{t}_{1}),q_{2}(\tilde{t}_{1}))=\tilde{x}^{\prime}_{1}$
in Fig.2;

  * (2b)

if $\bar{t}_{1}<\bar{t}-\frac{C}{|k_{n}|}$, we choose $\tilde{t}_{1}$ as the
first time after $\bar{t}_{1}$, corresponding to
$(\tilde{q}_{1}(\tilde{t}_{1}),q_{2}(\tilde{t}_{1}))=\tilde{x}^{\prime\prime}_{1}$
in Fig.2.

For Case 2a, $\tilde{t}_{1}\in[\bar{t},\bar{t}_{1}]$. For Case 2b,
$\tilde{t}_{1}\in[\bar{t}_{1},\bar{t}]$. From Lemma 4.2, it follows that
$\mathbb{L}(\tilde{t}_{1})-\mathbb{L}(\bar{t}_{1})\leq 0$, i.e.

$\int_{t_{0}}^{t_{2}}A_{n}(\tilde{q}_{1},\dot{\tilde{q}}_{1})dt-\int_{t_{0}}^{t_{2}}A_{n}(\bar{q}_{1},\dot{\bar{q}}_{1})dt\leq
0.$

Consequently, for any $\bar{t}_{1}\in(t_{0},t_{2})$, we can always find
$\tilde{t}_{1}\in(t_{0},t_{2})$ such that

$\displaystyle\int_{t_{0}}^{t_{2}}A_{n}(\tilde{q}_{1},\dot{\tilde{q}}_{1})dt-\int_{t_{0}}^{t_{2}}A_{n}(q_{1},\dot{q}_{1})dt$
$\displaystyle\leq\int_{t_{0}}^{t_{2}}A_{n}(\tilde{q}_{1},\dot{\tilde{q}}_{1})dt-\int_{t_{0}}^{t_{2}}A_{n}(\bar{q}_{1},\dot{\bar{q}}_{1})dt,$
$\displaystyle\preceq\left(\frac{1}{|k_{n}|}\right)^{2d+2\tau-1-\varepsilon}\exp\left(-C|k_{n}|^{\frac{3\varepsilon}{2}}\right),$

which contradicts (5.11) for $n$ large enough. Then we completes the proof of
Proposition 4.1. $\hfill{\Box}$

Acknowledgement. Part of this work was done during my visit to Dipartimento di
Matematica, Universita degli Studi di Roma “ Tor Vergata”. I would like to
thank Prof. Alfonso Sorrentino for his invitation and hospitality. This work
is partially under the support of National Natural Science Foundation of China
(Grant No. 12122109).

##  References

  * [1] J. Albrecht. On the existence of invariant tori in nearly-integrable Hamiltonian systems with finitely differentiable perturbations. Regul. Chaotic Dyn. 12 (2007), 281-320.
  * [2] D. Anosov and A. Katok. New examples in smooth ergodic theory. Ergodic diffeomorphisms. Trans. Moscow Math. Soc. 23 (1970), 1-35.
  * [3] M. C. Arnaud. On a theorem due to Birkhoff. Geom. Funct. Anal. 20 (2010), 1307-1316.
  * [4] M. C. Arnaud. A non-differentiable essential irrational invariant curve for a $C^{1}$ symplectic twist map. J. Mod. Dyn. 5(3) (2011), 583-591.
  * [5] M. C. Arnaud, J. Massetti and A. Sorrentino. On the fragility of periodic tori for families of symplectic twist maps. Adv. Math. 429 (2023), Paper No. 109175, 39 pp.
  * [6] A. Avila and B. Fayad. Non-differentiable irrational curves for $C^{1}$ twist map. Ergod. Th. & Dynam. Sys. 42 (2022), no. 2, 491-499.
  * [7] D. Bernstein and A. Katok. Birkhoff periodic orbits for small perturbation of completely integrable Hamiltonian systems with convex Hamiltonians. Invent. Math. 88 (1987), 225-241.
  * [8] U. Bessi. An analytic counterexample to KAM theorem. Ergod. Th. & Dynam. Sys. 20 (2000), 317-333.
  * [9] M. Bialy and L. Polterovich. Hamiltonian systems, Lagrangian tori and Birkhoff’s theorem. Math. Ann. 292 (1992), 619-627.
  * [10] J. Bovey and M. Dodson. The Hausdorff dimension of systems of linear forms. Acta Arith. 45 (1986), no. 4, 337-358.
  * [11] C.-Q. Cheng. Non-existence of KAM torus. Acta Mathmatica Sinica. 27 (2011), 397-404.
  * [12] C.-Q. Cheng and L. Wang. Destruction of Lagrangian torus for positive definite Hamiltonian systems. Geom. Funct. Anal. 23 (2013), 848-866.
  * [13] G. Contreras and R. Iturriaga. Global minimizers of autonomous Lagrangians. 22nd Colóquio Brasileiro de Matemática. [22nd Brazilian Mathematics Colloquium], Instituto de Matemática Pura e Aplicada (IMPA), Rio de Janeiro, 1999.
  * [14] A. Fathi, A. Giuliani and A. Sorrentino. Uniqueness of invariant Lagrangian graphs in a homology or a cohomology class. Ann. Sc. Norm. Super. Pisa Cl. Sci. (5) 8 (2009), no. 4, 659-680.
  * [15] J. Favard. Sur les meilleurs procédés d’approximation. B.S.M. 61 (1937), 243-256.
  * [16] B. Fayad and A. Katok. Constructions in elliptic dynamics. Ergod. Th. & Dynam. Sys. 24 (2004), no. 5, 1477-1520.
  * [17] B. Fayad. Topologically mixing and minimal but not ergodic, analytic transformation on $\mathbb{T}^{5}$. Bol. Soc. Brasil. Mat. (N.S.), 31(3):277-285, 2000
  * [18] G. Forni. Analytic destruction of invariant circles. Ergod. Th. & Dynam. Sys. 14 (1994), 267-298.
  * [19] H. Fürstenberg. Strict ergodicity and transformation of the torus. Am. J. Math. 83 (1961), 573-601.
  * [20] M. R. Herman. Sur la conjugation diff$\acute{e}$rentiable des diff$\acute{e}$omorphismes du cercle $\grave{a}$ des rotations. Publ. Math. IHES 49 (1979), 5-233.
  * [21] M. R. Herman. Sur les courbes invariantes par les difféomorphismes de l’anneau. Astérisque 103-104 (1983), 1-221.
  * [22] M. R. Herman. Sur les courbes invariantes par les diff$\acute{e}$omorphismes de l’anneau. Ast$\acute{\text{e}}$risque 144 (1986), 1-243.
  * [23] M. R. Herman. Existence et non existence de tores invariants par des difféomorphismes symplectiques. Séminaire sur les Équations aux Dérivées Partielles 1987-1988. École Polytechique, Palaiseau, 1988, Exp. No. XIV, 24.
  * [24] M. R. Herman. Inégalités “a priori” pour des tores lagrangiens invariants par des difféomrphismes symplectiques. Publ. Math. IHES 70 (1990), 47-101.
  * [25] M. R. Herman. On the dynamics of Lagrangian tori invariant by symplectic diffeomorphisms. In Progress in variational methods in Hamiltonian systems and elliptic equations (L’Aquila, 1990). Pitman Res. Notes Math. Ser. 243 (1992), 92-112.
  * [26] A. Katok and B. Hasselblatt. Introduction to the Modern Theory of Dynamical Systems (Encyclopedia of Mathematics and its Applications, 54). Cambridge University Press, Cambridge, 1995.
  * [27] J. Kwapisz and M. Mathison. Diophantine and minimal but not uniquely ergodic (almost). Nonlinearity 25(2012), no.7, 2027-2037.
  * [28] J. N. Mather. Destruction of invariant circles. Ergod. Th. & Dynam. Sys. 8 (1988), 199-214.
  * [29] J. N. Mather. Action minimizing invariant measures for postive definite Lagrangian systems. Math. Z. 207 (1991), 169-207.
  * [30] V. V. Nemitsky, V. V. Stepanov. Qualitative Theory of Differential Equations. Princeton, Princeton University Press, 1960.
  * [31] P. Ni and L. Wang. Aubry-Mather theory for contact Hamiltonian systems III. Sci. China Math., to appear.
  * [32] J. Pöschel. Integrability of Hamiltonian systems on Cantor sets. Comm. Pure Appl. Math. 35 (1982), 653-696.
  * [33] J. Pöschel. KAM below $C^{n}$. https://arxiv.org/abs/2104.01866.
  * [34] D. Salamon. The Kolmogorov-Arnold-Moser theorem. Math. Phys. Electron. J. 10 (2004), Paper 3, 37 pp.
  * [35] Z. Tong and Y. Li. Towards continuity: Universal frequency-preserving KAM persistence and remaining regularity. https://arxiv.org/abs/2302.14361.
  * [36] A. Zygmund. Trigonometric Series. Third Edition Volumes I & II combined, with a foreword by Robert Fefferman. Cambridge University Press, Cambridge, 2002.


11institutetext: Health Informatics Research Group, University of Applied
Sciences Osnabrück, Germany 11email<EMAIL_ADDRESS>22institutetext:
L3S Research Center, Leibniz University Hannover, Germany
22email<EMAIL_ADDRESS>
# Achieving differential privacy for $k$-nearest neighbors based outlier
detection by data partitioning

Jens Rauch 11 Iyiola E. Olatunji 22 Megha Khosla 22

###### Abstract

When applying outlier detection in settings where data is sensitive,
mechanisms which guarantee the privacy of the underlying data are needed. The
$k$-nearest neighbors ($k$-NN) algorithm is a simple and one of the most
effective methods for outlier detection. So far, there have been no attempts
made to develop a differentially private ($\epsilon$-DP) approach for $k$-NN
based outlier detection. Existing approaches often relax the notion of
$\epsilon$-DP and employ other methods than $k$-NN. We propose a method for
$k$-NN based outlier detection by separating the procedure into a fitting step
on reference inlier data and then apply the outlier classifier to new data. We
achieve $\epsilon$-DP for both the fitting algorithm and the outlier
classifier with respect to the reference data by partitioning the dataset into
a uniform grid, which yields low global sensitivity. Our approach yields
nearly optimal performance on real-world data with varying dimensions when
compared to the non-private versions of $k$-NN.

###### Keywords:

Differential privacy Outlier detection. $k$-Nearest neighbors

##  1 Introduction

Outliers are observations in a dataset, which deviate considerably from the
remainder of the data and might therefore be indicative of a different data
generating mechanism [22]. Detection of outliers has important applications in
medicine, finance and administrative monitoring, since it allows to identify
anomalous or suspicious data for later scrutiny. However, in many use cases
such as medical screenings, the data is inherently sensitive. This calls for
privacy preserving mechanisms that protect the data of individuals from being
revealed when releasing a data analytic model that relies on these data, as is
the case for outlier detection models. One powerful and widely accepted
approach for releasing data statistics or the trained model while concealing
the information about individuals in the employed dataset is _differential
privacy_ (DP) [8]. We specifically focus on $\epsilon$-DP in this work where
$\epsilon$ quantifies the privacy guarantee.

Under $\epsilon$-DP, one adds a sufficient level of noise during analysis so
that it is impossible to infer the presence or absence of single observations
in the underlying dataset from the final model. Perturbing model parameters by
adding noise evidently leads to a decreased model performance, which depends
on the algorithm for model training, as well as the specific dataset. It is
therefore of vital importance to study the impact on model precision when
applying $\epsilon$-DP to outlier detection algorithms.

Despite the extensive and growing body of methods in both outlier detection
and differentially private data mining, there is only scant literature on how
to perform outlier detection with privacy guarantees. In this paper, we
therefore combine two pertinent approaches from both domains, namely
$k$-nearest neighbor ($k$-NN) based detection of outliers and $\epsilon$-DP.
Such a conjoint approach has not been been examined before.

The existing works, which have proposed solutions for privacy preserving
outlier detection either relax the concept of $\epsilon$-DP [3, 5, 15] or use
simplified definitions of outliers [17, 4, 13] in order to obtain reasonable
detection performance. It is common to all these previous approaches that they
make no conceptual distinction between the training of an outlier classifier
and identifying outliers in a dataset. With our approach, instead, we could
directly build upon the original definitions of $\epsilon$-DP and $k$-NN based
outlier detection. We could achieve this by separating the procedure into
building a $k$-NN classifier, which precedes the identification of outliers.
The algorithm fulfils $\epsilon$-DP and outputs a $k$-NN based outlier
classifier, which can be interactively queried to determine outliers in new
data. The data used for the fitting procedure remains private as guaranteed by
$\epsilon$-DP. Moreover, this approach is computationally more efficient than
the approaches, which do not separate into training and outlier detection,
when perpetually applied to new incoming data [11].

While there are a number of advanced outlier detection methods, it has been
shown recently, that in many cases simple $k$-NN queries do perform as well as
the sophisticated approaches [6]. When using $k$-NN, an observation’s distance
to its nearest neighbors is a measure of its outlierness. In fact, a number of
the advanced methods based on density estimates, connectivity or angular
distance make use of $k$-NN queries, such as Local Outlier Factors (LOF) or
Kernel Density Estimation Outlier Score (KDEOS) [21, 19, 14]. Being a simple
and nonetheless very effective method, $k$-NN is an ideal candidate for
outlier detection under $\epsilon$-DP. To the best of our knowledge, this is
the first study which examines an approach of differentially private $k$-NN
based outlier detection.

Our Contributions. We propose a novel differential private algorithm for
outlier detection. The $\epsilon$-DP mechanism works by building a uniform
grid on a reference dataset, partitioning it into cells and perturbing the
count of elements in the cells. The resulting model of reference cell counts
can then be queried against with new data of interest, to determine whether
any of the new data points should be considered outliers. Our approach
guarantees $\epsilon$-DP for the reference data and allows for online querying
of new incoming data [11]. We experimentally evaluate our approach on five
benchmark datasets in comparison to four non-private baselines. To summarize,
we make the following contributions.

  1. 1.

We develop a novel yet simple algorithm for outlier detection with provable
differential privacy gurantees. Our approach is scalable for high dimensional
datasets as well as continuous domains.

  2. 2.

We showcase the effectiveness of our approach by comparing our approach with
several of the non-private baselines. Our approach yields close to optimal
performance on real-world datasets of varying dimensionality, when compared to
the baselines.

We have published the anonymized version of our
code.111https://anonymous.4open.science/r/fcf95211-3361-440a-986a-966bd13b1ede/

##  2 Related Work

Okada et al. [17] presented differentially private queries for fixed distance-
based outlier analysis. However, their work is targeted at outlier
characteristics, rather than outlier detection. It uses a fixed-distance
definition of outliers, whereas our work is based on $k$-NN based outlier
definition. Moreover, they set out from the relaxed definitions of
$\epsilon-\delta$-DP and smooth sensitivity instead of the stricter global
sensitivity, which we use. The two types of queries they provide include (i)
count queries which returns the number of detected outliers in a given
subspace and (ii) discovery of top-subspaces containing a large number of
outliers.

In another line of work, Lui and Pass [15] introduced a new privacy notion for
outliers as a generalization of $\epsilon$-DP with the goal of granting higher
privacy protection to outliers than inliers. Their definition, also called
tailored differential privacy (TDP) measures the privacy of an individual by
how much of an outlier the individual is. Therefore, their work is focused on
releasing histograms where outliers are provided more privacy. Moreover, their
goal is to define privacy from the perspective of outlier rather than
differentially private outlier detection.

For differentially private outlier analysis, several relaxation for
$\epsilon$-DP have been proposed. They include anomaly-restricted DP [4],
protected DP [13], relaxed sensitivity [5], and sensitive privacy [2]. All
$\epsilon$-DP relaxation except for [2] assume that the outlier model is data-
independent. In fact, Bittner et al. [4] assumes that the database only
contains one outlier while Kearns et al. [13] is specific to anomalies
searching in social networks. Böhler et al. [5] provided a relaxation of
global sensitivity by assuming that there is a separating boundary between
outlier records from the inlier records. Moreover, their data perturbation
does not require a privacy budget distributed over a series of queries.
However, all the relaxed DP methods for outlier detection except for sensitive
privacy [2] are not applicable to our work since our outlier model is data-
dependent (distance based).

Practically, outlier models are data-dependent where the outlyingness of a
record is defined by its distance to the other records in the database.
Sensitive privacy [2] generalizes the above notions of privacy and provides a
formal privacy framework of $\epsilon$-DP for anomaly detection. This ensures
that the outlier identification mechanism is unaffected by the presence or the
absence of the individual’s record in the database. Their approach first
defines the the notion of sensitive record and constructs an appropriate
sensitive neighborhood graph that can be used for outlier detection. However,
sensitive privacy cannot be directly applied to our problem.

Another approach of satisfying DP for outlier detection is by addition of
noise to the aggregate statistics. Fan and Xiong [9] proposed anomaly
detection framework from continual aggregates of user statistics with
$\epsilon$-DP guarantee by adding Laplace noise. A filtering algorithm which
generate posterior estimates takes the perturbed aggregate and if it passes
the sensitivity analysis, it is released else it is corrected, then released.
This increases the accuracy of released aggregates. However, their method only
releases a one-dimensional time series with differential privacy and outlier
detection is applied to the released data as a post process.

Recently, differentially private $k$-NN algorithm has been proposed by Gursoy
et al. [10] which works by first converting $k$-NN classifiers to private
radius neighbors ($r-N$) classifiers. The $r-N$ classifier utilizes majority
vote among neighbors within a given radius. In order to add noise to satisfy
$\epsilon$-DP, sensitivity analysis is performed over a region overlap graph
that determines the overlaps among the radii $r$ of the test instances. Hence,
given a test instance, the task is to find an accurate $r$ without leaking the
distances among the training instances or data distribution. However, the
choice of $r$ needs to be carefully chosen. For example, adding Laplacian
noise with variance greater than 1 to a significantly low radius, say $r$=0.01
would completely destroy its accuracy and lead to extremely inaccurate
results. Another drawback of their approach is that the data owner must be
online and available to perform classification on a querier’s demand since the
privacy budget is distributed over a series of queries. A non-interactive
algorithm was proposed to alleviate the drawback but fails when the
dimensionality of data exceedingly high or $\epsilon$ is very small. However,
our approach is scalable for high dimensional data. Moreover, their approach
does not focus on designing a differential private outlier detection
algorithm.

##  3 Problem definition and basics of differential privacy

After stating the problem definition, we will briefly revisit the key concepts
of $k$-NN based outlier detection and $\epsilon$-DP.

###  3.1 Problem definition

From the outlier analysis perspective, there are two classes of samples within
a dataset. The first class consists of inliers which form the majority of data
in the dataset. The inliers are samples that stem from a common, arbitrary
generating distribution. The second class are the remaining samples which are
considered to be the outliers. The outliers follow (potentially several)
different generating distributions, distinct from the inlier distribution.

While we have no prior knowledge regarding the generating distributions, we
possess a reference dataset $X$, which consists of inliers only and can be
thought of as a training set. The _task_ is to give a $\epsilon$-DP algorithm
that yields an outlier classifier (a scoring function) based on $X$. Suppose
we are given a set of new data points $Y$, the outlier classifier should
return an outlier score $s_{y}$ for each $y\in Y$ which reflects a degree of
outlierness. In the following we describe the $k$-NN based approaches for
computing outlier scores.

###  3.2 $k$-NN outlier detection

$k$-NN based outlier detection works by considering those data points as
outliers, which have a large distance to their neighbors in the reference
dataset. There are two variants. The basic $k$-NN algorithm considers the
distance to the $k$th nearest neighbor as an outlier score, while the weighted
$k$-NN algorithm considers the total distance to all $k$ neighbors.

The rationale behind using $k$-NN for outlier detection is that inliers are
assumed to lie in regions with relatively high density, whereas outliers are
to be found in the less densely populated regions. Points in high density
regions have small distances to their neighbors compared to points in low
density regions. The parameter $k$ can be made larger to take into account
that outliers themselves might appear as higher density clusters, albeit
smaller in number.

In the following, let $X$ be the reference dataset and $y$ a point in the test
set $Y$, for which we want to obtain an outlier score $s_{y}$.

####  3.2.1 Basic $k$-NN.

Formally, for a given data point $y$ the basic $k$-NN algorithm [18] computes
its outlier score $s_{y}$ as the euclidean distance to its $k$th nearest
neighbor $x_{k}$ in $X$,

$s_{y}=||x_{k}-y||_{2}.$ (1)

####  3.2.2 Weighted $k$-NN.

In the weighted $k$-NN algorithm [1], instead of only considering the distance
to the $k$th nearest neighbor, the outlier score is computed as the sum of the
distances to _all_ $k$ nearest neighbors $x_{1},\dots,x_{k}$ of $y$ in $X$,

$s_{y}=\sum_{i=1}^{k}||x_{i}-y||_{2}.$ (2)

This is called _weighted_ $k$-NN, since the neighbors of $y$ are weighted by
their distance to $y$. In the literature, it is also known as aggregate $k$-NN
[19], which more appropriately reflects the summation of neighbor distances.
However, we stick to the term weighted, because our approach will in fact lead
to weights, when applied to this algorithm.

###  3.3 Differential Privacy

The definition of differential privacy is based on neighboring datasets, i. e.
datasets having the same number of elements, which differ by exactly one
element.

######  Definition 1 (Differential Privacy)

An algorithm $\mathcal{A}$ is said to be ($\epsilon$-)differentially private
($\epsilon$-DP), when for all neighboring datasets $D$, $D^{\prime}$ and for
all possible outcomes $O$ of $\mathcal{A}$,

$Pr\,[\mathcal{A}(D)=O]\leq e^{\epsilon}\cdot
Pr\,[\mathcal{A}(D^{\prime})=O].$ (3)

The parameter $\epsilon$ is the privacy budget. Intuitively, for small
$\epsilon$ a differentially private algorithm $\mathcal{A}$ will output the
same result for both datasets with high probability.

The Laplace Mechanism [8] can be used to design differentially private
algorithms. It relies on the global sensitivity of a query function
$f:D\rightarrow\mathbb{R}^{m}$.

######  Definition 2 (Global sensitivity)

The global sensitivity $\Delta f$ of a function $f$ is defined as the maximal
worst case change in $f$ when applied to two neighboring datasets $D$,
$D^{\prime}$,

$\Delta f:=\underset{D,\,D^{\prime}}{\max}||f(D)-f(D^{\prime})||.$ (4)

A differentially private algorithm can be constructed from a query function
$f:D\rightarrow\mathbb{R}^{m}$ with the Laplace Mechanism as follows [8]. Draw
i.i.d random variables $\eta_{i}$, $i=1,\dots,m$ from the Laplace distribution
$Lap(0,\epsilon^{-1}\Delta f)$ and add these to the output of $f$,

$\mathcal{A}(f,\,D)=f(D)+(\eta_{1},\dots,\eta_{m}).$ (5)

The algorithm $\mathcal{A}$ is now a $\epsilon$-DP version of query $f$.
Certain privacy guarantees are also ensured under composition and post-
processing, as is stated in the following result [16].

######  Theorem 3.1 (Composition and Post-Processing)

Let $D$ be any dataset, $\mathcal{A}_{1}$ and $\mathcal{A}_{2}$ be two
algorithms that satisfy $\epsilon_{1}$-DP and $\epsilon_{2}$-DP, respectively.
Then the following properties hold for $\mathcal{A}_{1}$ and
$\mathcal{A}_{2}$:

  1. 1.

Releasing the output of $\mathcal{A}_{1}(D)$ and $\mathcal{A}_{2}(D)$
satisfies $(\epsilon_{1}+\epsilon_{2})$-DP _(Sequential composition)_.

  2. 2.

Given another _disjoint_ dataset $D^{\prime}$, releasing
$\mathcal{A}_{1}(D_{1})$ and $\mathcal{A}_{2}(D_{2})$ satisfies
$\max(\epsilon_{1},\epsilon_{2})$-DP _(Parallel Composition)_.

  3. 3.

Any post-processed output of $\mathcal{A}_{1}(D)$ still satisfies
$\epsilon_{1}$-DP _(Post-processing immunity)_.

##  4 Our approach

(a)

(b)

Figure 1: Illustration of the grid modification for $b=2$, $d=3$. The sub-
cubes depict the data partition grid. (a) The reference data $X$ in grey and a
test point $y$ in red. Two cells contain six data points each. (b) Centroids
of the grid cells with weight $w_{i}=6$ for both populated cells and $w_{i}=0$
for the other cells.

Our differentially private versions of $k$-NN and weighted $k$-NN (w$k$-NN)
rely on data partitioning in order to allow querying the reference dataset $X$
with a low global sensitivity. Our approach has been inspired by Su et al.
[20], who used a similar partitioning procedure for $\epsilon$-DP $k$-means
clustering. We partition the dataset by choosing a number $b$ and splitting
each dimension into $b$ equally spaced intervals. This results in a uniform
data grid on top of the reference dataset, so that data points are being
assigned to grid cells. In the following, we refer to this procedure as _grid_
modification of (w)$k$-NN.

Instead of considering the exact location of points in the reference set $X$
to determine an outlier score for $y$, our grid modifications treat the points
of each cell as if they were all located at the cell’s centroid. Essentially,
our algorithm then only considers the centroids, weighted by the number of
points in the respective cell, to determine the outlier scores by Equations 1
and 2. Our procedure is illustrated in Figure 1, where two data partitions
contain six points each. To determine the outlier score of the red point with
respect to the reference data, instead of considering the raw location of each
$x\in X$, we treat the centroids of all cells as data points with weights
according to the number of elements in the respective cell as shown in Figure
1(b). The formal approach is given in Section 4.2. These grid modification
will subsequently be made $\epsilon-DP$ (Section 4.3). For better comparison,
we will analyze both the non-private and $\epsilon-DP$ versions of the grid
modification.

###  4.1 Preprocessing

Before applying outlier detection methods, datasets should be normalized and
centered, since this can improve performance drastically [12]. In particular,
for a given $d$-dimensional dataset $X$ with $x_{ij}$ representing the $j$th
dimension/feature value of the $i$th element, we first scale each dimension
$j$ to the unit interval by $\alpha_{j}$ (maximum absolute value), i. e.

$\alpha_{j}=\underset{i=1,\dots,N}{\max}|x_{ij}|.$ (6)

We then perform a linear mapping from the resulting interval $[-1,1]$ onto the
unit interval. Next we center each dimension by subtracting the respective
mean value $\bar{x}_{j}$. We obtain a centered unit hypercube. The scaling and
centering parameters $\alpha_{j}$ and $\bar{x_{j}}$ are retained for later
processing of the test data. Coordinates of data points in the test data that
lie outside the unit interval after transformation are mapped to $0$ or $1$,
depending on whether they are negative or greater than 1, respectively.

###  4.2 Grid modification of $k$-NN and weighted $k$-NN

For our approach, we choose a grid parameter $b$ and construct a regular grid
on the dataset by splitting each dimension into $b$ equidistant intervals,
resulting in a grid partition with a total of $d^{b}$ cells, each being a
hypercube with edge length $\frac{1}{b}$. Let $q_{f}(c)$ denote the number of
data points in each cell $c$ (count query). To answer a $k$-NN query, a
trusted server with access to the original dataset $X$, will perform Algorithm
1.

Our algorithm first looks up the grid cell $c_{y}$ in the reference dataset,
in which a data point of interest $y$ resides (line 1). It will then traverse
all neighboring cells $C_{y}$ of data point $y$ in the order of their
respective distance to $y$ (where distance is measured from the centroid of
each neighboring cell $c\in C_{y}$; lines 1–1). The algorithm terminates
either when the cumulative number of elements in the traversed cells exceeds
the threshold value $k$ (line 1), or when a given maximal neighbor depth
$\delta_{\max}$ has been reached (line 1). In case of our grid modification of
basic $k$-NN, it will return the distance from point $y$ to the last visited
neighbor cell (line 1). In case of our grid modification of w$k$-NN, it will
return the weighted sum of all distances of the visited cells; the weights
beeing the count queries $q_{f}(c)$ (line 1).

In the next subsection we will formally describe the mechanism, by which our
grid modifications are made $\epsilon$-DP.

Input : preprocessed reference dataset $X\in\mathbb{R}^{n\times d}$, a new
data point $y\in\mathbb{R}^{d}$, partitioning parameter $b\in\mathbb{N}$,
parameter $k\in\mathbb{N}$, maximal neighbour depth $\delta_{\max}$,
$weighted\in\\{0,1\\}$

Output : outlier score $s_{y}$

1 begin

2 $c_{y}\longleftarrow$ grid cell, in which $y$ resides

3 $C_{y}\longleftarrow$ neighboring cells of $c_{y}$ with
$||\bar{c}-\bar{c}_{y}||_{1}\leq\delta_{\max},\forall c\in C_{y}$, where
$\bar{c}$ denotes the centroid of a cell

4 for  _$c\in C_{y}$_ do

5 // Collect distances to point $y$ to neighbor cells for sorting

6 $dist_{y}(c)\longleftarrow||y-\bar{c}||_{1}$

7

8 end for

9 $\widetilde{C_{y}}\longleftarrow C$ sorted by $dist_{y}(c_{i})$ in ascending
order

10 $Q\longleftarrow 0$ $s_{y}\longleftarrow 0$

11 for  _$c\in\widetilde{C_{y}}$ _ do

12 // $Q$ will keep track of how many points (cell count) we have visited

13 $Q\longleftarrow Q+q_{f}(c)$

14 $dist_{c}\longleftarrow||\bar{c}-\bar{c}_{y}||_{1}$

15 if  _weighted_ then

16 $s_{y}\longleftarrow s_{y}+q_{f}(c)\cdot dist_{c}$

17 // Sum weighted distances

18

19 else

20 $s_{y}\longleftarrow dist_{c}$

21 // Keep last distance only

22

23 end if

24 if  _$Q\geq k$_ then

25 break

26 // Terminate when threshold $k$ exceeded

27

28 end if

29

30 end for

31 return $s_{y}$

32 end

33

Algorithm 1 Grid modification of (w)$k$-NN outlier detection

###  4.3 Privacy mechanism for our approach

The count queries $q_{f}$ in our grid modifications of (w)$k$-NN can be
perturbed according to the Laplace-Mechanism to fulfil $\epsilon$-DP. To this
end, we first examine the global sensitivity of the count query function
$q_{f}$, which returns the number of elements in a given cell. The result is
given in the following Lemma.

###### Lemma 1

Let $D$ be any dataset, $C_{D}$ a partition of the domain of $D$ into cells
and $q_{f}:C_{D}\rightarrow\mathbb{N}_{0}$ the count query, which returns the
number of elements of $D$ $c\in C_{D}$. Then, the global sensitivity of the
count query function

$\Delta q_{f}=1.$ (7)

###### Proof

Let $D$, $D^{\prime}$ be two neighboring datasets, then there exists an $x\in
D$, which is replaced by $x^{\prime}\in D^{\prime}$, so that
$D\setminus{\\{x\\}}=D^{\prime}\setminus{\\{x^{\prime}\\}}$. Therefore, for
any $c\in C_{D}$ we have a corresponding $c^{\prime}\in C_{D^{\prime}}$, with
$c\setminus{\\{x\\}}=c^{\prime}\setminus{\\{x^{\prime}\\}}$ and hence
$|q_{f}(c)-q_{f}(c^{\prime})|=\big{|}|c|-|c^{\prime}|\big{|}=|\mathbf{1}_{\\{x\\}\in
c}-\mathbf{1}_{\\{x^{\prime}\\}\in c^{\prime}}|$, which is either $0$ or $1$.
∎

Thus, we obtain a differentially private count query $q^{*}_{f}(c)$ by adding
Laplace noise $\eta_{c}\sim Lap\left(\frac{1}{\epsilon}\right)$,

$q_{f}^{*}(c):=q_{f}(c)+\eta_{c}.$ (8)

Note that $q_{f}^{*}$ can take negative values, which however is desired,
since otherwise the distribution of cell counts would be skewed towards
positive values [20]. The noise variables $\eta_{c}$ will be realised only
once per cell $c$, to ensure privacy for repeated cell querying (see Theorem
4.1), which is indicated by the index $c$.

To answer a $k$-NN outlier detection query under $\epsilon$-DP, a trusted
server with access to the original unperturbed dataset will perform the grid
modifications of (w)$k$-NN (Algorithm 1), albeit replacing $q_{f}$ by the
perturbed count query $q^{*}_{f}$ in lines 1 and 1. The server will retain all
perturbed cell counts $q^{*}_{f}(c)$, once realised, and output the retained
value, in case a cell is queried repeatedly in order to prevent leakage of the
true value.

###### Theorem 4.1

Replacing $q_{f}$ by $q_{f}^{*}$ in Algorithm 1 will give an $\epsilon$-DP
version of our grid modification, provided that the random noise is realised
only once giving $\eta_{c}$ for each cell $c$ and then being kept constant.

###### Proof

The Laplace Mechanism guarantees that count query $q_{f}^{*}$ is $\epsilon$-DP
by Lemma 1. Algorithm 1 returns outlier score $s_{y}$, which is dependent on
the distance between cell centroids, $dist_{c}$ as well as $Q$ (the variable
that tracks how many points have been visited; see line 15) and
$\delta_{\max}$ (termination conditions). The maximum depth $\delta_{\max}$ is
constant. All distances $dist_{c}$ are independent of the dataset $D$, but
their composition (or last value in case of basic $k$-NN) is dependent on $Q$.
However, $Q$ is a parallel composition of $q_{f}^{*}$ for disjoint cells and
by Theorem 3.1 it is $\epsilon$-DP. By the post-processing property in Theorem
3.1 the computation of $dist_{c}$ is then also $\epsilon$-DP. Finally,
repeated querying of the same cell will result in the same output, since the
noise variable $\eta_{c}$ is realised only once for each cell, so that no
further information is gained, in case of sequential composition of Algorithm
1 on the same cell ($\epsilon_{i}=0,\forall i\geq 2$). ∎

##  5 Experiments

We designed our experiments to investigate the following research questions:

###### RQ 1

How does our non-private grid modification impact outlier detection
performance compared to basic $k$-NN and weighted $k$-NN?

###### RQ 2

How do our $\epsilon$-DP grid modifications compare to the non-private
baselines (w)$k$-NN and our non-private grid modifications?

###### RQ 3

What is the effect of the privacy budget $\epsilon$ on the performance of our
approach?

###  5.1 Dataset

We evaluated our approach using five benchmark real-world classification
datasets that have been previousy used for evaluating outlier detection
algorithms. We obtained all these datasets from the UCI Machine Learning
Database [7]. Statistics of all dataset are shown in Table 1

Lymph The Lymph dataset represents lymphographical patient data and is divided
according to radiographical examination findings. Only six patients had
findings normal or fibrosis. These are considered outliers. Three of the 17
measured attributes are continuous.

Diabetes The Diabetes dataset consists of diabetes test findings of Pima
Indians and eight medical predictors, all being continuous. The outliers are
the subjects, who were diagnosed positive.

Wdbc The Wdbc dataset describes diagnostic findings for breast cancer. Nuclear
characteristics are represented in 30 continuous attributes. Outliers are the
malignant findings.

Heart The Heart dataset consists of patients classified as healthy or as
having heart related problems. It has 13 continuous predictor variables.

Adult The Adult is the only non-medical dataset. We included it, since it was
used in [17] for evaluation of a privacy preserving method for outlier
detection. It contains seven socio-demographic continuous predictors and an
income level class. The outliers are individuals, who had a yearly salary
above $50,000.

Table 1: Statistics of the datasets used in experiments. | Dataset
---|---
Statistic | Lymph | Diabetes | Wdbc | Heart | Adult
Dimension $d$ | 3 | 8 | 30 | 13 | 7
Size of reference set | 113 | 400 | 285 | 110 | 19,776
Size of test set | 35 | 140 | 82 | 38 | 5,044
Outliers in test set | 6 | 40 | 10 | 10 | 100

###  5.2 Setup

Adhering to common practice [19], we treated the first $m$ instances of the
minority class in each dataset as outliers. The value $m$ was chosen according
to previous studies with these datasets [23, 6]. Consequently, the outlier
were downsampled in all datasets except the Lymph data. The remaining data
were labeled as inliers. The datasets and their statistics are shown in Table
1. We only included continuous and dichtomous variables from the datasets.

For each dataset, 80 % of the inliers were used as training dataset, which was
used by the algorithm as a reference set to identify outliers. The remaining
20 % were appended to set of outliers to build the test set. Pre-processing
was applied to both datasets as described in Section 4.1.

We ran our algorithm on each dataset with different values of $k$-NN parameter
$k$, grid parameter $b$ and privacy budget $\epsilon$. After selecting
appropriate values of $k$, we first varied the grid parameter $b$ in range
$b\in[2,10]$, to examine its impact on both our non-private and $\epsilon$-DP
grid modifications. From these results, we selected the smallest $b$ that
maximized the AUROC of our $\epsilon$-DP grid modifications for each dataset.
We used the selected parameters of $k$ and $b$ to evaluate our $\epsilon$-DP
grid modifications (DP Grid $k$-NN and DP Grid w$k$-NN) for different values
of $\epsilon$ in comparison to the non-private grid modifications and
(w)$k$-NN. The algorithm was run with values of
$\epsilon\in\\{5,2.5,1.25,.6,.3,.15,.075,.035,.015\\}$ to evaluate its
performance with respect to the privacy budget.

To account for random variability in the private algorithms’ performance due
to the Laplace noise, both $\epsilon$-DP versions of Algorithm 1 were applied
ten times on each dataset with different initial seeds for the random number
generator. We report mean performance and standard deviation over the ten
runs.

Figure 2: Comparison of algorithms with respect to the AUROC for different
grid partition parameters $b$ (left) and privacy budgets $\epsilon$ (right).
Figure 3: Comparison of algorithms with respect to the average precision (AP,
left) and the precision at $n$ ($P@n$, right) for different privacy budgets
$\epsilon$.

###  5.3 Results

We report outlier detection performance on the five datasets in terms of the
AUROC, the average precision (AP) and the precision at $n$ ($P@n$) [6]. We
compare our approach to the four baselines, basic and weighted $k$-NN as well
as the non-private grid modifications of these. For $P@n$, we set $n$ to the
actual number of outliers in each test set. In case of our private approach,
the $\epsilon$-DP grid modifications, mean and standard deviation (error bars)
over all ten iterations of the algorithm for different seeds are reported for
each dataset. The results are presented in Figures 2 and 3.

RQ 1. The unmodified (w)$k$-NN algorithms performed in nearly all cases best,
which is expected, because the modified versions introduce information loss
(green lines). The Adult dataset was the only dataset, for which none of the
algorithms showed acceptable performance. We present the results nonetheless,
to document this anomalous case.

We found that our non-private grid modifications showed only a modest decline
in performance for parameters $b=2$ compared to unmodified (w)$k$-NN. Notably,
in all but the Adult data even small grid parameters $b\geq 3$ yield mostly
comparable results and sometimes even outperforms (w)$k$-NN (green vs. red
lines in Figure 2, left). This might be explained by considering the grid
mechanism as some kind of regularizer, which could help to eliminate irrelvant
small deviations within the grid partitions that would otherwise impact the
exact $k$-NN distances negatively.

RQ 2 For our private grid modifications, a decline in outlier detection
performance is expected for larger values of $b$: at first, a larger $b$
increases data resolution, since the grid cells become smaller and hence the
distance between the original data points and the cell centroids decreases.
Nonetheless, the more cells are created, the more error is introduced by the
Laplace Mechanism. This error largely outweighs the benefit of a better
resolution, as can be seen in the performance decline in the Lymph and Wdbc
datasets (blue and black lines in Figure 2, left). In the Adult dataset this
relationship is reversed. However, this might be explained by the already
large proportion of errors in the grid modifications, which seems unaffected
by additional Laplace noise.

RQ 3 For all datasets, our basic $\epsilon$-DP grid algorithm performed
slightly better than our weighted version (blue vs. black lines). Our approach
showed performance nearly comparable to the four non-private baselines for all
metrics on the lower dimensional Lymph ($\epsilon=.15$), Diabetes
($\epsilon=.3$) and Adult ($\epsilon=.15$) data. For the higher dimensional
Heart data, the $P@n$ of our private approach was nearly as good as (w)$k$-NN
for $\epsilon=.3$. Finally, the AUROC for the Wdbc data, which had the most
dimensions, converged towards the non-private baselines for $\epsilon=5$. As
expected, a larger privacy budget $\epsilon$ resulted in better performance. A
smaller privacy budgets $\epsilon$ evidently introduces a larger amount of
noise being added to the cell counts. This is reflected in the results for the
Lymph , Diabetes and the AUROC of the Wdbc data, but not for the Heart or
Adult data, and not for the AP and $P@n$ of the Wdbc data. This could be
explained by the higher dimensionality of both Wdbc and Heart data, and the
anomaly in Adult data. A larger number of dimensions results in a larger
number of grid cells even for low values of $b$, and therefore additional
noise by the Laplace Mechanism.

##  6 Conclusion

This is the first study, which combines $\epsilon$-differential privacy and
$k$-NN based outlier detection. We proposed, analysed and evaluated a
$\epsilon$-DP grid modification approach of basic and weighted $k$-NN outlier
detection, which performs well on five real-world datasets for reasonably
small privacy budgets. We found that our non-private grid modifications of
both the basic and weighted $k$-NN result in no notable performance loss
compared to unmodified (w)$k$-NN. Consequently, the expected impact on outlier
detection performance in the private setting can be solely attributed to the
privacy guarantees and does not result from data partitioning. The results
underline that the $\epsilon$-DP grid modification is a promising candidate
for privacy preserving outlier detection and could give even stronger results,
when applied under relaxed DP guarantees.

## Acknowledgments

This work is in part funded by the Lower Saxony Ministry of Science and
Culture under grant number ZN3491 within the Lower Saxony ”Vorab” of the
Volkswagen Foundation and supported by the Center for Digital Innovations
(ZDIN), and the Federal Ministry of Education and Research (BMBF), Germany
under the project LeibnizKILabor (grant number 01DD20003).

## References

  * [1] Angiulli, F., Pizzuti, C.: Fast outlier detection in high dimensional spaces. In: European Conference on Principles of Data Mining and Knowledge Discovery. pp. 15–27. Springer (2002)
  * [2] Asif, H., Papakonstantinou, P.A., Vaidya, J.: How to accurately and privately identify anomalies. In: Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. pp. 719–736 (2019)
  * [3] Asif, H., Papakonstantinou, P.A., Vaidya, J.: A guide for private outlier analysis. IEEE letters of the Computer Society 3(1), 29–33 (2020)
  * [4] Bittner, D.M., Sarwate, A.D., Wright, R.N.: Using noisy binary search for differentially private anomaly detection. In: International Symposium on Cyber Security Cryptography and Machine Learning. pp. 20–37. Springer (2018)
  * [5] Böhler, J., Bernau, D., Kerschbaum, F.: Privacy-preserving outlier detection for data streams. In: IFIP Annual Conference on Data and Applications Security and Privacy. pp. 225–238. Springer (2017)
  * [6] Campos, G.O., Zimek, A., Sander, J., Campello, R.J.G.B., Micenková, B., Schubert, E., Assent, I., Houle, M.E.: On the evaluation of unsupervised outlier detection: Measures, datasets, and an empirical study. Data Mining and Knowledge Discovery 30(4), 891–927 (2016). https://doi.org/10.1007/s10618-015-0444-8
  * [7] Dua, D., Graff, C.: UCI machine learning repository (2017), http://archive.ics.uci.edu/ml
  * [8] Dwork, C.: Differential privacy: A survey of results. In: International Conference on Theory and Applications of Models of Computation. pp. 1–19. Springer (2008)
  * [9] Fan, L., Xiong, L.: Differentially private anomaly detection with a case study on epidemic outbreak detection. In: 2013 IEEE 13th International Conference on Data Mining Workshops. pp. 833–840. IEEE (2013)
  * [10] Gursoy, M.E., Inan, A., Nergiz, M.E., Saygin, Y.: Differentially private nearest neighbor classification. Data Mining and Knowledge Discovery 31(5), 1544–1575 (2017)
  * [11] Hamlet, C., Straub, J., Russell, M., Kerlin, S.: An incremental and approximate local outlier probability algorithm for intrusion detection and its evaluation. Journal of Cyber Security Technology 1(2), 75–87 (Apr 2017). https://doi.org/10.1080/23742917.2016.1226651
  * [12] Kandanaarachchi, S., Muñoz, M.A., Hyndman, R.J., Smith-Miles, K.: On normalization and algorithm selection for unsupervised outlier detection. Data Mining and Knowledge Discovery 34(2), 309–354 (2020)
  * [13] Kearns, M., Roth, A., Wu, Z.S., Yaroslavtsev, G.: Private algorithms for the protected in social network search. Proceedings of the National Academy of Sciences 113(4), 913–918 (2016)
  * [14] Kriegel, H.P., Kröger, P., Zimek, A.: Outlier detection techniques. Tutorial at KDD 10, 1–76 (2010)
  * [15] Lui, E., Pass, R.: Outlier privacy. In: Theory of Cryptography Conference. pp. 277–305. Springer (2015)
  * [16] McSherry, F.D.: Privacy integrated queries: An extensible platform for privacy-preserving data analysis. In: Proceedings of the 2009 ACM SIGMOD International Conference on Management of Data. pp. 19–30 (2009)
  * [17] Okada, R., Fukuchi, K., Sakuma, J.: Differentially Private Analysis of Outliers. In: Appice, A., Rodrigues, P.P., Santos Costa, V., Gama, J., Jorge, A., Soares, C. (eds.) Machine Learning and Knowledge Discovery in Databases. pp. 458–473. Lecture Notes in Computer Science, Springer International Publishing, Cham (2015). https://doi.org/10.1007/978-3-319-23525-728
  * [18] Ramaswamy, S., Rastogi, R., Shim, K.: Efficient algorithms for mining outliers from large data sets. In: Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. pp. 427–438 (2000)
  * [19] Schubert, E., Zimek, A., Kriegel, H.P.: Local outlier detection reconsidered: A generalized view on locality with applications to spatial, video, and network outlier detection. Data Mining and Knowledge Discovery 28(1), 190–237 (Jan 2014). https://doi.org/10.1007/s10618-012-0300-z
  * [20] Su, D., Cao, J., Li, N., Bertino, E., Jin, H.: Differentially private k-means clustering. In: Proceedings of the Sixth ACM Conference on Data and Application Security and Privacy. pp. 26–37 (2016)
  * [21] Tang, B., He, H.: A local density-based approach for outlier detection. Neurocomputing 241, 171–180 (Jun 2017). https://doi.org/10.1016/j.neucom.2017.02.039
  * [22] Williams, G., Baxter, R., He, H., Hawkins, S., Gu, L.: A comparative study of RNN for outlier detection in data mining. In: 2002 IEEE International Conference on Data Mining, 2002. Proceedings. pp. 709–712. IEEE (2002)
  * [23] Zhang, K., Hutter, M., Jin, H.: A New Local Distance-Based Outlier Detection Approach for Scattered Real-World Data. In: Theeramunkong, T., Kijsirikul, B., Cercone, N., Ho, T.B. (eds.) Advances in Knowledge Discovery and Data Mining. pp. 813–822. Lecture Notes in Computer Science, Springer, Berlin, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01307-2_84