* [11] Adam Coates and Andrew Y. Ng.  Learning feature representations with $k$-means.  In Grégoire Montavon, Genevieve B. Orr, and Klaus-Robert Müller, editors, Neural Networks: Tricks of the Trade - Second Edition, volume 7700 of Lecture Notes in Computer Science, pages 561–580. Springer, 2012.
  * [12] Michael B Cohen, Yin Tat Lee, Cameron Musco, Christopher Musco, Richard Peng, and Aaron Sidford.  Uniform sampling for matrix approximation.  In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 181–190. ACM, 2015.
  * [13] Michael B Cohen, Cameron Musco, and Christopher Musco.  Input sparsity time low-rank approximation via ridge leverage score sampling.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1758–1777. SIAM, 2017.
  * [14] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, and Chris Schwiegelshohn.  Towards optimal lower bounds for $k$-median and $k$-means coresets.  In STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 1038–1051. ACM, 2022.
  * [15] Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar.  Improved coresets for Euclidean $k$-means.  In Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, 2022\.
  * [16] Vincent Cohen-Addad and Jason Li.  On the fixed-parameter tractability of capacitated clustering.  In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1–41:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [17] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn.  Improved coresets and sublinear algorithms for power means in euclidean spaces.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 21085–21098, 2021.
  * [18] Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn.  A new coreset framework for clustering.  In Samir Khuller and Virginia Vassilevska Williams, editors, STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 169–182. ACM, 2021.
  * [19] Petros Drineas, Michael W Mahoney, and Shan Muthukrishnan.  Sampling algorithms for $\ell_{2}$ regression and applications.  In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, pages 1127–1136. Society for Industrial and Applied Mathematics, 2006.
  * [20] Dan Feldman and Michael Langberg.  A unified framework for approximating and clustering data.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 569–578, 2011.
  * [21] Dan Feldman, Melanie Schmidt, and Christian Sohler.  Turning big data into tiny data: Constant-size coresets for $k$-means, pca and projective clustering.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1434–1453. SIAM, 2013.
  * [22] Yann Guermeur.  Vc theory of large margin multi-category classifiers.  The Journal of Machine Learning Research, 8:2551–2594, 2007.
  * [23] Sariel Har-Peled and Soham Mazumdar.  On coresets for $k$-means and $k$-median clustering.  In 36th Annual ACM Symposium on Theory of Computing,, pages 291–300, 2004.
  * [24] Lingxiao Huang, Ruiyuan Huang, Zengfeng Huang, and Xuan Wu.  On coresets for clustering in small dimensional euclidean spaces.  CoRR, abs/2302.13737, 2023.
  * [25] Lingxiao Huang, Shaofeng H.-C. Jiang, Jian Li, and Xuan Wu.  $\varepsilon$-coresets for clustering (with outliers) in doubling metrics.  In 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 814–825. IEEE Computer Society, 2018.
  * [26] Lingxiao Huang, Shaofeng H.-C. Jiang, Jianing Lou, and Xuan Wu.  Near-optimal coresets for robust clustering.  The Eleventh International Conference on Learning Representations, 2023.
  * [27] Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi.  Coresets for clustering with fairness constraints.  In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d’Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 7587–7598, 2019.
  * [28] Lingxiao Huang, K Sudhir, and Nisheeth Vishnoi.  Coresets for regressions with panel data.  Advances in Neural Information Processing Systems, 33:325–337, 2020\.
  * [29] Lingxiao Huang, K. Sudhir, and Nisheeth K. Vishnoi.  Coresets for time series clustering.  In Marc’Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 22849–22862, 2021.
  * [30] Lingxiao Huang and Nisheeth K. Vishnoi.  Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal.  In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 1416–1429. ACM, 2020.
  * [31] Ibrahim Jubran, Alaa Maalouf, and Dan Feldman.  Fast and accurate least-mean-squares solvers.  In Advances in Neural Information Processing Systems, pages 8305–8316, 2019.
  * [32] Michael Langberg and Leonard J Schulman.  Universal $\varepsilon$-approximators for integrals.  In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 598–607. SIAM, 2010.
  * [33] Mu Li, Gary L Miller, and Richard Peng.  Iterative row sampling.  In 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pages 127–136. IEEE, 2013.
  * [34] Stuart P. Lloyd.  Least squares quantization in PCM.  IEEE Trans. Information Theory, 28(2):129–136, 1982.
  * [35] Mario Lucic, Matthew Faulkner, Andreas Krause, and Dan Feldman.  Training Gaussian mixture models at scale via coresets.  The Journal of Machine Learning Research, 18(1):5885–5909, 2017\.
  * [36] Sepideh Mahabadi, Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn.  Nonlinear dimension reduction via outer bi-lipschitz extensions.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1088–1101, 2018.
  * [37] Pascal Massart, Jean Picard, and École d’été de probabilités de Saint-Flour.  Concentration inequalities and model selection.  2007\.
  * [38] Shyam Narayanan and Jelani Nelson.  Optimal terminal dimensionality reduction in Euclidean space.  Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019.
  * [39] Balas K Natarajan.  On learning sets and functions.  Machine Learning, 4:67–97, 1989.
  * [40] Noam Nisan and Avi Wigderson.  Hardness vs randomness.  Journal of computer and System Sciences, 49(2):149–167, 1994.
  * [41] Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler.  Fair coresets and streaming algorithms for fair $k$-means.  In Evripidis Bampis and Nicole Megow, editors, Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers, volume 11926 of Lecture Notes in Computer Science, pages 232–251. Springer, 2019.
  * [42] Christian Sohler and David P. Woodruff.  Strong coresets for $k$-median and subspace approximation: Goodbye dimension.  In FOCS, pages 802–813. IEEE Computer Society, 2018.
  * [43] Pang-Ning Tan, Michael Steinbach, Vipin Kumar, et al.  Cluster analysis: basic concepts and algorithms.  Introduction to data mining, 8:487–568, 2006.
  * [44] Murad Tukan, Xuan Wu, Samson Zhou, Vladimir Braverman, and Dan Feldman.  New coresets for projective clustering and applications.  In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera, editors, International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of Proceedings of Machine Learning Research, pages 5391–5415. PMLR, 2022\.
  * [45] Ramon van Handel.  Probability in high dimension.  2014\.
  * [46] Jean-Louis Verger-Gaugry.  Covering a ball with smaller equal balls in r${}^{\mbox{n}}$.  Discret. Comput. Geom., 33(1):143–155, 2005.
  * [47] Tong Zhang.  Covering number bounds of certain regularized linear function classes.  Journal of Machine Learning Research, 2(Mar):527–550, 2002.

##  Appendix A Extension of Algorithm 1 to Any Constant $z\geq 1$

We need to generalize the notations of rings and groups. Again, we let
$A^{\star}=\left\\{a^{\star}_{1},\ldots,a^{\star}_{k}\in\mathcal{X}\right\\}\in\mathcal{X}^{k}$
be a constant approximation for the $(k,z)$-Clustering problem.

##### Ring structure and group structure for general $z\geq 1$.

We let $\Delta_{i}=\frac{\mathrm{cost}_{z}(P_{i},A^{\star})}{|P_{i}|}$ and
define _ring_ $R_{ij}:=\left\\{p\in P_{i}:2^{j}\Delta_{i}\leq
d^{z}(p,A^{\star})<2^{j+1}\Delta_{i}\right\\}$. The range of $j$ for main
rings is generalized to be $z\log(\varepsilon/z)<j<2z\log(z\varepsilon^{-1})$.

For the group structure, we generalize the range of $b$ to be
$z\log(\varepsilon/4z)-\log k<b\leq 0$. Observation 3.3 is generalized as
follows.

######  Observation A.1 (Main group cost for general $z\geq 1$ [14])

Let $G\in\mathcal{G}^{(m)}$ be a main group. Let $i\in[k]$ be an integer
satisfying that $P_{i}\cap G\neq\emptyset$. For any $p\in P_{i}\cap G$, we
have

$\mathrm{cost}_{z}(G,A^{\star})\leq 2k\cdot\mathrm{cost}_{z}(P_{i}\cap
G,A^{\star})\leq 4k\cdot|P_{i}\cap G|\cdot d^{z}(p,A^{\star}).$

We also generalize Lemma 3.4.

######  Lemma A.2 (Group number for general $z\geq 1$)

For general $z\geq 1$, there exist at most
$O(z^{2}\log(k\varepsilon^{-1})\log(z\varepsilon^{-1}))$ groups in
$\mathcal{G}$.

By using the above general group structure $\mathcal{G}$, we can generalize
Algorithm 1 to any constant $z\geq 1$. The only difference is that in Line 1
of Algorithm 1, we let the probability be
$\frac{d^{z}(p,A^{\star})}{\mathrm{cost}_{z}(G,A^{\star})}$ and let weights
$w(p)=\frac{\mathrm{cost}_{z}(G,A^{\star})}{\Gamma_{G}\cdot
d^{z}(p,A^{\star})}$.

##  Appendix B Proof of Theorem 3.10

We complete the missing details of the proof of Theorem 3.10 from Lemma 3.12.
in Section 3.5. The proof is almost the same as that in [14].

##### Proof:

[of Theorem 3.10] We have

$\displaystyle\mathbb{E}_{S}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(P,C+A^{\star})}\cdot\left|\sum_{p\in
S}w(p)\cdot d(p,C)-\mathrm{cost}(P,C)\right|\right]$ $\displaystyle\leq$
$\displaystyle\mathbb{E}_{S}\sup_{C\in\mathcal{X}^{k}}\sum_{G\in\mathcal{G}}\left[\frac{1}{\mathrm{cost}(P,C+A^{\star})}\cdot\left|\sum_{p\in
S_{G}}w(p)\cdot d(p,C)-\mathrm{cost}(G,C)\right|\right]$
$\displaystyle+\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(P,C+A^{\star})}\cdot\left|\sum_{i\in[k]}w(a^{\star}_{i})\cdot
d(a^{\star}_{i},C)-\mathrm{cost}(P\setminus G,C)\right|\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{S}\sup_{C\in\mathcal{X}^{k}}\sum_{G\in\mathcal{G}}\left[\frac{\mathrm{cost}(G,C+A^{\star})}{\mathrm{cost}(P,C+A^{\star})}\cdot\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left|\frac{\sum_{p\in
S_{G}}w(p)\cdot
d(p,C)-\mathrm{cost}(G,C)}{\mathrm{cost}(G,C+A^{\star})}\right|\right]$
$\displaystyle+\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(P,C+A^{\star})}\cdot\left|\sum_{i\in[k]}w(a^{\star}_{i})\cdot
d(a^{\star}_{i},C)-\mathrm{cost}(P\setminus G,C)\right|\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{S}\sup_{C\in\mathcal{X}^{k}}\sum_{G\in\mathcal{G}}\left[\frac{\mathrm{cost}(G,C+A^{\star})}{\mathrm{cost}(P,C+A^{\star})}\cdot
3\varepsilon\right]+\varepsilon\quad\quad(\text{Lemma\leavevmode\nobreak\
\ref{lm:key}})$ $\displaystyle\leq$ $\displaystyle 4\varepsilon.$

By the Markov inequality, with probability at least 0.9, the following
inequality holds

$\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(P,C+A^{\star})}\cdot\left|\sum_{p\in
S}w(p)\cdot d(p,C)-\mathrm{cost}(P,C)\right|\right]\leq 40\varepsilon.$

Then for any $C\in\mathcal{X}^{k}$, we have

$\left|\sum_{p\in S}w(p)\cdot d(p,C)-\mathrm{cost}(P,C)\right|\leq
40\varepsilon\cdot(\mathrm{cost}(P,C+A^{\star}))\leq
O(\varepsilon)\cdot\mathrm{cost}(P,C),$

since $A^{\star}$ is an $O(1)$-approximate solution. This completes the proof.
$\square$

##  Appendix C Proof of Lemma 3.16: Error Analysis for $x^{C}$

##### Proof:

The proof idea is from that in [14, Lemma 15]. We have

$\displaystyle\begin{aligned}
&\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(G,C+A^{\star})}\left|\sum_{p\in
S_{G}}w(p)\cdot x^{C}_{p}-\|x^{C}\|_{1}\right|\right]\\\
=&\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(G,C+A^{\star})}\left|\sum_{p\in
S_{G}}w(p)\cdot
x^{C}_{p}-\|x^{C}\|_{1}\mid\xi_{G}\right|\right]\cdot\Pr\left[\xi_{G}\right]\\\
&+\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(G,C+A^{\star})}\left|\sum_{p\in
S_{G}}w(p)\cdot
x^{C}_{p}-\|x^{C}\|_{1}\mid\overline{\xi_{G}}\right|\right]\cdot\Pr\left[\overline{\xi_{G}}\right].\end{aligned}$
(35)

For the first term on the right side, a trivial upper bound for
$\Pr\left[\xi_{G}\right]$ is 1. For each $C\in\mathcal{X}^{k}$, let
$M_{C}\subseteq[k]$ be the collection of $i$ with $P_{i}\cap(H(G,C)\cup
T(G,C))=\emptyset$. Assuming $\xi_{G}$ holds, we have that

$\displaystyle\begin{aligned} \sum_{p\in S_{G}}w(p)\cdot x^{C}_{p}&=\sum_{i\in
M_{C}}\sum_{p\in P_{i}\cap S_{G}}w(p)\cdot x^{C}_{p}&\\\ &=\sum_{i\in
M_{C}}(d(a^{\star}_{i},C)-2^{j+1}\Delta_{i})\cdot\sum_{p\in P_{i}\cap
S_{G}}w(p)&(\text{Definition\leavevmode\nobreak\ \ref{def:split_main}})\\\
&\in(1\pm\varepsilon)\sum_{i\in
M_{C}}(d(a^{\star}_{i},C)-2^{j+1}\Delta_{i})\cdot|P_{i}\cap G|&(\text{Defn. of
$\xi_{G}$})\\\
&\in(1\pm\varepsilon)\cdot\|x^{C}\|_{1},&(\text{Definition\leavevmode\nobreak\
\ref{def:split_main}})\end{aligned}$ (36)

which implies that

