text:
\begin{document}
\title{On Suboptimality of Least Squares with Application to Estimation of Convex Bodies}

\author{Gil Kur \thanks{Massachusetts Institute of Technology, \texttt{gilkur@mit.edu}}
	\and
	Alexander Rakhlin \thanks{Massachusetts Institute of Technology, \texttt{rakhlin@mit.edu}}
	\and
	Adityanand  Guntuboyina \thanks{UC Berkeley, \texttt{aditya@stat.berkeley.edu}.}}
\date{}
\maketitle

\begin{abstract}
	We develop a technique for establishing lower bounds on the sample complexity of Least Squares (or, Empirical Risk Minimization) for large classes of functions. As an application, we settle an open problem regarding optimality of Least Squares in estimating a convex set from noisy support function measurements in dimension $d\geq 6$. Specifically, we establish that Least Squares is mimimax \textit{sub-optimal}, and achieves a rate of $\tilde{\Theta}_d(n^{-2/(d-1)})$ whereas the minimax rate is $\Theta_d(n^{-4/(d+3)})$.
\end{abstract}

\paragraph{keywords}
	Non-parametric statistics, regression, support function, ERM, Least squares, non-Donsker regime

\section{Introduction and main results}
Consider the problem of regression where the goal is to estimate a function $f^* : \mathcal{X} \rightarrow \R $  from observations $(X_1, Y_1), \ldots, (X_n, Y_n)$ drawn according to the model
\begin{equation*}
Y_i = f^*(X_i) + \xi_i \qt{for $i = 1, \dots, n$}
\end{equation*}
where $X_1, \dots, X_n$ are design points (fixed or random) and $\xi_1, \dots, \xi_n$ are i.i.d random variables with mean zero.  Assume that the unknown function $f^*$ belongs to a known \emph{convex} class of functions $\mathcal{F}$.
The most natural and basic estimator in this setting is the Least Squares Estimator (LSE)
\begin{equation*}
\hat{f}_n \in \argmin_{f \in \mathcal{F}} \sum_{i=1}^n \left(Y_i - f(X_i) \right)^2,
\end{equation*}
which is also the Maximum Likelihood Estimator (MLE) under Gaussian noise. It is customary to evaluate the performance of $\hat{f}_n$ via the risk
\begin{equation}\label{fdloss}
\|\hat{f}_n - f^*\|^2_{\PP_n} :=  \frac{1}{n} \sum_{i=1}^n \left(\hat{f}_n(X_i) - f^*(X_i) \right)^2
\end{equation}
in the fixed-design setting where $X_1, \dots, X_n$ are assumed to be non-random points in $\mathcal{X}$, and via
\begin{equation}\label{rdloss}
\|\hat{f}_n - f^*\|^2_{\PP} := \int_{\mathcal{X}} \left(\hat{f}_n(x) - f^*(x) \right)^2 d\PP(x)
\end{equation}
in the random design setting where $X_1, \ldots, X_n \overset{i.i.d}{\sim} \PP$. We shall focus on the optimality of the LSE as measured in the minimax sense (see e.g., \cite{tysbakovnon}) via the worst-case risk
\[
\Ri_{\PP_n}(\hat{f}_n,\F) := \sup_{f^* \in \F}\E_{f^*} \|\hat{f}_n - f^*\|_{\PP_n}^2 ~~~ \text{ or } ~~~ \Ri_{\PP}(\hat{f}_n,\F) := \sup_{f^* \in \F}\E_{f^*} \|\hat{f}_n - f^*\|_{\PP}^2,
\]
in the fixed and random designs, respectively.

The accuracy of the LSE is one of the most basic questions in statistics \citep{van2000empirical,birge1993rates,koltchinskii2011oracle,van1996weak}. Typical results impose conditions on the metric entropy on (natural subsets of) the class $\mathcal{F}$. We shall denote the $\epsilon$-metric entropy of a class $\mathcal{G}$ of functions under the $L^2(\mathbb{Q})$ pseudometric by $\log \Ncal(\epsilon, \mathcal{G}, \mathbb{Q})$.
Here $\Ncal(\epsilon, \mathcal{G}, \mathbb{Q})$ is the minimal cardinality of a set $\mathcal{N}_{\epsilon}$ of functions such that for any $g\in\mathcal{G}$ there exists a $g'\in\mathcal{N}_{\epsilon}$ with $\|g-g'\|_{\mathbb{Q}} \leq \epsilon$.

It is convenient to isolate the existing results on the LSE into two categories depending on whether the class of functions $\mathcal{F}$ is in the \textit{Donsker} regime or in the \textit{non-Donsker} regime. By the Donsker (or, more precisely, $\mathbb{P}$-Donsker) regime, we mean that the $L^2(\mathbb{P})$ metric entropy of natural totally bounded subsets of $\mathcal{F}$ grows as $\epsilon^{-p}$ for some $p < 2$.\footnote{In this section, for brevity we may omit constants that may depend on $p$.} In contrast, for the non-Donsker regime, the entropy grows as $\epsilon^{-p}$ for some $p > 2$.

It should be noted that the two regimes can often occur in different settings of the same general problem. For example, the class of support functions of compact, convex subsets of $\R^d$ is Donsker for $d \leq 4$ and non-Donsker for $d \geq 6$. We shall revisit this example in detail in Section \ref{suppest}.

In the Donsker regime, it is well-known that the LSE achieves the rate $n^{-2/(2+p)}$, which is the minimax rate of convergence, under minimal assumptions \citep{barron1999risk}. Thus, the LSE is minimax optimal when the class $\mathcal{F}$ is Donsker with respect to $\mathbb{P}$ or $\mathbb{P}_n$. In contrast, the minimax optimality of the LSE in the non-Donsker regime remains unresolved. In a fundamental paper, \cite{birge1993rates} proved that in the non-Donsker regime, the rate of convergence of the LSE is bounded from above by $n^{-1/p}$. However, it is also well-known (see e.g., \cite{yang1999information}) that the minimax rate of estimation is still $n^{-2/(2+p)}$.

It was first observed in \citep[Section 4]{birge1993rates} and later in \cite{birge2006model} that it is possible to design ``pathological'' function classes $\mathcal{F}$ where the LSE provably achieves a risk of $\Tilde{\Theta}(n^{-1/p})$. However, for a general non-Donsker class $\mathcal{F}$, the fundamental question of whether the rate of convergence of the LSE is $n^{-1/p}$ or $n^{-2/(2+p)}$ (or some intermediate rate) is unresolved.

Some important progress on this open problem has been made in the recent papers \citep{kur2019optimality,han2019global,carpenter2018near,han2019isotonic}. Specifically, these papers have shown that there exist ``natural'' non-Donsker families of functions (including the class of bounded convex functions on a smooth domain in $\R^d$ for $d \geq 3$, the class of multivariate Isotonic functions over $\R^d$ for $d \geq 2$, etc.) where the LSE achieves the minimax rate of $n^{-2/(2+p)}$, in contrast to the pessimistic upper bound of $n^{-1/p}$.

In this paper, we give a recipe for establishing a lower bound for the LSE's risk for convex families of functions in the \emph{non}-Donsker regime both in fixed and random design. As an application, we complement the aforementioned recent results by proving that there also exist other ``natural'' non-Donsker families of functions (such as the class of support functions of compact convex subsets of $\R^d$ for $d \geq 6$) where the LSE cannot achieve a rate faster than $n^{-1/p}$, up to logarithmic multiplicative factors. In other words, for these non-Donsker classes, the LSE is provably \textit{suboptimal}.

We start by stating assumptions that imply sub-optimality of LSE in a fixed design. Then, we extend these assumption to the random design setting. These assumptions will be verified for the case of support functions in Section~\ref{suppest}.

Throughout, we assume that $\mathcal{F}$ is a \emph{convex} family of functions.
Also, in the remainder of the paper, we assume for simplicity that $\xi \sim N(0,1)$; see Remark \ref{Remark1} for more general assumptions on the noise. We employ the notation $a\lesssim b$ to mean inequality up to a constant that may depend on $p$. Let
$$B_{\PP_n}(f_0, t) := \left\{f \in \mathcal{F} : \|f - f_0\|_{\PP_n} \leq t \right\}$$ and for a set of functions $\mathcal{G}$ on $\mathcal{X}$, the Gaussian width of $\mathcal{G}$ is defined, conditionally on $X_1,\ldots,X_n$, as
\begin{equation}\label{Eq:GWdef}
\GW(\mathcal{G}) := \E \sup_{f \in \mathcal{G}} \frac{1}{n}
\sum_{i=1}^n g_i  f(X_i),
\end{equation}
where $g_1,\ldots,g_n$ are i.i.d. $N(0,1)$.

We are now ready to state our key structural assumptions.
\paragraph{Assumptions: Fixed design} Let $p > 2$  and $n \gtrsim 1$. Assume there are two functions $f_0,f_{(n)} \in \Fcal$ such that for some $\beta, \gamma \geq 0$,
\begin{equation}\label{A21}
\log \Ncal(\epsilon, B_{\PP_n}(f_0,2\epsilon), \PP_n) \gtrsim \epsilon^{-p} \quad   \forall~ \epsilon  \gtrsim n^{-1/p}\log(n)^{\gamma}.
\end{equation}
Furthermore, suppose
\begin{equation}\label{A31}
\|f_{(n)} - f_0\|_{\PP_n} \lesssim n^{-\frac{1}{2p}}\log(n)^{-s_{p,\gamma}},
\end{equation}
where $s_{p,\gamma} = \frac{\gamma}{2}(\frac{p}{2}-1)$, and either
\begin{equation}\label{A41}
\log \Ncal(\epsilon, B_{\PP_n}(f_{(n)}, t), \PP_n) \lesssim \sqrt{n}\log(n)^{p \cdot s_{p,\gamma}}\left(\log \frac{1}{\epsilon} \right)^{\beta} \left(\frac{t}{\epsilon} \right)^p
\end{equation}
for every $ n^{-\frac{1}{p}}\log (n)^{-s_{p,\gamma}} \lesssim \eps \leq t \lesssim n^{-\frac{1}{2p}} \log (n)^{-\frac{\beta}{p} -\frac{3s_{p,\gamma}}{2}}$ or a weaker condition
\begin{align}
\label{eq:weaker_cond}
\GW(B_{\PP_n}(f_{(n)}, t)) \lesssim n^{-\frac{1}{2p}}\log(n)^{\frac{\beta}{p} + s_{\gamma,p}}t,
\end{align}
for some $t \lesssim n^{-\frac{1}{2p}} \log (n)^{-\frac{\beta}{p} -\frac{3s_{p,\gamma}}{2}}$ holds.

The following theorem establishes that the rate of convergence of the LSE equals $n^{-1/p}$, up to a poly-logarithmic multiplicative factor, under the aforementioned assumptions.
\begin{theorem}\label{Thm:LowerBirgeMassartFixed}
	Assume that $\mathcal{F}$ is a convex class of functions satisfying \eqref{A21}, \eqref{A31}, and either \eqref{A41} or \eqref{eq:weaker_cond} holds for some $p > 2$ and $n \gtrsim 1$. Then the following holds:
	\begin{equation*}
	\mathcal{R}_{\PP_n}(\hat{f}_n, \F) \gtrsim n^{-\frac 1p}\log(n)^{-\frac{2\beta}{p} -3s_{p,\gamma}}.

	\end{equation*}
\end{theorem}
We shall next extend Theorem \ref{Thm:LowerBirgeMassartFixed} to the case of random design, where the design points $X_1, \dots, X_n$ are independent with common distribution $\PP$. It is sufficient for our purposes to establish near-isometry: with high probability,
\begin{equation}\label{Eq:Distortion}
\begin{aligned}
\forall f,g\in\F,~~~ \frac{1}{2}\|f-g\|_{\PP_n} - d_n \leq \|f-g\|_{\PP} \leq  2\|f-g\|_{\PP_n} + d_n

\end{aligned}
\end{equation}
for some remainder $d_n$ that decays to zero with increasing $n$. In the case of uniformly bounded functions, sufficient conditions for the two-sided inequality \eqref{Eq:Distortion} can be found in the literature on local Rademacher averages (see e.g., \citep{bousquet2002concentration,bartlett2005local}), while the right-hand side of \eqref{Eq:Distortion} holds under weaker conditions \citep{koltchinskii2013bounding,mendelson2014learning,mendelson2017aggregation}. For the purpose of proving lower bounds for random design, however, we need the more demanding left-hand side of \eqref{Eq:Distortion}. Hence, we shall assume that functions in $\Fcal$ are uniformly bounded.

In addition, we assume the growth of Koltchinskii-Pollard entropy
\begin{equation}\label{A1}
\sup_{n \in \mathbb{N}}\sup_{{\mathbb Q} \in \mathcal{P}_n}\log \mathcal{N}(\epsilon,\F,{\mathbb Q})   \lesssim \epsilon^{-p}
\end{equation}
where $\mathcal{P}_{n}$ denotes the set of all probability measures supported on finite subsets of $\mathcal{X}$ of cardinality at most $n$. Under this assumption, with high probability $d_n \lesssim(\log n)^{2} n^{-1/p}$  \citep{rakhlin2017empirical}. This will allow us to reduce the random design setting to a fixed design and use Theorem \ref{Thm:LowerBirgeMassartFixed}, since the remainder $(d_n)^2$ is of the lower order than $n^{-1/p}$.\footnote{For some families of functions it might be possible to relax the additional assumptions of uniform boundedness and \eqref{A1} and achieve a similar result to Corollary \ref{Thm:LowerBirgeMassartRandom}, see for example \cite{KurConv}}

To establish a lower bound for LSE in random design, we may verify that above assumptions \eqref{A21}, \eqref{A31}, \eqref{A41} hold with high probability for random measures $\PP_n$ and employ near-isometry for the distance between LSE and the regression function. Alternatively, it may be easier to verify the corresponding assumptions in the population. We now state this latter approach.

First, recall that bracketing number $\Ncal_{[]}(\epsilon, \mathcal{G}, \PP)$ is the minimal cardinality of a set $\mathcal{N}_{[],\epsilon}$ of pairs of functions $(g^{-},g^{+})$ such that $\|g^{+}-g^{-}\|_{\PP} \leq \epsilon$, and for any $g \in \mathcal{G}$ there exists $(g^{-},g^{+}) \in  \mathcal{N}_{[],\epsilon}$ such that $g^{-} \leq g \leq g^{+}.$

\paragraph{Assumptions: Random design} Let $p > 2$. Assume there exists a function $f_0 \in \Fcal$ such that for every integer $m \gtrsim 1$, there exists $f_{(m)} \in \mathcal{F}$
such that
\begin{equation}\label{A2}
\log \Ncal(\epsilon, B_{\PP}(f_0,2\epsilon), \PP) \gtrsim \epsilon^{-p} \quad   \forall \epsilon  \geq  0
\end{equation}
and
\begin{equation}\label{A3}
\|f_{(m)} - f_0\|_{\PP} \lesssim m^{-\frac{1}{p}}.
\end{equation}
Furthermore, for some $\beta \geq 0$
\begin{equation}\label{A4}
\log \Ncal_{[]}(\epsilon, B_{\PP}(f_{(m)}, t), \PP) \lesssim m \left(\log \frac{1}{\epsilon} \right)^{\beta} \left(\frac{t}{\epsilon} \right)^p,
\end{equation}
for every $ 0< \epsilon \leq t \lesssim \log(m)^{-\beta/p}m^{-1/p}$.

We remark that assumption \eqref{A2} is satisfied for non-Donsker classes of functions: see \cite[Lemma 3]{yang1999information} for the proof of existence.

The following is our lower bound for the random-design setting:
\begin{corollary}\label{Thm:LowerBirgeMassartRandom}
	Assume that $\F$ is a convex class of uniformly bounded functions satisfying \eqref{A1}, \eqref{A2}, \eqref{A3}, and \eqref{A4} for some $p>2$ and $n\gtrsim 1$. Then
	\begin{equation*}
	\mathcal{R}_{\PP}(\hat{f}_n, \F) \gtrsim n^{-\frac 1p}\log(n)^{-\frac{2\beta}{p} -3(\frac{p}{2}-1)}.
	\end{equation*}