$\displaystyle\begin{aligned}
&\quad\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(G,C+A^{\star})}\left|\sum_{p\in
S_{G}}w(p)\cdot
x^{C}_{p}-\|x^{C}\|_{1}\right|\mid\xi_{G}\right]\cdot\Pr\left[\xi_{G}\right]&\\\
\leq&\quad\varepsilon\cdot\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(G,C+A^{\star})}\|x^{C}\|_{1}\right]&(\text{Ineq.\leavevmode\nobreak\
(\ref{ineq2:proof_main_small_x})})\\\ \leq&\quad\varepsilon.&(\text{triangle
ineq.})\end{aligned}$ (37)

On the other hand, assuming $\xi_{G}$ does not hold, we have
$\Pr\left[\overline{\xi_{G}}\right]\leq
k\cdot\exp(-\varepsilon^{2}\Gamma_{G}/9k)$ by Lemma 3.13. Since
$\Gamma_{G}\geq O(k\varepsilon^{-2}\log k)$, we have
$\Pr\left[\overline{\xi_{G}}\right]\leq\varepsilon/4k$. Moreover,

$\displaystyle\begin{aligned} \sum_{p\in S_{G}}w(p)\cdot
x^{C}_{p}=&\quad\sum_{i\in M_{C}}\sum_{p\in P_{i}\cap S_{G}}w(p)\cdot
x^{C}_{p}&\\\ =&\quad\sum_{i\in M_{C}}d(a^{\star}_{i},C)\cdot\sum_{p\in
P_{i}\cap S_{G}}\frac{\mathrm{cost}(G,A^{\star})}{\Gamma_{G}\cdot
d(p,A^{\star})}&(\text{Defn. of $w(p)$})\\\ \leq&\quad\sum_{i\in
M_{C}}d(a^{\star}_{i},C)\cdot\sum_{p\in P_{i}\cap S_{G}}\frac{4k|P_{i}\cap
G|}{\Gamma_{G}}&(\text{Observation\leavevmode\nobreak\ \ref{ob:group}})\\\
\leq&\quad 4k\sum_{i\in M_{C}}d(a^{\star}_{i},C)\cdot|P_{i}\cap G|&(|P_{i}\cap
S_{G}|\leq\Gamma_{G})\\\ =&\quad 4k\|x\|_{1},&\end{aligned}$ (38)

which implies that

$\displaystyle\begin{aligned}
&\quad\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(G,C+A^{\star})}\left|\sum_{p\in
S_{G}}w(p)\cdot
x^{C}_{p}-\|x^{C}\|_{1}\mid\overline{xi_{G}}\right|\right]\cdot\Pr\left[\overline{\xi_{G}}\right]&\\\
\leq&\quad
4k\cdot\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(G,C+A^{\star})}\|x^{C}\|_{1}\right]\cdot\Pr\left[\overline{\xi_{G}}\right]&(\text{Ineq.\leavevmode\nobreak\
(\ref{ineq4:proof_main_small_x})})\\\ \leq&\quad
4k\cdot\Pr\left[\overline{\xi_{G}}\right]&\\\ \leq&\quad
4k\cdot\frac{\varepsilon}{4k}&\\\ =&\quad\varepsilon.\end{aligned}$ (39)

The lemma is a direct corollary of Inequalities (35), (37) and (39). $\square$

##  Appendix D Proof of Theorem 3.11: Analysis of Algorithm 1 for General
$z\geq 1$

We first show how to choose the number of samples $\Gamma_{G}$ for group $G$
in Theorem 3.11. For preparation, we generalize the definition of coverings.

###  D.1 Coverings for general $z\geq 1$

For a main group $G^{(m)}(j,b)\in\mathcal{G}^{(m)}$, we generalize the
definition of $H(G,C)$ to be

$H(G,C):=\left\\{p\in R_{ij}\cap G^{(m)}(j,b):i\in[k],d(a^{\star}_{i},C)\geq
8z\varepsilon^{-1}\cdot 2^{j}\Delta_{i}\right\\},$

such that we have the following observation.

###### Observation D.1

For a $k$-center set $C\in\mathcal{X}^{k}$, $i\in[k]$ and $p\in P_{i}\cap
H(G,C)$, we have $d^{z}(p,C)\in(1\pm\varepsilon)\cdot d^{z}(a^{\star}_{i},C)$.

We also generalize Definition 3.7 as follows.

######  Definition D.2 (Coverings and covering numbers of main groups for
general $z\geq 1$)

Fix constant $z\geq 1$. Let $G\in\mathcal{G}^{(m)}$ be a group. Let
$S\subseteq G$ be a subset, $\alpha>0$ and
$0\leq\beta<\log(z\varepsilon^{-1})$ be an integer. We say a set
$V\subset\mathbb{R}^{|S|}$ of _cost vectors_ is an _$\alpha$ -covering_ of $S$
if for each $C\in\mathcal{X}^{k}$, there exists a cost vector $v\in V$ such
that for any $i\in[k]$ and $p\in P_{i}\cap S\setminus H(G,C)$, the following
inequality holds:

$\displaystyle\left|d^{z}(p,C)-d^{z}(a^{\star}_{i},C)-v_{p}\right|\leq\alpha\cdot\mathsf{err}(p,C),$
(40)

where $\mathsf{err}(p,C)$ is the generalized relative covering error of $p$ to
$C$ defined as follows

$\displaystyle\mathsf{err}(p,C):=\sqrt{d^{z}(p,C)\cdot
d^{z}(p,A^{\star})}+d^{z}(p,A^{\star}))\cdot\sqrt{\frac{\mathrm{cost}_{z}(G,C+A^{\star})}{\mathrm{cost}_{z}(G,A^{\star})}}.$
(41)

Define $\mathcal{N}^{(m)}(S,\alpha)$ to be the minimum cardinality $|V|$ of an
arbitrary $\alpha$-covering $V$ of $S$. The definition of _$(\Gamma,\alpha)$
-covering number_ $\mathcal{N}^{(m)}(\Gamma,\alpha)$ of $G$ remains the same.

By the triangle inequality, we directly have for any $C\in\mathcal{X}^{k}$,
$i\in[k]$ and $p\in P_{i}\cap G\setminus H(G,C)$

$\displaystyle\begin{aligned} &\quad d^{z}(a^{\star}_{i},C)-d^{z}(p,C)\\\
\leq&\quad(d(a^{\star}_{i},C)-d(p,C))\cdot
z(d^{z-1}(p,C)+d^{z-1}(a^{\star}_{i},C))&\\\ \leq&\quad
3zd(p,A^{\star})\cdot(8z\varepsilon^{-1}\cdot 2^{j}\Delta_{i})^{z-1}&(p\notin
H(G,C))\\\ \leq&\quad(8z)^{z}\varepsilon^{-z+1}d^{z}(p,A^{\star}),\quad&(p\in
R_{ij}).\end{aligned}$ (42)

Hence, for any $\alpha\geq(8z)^{z}\varepsilon^{-z+1}$,
$\mathcal{N}^{(m)}_{G}(\Gamma,\alpha)=1$ always holds by Definition 3.7 and we
can trivially use $0^{|S_{G}|}$ as an $\alpha$-covering of $S_{G}$.
Consequently, we only need to consider the range
$0<\alpha\leq(8z)^{z}\varepsilon^{-z+1}$. For outer groups, Definition 3.9
remains the same except that we replace $d$ by $d^{z}$ for general $z\geq 1$.

###  D.2 Proof of Theorem 3.11

Fix constant $z\geq 1$. The proof is similar to that of Theorem 3.10. Again,
we only need to verify the correctness. For preparation, we provide the
following relaxed triangle inequality.

######  Lemma D.3 (Relaxed triangle inequality)

Let $a,b,c\in\mathcal{X}$ and $z\geq 1$. For every $t\in(0,1]$, the following
inequalities hold:

$d^{z}(a,b)\leq(1+t)^{z-1}d^{z}(a,c)+(1+\frac{1}{t})^{z-1}d^{z}(b,c).$

We have the following lemma that generalizes Lemma 3.12.

######  Lemma D.4 (Generalization of Lemma 3.12)

The followings hold

  1. 1.

For each $G\in\mathcal{G}^{(m)}$, we have

$\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}_{z}(G,C+A^{\star})}\cdot\left|\sum_{p\in
S_{G}}w(p)\cdot
d^{z}(p,C)-\mathrm{cost}_{z}(G,C)\right|\right]\leq\varepsilon.$

  2. 2.

For each $G\in\mathcal{G}^{(o)}$, we have

$\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}_{z}(P^{G},C+A^{\star})}\cdot\left|\sum_{p\in
S_{G}}w(p)\cdot
d^{z}(p,C)-\mathrm{cost}_{z}(G,C)\right|\right]\leq\varepsilon.$

  3. 3.

For any $C\in\mathcal{X}^{k}$, we have

$\left|\mathrm{cost}_{z}(P\setminus\mathcal{G},C)-\sum_{i\in[k]}w(a^{\star}_{i})\cdot
d^{z}(a^{\star}_{i},C)\right|\leq\varepsilon\cdot\mathrm{cost}_{z}(P,C+A^{\star}).$

By the same argument as for Theorem 3.10, we know that Theorem 3.11 is a
direct corollary of the above three lemmas. Hence, it remains to prove Lemma
D.4.

##### Proof:

[of Lemma D.4]

##### Item 1.

The proof is almost the same as Item 1 of Lemma 3.12. Fix a main group
$G\in\mathcal{G}^{(m)}$ and let $\Gamma^{\prime}_{G}=2^{O(z)}\Gamma_{G}\geq
2^{3z}\Gamma_{G}$ be the sample number of $G$. The good event $\xi_{G}$ is
generalized to be

$\displaystyle\sum_{p\in P_{i}\cap S_{G}}w(p)=\sum_{p\in P_{i}\cap
S_{G}}\frac{\mathrm{cost}_{z}(G,A^{\star})}{\Gamma^{\prime}_{G}\cdot
d^{z}(p,A^{\star})}\in(1\pm\varepsilon)\cdot|P_{i}\cap G|,$

and Lemma 3.13 still holds.

We generalize the notion of $T(G,C)$ to be

$T(G,C):=\left\\{p\in R_{ij}\cap G:i\in[k],d(a^{\star}_{i},C)\leq
z\varepsilon^{\frac{-z+1}{z}}2^{j+3}\Delta_{i}\right\\},$

i.e., the collection of rings $R_{ij}\in G$ with $d(a^{\star}_{i},C)\leq
z\varepsilon^{\frac{-z+1}{z}}2^{j+3}\Delta_{i}$. Also, we generalize
Definition 3.14.

######  Definition D.5 (Cost vectors of main groups for general $z\geq 1$)

Given a $k$-center set $C\in\mathcal{X}^{k}$, we define the following cost
vectors:

  * •

Let $u^{C}\in\mathbb{R}_{\geq 0}^{|G|}$ be a cost vector satisfying that 1)
for any $p\in H(G,C)$, $u^{C}_{p}:=d^{z}(p,C)$; 2) for any $p\in G\setminus
H(G,C)$, $u^{C}_{p}:=0$.

  * •

Let $x^{C}\in\mathbb{R}_{\geq 0}^{|G|}$ be a cost vector satisfying that 1)
for any $i\in[k]$ and $p\in P_{i}\cap G\setminus(H(G,C)\cup T(G,C))$,
$x^{C}_{p}:=d^{z}(a^{\star}_{i},C)-(8z)^{z}\varepsilon^{-z+1}2^{jz}\Delta_{i}^{z}$;
2) for any $p\in H(G,C)\cup T(G,C)$, $x^{C}_{p}:=0$.

  * •

Let $y^{C}\in\mathbb{R}_{\geq 0}^{|G|}$ be a cost vector satisfying that 1)
for any $i\in[k]$ and $p\in P_{i}\cap G\setminus(H(G,C)\cup T(G,C))$,
$y^{C}_{p}:=d^{z}(p,C)-d^{z}(a^{\star}_{i},C)+(8z)^{z}\varepsilon^{-z+1}2^{jz}\Delta_{i}^{z}$;
2) for any $p\in T(G,C)$, $y^{C}_{p}:=d^{z}(p,C)$; 3) for any $p\in H(G,C)$,
$y^{C}_{p}:=0$.

Note that $y^{C}\in\mathbb{R}_{\geq 0}^{|G|}$ holds since we have Inequality
(42). Then Lemmas 3.15 and 3.16 still hold by generalizing all
$\mathrm{cost}(\cdot,\cdot)$ to $\mathrm{cost}_{z}(\cdot,\cdot)$. The
arguments are the same – still relying on Lemma 3.13.

The main difference is the following generalization of Lemma 3.17.

######  Lemma D.6 (Estimation error of $y^{C}$ for general $z\geq 1$)

The following inequality holds:

$\mathbb{E}_{S_{G}}\sup_{C\in\mathcal{X}^{k}}\left[\frac{1}{\mathrm{cost}(G,C+A^{\star})}\left|\sum_{p\in
S_{G}}w(p)\cdot y^{C}_{p}-\|y^{C}\|_{1}\right|\right]\leq\varepsilon.$

Similarly, Item 1 of Lemma D.4 is a direct corollary. Thus, it suffices to
prove Lemma D.6. We first generalize Definition 3.18.

######  Definition D.7 ($\alpha$-Layered-Coverings of main groups for general
$z\geq 1$)

Let $G\in\mathcal{G}^{(m)}(j)$ be a main group. Let $S\subseteq G$ be a subset
and $\alpha>0$. We say a set $V\subset\mathbb{R}^{|S|}$ of _cost vectors_ is
an _$\alpha$ -layered covering_ of $S$ if for each $C\in\mathcal{X}^{k}$,
there exists a cost vector $v\in V$ such that

  * •

for any $p\in T(G,C)\cap S\setminus H(G,C)$, the following holds:

$\left|d^{z}(p,C)-v_{p}\right|\leq\alpha\cdot\mathsf{err}(p,C);$

  * •

for any $i\in[k]$ and $p\in P_{i}\cap S\setminus(H(G,C)\cup T(G,C))$, the
following holds:

$\left|d^{z}(p,C)-d^{z}(a^{\star}_{i},C)+(8z)^{z}\varepsilon^{-z+1}2^{jz}\Delta_{i}^{z}-v_{p}\right|\leq\alpha\cdot\mathsf{err}(p,C);$

where $\mathsf{err}(p,C)$ is the relative covering error defined in Definition
D.2.

The same to Definition 3.19, we can define the generalized covering numbers
$\widehat{\mathcal{N}}^{(m)}(S,\alpha)$ and
$\widehat{\mathcal{N}}^{(m)}_{G}(\Gamma,\alpha)$ according to the above
definition.

Also, note that for any $i\in[k]$ and $p\in P_{i}\cap T(G,C)\cap S\setminus
H(G,C)$, we have

$d^{z}(p,C)\leq(d(p,a^{\star}_{i})+d(a^{\star}_{i},C))^{z}\leq(16z)^{z}\varepsilon^{-z+1}d^{z}(p,A^{\star}).$

Since $\mathsf{err}(p,C)\geq\sqrt{d^{z}(p,C)\cdot d^{z}(p,A^{\star})}$, we
again only need to focus on the range
$0\leq\alpha\leq(8z)^{z}\varepsilon^{-z+1}$ for layered coverings. We again
have the following relations between two covering numbers that generalized
Lemma 3.20.

######  Lemma D.8 (Relations between two covering numbers for general $z\geq
1$)

Let $G\in\mathcal{G}^{(m)}(j)$ be a main group. Let $S\subseteq G$ be a subset
and $\alpha>0$. We have

$\log\widehat{\mathcal{N}}^{(m)}(S,\alpha)=O\left(\log\mathcal{N}^{(m)}(S,\alpha)+zk\log(\alpha^{-1}\varepsilon^{-1})\right).$

Moreover, for any integer $\Gamma\geq 1$, the following holds:

$\log\widehat{\mathcal{N}}^{(m)}(\Gamma,\alpha)=O\left(\log\mathcal{N}^{(m)}(\Gamma,\alpha)+zk\log(\alpha^{-1}\varepsilon^{-1})\right).$

The proof of the above lemma is almost identical to that of Lemma 3.20 except
that we discretize the range of $d^{z}(a^{\star}_{i},C)$ to be $0,\alpha
2^{jz}\Delta_{i}^{z},2\alpha
2^{jz}\Delta_{i}^{z},\ldots,(16z)^{z}\varepsilon^{-z+1}2^{jz}\Delta_{i}^{z}$,
which contains at most $z^{O(z)}\varepsilon^{-z+1}\alpha^{-1}$ distinct values
and results in the term $zk\log(\alpha^{-1}\varepsilon^{-1})$. By the above
lemma, we also know that

$\Gamma_{G}\geq
O\left(\varepsilon^{-2}\left(\int_{0}^{+\infty}\sqrt{\log\widehat{\mathcal{N}}^{(m)}_{G}(\Gamma_{G},\alpha)}d\alpha\right)^{2}+k\varepsilon^{-2}\log(k\varepsilon^{-1})\right),$

which is useful for the reduction to a Gaussian process.

Now we are ready to prove Lemma D.6. We still reduce to a Gaussian process and
consider the following generalized estimators:

$X_{C,h}:=\frac{1}{\mathrm{cost}_{z}(G,C+A^{\star})}\sum_{p\in S_{G}\setminus
H(S_{G},C)}\xi_{p}\cdot w(p)\cdot(v^{C,h+1}_{p}-v^{C,h}_{p}),$

The key difference is the variance of $X_{C,h}$; summarized by the following
generalization of Lemma 3.22.

######  Lemma D.9 (Variance of $X_{C,h}$ for general $z\geq 1$)

Fix a $k$-center set $C\in\mathcal{X}^{k}$. The variance of $X_{C,h}$ is
always at most

$\sum_{p\in S_{G}\setminus
H(S_{G},C)}\left(\frac{w(p)\cdot(v^{C,h+1}_{p}-v^{C,h}_{p})}{\mathrm{cost}_{z}(G,C+A^{\star})}\right)^{2}\leq\frac{2^{-2h+4}k}{\Gamma_{G}}.$

Moreover, conditioned on event $\xi_{G}$, the variance of $X_{C,h}$ is always
at most

$\sum_{p\in S_{G}\setminus
H(S_{G},C)}\left(\frac{w(p)\cdot(v^{C,h+1}_{p}-v^{C,h}_{p})}{\mathrm{cost}_{z}(G,C+A^{\star})}\right)^{2}\leq\frac{2^{-2h+5}}{\Gamma_{G}}.$

Since the variance of $X_{C,h}$ has an additional factor $2^{O(z)}$, we can
upper bound

$\sum_{h\geq
0}\mathbb{E}_{\xi}\sup_{C\in\mathcal{X}^{k}}|X_{C,h}|\leq\frac{\varepsilon}{6},$

which completes the proof of Lemma D.6.

It remains to prove Lemma D.9. We still let $M_{C}\subseteq[k]$ denote the
collection of $i\in[k]$ with $P_{i}\cap S_{G}\setminus
H(S_{G},C)\neq\emptyset$. For any $i\in[k]$ and point $p\in P_{i}\cap G$, let
$q=\arg\min_{p^{\prime}\in P_{i}\cap G}d(p^{\prime},C)$. Firstly, Inequality
(15) generalizes to be

$\displaystyle d^{z}(p,C)$
$\displaystyle\leq(d(q,C)+d(p,A^{\star})+d(q,A^{\star}))^{z}$
$\displaystyle(\text{triangle ineq.})$
$\displaystyle\leq(d(q,C)+3d(p,A^{\star}))^{z}$ $\displaystyle(\text{Defn. of
$R_{ij}$})$ $\displaystyle\leq 2^{z}d(q,C)+6^{z}d^{z}(p,A^{\star})$
$\displaystyle(\text{Lemma\leavevmode\nobreak\ \ref{lm:relaxed}})$
$\displaystyle\leq\frac{2^{z}\mathrm{cost}_{z}(P_{i}\cap G,C)}{|P_{i}\cap
G|}+6^{z}d^{z}(p,A^{\star})$ $\displaystyle(\text{Defn. of $q$}).$

Then conditioned on $\xi_{G}$, we have

$\displaystyle\sum_{p\in S_{G}\setminus
H(S_{G},C)}\left(\frac{w(p)\cdot(v^{C,h+1}_{p}-v^{C,h}_{p})}{\mathrm{cost}_{z}(G,C+A^{\star})}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\frac{2^{-2h+2}}{\Gamma^{\prime}_{G}}\cdot\sum_{i\in
M_{C}}\sum_{p\in P_{i}\cap
S_{G}}\frac{w(p)}{\mathrm{cost}_{z}(G,C+A^{\star})}\cdot(\frac{2^{z}\mathrm{cost}_{z}(P_{i}\cap
G,C)}{|P_{i}\cap G|}+6^{z}d^{z}(p,A^{\star}))$ $\displaystyle\leq$
$\displaystyle\frac{2^{-2h+5}}{\Gamma_{G}}.$

In general, we also have

$\displaystyle\sum_{p\in S_{G}\setminus
H(S_{G},C)}\left(\frac{w(p)\cdot(v^{C,h+1}_{p}-v^{C,h}_{p})}{\mathrm{cost}_{z}(G,C+A^{\star})}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\frac{2^{-2h+2}}{\Gamma^{\prime}_{G}}\cdot\sum_{i\in
M_{C}}\sum_{p\in P_{i}\cap
S_{G}}\frac{w(p)}{\mathrm{cost}_{z}(G,C+A^{\star})}\cdot(\frac{2^{z}\mathrm{cost}_{z}(P_{i}\cap
G,C)}{|P_{i}\cap G|}+6^{z}d^{z}(p,A^{\star}))$ $\displaystyle\leq$
$\displaystyle\frac{2^{-2h+5}k}{\Gamma_{G}}.$

Thus, we complete the proof of Lemma D.9, which completes the proof of Item 1.

##### Item 2.

Again, the proof idea is almost the same as that of [14, Lemma 13]. The same
as Item 2 of Lemma 3.12, we can consider the coverings on $S_{G}$ instead of
$G$. Recall that [14, Lemma 18] selects the sample size
$\delta=z^{O(z)}\Gamma_{G}$ containing factor $z^{O(z)}$ instead of
$2^{O(z)}$. However, by the proof of [14, Lemma 18], we can see that the
variance of $X_{C,h}$ is actually upper bounded by
$\frac{16^{z}2^{-2h+5}k}{\delta}$. Hence, the sample size $\delta$ in [14,
Lemma 18] can be modified to be $2^{O(z)}\Gamma_{G}$, which matches Item 2 of
Lemma D.4.

##### Item 3.

Item 3 has been proved in [18, 14]; see e.g., [18, Lemma 4]. $\square$

##  Appendix E Proof of Theorem 4.1 for general $z\geq 1$: Euclidean coresets

The key is to prove the following lemma that generalizes Lemma 4.2. Theorem
4.1 is a direct corollary of the following lemma and the fact that we only
need to consider the range $0<\alpha\leq(8z)^{z}\varepsilon^{-z+1}$.

######  Lemma E.1 (Covering number in Euclidean metrics for general $z\geq 1$)

For each $G\in\mathcal{G}^{(m)}$, $0<\alpha\leq 1$, and integer
$0\leq\beta<\log(z\varepsilon^{-1})$,

$\log\mathcal{N}^{(m)}_{G}(\Gamma_{G},\alpha)=2^{O(z)}k\cdot\min\left\\{k^{\frac{z}{z+2}}\alpha^{-2}\log\|P\|_{0}\log\varepsilon^{-1},d\right\\}\cdot\log(\varepsilon^{-1}\alpha^{-1}).$

For each $G\in\mathcal{G}^{(o)}$ and any $0<\alpha\leq 1$,

$\log\mathcal{N}^{(o)}_{G}(\Gamma_{G},\alpha)=O(z^{2}k\cdot\min\left\\{\alpha^{-2}\log\|P\|_{0},d\right\\}\cdot\log\alpha^{-1}).$

##### Proof:

By [14, Lemma 21], we can obtain the upper bound for
$\mathcal{N}^{(o)}_{G}(\Gamma_{G},\alpha)$.

Fix $\alpha\in(0,1)$, $z\geq 1$ and let $G\in\mathcal{G}^{(m)}(j)$ be a main
group. We generalize Definition 4.9, the partition of $G$, by setting the
range of $\beta$ to be $0\leq\beta<2+\log(z\varepsilon^{-1})$. Fix a subset
$S\subseteq G$ of size $\Gamma_{G}$.

##### Generalization of Lemma 4.8.

We first show how to generalize Lemma 4.8.

######  Lemma E.2 (Covering construction for general $z\geq 1$ in Euclidean
spaces)

Suppose $d\geq\log k$ and constant $z\geq 1$. Let $X\subset\mathbb{R}^{d}$ be
a dataset that consists of $X_{1}\subset B(a^{\star}_{1},r_{1}),X_{1}\subset
B(a^{\star}_{2},r_{2}),\ldots,X_{t}\subset B(a_{t},r_{t})$ for some $1\leq
t\leq k$, $a^{\star}_{1},\ldots,a^{\star}_{t}\in\mathbb{R}^{d}$ and
$r_{1},\ldots,r_{t}>0$. Let $\alpha\in(0,1)$ and $u\geq 1$. There exists an
$\alpha$-covering $V\subset\mathbb{R}^{|X|}$ of $X$ with
$\log|V|=O(zkd\log(u\alpha^{-1}))$, i.e., for any $k$-center set
$C\in\mathcal{X}^{k}$, there exists a cost vector $v\in V$ $i\in[t]$ with
$d(a^{\star}_{i},C)\leq u\cdot r_{i}$ and $p\in X_{i}$ such that

$|d^{z}(p,C)-d^{z}(a^{\star}_{i},C)-v_{p}|\leq\alpha\cdot r_{i}^{z}.$

##### Proof:

For each $i\in[t]$, take an $\frac{\alpha}{10(u+2)^{z}}\cdot r_{i}$-net of the
Euclidean ball $B(a^{\star}_{i},10zur_{i})$. Since $d\geq\log k$ and $z=O(1)$,
the union $\Lambda$ of these nets has size at most

$k\cdot\exp\left(O(zd\log(u\alpha^{-1}))\right)=\exp\left(O(zd\cdot\log(zu\alpha^{-1}))\right).$

For any $S\subseteq G$, we then define an $\alpha$-covering
$V\subset\mathbb{R}^{|S|}$ of $S$ as follows: for any $k$-center set
$C\subseteq\Lambda$, we construct a vector $v\in V$ in which the entry
corresponding to point $p$ (say $p\in R_{ij}\cap S$) is

$v_{p}=d^{z}(p,C)-d^{z}(a^{\star}_{i},C).$

Obviously, we have $\log|V|=O(zkd\cdot\log(u\alpha^{-1}))$. It remains to
verify that $V$ is indeed an $\alpha$-covering of $S$. For any
$C=(c_{1},\ldots,c_{k})\in\mathcal{X}^{k}$, let
$C^{\prime}=(c^{\prime}_{1},\ldots,c^{\prime}_{k})\in V$ such that
$c^{\prime}_{i}$ is the closest point of $c_{i}$ in $\Lambda$ ($i\in[k]$).
Then for any $i\in[t]$ with $d(a^{\star}_{i},C)\leq u\cdot r_{i}$ and $p\in
X_{i}$, we have the following observation: for every $c_{i}\in C$,

  1. 1.

If $d(p,c_{i})\geq 4u\cdot r_{i}^{z}$, then $d(p,c^{\prime}_{i})\geq 2u\cdot
r_{i}\geq d(p,C)$ since $d(p,C)\leq d(a^{\star}_{i},C)+d(p,a^{\star}_{i})$.

  2. 2.

If $d(p,c)\leq 4u\cdot r_{i}$, then $d(p,c^{\prime})\in
d(p,c)\pm\frac{\alpha}{10(u+2)^{z}}\cdot r_{i}$ by the construction of
$\Lambda$.

Consequently, we have

$\displaystyle d(p,C^{\prime})\in d(p,C)\pm\frac{\alpha}{10(u+2)^{z}}\cdot
r_{i},$ (43)

which implies that

$\displaystyle|d^{z}(p,C^{\prime})-d^{z}(p,C)|$ $\displaystyle\leq$
$\displaystyle|d(p,C^{\prime})-d(p,C)|\cdot
z(d^{z-1}(p,C^{\prime})+d^{z-1}(p,C))$ $\displaystyle\leq$
$\displaystyle\frac{\alpha}{10(u+2)^{z}}\cdot
r_{i}\cdot\left((d(a^{\star}_{i},C^{\prime})+r_{i})^{z-1}+(d(a^{\star}_{i},C)+r_{i})^{z-1}\right)$
$\displaystyle(\text{triangle ineq. and Ineq.\leavevmode\nobreak\
(\ref{ineq1:proof_Euclidean_general})})$ $\displaystyle\leq$
$\displaystyle\frac{\alpha}{10(u+2)^{z}}\cdot r_{i}\cdot
2(u+2)^{z-1}r_{i}^{z-1}$ $\displaystyle(d(a^{\star}_{i},C)\leq u\cdot r_{i})$
$\displaystyle\leq$ $\displaystyle\frac{\alpha}{2}\cdot r_{i}^{z}.$

The above two inequalities directly lead to the following conclusion:

$|d^{z}(p,C)-d^{z}(a^{\star}_{i},C)-v_{p}|=|d^{z}(p,C)-d^{z}(a^{\star}_{i},C)-(d^{z}(p,C^{\prime})-d^{z}(a^{\star}_{i},C^{\prime}))|\leq\alpha\cdot
r_{i}^{z},$

which completes the proof. $\square$

##### Generalization of Inequality (25).

We first verify the following inequality that generalizes Inequality (25).

$\displaystyle\log\mathcal{N}^{(m)}_{G}(\Gamma_{G},\alpha)=O(zkd\log(\varepsilon^{-1}\alpha^{-1})).$
(44)

This is actually a direct corollary of Lemma 4.8 by letting $X=S$,
$X_{i}=S\cap R_{ij}$, $r_{i}=2^{j+1}\Delta_{i}$ for $i\in[k]$, and
$u=10z\varepsilon^{-1}$.

##### Generalization of Inequality (26).

Next, we verify the following inequality that generalizes Inequality (26):

$\displaystyle\log\mathcal{N}^{(m)}_{G}(\Gamma_{G},\alpha)\leq
2^{O(z)}k^{\frac{2z+2}{z+2}}\alpha^{-2}\log\|P\|_{0}\log\varepsilon^{-1}\log(\varepsilon^{-1}\alpha^{-1})).$
(45)