\end{corollary}

\subsection{The ideas behind our assumptions}

Assumption \eqref{A2} says that the function $f_0$ is ``complex'' in that its local neighborhood is as complex as the entire function class $\mathcal{F}$ when $\log\Ncal(\epsilon,\F,\PP) \sim \epsilon^{-p}$.
The assumption \eqref{A3} states that $f_0$ is approximated by $f_{(m)}$ up to the accuracy $m^{-1/p}$ for every $m$. The assumption \eqref{A4} captures the ``simplicity'' of the functions $f_{(m)}$ in relation to the complex function $f_0$ satisfying \eqref{A2}. Note that when $t = O(\epsilon)$, the right hand side of \eqref{A4} is logarithmic in $\epsilon$ (assuming that $m$ is not too large) while the right hand side of \eqref{A2} is polynomial in $1/\epsilon$. Thus the local neighborhood of $f_{(m)}$ is smaller than that of $f_0$ and in this sense $f_{(m)}$ is simpler than $f_0$. Note also that there is a factor of $m$ on the right hand side of \eqref{A4} which means that the complexity of the functions $f_{(m)}$ increases with $m$.

There exist natural non-Donsker function classes $\mathcal{F}$ which satisfy \eqref{A2}, \eqref{A3} and \eqref{A4}. In Section \ref{suppest}, we show that the class of support functions of compact convex sets in $\R^d$ satisfy these assumptions with $f_0$ being the support function of the unit ball and $f_{(m)}$ the support function of a regular polytopal approximation to the unit ball with $m$ vertices.

The proof of Theorem \ref{Thm:LowerBirgeMassartFixed} will reveal that $\hat{f}_n$ achieves the rate $n^{-1/p}$ (up to logarithmic factors) when the regression function is in the class $\{f_{(m)}, m \geq 1\}$. In fact, the specific function achieving the rate $n^{-1/p}$ is $f^*=f_{(m)}$ for $m \sim \sqrt{n}$. It is interesting to note that for $m \sim \sqrt{n}$ and $t^2 \sim n^{-1/p}$, the local neighborhood $B_{\PP_n}(f_{(m)}, t)$ has the same metric entropy as the right hand side of \eqref{A2}. Our main technical insight is that the sub-optimality occurs at a function $f^*=f_{(m)}$ instead of perhaps a more natural candidate function such as $f_0$ (we actually believe that the rate at $f_0$ may be equal to $n^{-2/(2+p)}$).

\subsection{Discussion: the non-Donsker regime, revisited}

From the recent results on families in the non-Donsker regime \citep{kur2019optimality,han2019global,carpenter2018near,KurConv,han2019isotonic} and the present results, the LSE may be optimal or sub-optimal in the non-Donsker regime for natural classes of functions, even if uniformly bounded. These results also indicate that LSE achieves a risk that equals to the Gaussian complexity of the class, up to a constant that depends on dimension. Namely, in contrast to the Donsker regime, there is no localization. In the problem of convex regression with uniformly bounded functions and  \emph{Euclidean ball} as domain, as well as in multiple isotopic regression, the minimax rate equals to the Gaussian complexity of the family. In contrast, by Theorem \ref{Cor:SuppRandom}, for support function regression and for convex uniformly bounded regression (or Lipshitz-convex regression) with support on the \emph{cube} \citep{KurConv}, the Guassian complexity differs from the minimax rate.

\section{Application: Sub-optimality of Least Squares for estimating a convex set from noisy support function measurements}\label{suppest}
In this section, we shall use Corollary  \ref{Thm:LowerBirgeMassartRandom} to resolve a long-standing open problem on the sub-optimality of the least squares estimator in the problem of estimating a convex set in dimension $d\geq6$ from noisy support function measurements, see for example \citep{gardner2006convergence,brunel2016adaptive,brunel2013adaptive,brunel2018estimation,guntuboyina2012optimal,fisher1997estimation,balazs2015near,soh2019fitting}. Let us first recall that the support function $h_K: \Sd \rightarrow \R$ of a compact convex set $K$ in $\R^d$ is defined as
\begin{equation*}
h_K(u) = \max_{x \in K} \left<x, u \right> \qt{for $u \in \Sd := \left\{u : \|u\| = 1 \right\}$}.
\end{equation*}
The support function uniquely determines the compact convex set $K$ and is a fundamental object in convex geometry (see, for example, \cite[Section 1.7]{schneider2014convex} or \cite[Section 13]{rockafellar1970convex}). Consider now the problem of estimating an unknown compact, convex set $K^*$ from observations $(X_1, Y_1), \dots, (X_n, Y_n)$ drawn according to the model:
\begin{equation*}
Y_i = h_{K^*}(X_i) + \xi_i \qt{for $i = 1, \dots n$}
\end{equation*}
where $X_1, \dots, X_n$ are design points (fixed or random) and $\xi_1, \dots, \xi_n$ are i.i.d. $N(0,1)$. Recovery of $K^*$ is a fundamental problem in geometric tomography \citep{prince1990reconstructing,gardner1995geometric}. The natural estimator in this problem is the least squares estimator defined by
\begin{equation*}
\hat{K}_n \in \argmin_{K \in \mathcal{C}} \sum_{i=1}^n \left(Y_i - h_K(X_i) \right)^2
\end{equation*}
where $\mathcal{C}$ denotes the class of all compact, convex sets in $\R^d$. Basic properties and algorithms for computing $\hat{K}_n$ can be found in \citep{prince1990reconstructing,lele1992convex} and \citep{kiderlen2008new}. Rigorous accuracy results for $\hat{K}_n$ as an estimator of $K^* \subset B_d$ (here $B_d$ denotes the unit-Euclidean ball) were proved in \citep{gardner2006convergence}. Specifically, \cite[Corollary 5.7]{gardner2006convergence} proved that, under the fixed design setting of any $X_1,\ldots,X_n$ (fixed points) that form a well-separated set, (i.e. a set of $n$ points on the unit-sphere that are at least $c(d)n^{-\frac{1}{d-1}}$ far from each other),
\begin{equation}\label{gardub}
\|h_{\hat{K}_n} - h_{K^*}\|_{\PP_n}^2 = O_P(\beta_n) \quad \text{ where }
\beta_n =
\begin{cases}
n^{-4/(d+3)} & \text{for } d = 2, 3, 4 \\
n^{-4/(d+3)} \cdot \log n       & \text{for } d = 5 \\
n^{-2/(d-1)} & \text{ for } d \geq 6.
\end{cases}
\end{equation}
Complementarily, \cite{guntuboyina2012optimal} proved that the minimax rate of estimation in this problem (under the same fixed design version of the problem and the $\|\cdot\|_{\PP_n}$ loss function) equals $\Theta_d(n^{-4/(d+3)})$ for all $d \geq 2$. These two results combined imply that the least squares estimator $\hat{K}_n$ is minimax optimal for $d = 2, 3, 4$ and nearly minimax optimal (up to the logarithmic multiplicative factor $\log n$) for $d = 5$. However, there is a gap between the upper bound $n^{-2/(d-1)}$ on the rate of convergence of the least squares estimator \eqref{gardub} and the minimax rate $n^{-4/(d+3)}$ for $d \geq 6$. This gap has remained open since the paper \cite{gardner2006convergence} where it was suggested that the upper bound is accurate and that the least squares estimator is indeed minimax \emph{suboptimal} for $d \geq 6$. The goal of this section is to confirm the conjecture of \cite{gardner2006convergence}.

Specifically, we use Corollary  \ref{Thm:LowerBirgeMassartRandom} to prove that the LSE is suboptimal for $d \geq 6$, in the sense that there exist sets  for which the rate of convergence for LSE is bounded from below by $n^{-2/(d-1)}$ up to a logarithmic multiplicative factor. Moreover, in this result, $f_0$ will be the $d-$dimensional ball, and the sets $\{K_{m}\}_{m=d+1}^{\infty} \subset \mathcal{C}$ will be ``regular'' polytopes that form an optimal approximation to the ball with $m \geq d+1$ vertices (see Lemma \ref{Lem:Regu} for more details).

\begin{corollary}\label{Cor:SuppRandom}
	Let $d \geq 6$. Suppose $X_1, \dots, X_n \sim \PP,$ where $\PP$ is the uniform distribution\footnote{Or for any density $g(x)$ on the sphere, such that $g(x) \geq c_1$ for all $x \in \Sd$.} on $\Sd$. There exist a positive constants, $C_d$, $\gamma_d$ depending only on $d$ such that
	\begin{equation*}
	\sup_{K^* \in \mathcal{C}(1)} \E_{K^*} \|h_{\hat{K}_n} - h_{K^*}\|^2_{\PP}  \geq C_d n^{-2/(d-1)}\log(n)^{-\gamma_d},
	\end{equation*}
	where $\mathcal{C}(1)$ is the set of all compact convex sets that are contained in the unit Euclidean ball in $\mathbb{R}^d$.
\end{corollary}
Observe that here the LSE in not restricted to $\mathcal{C}(1)$, i.e. $h_{\hat{K}_n}$ can return any convex set in $\R^d$.

Finally, the proof of the above corollary can be modified to hold for any fixed design of $n$ well-separated points. The modification will follow from the fact that $n$ well-separated points are a discrete approximation to the uniform measure on the sphere. Therefore, we settle the question in \citep{gardner2006convergence}.

\paragraph{Acknowledgments}
The first and second authors acknowledge the support from NSF under award DMS-1953181, and from the Center for Minds, Brains and Machines (CBMM) funded by NSF award CCF-1231216. The third author is supported by NSF CAREER Grant DMS-1654589. We also acknowledge the anonymous referees for their useful comments.

\section{Proofs}

\paragraph{Notation}
Throughout this text, $c,C$ with subscripts are positive absolute constants that do not depend on the dimension $d$. Additionally, positive  constants  that only depend on the dimension or on $p$ are explicitly denoted, respectively, by $c(d),C(d),c(p), C(p)$. These constants may change from line to line, and from section to section. $B_d$ denotes the unit Euclidean ball in $\R^d$. $\Tilde{O}(\cdot),\Tilde{\Omega}(\cdot)$ denotes behavior up to logarithmic factors of ($n$ or $\epsilon$).

\subsection{Proof of Theorem \ref{Thm:LowerBirgeMassartFixed}}
Our main technical tool is the following important result of \cite{chatterjee2014new} which gives sharp upper and lower bounds for the accuracy of an LSE over a convex family of functions in the fixed-design setting. We use the following notation in this result.

\begin{theorem}[ Theorem 1.1 \cite{chatterjee2014new}]\label{chat}
	Let $\F$ be a convex family of functions and consider the LSE for the fixed design setting. Let
	\begin{equation}\label{chat.t}
	t_f := \argmax_{t \geq 0}H_f(t)\qt{ where $H_f(t) := \GW(B_{\PP_n}(f,t)) - \frac{t^2}{2}$}.
	\end{equation}
	Then, $t_f$ is unique, $H_{f}(\cdot)$ is a concave function, and  we have
	\begin{equation}\label{Eq:SouarvBd}
	\P \left\{0.5t_f^2\leq \|\hat{f}_n - f\|^2_{\PP_n}  \leq 2t_f^2 \right\} \geq 1 - 3p_n,
	\end{equation}
	where $p_n = \exp \left(-c n t_f^2 \right)$.
\end{theorem}
\begin{remark}\label{Remark1}
	Based on the proof of \cite[Thm 1.1]{chatterjee2014new}, the assumption on $g = (g_1,\ldots,g_n) \sim N(0,I_{n \times n})$ can be relaxed to any isotropic random vector that satisfies a convex Lipshitz concentration inequality \citep{adamczak2015note,boucheron2013concentration}.  Also, the same result for an isotropic log-concave noise with $p_n= \exp \left(-c \sqrt{n} t_f^2 \right)$ follows from the recent result of \cite{lee2018stochastic}, which is a concentration inequality for Lipshitz functions for isotropic log-concave distributions. Finally, we remark that for zero-mean $\xi$ with variance $\sigma^2$, all our results scale by $\sigma^2$.
\end{remark}
The proof of Theorem \ref{Thm:LowerBirgeMassartFixed} is reduced to the following ``two points'' lemma that is mainly based on Theorem \ref{chat}. The notation $f_{(n)}$ is to emphasize the fact that $f_{(n)}$ is a function that is chosen based on the number of samples.
\begin{lemma}\label{Lem:Twoptsfixed}[Lower bound for fixed design]
	Let $f_0,f_{(n)} \in \F$, and $r_n \geq Cn^{-1/4},\delta_n,w_n,s_n$ be positive constants. Also, let $w_n' = \max\{\frac{r_n^2}{8\delta_n},w_n\} $, and assume the following:
	\begin{itemize}

		\item $ \GW(B_{\PP_n}(f_0,s_n))\geq r_n^2 $
		\item $\|f_{(n)}-f_0\|_{\PP_n} \leq \delta_n$,  and $ r_n \leq 2\delta_n$,
		$s_n \leq \delta_n$.
		\item $\GW(B_{\PP_n}(f_{(n)},t)) \leq w_n't$~ for some ~$ t \leq \frac{r_n^4}{16\delta_n^2w_n'}$.

	\end{itemize}
	Then, when $Y_i = f_{(n)}(x_i) + \xi_i$, the following holds with high probability
	\begin{equation*}
	\|\hat{f}_n - f_{(n)}\|^2_{\PP_n} \geq c \cdot
	\min\left\{\frac{r_n^8}{\delta_n^4w_n^2},\frac{r_n^4}{\delta_n^2}\right\}.
	\end{equation*}