We again partition $G\setminus H(G,C)$ as Definition 4.9. The only difference
is that the range of $\beta$ changes to be $0\leq\beta\leq
2+\log(z\varepsilon^{-1})$. The same as the proof in Section 4.3, we denote
$\phi^{(C)}\in\left\\{0,1,\ldots,2+\lfloor\log(z\varepsilon^{-1})\rfloor,+\infty\right\\}^{k}$
for each $C\in\mathcal{X}^{k}$. There are at most
$(3+\log(z\varepsilon^{-1}))^{k}$ distinct $\phi^{(C)}$s. For each
$\phi\in\left\\{0,1,\ldots,2+\lfloor\log(z\varepsilon^{-1})\rfloor,+\infty\right\\}^{k}$,
we again denote $S_{\phi,\beta}$ for each integer $0\leq\beta\leq
2+\log(z\varepsilon^{-1})$. We have the following lemma that generalizes Lemma
4.11.

######  Lemma E.3 (An upper bound of the covering number for each $\beta$ for
general $z\geq 1$)

Let $G\in\mathcal{G}^{(m)}(j)$ for some integer
$\log\varepsilon<j<2\log\varepsilon^{-1}$ be a main group and let $S\subseteq
G$ be a subset. Fix a vector
$\phi\in\left\\{0,1,\ldots,2+\lfloor\log(z\varepsilon^{-1})\rfloor,+\infty\right\\}^{k}$
and an integer $0\leq\beta\leq 2+\log(z\varepsilon^{-1})$. There exists an
$\alpha$-covering $V_{\phi,\beta}\subset\mathbb{R}^{|S_{\phi,\beta}|}$ of
$S_{\phi,\beta}$ satisfying that for each $C\in\mathcal{X}^{k}$ with
$\phi^{(C)}=\phi$, there exists a cost vector $v\in V_{\phi,\beta}$ such that
for any $i\in[k]$ and $p\in R_{ij}\cap S_{\phi,\beta}$, Inequality (40) holds,
i.e.,

$\left|d^{z}(p,C)-d^{z}(a^{\star}_{i},C)-v_{p}\right|\leq\alpha\cdot(\sqrt{d^{z}(p,C)\cdot
d^{z}(p,A^{\star})}+d^{z}(p,A^{\star}))\cdot\sqrt{\frac{\mathrm{cost}_{z}(G,C+A^{\star})}{\mathrm{cost}_{z}(G,A^{\star})}}.$

Moreover, the size of $V_{\phi,\beta}$ satisfies

$\log|V_{\phi,\beta}|\leq 2^{O(z)}k\cdot\min\left\\{2^{\beta
z}\alpha^{-2}\log(k\varepsilon^{-1}),(1+k2^{-2\beta})\alpha^{-2}\log(k\varepsilon^{-1})\right\\}\cdot\log(\varepsilon^{-1}\alpha^{-1}).$

By a similar argument as that in Section 4.3, we can prove that Lemma E.1 is a
corollary of the above lemma. The only difference is that we should upper
bound the term $\min\left\\{2^{\beta z},1+k2^{-2\beta}\right\\}$ instead of
$\min\left\\{2^{\beta},1+k2^{-2\beta}\right\\}$. Letting
$2^{\beta}=k^{\frac{1}{(z+2)}}$, we have

$\min\left\\{2^{\beta z},1+k2^{-2\beta}\right\\}\leq k^{\frac{z}{(z+2)}},$

which implies Lemma E.1. Then it remains to prove Lemma E.3.

##### Proof:

[of Lemma E.3]

##### Case $\beta=0$ for general $z\geq 1$.

Let $f$ be an $2^{-5z}\alpha$-terminal embedding of $A^{\star}\cup S$ into
$m=2^{10z}\alpha^{-2}\log\|P\|_{0}$ dimensions given by Theorem 4.4. Given a
$k$-center set $C\in\mathcal{X}^{k}$ with $\phi^{(C)}=\phi$, we have that for
any $p\in A\cup S_{\phi,0}$,

$\displaystyle\begin{aligned} d^{z}(f(p),f(C))&=\min_{q\in
C}d^{z}(f(p),f(q))&\\\ &\in(1\pm\alpha 2^{-5z})^{z}\cdot\min_{q\in
C}d^{z}(p,q)&(\text{Theorem\leavevmode\nobreak\ \ref{thm:embedding}})\\\
&\in(1\pm\alpha 2^{-3z})\cdot d^{z}(p,C)&\\\ &\in d^{z}(p,C)\pm\alpha\cdot
d^{z}(p,A^{\star}).&(\text{Observation\leavevmode\nobreak\
\ref{ob:main_gap}})\end{aligned}$ (46)

The remaining argument is the same as in Lemma 4.2, say applying Lemma 4.8
with $d=m$, $X=S_{\phi,0}$, $X_{i}=R_{ij}\cap S_{\phi,0}$,
$r_{i}=2^{j+4}\Delta_{i}$ for $i\in[k]$, and $u=O(1)$ to construct an
$\alpha$-covering of $f(S)$. Note that the target dimension is
$m=2^{O(z)}\alpha^{-2}\log\|P\|_{0}$, which completes the proof.

##### Case $\beta\geq 1$ for general $z\geq 1$.

We first construct an $\alpha$-covering $V_{\phi,\beta}$ of $S_{\phi,\beta}$
with

$\displaystyle\log|V_{\phi,\beta}|=2^{O(z)}k2^{\beta
z}\alpha^{-2}\log\|P\|_{0}\cdot\log(\varepsilon^{-1}\alpha^{-1}).$ (47)

Let $f$ be an $2^{-5z-\beta z/2}\alpha$-terminal embedding of $A^{\star}\cup
S_{\phi,\beta}$ into $m=2^{10z+\beta z}\alpha^{-2}\log\|P\|_{0}$ dimensions
given by Theorem 4.4. Given a $k$-center set $C\in\mathcal{X}^{k}$ with
$\phi^{(C)}=\phi$, we have that for any $i\in[k]$ and $p\in R_{ij}\cap
S_{\phi,\beta}$,

$\displaystyle d^{z}(f(p),f(C))$ $\displaystyle=\min_{q\in C}d^{z}(f(p),f(q))$
$\displaystyle\in(1\pm\alpha 2^{-5z-\beta z/2})^{z}\cdot\min_{q\in
C}d^{z}(p,q)$ $\displaystyle(\text{Theorem\leavevmode\nobreak\
\ref{thm:embedding}})$ $\displaystyle\in(1\pm\alpha 2^{-3z-\beta z/2})\cdot
d^{z}(p,C)$ $\displaystyle\in d^{z}(p,C)\pm
O(\alpha)\cdot\sqrt{d^{z}(p,C)\cdot d^{z}(p,A^{\star})},$
$\displaystyle(\text{Observation\leavevmode\nobreak\ \ref{ob:main_gap}})$

and

$d^{z}(f(a^{\star}_{i}),f(C))\in d^{z}(a^{\star}_{i},C)\pm
O(\alpha)\cdot\sqrt{d^{z}(p,C)\cdot d^{z}(p,A^{\star})}.$

The remaining argument is the same as in Lemma 4.11 by applying Lemma 4.8 with
$d=m$, $X=S_{\phi,0}$, $X_{i}=R_{ij}\cap S_{\phi,0}$,
$r_{i}=2^{j+4}\Delta_{i}$ for $i\in[k]$, and $u=2^{\beta+10}$ to construct an
$\alpha$-covering of $f(S)$. Since the target dimension is $m=2^{O(z)-\beta
z}\alpha^{-2}\log\|P\|_{0}$, we complete the proof of Inequality (47).

Finally, we construct an $\alpha$-covering $V_{\phi,\beta}$ of
$S_{\phi,\beta}$ with

$\displaystyle\log|V_{\phi,\beta}|=2^{O(z)}(k^{2}2^{-2\beta}\alpha^{-2}\log\|P\|_{0}\cdot\log(\varepsilon^{-1}\alpha^{-1})).$
(48)

We again let $B\subseteq[k]$ be the collection of $i\in[k]$ with $R_{ij}\cap
S\subseteq S_{\phi,\beta}$. Similar to Inequality (32), we note that for any
$C\in\mathcal{X}^{k}$ with $\phi^{(C)}=\phi$,

$\displaystyle\frac{\mathrm{cost}_{z}(G,C)}{\mathrm{cost}_{z}(G,A^{\star})}\geq\frac{|B|2^{(\beta
z-1)}}{k}.$ (49)

For each $i\in B$, let $g_{i}$ be an
$\sqrt{|B|k^{-1}}2^{\beta-5z}\alpha$-additive terminal embedding of
$T_{i}=\left\\{p-a^{\star}_{i}:p\in R_{ij}\cap S\right\\}$ into
$m=O(|B|^{-1}k2^{10z-2\beta}\alpha^{-2}\log\|P\|_{0})$ dimensions given by
Theorem 4.6.

Let $r=2^{j+1}\Delta_{i}$. We again define a function $f_{i}$ as follows:
$f_{i}(p)=g_{i}(p-a^{\star}_{i})$ for any $p\in\mathbb{R}^{d}$. Recall that
$G\in\mathcal{G}^{(m)}(j)$, and hence, $R_{ij}\cap S\in B(a^{\star}_{i},r)$.
Then by Theorem 4.6, we have that for any $p\in R_{ij}\cap S$ or
$p=a^{\star}_{i}$ and $q\in\mathbb{R}^{d}$,
$|d(p,q)-d(f_{i}(p),f_{i}(q))|\leq\sqrt{|B|k^{-1}}2^{\beta-5z}\alpha r$. Given
a $k$-center set $C\in\mathcal{X}^{k}$ with $\phi^{(C)}=\phi$, we have that
for any $p\in R_{ij}\cap S$, $d(a^{\star}_{i},C)\geq
2^{\beta+j+2}\Delta_{i}\geq 4r$. Consequently, we know that
$C\subset\mathbb{R}^{d}\setminus B(a^{\star}_{i},2r)$. For any $p\in
R_{ij}\cap S_{\phi,\beta}$ and $c_{p}=\arg\min_{c\in
C}d(p,C)\in\mathbb{R}^{d}$, we have

$\displaystyle d^{z}(f_{i}(p),f_{i}(c_{p}))$ $\displaystyle\in$
$\displaystyle(d(p,c)\pm\sqrt{|B|k^{-1}}2^{\beta-5z}\alpha r)^{z}$
$\displaystyle\in$ $\displaystyle(1\pm
2^{1-5z}\sqrt{|B|k^{-1}}\alpha)^{z}d^{z}(p,c_{p})$ $\displaystyle(p\in
H(G,C)\cap S)$ $\displaystyle\in$ $\displaystyle(1\pm
2^{-4z}\sqrt{|B|k^{-1}}\alpha)d^{z}(p,c_{p})$ $\displaystyle\in$
$\displaystyle d^{z}(p,c_{p})\pm\alpha\cdot\sqrt{d^{z}(p,c_{p})\cdot
d^{z}(p,A^{\star})}\cdot\sqrt{\frac{\mathrm{cost}_{z}(G,C)}{\mathrm{cost}_{z}(G,A^{\star})}}$
$\displaystyle(\text{Observation\leavevmode\nobreak\ \ref{ob:main_gap} and
Ineq.\leavevmode\nobreak\
(\ref{ineq6:proof_Euclidean_covering_number_general})})$ $\displaystyle\in$
$\displaystyle d^{z}(p,C)\pm\alpha\cdot\sqrt{d^{z}(p,C)\cdot
d^{z}(p,A^{\star})}\cdot\sqrt{\frac{\mathrm{cost}_{z}(G,C)}{\mathrm{cost}_{z}(G,A^{\star})}}$
$\displaystyle(\text{Defn. of $c_{p}$})$

Moreover, we have for any $p\in R_{ij}\cap S_{\phi,\beta}$ and
$c_{p}=\arg\min_{c\in C}d(p,C)\in\mathbb{R}^{d}$,

$|d^{z}(f_{i}(a^{\star}_{i}),f_{i}(C))-d^{z}(a^{\star}_{i},C)|\leq
O(\alpha)\cdot\sqrt{d^{z}(p,C)\cdot
d^{z}(p,A^{\star})}\cdot\sqrt{\frac{\mathrm{cost}_{z}(G,C)}{\mathrm{cost}_{z}(G,A^{\star})}}.$

Combining the above two inequalities, we directly have

$\displaystyle\left|(d^{z}(f_{i}(p),f_{i}(C))-d^{z}(f_{i}(a^{\star}_{i}),f_{i}(C)))-(d^{z}(p,C)-d^{z}(a^{\star}_{i},C))\right|$
(50) $\displaystyle\leq$ $\displaystyle O(\alpha)\cdot\sqrt{d^{z}(p,C)\cdot
d^{z}(p,A^{\star})}\cdot\sqrt{\frac{\mathrm{cost}_{z}(G,C)}{\mathrm{cost}_{z}(G,A^{\star})}}.$
(51)

The remaining argument is the same as in Lemma 4.11. Since the target
dimension is $m=2^{O(z)}|B|^{-1}k2^{-2\beta}\alpha^{-2}\log\|P\|_{0}$, we
complete the proof of Inequality (48). $\square$

Overall, we complete the proof of Lemma E.1.

$\square$

By the same argument as for $z=1$, Theorem 4.1 is a direct corollary of Lemma
E.1.


# Sine-Gordon on a wormhole

Piotr Bizoń  Institute of Theoretical Physics, Jagiellonian University, Kraków
<EMAIL_ADDRESS>,  Maciej Dunajski  DAMTP, University of Cambridge,
Cambridge<EMAIL_ADDRESS>,  Michał Kahl  Institute of Theoretical
Physics, Jagiellonian University, Kraków<EMAIL_ADDRESS>and
Michał Kowalczyk  Departamento de Ingeniería Matemática and Centro de
Modelamiento Matemático
Universidad de Chile
Santiago, Chile<EMAIL_ADDRESS>
###### Abstract.

In an attempt to understand the soliton resolution conjecture, we consider the
Sine-Gordon equation on a spherically symmetric wormhole spacetime. We show
that within each topological sector (indexed by a positive integer degree $n$)
there exists a unique linearly stable soliton, which we call the $n$-kink. We
give numerical evidence that the $n$-kink is a global attractor in the
evolution of any smooth, finite energy solutions of degree $n$. When the
radius of the wormhole throat $a$ is large enough, the convergence to the
$n$-kink is shown to be governed by internal modes that slowly decay due to
the resonant transfer of energy to radiation. We compute the exact asymptotics
of this relaxation process for the $1$-kink using the Soffer-Weinstein weakly
nonlinear perturbation theory.

##  1\. Introduction

If a solution of an evolution equation exists for all times $t$, then it is
natural to ask how it behaves as $t\rightarrow\infty$. This question is
particularly interesting if the equation admits solitons (spatially localized,
finite energy solutions) because they may appear as late-time attractors. For
nonlinear dispersive wave equations it is believed that for any reasonable
(e.g. smooth and finite energy) generic initial data, the solution eventually
resolves into a superposition of a radiative component plus a finite number of
solitons. This belief, known as the soliton resolution conjecture [1], is
fairly well understood for small perturbations of solitons [2, 3], however
little is known in the non-perturbative regime (but the one-dimensional
completely integrable equations where solutions can be computed explicitly via
inverse scattering methods [4, 5] and few results in higher dimensions, e.g.
[6, 7]).

In an attempt to understand the soliton resolution conjecture in a simple
setting, two of us proposed in [8] to study nonlinear waves propagating on a
spherically symmetric curved spacetime with the metric

$ds^{2}=-dt^{2}+dr^{2}+(r^{2}+a^{2})d\omega^{2}\,,$ (1)

where $(t,r)\in\mathbb{R}^{2}$, $d\omega^{2}$ is the round metric on the unit
two-sphere, and $a$ is a positive constant. This spacetime, introduced by
Ellis [9] and Bronnikov [10], is the simplest example of a wormhole geometry
that has two asymptotically flat ends at $r\rightarrow\pm\infty$ connected by
a spherical throat (minimal surface) of area $4\pi a^{2}$ at $r=0$.

Figure 1. Left panel: the isometric embedding of the constant time equatorial
cross–section of the wormhole in $\mathbb{R}^{3}$. Right panel: the conformal
diagram of the wormhole spacetime. The boundaries of each side of the diamond,
denoted by $\mathcal{J}^{\pm}_{L,R}$, represent future/past
($t\rightarrow\pm\infty$) and left/right ($r\rightarrow\mp\infty$) null
infinities.

Although the wormhole belongs more to science-fiction than physics [11], it
has a number of features that makes it an attractive testing ground for the
soliton resolution conjecture. First, there is no singularity at $r=0$ which
basically ensures global well-posedness for dispersive equations with coercive
nonlinearities. Second, due to the presence of the length scale $a$, Derrick’s
non-existence scaling arguments are evaded and solitons do exist (often in
abundance) for some nonlinearities. Third, if a soliton exists, it is
completely rigid so no modulation analysis is needed. Finally, the equations
posed on the wormhole combine the simplicity of one-dimensional equations on
the whole real line with the three-dimensional dispersive properties.

In [8] the soliton resolution conjecture was formulated and verified
numerically for equivariant wave maps from the wormhole (1) into the 3-sphere.
In addition, the rate of convergence to the soliton (which in this case is a
harmonic map from a $t=\text{const}$ hypersurface of the wormhole into the
3-sphere) was computed by perturbation methods. Subsequently, the conjecture
made in [8] was proved (without a decay rate, though) by Rodriguez [12, 13]
via the concentration-compactness method as in [7]. The key ingredient in
getting these results was the fact that the linearized perturbations around
the solitons decay in time. In this paper, we consider a different
nonlinearity for which the latter property does not hold and the asymptotic
stability of solitons is an inherently nonlinear phenomenon.

On the wormhole spacetime we consider a real scalar field $\phi$ obeying the
semilinear wave equation111For dimensional reasons the nonlinear term must
have the form $\ell^{-2}\sin(2\phi)$, where $\ell$ is a fixed scale of length.
Hereafter, we set $\ell=1$ by the choice of the unit of length.

$\Box_{g}\phi+\sin(2\phi)=0,$ (2)

where $\Box_{g}$ is the wave operator associated with the metric (1). Assuming
that $\phi=\phi(t,r)$, we get

$\ddot{\phi}=\phi^{\prime\prime}+\frac{2r}{r^{2}+a^{2}}\,\phi^{\prime}-\sin(2\phi),$
(3)

where an overdot and prime denote derivatives with respect to $t$ and $r$. For
$a=\infty$ this equation reduces to the one-dimensional Sine-Gordon equation

$\ddot{\phi}=\phi^{\prime\prime}-\sin(2\phi),$ (4)

which is completely integrable, hence for large values of $a$ equation (3) can
be viewed as a non-integrable perturbation of (4)222The $\phi^{4}$ model on
the wormhole was considered in [14] following an earlier unpublished version
of our paper. The key difference which makes the $\phi^{4}$ model less
interesting than Sine-Gordon is that the former is non-integrable already in
flat space. Equation (3) is indeed not integrable for any finite $a$ as it
does not possess the Painlevé property..

The conserved energy associated with equation (3) reads

$E=\int\limits_{-\infty}^{\infty}\left(\frac{1}{2}\dot{\phi}^{2}+\frac{1}{2}\phi^{\prime
2}+\sin^{2}{\\!\phi}\right)(r^{2}+a^{2})\,dr\,.$ (5)

Finiteness of energy requires that $\phi(t,-\infty)=n_{-}\pi$,
$\phi(t,\infty)=n_{+}\pi$, where $n_{-}$ and $n_{+}$ are integers. Without
loss of generality we choose $n_{-}=0$; then $n=n_{+}$ determines the
topological degree of the solution (which is preserved in the evolution).

The goal of this paper is to describe the asymptotic behaviour of solutions of
equation (3) for $t\rightarrow\infty$. Due to the dissipation of energy by
dispersion, solutions are expected to settle down to stationary states, in
accord with the soliton resolution conjecture. In section 2 we prove that for
each degree $n$ there exists a unique smooth, finite-energy stationary
solution, which we call the $n$-kink. The linear stability of the $n$-kinks is
analyzed in section 3. We show that the spectrum of the linearized operator
around the $n$-kink has no negative or zero eigenvalues, hence the $n$-kink is
linearly stable. However, for sufficiently large $a$ there are $n$ positive
eigenvalues in the mass gap between zero and the bottom of the continuous
spectrum. These positive eigenvalues give rise to internal modes that
oscillate harmonically and therefore prevent asymptotic stability of kinks at
the linear level (if $a$ is large enough). Nonetheless, it is expected that
the $n$-kink is asymptotically stable thanks to the nonlinear resonant damping
of internal modes, as described by Soffer and Weinstein in [15]. In section 4
we use their weakly nonlinear perturbation method to derive the decay rate of
the internal mode for the $1$-kink. Finally, in section 5 we give numerical
evidence for the soliton resolution conjecture and verify the predictions of
perturbative computations. As in [8], we solve equation (3) numerically using
the hyperboloidal formulation of the initial value problem. This approach
allows us to reach very long times of evolution in a reasonable computational
time. In the appendix we give some details of the computation of parameters of
kinks.

##  2\. Kinks

Time-independent solutions $\phi=\phi(r)$ of equation (3) satisfy the ordinary
differential equation

$\phi^{\prime\prime}+\frac{2r}{r^{2}+a^{2}}\,\phi^{\prime}-\sin(2\phi)=0\,.$
(6)

This equation can be viewed as the equation of motion, with ‘time’ $r$, for
the unit mass particle moving in the potential $-\sin^{2}{\\!\phi}$ and
subject to friction with the time-dependent friction coefficient
$\frac{2r}{r^{2}+a^{2}}$. The solution of degree $n$ corresponds to the
trajectory whose projection on the phase plane $(\phi,\phi^{\prime})$ starts
from the saddle point $(0,0)$ at $r=-\infty$ and goes to the saddle point
$(n\pi,0)$ for $r=+\infty$. The existence and uniqueness of such a connecting
trajectory for each $n$ follows from an elementary shooting argument. For
example, let the particle be located at $\phi=\pi/2$ for $r=0$. If the
velocity $b=\phi^{\prime}(0)$ is too small, then the particle will never reach
the hilltop at $\phi=\pi$, while if $b$ is sufficiently large it will roll
over the hilltop. By continuity, there must be a critical velocity $b_{1}$ for
which the particle reaches the hilltop in infinite time (obviously, by the
uniqueness of trajectories, the particle cannot stop at the hilltop in finite
time). Due to reflection symmetry $r\rightarrow-r$, the particle sent
backwards in time reaches $\phi=0$ for $r\rightarrow-\infty$, giving the
desired connecting trajectory with $n=1$333If $0<\phi(0)<\pi/2$, then by the
same shooting argument there exists a velocity $\phi^{\prime}(0)$ such that
the particle tends to $\pi$ as $r\rightarrow\infty$, however going backwards
this particle will overshoot $0$ and end up at $-\pi/2$ for
$r\rightarrow-\infty$. Thus, there are no asymmetric kinks.. Repeating this
argument for higher $n$ we get a countable family of unique connecting
trajectories $\phi_{n}(r)$ which are symmetric with respect to the midpoint
$\phi(0)=n\pi/2$, that is $\phi_{n}(r)+\phi_{n}(-r)=n\pi$. Near $r=0$

$\phi_{n}(r)=\frac{n\pi}{2}+b_{n}r+\mathcal{O}(r^{3})\,,$ (7)

where the parameter $b_{n}$ uniquely determines the trajectory. For
$r\rightarrow\mp\infty$ the leading asymptotics are, respectively

$\phi_{n}(r)\sim-\frac{c_{n}}{r}\,e^{\sqrt{2}r}\quad\mbox{and}\quad\phi_{n}(r)\sim
n\pi-\frac{c_{n}}{r}\,e^{-\sqrt{2}r}\,,$ (8)

where the parameter $c_{n}$ is determined by $b_{n}$. In the following, we
shall refer to the stationary solution $\phi_{n}$ as the $n$-kink. Fig. 2
depicts sample profiles of $n$-kinks for $n=1,2$. A few values of the
parameters $b_{n}$ and $c_{n}$ are listed in Table I for different values of
$a$ and $n$. While the numerical computation of the parameters $b_{n}$ is
straightforward by means of the shooting method, the computation of the
parameters $c_{n}$ is more difficult because the leading asymptotic behavior
(8) is only the first term of the asymptotic series which has to be summed to
give an accurate approximation of the solution. The details of this
computation are given in the appendix.

Figure 2. Profiles of the $n$-kinks for $n=1,2$. $a$ | $(b_{1},c_{1})$ | $(b_{2},c_{2})$ | $(b_{3},c_{3})$
---|---|---|---
1 | (2.0163, 1.5054) | (2.8709, 4.2523) | (4.3285, 8.5162)
2 | (1.6152, 3.4063) | (1.6531, 13.109) | (2.7121, 33.218)
3 | (1.5123, 5.3885) | (1.1993, 26.592) | (2.1862, 82.056)
Table 1. Parameters $b_{n}$ and $c_{n}$ for three values of $a$.

Next, we shall derive analytic approximations of the kink solutions for large
and small values of $a$. These approximations will be used below in the
stability analysis of the kink. Large $a$ approximation: For $a=\infty$,
equation (6) reduces to the static Sine-Gordon equation

$\phi^{\prime\prime}-\sin(2\phi)=0\,,$ (9)

whose unique (modulo translation) soliton solution is the Sine-Gordon kink

$H(r)=2\arctan{e^{\sqrt{2}r}}\,.$ (10)

Let $\varepsilon=1/a\ll 1$ and write

$\phi(r)=H(r)+\varepsilon^{2}\psi(r)+\mathcal{O}\left(\varepsilon^{4}\right).$
(11)

Substituting this expansion into equation (6) and collecting terms of order
$\varepsilon^{2}$, we obtain