\end{lemma}
\begin{proof}[Proof of Lemma \ref{Lem:Twoptsfixed}]
	By Theorem \ref{chat}, it is enough to show that $t_{f_{(n)}}$ is greater than $\frac{r_n^4}{16\delta_n^2w_n}$. Namely, the  functional $H_{f_{(n)}}(\cdot)$ attains its unique maximum on a $t_{f_{(n)}} \geq \frac{r_n^4}{16\delta_n^2w_n}$. First, using the second assumption and the upper bound on $\delta_n$, we see that
	\[
	B_{\PP_n}(f_0, s_n) \subseteq B_{\PP_n}(f_{(n)}, \|f_{(n)}-f_0\|_{\PP_n}+ s_n) \subseteq B_{\PP_n}(f_{(n)}, 2\delta_n).
	\]
	By the convexity of $\F$, the function $t\mapsto \GW(B_{\PP_n}(f_{(n)},t))/t$ is nonincreasing. Therefore, by the first assumption and the above inclusion, for all $t \leq 2\delta_n$
	\[
	\GW(B_{\PP_n}(f_{(n)},t)) \geq \frac{r_n^2}{2\delta_n}t.
	\]
	Now, by the last equation and the second assumption, we know that for $t_1 = \frac{r_n^2}{2\delta_n} \leq 2\delta_n$
	\begin{align*}
	H_{f_{(n)}}(\frac{r_n^2}{2\delta_n}) &= \GW(B_{\PP_n}(f_{(n)},\frac{r_n^2}{2\delta_n})) - \frac{\left(\frac{r_n^2}{2\delta_n}\right)^2}{2}
	\geq \frac{r_n^2}{2\delta_n} \cdot \left(\frac{r_n^2}{2\delta_n}\right) - \frac{\left(\frac{r_n^2}{2\delta_n}\right)^2}{2} \geq \frac{r_n^4}{8\delta_n^2}.
	\end{align*}

	Finally, by the last assumption, we know that for $t_2 = \frac{r_n^4}{16\delta_n^2w_n'} < t_1$ the following holds:
	\[
	H_{f_{(n)}}(\frac{r_n^4}{16\delta_n^2w_n'}) \leq \GW(B_{\PP_n}(f_{(n)}, \frac{r_n^4}{16\delta_n^2w_n'})) \leq w_n'\frac{r_n^4}{16\delta_n^2w_n'} = \frac{r_n^4}{16\delta_n^2}.
	\]
	Since $H_{f_{(n)}}(\cdot)$ is concave in $ t$, we conclude by
	the last two equations that $ t_{f_{(n)}} \geq \frac{r_n^4}{16\delta_n^2w_n'}$ and the claim follows from Theorem \ref{chat}.
\end{proof}

In addition to Lemma \ref{Lem:Twoptsfixed}, we need the following two standard facts (which can be found, for example, in \cite{koltchinskii2011oracle}) to prove Theorem \ref{Thm:LowerBirgeMassartFixed}.

\begin{lemma}[Sudakov Minoration]\label{Lem:sud}
	There exists a universal positive constant $C$ such that the following holds for any class $\F$ of real-valued functions:
	\begin{equation*}
	\GW(\F) \geq  \frac{C}{\sqrt{n}} \sup_{\epsilon > 0}
	\left\{\epsilon \sqrt{\log \Ncal(\epsilon,\F, \PP_n)} \right\}.
	\end{equation*}
\end{lemma}
\begin{lemma}[Dudley Integral]\label{Lem:Dud}
	There exists a universal positive constant $C$ such that the following holds for any class $\F$ of real-valued functions:
	\begin{equation*}
	\GW(\F) \leq C\inf_{\epsilon > 0} \left(\epsilon + \frac{1}{\sqrt{n}}\int_{\epsilon}^{\mathrm{diam}(\F,\PP_n)/2}
	\sqrt{\log \Ncal(u,\F, \PP_n)}du\right),
	\end{equation*}
	where $\mathrm{diam}(\F,\PP_n)$ is the diameter of $\F$ with respect to $L^2(\PP_n)$.
\end{lemma}
\begin{proof}[Proof of Theorem \ref{Thm:LowerBirgeMassartFixed}]
	We aim to apply Lemma \ref{Lem:Twoptsfixed}. In order to satisfy its first assumption, we need to estimate the Gaussian width of $B_{\PP_n}(f_0, C_3n^{-1/p}\log(n)^{\gamma})$. By Lemma \ref{Lem:sud} and Eq. \eqref{A2}
	\begin{equation}\label{Eq:51}
	\begin{aligned}
	\GW(B_{\PP_n}(f_0, C_3n^{-1/p}\log(n)^{\gamma})) &\geq \frac{C}{\sqrt{n}} \sup_{\epsilon > C_1n^{-1/p}\log(n)^{\gamma}}
	\left\{\epsilon \sqrt{\log \Ncal(\epsilon,B_{\PP_n}(f_0, C_3n^{-1/p}\log(n)^{\gamma},\PP_n)} \right\} \\&\geq  \frac{c_2}{\sqrt{n}}n^{-\frac{1}{p}}\log(n)^{\gamma}\sqrt{\log \Ncal(\epsilon,B_{\PP_n}(f_0, C_3n^{-1/p}\log(n)^{\gamma}),\PP_n)} \\&\geq c_3(p)n^{-\frac{1}{p}}\log(n)^{-\gamma(\frac{p}{2}-1)}.
	\end{aligned}
	\end{equation}
	Now, we aim to upper bound $\GW(B_{\PP_n}(f_{(n)},t))$ when
	$$   t = c_1(p)n^{-\frac{1}{2p}} \log (n)^{-\frac{\beta}{p} -\frac{3\gamma}{2}(\frac{p}{2}-1)},$$
	for some suitable $c_1(p)$. By using  Lemma \ref{Lem:Dud}, and Eq. \eqref{A3}, we see that
	\begin{equation}\label{Eq:blablabla}
	\begin{aligned}
	\GW(B_{\PP_n}(f_{(n)},t)) &\leq C\inf_{\epsilon >0} \left(\epsilon + \frac{1}{\sqrt{n}}\int_{\epsilon}^{t}\sqrt{\log\Ncal(u,B_{\PP_n}(f_{(n)}, t),\PP_n)}du\right)
	\\& \leq C\inf_{\epsilon >0 } \left(\epsilon + \frac {C_2(p)}{\sqrt{n}}\int_{\epsilon}^{t}\left(\frac{tn^{\frac 1{2p}}\log(n)^{\frac{\gamma}{2}(\frac{p}{2}-1)}\log(u^{-1})^{\frac{\beta}{p}}}{u}\right)^{\frac p2}du\right)
	\\& \leq C\inf_{\epsilon >0} \left(\epsilon + \frac {C_3(p)}{\sqrt{n}}\left(\frac{tn^{\frac 1{2p}}\log(\epsilon^{-1})^{\frac{\beta}{p}}\log(n)^{\frac{\gamma}{2}(\frac{p}{2}-1)}}{\epsilon}\right)^{\frac p2}\epsilon\right)
	\\&\leq C_4(p)n^{-\frac{1}{2p}}\log(n)^{\frac{\beta}{p} + \frac{\gamma}{2}(\frac{p}{2}-1)}t,
	\end{aligned}
	\end{equation}
	where we used the fact that $p > 2$ and set $$\epsilon =   C_1(p)n^{-\frac{1}{2p}}\log(n)^{\frac{\beta}{p} + \frac{\gamma}{2}(\frac{p}{2}-1)}t = C_2(p)n^{-\frac{1}{p}}\log(n)^{-\gamma(\frac{p}{2} -1 )} .$$ Hence, it is enough to assume \eqref{eq:weaker_cond} in place of \eqref{A41}.  Finally, we can apply Lemma \ref{Lem:Twoptsfixed} with the following parameters:
	$$ \|f_{(n)} - f_0\|_{\PP_n} \leq c_1(p)n^{-\frac{1}{2p}}\log(n)^{-\frac{\gamma}{2}(\frac{p}{2}-1)} =: \delta_n,$$
	where we used Eq. \eqref{A41}. Also, we set $s_n =  C_5(p)n^{-1/p}\log(n)^{\gamma}$,
	$$r_n^2 =  \min\{c_3(p),c_1(p)/8\}n^{-\frac{1}{p}}\log(n)^{-\gamma(\frac{p}{2}-1)}$$ and $$w_n =C_4(p) n^{-\frac{1}{2p}}\log(n)^{\frac{\beta}{p} + \frac{\gamma}{2}(\frac{p}{2}-1)}.$$ Therefore, Lemma \ref{Lem:Twoptsfixed} gives that
	\[
	\Ri_{\PP}(\hat{f}_n,\F) \geq c_5(p)\left(\frac{n^{-\frac{1}{p}}\log(n)^{-\gamma(\frac{p}{2}-1)}}{n^{-\frac{1}{2p}}\log^{\frac{\beta}{p} + \frac{\gamma}{2}(\frac{p}{2}-1)}(n)}\right)^2 \gtrsim n^{-\frac 1p}\log(n)^{-\frac{2\beta}{p} -3\gamma(\frac{p}{2}-1)},
	\]
	and the claim follows.
\end{proof}
\subsection{Proof of Corollary \ref{Thm:LowerBirgeMassartRandom}}\label{SectionThm}
For completeness, we state a consequence of \cite[Thm 5.11]{van2000empirical} (see Appendix for a proof).
\begin{lemma}\label{Lem:BMbound}
	Let $\cG$ be a family of functions uniformly bounded by one, and $\PP$ be some probability measure. For any $f \in \cG$ and $t \geq 0$, let
	$\varepsilon(f,t)$ be the stationary point of
	$$ \frac{1}{\sqrt{n}}\int_{\frac{\delta}{c}}^{t}\sqrt{\log\Ncal_{[]}(u, B_{\PP}(f,t),\PP)}du = \delta$$
	for some absolute constant $c > 0 $. Then, for any $\varepsilon \geq \varepsilon(f,t) $ the following holds with probability of at least $1-C\exp(-cn\varepsilon^2)$

	\[
	\GW(B_{\PP}(f,t)) \lesssim \varepsilon + n^{-1/2}.
	\]

\end{lemma}

\begin{proof}[Proof of Corollary~\ref{Thm:LowerBirgeMassartRandom}]
	First, we take $m = C(p)\sqrt{n}\log(n)^{\frac{p\gamma}{2}(\frac{p}{2}-1)}$ in \eqref{A3} and set $f_{(n)}:=f_{(m)}$. By using Eq. \eqref{Eq:Distortion} and the estimate $d_n \lesssim(\log n)^{2} n^{-1/p}$  from \citep{rakhlin2017empirical}, we see that with high probability,
	\[
	\|f_{(n)} - f_0\|_{\PP_n} \leq 2\|f_{(n)} - f_0\|_{\PP} + C\log^2(n)n^{-\frac{1}{p}} \lesssim n^{-\frac{1}{2p}}\log(n)^{\frac{\gamma}{2}(\frac{p}{2}-1)}.
	\]
	Thus Eq. \eqref{A31} holds for $f_{(n)}$.
	Next, by using Eq. \eqref{Eq:Distortion}, it is easy to see that Eq. \eqref{A21} hold with $\gamma = 2$. It remains to show that \eqref{eq:weaker_cond} holds.

	First, by Eq. \eqref{Eq:Distortion}, we know that for $t \geq Cd_n$ the following holds:
	\[
	\GW(B_{\PP_n}(f_{(n)},t)) \leq \GW(B_{\PP}(f_{(n)},2t + d_n))  \leq \GW(B_{\PP}(f_{(n)},4t)) .
	\]
	To estimate the last term, we use our bracketing assumption along with the uniform boundedness of functions in $\Fcal$. These assumptions let us apply Lemma \ref{Lem:BMbound} that yields an upper bound on this term. In order to upper bound $\varepsilon(f_{(n)},4t)$ (the fixed point of Lemma \ref{Lem:BMbound}), we use Eq. \eqref{A4} and derive that
	\begin{align*}
	\frac{1}{\sqrt{n}}\int_{\frac{\varepsilon}{c}}^{4t} \left(\frac{tn^{\frac 1{2p}}\log(n)^{\frac{\gamma}{2}(\frac{p}{2}-1)}\log(u^{-1})^{\frac{\beta}{p}}}{u}\right)^{\frac p2}du
	\lesssim \frac {1}{\sqrt{n}}\left(\frac{tn^{\frac 1{2p}}\log(n)^{\frac{\beta}{p}}\log(n)^{\frac{\gamma}{2}(\frac{p}{2}-1)}}{\varepsilon}\right)^{\frac p2}\varepsilon
	\end{align*}
	where in the last inequality we used the fact that $p > 2$ and $\varepsilon\geq 1/n$. Setting the right-hand side equal to $\varepsilon$, we find an upper bound on the fixed point
	$$ \varepsilon(f_{(n)},4t) \lesssim   n^{-\frac{1}{2p}}\log^{\frac{\beta}{p} + \frac{\gamma}{2}(\frac{p}{2}-1)}(n)t. $$
	We now set $t \sim n^{-\frac{1}{2p}} \log (n)^{-\frac{\beta}{p} -\frac{3s_{p,\gamma}}{2}}$ and apply Lemma \ref{Lem:BMbound} with $\varepsilon \sim n^{-1/p}\log(n)^{-\gamma (p/2-1)} $, concluding that with probability of at least $1-C\exp(-c\Tilde{\Omega}(n^{1-2/p}))$
	\[
	\GW(B_{\PP}(f_{(n)},4t)) \lesssim \varepsilon \sim n^{-\frac{1}{2p}}\log^{\frac{\beta}{p} + \frac{\gamma}{2}(\frac{p}{2}-1)}(n)t.
	\]
	Hence, all the assumptions of Theorem \ref{Thm:LowerBirgeMassartFixed} hold with high probability. Therefore, by Eq. \eqref{Eq:Distortion} and Theorem \ref{Thm:LowerBirgeMassartFixed}, we conclude that
	\begin{align*}
	\|\hat{f}_n - f^{*}\|_{\PP}^2 &\geq \frac{1}{4}\|\hat{f}_n - f^{*}\|^2_{\PP_n} - 2d_n^2 \geq \frac{1}{8}\|\hat{f}_n - f^{*}\|_{\PP_n}^2 \\&\gtrsim n^{-\frac 1p}\log(n)^{-\frac{2\beta}{p} -3\gamma(\frac{p}{2}-1)},
	\end{align*}
	and the claim follows.
\end{proof}
\subsection{Proof of Corollary \ref{Cor:SuppRandom}}
Throughout this subsection $\PP$ denotes the uniform measure on the sphere. In this proof we will use the following auxiliary lemmas:
\begin{lemma}[\cite{bronshtein1976varepsilon,dudley1999uniform}]\label{Lem:Bro}
	The following holds for all  $0 < \epsilon < 1 $,
	\[
	2^{-d}\epsilon^{-\frac{d-1}{2}}\leq \log\mathcal{N}_{2}\left(\epsilon,\C,\PP \right) \leq \log \mathcal{N}_{\infty}\left(\epsilon,\C,\PP\right)
	\leq Cd^{5/2} \epsilon^{-\frac{d-1}{2}},
	\]
	where $\log \mathcal{N}_{\infty}\left(\epsilon,\C,\PP\right)$ denotes covering with respect to $\|\cdot\|_{\infty}$.
\end{lemma}
\begin{lemma}[\cite{bronshtein1976varepsilon,dudley1999uniform}]\label{Lem:BroLower}
	Let $h_{B_d}$ be the support of function of the unit ball in $\R^d$, that is $h_{B_d} \equiv 1$.
	Then for any $0 \leq \epsilon \leq c$, there exists a set of cardinality $ M(\epsilon,d) \geq 2^{10^{-d}\epsilon^{-(d-1)/2}}$, denoted by $h_1,\ldots,h_{K_{M(\epsilon,d)}}$, that has the following properties:
	\begin{itemize}
		\item $\forall $ $1 \leq i < j \leq M(\epsilon,d)$: $ \|h_{K_i} - h_{K_j}\|_{\PP} \geq \epsilon 	$.
		\item $\forall $  $1 \leq i \leq M(\epsilon,d)$: $\|h_{K_i}-h_{B_d}\|_{\PP} \leq 8\epsilon$.
	\end{itemize}
\end{lemma}
\begin{definition}
	We say that $f: \R^d \to \R$ is a \emph{$k$-piecewise simplicial linear} if $f$ is a convex piecewise linear function and its support can be written as a union of $k$-simplicials, and  $f$ is linear in each of them.
\end{definition}
For the following lemma, let $\mathcal{P}_d$  be the regular simplex with $d+1$ faces that contains the unit Euclidean ball, with vertices at distance $d$ from the origin.
\begin{lemma}[Theorem 4.4 in \cite{KurConv} ]\label{Lem:convEnt}
	Let $\F(\Gamma,\mathcal{P}_d)$ be the family of all the convex functions that are uniformly bounded by $\Gamma > 0$, and their domain is a simplex.
	Let $f_k \in \F(\Gamma,\mathcal{P}_d)$ be $k$ piecewise simplicial linear. Then, the following bound holds for $0 \leq \epsilon \leq t$:
	\[
	\mathcal{N}_{[]}(\epsilon, B_{\mathrm{Unif}}(f_k,t),\mathrm{Unif}) \leq C(d)\left(t/\epsilon\right)^{d/2}\log^{d+1}\left(\eps^{-1}\right)\log(\Gamma)
	\]
	where $B_{\mathrm{Unif}}(f_k,t) \subset \F(M,\mathcal{P}_d)$ and $\mathrm{Unif}$ denotes the Lebesgue volume measure.
\end{lemma}

In order to prove Corollary \ref{Cor:SuppRandom}, we first prove that when we restrict the LSE to $\mathcal{C}(C_1 \cdot d)$ (here $C_1$ is some absolute constant) we achieve the desired bound:
\begin{lemma}\label{fr}
	For every $d \geq 6, n \geq C(d)$, the following holds
	\begin{equation}\label{fr.eq}
	\argmin_{K \in \mathcal{C}(C_1 \cdot d)} \sum_{i=1}^n \left(Y_i - h_K(X_i) \right)^2 \geq c(d)\log^{\gamma_d}(n)\nnt,
	\end{equation}
	whenever $K^{*} \in \C$.
\end{lemma}
Then, in Subsection \ref{Sec:reduc}, we prove that with high probability,
\[
\argmin_{K \in \mathcal{C}} \sum_{i=1}^n \left(Y_i - h_K(X_i) \right)^2 = \argmin_{K \in \mathcal{C}(C_1 \cdot d )} \sum_{i=1}^n \left(Y_i - h_K(X_i) \right)^2
\]
whenever $K^{*} \in \C$, and therefore Corollary \ref{Cor:SuppRandom} follows.

\begin{proof}[Proof of Lemma \ref{fr}]
	Let $h_{K} \in \C $ and $t > 0$, denote by
	\[
	B_{\PP}(h_{K},t) := \{L \in \mathcal{C}(C_1 \cdot d): \|h_{K} - h_{L} \|_{\PP} \leq t \}.
	\]
	We will need the following Lemma (its proof appears in the next subsection).
	\begin{lemma}[The regular polytope lemma]\label{Lem:Regu}
		For every $m \geq  4^d,d \geq 2 $ there exists a polytope $P_{m,d} \subset B_d$ with $m$ vertices that satisfies the following:
		\begin{enumerate}
			\item  $ \|\hp(x) - 1\|_{\infty} \leq C_1 m^{-\frac{2}{d-1}}$

			\item   $	\log \mathcal{N}_{[]}(\epsilon, B_{\Unif}( \hp,t),\Unif) \leq C(d)m\log(\epsilon^{-1})^{d}
			\left(\frac{t}{\epsilon} \right)^{(d-1)/2} \ \ $
			for all $  0 \leq \epsilon \leq t $.
		\end{enumerate}

	\end{lemma}
	Now, observe that the family is uniformly bounded by $C_1\cdot d$. Therefore, we can invoke Corollary \ref{Thm:LowerBirgeMassartRandom} with $f_{(m)} = \hp$, $\beta = d$, $f_0 = h_{B_d}$, and $p = \frac{d-1}{2}$. By Lemmas \ref{Lem:Bro}, \ref{Lem:BroLower}, and \ref{Lem:Regu}, we satisfy all the corollary's assumptions (observe that an upper bound on $\infty$-covering  implies that Koltchinski-Pollard entropy satisfies the same upper bound). Thus  $\Ri(\hat{h}_{\hat{K}_n},\C) \geq \Tilde{\Omega}(n^{-\frac{2}{d-1}}),$
	and the claim follows.
\end{proof}
\subsection{Proof of Lemma \ref{Lem:Regu}}
In this proof, we denote by $B_G(x,r)$ a geodesic ball on the sphere with center $x$ and radius $r$. Let $ \V:=\{v_i\}_{i=1}^{s} $ be a set of vertices of size $ m \leq s \leq 400d\ln(d)m$ with norm one. This set is a $m^{-\frac{1}{d-1}}$-net on $ \Sd $ with the following property: In any geodesic ball with radius  of $m^{-\frac{1}{d-1}}$ on the sphere there are at most $400d\ln(d)$ points. When $m \geq C^d$ such a set exists by \citep{boroczky2003covering}.

Now, we define a polytope $P_{m,d} := \mathrm{conv}\{\V\}$. First, observe that for each $x \in \R^d$ the following holds:
\begin{equation}\label{Eq:support}
\hp(x) =\max_{v \in \V}\|x\|\|v\| \cos(\angle(x,v_{\pi}))= \|x\|\cos(\angle(x,v_{\pi})),
\end{equation}
where $v_{\pi}$ is the closest point in the net to $x/\|x\|$. Then, using the fact that $\cos(t) = 1 - t^2/2 +O(t^4),$ we know that when $m \geq C_1^d$, for all $u \in \Sd$
$$
0 \leq 1-\hp(u) \leq C\mmt
$$
and the first part of the Lemma follows.

Now, we prove the last part of  Lemma \ref{Lem:Regu}, that is an upper bound on the entropy numbers.
Let us consider the support function when it is restricted to the facets of regular simplex $\mathcal{P}_d$, denoted by $S_k$, $ 1 \leq k \leq d+1 $. Now we prove the following:
\begin{lemma}
	For any $k\in\{1,\ldots,d+1\}$,  $\hp:S_k \to \R$ is at most $C\ln(d)m$ piecewise linear, and every piece has at most $C(d\ln(d))^24^{d-1} \ $ $(d-2)$- facets.
\end{lemma}
\begin{proof}
	\begin{figure}[htbp]
		\centering
		\includegraphics[width=0.5\linewidth]{support_function_construction.pdf}
		\caption{Illustration of the proof. The function $\hp$ is linear on the set $R^{-1}(C(v_i))$ (in blue) and convex piece-wise linear on $S_k$.}
		\label{fig}
	\end{figure}

	First, we use the Voronoi cells of the vertices $\V$ when they are restricted to $\Sd$, that is each cell, denoted by $C(v_i)$, $1 \leq i \leq |\V|$, is defined by $$ C(v_i) := \{x \in \Sd: \|v_i -x \| \leq \|v_j -x \| \ \ \forall   j \ne i\}.$$

	By Eq. \eqref{Eq:support} we know that for each $x \in \R^{d}$ the value of $\hp$ is attained on the closest $v_{i} \in \V$ to $x/\|x\|$ (since all the vertices of $ P_{n,d} $ have the same norm). Thus, we can write $$S_k = \bigcup_{i=1}^{|\V|}R^{-1}(C(v_i)) \cap S_k $$
	where $R$ denotes the radial function from $\mathcal{P}_d$ to $\Sd$. Moreover, observe that $$\hp: R^{-1}(C(v_i))(x) \equiv v_i^Tx.$$
	Since $\hp:S_k \to \R$ is a convex function, we conclude that it i also piecewise linear. Due to the regularity of the net  $\V$, we know that number of pieces can be bounded by $2|\V|/(d+1) \leq C\ln(d)m$.

	Next, observe that the number of $d-2$ facets of each piece, which corresponds to some $v_i \in \mathcal{V}$, is determined by the number of neighbors of the Voronoi cell $C(v_i)$. By the construction of $ \V $, it can be bounded by $C(d\ln(d))^24^{d-1}$.
	To see this, since $\mathcal{V}$ is a $m^{-1/(d-1)}$-net, clearly all the neighbors of $v_i \in \mathcal{V}$ lie in $B_G(v_i,4\eps)$. Moreover, we can bound the number of vertices in this ball by
	\begin{align*}
	|\{v \in \mathcal{V}: v \in B_G(v_i,4\eps)\}| &\leq 400d\ln(d) \cdot
	|\Ncal(\eps,B_G(v_i,4\eps),\mathrm{Unif})| \\& \leq  C(d\ln(d))^24^{d-1},
	\end{align*}
	and the claim follows.

\end{proof}
Now, we are ready to prove Lemma \ref{Lem:Regu}. It is easy see that each $\hp:S_k \to \R$ is uniformly bounded by $d$ (since $K \subset B_d$ implies that $h_K$ restricted to $S_k$ is bounded by $d$). Moreover, since we assume that all $h_{L} \in B_{\PP}(h_K,t)$ are bounded in $C_1d$, we also know that our family is uniformly bounded by $Cd^2$. Now, recall that all of $\hp \ \ $   $C\sqrt{m}/(d-1)$-pieces have at most $(Cd\ln(d))^24^{(d-1)}$ facets, hence, it is also $C(d)\sqrt{m}$ piecewise simplicial linear.  Thus, we can apply Lemma \ref{Lem:convEnt} and  find a $(d+1)^{-1/2}\epsilon$-net, denoted by $\{f_{k,j}\}_{j=1}^{S_{\epsilon}}$,  with respect to $\mathrm{Unif}(S_k)$, where
\[
S_{\epsilon}:= \log\mathcal{N}_{[]}((d+1)^{-1/2}\epsilon, B_{\mathrm{Unif}(S_k)}( \hp,t),\mathrm{Unif}(S_k)) \leq
C(d)m\log(\epsilon^{-1})^{d} \left(\frac{t}{\epsilon} \right)^{(d-1)/2}.
\]
Recall that we aim to bound the entropy numbers of the the support function on the sphere. Therefore, we use the radial function to project each facet $S_k$ onto the sphere, and show that the set of functions  $$\{\|R^{-1}(x)\|^{-1}f_{k,j}(R^{-1}(x))\}_{j=1}^{S_{\epsilon}}$$ forms an $(d+1)^{-1/2}\epsilon$-net on $B_{\mathrm{Unif}(R(S_k))}(\hp,t)$ with respect to uniform measure.

Let $h_{K} \in  \mathcal{C}(C_1 \cdot d) $ (which is convex and bounded by one) that is at least $(d+1)^{-1/2}\epsilon$ far from $\hp$, when the support functions are restricted to $R(S_k)$. Denote by $h_{\pi,K}$  the closest member to the $h_{K}$ with respect to  $\mathrm{Unif}(S_k)$ in the aforementioned set. Then,
\begin{align*}
&\sqrt{\int_{R(S_k)}(h_K(x) - \|R^{-1}(x)\|^{-1}h_{\pi,K}(R^{-1}(x))^2dS(x)}
\\&= \sqrt{\int_{R(S_k)}\|R^{-1}(x)\|^{-2}(h_K(R^{-1}(x)) - h_{\pi,K}(R^{-1}(x)))^2dS(x)} \\&=\sqrt{\int_{S_k}(h_K(x) - h_{\pi,K}(x))^2\frac{u_i^Tx}{\|x\|^{d+2}}dx} \leq \sqrt{\int_{S_k}(h_K(x) - h_{\pi,K}(x))^2dx} \leq (d+1)^{-1/2}\epsilon,
\end{align*}
where we used the homogeneity of the support function, and Lemma \ref{Lem:CV}. Therefore, we found our desired net.
Now, we can use  \citep[Lemma 2.8]{gao2017entropy}, and conclude that for all $0 \leq \epsilon \leq t$
\begin{align*}
\log \Ncal_{[]}(\epsilon, B_{\Unif}( \hp,t),\PP) &\leq   \sum_{k=1}^{d+1}\log \mathcal{N}_{[]}(\frac{\epsilon}{\sqrt{d+1}}, B_{\mathrm{Unif}(R(S_k))}( \hp,t),\mathrm{Unif}(R(S_k)))
\\&\leq   \sum_{k=1}^{d+1}\log \mathcal{N}_{[]}
(\frac{\epsilon}{\sqrt{d+1}}, B_{S_k}( \hp,t),\mathrm{Unif}(S_k))
\\&\leq C(d) m \log(\epsilon^{-1})^{d} \left(\frac{t}{\epsilon} \right)^{(d-1)/2},
\end{align*}
and the claim follows.
\subsection{Reduction to Lemma  \ref{fr}}\label{Sec:reduc}
We will show that when $K^{*} \in \C$, the LSE only considers convex sets in $\mathcal{C}(C_1 \cdot d )$. First, observe that the score of $h_{K^*}$ is bounded by $5$ when $n$ is large enough. To see this,
\begin{equation}\label{Eq:bla}
\begin{aligned}
n^{-1}\sum_{i=1}^{n}(Y_i - h_{K^{*}}(X_i))^2 &\leq 2n^{-1}\left(\sum_{i=1}^{n}\xi_i^2+ h_{K^{*}}(X_i)^2\right) \\&\leq 2\left(\int_{\Sd}h_K^2(x)d\PP(x) + 1 + O(\frac{1}{\sqrt{n}})\right) \leq 5.
\end{aligned}
\end{equation}
where we used the fact that $h_{K^*}(x) \leq 1$ when $x \in \Sd$.

Now, let $K \notin \mathcal{C}(C_1 \cdot d )$. Then, $K$ has a vertex (denoted by $v_1$)  with $\|v_1\|_2 > C_1d$. In this case for $C_1$ that is large enough, there exists a spherical cap of $\Sd$, denoted by $C(v_1)$, with center $v_1/\|v_1\|$ and normalized surface area of  $1/3$, such that $$h_{K}(u) \geq 100 \ \ \forall u \in C(v_1).$$

To see this, observe that if $C(v_1)$ has a normalized surface of $1/3$, then it implies that the geodesic distance between $v_1/\|v_1\|$ and its boundary is at most $\pi/2-c_2/(d-1)$ (for some fixed $c_2 \geq 0$). Thus, for any $u \in C(v_1)$ the following holds:
\begin{align*}
h_{K}(u) &\geq \|v_1\|\cos(\angle(v_1,u)) \geq C_1d\cos(\pi/2-c_2/(d-1))  \\&= C_1d\sin(c_2/(d-1)) \geq C_1c_2/2,
\end{align*}
therefore if we choose $C_1$ to be large enough then $h_{K}(u) \geq 100$ for all $u \in C(v_1)$.

Now, using the fact that $X_i$ are i.i.d uniform on the sphere, we know that with  probability of at least $1-e^{-cn}$, there are at least $n/4$ points in this cap (using concentration for Bernoulli random variables). Moreover, since $\xi_i \sim N(0,1)$, we know that with high probability, at least $0.49$ of the points that lie in this cap, the $\xi_i$ are negative. Thus, we conclude that with high probability
\begin{align*}
n^{-1}\sum_{i=1}^{n}(Y_i - h_{K}(X_i))^2 &\geq n^{-1}\sum_{X_i \in C(v_1),~ \xi_i \leq 0}(h_{K}(X_i)- 1 -\xi_i)^2 \geq 11.
\end{align*}
Using the last equation and Eq. \eqref{Eq:bla}, only sets in $\mathcal{C}(C_1 \cdot d)$ will be considered, and the claim follows.

\bibliography{bib}
\appendix
\section{Auxiliary results and basic facts}
\begin{proof}[Proof of Lemma \ref{Lem:BMbound}]
	Under the conditions of the Lemma, \cite[Thm 5.11]{van2000empirical} implies that for the fixed point $\varepsilon$,
	\[
	\sup_{g \in B_{\PP}(f,t)}\big| \PP_n(g) - \PP(g)\big| \lesssim \varepsilon,
	\]
	with probability of at least $1-C\exp(-c(n(\varepsilon/t)^2)) \geq 1-C\exp(-cn\varepsilon^2)$ since $t\leq 1$ due to uniform boundedness. Now, using de-symetrization argument (e.g. \citep{koltchinskii2011oracle}), we know that
	\[
	\E\GW(B_{\PP}(f,t)) - \frac{1}{\sqrt{n}} \lesssim \E\sup_{g \in B_{\PP}(f,t)}\big| \PP_n(g) - \PP(g)\big| \lesssim  \varepsilon.
	\]
	Therefore, in expectation we have the desired bound. Since the class in uniformly bounded by one, we can apply McDiarmid’s inequality which gives
	\[
	\Pr\left(\GW(B_{\PP}(f,t)) - C(n^{-1/2} + \varepsilon) \geq u\right) \leq \exp(-cnu^2)
	\]
	and by setting $ u = C(\varepsilon + n^{-1/2})$ the claim follows.
\end{proof}
\begin{lemma}[Jacobian of the radial function, see for example \cite{schneider2008stochastic}]\label{Lem:CV}
	Let $H= \{x \in \R^d\ : \  x^Tu = h\}$ be a $d-1$ hyper-plane and any integrable $f:H \to \R$, the following holds for the radial function $R(x) = x/\|x\|$:
	$$\int_{H}f(x)\frac{u^Tx}{\|x\|^{d}}dx = \int_{R(H)}f(R^{-1}(x))dS(x).$$
\end{lemma}

\begin{lemma}[Basic facts on the support function, see for example \citep{artstein2015asymptotic}]\label{Lem:BasF}
	\quad
	\begin{itemize}
		\item  For every $K \in \C$, the function $h_K$ can be extended to the whole of $\R^d$ via $h_K(x) = \|x\|h_K(x/\|x\|)$ and this extension makes $h_K$ a convex and 1-Lipschitz function on $\R^d$.
		\item For any $\lambda > 0$, $K \in \mathcal{C}$ the following holds for all $x\in\R^d$: $h_{\lambda K}(x) = \lambda h_{K}(x)$.
	\end{itemize}

\end{lemma}

\end{document}

config: arxiv


TITLE: Learning concepts in mathematics
QUESTION [2 upvotes]: Apologies for the soft question, but I was wondering whether it is a good idea, in mathematics, to learn/study things simply for the sake of studying it. A very good example comes from category theory. I've seen many people here on MSE who wish to study category theory for the sake of studying the abstractness and the richness of category theory. While pure category theory is fun, it was built to be applied, like in algebraic topology and homotopy theory.

Is it alright to have this attitude when studying "abstract concepts" (like (higher) category theory)? How about when publishing research? Does research always have to have some applications to something known previously?

REPLY [0 votes]: I think that a good work (for instance, it which are obtained new and beautiful results) is worth to be published. As a mathematician and a referee, I am pro such works. I think that the essence of development concerns with creation of new things. I think that a theory has own growth and development, and, therefore it is not restricted to serve to applications. And a study is a form of own development of a mathematician. Now I step back, and Alfred Tarski give  the final remarks.


text:
\begin{document}

\begin{titlepage}

\begin{center}
{\large \bf  Noncommutative Chern-Simons gauge and gravity theories\\[.5em]  and their geometric Seiberg-Witten map}\\[3em]
 {\bf Paolo Aschieri} and {\bf Leonardo Castellani} \\ [2em] {\sl Dipartimento di Scienze e Innovazione Tecnologica
\\ and INFN Torino, Gruppo collegato di Alessandria,\\Universit\`a del Piemonte Orientale,\\ Viale T. Michel 11,  15121 Alessandria, Italy\\[1em]
}
\end{center}

\begin{abstract}

\vskip 0.2cm

We  use a geometric generalization of the Seiberg-Witten map
between noncommutative and commutative gauge theories to find
the expansion of noncommutative Chern-Simons (CS) theory in any odd
dimension $D$ and at first  order in the noncommutativity parameter $\theta$.
This expansion extends the classical CS theory with higher powers of the curvatures and their derivatives.

 A  simple explanation of the equality between noncommutative and
 commutative CS actions in $D=1$ and $D=3$ is obtained.
The $\theta$ dependent terms are present  for $D\geq 5$ and give
 a higher derivative theory on commutative space
 reducing to classical CS theory for $\theta\to 0$.
These terms depend on the field strength and not on the bare gauge
potential.

In particular, as for the
 Dirac-Born-Infeld action, these terms vanish in the slowly varying field strength
 approximation: in this case noncommutative  and commutative CS actions coincide in any dimension.

The Seiberg-Witten map on the $D=5$ noncommutative CS theory is explored in more detail, and we give its second order $\theta$-expansion for any gauge group. The example of extended $D=5$ CS gravity, where the gauge group is $SU(2,2)$, is  treated explicitly.

 \end{abstract}

\vskip 3cm \noi \hrule \vskip.2cm \noi {\small
aschieri@unipmn.it\\leonardo.castellani@mfn.unipmn.it}

\end{titlepage}

\newpage
\setcounter{page}{1}

\sect{Introduction and Summary}
Noncommutative (NC) actions can be expanded order by order in the
noncommutativity parameter  $\theta$ and be
interpreted as effective actions on commutative spacetimes, the noncommutativity
leading to extra interaction terms, possibly capturing some
quantum spacetime effect. These actions involve higher
derivatives in the field strengths.
For gauge theory actions one can expand not only the
$\star$-products but also the noncommutative fields in terms of the
commutative ones using the Seiberg-Witten (SW) map \cite{SW} .
This allows to define NC gauge theories with any simple gauge group in
arbitrary representations \cite{JSSW, JMSW}.  In the literature
deformations have been studied mainly at first order in $\theta$.

In \cite{Moller:2004qq,Aschieri:2011ng, Aschieri:2012in,
Dimitrijevic:2012pk, DiGrezia:2012kf, Dimitrijevic:2014iwa},
extensions of  Yang-Mills and  gravity
theories have been obtained at second order in the
noncommutativity parameter $\theta$ starting from NC actions. The
second order expansion is needed in the case of $D=4$ gravity theories
because the first order $\theta$-correction vanishes\footnote{A complementary route, named $\theta$-exact
  approach, is to expand the NC  actions in power series of the gauge
  potential while keeping all orders in $\theta$, see  \cite{Schupp:2008fs,
    Horvat:2013rga} for  expansions up to second order in the gauge
  potential and quantum field theories applications and \cite{martin} for expansions up to third order.}.

Some gauge theory actions have the remarkable property of being
invariant under the SW map. This is notably the case for the CS action in 3
dimensions \cite{Grandi:2000av} and, if we consider slowly varying field strengths, for
the Dirac-Born-Infeld theory in any dimension \cite{SW, JSW} .
Noncommutative CS actions can be studied in any (odd) dimension
\cite{CF,Poli1,Cacciatori2002,Castellani:2013tva}.
In \cite{Castellani:2013tva} noncommutativity is given by a Drinfeld
twist defined by a set of commuting vector fields (so-called abelian Drinfeld twist), this
noncommutativity including as a special case Moyal-Groenewold
noncommutativity.
\sk
In this paper we apply the geometric Seiberg-Witten map
\cite{Aschieri:2011ng} (i.e. the geometric generalization of the SW map that
applies to Drinfeld twist noncommutativity) to
the noncommutative Chern-Simons  actions
in any odd dimension studied in \cite{Castellani:2013tva}.
We obtain the correction to the classical action up to first order in the
noncommutativity  parameter $\theta$. The correction is  expressed in
terms of the curvature $R=d\Om-\Om \we \Om$, of its contraction along the
vector fields determining the noncommutativity and of its covariant
derivative. These terms are covariant under gauge transformations and
therefore the  correction  is truly gauge invariant (not just
up to boundary terms).
The construction of these extended commutative CS actions obtained by adding correction terms order by order in $\theta$ applies to any gauge group $G$. For slowly varying field
strength we show that these correction terms vanish, so that, as for
Dirac-Born-Infeld theory, also noncommutative and commutative CS
theories coincide in any dimension in this approximation.

The variation of the NC Chern-Simons form under SW map has an intriguing structure. We find that the SW map relates the NC topological terms
$Tr(R^n)$ and $Tr(R^{n+1})$ and therefore relates the
NC  CS forms in $D$ and in $D+2$
dimensions. In fact  $D$-dimensional CS forms are mapped into double
contractions of the $(D+2)$-dimensional CS forms, plus
contractions of $(D+1)$-forms, plus extra terms that are covariant
under gauge transformations. Since in $D$
dimensions  $(D+2)$- and $(D+1)$-forms vanish, only the extra covariant terms are
relevant in computing the SW map of the CS action. In $D=1$ and $D=3$
the extra covariant  terms are absent, which easily explains why in these cases the SW
map is trivial, as first observed by
\cite{Grandi:2000av}.
Our  results confirm those of
\cite{Poli2}, where, using a different approach based on operator valued
fields, a (generalized) NC CS action defined only in terms of covariant
derivatives was shown to be nontrivial under the SW map in dimension $D>3$.
We sharpen the findings in \cite{Poli2} by explicitly computing
and analyzing the extra terms in $D>3$. Moreover we
are not constrained to consider Moyal-Groenewold
noncommutativity, and our commutative limit, never involving the
inverse of $\theta^{\mu\nu}$, is well under control for $\theta\to 0$.

The first nontrivial $\theta$ dependence occurs in $D=5$ NC CS theory. For this case we compute also the second order expansion in $\theta$.

Next we specialize to NC CS gravity \cite{Castellani:2013tva} where
the gauge group is $G=SU(2,2)$, and explicitly compute  its expansion to first order in $\theta$
in terms of component fields.

In this paper we  focus on
local properties of CS forms:
in particular the connection $\Omega$ is
always  globally defined, and the underlying principal $G$-bundle
is trivial.
\sk

It would be
interesting to extend our analysis to the D=5 noncommutative Chern-Simons supergravity theory
constructed in \cite{Castellani:2013tva}, invariant under the local action of the
$\star$-supergroup $U(2,2|N)$ that includes $N$ supersymmetries.
In this case the SW map relates $\star$-supersymmetry to ordinary supersymmetry,
so that the $\theta$-correction terms of the SW expansion are separately invariant under
ordinary supersymmetry. The result is an extended $D=5$ CS supergravity with
(locally) supersymmetric higher order terms. This work is in progress.
\sk

The paper is organized as follows. In Section 2 we recall a few facts on Chern-Simons
forms and their noncommutative versions. In Section 3 we recall the
geometric generalization of the Seiberg-Witten map. In Section 4 we compute
the SW variation of the NC topological term $Tr(R^n)$, of the CS forms and of the
CS actions. In Section 5 we apply these results to $D=5$
CS and present the first and second order corrections in $\theta$; finally
we consider the case of $D=5$ CS gravity. In Appendix
\ref{SWTrRn} we give the derivation of the SW variation of the noncommutative topological term $Tr (R^n)$. In
Appendix \ref{UI} we collect useful identities, and Appendix \ref{gamma}
contains a summary of $D=5$ gamma matrix properties.
\sk

\sect{Chern-Simons forms and their noncommutative versions}
\sk
{\noi\bf Commutative CS forms}
\sk
\noi  The CS Lagrangian in $(2n-1)$-dimensions  is a $(2n-1)$-form given in terms of the  $G$-gauge connection $\Om$ and its
 exterior derivative
 $d\Om$, or equivalently its curvature $2$-form $R=d\Om - \Om \we \Om$, by
  the following expressions (see e.g. \cite{Nakahara,EGH}):
   \eq
    L_{CS}^{(2n-1)}= n \int^1_0 Tr[\Om(t d\Om-t^2 \Om^2)^{n-1} ] dt= n \int^1_0 t^{n-1} Tr[\Om(R+(1-t)\Om^2)^{n-1} ] dt
     \en
where we have omitted writing explicitly the wedge product.  For example:
      \eqa
& &  L^{(1)}_{CS} = Tr[\Om]\\
      & & L^{(3)}_{CS} = Tr[R\Om + {1 \over 3} \Om^3] \\
      & & L^{(5)}_{CS} = Tr[R^2\Om + \unmezzo R \Om^3 + {1 \over 10} \Om^5] \label{CS5}\\
        & & L^{(7)}_{CS} = Tr[R^3\Om + {2 \over 5} R^2 \Om^3 + {1 \over 5} R \Om^2 R \Om +  {1 \over 5} R \Om^5
        +{1 \over 35} \Om^7]
         \ena
These expressions are obtained by solving the condition
\eq
 dL_{CS}^{(2n-1)} = Tr(R^n)  \label{CSdef}~.
 \en
The CS form $L_{CS}^{(2n-1)}$ contains (exterior
products of) the Lie$(G)$-valued  gauge potential one-form $\Om$ and
its exterior derivative. The trace $Tr$ is taken on some representation of the Lie algebra $Lie(G)$.
\footnote{ More generally $Tr$ can be any multilinear function of the Lie algebra,
invariant under cyclic permutations. In this paper $Tr$ stands for the usual matrix trace.}
\sk
Because of (\ref{CSdef}), the  CS action on the boundary $\partial M$ of a manifold $M$ is related to a topological action in $2n$ dimensions  via Stokes theorem:
 \eq
  \int_{\part M} L_{CS} ^{(2n-1)}= \int_{M} Tr(R^n)~.
 \en
Infinitesimal  gauge transformations are defined by
 \eq
 \de_\epsi \Om = d \epsi - \Om \epsi + \epsi \Om,~~~ \Rightarrow ~~~\de_\epsi R = - R \epsi + \epsi R \label{gaugetransf}
 \en
 so that $Tr(R^n)$ is manifestly gauge invariant. Therefore also the
 CS action is gauge invariant under infinitesimal gauge
 transformations\footnote{Notice that this argument does not work for finite gauge
transformations because not all finite gauge transformations on the
 boundary $\partial M$ are induced by finite gauge transformations in the bulk
 $M$. In general under finite gauge transformations  the  CS form
 changes by a locally exact form, related to a winding
 number. Hence only the equations of motion are invariant under finite transformations.}.
\sk

 Considering $  L_{CS}^{(2n-1)}$ as a function of $\Om$ and $R$, a
 convenient formula for its gauge variation is (see for example ref. \cite{Castellani:2013tva})
  \eq
   \de_\epsi L_{CS}^{(2n-1)} = d ( j_\epsi L_{CS}^{(2n-1)}) \label{CSvariationepsi}
   \en
 \noi where $j_\epsi$ is a contraction acting selectively on $\Om$, i.e.
  \eq
   j_\epsi \Om = \epsi,~~~   j_\epsi R = 0 \label{CSvariationepsi1}
    \en
   with the graded Leibniz rule $j_\epsi (\Om \Om) = j_\epsi (\Om) \Om
   - \Om  j_\epsi (\Om) = \epsi \Om - \Om \epsi$ etc.
Considering instead $L_{CS}^{(2n-1)}$ as  a function of $\Omega$ and
$d\Omega$, formula (\ref{CSvariationepsi}) holds with the rules
  $ j_\epsi \Om = \epsi $ and $j_\epsi d\Omega=\epsi\Omega-\Omega\epsi$.

\sk\sk
\noi{\bf $\star$-Exterior products from abelian Drinfeld twists}
\sk
\noi The preceding discussion is  based on algebraic manipulations, and relies
on the (graded) cyclicity of $Tr$. As such, it can be exported immediately to the
noncommutative setting, provided we ensure that cyclicity holds.
The noncommutativity we consider here is controlled by an abelian twist, and
amounts to a deformation of the  exterior product:
 \eqa
 \!\!\!\!\!\!\!& & \!\!\!\!\!\!\!\!\!  \tau \westar \tau' \equiv  \sum_{n=0}^\infty {1 \over n!} \left( {i \over 2}\right)^n \theta^{A_1B_1} \cdots \theta^{A_nB_n}
   (\ell_{{A_1}} \cdots \ell_{{A_n}} \tau) \we  (\ell_{{B_1}} \cdots \ell_{{B_n}} \tau')  \nonumber \\
 \!\!\!\!\!\!\!  & & \!\!\!\!\!\!\! ~~ = \tau \we \tau' + {i \over 2} \theta^{AB} (\ell_{A} \tau) \we (\ell_{B} \tau') + {1 \over 2!}  {\left( i \over 2 \right)^2} \theta^{A_1B_1} \theta^{A_2B_2}  (\ell_{{A_1}} \ell_{{A_2}} \tau) \we
 (\ell_{{B_1}} \ell_{{B_2}} \tau') + \cdots \nonumber \\
  \label{defwestar}
\ena
       \noi where $\theta^{AB}$ is a constant antisymmetric matrix, and $\ell_{A}$ are Lie derivatives along commuting
       vector fields $X_A$. The product is associative due to $[X_A , X_B]=0$ ($ \Rightarrow [\ell_A , \ell_B]=0$) .  If  the vector fields $X_A$ are chosen to  coincide with the partial derivatives
$\partial_\mu$, and if $\tau$, $\tau'$ are $0$-forms, then
$\tau\star\tau'$ reduces to the well-known Moyal-Groenewold product
\cite{MoyalGroenewold}. A short review on twisted differential
geometry can be found for example in \cite{AC1}.

The deformed exterior product differs from the undeformed one by a
total Lie derivative, indeed since  $[\ell_A , \ell_B]=0$ we can write
\eqa
   \tau \westar \tau' & =& \tau\wedge\tau'+
\ell_{A_1} \sum_{n=1}^\infty {1 \over n!} \left({i \over 2}\right)^n \theta^{A_1B_1} \cdots \theta^{A_nB_n}
   (\ell_{{A_2}} \cdots \ell_{{A_n}} \tau) \we
   (\ell_{{B_1}}\ell_{{B_2}}\cdots \ell_{{B_n}} \tau') \nonumber\\
&=& \tau\wedge\tau'+ \ell_{A_1} \,Q^{A_1}\label{totalLie}
\ena
where for brevity we have renamed the summation $Q^{A_1}$. In particular when  $\tau\wedge\tau'$ is a top form
we have
\eq\label{cyclicp}
\int \tau\wedge_\star\tau'=\int\tau\wedge\tau'
\en
for suitable boundary conditions; indeed

$\int \ell_{A_1}Q^{A_1}=\int (i_{A_1}d+di_{A_1})Q^{A_1}=0$ because
$dQ^{A_1}=0$ since $Q^{A_1}$ is a top form, and $\int di_{A_1}Q^{A_1}=0$
if we integrate on a manifold without boundary or if the forms $\tau$
and $\tau'$ have suitable boundary conditions.
The equality (\ref{cyclicp}) implies that the integral of
$\star$-wedge products of homogeneous  forms has the usual graded cyclic
property $\int \tau\wedge_\star\tau'=(-1)^{deg(\tau)deg(\tau') }\int \tau'\wedge_\star\tau$. Notice however that in general
 $\int \tau\wedge_\star\tau'\wedge_\star\tau''\not= \int \tau\wedge
 \tau'\wedge \tau''$.
\sk
If we now consider homogeneous forms $\Tau, \Tau'$ that are Lie algebra valued, the trace of the $\wedge_\star$-product of forms is still graded cyclic up to total Lie derivative terms:
\eq
Tr(\Tau\wedge_\star\Tau')=(-1)^{deg(\Tau)\deg(\Tau')\;}Tr(\Tau'\wedge_\star\Tau)+\ell_AQ^A~;\label{ambiguity}
\en
and for suitable boundary conditions the integral of the trace has the graded cyclic property.

\sk\sk
\noi{\bf Noncommutative CS forms}
\sk
\noi We define noncommutative Chern-Simons actions by replacing
$\wedge$-products with $\wedge_\star$-products in the commutative
Chern-Simons action. This procedure is unique if we integrate
over manifolds without boundary or if the fields are properly behaving at
the boundary; it is not unique for CS forms because
of the cyclic ordering ambiguities (\ref{ambiguity}), that are however
irrelevant in the present paper. We denote by $L^{(2n-1)}_{CS^*}$ any
one of  the NC generalizations of the CS form $L^{(2n-1)}_{CS}$.

The check  that the exterior derivative of the commutative CS
form $L_{CS}^{{(2n-1})}$ gives  $Tr(R^n)$ is algebraic, and relies only on  the Leibniz rule
property of the exterior derivative and on the graded cyclicity of the trace.
Since the exterior derivative satisfies the Leibniz rule also
in the noncommutative case, and the graded cyclicity of the trace holds
up to total Lie derivatives, we can conclude that the
noncommutative Chern-Simons form satisfies the relation
\eq
dL_{CS^*}^{(2n-1)}=Tr(R^{\wedge_\star n}) + \ell_C Q^{(2n)\,C} \label{dLequalR}
\en
where $Q^{(2n)C}$ is due to cyclic reorderings and is  a sum of wedge products of Lie derivatives of
connections and of their exterior derivatives.

We note that  $Q^{(2n) C}$ is
local in the noncommutative connection, in the sense that expanding the
$\wedge_\star$-product, for any finite order in
$\theta$ there is a finite number of Lie or exterior
derivatives.

\sk
In the noncommutative case the gauge group $G$ usually has to be extended,
because $\star$-commutators in general do not close in the original Lie
algebra Lie$(G)$.  For example
\eqa
\Om\wedge_\star\Om&=&\Om^a\wedge_\star\Om^b\,T^aT^b \label{closurefields}\\
&=&
\frac{1}{2}(\Om^a\wedge_\star\Om^b-\Om^b\wedge_\star\Om^a)[T^a,T^b]+\frac{1}{2}
(\Om^a\wedge_\star\Om^b+\Om^b\wedge_\star\Om^a)\{T^a,T^b\}~,\nonumber
\ena
with the second term nonvanishing because the $\wedge_{\star}$-product is
not antisymmetric. We therefore consider Lie algebras with representations $T^a$
that close under the usual matrix product (i.e. under commutators and anticommutators).
Note however that this restriction can be lifted when using the Seiberg-Witten map
(see Section 5).

It is easy to  prove the  invariance of the
noncommutative Chern-Simons action under infinitesimal $\star$-gauge transformations  defined by:
 \eq
 \de_\epsi^\star \Om = d \epsi - \Om \star \epsi + \epsi \star \Om,~~~ \Rightarrow ~~~\de_\epsi^\star R = - R \star \epsi + \epsi \star R \label{stargaugetransf}~.
 \en
Indeed
 \eq
 \de_\epsi^\star \int L^{(2n-1)}_{CS^*}=\int d ( j_\epsi L_{CS^*}^{(2n-1)}) =0
 \en
\noi for suitable boundary conditions. This is so because  in the
$\star$-deformed case the
variation formulae (\ref{CSvariationepsi}), (\ref{CSvariationepsi1})
still hold true under integration.
\sk
\noi For example the $D=5$ $\star$-Chern-Simons action reads
\eq
 \int L^{(5)}_{CS^*} =
\int  Tr[R \westar R \westar \Om + \unmezzo R \westar \Om \westar \Om \westar \Om +
  {1 \over 10} \Om \westar \Om\westar \Om \westar \Om \westar \Om] \label{starCS5}~.
\en
\noi and  is invariant under the $\star$-gauge variations (\ref{stargaugetransf}).

\sect{The Seiberg-Witten map}

In the framework of Moyal deformed gauge theories, Seiberg
and Witten showed how to relate noncommutative fields (that transform under deformed gauge transformations) to ordinary fields, called also classical fields, transforming with the usual gauge
variation laws. The Seiberg-Witten map expresses the NC fields as
functions of the ordinary fields in such a way that usual gauge variations
on the latter induce  $\star$-gauge variations on the former. The map is nonlinear, and is determined order by order in the noncommutativity parameter $\theta$.

Under this map, a NC action can be re-expressed in terms of classical fields. The result is
invariant under usual gauge variations (since the NC action is
invariant under  $\star$-gauge variations), and can be written as the
classical action plus higher order $\theta$ corrections, each of which
is separately gauge invariant under usual gauge variations (because usual gauge
variations do not involve $\theta$).  This map provides therefore an
interesting mechanism to generate extensions of usual commutative
actions, with interaction terms that depend on $\theta$ (for gravity actions see
\cite{Aschieri:2011ng,   Aschieri:2012in, Dimitrijevic:2012pk, DiGrezia:2012kf, Dimitrijevic:2014iwa}).
\sk
Denoting by $\Omhat$ the NC
gauge field, and by $\epsihat$ the NC  gauge parameter, the Seiberg-Witten map relates  $\Omhat$
to the ordinary  $\Om$, and
$\epsihat$ to  the ordinary  $\epsi$ and to $\Omega$ so as to
satisfy:
 \eq
\Omhat (\Om) + {\widehat{\delta}}_\epsihat
\Omhat (\Om) = \Omhat (\Om + \de_\epsi \Om)
\label{SWcondition}
\en
 with
  \eqa
   & &
  \de_\epsi \Om = d \epsi + \epsi ~\Om -  \Om
      \epsi~, \\
      & &
  \deltahat_\epsihat{} \Omhat = d \epsihat + \epsihat \star \Omhat -  \Omhat \star
      \epsihat~.
      \ena

\noi  Thus the dependence of the NC gauge field on the ordinary gauge field  is determined
by requiring that ordinary gauge variations of $\Om$ inside
$\Omhat(\Om)$ produce the noncommutative gauge variation of $\Omhat$.

The condition (\ref{SWcondition}) is satisfied if the following differential equations in the
noncommutativity parameter $\theta^{AB}$ hold \cite{SW, Aschieri:2011ng}:
\eqa
 &  &\delta_\theta \Omhat \equiv \delta\theta^{AB}{ \part ~~\over \part \theta^{AB}} \Omhat = {i \over 4}  \delta\theta^{AB}\{ \Omhat^{}_{A},  \ell^{}_{B} \Omhat +\Rhat^{}_{B} \}_\star ~,\label{diffeqOm} \\
&  &\delta_\theta\epsihat\equiv\delta\theta^{AB} { \part ~~\over \part \theta^{AB}}  \epsihat = {i \over 4}  \delta\theta^{AB}\{ \Omhat_{A},  \ell^{}_{B} \epsihat \}_\star \label{diffeqepsi} ~,
\ena
\noi where:\\
$\bullet$ $\Omhat_A$, $\Rhat_A$ are defined as the contraction $i_A$ along the tangent
vector $X_A$ of the exterior forms $\Omhat$, $\Rhat$, i.e. $\Omhat_A\equiv i_A\Omhat$,
$\Rhat_A \equiv i_A \Rhat$.\\[.2em]
$\bullet$ The bracket $\{~,~\}_\star$ is the usual $\star$-anticommutator, for
example $\{\Om_A,R_B\}_\star=\Om_A\star R_B+R_B\star\Om_A$.

\sk
The differential equations (\ref{diffeqOm})-(\ref{diffeqepsi}) hold
for any abelian twist defined by arbitrary commuting vector
fields $X_A$    \cite{Aschieri:2011ng}.  They reduce to the usual Seiberg-Witten
differential equations  \cite{SW}  in the case of a Moyal-Groenewold  twist, i.e. when $X_A\to \partial_\mu$.

\sk
We can solve these differential equations order by order in $\theta$
by expanding $\Omhat$ and $\epsihat$ in power series of
$\theta$, so that (the factor $\frac{i}{2}$ is inserted for ease
of later notation) $\Omhat=\Om+\frac{i}{2}\theta^{AB}\Om'_{AB}-\frac{1}{8}\theta^{AB}\theta^{EF}{}\Om''_{AB\;EF}+\ldots$
 where
 $\frac{i}{2}\Om'_{AB}=\frac{\partial~}{\partial\theta^{AB}}\Omhat|_{\theta=0}$ etc.,
 and similarly for $\epsihat$.
For example up to first order in $\theta$ from (\ref{diffeqOm}) and
(\ref{diffeqepsi}) we immediately find
\eqa
& & \Omhat=\Om+   {i \over 4}  \theta^{AB}\{ \Om^{}_{A},
\ell^{}_{B} \Om +R^{}_{B} \} +{\cal O}(\theta^2)~,\label{solOm} \\
&  & \epsihat = \epsi+ {i \over 4}\theta^{AB}  \{ \Om_{A},  \ell^{}_{B} \epsi \}+{\cal O}(\theta^2) ~.\label{solepsi}
\ena
Recursive formulas were found in \cite{Ulker} for the Moyal-Weyl product, and generalized  for the geometric
SW map in
\cite{Aschieri:2011ng}.
Typically $\Omhat$ is a  power series in $\theta$ of
sums of products of commutative connections, also  contracted and
differentiated (e.g. $\Om_A, i_Ad\:\!\Om, \ell_A\ell_B\Om$, etc.). Again we say that $\Omhat$ is
local in the commutative connection because for every power of
$\theta$ only a finite number of exterior derivatives appears. It
follows that  in this framework noncommutative Lagrangians are power
series in $\theta$ of commutative Lagrangians that are  local in the connection
$\Om$.

\sect{The SW variation of  NC Chern-Simons forms}
In the following we omit the hat
denoting noncommutative fields,  the $\star$ and $\wedge_\star$
products, and simply write $\{~,~\}$, $[~,~]$  for the
$\star$-anticommutator and the $\star$-commutator
$\{~,~\}_\star$, $[~,~]_\star$.
\sk
\sk\noi {\bf SW variation of $Tr(R^n)$}
\sk

\noi An expression equivalent to (\ref{diffeqOm}) for the SW variation of the  connection 1-form is
\eq\label{omequivsw}
\de_\theta \Om = {i \over 4} \de \theta^{AB}  \{\Om_A, \Lfat_B  \Om - d \Om_B \}~.
 \en

\noi The ``fat" Lie derivative  $\Lfat_B$ is defined by
$\Lfat_B\equiv \ell_B+L_B\,$ where $L_B$ is the  covariant Lie derivative  along the
tangent vector $X_B$; it acts on every field $P$ as
$$L_B P = \ell_B P - [\Om , P]. $$
\noi In fact the covariant Lie derivative $L_B$ can be written in Cartan form:
 \eq
  L_B = i_B D + D i_B~,
    \en
where $D$ is the covariant derivative: $
DP=dP-[\Om,P]$ {for} P {even form},  $DP=dP-\{\Om,P\} $ {for} P {odd
  form}. In particular $DR=0$ (Bianchi identity) follows from the
definition of $R$. Moreover $L_AR=i_ADR+Di_AR=DR_A$.

The SW variation of the connection implies the following
variation for the curvature 2-form $R = d\Om - \Om \we \Om$
(an easy derivation uses equation (\ref{SWPQ}) with $P=Q=\Om$),
 \eq
 \de_\theta R = {i \over 4} \de \theta^{AB} ( \{\Om_A, \Lfat_B  R \} - [R_A,R_B]) \label{SWonR}~.
 \en
From this formula and  iterated use of (\ref{SWPQ}) the SW variation of the trace of $R^n$ can be proven to be  (see Appendix \ref{SWTrRn}):
\eq
 \de_\theta Tr (R^n)=\frac{i}{2} \de \theta^{AB} Tr \Big(
     \frac{1}{n+1}i_Bi_AR^{n+1}\Big)+\frac{i}{2} \de \theta^{AB} \Big( dU_{AB}+ \ell_C Q^C_{AB}\Big)
\label{SWonRn}
  \en
  \noi where the $(2n-1)$-form
$U_{AB}$ is given by
   \eq
U_{AB} = Tr\Big(\sum_{i=2}^{n-1}R^{i-1}DR_{[A}(R^{n-i})_{B]}\Big)~
 \label{Pformula}
  \en
 \noi
with $(R^{n-i})_{B}\equiv i_B  (R^{n-i})$. Antisymmetrization
in the indices $_{A~B}$ has weight one (i.e.  $_{[A~B]}\, =
    \,\frac{1}{2} \; {}_{A~B} \;-\;\frac{1}{2} \;  {}_{B~A}$).
The precise expression (see Appendix \ref{SWTrRn} for details) of the
$2n$-form $Q_{AB}^C$, local in the NC connection, will not be relevant in the following.
\sk
\sk
\noi {\bf SW variation of $Tr(R^n)$ on a $2n$-dimensional manifold $M$}\sk
\noi
If the forms are defined on a $2n$-dimensional manifold $M$, $Tr(R^n)$ has top
degree and its SW variation  (\ref{SWonRn})  simplifies since
$R^{n+1}=0$ being a $(2n+2)$- form.
Moreover,  writing $\ell_C=i_Cd+d\,i_C$ and observing that
$dQ^C_{AB}=0$
because it is a ($2n+1$)-form, we obtain the SW variation of the top form $Tr(R^n)$:
\eq
\delta_\theta Tr(R^n)
=
\frac{i}{2} \de \theta^{AB}
d\big(U_{AB} +  i_C Q^C_{AB}\big)
\label{(4.6)}
\en

\noi Let's comment on the nontrivial information in this formula. The exactness of  $\delta_\theta Tr(R^n)$ is a trivial
consequence of considering $R^n$ a top form.
We write
$\delta_\theta Tr(R^n)=d\eta$ and compare this expression with  the SW variation of
(\ref{dLequalR}) that when $R^n$ is a top form reads $\delta_\theta
Tr(R^n)= d\delta_\theta L_{CS^\star}^{(2n-1)} - di_C \delta_\theta Q^{(2n)\,C} $.
Recalling the differential equation
(\ref{diffeqOm})
 we see that  $\eta$  is local in the NC
 connection (i.e., that expanding the $\wedge_\star$-product, for any finite order in
$\theta$ we have a finite number of Lie or exterior derivatives in the
NC connection).

The nontrivial information in  (\ref{(4.6)}) is that $\eta_{AB}$, defined by $\eta=\de \theta^{AB} \eta_{AB}$, is given by the sum
$U_{AB} +i_CQ^C_{AB}$ where the second term is a contraction
of a $2n$-form (local in the NC connection), and the first term is
expressed only  in terms of products of curvatures, their contractions
and covariant derivatives, i.e., in terms of only gauge covariant fields.

\sk\sk
\noi {\bf SW variation of $L_{CS^\star}^{(2n-1)}$}

\sk
\noi The SW variation of $L_{CS^\star}^{(2n-1)}$ can be inferred from eq. (\ref{dLequalR}):
 $
  d L_{CS^\star}^{(2n-1)} = Tr (R^n) + \ell_C Q^{(2n)\,C} ,
$
    \noi where the Lie derivative term on the right hand side comes from cyclic reorderings
     (in the commutative limit $Q^{(2n) C}=0$ since the trace in that case is
     cyclic).
 Using this relation in (\ref{SWonRn})
yields the SW variation of $dL_{CS^\star}^{(2n-1)}$ in a  manifold of arbitrary dimension,
\eqa
 \de_\theta d\,  L_{CS^\star}^{(2n-1)}\!\!\!&=& \!\!\!{i \over 2} \de \theta^{AB} d\,\Big(
  {1 \over n+1}  i_B i_A (  L_{CS}^{(2n+1)} ) + U_{AB} \Big)\label{CSvariation}\\
 & & \!\!\!\!\!\!\! + {i \over 2} \de \theta^{AB} \Big(  {-1 \over n+1}  i_B
 i_A \ell_C Q^{(2n+2)\,C}+ \ell_C Q^{C}_{AB}
\Big) +
 \ell_C (\de_\theta Q^{(2n)\,C})  \nonumber ~.
       \ena
For forms living in a $2n$-dimensional manifold $M$, this becomes
\eq
 \de_\theta d\,  L_{CS^\star}^{(2n-1)}={i \over 2} \de \theta^{AB} d\big(
 U_{AB} \label{CSvariationsimp}+
i_C Q^{C}_{AB}\big) +
 di_C (\de_\theta Q^{(2n)\,C})  \nonumber ~
\en
 where we used the identity $\ell_C=i_Cd+d\,i_C$ and the vanishing of
forms of degree higher than $2n$. Equivalently on $M$ we have

\eq
 \de_\theta  L_{CS^\star}^{(2n-1)}={i \over 2} \de \theta^{AB} \Big( U_{AB} \label{CSvariationsimp1}\\
+  i_C Q^{C}_{AB} \Big)+
i_C (\de_\theta Q^{(2n)\,C})+d\varphi  \nonumber ~
\en
for some ($2n-1$)-form $\varphi$ written in terms of the connection, of exterior
derivatives and of contraction operators along the noncommutative
directions\footnote{The  local structure of $\varphi$ follows observing
  that the SW map is local in the sense discussed at the end of
  Section 3.}.

We now consider a ($2n-1$)-dimensional  submanifold $N$ of $M$ and
choose commuting vector fields $\{X_A\}$ on $M$ that restrict to
vector fields on $N$.
In this case
$L_{CS^\star}^{(2n-1)}$ is a top form on
$N$, and
$Q^{C}_{AB}=\de_\theta Q^{(2n)\,C}=0$ being $2n$-forms on
the ($2n-1$)-dimensional manifold $N$.
The SW variation of the CS action on a manifold $N$ with no
boundary or with  fields that have
appropriate boundary conditions is therefore
\eqa
\delta_\theta\int L_{CS^\star}^{(2n-1)}&=&{i \over 2} \de \theta^{AB}  \int U_{AB}\label{CSSW2n-1}
\\
&=&{i \over 2} \de \theta^{AB} \int
 Tr\Big(\sum_{i=2}^{n-1}R^{i-1}DR_{A}(R^{n-i})_{B}\Big)
\nonumber\\
&=&{i \over 2} \de \theta^{AB} \int Tr \Big( RDR_A\sum_{k=0}^{n-3}
(k+1)R^{n-3-k}R_BR^k\Big)
\nonumber
\ena
where in the last equality we have evaluated the contraction
operator $i_B$ on $R^{n-i}$ , integrated by parts and cyclically reordered the terms in the sum.
\sk

 This variation is zero for $n=1,2$. The first nonvanishing SW
 variation of a Chern-Simons action  occurs for $n=3$.  In particular in three dimensions
 the SW expansion of the  noncommutative Chern-Simons action
 equals the commutative  Chern-Simons action; this result,
 for Moyal-Groenewold noncommutativity, was obtained in
 \cite{Grandi:2000av}\footnote{
We mention that the solution to (\ref{SWcondition}) is not unique. For example
      if $\hat A$ is a solution, any finite noncommutative gauge
      transformation of $\hat A$ gives another solution. Another
      source of ambiguities is related to field redefinitions of the
      gauge potential. Use of a nonstandard solution to SW map
may lead to different results, see   \cite{Vilar} where  a nontrivial second order  in
$\theta$ expansion of the $D=3$ CS action is constructed via a nonstandard
solution to SW map.}.

In higher dimensions the variation is nonvanishing, and is expressed in
terms of the gauge covariant quantities $R$, $R_A$ and their covariant derivatives.
\sk
\sk
\noi {\bf Slowly varying fields and invariance of NC CS action
  under SW map}\\

\noi In \cite{SW} (Section 4.1) it is shown that for slowly varying field strength the
noncommutative  and commutative Dirac-Born-Infeld actions coincide (up to
a redefinition of the coupling constant and of the metric).
In our geometric framework, where the noncommutativity is given by the vector fields
$\{X_A\}$, we can consider field strengths that are slowly varying
just along the noncommutative directions. The gauge covariant
formulation of the slowly varying field strength condition is  $L_AR\sim 0$.
In this case the noncommutative and commutative CS actions
coincide. Indeed  $DR_A=i_ADR+Di_AR=L_AR\sim 0$, and hence
$U_{AB}\sim 0$ (cf. (\ref{CSSW2n-1})).

This result holds in particular in the $U(1)$ case where the slowly
varying field strenght condition  on commutative spacetime
reads $\ell_AR^{commutative}\sim 0$. For nondegenerate Moyal-Groenewold
noncommutativity this is equivalent to $\partial_\mu
R^{commutative}_{\nu\sigma}\sim 0$
that is the condition considered in \cite{SW}.
\sk\sk

\sect{Extended CS actions from NC CS actions}

Consider the Taylor series expansion of a NC CS action in powers of
$\theta$ (the $\theta$ dependence is due to the $\star$-product and to
the SW map),
\eq
\int \! L_{CS^\star}^{(2n-1)}= \int\! L^{(2n-1)}_{CS}\,+\,\frac{i}{2}\theta^{AB}\!\int\! L_{CS\;AB}^{(2n-1)\,'}\,-\,
\frac{1}{8}\theta^{AB}\theta^{EF}\!\int \!L_{CS\;ABEF}^{(2n-1)\;''} \,+\, {\cal O}(\theta^3)\label{eq5.1}
\en
where $\int\! L^{(2n-1)}_{CS}=\int \!
L_{CS^\star}^{(2n-1)}|_{\theta=0\,}$, $\frac{i}{2}\int\! L_{CS\;AB}^{(2n-1)\,'}=
\frac{\partial~}{\partial\theta^{AB}}\! \int \! L_{CS^\star}^{(2n-1)}|_{\theta=0}$, etc..
The right hand side is a higher derivative action on commutative
spacetime. It is an extension, with $\theta$ corrections, of the
commutative CS action
$\int\! L^{(2n-1)}_{CS}$. The result of the previous section
gives the first order $\theta$-correction to the commutative CS theory, so that the action of
the extended CS theory reads
\eq
\int\! L^{(2n-1)}_{CS\,}+\,
{i \over 2}  \theta^{AB} \int Tr \Big( RDR_A\sum_{k=0}^{n-3}
(k+1)R^{n-3-k}R_BR^k\Big)~.\label{extendedCS}
\en
We notice that this action is well defined for any gauge group $G$,
and that it has the same (off shell) degrees of freedom as the
usual CS action. Like in modified gravity theories the $\theta$
correction is just a further interaction term among the fields.

\sk
\noi {\bf Note }
In Section 2 we had to consider NC CS actions with fields valued
in a Lie algebra representation $T^a$ closed under the matrix product
rather than under commutators (recall (\ref{closurefields})). This  in
general is a severe restriction on the gauge group $G$ (typically
requiring $G=U(N)$). Here however, the SW map relates the noncomutative
fields corresponding to products of generators $T^aT^b\ldots$ to the
classical gauge fields of any gauge group $G$ \cite{JSSW, JMSW}.
Thus the SW map allows to define NC CS actions for any gauge group.
\sk

\subsection{$D=5$ CS form to second order in $\theta$}
To evaluate the second order variation of $\int L_{CS^\star}^{(5)}$,
\eq
\delta_\theta\delta_\theta \int L_{CS^\star}^{(5)}=\frac{i}{2}\de_\theta
\de\theta^{AB}\int RDR_A R_B
\en
we need the SW variation of $R_B$ and $DR_A$. The first one is
easily obtained by applying the contraction operator $i_B$ to the SW
variation of the curvature 2-form $R$, eq. (\ref{SWonR}). The second
one is obtained by summing the SW variation of $dR_A$ to the SW variation
of $\{\Om,R_A\}$, that is evaluated using
(\ref{omequivsw}) and  (\ref{SWPQ}). The result is
\eqa
\delta_\theta R_B&=&\frac{i}{4}\theta^{CD}\Big( \{\Om_C,
\Lfat_D R_B\}-2\{R_{CB},R_D\}\Big)~,\nonumber\\[.2em]
\delta_\theta DR_A&=&\frac{i}{4}\theta^{CD}\Big( \{\Om_C,
\Lfat_D DR_A\}+2\{DR_C,R_{DA}\} - L_A [R_C,R_D]\Big)~.
\ena
 Next with the help of   (\ref{SWPQ}) we compute $\delta_\theta DR_AR_B$ and
 finally using (\ref{intPQ}) we obtain\footnote{the last two terms are obtained  from the term $-2DR_A(L_DR_B)L_CR$ by use
of the Cartan identity
$L_D=i_DD+Di_D$, integrating by parts the exterior covariant
derivative, observing that $D DR_A=-[R,R_A]$ and renaming indices.}
\eqa \label{CS5''}
\delta_\theta\delta_\theta \int L_{CS^\star}^{(5)}&\!\!=\!&\frac{i}{2}\de_\theta
\de\theta^{AB}\!\!\int Tr( R\,DR_A R_B)  \\[.6em]
&&\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!=-\frac{1}{4}\delta \theta^{{AB}}\delta \theta^{CD}\!
\int\! Tr\Big(DR_A\Big( \{R_B R,R_{CD}\}+  \{R_B, R_{CD}R\}  +\, 2\{ R_{BC},R_D\}R + \nonumber \\
&&\!\!\!\!\!\!\!+2 \{R_{BC}, R_D R \}-2[R_B,R_C R_D] +2[R_{BC},[R,R_D]]-2i_D(DR_B)DR_C

\Big)\Big)\nonumber
\ena
The expansion at second order in power series
of $\theta$ of the $D=5$ noncommutative CS action (\ref{starCS5}) is then given by
\eq
\int\! L^{(5)}_{CS^\star}=\int\! L^{(5)}_{CS\,{}}+\frac{i}{2}\theta^{AB}\!\int\! Tr(RDR_AR_B)-
\frac{1}{8}\theta^{AB}\theta^{CD}\!\int \!L_{CS\;ABCD}^{(5)\;''}+{\cal O}(\theta^3) \label{CSextended}
\en
where  $L_{CS\;ABCD}^{(5)\;''}$ is the integrand in (\ref{CS5''}).

\subsection{Extended $D=5$ CS gravity to first order in $\theta$}

CS gravities and supergravities \cite{ChamD5,Troncoso1998,Zanelli2005,Zanelli2012} present interesting alternatives to standard (super)gravities
in odd dimensions. Indeed CS gravities are a particular case of Lovelock gravities \cite{Lovelock}, with at most second order equations for the metric. Moreover the gauge (super)group contains the anti-de Sitter (super)algebra, so that the theory
is translation invariant and does not have dimensionful coupling constants. One can use group contraction to recover the (super)Poincar\'e algebra, but retrieving the Einstein-Hilbert term in this limit is problematic. There are however techniques (S-expansion method \cite{Izaurieta2009}) to recover Poincar\'e gravity from CS gravity with a particular ``expanded" gauge algebra.

We study here the example of $D=5$ Chern-Simons AdS pure gravity. The commutative
$SU(2,2)$ connection and curvature are given by
 \eq
 \Om = {1\over 4} \om^{ab} \ga_{ab} - {i \over 2} V^a \ga_a, ~~R = {1\over 4} R^{ab} \ga_{ab} - {i \over 2} R^a \ga_a
 \en
 \noi with
 \eq
 R^{ab}= d \om^{ab}-\om^{ac} \om_c^{~b}+V^a V^b,~~R^a=dV^a-\om^{a}_{~c} V^c
  \en
  \noi all indices $a,b,...$ running on five values. The $D=5$ gamma matrices $\ga_a$, together with their
  commutators $\ga_{ab} \equiv \unmezzo [\ga_a,\ga_b]$, close on the $D=5$ AdS algebra $SU(2,2) \approx SO(2,4)$. The $SU(2,2)$ connection contains both the vielbein $V^a$ and the spin connection $\om^{ab}$, and correspondingly the $SU(2,2)$ curvature contains both the AdS curvature
  $R^{ab}$ and the torsion $R^a$.
  After applying the SW map to the $D=5$ noncommutative CS action (\ref{starCS5}), and using the expression for the first order correction in (\ref{CSextended}), we obtain the extended $D=5$ AdS gravity action:
   \eqa
\int L^{(5)}_{CS^\star} &\!\!\!=\!\!\!& \int {1\over 8} \epsilon_{abcde} (R^{ab} R^{cd} V^e + {2\over 3} R^{ab} V^c V^d V^e + {1\over 5} V^a V^b V^c V^d V^e ) +  \\
&&+ \unmezzo \theta^{AB} \! \Big(R^{ab} DR^{ac}_A R^{bc}_B + 2 R^{ab}  V^a R_A^c R^{bc}_B + R^{ab} DR^a_A R^b_B + \nonumber \\
&&
+ R^{ab} R^{ac}_A V^c R^b_B + R^a D(R^{ab}_A R^b_B)  +2 R^a V^{[a} R^{b]}_A R^b_B+ R^a R^{bc}_A V^c R^{ab}_B\Big) +O(\theta^2),\nonumber
\ena
where $D$ is the $SO(1,4)$ Lorentz covariant derivative (with connection $\om^{ab}$).

  \sk\sk
{\noi \bf Acknowledgements}\\
We thank Marija Dimitrijevi\'{c} for useful discussions and insights
concerning initial calculations on NC CS actions.
P.A. acknowledges the hospitality of Faculty of Physics, University of
Belgrade during commencement of this work, and of Charles University in Prague,
Faculty of Mathematics and Physics, Mathematical Institute, during its
completion.

This work is partially supported by the Inter-Government Executive
Programme 2013-2015 for scientific and technical cooperation between
Italy and Serbia,  project RS13MO8 ``Gravity in quantum spacetime".

\appendix

\sect{The SW variation of $Tr(R^n)$}\label{SWTrRn}

We first recall some formulas for the variation of a
$\wedge_\star$-product of fields \cite{Aschieri:2012in}. We omit writing explicitly
star products.
\sk
\noi {\bf{Lemma 1}}~ Let $P,Q$ be arbitrary exterior forms. Then
\eq
\{\Om^{}_{[A},\Lfat^{}_{B]}P\}
Q+P\{\Om^{}_{[A},\Lfat^{}_{B]}Q\} + 2\ell^{}_{[A}P\ell^{}_{B]}Q
=\{\Om^{}_{[A},\Lfat^{}_{B]}(P Q)\} +2L^{}_{[A}P L^{}_{B]}Q\,,
\en
where we recall that the  bracket ${}_{[A\; B]}$ denotes antisymmetrization of the indices $A$ and $B$
with weight 1, so that for example
$\Omhat_{[A} \Lfat_{B]} =\frac{1}{2}(\Omhat_A\Lfat_B-\Omhat_B\Lfat_A)$.
The proof is by a straightforward calculation.
\sk
\noi {\bf{Lemma 2}}~ Let  $P,Q$ be arbitrary exterior forms  and
$P'_{[A\,B]}, Q'_{[A\,B]}$ be defined by their variations via the equations
\eqa
& & \de_\theta P= {i \over 4} \de \theta^{AB} \Big( \{\Om_{A},\Lfat_{B}P\} +
P'_{[A\,B]} \Big)~,\\
& &
 \de_\theta Q= {i \over 4} \de \theta^{AB} \Big( \{\Om_{A},\Lfat_{B}Q\} +
Q'_{[A\,B]} \Big)~.
\ena
Then
\eq
 \de_\theta (PQ)= {i \over 4} \de \theta^{AB} \Big(\{\Om^{}_{A},\Lfat^{}_{B}(P  Q)\}
+2L^{}_{A}P L^{}_{B}Q
+P'^{}_{[A\,B]} Q+P
Q'^{}_{[A\,B]}\Big)~.\label{SWPQ}
\en
This result easily follows from the previous lemma and from  the
$\wedge_\star$-product variation
$P\wedge_{\star_{\theta+\delta\theta}}Q=P\wedge_{\star_\theta} Q+
\frac{i}{2}\delta\theta^{AB}\ell_AP\wedge_{\star_\theta} \ell_BQ$.
\sk
\noi We can now apply formula (\ref{SWPQ}) to  $\de_\theta R^n$  written as $ \de_\theta (RR^{n-1})$.
Recalling the SW variation of $R$ given in (\ref{SWonR}), and defining
$(R^{n-1})'_{[A B]} $ from
\eq
  \de_\theta R^{n-1} = {i \over 4} \de \theta^{AB} \Big( \{\Om_A, \Lfat_B  R^{n-1} \} + (R^{n-1})'_{[AB]} \Big)
   \en
  one finds
 \eq
  \de_\theta R^n = {i \over 4} \de \theta^{AB} \Big( \{ \Om_A, \Lfat_B R^n \} + 2 L_A R L_B R^{n-1}
   - 2 R_A R_B R^{n-1} + R (R^{n-1})'_{[AB]} \Big)~.
  \en
Comparison with $  \de_\theta R^{n} = {i \over 4} \de \theta^{AB}
\Big( \{\Om_A, \Lfat_B  R^{n} \} + (R^{n})'_{[AB]} \Big)$
leads to the recursive relation
   \eqa
    (R^n)'_{[AB]}&=&2  L_{[A} R L_{B]} R^{n-1} - 2 R_{[A} R_{B]} R^{n-1} + R ( R^{n-1})'_{[AB]}\nonumber\\
    &=&2  D R_{[A} D (R^{n-1})_{B]} - 2  R_{[A} R_{B]} R^{n-1} + R ( R^{n-1})'_{[AB]}
\ena
with initial condition $R'_{[AB]}=-[R_A,R_B]=-2R_{[A}R_{B]}$.    This
recursive relation is easily seen to be solved by
     \eq
 (R^n)'_{[AB]} = 2\sum_{i=1}^{n-1}R^{i-1}DR_{[A}D(R^{n-i})_{B]}-2\sum_{i=1}^{n}R^{i-1}R_{[A}R_{B]}R^{n-i}~.
\en
    Using this expression, the Leibniz rule for $\Lfat_B$ and
    the identity $\Lfat_B\Omega_A=R_{BA}$,  we can rewrite the SW variation of $Tr(R^n)$ as
     \eqa
         \de_\theta Tr(R^n)&=& {i \over 4} \de \theta^{AB} Tr \Big(
       \Lfat_B \{\Om_A,R^{n} \} +\{R_{AB},R^{n} \} -2\sum_{i=1}^{n}R^{i-1}R_AR_BR^{n-i} +\nonumber\\
& &
\,+ \,2\sum_{i=1}^{n-1}R^{i-1}DR_AD(R^{n-i})_B
\Big)  \nonumber\\

          &=& \frac{i}{2} \de \theta^{AB} Tr \Big(
       \ell_B \{\Om_A,R^{n} \} +R_{AB}R^{n} -nR_AR_B
       R^{n-1}+ \ell_C \check{Q}^C_{AB} +\nonumber\\
& &\,+\sum_{i=1}^{n-1}
R^iR_A(R^{n-i})_B-\sum_{i=1}^{n-1} R^{i-1}R_AR(R^{n-i})_B+D \sum_{i=1}^{n-1}R^{i-1}DR_A(R^{n-i})_B\Big)
\nonumber\\ \ena
 \noi where in the third line we have used cyclic reorderings to
 simplify the first line; the effect
 of these reorderings is the addition of a total Lie derivative term
 $ \ell_C \check{Q}^C_{AB}$ that can be explicitly computed.
The last line is the rewriting of the second line using the Leibniz rule for $D$:
$R^{i-1}DR_AD(R^{n-i})_B=
D \big(R^{i-1}DR_A(R^{n-i})_B\big)-R^{i-1}DDR_A (R^{n-i})_B$
and $DDR_A=-RR_A+R_AR$.

We next use the Leibniz rule for the contraction operator in  the
form $R_A(R^{n-i})_B= R_AR_BR^{n-i-1}+R_AR(R^{n-i-1})_B$ and then cyclic reorder  the first and
second terms in the last line: they drastically simplify to just two
summands
(up to a total Lie derivative absorbed in the term $\ell_C \check{Q}^C_{AB}$),
and we obtain
\eqa
 \de_\theta Tr(R^n)&=&
\frac{i}{2} \de \theta^{AB} Tr \Big(
      \ell_B \{\Om_A,R^{n} \} +R_{AB}R^{n} -R_AR_B
      R^{n-1}-R_AR(R^{n-1})_B+\nonumber \\
& &\,+D\sum_{i=1}^{n-1}R^{i-1}DR_A(R^{n-i})_B+ \ell_C
\check{Q}^C_{AB}\Big)\nonumber \\
&=&\frac{i}{2} \de \theta^{AB} Tr \Big(
      \ell_B \{\Om_A,R^{n} \}
      +\frac{1}{n+1}i_Bi_AR^{n+1}+
      \ell_C \check{Q}^C_{AB}\Big)+\nonumber\\
& & \,+\frac{i}{2} \de \theta^{AB} \,d\,Tr\Big(\sum_{i=2}^{n-1}R^{i-1}DR_A(R^{n-i})_B\Big)~
\ena
To derive the last equality we observe that up to cyclic reorderings (absorbed in the $\ell_C \check{Q}^C_{AB}$
term):

\noi $\bullet$  $Tr(i_Bi_AR^{n+1})=(n+1) Tr[R_{AB}R^n-R_A(R^n)_B]=(n+1) Tr[R_{AB}R^n-R_AR_BR^{n-1}-R_AR(R^{n-1})_B]$,

\noi $\bullet$ the covariant derivative can be
replaced by the exterior derivative,

\noi $\bullet$ the first term in the sum
$\delta\theta^{AB}d\,Tr\big(\sum_{i=1}^{n-1}R^{i-1}DR_A(R^{n-i})_B\big)$, i.e.
$\delta\theta^{AB}d\,Tr  \big(DR_A(R^{n-1})_B\big)$,
vanishes.\footnote{one proves that up to cyclic reorderings Tr  $\big(DR_A(R^{n-1})_B\big)$ is a total derivative,
and therefore its exterior derivative vanishes (since $d^2=0$). Indeed
$Tr\big(DR_{[A}(R^{m})_{B]}\big)=
Tr \big(\sum_{j=0}^{m-1}DR_{[A}R^jR_{B]}R^{m-j-1}\big)$
and the terms in this sum combine in pairs to give total derivatives
(for $m$ odd the central term is by itself a total derivative). For example up to cyclic reorderings
$Tr \big(DR_{[A}R^jR_{B]}R^{m-j-1}+DR_{[A}R^{m-j-1}R_{B]}R^j\big)=
Tr \big(DR_{[A}R^jR_{B]}R^{m-j-1}+ R_{[B}R^jDR_{A]}R^{m-j-1}\big)=
Tr \big(D(R_{[A}R^jR_{B]}R^{m-j-1})\big)= d Tr \big(R_{[A}R^jR_{B]}R^{m-j-1}\big)$.}

\sk
\noi In conclusion the SW variation of $Tr(R^n)$ is given by
\eqa
 \de_\theta Tr(R^n)&=&\nonumber
\frac{i}{2} \de \theta^{AB} Tr \Big(
      \frac{1}{n+1}i_Bi_AR^{n+1}\Big) +\frac{i}{2} \de \theta^{AB} \,d\,Tr\Big(\sum_{i=2}^{n-1}R^{i-1}DR_A(R^{n-i})_B\Big)\nonumber\\~&&+
    \frac{i}{2} \de \theta^{AB}  \ell_C {Q}^C_{AB}
\ena
where the sum $Tr(\ell_B\{\Om_A,R^n\}+\ell_C\check{Q}^C_{AB})$ has been renamed  $\ell_CQ^C_{AB}$.

\sect{Useful identities} \label{UI}
{\it Cartan formulae}\\
The usual Cartan calculus formulae simplify if we consider commuting
vector fields $X_A$, and read \\
\[
\begin{array}{ll}
\,\ell_A=i_Ad+di_A ~, &~~~L_A=i_AD+D i_A \\
\,[\ell_A,\ell_B]=0~, &~~~[L_A,L_B]=i_Ai_B R \\
\,[\ell_A,i_B]=0~, &~~~[L_A,i_B]=0 \\
\,i_Ai_B+i_Bi_A=0~, &~~~d\circ d=0~,  ~~~~~~~D\circ D=- R~.
\end{array}
\]
\sk
\noi Other useful identities are (cf. also \cite{Aschieri:2012in}):
\eqa
 & & \theta^{AB} L_A L_B P = - \unmezzo \theta^{AB} [R_{AB},P ]~\label{!!!!} \\
 & & \theta^{AB} \Lfat_A \Om_B  =  \theta^{AB} R_{AB} \\

 & & \theta^{AB}\int Tr\Big( \{\Om_A,I\!\!L_B(PQ)\} +2L_AP\,L_B
Q\,\Big)=\,\theta^{AB}\int Tr \Big(\{R_{AB}, P\}Q\Big)~\label{intPQ}
\ena
where  $L_AP=\ell_AP-[\Om_A,P]$,
$\Lfat_A\equiv \ell_A+L_A$ and $R_A\equiv i_AR$, $R_{AB} \equiv i_B
i_A R $.

\sect{Gamma matrices in $D=5$ }\label{gamma}

We summarize in this Appendix our gamma matrix conventions in $D=5$.
\eqa
& & \eta_{ab} =(1,-1,-1,-1,-1),~~~\{\ga_a,\ga_b\}=2 \eta_{ab},~~~[\ga_a,\ga_b]=2 \ga_{ab}, \\
& & \ga_0\ga_1\ga_2\ga_3\ga_4=-1,~~~\epsi_{01234} =  \epsi^{01234}=1, \\
& & \ga_a^\dagger = \ga_0 \ga_a \ga_0,  \\
& & \ga_a^T =  C \ga_a C^{-1}, ~~~C^2 =-1,~~~C^\dagger=C^T =-C
\ena

\subsection{Gamma identities}

\eqa
 & &\ga_a\ga_b= \ga_{ab}+\eta_{ab}\\
 & & \ga_{abc}  = {1 \over 2} \epsilon_{abcde} \ga^{de}\\
 & & \ga_{abcd}  = - \epsilon_{abcde} \ga^{e}\\
 & &\ga_{ab} \ga_c=\eta_{bc} \ga_a - \eta_{ac} \ga_b +{1 \over 2} \epsilon_{abcde} \ga^{de}\\
 & &\ga_c \ga_{ab} = \eta_{ac} \ga_b - \eta_{bc} \ga_a+{1 \over 2} \epsilon_{abcde} \ga^{de}\\
 & &\ga^{ab} \ga_{cd} = - \epsi^{ab}_{~~cde}\ga^e - 4 \de^{[a}_{[c} \ga^{b]}_{~~d]} - 2 \de^{ab}_{cd}
 \ena
\noi where
$\delta^{ab}_{cd} \equiv \frac{1}{2}(\delta^a_c\delta^b_d-\delta^b_c\delta^a_d)$,
and indices antisymmetrization in square brackets has total weight $1$.


TITLE: Prove sequence convergence using Cauchy Sequences
QUESTION [0 upvotes]: How should I prove convergence using Cauchy sequences $$ \sum_{k=1}^{n} \frac{\sin({k^{3}+1)}}{(4k+1)(4k+5)}  $$
I tried starting with the definition $\forall\varepsilon>0,\exists N\in\mathbb{N}\ \forall n,p\geq N: |x_{n+p}-x_n|<\varepsilon$
$$ \left|\frac{\sin(2)}{(5)(9)} +\frac{\sin(9)}{(9)(13)}+ ...+\frac{\sin({n^{3}+1)}}{(4n+1)(4n+5)}+...+\frac{\sin({(n+p)^{3}+1)}}{(4(n+p)+1)(4(n+p)+5)}-\left(\frac{\sin(2)}{(5)(9)} +\frac{\sin(9)}{(9)(13)}+ ...+\frac{\sin({n^{3}+1)}}{(4n+1)(4n+5)}\right)\right|.$$
thus, after subtracting terms
$$\left|\frac{\sin({(n+1)^{3}+1)}}{(4n+5)(4n+9)}+...+\frac{\sin({(n+p)^{3}+1)}}{(4(n+p)+1)(4(n+p)+5)}\right|$$
Since $\:-1\leq \sin(x) \leq 1\:$ and $\:n^2 \lt (4n+5)(4n+9)$ then $$\left|\frac{\sin({(n+1)^{3}+1)}}{(4n+5)(4n+9)}+...+\frac{\sin({(n+p)^{3}+1)}}{(4(n+p)+1)(4(n+p)+5)}\right| \lt\sum_{}^{\infty}{\frac{1}{n^2}}.$$
How do we find $n$ if the result of our greatest sum $\sum_{}^{\infty}{\frac{1}{n^2}}$, equals $\frac{\pi^2}{6}$

REPLY [2 votes]: You have
$$\begin{eqnarray}
|x_{n+p}-x_n|
& = &\left|\sum_{k=n+1}^{n+p} \frac{\sin (k^2+1)}{(4k+1)(4k+5)}\right|\\
&\leqslant & \sum_{k=n+1}^{n+p} \left|\frac{\sin (k^2+1)}{(4k+1)(4k+5)}\right|\\
& \leqslant& \sum_{k=n+1}^{n+p} \frac{1}{(4k+1)(4k+5)}\\
&=& \frac14 \sum_{k=n+1}^{n+p} \left(\frac{1}{(4k+1)}-\frac{1}{(4k+5)}\right)\\
&=& \frac14 \left( \frac{1}{4n+5} -\frac{1}{4(n+p)+5} \right)\\
&\leqslant & \frac{1}{4(4n+5)}
\end{eqnarray}
$$
and so choosing $N>\frac{1}{16\epsilon}$ will provide an $N$ for you to use in proving that $\{x_n\}_{1}^{\infty}$ is Cauchy.