${\psi}^{\prime\prime}-2\cos{(2H)}\psi=-2rH^{\prime}\,.$ (12)

The solution $H^{\prime}$ of the homogeneous equation is even, while the right
hand side is odd, hence the Fredholm solvability condition is satisfied and
consequently there is a unique solution that is odd and decays at $\pm\infty$.
This solution can be written in closed form (using a polylogarithmic function)
but we refrain from displaying it here because it will not be used below. We
confirmed numerically that the approximation $\phi_{1}(r)\approx
H(r)+\psi(r)/a^{2}$ is very accurate for sufficiently large $a^{2}$ (and
$r^{2}<a^{2}$).

The $n$-kink for large $a$ can be approximated by a superposition of $n$ well-
separated Sine-Gordon kinks. For example, for $n=2$ we have

$\phi_{2}(r)\approx H(r-R)+H(r+R).$ (13)

The dependence of the separation parameter $R$ on $a$ can be calculated as
follows. Multiplying equation (6) by $\phi^{\prime}$ and integrating from
$r=0$ to $r=\infty$, we get

$\frac{1}{2}\phi^{\prime}(0)^{2}-\sin^{2}{(\phi(0))}={\int_{0}}^{\infty}\frac{2r}{r^{2}+a^{2}}{\phi^{\prime}}^{2}dr.$
(14)

In terms of the mechanical analogy this equation represents the balance
between the initial energy of the fictitious particle and the energy lost by
friction. Substituting (13) into (14) and assuming that $R$ and $a$ are large,
we get at the leading order $16e^{-2\sqrt{2}R}=\gamma/a^{2},$ where $\gamma$
is a constant. Thus,

$R\approx\frac{1}{\sqrt{2}}\ln{(a)}\quad\mbox{for}\quad a\gg 1.$ (15)

Similar large-$a$ approximations can be given for $n$-kinks with larger $n$.
Small $a$ approximation: Changing variables to $\rho=r/a$ and
$g(\rho)=\phi(r)$, and taking the limit $a\rightarrow 0$, we get the linear
equation

$\frac{d^{2}g}{d\rho^{2}}+\frac{2\rho}{\rho^{2}+1}\frac{dg}{d\rho}=0,$ (16)

whose two linearly independent solutions are $g_{1}=1$ and
$g_{2}=\arctan{\rho}$. Thus, for $a\ll 1$ the $n$-kink is approximated by

$\phi_{n}(r)\approx n\Big{(}\frac{\pi}{2}+\arctan\left(r/a\right)\Big{)}.$
(17)

##  3\. Linear perturbations

In this section we analyze linear stability of kinks $\phi_{n}(r)$. Let

$\phi(t,r)=\phi_{n}(r)+(r^{2}+a^{2})^{-1/2}u(t,r),$ (18)

where the perturbation $u$ is assumed to be small. Plugging this into equation
(3), dropping nonlinear terms in $u$, and assuming harmonic time dependence
$u(t,r)=e^{-i\omega t}v(r)$, we get the eigenvalue problem for the one-
dimensional Schrödinger operator

$L_{n}v\equiv\Big{(}-\frac{d^{2}}{dr^{2}}+2+V_{n}(r)\Big{)}v=\omega^{2}v$ (19)

with the potential

$V_{n}(r)=-4\sin^{2}{\\!\phi_{n}(r)}+\frac{a^{2}}{(r^{2}+a^{2})^{2}}.$ (20)

Figure 3. The potential $V_{n}(r)$ for $n=1,2$ and two values of $a$.

Let us first consider the case $n=1$. As discussed above, in this case the
1-kink $\phi_{1}(r)$ tends for $a\rightarrow\infty$ to the Sine-Gordon kink
$H(r)$ given by (10) for which the corresponding linear stability operator is

$L=-\frac{d^{2}}{dr^{2}}+2-4\sin^{2}{\\!H(r)}=-\frac{d^{2}}{dr^{2}}+2-\frac{4}{\cosh^{2}(\sqrt{2}r)}\,.$
(21)

This operator has a continuous spectrum $\omega^{2}\geq 2$ (the bottom
$\omega^{2}=2$ is a resonance) and a single eigenvalue $\omega^{2}=0$ which is
due to translation symmetry of the Sine-Gordon equation; the associated
normalized eigenfunction (zero mode) is given by

$v_{0}(r)=2^{-3/4}H^{\prime}(r)=\frac{2^{-1/4}}{\cosh(\sqrt{2}r)}.$ (22)

The absence of eigenvalues in the gap $(0,2)$ is believed to be intimately
tied with the complete integrability of the Sine-Gordon equation [16].

The operator $L_{1}$ can be viewed as a compact perturbation of $L$ so it has
the same continuous spectrum $\omega^{2}\geq 2$ but the discrete spectra are
different. We claim that $L_{1}>L$. To show this, let us observe that
$\phi_{1}(r)>H(r)$ for $r>0$ (and by the reflection symmetry
$0<\phi_{1}(r)<H(r)$ for $r<0$). This fact is evident within our mechanical
analogy because the fictitious particle corresponding to $\phi_{1}$ is subject
to friction while the one corresponding to $H$ moves without friction. To see
this, note that $\phi_{1}(0)=H(0)=\pi/2$ and
$\phi^{\prime}_{1}(0)>H^{\prime}(0)$, hence $\phi_{1}(r)>H(r)$ for small
$r>0$. In fact, this inequality holds for all $r>0$ because the $H$-particle
cannot overtake the $\phi_{1}$-particle (since at the overtake point the
$\phi_{1}$-particle would have smaller kinetic energy than the $H$-particle
and could not reach the hilltop). Since $-\sin^{2}{\phi}$ is decreasing for
$\phi\in[0,\pi/2]$ and increasing for $\phi\in[\pi/2,\pi]$, it follows that
$-\sin^{2}{\phi_{1}(r)}>-\sin^{2}{H(r)}$ for all $r$ which by (19) and (21)
implies that $L_{1}>L$. Since $L$ has exactly one eigenvalue at
$\omega^{2}=0$, it follows (see, e.g., Corollary 4.11 on page 119 in [17])
that $L_{1}$ has no negative eigenvalues and at most one positive eigenvalue
in the gap $(0,2)$.

To obtain a more quantitative information about the gap eigenvalue of $L_{1}$
for large values of $a$ we seek a perturbative solution of the eigenvalue
problem (19) in the form

$v=v_{0}+\varepsilon^{2}v_{1}+\mathcal{O}\left(\varepsilon^{4}\right),\quad\omega^{2}=c\,\varepsilon^{2}+\mathcal{O}\left(\varepsilon^{4}\right),$
(23)

where $\varepsilon=1/a\ll 1$. Inserting (11) and (23) into (19), at the zero
order we obtain $Lv_{0}=0$, while at the order $\varepsilon^{2}$ we get

$Lv_{1}=cv_{0}+2r{v_{0}}^{\prime}+4\sin(2H)\psi v_{0}.$

The right hand side must be orthogonal to $v_{0}$ which yields

$c=1-4\int_{-\infty}^{\infty}\sin{(2H(r))}\psi(r){v_{0}(r)}^{2}dr\,.$ (24)

To calculate the above integral we differentiate equation (12)

$L\psi^{\prime}=4\sin(2H)H^{\prime}\psi+2(rH^{\prime})^{\prime}\,.$ (25)

Taking the inner product with $v_{0}$ and integrating by parts we get

$4\int_{-\infty}^{\infty}\sin(2H(r))\psi(r)v_{0}(r)^{2}\,dr=-\int_{-\infty}^{\infty}v_{0}(r)^{2}\,dr=-1.$
(26)

Substituting this into (24) we obtain $c=2$.

As $a$ decreases, the potential well gets shallower and eventually becomes a
barrier, as follows from the small-$a$ approximation of kinks (17); see Fig.
3. Accordingly, as shown in Fig. 4, the eigenvalue $\omega^{2}$ migrates
through the gap $(0,2)$ and disappears into the continuous spectrum for $a$
smaller than some critical value $a^{*}$ (for $a=a^{*}$ there is a resonance
at the bottom of the continuous spectrum)444A similar behavior of the gap
eigenvalue was found for some geometric wave equations on the hyperbolic space
[18].. Numerically, we find that $a^{*}\approx 0.536$.

Figure 4. The frequency of the internal mode of the $1$-kink as a function of
$1/a$.

For a given $n\geq 2$ and sufficiently large $a$, it follows from the
large-$a$ approximation of $n$-kinks that the potential has the form of $n$
wells equally separated by the distance $\propto\ln(a)$. Consequently, if $a$
is large enough there are $n$ gap eigenvalues

$0<\omega_{1}^{2}<\dots<\omega_{n}^{2}<2.$

As $a$ decreases, the potential wells go up (see Fig. 3) and the gap
eigenvalues disappear one by one into the continuous spectrum at certain
critical values $a^{*}_{1}<a^{*}_{2}<\dots<a^{*}_{n}$. For example, for $n=2$
we find numerically $a^{*}_{1}\approx 0.39$ and $a^{*}_{2}\approx 0.81$.

##  4\. Weakly nonlinear dynamics near the $1$-kink

In this section we study solutions of equation (3) for initial data near the
kink $\phi_{1}$. In terms of $u(t,r)$ defined in (18), equation (3) takes the
form

$\ddot{u}+L_{1}u=f(u,r)\,,$ (27)

where the linear operator $L_{1}$ is defined in (19) and the nonlinear term

$f(u,r)=\sqrt{r^{2}+a^{2}}\left[\sin(2\phi_{1})-\sin\left(2\phi_{1}+\frac{2u}{\sqrt{r^{2}+a^{2}}}\right)\right]+2\cos(2\phi_{1})u$
(28)

is real-analytic in $u$ and $r$ (in what follows we suppress the dependence of
$f$ on $r$). The Taylor series of $f(u)$ starts from the quadratic term:

$f(u)=\frac{2\sin(2\phi_{1})}{\sqrt{r^{2}+a^{2}}}\,u^{2}+\frac{4\cos(2\phi_{1})}{2(r^{2}+a^{2})}\,u^{3}+\mathcal{O}(u^{4}).$
(29)

As follows from (8), the coefficients in this expansion are decaying functions
(exponentially for even powers of $u$ and algebraically for odd powers), which
means that the nonlinear terms are spatially localized. This property,
intimately related to the fact that our equation descends from higher
dimensions, will play an important role in our analysis555We point out that
the lack of spatial localization of nonlinear interactions is one of the major
difficulties in the studies of asymptotic stability of topological solitons in
one spatial dimension, see [3, 19, 20]..

We recall from the previous section that for $a<a^{*}$ the spectrum of the
operator $L_{1}$ is purely continuous. In this case, the nonlinear term
$f(u)$, due to its strong spatial localization, does not affect the leading
order asymptotic behavior of small amplitude solutions. Consequently, such
solutions decay as $t^{-3/2}$ for $t\rightarrow\infty$, which is the three-
dimensional free linear dispersive decay or, equivalently, the one-dimensional
linear dispersive decay in the presence of the rapidly decreasing potential
(which has no bound states nor a resonance at the bottom of the continuous
spectrum) [21, 22].

For the rest of this section we shall focus on the more interesting case
$a>a^{*}$ where

$\mathrm{spec}(L_{1})=\\{\omega^{2}\\}\cup[2,+\infty),\quad 0<\omega^{2}<2.$

In what follows, the normalized eigenfunction associated to the eigenvalue
$\omega^{2}$ is denoted by $v$, while the modes of the continuous spectrum are
denoted by $\eta$. We decompose the solution as the orthogonal sum of the
discrete and continuum modes of $L_{1}$

$u(t,r)=\alpha(t)v(r)+\eta(t,r),\quad\mbox{where}\quad\langle
v,\eta\rangle=0.$ (30)

Substituting this decomposition into (27) and projecting on the discrete and
continuous components, using the projection operators $Pf=\langle v,f\rangle
v$ and $P^{\perp}f=f-\langle v,f\rangle v$ (where $\langle
v,f\rangle:=\int_{-\infty}^{+\infty}\bar{v}(r)f(r)\,dr$), we get a system

$\displaystyle\ddot{\alpha}+\omega^{2}\alpha$ $\displaystyle=$
$\displaystyle\langle v,f(\alpha v+\eta)\rangle,$ (31)
$\displaystyle\ddot{\eta}+L_{1}\eta$ $\displaystyle=$ $\displaystyle
P^{\perp}f(\alpha v+\eta)\,.$ (32)

This system describes interaction between the internal mode and radiation.
When the nonlinearity is “switched off”, equations (31) and (32) decouple and
the internal mode performs harmonic oscillations with frequency $\omega$. If
the perturbation $u$ is small, the system is weakly coupled and the energy is
slowly transferred from the internal mode to the continuum modes and then
disperses to infinity. As the result, the amplitude of the internal mode
decays asymptotically to zero and the solution converges (on any compact
spatial interval) to the static solution $\phi_{1}$. The key mechanism of this
relaxation process is the nonlinear resonance between the internal mode and
the continuum. It was first described rigorously by Soffer and Weinstein in a
seminal paper [15] (see also [23] for a formal construction, [24, 25] for
ramifications, and [26] for a recent review). Below we will adapt their
approach to our case, however in contrast to [15] we will not justify our
formal calculations by error estimates (which would be quite technical).
Instead, to feel confident that the results are true, in the next section we
will verify them by numerical computations.

It is convenient to use the complex variable
$z=\alpha+\frac{i}{\omega}\dot{\alpha}$ and rewrite equation (31) as the
first-order ordinary differential equation

$\dot{z}+i\omega z=\frac{i}{\omega}\langle
v,f\left(\frac{1}{2}(z+\bar{z})v+\eta\right)\rangle\,.$ (33)

We expand the nonlinearity in the formal power series in $z,\bar{z}$ and
$\eta$

$f\left(\frac{1}{2}(z+\bar{z})v+\eta\right)=\sum_{k+l+m\geq
2}f_{mkl}\eta^{m}z^{k}\bar{z}^{l},$ (34)

where indices run over nonnegative integers. The coefficients $f_{mkl}(r)$ are
symmetric in the last two indices and can be read off from the Taylor series
(29). Substituting this expansion into equations (33) and (32) we arrive at
the system

$\displaystyle\dot{z}+i\omega z$ $\displaystyle=$
$\displaystyle\frac{i}{\omega}\sum_{k+l+m\geq 2}\langle
f_{mkl}\eta^{m},v\rangle\,z^{k}\bar{z}^{l},$ (35)
$\displaystyle\ddot{\eta}+L_{1}\eta$ $\displaystyle=$
$\displaystyle\sum_{k+l+m\geq 2}P^{\perp}(f_{mkl}\eta^{m})\,z^{k}\bar{z}^{l}.$
(36)

In the following we introduce the symbol $\mathcal{O}_{p}(z,\eta)$ defined by

$\sum_{k+l+m\geq
2}c_{mkl}\eta^{m}z^{k}\bar{z}^{l}=\mathcal{O}_{p}(z,\eta)\quad\mbox{if}\quad\min\\{k+l+2m\mid
c_{mkl}\neq 0\\}=p,$ (37)

which incorporates a heuristic rule of thumb (to be justified a posteriori)
that $\eta=\mathcal{O}(z^{2})$. With this notation, those terms on the right
hand sides of equations (35) and (36) that do not involve $\eta$ are of the
order $\mathcal{O}_{2}$, while those that involve $\eta$ are of the order
$\mathcal{O}_{3}$.

Next, we make a near-identity coordinate transformation

$\eta=\tilde{\eta}+\sum_{k+l\geq 2}a_{kl}z^{k}\bar{z}^{l}\,,$ (38)

where the coefficients $a_{kl}$ (which are symmetric) are functions of $r$.
The purpose of this transformation is to eliminate the terms of order
$\mathcal{O}_{2}$ on the right hand side of equation (36). As we will see
shortly, this change of variables is formal in the sense that, although a
priori $\eta$ is decaying in space, the functions $a_{kl}$ in general do not
decay. To justify rigorously the procedure described below one can consider
(27) in weighted spaces consistent with (18), c.f. [22] or in the energy space
following the arguments in [28, 29, 30]. A heuristic reason why the procedure
works in the first place is that the system governing the dynamics of the
internal modes is always localized by the projection on the eigenspace.

Substituting (38) into (36) we get

$\ddot{\tilde{\eta}}+L_{1}\tilde{\eta}+\sum_{k+l=2}(L_{1}-(k-l)^{2}\omega^{2})a_{kl}z^{k}\bar{z}^{l}=\sum_{k+l=2}P^{\perp}f_{0kl}z^{k}\bar{z}^{l}+\mathcal{O}_{3}\,.$
(39)

If we manage to remove the $\mathcal{O}_{2}$ terms then formally
$\tilde{\eta}=\mathcal{O}_{3}$. To do so we impose the condition

$\left(L_{1}-(k-l)^{2}\omega^{2}\right)a_{kl}=P^{\perp}f_{0kl},\qquad k+l=2.$
(40)

For the combination of indices $(k,l)=(1,1)$, there is a unique real-valued
solution $a_{11}(r)$ that decays for $|r|\rightarrow\infty$. We do not write
it down because the only thing that matters is that this solution is real
valued. For the combination $(k,l)=(2,0)$ we need to consider two cases: (i)
$4\omega^{2}>2$ and (ii) $4\omega^{2}<2$ (we omit the nongeneric case
$4\omega^{2}=2$ which is more involved). We postpone the analysis of the case
(ii) until afterwards and now we focus on the case (i). In this case, the
frequency $2\omega$ lies in the continuous spectrum of $L_{1}$ and therefore
solutions of the homogeneous equation $(L_{1}-4\omega^{2})a=0$ are oscillatory
at infinity. Among them there is a unique (complex) solution $a_{20}(r)$ that
satisfies the outgoing boundary conditions for $|r|\rightarrow\infty$. Using
the method of variation of parameters, this solution can be expressed in the
form

$a_{20}(r)=\frac{i}{2\xi}\,k(r)\int\limits_{-\infty}^{r}\bar{k}(s)P^{\perp}f_{020}(s)ds+\frac{i}{2\xi}\,\bar{k}(r)\int\limits_{r}^{\infty}k(s)P^{\perp}f_{020}(s)ds,$
(41)

where $\xi=\sqrt{4\omega^{2}-2}$ and $k(r)$ is the solution of the homogeneous
equation satisfying the following outgoing boundary condition at $+\infty$

$k(r)=e^{i\xi r}m(r),\quad\lim_{r\rightarrow\infty}m(r)=1,$ (42)

and $\bar{k}(r)$ satisfies the corresponding outgoing boundary condition at
$-\infty$. In (41) we used the Wronskian

$W[k(r),\bar{k}(r)]:=k(r)\bar{k}^{\prime}(r)-\bar{k}(r)k^{\prime}(r)=-2i\xi,$
(43)

which follows from (42) and the fact that $\bar{k}(r)=k(-r)$ (what in turn
follows from invariance of $L_{1}$ under reflections $r\rightarrow-r$).

Substituting (38) into (35) and using $\tilde{\eta}=\mathcal{O}_{3}$, we get

$\dot{z}+i\omega z=\frac{i}{\omega}\sum_{2\leq k+l\leq 3}\langle
v,f_{0kl}\rangle
z^{k}\bar{z}^{l}+\frac{i}{\omega}\sum_{\begin{subarray}{c}k+l=1\\\
p+q=2\end{subarray}}\langle v,f_{1kl}a_{pq}\rangle
z^{k+p}\bar{z}^{l+q}+\mathcal{O}_{4}\,.$ (44)

The key point is that all the dependence on $\tilde{\eta}$ on the right hand
side is contained in the term $\mathcal{O}_{4}$, hence up to the third order
this equation is decoupled from the radiation equation. To factor out fast
oscillations with frequency $\omega$ we let $z=e^{-i\omega t}Z$. Substituting
this into (44) and dropping all nonresonant terms666A rigorous justification
of this procedure, also called normal form transformation, can be found in
[27]. i.e. terms involving powers of $e^{i\omega t}$ (because such terms time-
average to zero), we finally obtain the third order resonant approximation for
$t>0$777We point out that equation (45) is not invariant under the time
reversal $t\rightarrow-t$. The arrow of time was selected by the outgoing
boundary conditions imposed on $a_{20}$.

$\dot{Z}=\frac{i}{\omega}\left(\langle v,f_{021}\rangle+\langle
v,f_{110}a_{11}\rangle+\langle v,f_{110}a_{20}\rangle\right)Z^{2}\bar{Z}.$
(45)

The first two terms in the bracket are real, hence multiplying (45) by
$\bar{Z}$ and taking the real part we get

$\frac{d}{dt}|Z|^{2}=-\Gamma|Z|^{4},\quad\mbox{where}\quad\Gamma=\frac{2}{\omega}\langle
v,f_{110}\operatorname{Im}(a_{20})\rangle.$ (46)

The coefficient $\Gamma$ can be calculated as follows. From (29) and (30) we
find

$f_{110}=\frac{2\sin(2\phi_{1})}{\sqrt{r^{2}+a^{2}}}\,v\quad\mbox{and}\quad
f_{020}=\frac{\sin(2\phi_{1})}{2\sqrt{r^{2}+a^{2}}}\,v^{2}=\frac{1}{4}f_{110}v.$
(47)

Since $f_{020}(r)$ is an odd function while $v(r)$ is even, it follows that
$P^{\perp}f_{020}=f_{020}$, and from (41) we get

$\operatorname{Im}(a_{20})=\frac{1}{2\xi}\operatorname{Re}\left(k(r)\int\limits_{-\infty}^{\infty}\bar{k}(s)f_{020}(s)ds\right)\,.$
(48)

Inserting this expression into formula (46) and using (47), we finally obtain

$\Gamma=\frac{1}{\xi\omega}\,\left\lvert\left\langle
k,\frac{\sin(2\phi_{1})v^{2}}{\sqrt{r^{2}+a^{2}}}\right\rangle\right\rvert^{2}\,,$
(49)

hence $\Gamma\geq 0$. Generically $\Gamma$ is strictly positive888This
genericity condition is sometimes referred to as the Fermi Golden Rule [31,
15], which goes back to Dirac’s theory of radiation in quantum mechanics [32].
and then equation (46) gives

$|Z|\sim\Gamma^{-\frac{1}{2}}t^{-\frac{1}{2}}\quad\mbox{as}\quad
t\rightarrow\infty.$ (50)

The purely imaginary terms on the right hand side of equation (45) determine
the phase of $Z$. Returning to the amplitude
$\alpha=\frac{1}{2}\left(e^{-i\omega t}Z+e^{i\omega t}\bar{Z}\right)$, we get
the asymptotic behavior

$\alpha(t)\sim\Gamma^{-\frac{1}{2}}t^{-\frac{1}{2}}\cos\left(\omega
t+\theta(t)\right),\quad\mbox{where}\quad\theta(t)=\mathcal{O}(\ln{t}),$ (51)

hence as the amplitude of the internal mode decays asymptotically to zero, its
frequency tends to the linear frequency $\omega$ (in other words, no frequency
shift or ‘memory’ effect occurs). Now, we return to the case (ii)
$4\omega^{2}<2$. In this case the frequency $2\omega$ generated by the
quadratic term is below the continuous spectrum so there is no resonant
damping present at the third perturbative order (technically, in this case the
solution $a_{20}$ of equation (40) is real and therefore the right hand side
of equation (45) is purely imaginary). One needs to go to higher orders to see
the damping. Let $N$ be a positive integer such that

$N^{2}\omega^{2}<2<(N+1)^{2}\omega^{2}\,,$ (52)

hence $(N+1)\omega$ is the lowest multiple of the frequency $\omega$ that lies
in the continuous spectrum. The case (i) discussed above corresponds to $N=1$.
For $N\geq 2$ we iterate the near-identity transformation (38) $N$ times to
eliminate terms of order $N+1$ in the radiation equation. As the result of
this iteration, the internal mode equation decouples from radiation up to
order $\mathcal{O}_{2N+1}$. By the same reasoning as above, this yields the
resonant approximation of order $\mathcal{O}_{2N+1}$ for the internal mode
equation

$\dot{Z}=\sum_{1\leq l<N}c_{l}Z^{l+1}\bar{Z}^{l}+c_{N}Z^{N+1}\bar{Z}^{N}\,,$
(53)

where the coefficients $c_{l}$ with $l<N$ are purely imaginary, while
$\operatorname{Re}(c_{N})~{}\leq 0$. Thus,

$\frac{d}{dt}|Z|^{2}=2\operatorname{Re}(c_{N})|Z|^{2N+2},$ (54)

which gives (assuming that $\operatorname{Re}(c_{N})$ is strictly negative)
for $t\rightarrow\infty$

$|Z|\sim C_{N}t^{-\frac{1}{2N}},\quad\mbox{where}\quad
C_{N}=\left(2N|\operatorname{Re}(c_{N})|\right)^{-\frac{1}{2N}}\,.$ (55)

Assuming that the coefficient $c_{1}$ in (53) is nonzero, the amplitude of the
internal mode behaves asymptotically as

$\alpha(t)\sim C_{N}t^{-\frac{1}{2N}}\cos\left(\omega
t+\theta(t)\right),\quad\mbox{where}\quad\theta(t)=\mathcal{O}(t^{\frac{N-1}{N}}).$
(56)

Having the formulae for $\alpha(t)$, we now return to the radiation field
$\eta(t,r)$. The asymptotic behavior of $\eta(t,r)$ for $t\rightarrow\infty$
is determined by the quadratic term in equation (36), hence to the leading
order we have

$\ddot{\eta}+L_{1}\eta\simeq
P^{\perp}\left(\alpha^{2}\,f_{2}v^{2}+2\alpha\,f_{2}v\eta+f_{2}\eta^{2}\right),$
(57)

where $f_{2}=\frac{2\sin(2\phi_{1})}{\sqrt{r^{2}+a^{2}}}$ is the coefficient
of the quadratic term in (29). All terms on the right hand side are
exponentially localized in space and the dominant contribution comes from the
first term which behaves as $\alpha^{2}$. Inserting $\alpha(t)\sim t^{-1/2N}$
and noting that the solution of the homogeneous equation decays as $t^{-3/2}$
[22], we conclude that $\eta(t,r)\sim t^{-1/N}$. This heuristic argument
justifies a posteriori that $\eta=\mathcal{O}(z^{2})$, as claimed above.

##  5\. Numerical evidence

In this section we solve equation (3) numerically using the hyperboloidal
formulation of the initial value problem [33]. As in [8] we define new
coordinates

$s=\frac{t}{a}-\sqrt{\frac{r^{2}}{a^{2}}+1}\,,\quad
y=\arctan\left(\frac{r}{a}\right)\,.$ (58)

The hypersurfaces of constant $s$ are ‘hyperboloidal’, that is they are
spacelike hypersurfaces that approach the ‘left’ and ‘right’ future null
infinities of the wormhole spacetime along the outgoing null cones. In terms
of the coordinates $(s,y)$ and $h(s,y)=\phi(t,r)$ equation (3) takes the form

$\partial^{2}_{s}h+2\sin{y}\,\partial_{s}\partial_{y}h+\frac{1+\sin^{2}{y}}{\cos{y}}\,\partial_{s}h=\cos^{2}{\\!y}\,\partial^{2}_{y}h-a^{2}\,\frac{\sin(2h)}{\cos^{2}{y}}\,.\\\
$ (59)

We solve this equation for smooth initial data of degree $n$

$h(0,y)=\alpha(y),\quad\partial_{s}h(0,y)=\beta(y),$ (60)

where the functions $\alpha(y)$ and $\beta(y)$ tend exponentially to
$\alpha(-\frac{\pi}{2})=0$, $\alpha(\frac{\pi}{2})=n\pi$ and
$\beta(\pm\frac{\pi}{2})=0$. In this formulation, the $n$-kink denoted by
$h_{n}(y)$ satisfies the boundary conditions $h_{n}(-\frac{\pi}{2})=0$,
$h_{n}(\frac{\pi}{2})=n\pi$. No boundary conditions are imposed because the
principal part of equation (59) degenerates to $\partial_{s}(\partial_{s}\pm
2\partial_{y})h$ at the endpoints $y=\pm\pi/2$, hence there are no ingoing
characteristics at the boundaries999We remark that for massless fields
considered in [8] there was an outflow of energy defined on hyperboloidal
slices through the boundaries due the outgoing radiation. In the case at hand,
the boundaries do not participate in the evolution, and hence the energy is
conserved, because the group velocity of waves is strictly less than one..
Following [8, 33] we define the auxiliary variables

$q=\partial_{y}h\quad\mbox{and}\quad
p=\partial_{s}h+\sin{y}\,\partial_{y}h\,,$

and rewrite equation (59) as the first order symmetric hyperbolic system

$\displaystyle\partial_{s}h$ $\displaystyle=$ $\displaystyle p-q\sin{y}\,,$
(61a) $\displaystyle\partial_{s}q$ $\displaystyle=$
$\displaystyle\partial_{y}\left(p-q\sin{y}\right)\,,$ (61b)
$\displaystyle\partial_{s}p$ $\displaystyle=$
$\displaystyle\partial_{y}\left(q-p\sin{y}\right)+2\tan{y}\left(q-p\sin{y}\right)-a^{2}\,\frac{\sin(2h)}{\cos^{2}{y}}.$
(61c)

The initial data (60) translate to

$h(0,y)=\alpha(y),\quad q(0,y)=\alpha^{\prime}(y),\quad
p(0,y)=\beta(y)+\sin{y}\,\alpha^{\prime}(y)\,.$ (62)

We solve this system numerically using the method of lines with a fourth-order
Runge-Kutta time integration and eighth-order spatial finite differences. One-
sided stencils are used at the boundaries. Kreiss-Oliger dissipation is added
in the interior in order to reduce unphysical high-frequency noise. To
suppress violation of the constraint $q-\partial_{y}h=0$, we add the term
$\epsilon(q-\partial_{y}h)$ with a small negative $\epsilon$ to the right hand
side of equation (61b). For any initial data of degree $n$, we find that the
solution $h(s,y)$ converges pointwise to the $n$-kink $h_{n}(y)$ as
$s\rightarrow\infty$. In the following, we focus on solutions of degree one
and illustrate the results of numerical computations for sample initial data
of the form

$\alpha(y)=h_{1}(y)+e^{-\frac{1}{4}\tan^{2}{y}},\quad\beta(y)=0.$ (63)

The convergence rates for several values of $a$ are depicted in Fig. 6.

Figure 5. The snapshots of $h(s,y)$ for the initial data (63). The solution
converges to the $1$-kink $h_{1}(y)$ (solid black line) in an oscillatory
manner. Figure 6. Amplitudes of perturbations evaluated at $y=0$ in the
evolution of initial data (63) for different values of the wormhole radius:
$a=0.25$ (no gap eigenvalue) and $a=1$ ($\omega=1.0682$), $a=2$
($\omega=0.6345$), $a=3$ ($\omega=0.4455$), corresponding to $N=1,2,3$ in
(52), respectively. The red dashed lines depict analytic predictions with
empirically fitted coefficients.

The results are in accord with the formulae (51) and (56) for the decay of the
internal mode, and verify the decay rate $s^{-3/2}$ when the internal mode is
absent. We emphasize that both the decay rates and the coefficients are
universal (i.e., independent of initial data). In the $N=1$ case the
coefficient $2.79$ obtained from the empirical fit agrees (to three decimal
places) with $\Gamma^{-1/2}$ calculated from formula (49). This excellent
quantitative agreement between analytic and numerical results makes us feel
confident that _both_ computations are correct.

For the evolutions depicted in Fig. 6 the frequencies of internal modes are
well separated from the threshold values $\sqrt{2}/(N+1)$. If the frequency of
the internal mode is near a threshold value, an intermediate dynamics is more
complicated. This is illustrated in Fig. 7 where we plot the effective
frequency $\omega(s)$ (computed from the distances of subsequent maxima of
oscillations) and amplitude of perturbation for $a=1.65$ for which
$\omega=0.7422$ is a little above the $N=1$ threshold value $\sqrt{2}/2\approx
0.7071$. Initially, the effective frequency is below $\sqrt{2}/2$ and the
amplitude decays approximately as $s^{-1/4}$ (as in the $N=2$ case). For later
times, the effective frequency increases above the threshold and concurrently
the decay rate of the amplitude undergoes a transition to the asymptotic rate
$s^{-1/2}$ ($N=1$ case).

Figure 7. The effective frequency (left panel) and the amplitude (right panel)
in the evolution of initial data (63) for $a=1.65$. The late-time small
oscillations of the frequency are believed to be due to nonresonant
interactions.

To summarize, the Sine-Gordon equation on the wormhole is a rich model for
developing understanding of the asymptotic stability of topological solitons
with internal modes. In this work we focused mainly on dynamics of
perturbations of the 1-kink. It would be interesting to generalize the weakly
nonlinear perturbation analysis from section 4 to $n$-kinks with multiple
internal modes. We leave this to future work.

_Acknowledgement._ We acknowledge helpful conversations with Gary Gibbons
during the early stage of this project. This work was supported in part by the
National Science Centre grant no. 2017/26/A/ST2/00530 (to PB), STFC
consolidated grant no. ST/P000681/1 (to MD), FONDECYT 1170164 and CMM Conicyt
PIA AFB170001 (to MK).

##  6\. Appendix

We describe here how we computed the coefficients $c_{n}$ in the asymptotic
expansion (8). Since the solutions $\phi_{n}(r)$ of equation (6) are
symmetric, it is sufficient to consider the asymptotic behavior at one end,
say $r\rightarrow\infty$

$n\pi-\phi_{n}(r)\sim\frac{c_{n}}{r}\,e^{-\sqrt{2}r}.$ (64)

Let us observe that for large values of $r$ we have

$n\pi-\phi_{n}(r)=c_{n}\,\phi_{L}(r)+\mathcal{O}(e^{-3\sqrt{2}r}),$ (65)

where $\phi_{L}(r)$ is the solution of the linearized equation

$\phi_{L}^{\prime\prime}+\frac{2r}{r^{2}+a^{2}}\,\phi_{L}^{\prime}-2\phi_{L}=0,$
(66)

such that

$\phi_{L}(r)\sim\frac{1}{r}\,e^{-\sqrt{2}r}\quad\text{for}\,\,r\rightarrow\infty.$
(67)

Equation (66) has two regular singular points $r=\pm ai$ and the irregular
singularity at $r=\infty$ and the general solution can be expressed in terms
of confluent Heun functions [34]

$\phi_{L}=C_{1}\,\text{HeunC}\left(0,-\alpha,0,\gamma,\delta,-r^{2}/a^{2}\right)+C_{2}\,\text{HeunC}\left(0,\alpha,0,\gamma,\delta,-r^{2}/a^{2}\right)\,,$
(68)

where
$\alpha=\frac{1}{2},\gamma=\frac{1}{2}a^{2},\delta=-\frac{1}{2}a^{2}+\frac{1}{4}$.
In order to find the coefficients $C_{1}$ and $C_{2}$ such that $\phi_{L}$
satisfies (67) we proceed in two steps. In the first step, we temporarily set
$C_{1}=1$ and determine $C_{2}$ numerically by solving the equation
$\phi_{L}(r)=0$ for some large value of $r$, say $r=60$. This computation has
to be performed with very high precision (up to 60 decimal places) which is
possible in Maple where the Heun functions are tabulated. Having that, in the
second step, we compute numerically the limit
$\beta=\lim_{r\rightarrow\infty}re^{\sqrt{2}r}\phi_{L}(r)$. This is done by
evaluating $r_{j}e^{\sqrt{2}r_{j}}\phi_{L}(r_{j})$ for an increasing series of
$r_{j}$ (say from $r_{1}=20$ to $r_{10}=30$) and using the Shanks
transformation to accelerate the convergence. Rescaling the coefficients
$C_{k}\mapsto C_{k}/\beta$ we get the solution $\phi_{L}(r)$ satisfying (67).
Finally, taking the numerical solution $\phi_{n}(r)$ obtained by the shooting
method we compute the coefficients $c_{n}$ using the formula

$c_{n}\approx\frac{n\pi-\phi_{n}(r_{0})}{\phi_{L}(r_{0})},$ (69)

where $r_{0}$ is small enough, say $r_{0}=6$, so that the value
$\phi_{n}(r_{0})$ is accurate.

## References

  * [1] A. Soffer, _Soliton dynamics and scattering,_ ICM-2006 Conference Book, 2007.
  * [2] T. Tao, _Why are solitons stable?,_ Bull. Amer. Math. Soc. 46, 1-33 (2009)
  * [3] M. Kowalczyk, Y. Martel, C. Muñoz, _On asymptotic stability of nonlinear waves,_ Séminaire Laurent Schwartz-EDP et applications 18, 27 (2016-2017)
  * [4] W. Eckhaus, P.C. Schuur, _The emergence of solitons of the Korteweg-deVries equation from arbitrary initial conditions,_ Math. Methods Appl. Sci.5.1, 97–116 (1983)
  * [5] P.C. Schuur, _Asymptotic analysis of soliton problems: an inverse scattering approach,_ Lecture Notes in Mathematics vol.1232, Springer-Verlag (1986)
  * [6] T. Duyckaerts, C.E. Kenig, F. Merle, _Classification of radial solutions of the focusing, energy-critical wave equation,_ Camb. J. Math. 1, 75-144 (2013)
  * [7] C. E. Kenig, A. Lawrie, B. Liu, W. Schlag, _Stable soliton resolution for exterior wave maps in all equivariance classes,_ Adv. Math. 285, 235-300 (2015)
  * [8] P. Bizoń, M. Kahl, _Wave maps on a wormhole,_ Phys. Rev. D 91, 065003 (2015)
  * [9] H. Ellis, _Ether flow through a drainhole: A particle model in general relativity,_ J. Math. Phys. 14, 104 (1973).
  * [10] K. Bronnikov, _Scalar-tensor theory and scalar charge,_ Acta Phys. Polonica B 4, 251-266 (1973)
  * [11] M.S. Morris, K.S. Thorne, _Wormholes in spacetime and their use for interstellar travel: A tool for teaching general relativity,_ Am. J. Phys. 56, 395 (1988)
  * [12] C. Rodriguez, _Soliton resolution for equivariant wave maps on a wormhole,_ Comm. Math. Phys. 359, 375-426 (2018)
  * [13] C. Rodriguez, _Soliton resolution for corotational wave maps on a wormhole,_ Int. Math. Res. Not. 15, 4603-4706 (2019)
  * [14] A. Waterhouse, _The $\phi^{4}$ kink on a wormhole spacetime,_ arXiv:1908.09650
  * [15] A. Soffer, M.I. Weinstein, _Resonances, radiation damping and instability in Hamiltonian nonlinear wave equations,_ Invent. Math. 136, 9-74 (1999)
  * [16] Y. Kivshar, D. Pelinovsky, T. Cretegny, M. Peyrard, _Internal modes of solitary waves,_ Phys. Rev. Lett. 80, 5032-5035 (1998)
  * [17] G. Teschl, Mathematical Methods in Quantum Mechanics: With Applications to Schrd̈inger Operators, AMS 2009.
  * [18] A. Lawrie, S.-J. Oh, S. Shahshahani, _Gap eigenvalues and asymptotic dynamics of geometric wave equations on hyperbolic space_ , J. Funct. Anal. 271, 3111-3161 (2016)
  * [19] H. Lindblad, J. Luhrmann, A. Soffer, _Asymptotics for 1D Klein-Gordon equations with variable coefficient quadratic nonlinearities,_ arXiv:2006.00938
  * [20] P. Germain, F. Pusateri, _Quadratic Klein-Gordon equations with a potential in one dimension,_ arXiv:2006.15688
  * [21] W. Schlag, _Spectral theory and nonlinear PDE: a survey,_ Discrete Cont. Dyn. Syst. 15, 703-723 (2006)
  * [22] I.E. Egorova, E.A. Kopylova, V.A. Marchenko, G. Teschl, _Dispersion estimates for one-dimensional Schrödinger and Klein–Gordon equations revisited,_ Uspekhi Mat. Nauk 71, 3–26 (2016)
  * [23] D.E. Pelinovsky, Y.S. Kivshar, V.V. Afanasjev, _Internal modes of envelope solitons,_ Physica D 116, 121-142 (1998)
  * [24] D. Bambusi, S. Cuccagna, _On dispersion of small energy solutions to the nonlinear Klein-Gordon equation with a potential,_ Amer. J. Math. 133, 1421-1468 (2011)
  * [25] X. An, A. Soffer, _Fermi’s Golden Rule and $H^{1}$ scattering for nonlinear Klein-Gordon equations with metastable states,_ Discrete Cont. Dyn. Sys. A 40, 331-371 (2020)
  * [26] S. Cuccagna, M. Maeda, _A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II,_ arXiv:2009.00573
  * [27] D. Bambusi, _Asymptotic stability of ground states in some hamiltonian PDEs with symmetry,_ Commun. Math. Phys. 305, 279-331 (2011)
  * [28] M. Kowalczyk, Y. Martel, C. Muñoz, _Kink dynamics in the $\phi^{4}$ model: asymptotic stability for odd perturbations in the energy space,_ J. Amer. Math. Soc. 30, 769–798 (2017)
  * [29] M. Kowalczyk, Y. Martel, C. Muñoz, _Soliton dynamics for the 1D NLKG equation with symmetry and in the absence of internal modes,_ arXiv:1903.12460
  * [30] M. Kowalczyk, Y. Martel, C. Muñoz, H. Van Den Bosch, _A sufficient condition for asymptotic stability of kinks in general (1+1)-scalar field models,_ arXiv:2008.01276.
  * [31] I.M. Sigal, _Nonlinear wave and Schrödinger equations. I. Instability of periodic and quasiperiodic solutions,_ Comm. Math. Phys. 153, 297–320 (1993)
  * [32] P.A.M. Dirac, _The Quantum Theory of the Emission and Absorption of Radiation,_ Proc. Roy. Soc. London. A 114, 243-264 (1927)
  * [33] A. Zenginoğlu, _A hyperboloidal study of tail decay rates for scalar and Yang-Mills fields,_ Class. Quant. Grav. 25, 175013 (2008)
  * [34] NIST Digital Library of Mathematical Functions, http://dlmf.nist.gov/