text:
\section{Introduction}

It is well-known that the shape of the Euclidean unit ball
$\mathbf{B}_2=\{\,\mathbf{x}:\sum_{i=1}^nx_i^2\leq1\,\}$
has spectacular geometric properties with respect to other shapes. For
instance, the sphere has the smallest surface area among all surfaces enclosing a given volume and it encloses the largest volume among all closed surfaces with a given surface area; Hilbert and Cohn-Vossen \cite{hilbert} even describe eleven geometric properties of the sphere!

But $\mathbf{B}_2$ has also another spectacular (non-geometric) property related to its algebraic representation which is
obvious even to people with a little background in Mathematics:
Namely, its defining polynomial
$\mathbf{x}\mapsto g_2(\mathbf{x}):=\sum_{i=1}^nx_i^2$ cannot be simpler!! Indeed, among all nonnegative quadratic  homogeneous polynomials
$\mathbf{x}\mapsto g(\mathbf{x})=\sum_{i\leq j}g_{ij}x_ix_j$ that define a bounded ball $\{\,\mathbf{x}:g(\mathbf{x})\leq 1\,\}$,
$g_2$ is the one that minimizes the ``cardinality norm" $\Vert g\Vert_0:=\#\{\,(i,j):g_{ij}\neq0\,\}$ (which actually is not a norm).
Only $n$ coefficients of $g_2$ do not vanish and there cannot be less than $n$ non zero coefficients to define a bounded ball $\{\,\mathbf{x}: g(\mathbf{x})\leq1\,\}$. The same is true for the $d$-unit ball $\mathbf{B}_d=\{\,\mathbf{x}:\sum_{i=1}^nx_i^d\leq1\,\}$ and its defining polynomial
$\mathbf{x}\mapsto g_d(\mathbf{x})=\sum_ix_i^d$ for any even integer $d$,
when compared to any other nonnegative homogeneous polynomial $g$ of degree $d$ whose
sublevel set $\{\,\mathbf{x}:g(\mathbf{x})\leq1\,\}$ has finite Lebesgue volume. Indeed, again $\Vert g_d\Vert_0=n$, i.e.,
out of potentially ${n+d-1\choose d}$ coefficients only $n$ do not vanish! In other words,
\begin{equation}
\label{norm-ell0}
g_d\,=\,\displaystyle\arg\min_g\,\{\,\Vert g\Vert_0:\: {\rm vol}\,(\{\mathbf{x}:g(\mathbf{x})\leq1\,\})\,\leq\,1\,\}\end{equation}
where the minimum is taken over all homogeneous polynomials of degree $d$.

So an natural question which arises is as follows:
{\it In view of the many ``geometric properties" of the unit ball $\mathbf{B}_d$, is
the  ``algebraic sparsity" of its representation $\{\mathbf{x}:\sum_ix_i^d\leq1\,\}$ a coincidence or does it also corresponds
to a certain extremal property on all possible representations?}

So we are interested in the following optimization problem in computational geometry
and with an algebraic flavor.

{\it Given an even integer $d$, determine the nonnegative homogeneous polynomial
$g^*$ of degree $d$ whose $\ell_1$-norm $\Vert g^*\Vert_1$ (or $\ell_2$-norm $\Vert g^*\Vert_2$)
of its vector of coefficients is minimum among all degree-$d$ nonnegative homogeneous polynomials
with same (fixed) volume of their sublevel set $\mathbf{G}=\{\,\mathbf{x}:g(\mathbf{x})\leq 1\,\}$. That is, solve:}
\begin{equation}
\label{relax-0-1}
\inf_{g}\,\{\,\Vert g\Vert_{p=1,2}:\: {\rm vol}\,(\mathbf{G})\,=\,1\,;\:\mbox{$g$ homogeneous of degree $d$}\,\}.\end{equation}
In particular, {\it Can the parsimony property
of the $L_d$-unit balls be recovered from (\ref{relax-0-1}) with the $\ell_1$-norm $\Vert g\Vert_1$
(instead of minimizing the nasty function $\Vert \cdot\Vert_0$ in (\ref{norm-ell0}))?}\\

By homogeneity, this problem also has the equivalent formulation:  {\it Among all homogeneous polynomials
$g$ of degree $d$ and with constant norm $\Vert g\Vert_1=1$ (or $\Vert g\Vert_2=1$) find the one
with level set $\mathbf{G}$ of minimum volume.}\\

One goal of this paper is to prove that (\ref{relax-0-1}) is a convex optimization problem with a {\it unique optimal solution},
which is the same as $g_d$ in (\ref{norm-ell0}) when one minimizes the $\ell_1$-norm $\Vert g\Vert_1$.
In addition $g_d$ cannot be an optimal solution of (\ref{relax-0-1}) when one minimizes
the $\ell_2$-norm $\Vert g\Vert_2$ (except when $d=2$).
This illustrates in this context of  computational geometry that again,
the sparsity-induced $\ell_1$-norm does a perfect job
in the relaxation (\ref{relax-0-1}) (with $\Vert\cdot\Vert_1$) of problem (\ref{norm-ell0}) with $\Vert \cdot\Vert_0$.
This convex ``relaxation trick"
in (non convex) $\ell_0$-optimization has been used successfully in several important applications; see e.g.
Cand\`es et al. \cite{candes}, Donoho \cite{donoho1}, Donoho and Elad \cite{donoho2}
in compressed sensing applications and Recht et al. \cite{recht} for matrix applications (where the
small-rank induced {\it nuclear norm} is the matrix analogue of the $\ell_1$-norm). For more details on optimization with sparsity constraints and/or sparsity-induced penalties,
the interested reader is referred to Beck and Eldar \cite{beck} and Bach et al. \cite{bach}.\\

To address our problem we consider the following framework:
Let $\mathbf{Hom}_{d}\subset\mathbb{R}[\mathbf{x}]_{d}$ be the vector space of homogeneous polynomials of even degree $d$,
and given $g\in\mathbf{Hom}_{d}$, let $\mathbf{g}=(g_\alpha)$ be its vector of coefficients, i.e.,
\[\mathbf{x}\mapsto g(\mathbf{x})\,=\,\sum_\alpha g_\alpha\,\mathbf{x}^\alpha \:\left(=\sum_{\alpha}g_\alpha\,\mathbf{x}_1^{\alpha_1}\cdots \mathbf{x}_n^{\alpha_n}\right),\qquad \sum_i\alpha_i=d,\]
with standard $\ell_1$-norm $\Vert g\Vert_1=\vert \mathbf{g}\vert=\sum_{\alpha}\vert g_\alpha\vert$. With any
$g\in\mathbf{Hom}_{d}$ is associated its sublevel set $\mathbf{G}\subset\mathbb{R}^n$ defined by:
\begin{equation}
\label{set-G}
\mathbf{G}\,:=\,\{\,\mathbf{x}\in\mathbb{R}^n\::\: g(\mathbf{x})\,\leq\,1\,\},\qquad g\in\mathbf{Hom}_{d}.
\end{equation}
In particular, with $\mathbf{x}\mapsto g^*(\mathbf{x}):=\sum_{i=1}^nx_i^{d}$, the sublevel set $\mathbf{G}^*$ is nothing less than
the standard $d$-unit ball
\[\mathbf{B}_{d}\,=\,\{\,\mathbf{x}:\sum_{i=1}^nx_i^{d}\leq1\,\}\,=:\,\{\,\mathbf{x}:\Vert \mathbf{x}\Vert^{d}_{d}\,\leq1\,\},\]
whose Lebesgue volume ${\rm vol}\,(\mathbf{B}_d)$ is denoted $\rho_d$.
(When $g\in\mathbf{Hom}_{d}$ is convex then $\mathbf{x}\mapsto g(\mathbf{x})$ defines a norm $\Vert\mathbf{x}\Vert_g:=g(\mathbf{x})^{1/d}$ with $\mathbf{G}$ as associated unit ball.)

\subsection*{Contribution}

(a) In a first contribution we prove that
the optimization problem:
\begin{equation}
\label{pb1-intro}
\mathbf{P}_1:\quad \inf_g\,\{\,\Vert g\Vert_1\,:\: {\rm vol}\,(\mathbf{G})\,\leq\,\rho_d\,;\quad g\in\mathbf{Hom}_{d}\,\},\end{equation}
has a unique optimal solution $g^*_1$ which is the $L_d$-norm polynomial $\mathbf{x}\mapsto \Vert\mathbf{x}\Vert_{d}^{d}$.
Observe that $g^*_1$ has the minimal number $n$ of coefficients
over potentially $s(d):={n-1+d\choose d}$  coefficients. (Indeed for a polynomial $g\in\mathbf{Hom}_{d}$
with $m<n$ non zero coefficients, its sublevel set $\mathbf{G}$ cannot have finite Lebesgue volume.)
Therefore the $L_d$-norm polynomial $g^*_1$ associated with the unit ball $\mathbf{B}_d$ is the ``sparsest" solution among all $g\in\mathbf{Hom}_{d}$ such that ${\rm vol}\,(\mathbf{G})\leq{\rm vol}\,(\mathbf{B}_d)$.
In particular, $g^*_1$ not only solves problem $\mathbf{P}_1$ but also solves the non convex optimization problem
\[\mathbf{P}_0:\quad \inf_g\,\{\,\Vert g\Vert_0\,:\: {\rm vol}\,(\mathbf{G})\,\leq\,\rho_d\,;\quad g\in\mathbf{Hom}_{d}\,\},\]
of which $\mathbf{P}_1$ is a ``convex relaxation". But this is also equivalent to state that among all
homogeneous polynomials of degree $d$ with constant $\ell_1$-norm,
the $L_d$-unit ball is the one with minimum volume ${\rm vol}\,(\mathbf{B}_d)\leq{\rm vol}(\mathbf{G})$.

(b) In a second contribution we consider the $\ell_2$-norm version of (\ref{pb1-intro}):
\begin{equation}
\label{pb2-intro}
\mathbf{P}_2:\quad \inf_g\,\{\,\Vert g\Vert_2\,:\: {\rm vol}\,(\mathbf{G})\,\leq\,\rho_d\,;\quad g\in\mathbf{Hom}_{d}\,\},\end{equation}
with weighted Euclidean norm $g\mapsto \Vert g\Vert_2$ defined by:
\[\Vert g\Vert_2^{2}\,:=\,\sum_{\vert\alpha\vert=d} c_\alpha\,g_\alpha^2,\qquad g\in\mathbf{Hom}_{d},\quad
\mbox{where }c_\alpha:=\frac{(d){\rm !}}{\alpha_1{\rm !}\cdots\alpha_n{\rm !}}.\]
We then show that $\mathbf{P}_2$ also has a unique optimal solution $g^*_2$,
but in contrast to the optimal solution $g^*_1$ of problem $\mathbf{P}_1$, $g^*_2$ is not sparse at all! This is because
one can show that all ${n-1+d\choose d}$ coefficients of the form $g^*_{2\beta}$ with $\vert\beta\vert=d/2$ are non-zero.
In addition,
$g^*_2$ is a particular sum of squares (SOS) polynomial as it is a sum of $d$-powers of linear forms.
(Notice that $g^*_1$ is also a (very particular and simple) sum of $d$-powers of linear forms.) In particular, when $d=4$
the optimal solution of $\mathbf{P}_2$ is the Euclidean ball $\{\mathbf{x}:\sum_ix_i^2\leq1\}$ which has the equivalent quartic representation
$\{\mathbf{x}:(\sum_{i=1}^nx_i^2)^2\leq1\}$ and the SOS quartic polynomial $\mathbf{x}\mapsto (\sum_{i=1}^nx_i^2)^2$ solves $\mathbf{P}_2$.\\

(c) We also consider the SOS (sum of squares) version of $\mathbf{P}_1$, that is one now searches for
a degree-$d$ SOS homogeneous polynomial $g_\mathbf{Q}(\mathbf{x})=\mathbf{v}_{d/2}(\mathbf{x})\mathbf{Q}\mathbf{v}_{d/2}(\mathbf{x})$, $\mathbf{Q}\succeq0$,
(where $\mathbf{v}_{d/2}(\mathbf{x})=(\mathbf{x}^\alpha)$, $\vert\alpha\vert=d/2$). That is, one characterizes the unique optimal
solution of the optimization problem:
\begin{equation}
\label{pb3-intro}
\mathbf{P}_3:\quad \inf_{\mathbf{Q}\succeq0}\,\{\,{\rm trace}\,(\mathbf{Q})\,:\: {\rm vol}\,(\mathbf{G}_{\mathbf{Q}})\,\leq\,\rho_d\,;\: \mathbf{Q}\succeq0\,\}.\end{equation}
In this matrix context, ${\rm trace}\,(\mathbf{Q})$ is the {\it nuclear norm} of $\mathbf{Q}$ and so
solving $\mathbf{P}_3$ aims at finding an optimal solution $\mathbf{Q}^*$ with small rank, which translates into an homogeneous
polynomial  $g_{\mathbf{Q}^*}$  which is a sum of a few squares. We also proves that
$g^*_1$ associated with the $L_d$-unit ball cannot be an optimal solution of $\mathbf{P}_3$ (and indeed
$g_{\mathbf{Q}^*}$ being a sum of a few squares does not necessarily implies
that it has a small number of coefficients).

(d) Finally we also show that results in (a) and (b) extend to the case of
other values of $d$ (including $p=1$ and rationals) in which case one now deals with positively homogeneous
``generalized polynomials" (instead of homogeneous polynomials) and one has to define an appropriate finite-dimensional
analogue analogue of $\mathbf{Hom}_{d}$. This includes the interesting case of
the $L_1$-unit ball $\{\,\mathbf{x}:\sum_i\vert x_i\vert\leq1\,\}$ and when $p<1$, balls which are not associated with norms.

\section{Notation, definitions and preliminary results}
\label{notation}
Let $\mathbb{R}[\mathbf{x}]$ denote the ring or real polynomials in the variables $\mathbf{x}=(x_1,\ldots,x_n)$, and
let $\mathbb{R}[\mathbf{x}]_d$ be the vector space of real polynomials of degree at most $d$.
Similarly, let $\Sigma[\mathbf{x}]\subset\mathbb{R}[\mathbf{x}]$ denote the convex cone of real polynomials that are sums of squares (SOS) of polynomials,
and $\Sigma[\mathbf{x}]_d\subset\Sigma[\mathbf{x}]$ its subcone of SOS polynomials of degree at most $d$.
Denote by $\mathcal{S}^m$ the space of $m\times m$ real symmetric matrices. For a given matrix $\mathbf{A}\in\mathcal{S}^m$, the notation
$\mathbf{A} \succeq 0$ (resp. $\mathbf{A}\succ0$) means that $\mathbf{A}$ is positive semidefinite (psd) (resp. positive definite (pd)), i.e., all its eigenvalues
are real and nonnegative (resp. positive).

A polynomial $p\in\mathbb{R}[\mathbf{x}]_d$ is homogenous if $p(\lambda \mathbf{x})=\lambda^d p(\mathbf{x})$ for all $\mathbf{x}\in\mathbb{R}^n$, $\lambda\in\mathbb{R}$.
A function $f:\mathbb{R}^n\to\mathbb{R}$ is positively homogeneous of degree $d\in\mathbb{R}$ if $f(\lambda\mathbf{x})=\lambda^df(\mathbf{x})$
for all $0\neq\mathbf{x}\in\mathbb{R}^n$, $\lambda>0$. For instance $x\mapsto \vert x\vert$ is not homogeneous but is positively homogeneous of degree $1$.

Let $\mathbf{Hom}_{d}\subset\mathbb{R}[\mathbf{x}]_{d}$ be the vector space of homogeneous polynomials of even degree $d$, and
let $\mathbb{N}^n_{d}:=\{(\alpha_1,\ldots,\alpha_n)\::\:\sum_i\alpha_i=d\}$.
For an homogeneous polynomial $g\in\mathbb{R}[\mathbf{x}]_{d}$, and
with $s(d):={n-1+d\choose d}$), let  $\mathbf{g}=(g_\alpha)\in\mathbb{R}^{s(d)}$ be its vector of coefficients, i.e.,
\[\mathbf{x}\mapsto g(\mathbf{x})\,:=\,\sum_{\alpha\in\mathbb{N}^n_{d}}g_\alpha\,\mathbf{x}^\alpha
\:\left(=\sum_{\alpha\in\mathbb{N}^n_{d}}g_\alpha\,x_1^{\alpha_1}\cdots x_n^{\alpha_n}\right).\]
Denote by $\mathbf{G}\subset\mathbb{R}^n$
its associated sublevel set $\mathbf{G}:=\{\mathbf{x}:g(\mathbf{x})\leq1\}$.

Let $\mathbf{P}[\mathbf{x}]_d\subset\mathbf{Hom}_{d}$ be the set of homogeneous polynomials of degree $d$
whose associated level set $\mathbf{G}$ has finite Lebesgue volume. It is a convex cone; see \cite[Proposition 2.1]{lowner}.
Let $f:\mathbf{Hom}_{d}\to \mathbb{R}_+$ be the function defined by:
\[g\,\mapsto\,f(g)\,:=\,\left\{\begin{array}{ll}
{\rm vol}\,(\mathbf{G})&\mbox{if $g\in\mathbf{P}[\mathbf{x}]_d$}\\
+\infty&\mbox{otherwise.}\end{array}\right.\]
It is important to realize that the sublevel set $\mathbf{G}$ need not be convex! For instance
Figure \ref{figure1} displays two examples of non convex sets $\mathbf{G}$.
\begin{center}
\begin{figure}
\label{figure1}
\resizebox{0.9\textwidth}{!}
{\includegraphics{d=4-3}\includegraphics{d=6}}
\caption{$\mathbf{G}_1$ with $x^4+y^4-1.925\,x^2y^2$ and $x^6+y^6-1.925\,x^3y^3$}
\end{figure}
\end{center}
More generally, for every $\alpha\in\mathbb{N}^n$ define $f_\alpha:\mathbf{P}[\mathbf{x}]_d\to\mathbb{R}$ by
\[g\,\mapsto\,f_\alpha(g)\,:=\,\left\{\begin{array}{ll}
\displaystyle\int_{\mathbf{G}}\mathbf{x}^\alpha\,d\mathbf{x}&\mbox{if $g\in\mathbf{P}[\mathbf{x}]_d$}\\
+\infty&\mbox{otherwise.}\end{array}\right.\]
In particular, $f(g)=f_0(g)$.

\subsection*{A preliminary result}

We will need the following result of independent interest already proved in \cite{lowner} but
for which we provide a brief sketch. We use the same technique based on Laplace transform
as in Lasserre \cite{monthly} and Lasserre and Zeron \cite{applicationes}  for providing closed form expressions for certain class of integrals.

\begin{theorem}
\label{th1}
Let $h:\mathbb{R}^n\to\mathbb{R}$ be a nonnegative positively homogeneous function of degree $0\neq d\in\mathbb{R}$ such that ${\rm vol}\,(\{\,\mathbf{x}:h(\mathbf{x})\leq 1\,\})<\infty$.
Then for every $\alpha\in\mathbb{N}^n$:
\begin{equation}
 \label{vol-alpha}
\int_{\{\,\mathbf{x}:h(\mathbf{x})\leq1\,\}}\mathbf{x}^\alpha\,d\mathbf{x}\,=\,\frac{1}{\Gamma(1+(n+\vert\alpha\vert)/d)}\int_{\mathbb{R}^n}\mathbf{x}^\alpha\,\exp(-h(\mathbf{x}))\,d\mathbf{x}.
\end{equation}
In particular when $d$ is an even integer: For every $g\in\mathbf{P}[\mathbf{x}]_d$
 \begin{equation}
 \label{vol-exp}
f(g)\,=\,{\rm vol}\,(\mathbf{G})\,=\,\frac{1}{\Gamma(1+n/d)}\int_{\mathbb{R}^n}\exp(-g(\mathbf{x}))\,d\mathbf{x},
 \end{equation}
and the function $f$ is nonnegative, strictly convex and homogeneous of degree $-n/d$.
Moreover, if $g\in\,{\rm int}\,(\mathbf{P}[\mathbf{x}]_d)$:

\begin{eqnarray}
\label{relation-1}
\frac{\partial f(g)}{\partial g_\alpha}&=&-\frac{n+d}{d}\,\int_{\mathbf{G}}\mathbf{x}^\alpha\,d\mathbf{x},\qquad\alpha\,\in\,\mathbb{N}^n_d\\
\label{relation-2}
\int_\mathbf{G} g(\mathbf{x})\,d\mathbf{x}&=&\frac{n}{n+d}\,\int_{\mathbf{G}}\,d\mathbf{x}.
\end{eqnarray}
\end{theorem}
\begin{proof}
For $\alpha\in\mathbb{N}^n$, let $v_\alpha:\mathbb{R}_+\to\mathbb{R}$ be the function $y\mapsto v_\alpha(y):=\int_{\{\mathbf{x}:h(\mathbf{x})\leq\,y\,\}}\mathbf{x}^\alpha\,d\mathbf{x}$.
Observe that $v_\alpha(y)=0$ whenever $y<0$. So let $\mathcal{L}[v_\alpha]:\mathbb{C}\to\mathbb{C}$ be the Laplace transform $\mathcal{L}[v_\alpha]$ of the function $v_\alpha$, i.e.,
\[\lambda\,\mapsto\,\mathcal{L}[v_\alpha](\lambda)\,:=\,\int_0^\infty \exp(-\lambda y)\,v_\alpha(y)\,dy,\qquad \lambda\in\mathbb{C}\,;\:\Re(\lambda)>0.\]
Let $H_\alpha:\mathbb{R}_+\to\mathbb{R}$ be the function $\lambda\mapsto H_\alpha(\lambda):=\mathcal{L}[v_\alpha](\lambda)$, $\lambda\in\mathbb{R}_+$. Then:
\begin{eqnarray*}
H_\alpha(\lambda)&=&\int_0^\infty \exp(-\lambda y)\left(\int_{\{\,\mathbf{x}:h(\mathbf{x})\leq y\,\}}\mathbf{x}^\alpha\,d\mathbf{x}\right)\,dy\\
&=&\int_{\mathbb{R}^n}\mathbf{x}^\alpha\left(\int_{h(\mathbf{x})}^\infty \exp(-\lambda y)\,dy\right)\,d\mathbf{x}\\
&=&\frac{1}{\lambda}\int_{\mathbb{R}^n}\mathbf{x}^\alpha\exp(-\lambda h(\mathbf{x}))\,d\mathbf{x}\\
&=&\frac{1}{\lambda^{1+(n+\vert\alpha\vert)/d}}\int_{\mathbb{R}^n}\mathbf{x}^\alpha\exp(-h(\mathbf{x}))\,d\mathbf{x}\quad\mbox{[by homogeneity]}\\
&=&\frac{\Gamma(1+(n+\vert\alpha\vert)/d)}{\lambda^{1+(n+\vert\alpha\vert)/d}}\left(\underbrace{\frac{1}{\Gamma(1+(n+\vert\alpha\vert)/d)}\int_{\mathbb{R}^n}\mathbf{x}^\alpha\exp(-h(\mathbf{x}))\,d\mathbf{x}}_{c}\,\right)\\
&=&c\,\frac{\Gamma(1+(n+\vert\alpha\vert)/d)}{\lambda^{1+(n+\vert\alpha\vert)/d}}.
\end{eqnarray*}
The function $H_\alpha$ is analytic on $\Theta=\{\lambda\in\mathbb{C}:\Re(\lambda) >0\}$ and
coincides with $\mathcal{L}[v_\alpha]$ on $[0,\infty)$. By the identity Theorem on analytic functions
(see e.g. \cite[Theorem III.3.2, p. 125]{freitag}),
$H_\alpha=\mathcal{L}[v_\alpha]$ on $\Theta$. But $H_\alpha=\mathcal{L}[c\,y^{(n+\vert\alpha\vert)/d}]$ which concludes the proof and yields (\ref{vol-alpha}) when $y=1$.

Next when $g\in{\rm int}\,(\mathbf{P}[\mathbf{x}]_d)$, one obtains (\ref{relation-1}) by differentiating under the integral sign which is
permitted in this context; see \cite{lowner} for a rigorous proof. This yields
\begin{eqnarray*}
\frac{\partial f(g)}{\partial g_\alpha}&=&\frac{-1}{\Gamma(1+n/d)}\int_{\mathbb{R}^n}\mathbf{x}^\alpha\,\exp(-g(\mathbf{x}))\,d\mathbf{x},\qquad\alpha\in\mathbb{N}^n_d\\
&=&\frac{-\Gamma(1+(n+d)/d)}{\Gamma(1+n/d)}\int_{\mathbf{G}}\mathbf{x}^\alpha\,d\mathbf{x},\qquad\alpha\in\mathbb{N}^n_d\\
&=&-\,\frac{n+d}{d}\int_{\mathbf{G}}\mathbf{x}^\alpha\,d\mathbf{x},\qquad\alpha\in\mathbb{N}^n_d,\end{eqnarray*}
where we have use the identity $\Gamma(z+1)=z\,\Gamma(z)$.
Finally, to get
(\ref{relation-2}) observe that $f$ is a positively homogeneous function of degree $-n/d$ and so Euler's identity
$\langle \nabla f(g),g\rangle=-n\,f(g)/d$ for homogeneous functions yields:
\[-\frac{n}{d}\int_{\mathbf{G}}d\mathbf{x}\,=\,\langle g,\nabla f(g)\rangle\,=\,-\frac{n+d}{d}\int_{\mathbf{G}}g(\mathbf{x})\,d\mathbf{x}.\]
\end{proof}

\section{The $\ell_1$-norm formulation}
\label{section-ell-1}
With $d\in\mathbb{N}$ a fixed even integer and $g\in\mathbf{Hom}_{d}$ written as
\[\mathbf{x}\mapsto g(\mathbf{x})\,=\,\sum_{\alpha\in\mathbb{N}^n_d}\,g_\alpha \,\mathbf{x}^\alpha,\qquad\mathbf{x}\in\mathbb{R}^m,\]
let $\mathbf{B}_d\subset\mathbb{R}^n$ be the $L_d$-unit ball and $\rho_d$ its Lebesgue volume, i.e.,
\begin{equation}
\label{vol-unit}
\mathbf{B}_d\,=\,\{\,\mathbf{x}:\sum_{i=1}^nx_i^{d}\,\leq\,1\,\}\quad \mbox{and}\quad \rho_d\,:=\,{\rm vol}\,(\mathbf{B}_d)\,=\,\int_{\mathbf{B}_d}d\mathbf{x}.
\end{equation}
Let $\Vert g\Vert_1:=\sum_{\alpha\in\mathbb{N}^n_d}\vert g_\alpha\vert$ and consider
the optimization problem $\mathbf{P}_1$:
\begin{equation}
\label{problem-P-222}
\mathbf{P}_1:\quad\inf_g\:\{\,\Vert g\Vert_1: \:f(g)\,=\,\rho_d\,;\quad g\in\mathbf{Hom}_{d}\,\}.
\end{equation}
That is, among all degree-$d$ homogeneous polynomials $g$ whose
level set $\mathbf{G}$ has same Lebesgue volume as the $L_d$-unit ball $\mathbf{B}_d$,
one seeks the one which minimizes the $\ell_1$-norm
of its coefficients.

In fact, since $f(\lambda g)=\lambda^{-n/d}f(g)$ one may replace the constraint
$f(g)=\rho_d$ with the inequality constraint $f(g)\leq\rho_d$ and (\ref{problem-P-222}) reads:
\begin{equation}
\label{problem-P-22}
\mathbf{P}_1:\qquad \ell_1^*\,=\,\inf_g\:\{\,\Vert g\Vert_1: \:f(g)\,\leq\,\rho_d\,;\quad g\in\mathbf{Hom}_{d}\:\}.
\end{equation}
\begin{theorem}
\label{th2-ell1}
Let $d\geq 2$ be an even integer. The $L_d$-norm polynomial
\[\mathbf{x}\mapsto g^*(\mathbf{x})\,=\,\Vert\mathbf{x}\Vert_d^{d}\,\left(=\,\sum_{i=1}^n x_i^{d}\,\right),\]
is the unique optimal solution of Problem $\mathbf{P}_1$ in (\ref{problem-P-22}) and
moreover,
\begin{equation}
\label{relationship}
{\rm vol}\,(\mathbf{B}_d)=\displaystyle\int_{\mathbf{G}^*}\,d\mathbf{x}\,=\,\frac{2^n\Gamma(1/d)^n}{n\,d^{n-1}\,\Gamma(n/d)};
\:\displaystyle\int_{\mathbf{G}^*} x_i^{d}\,d\mathbf{x}
\,=\,\frac{{\rm vol}\,(\mathbf{B}_d)}{n+d}\,\quad i=1,\ldots,n.
\end{equation}
\end{theorem}
\begin{proof}
Problem $\mathbf{P}_1$ has an optimal solution $g^*\in\mathbf{Hom}_{d}$. Indeed let $(g_k)$, $k\in\mathbb{N}$, be a minimizing sequence with
$\Vert g_k\Vert_1\to\ell_1^*\geq0$ as $k\to\infty$. Hence the sequence $(g_n)$ is
$\ell_1$-norm bounded and therefore there is a subsequence $(k_t)$ and a polynomial
$g^*\in\mathbf{Hom}_{d}$ such that for every $\alpha\in\mathbb{N}^n_d$,
$(g_{k_t})_\alpha\to g^*_\alpha$ as $t\to\infty$. Then of course one also obtains the pointwise
$g_{k_t}(\mathbf{x})\to g^*(\mathbf{x})$, as $t\to\infty$.
Next, as $f$ is nonnegative, by Fatou's Lemma
\begin{eqnarray*}
\rho_d\,\geq\,\liminf_{t\to\infty}f(g_{k_t})&=&\liminf_{t\to\infty}\frac{1}{\Gamma(1+n/d)}\int_{\mathbb{R}^n}\exp(-g_{k_t}(\mathbf{x}))\,d\mathbf{x}\\
&\geq&\frac{1}{\Gamma(1+n/d)}\int_{\mathbb{R}^n}\liminf_{t\to\infty}\exp(-g_{k_t}(\mathbf{x}))\,d\mathbf{x}\\
&=&\frac{1}{\Gamma(1+n/d)}\int_{\mathbb{R}^n}\exp(-g^*(\mathbf{x}))\,d\mathbf{x}
\end{eqnarray*}
which proves that $g^*$ is feasible for $\mathbf{P}_1$ and so is an optimal solution of $\mathbf{P}_1$.

Problem $\mathbf{P}_1$ has the equivalent formulation:
\[\begin{array}{rl}
\displaystyle\inf_{\lambda_\alpha,g_\alpha} &\displaystyle\sum_{\alpha\in\mathbb{N}^n_d}\lambda_\alpha\\
\mbox{s.t.}& \lambda_\alpha-g_\alpha\geq0,\quad\forall\alpha\in\mathbb{N}^n_d\\
& \lambda_\alpha+g_\alpha\geq0,\quad\forall\alpha\in\mathbb{N}^n_d\\
&f(g)\,\leq\,\rho_d;\:\lambda_\alpha\geq0,\quad\forall\alpha\in\mathbb{N}^n_d,
\end{array}\]
which is a convex optimization problem for which Slater's condition holds.
Hence at an optimal solution $(g^*,\lambda)$, the Karush-Kuhn-Tucker (KKT) optimality conditions
conditions read:
\[\begin{array}{rl}
1-u_\alpha-v_\alpha-\psi_\alpha&=0,\quad\forall\alpha\in\mathbb{N}^n_d\\\\
u_\alpha-v_\alpha +\theta\,\frac{\partial f(g^*)}{\partial g_\alpha}&=0,\quad\forall\alpha\in\mathbb{N}^n_d\\\\
\lambda_\alpha,\,u_\alpha,\,v_\alpha,\,\psi_\alpha,\,\theta&\geq0,\quad\forall\alpha\in\mathbb{N}^n_d\\
f(g^*)&\leq\,\rho_d\\
\lambda_\alpha\psi_\alpha\,=\,0;\:u_\alpha\,(\lambda_\alpha-g^*_\alpha)&=0,\quad\forall\alpha\in\mathbb{N}^n_d\\
\theta\,(1-f(g^*))=0;\:v_\alpha\,(\lambda_\alpha+g^*_\alpha)&=0,\quad\forall\alpha\in\mathbb{N}^n_d
\end{array}\]
for some dual variables $(\mathbf{u},\mathbf{v},\psi,\theta)$.

The meaning of the above optimality conditions is clear.
Indeed at an optimal solution $(g^*,\mathbf{\lambda})$ we must have
$\lambda_\alpha=\vert g^*_\alpha\vert$ for all $\alpha$.
Moreover, from the complementarity conditions
one also has $u_\alpha\,v_\alpha=0$ whenever $g^*_\alpha\neq0$.
In addition, from the two first equations, and the fact that
$1=u_\alpha+v_\alpha=\vert u_\alpha-v_\alpha\vert$, $\lambda_\alpha=\vert g^*_\alpha\vert$,
all moments $\int_{\mathbf{G}^*}\mathbf{x}^\alpha d\mathbf{x}$ must be equal whenever $g^*_\alpha\neq0$.

We next show that $\mathbf{x}\mapsto g^*(\mathbf{x})=\sum_{i=1}^nx_i^{d}$ is an optimal solution.
Recall that $\partial{f(g)}/\partial{g_\alpha}=\frac{n+d}{d}\int_{\mathbf{G}^*}\mathbf{x}^\alpha\,d\mathbf{x}$.
Choose
\[\theta\,:=\,\frac{d}{n+d}\left(\int_{\mathbf{G}^*} x_1^{d}d\mathbf{x}\right)^{-1};\quad u_\alpha\,=\,
\theta\,\frac{n+d}{d}\int_{\mathbf{G}^*}\mathbf{x}^\alpha\,d\mathbf{x},\]
and $v_\alpha=0$, $\lambda_\alpha=g^*_\alpha$, for all $\alpha\in\mathbb{N}^n_d$.
(Notice that $u_\alpha=1$ whenever $\mathbf{x}^\alpha=x_i^{d}$ for some $i$.)
Hence
$u_\alpha\geq0$ for all $\alpha\in\mathbb{N}^n_d$ (because $u_\alpha=0$
whenever some $\alpha_i$ is odd), and let
and $\psi_\alpha:=1-u_\alpha$ for all $\alpha\in\mathbb{N}^n_d$. Observe that
$\psi_\alpha\geq0$ because
\[\left\vert\int_{\mathbf{G}^*}\mathbf{x}^\alpha\,d\mathbf{x}\,\right\vert\,\leq\, \int_{\mathbf{G}^*}x_1^{d}\,d\mathbf{x},\qquad\forall\alpha\in\mathbb{N}^n_d.\]
Therefore,
$(g^*,\mathbf{u},\mathbf{v},\psi,\mathbf{\lambda},\theta)$ satisfies the (necessary) KKT-optimality conditions
and as Slater's conditions holds and $\mathbf{P}_1$ is convex, the KKT-optimality conditions are also sufficient.
Hence we may conclude that $g^*$ is an optimal solution of $\mathbf{P}_1$.
Finally, observe that
\begin{eqnarray*}
\ell_1^*\,=\,\Vert g^*\Vert_1\,=\,n\,=\,\sum_{\alpha\in\mathbb{N}^n_d}\lambda_\alpha&=&\sum_{\alpha\in\mathbb{N}^n_d}(u_\alpha-v_\alpha)\,g^*_\alpha\\
&=&-\theta\,\langle\nabla f(g^*),g^*\rangle\,=\,\theta\,\frac{n}{d}f(g^*),
\end{eqnarray*}
from which we deduce
\[\displaystyle\int_{\mathbf{G}^*} x_i^{d}\,d\mathbf{x}\,=\,\frac{1}{n+d}\,\displaystyle\int_{\mathbf{G}^*}\,d\mathbf{x},\]
for $i=1,\ldots,n$, which is (\ref{relationship}). Finally, for the numerical value of ${\rm vol}\,(\mathbf{B}_d)$ in
(\ref{relationship}) see Lemma \ref{lemma-appendix}.

It remains to prove that $g^*$ above is the unique optimal solution of $\mathbf{P}_1$. So suppose that $\mathbf{P}_1$
has another optimal solution
$h\in\mathbf{Hom}_{d}$ (hence such that $h\neq g^*$ and $\Vert h\Vert_1=\Vert g^*\Vert_1=n$). As we have seen, necessarily
$f(h)=f(g^*)=\rho_d={\rm vol}(\mathbf{B}_d)$. But then as $\mathbf{P}_1$ is a convex optimization problem, any convex combination
$h_\lambda:=\lambda h+(1-\lambda)g^*\in\mathbf{Hom}_{d}$, $\lambda\in (0,1)$, is also an optimal solution of $\mathbf{P}$.
By strict convexity of $f$,
\[f(h_\lambda)\,<\,\lambda f(h)+(1-\lambda)f(g^*)\,=\,\rho_d.\]
But again by taking $k^{-n/d}f(h_\lambda)=\rho_d$ (so that $k<1$) we exhibit another feasible solution
$\tilde{g}:=k\,h_\lambda\in\mathbf{Hom}_{d}$ with smaller $\ell_1$-norm
norm $\Vert \tilde{g}\Vert_1=k\Vert g^*\Vert_1$, in contradiction with
the fact that $g^*$ is an optimal solution of $\mathbf{P}$. Hence $g^*$ is the unique optimal solution of $\mathbf{P}_1$.
\end{proof}

\subsection*{An alternative formulation}

We may also consider the alternative but equivalent formulation
\begin{equation}
\label{equiv}
\mathbf{P}'_1:\quad\rho'=\inf_g \{\,f(g):\quad \Vert g\Vert_1 \leq n\,;\quad g\in\mathbf{Hom}_{d}\,\}.
\end{equation}
\begin{prop}
Let $\mathbf{P}_1$ and $\mathbf{P}'_1$ be as in (\ref{problem-P-22}) and (\ref{equiv}), respectively.
Then $\mathbf{P}'_1$ and $\mathbf{P}_1$ have same optimal value $\rho_d$ and moreover the homogeneous polynomial
$\mathbf{x}\mapsto g^*(\mathbf{x})=\sum_{i=1}^nx_i^{d}$ is the unique optimal solution of $\mathbf{P}'_1$.
\end{prop}
\begin{proof}
Again as $f(\lambda g)=\lambda^{-n/d}f(g)$ we may only consider those $h\in\mathbf{Hom}_{d}$
with $\Vert h\Vert_1=n$.
Suppose that $h$ is an optimal solution of $\mathbf{P}'_1$ with $f(h)=\rho'<\rho_d$ and $\Vert h\Vert_1=n$.
Then take $\tilde{g}=kh$ with $k^{-n/(d)}\rho'=\rho_d$ so that $k<1$. Then $\Vert \tilde{g}\Vert_1=k\Vert n\Vert_1=kn<n$.
But this implies that $\tilde{g}$ would be a better solution for $\mathbf{P}_1$ than $g^*$, a contradiction. Therefore
$\rho'\geq\rho_d$ and in fact $\rho'=\rho_d$ as $g^*$ is feasible for $\mathbf{P}'_1$ with $f(g^*)=\rho_d$.
Next, observe that $\mathbf{P}'_1$ is a convex optimization problem with a strictly convex objective function;
hence an optimal solution is unique.
\end{proof}
Therefore problem $\mathbf{P}_1$ has the equivalent formulation:
{\it Among all homogeneous polynomials $g\in\mathbf{Hom}_{d}$ with $\Vert g\Vert_1=1$ which
is the one with minimum volume?}
By Theorem \ref{th1} the $L_d$-unit ball has minimum volume.

\section{The $\ell_2$-norm formulation}

Let denote by  $\mathbf{x}\cdot\mathbf{y}$ the usual scalar product in $\mathbb{R}^n$.
For every $\alpha\in\mathbb{N}^n$ let $c_\alpha:=\frac{(\sum_i\alpha_i){\rm !}}{\alpha_1{\rm !}\cdots\alpha_n{\rm !}}$.
Recall that $\mathbb{N}^n_d:=\{\alpha\in\mathbb{N}^n:\vert\alpha\vert=d\}$ and $s_d={n-1+d\choose d}$. We
now write
\[\mathbf{x}\mapsto p(\mathbf{x})\,:=\,\sum_{\alpha\in\mathbb{N}^n_d}c_\alpha\,p_\alpha\,\mathbf{x}^\alpha,\qquad p\in\mathbf{Hom}_{d},\]
for some vector $\mathbf{p}=(p_\alpha)\in\mathbb{R}^{s_d}$, and  equip $\mathbf{Hom}_{d}$ with the scalar product
\[\langle p,q\rangle_d\,:=\,\sum_{\alpha\in\mathbb{N}^n_d}c_\alpha \,p_\alpha\,q_\alpha,\quad p,q\in\mathbf{Hom}_{d},\]
with associated norm $\Vert p\Vert_{2,d}^2=\langle p,p\rangle_d$.
Next, denote by $\mathcal{P}_d\subset\mathbf{Hom}_{d}$ the convex cone of homogeneous polynomials of degree $d$
which are nonnegative, and let $\mathcal{C}_d\subset\mathbf{Hom}_{d}$
be the convex cone of sums of $d$-powers of linear forms. Then $\mathcal{C}_d$
is the dual cone of $\mathcal{P}_d$, i.e.,  $\mathcal{P}_d^*=\mathcal{C}_d$; see e.g. Reznick \cite{reznick}.

As in \S \ref{section-ell-1}, let $\rho_d={\rm vol}(\mathbf{B}_d)$ and  consider the following optimization problem:
\begin{equation}
\label{problem-P-11}
\mathbf{P}_2:\qquad \ell^*_2\,=\,\inf_g\:\{\,\Vert g\Vert_{2,d}^2: \:f(g)\leq\rho_d\,;\quad g\in\mathbf{Hom}_{d}\,\},
\end{equation}
a (weighted) $\ell_2$-norm analogue of $\mathbf{P}_1$ in (\ref{problem-P-222}).
In view of Theorem \ref{th1}, problem $\mathbf{P}_2$ is a convex
optimization problem.

\begin{theorem}
\label{th2}
Problem $\mathbf{P}_2$ in (\ref{problem-P-11}) has a unique optimal solution $g^*\in\mathbf{Hom}_{d}$
whose vector of coefficients $\mathbf{g}^*=(g^*_\alpha)\in\mathbb{R}^{s_d}$
satisfies:
\begin{equation}
\label{th2-1}
g^*_\alpha\,=\,\ell^*_2\,\frac{n+d}{n}\cdot\frac{\displaystyle\int_{\mathbf{G}^*}\mathbf{x}^\alpha\,d\mathbf{x}}{\displaystyle\int_{\mathbf{G}^*}\,d\mathbf{x}},
\qquad \forall\,\alpha\in\mathbb{N}^n_{d},
\end{equation}
where $\mathbf{G}^*=\{\mathbf{x}:g^*(\mathbf{x})\leq1\}$ and ${\rm vol}\,(\mathbf{G}^*)=\rho_d$.

Therefore, $\mathbf{g}^*=(g^*_\alpha)$, $\alpha\in\mathbb{N}^n_d$, is an element of $\mathcal{C}_d=\mathcal{P}^*_d$. More precisely:
\begin{equation}
\label{lin-form-1}
\mathbf{x}\,\mapsto\,g^*(\mathbf{x})\,=\,\ell^*_2\,\frac{n+d}{n}\cdot\frac{\displaystyle\int_{\mathbf{G}^*}(\mathbf{z}\cdot \mathbf{x})^{d}\,d\mathbf{z}}{\displaystyle\int_{\mathbf{G}^*}\,d\mathbf{z}}
\end{equation}
and in fact the exist  $\mathbf{z}_i\in\mathbb{R}^n$, $\theta_i>0$, $i=1,\ldots,s$ with $s\leq {n-1+d\choose d}+1$, such that
\begin{equation}
\label{lin-form-2}
\mathbf{x}\,\mapsto\,g^*(\mathbf{x})\,=\,\ell^*_2\,\frac{n+d}{n}\,\sum_{i=1}^s \theta_i \,(\mathbf{z}^i\cdot \mathbf{x})^{d}.
\end{equation}
\end{theorem}
\begin{proof}
That $\mathbf{P}_2$ has an optimal solution follows exactly with same arguments as for $\mathbf{P}_1$.
Moreover Slater's condition also holds for $\mathbf{P}_2$. Hence by the KKT-optimality conditions, there exists $\lambda^*\geq0$ such that
\[2\,g^*_\alpha\,c_\alpha\,=\,-\lambda^*\,\frac{\partial{f(g^*)}}{\partial g_\alpha}\,=\,\lambda^*\,\frac{n+d}{d}\int_{\mathbf{G}^*}c_\alpha\,\mathbf{x}^\alpha\,d\mathbf{x},\qquad \forall\alpha\in \mathbb{N}^n_{d}.\]
Therefore, multiplying each side with $g^*_\alpha$ and summing up yields
\[2\,\Vert g^*\Vert^2_{2,d}\,=\,2\ell^*_2\,=\,-\lambda^*\langle\nabla f(g^*),g^*\rangle\,=\,\lambda^*\,\frac{n}{d}\,f(g^*)\,=\,\lambda^*\,\frac{n}{d}\,\rho_d.\]
Hence $\lambda^*=4\ell^*_2\,d/(n\rho_d)$ and $g^*_\alpha=\ell^*_2\,\frac{n+d}{n\rho_d}\displaystyle\int_{\mathbf{G}^*}\mathbf{x}^\alpha\,d\mathbf{x}$,
from which (\ref{th2-1}) follows.

But then (\ref{th2-1}) means that $(g^*_\alpha)\in\mathcal{P}_d^*=\mathcal{C}_d$, which yields
(\ref{lin-form-1}). To get (\ref{lin-form-2}) we use a generalization of Tchakaloff's theorem described in
\cite{lowner}, Anastassiou \cite{anastassiou} and Kemperman \cite{kemperman}.
\end{proof}
So both  optimal solutions $g^*_1$ of $\mathbf{P}_1$ and $g^*_2$ of $\mathbf{P}_2$ are sums of $d$-powers of linear forms.
But $g^*_2$ does not have the parsimony property as shown below.

\begin{cor}
\label{cor-1}
Let $g^*\in\mathbf{Hom}_{d}$ be the optimal solution of $\mathbf{P}_2$. Then all its coefficients
$g^*_\alpha$ with $\alpha=2\beta\in\mathbb{N}^n_{d}$ for some $\beta\in\mathbb{N}^n_{d/2}$, are strictly positive.
Hence if $d\geq4$ the optimal solution $\mathbf{x}\mapsto g^*_1(\mathbf{x})=\Vert \mathbf{x}\Vert_d^{d}$ of $\mathbf{P}_1$ cannot be an optimal solution.
\end{cor}
\begin{proof}
From the characterization (\ref{th2-1}), every coefficient $g^*_{2\beta}$ with $2\vert\beta\vert=d$
must be positive. Hence the optimal solution $g_1^*$ of problem $\mathbf{P}_1$ cannot be an optimal solution of $\mathbf{P}_2$.
Moreover there are ${n+d/2-1\choose d/2}$ such coefficients.
\end{proof}
Corollary \ref{cor-1} states that the optimal solution of $\mathbf{P}_2$
does not have a parsimony property as it has at least ${n+d/2-1\choose d/2}$ non zero coefficients!

The only case where the optimal solution of $\mathbf{P}_1$ also solves $\mathbf{P}_2$ is the quadratic case $d=2$.
Indeed straightforward computation shows that
(\ref{th2-1}) is satisfied by the polynomials $g^*_1$ of Theorem \ref{th1}.

\begin{ex}
{\rm Let $n=2$ and $d=4$. By symmetry we may guess that the optimal solution $g^*\in\mathbf{Hom}_{d}$ is of the form:
\[\mathbf{x}\mapsto g^*(\mathbf{x})\,=\,g_{40}\,(x_1^4+x_2^4)\,+\,6\,g_{22}\,x_1^2\,x_2^2,\]
with $\ell^*_2=2g_{40}^2+g_{22}^2$ and
\[g_{40}\,=\,3\,\ell^*_2\,\frac{\displaystyle\int_{\mathbf{G}^*} x_1^4\,d\mathbf{x}}{\displaystyle\int_{\mathbf{G}*}\,d\mathbf{x}}\,;\quad
g_{22}\,=\,3\,\ell^*_2\,\frac{\displaystyle\int_{\mathbf{G}^*} x_1^2\,x_2^2\,d\mathbf{x}}{\displaystyle\int_{\mathbf{G}^*}\,d\mathbf{x}}.\]
Observe that by homogeneity, an optimal solution $g^*$ of $\mathbf{P}_2$
is also optimal when we replace $\rho_d$ with any constant $a$; only the optimal value changes
and the characterization (\ref{th2-1}) remains the same with the new optimal value $\ell^*_2$.
After several numerical trials we conjecture that
\[\mathbf{x}\mapsto g^*(\mathbf{x})\,\approx\,x_1^4+x_2^4+2\,x_1^2x_2^2\,=\,(x_1^2+x_2^2)^2,\]
i.e. $\mathbf{g}^*=(1,0,1/3,0,1)$, is an optimal solution. But then observe that
\[\mathbf{G}^*\,=\,\{\,\mathbf{x}:g^*_2(\mathbf{x})\leq1\,\}\,=\,\{\,\mathbf{x}:(x_1^2+x_2^2)^2\leq\,1\,\}\,=\,\mathbf{B}_2!\]
That is, $\mathbf{G}^*$ is another representation of the unit sphere $\mathbf{B}_2$ by
homogeneous polynomials of degree $4$ instead of quadratics!
\[\int_{\mathbf{G}^*}\,d\mathbf{x}\,\approx\,3.1415926\,;\quad \int_{\mathbf{G}^*}x_1^4\,d\mathbf{x}\,\approx\,0.392699\,;\quad
\int_{\mathbf{G}^*}x_1^2x_2^2\,d\mathbf{x}\,\approx\,0.130899.\]
With $a:=\int_{\mathbf{G}^*}d\mathbf{x}$, (\ref{th2-1}) yields  (up to $10^{-8}$)
\[3\,\ell^*_2\cdot\frac{\displaystyle\int_{\mathbf{G}^*}\mathbf{x}_1^4\,d\mathbf{x}}{\displaystyle\int_{\mathbf{G}^*}\,d\mathbf{x}}\,=\, 1= g^*_{40}\,;
\quad 3\ell^*_2\cdot\frac{\displaystyle\int_{\mathbf{G}^*}x_1^2x_2^2\,d\mathbf{x}}{\displaystyle\int_{\mathbf{G}^*}\,d\mathbf{x}}\,=\,
\frac{1}{3}\,=\,g^*_{22}.\]
Observe also that
\[(x_1^2+x_2^2)^2\,=\,\frac{1}{6}(x_1+x_2)^4+\frac{1}{6}(x_1-x_2)^4+\frac{2}{3}\,(x_1^4+
x_2^4),\]
i.e., a sum of $4$-powers of linear forms as predicted by Theorem \ref{th2}.
}\end{ex}
In fact we have:
\begin{theorem}
If $d=4$ then for every $n$ the optimal solution of $\mathbf{P}_2$
is $g^*(\mathbf{x})=(\sum_{i=1}^n x_i^2)^2$ whose level set $\mathbf{G}$ is the unit ball $\mathbf{B}_2$.
\end{theorem}
\begin{proof}
Let $\mathbf{x}\mapsto g^*(\mathbf{x}):=(\sum_{i=1}^n x_i^2)^2$. It is enough to prove that (\ref{th2-1}) holds
(as by homogeneity (\ref{th2-1}) still holds when one replaces $g$ with $\lambda\,g$ for any
$\lambda>0$.)
Since $g^*(\mathbf{x})=\sum_ix_i^4+2\sum_{i<j}x_i^2x_j^2$, we have $\ell^*_2=(n+\frac{n(n-1)}{2}\cdot 6(\frac{2}{6})^2)=n(n+2)/3$.
Moreover
\[A:=\int_{\mathbf{B}_2}x_1^4\,d\mathbf{x}\,\left(\int_{\mathbf{B}_2}d\mathbf{x}\,\right)^{-1}\,=\,\frac{3}{(n+4)(n+2)}\]
Therefore with $d=4$,
\[\ell^*_2\,\frac{n+d}{n}\,A\,=\,\frac{n(n+2)}{3}\,\frac{n+4}{n}\,\frac{3}{(n+2)(n+4)}\,
\,=\,1\,=\,g^*_{40}.\]
Similarly one has
\[B:=\int_{\mathbf{B}_2}x_1^2\,x_2^2\,d\mathbf{x}\,\left(\int_{\mathbf{B}_2}d\mathbf{x}\,\right)^{-1}\,=\,\frac{1}{(n+4)(n+2)}\]
so that
\[\ell^*_2\,\frac{n+4}{n}\,B\,=\,\frac{n(n+2)}{3}\,\frac{n+4}{n}\,\frac{1}{(n+2)(n+4)}\,
\,=\,\frac{1}{3}\,=\,g^*_{22}.\]
\end{proof}
In other words, when $d=4$ the Euclidean unit ball $\mathbf{B}_2=\{\mathbf{x}:\sum_ix_i^2\leq1\}$ (which has
the equivalent quartic representation $\{\mathbf{x}: (\sum_{i=1}^n x_i^2)^2\leq 1\}$) solves problem $\mathbf{P}_2$!

\section{The SOS formulation}

As we have seen that both optimal solutions of the $\ell_1$-norm and $\ell_2$-norm formulations are
sums of $d/2$ powers of linear forms, hence sums of squares (in short SOS). Therefore one may now restrict to
homogeneous polynomials in $\mathbf{Hom}_{d}$ that are SOS, i.e., polynomials of the form
\[\mathbf{x}\,\mapsto\,g_\mathbf{Q}(\mathbf{x})\,=\,\mathbf{v}_{d/2}(\mathbf{x})^T\mathbf{Q}\,\mathbf{v}_{d/2}(\mathbf{x}),\]
where $\mathbf{v}_{d/2}(\mathbf{x})=(\mathbf{x}^\alpha)$, $\alpha\in\mathbb{N}^n_{d/2}$, and $\mathbf{Q}$ is some real psd symmetric matrix
($\mathbf{Q}\succeq0$) of size $s(d/2)={n-1+d/2\choose d/2}$. If we denote by $\mathcal{S}_d$ the space of real symmetric matrices of size $s(d)$, there is not a one-to-one correspondence between
$g\in\mathbf{Hom}_{d}$ and $\mathbf{Q}\in\mathcal{S}_d$ as several $\mathbf{Q}$ may produce the same polynomial $g_\mathbf{Q}$.

Given $0\preceq\mathbf{Q}\in\mathcal{S}_d$, denote by $\mathbf{G}_\mathbf{Q}$ the sublevel set
$\{\mathbf{x}:g_\mathbf{Q}(\mathbf{x})\,\leq\,1\}$ associaterd woth $g_\mathbf{Q}\in\mathbf{Hom}_{d}$ and let $f(\mathbf{Q}):={\rm vol}\,(\mathbf{G}_\mathbf{Q})$. Observe that
again $f$ is positively homogeneous of degree $-n/d$.\\

So the natural analogue for $\mathbf{Q}$ of the $\ell_1$-norm $\Vert g\Vert_1$ for $g\in\mathbf{Hom}_{d}$
is now the nuclear norm of $\mathbf{Q}$ which as $\mathbf{Q}\succeq0$ reduces to $\langle \mathbf{I},\mathbf{Q}\rangle={\rm trace}\,(\mathbf{Q})$.
It is well-known that optimizing the nuclear norm on convex problems
with matrices induce a parsimony effect, namely an optimal solution
will generally have  a small rank. In our context, $\mathbf{Q}$ having a small
rank means that $g_\mathbf{Q}$ can be written a sum of a small number of squares.
However, when expanded in the monomial basis, $g_\mathbf{Q}$ may have many non-zero coefficients
and so its $\ell_1$-norm $\Vert g_\mathbf{Q}\Vert_1$ may not be small.\\

So in the same spirit as for the $\ell_1-$ and $\ell_2$-norm, we now consider the optimization problem:
\[\mathbf{P}_3:\quad \ell^*_3=\inf_{\mathbf{Q}\in\mathcal{S}_d}\,\{\,\langle \mathbf{I},\mathbf{Q}\rangle:\:f(\mathbf{Q})\,\leq\,\rho_d\,; \quad\mathbf{Q}\succeq0\,\},\]
and characterize its unique optimal solution $\mathbf{Q}^*$.
\begin{theorem}
\label{th-Q}
Problem $\mathbf{P}_3$ has a unique optimal solution. Moreover, $\mathbf{Q}^*\in\mathcal{S}_d$
is an optimal solution of $\mathbf{P}_3$ if and only if $f(\mathbf{Q}^*)=\rho_d$ and:
\begin{equation}
\label{th-Q-1}
\mathbf{I}\,\succeq\,\frac{(n+d)\,\langle\mathbf{I},\mathbf{Q}^*\rangle}{n\,\rho_d}\,\displaystyle\int_{\mathbf{G}_{\mathbf{Q}^*}}\mathbf{v}_{d/2}(\mathbf{x})\,\mathbf{v}_{d/2}d(\mathbf{x})^T\,d\mathbf{x}
\end{equation}
where
\[\mathbf{x}\mapsto g_{\mathbf{Q}^*}(\mathbf{x}):=\mathbf{v}_{d/2}(\mathbf{x})^T\mathbf{Q}^*\mathbf{v}_{d/2}(\mathbf{x}),\quad\mathbf{x}\in\mathbb{R}^n.\]
Moreover, the polynomial $\mathbf{x}\mapsto g(\mathbf{x})=\sum_{i=1}^nx_i^{d}$ cannot be solution
of $\mathbf{P}_3$.
\end{theorem}
\begin{proof}
Let $(\mathbf{Q}_k)$, $k\in\mathbb{N}$, be a minimizing sequence. As $\sup_k\langle \mathbf{I},\mathbf{Q}_k\rangle \leq\langle \mathbf{I},\mathbf{Q}_1\rangle$,
the sequence $(\mathbf{Q}_k)$ is norm-bounded in $\mathcal{S}_d$. Therefore
it has a converging subsequence $\mathbf{Q}_{k_j}\to\mathbf{Q}^*\in\mathcal{S}_d$ with $\mathbf{Q}^*\succeq0$
and $f(\mathbf{Q}^*)\leq\rho_d$ (by a simple continuity argument). Therefore $\mathbf{Q}^*$ is an optimal solution
of $\mathbf{P}_3$ and again, uniqueness follows from the strict convexity and homogeneity of the function $f$.
Moreover, Slater's condition obviously holds for $\mathbf{P}_3$ which is a convex optimization problem.
Then the  KKT-optimality conditions read:
\begin{eqnarray}
\label{kkt1}
\mathbf{I}+\lambda\,\nabla f(\mathbf{Q}^*)&=&\Psi\,\succeq\,0\\
\label{kkt2}
\langle \mathbf{Q}^*,\Psi\rangle&=&0\\
\label{kkt3}
f(\mathbf{Q}^*)&\leq&\rho_d; \quad \lambda\,(f(\mathbf{Q}^*)-\rho_d)=0,
\end{eqnarray}
for some dual variables $(\lambda,\Psi)\in\mathbb{R}_+\times\mathcal{S}_d$.
By homogeneity one must have $f(\mathbf{Q}^*)=\rho_d$.
Again Euler's identity for homogeneous functions yields $\langle \nabla f(\mathbf{Q}^*),\mathbf{Q}^*\rangle=-nf(\mathbf{Q}^*)/d$.
Therefore using (\ref{kkt1}) and (\ref{kkt2})
one obtains $\ell^*_3=\langle \mathbf{I},\mathbf{Q}^*\rangle=\lambda\,n\,\rho_d/d$, that is, $\lambda=d\,\ell^*_3/(n\rho_d)$.
Next combining $\Psi\succeq0$ with Theorem \ref{th1}, one also gets
\[\mathbf{I}\,\succeq\,\frac{n+d}{d}\,\lambda \int_{\mathbf{G}_{\mathbf{Q}^*}}\mathbf{v}_{d/2}(\mathbf{x})\,\mathbf{v}_{d/2}(\mathbf{x})^T\,d\mathbf{x},\]
or, equivalently
\[\mathbf{I}\,\succeq\,\frac{(n+d)\,\langle\mathbf{I},\mathbf{Q}^*\rangle}{n\,\rho_d}\,\displaystyle\int_{\mathbf{G}_{\mathbf{Q}^*}}\mathbf{v}_{d/2}(\mathbf{x})\,\mathbf{v}_{d/2}(\mathbf{x})^T\,d\mathbf{x},\]
which is (\ref{th-Q-1}). This proves the {\it only if part} in Theorem \ref{th-Q}.

Conversely, assume that $0\preceq\mathbf{Q}^*\in\mathcal{S}_d$ satisfies $f(\mathbf{Q}^*)=\rho_d$ and (\ref{th-Q-1}).
Let
\[\lambda\,:=\,d\,\langle\mathbf{I},\mathbf{Q}^*\rangle/(n\rho_d)\,;\quad\Psi:=\mathbf{I}\,-\,
\frac{(n+d)\,\langle\mathbf{I},\mathbf{Q}^*\rangle}{n\,\rho_d}\,\displaystyle\int_{\mathbf{G}_{\mathbf{Q}^*}}\mathbf{v}_{d/2}(\mathbf{x})\,\mathbf{v}_{d/2}(\mathbf{x})^T\,d\mathbf{x}.\]
Obviously $\lambda\geq0$, $\Psi\succeq0$, and:
\begin{eqnarray*}
\langle \mathbf{Q}^*,\Psi\rangle&=&
\langle\mathbf{I},\mathbf{Q}^*\rangle\left[1-\frac{n+d}{n\,\rho_d}\,
\displaystyle\int_{\mathbf{G}_{\mathbf{Q}^*}}\left\langle\mathbf{Q}^*,\mathbf{v}_{d/2}(\mathbf{x})\,\mathbf{v}_{d/2}(\mathbf{x})^T\right\rangle\,d\mathbf{x}\right]\\
&=&\langle\mathbf{I},\mathbf{Q}^*\rangle\left[1-\frac{n+d}{n\,\rho_d}\,
\displaystyle\int_{\mathbf{G}_{\mathbf{Q}^*}}g_{\mathbf{Q}^*}(\mathbf{x})\,d\mathbf{x}\right]\\
&=&\langle\mathbf{I},\mathbf{Q}^*\rangle\left[1-\frac{n+d}{n\,\rho_d}\,
\frac{n}{n+d}\displaystyle\int_{\mathbf{G}_{\mathbf{Q}^*}}\,d\mathbf{x}\right]\quad\mbox{[by Theorem \ref{th1}]}\\
&=&0,
\end{eqnarray*}
which shows that the triplet $(\mathbf{Q}^*,\lambda,\Psi)$ satisfy the KKT-optimality conditions (\ref{kkt1})-(\ref{kkt3}).
As Slater's condition holds for $\mathbf{P}_3$, (\ref{kkt1})-(\ref{kkt3}) are sufficient for optimality, which  concludes the {\it if part}
of the proof.

We next prove that $\mathbf{x}\mapsto g(\mathbf{x}):=\sum_{i=1}^n x_i^d$ (so that $\mathbf{G}=\mathbf{B}_d$) cannot be the optimal solution of $\mathbf{P}_3$. Among all $\mathbf{Q}\succeq0$ such that $\sum_ix_i^d=\mathbf{v}_{d/2}(\mathbf{x})^T\mathbf{Q}\mathbf{v}_{d/2}(\mathbf{x})$, the one that minimizes
${\rm trace}\,(\mathbf{Q})$ is $\mathbf{Q}=\mathbf{I}$ with ${\rm trace}\,(\mathbf{Q})=n$.
By Lemma \ref{lemma-appendix}, observe that
\[\frac{\displaystyle\int_{\mathbf{G}}x_i^d\,d\mathbf{x}}{\displaystyle\int_{\mathbf{G}}d\mathbf{x}}\,=\,
\frac{\displaystyle\int_{\mathbf{B}_d}x_i^d\,d\mathbf{x}}{\rho_d}\,=\,\frac{1}{n+d},\]
and so (\ref{th-Q-1}) cannot hold because for instance the north-west and south-east corner
elements of the matrix
\begin{eqnarray*}
\mathbf{A}&:=&\mathbf{I}\,-\,\frac{(n+d)\,\langle\mathbf{I},\mathbf{Q}\rangle}{n\,\rho_d}\,\displaystyle\int_{\mathbf{G}}\mathbf{v}_{d/2}(\mathbf{x})\,\mathbf{v}_{d/2}d(\mathbf{x})^T\,d\mathbf{x}\\
&=&\mathbf{I}\,-\,(n+d)\frac{\displaystyle\int_{\mathbf{G}}\mathbf{v}_{d/2}(\mathbf{x})\,\mathbf{v}_{d/2}d(\mathbf{x})^T\,d\mathbf{x}}
{\displaystyle\int_{\mathbf{G}}\,d\mathbf{x}}\end{eqnarray*}
vanish whereas the north-east and south-west corner elements are non-zero, in
contradiction with $\mathbf{A}\succeq0$.
\end{proof}
The fact that the $L_d$-unit ball is not an optimal solution of $\mathbf{P}_3$
is not a surprise as  the sparsity-induced norm ${\rm trace}\,(\mathbf{Q})$ (when $\mathbf{Q}\succeq0$)
aims at find a polynomial $g_\mathbf{Q}\in\mathbf{Hom}_{d}$ which can be written as a sum of squares
with as few terms as possible in the sum. On the other hand, the sparsity-induced norm
$\Vert g\Vert_1$ aims at finding a polynomials $g\in\mathbf{Hom}_{d}$ with
as few monomials as possible when $g$ is expanded in the monomial basis. These can be two conflicting criteria!

\section{Extension to generalized polynomials}

In this section $d$ is now a (positive) rational with $L_d$-unit ball
$\{\,\mathbf{x}:\:\,\sum_{i=1}^n\vert x_i\vert^d\leq1\,\}$. Even though the function $\mathbf{x}\mapsto \sum_{i=1}^n\vert x_i\vert^d$ is a ``generalized polynomial" and not a polynomial any more,  it is still a nonnegative positively homogeneous of degree $d$ for which Theorem \ref{th1}(a) applies. On the other hand, the vector
space of positively homogeneous functions of degree $d$ is not finite-dimensional and so for optimization purposes we need define an appropriate finite-dimensional
analogue of $\mathbf{Hom}_{d}$.

We will use the notation $\vert\mathbf{x}\vert\in\mathbb{R}^n_+$ for the vector $(\vert x_1\vert,\ldots,\vert x_n\vert)$ and
$\vert\mathbf{x}\vert^\alpha$ for the generalized monomial $\vert x_1\vert^{\alpha_1}\cdots\vert x_n\vert^{\alpha_n}$, whenever
$\alpha\in\mathbb{Q}^n_+$.
\begin{defn}
Let $0<d\in\mathbb{Q}$. Define the space $\mathscr{C}_d$ as:
\begin{equation}\label{general}
\mathscr{C}_d\,:=\,\{\,\sum_{\alpha\in\mathbb{Q}^n_+}g_\alpha\,\vert \mathbf{x}\vert^\alpha\,:\quad g_\alpha\in\mathbb{R}\,;\quad\vert\alpha\vert\,(:=\sum_{i=1}^n \alpha_i)\,=d\,\}
\end{equation}
where only {\it finitely many} coefficients $g_\alpha$ are non-zero. Then:
\[\Vert g\Vert_1\,=\,\sum_\alpha\,\vert g_\alpha\vert\,;\quad
\Vert g\Vert_2^2\,=\,\sum_\alpha\,g_\alpha^2.\]
\end{defn}
The space $\mathscr{C}_d$ is a real infinite-dimensional vector space and each element of $\mathscr{C}_d$ is a
positively homogeneous functions of degree $d$.
\begin{defn}
With $q\in\mathbb{N}$ let $\mathbb{Z}^n_q\subset\mathbb{R}^n$ be the lattice $\{\,\mathbf{z}\in\mathbb{R}^n: q\,\mathbf{z}\in\mathbb{Z}^n\,\}$. With
$0<d\in\mathbb{Z}_q$, denote by
$\mathcal{N}^n_{dq}$ the finite set $\{\,\alpha\in\mathbb{Z}^n_q:\alpha\geq0\,;\:\sum_{i=1}^n\alpha_i=d\,\}$
of cardinality $m(d,q)$ and by $\mathbf{Hom}^q_d\subset\mathscr{C}_d$
the vector space of functions $g:\mathbb{R}^n\to \mathbb{R}$ defined by:
\begin{equation}
\label{help}
\mathbf{Hom}^q_d\,:=\,\{\sum_{\alpha\in\mathcal{N}^n_{dq}}\,g_\alpha\,\vert \mathbf{x}\vert^{\alpha}:\quad (g_\alpha)\in\mathbb{R}^{m(d,q)}\,\},\end{equation}
which is a finite-dimensional vector space.
\end{defn}
For instance with $n=2$ and $d=1$ one has $\mathbf{B}_1:=\{\,\mathbf{x}\in\mathbb{R}^n:\:\sum_{i=1}^n\vert x_i\vert\leq1\,\}$ and with $0<q\in\mathbb{N}$,
\[\mathcal{N}_{1q}\,=\,\{(\frac{k}{q},\frac{q-k}{q}): k=0,\ldots,q\,\}\,;\quad m(d,q)=q+1,\]
and $g\in\mathbf{Hom}^q_d$ can be written as
\[\mathbf{x}\mapsto g(\mathbf{x})\,=\,\sum_{k=0}^q\,g_k \,\vert x_1\vert  ^{\frac{k}{q}}\,\vert x_2\vert^{\frac{q-k}{q}},\qquad \mathbf{x}\in\mathbb{R}^2,\]
for some vector $\mathbf{g}=(g_k)\in\mathbb{R}^{t+1}$.

Obviously
$\mathbf{Hom}^q_d$ is a vector space of dimension $m(d,q)$ and every function in $\mathbf{Hom}^q_d$ is positively homogeneous
of degree $d$.
As we did in \S \ref{section-ell-1}, with $g\in\mathbf{Hom}^q_d$ is associated the level set $\mathbf{G}:=\{\,\mathbf{x}:g(\mathbf{x})\leq 1\,\}$, and
whenever $\mathbf{G}$ has finite volume let $f(g):={\rm vol}\,(\mathbf{G})$, $g\in\mathbf{Hom}^q_d$. It follows that
$f$ is positively homogeneous of degree $-n/d$. Therefore (\ref{vol-exp})-(\ref{relation-2})
in Theorem \ref{th1} holds for $f$.
Finally, let
\[\mathbf{x}\mapsto g^*(\mathbf{x})\,:=\,\sum_{i=1}^n\vert x_i\vert^d;\quad \mathbf{B}_d=\mathbf{G}^*;\quad \rho_d\,=\,{\rm vol}\,(\mathbf{G}^*),\]
and consider the finite-dimensional optimization problem
\begin{equation}
\label{problem-P-33}
\mathbf{P}_{1q}:\qquad \ell_1^*\,=\,\inf_g\:\{\,\Vert g\Vert_1: \:f(g)\,\leq\,\rho_d\,;\quad g\in\mathbf{Hom}^q_d\,\}.
\end{equation}
When $d<1$ the unit ball $\mathbf{B}_d$ is not convex and is not associated with a norm as can be seen
in Figure \ref{fig-undemi} where $d=1/2$.
\begin{center}
\begin{figure}
 \resizebox{0.9\textwidth}{!}
{\includegraphics{undemi}}
\caption{The $L_{1/2}$-unit ball $\{\,\mathbf{x}:\sqrt{\vert x_1\vert}+\sqrt{\vert x_2\vert}\leq1\,\}$ \label{fig-undemi}}
\end{figure}
\end{center}

However, we have the following analogue of Theorem \ref{th2-ell1}

\begin{theorem}
\label{th3-ell1-q}
Let $0<q\in\mathbb{N}$ and $0<d\in\mathbb{Z}_{q/2}$. The polynomial
\begin{equation}
\label{general-gstar}
\mathbf{x}\mapsto g^*(\mathbf{x})\,=\,\sum_{i=1}^n \vert x_i\vert ^{d}\,\end{equation}
is the unique optimal solution of Problem $\mathbf{P}_{1q}$ in (\ref{problem-P-33}) and
moreover,
\begin{equation}
\label{relationship-q}
{\rm vol}\,(\mathbf{B}_d)\,=\,\frac{2^n\Gamma(1/d)^n}{n\,d^{n-1}\,\Gamma(n/d)};
\:\displaystyle\int_{\mathbf{G}^*} \vert x_i\vert ^{d}\,d\mathbf{x}
\,=\,\frac{{\rm vol}\,(\mathbf{B}_d)}{n+d}\,\quad i=1,\ldots,n.
\end{equation}
\end{theorem}
\begin{proof}
The proof is almost a verbatim copy of that of Theorem \ref{th2-ell1} except that we now have to deal with generalized moments $\int_\mathbf{G} \vert\mathbf{x}\vert^\alpha d\mathbf{x}$, $\alpha\in\mathcal{N}^n_{dq}$ instead of standard
monomial moments $\int_\mathbf{G} \mathbf{x}^\alpha d\mathbf{x}$, $\alpha\in\mathbb{N}^n$. But the crucial fact that we exploit is that $f$ is strictly convex and Theorem \ref{th1} holds for $f$. As in the proof of Theorem \ref{th2-ell1}, to show
that $g^*$ in (\ref{general-gstar}) satisfies the KKT-optimality conditions we only need prove that
\[\int_{\mathbf{G}^*}\vert\mathbf{x}\vert^\alpha\,d\mathbf{x}\,\leq\, \int_{\mathbf{G}^*}\vert x_1\vert^{d}\,d\mathbf{x},\qquad\forall\alpha\in\mathcal{N}^n_{dq}.\]
Define the Hankel-type moment matrix $\mathbf{M}$ to be the real symmetric matrix with rows
and columns indexed by $\alpha\in\mathcal{N}^n_{d\frac{q}{2}}$ and with entries
\[\mathbf{M}(\alpha,\beta)\,:=\,\int_{\mathbf{G}^*}\vert\mathbf{x}\vert^{(\alpha+\beta)/2}\,d\mathbf{x},\qquad\alpha,\beta\,\in\,\mathcal{N}^n_{d\frac{q}{2}}.\]
Equivalently, letting $\mathbb{N}^n_{dq/2}=\{\beta\in\mathbb{N}^n:\sum_i\beta_i=dq/2\}$ and re-indexing rows and columns of $\mathbf{M}$ with $\tilde{\alpha}:=q\alpha/2\in\mathbb{N}^n_{dq/2}$,
\[\mathbf{M}(\tilde{\alpha},\tilde{\beta})\,:=\,\int_{\mathbf{G}^*}(\vert\mathbf{x}\vert^{1/q})^{\tilde{\alpha}+\tilde{\beta}}\,d\mathbf{x}\,=:\,y_{\tilde{\alpha}+\tilde{\beta}},\qquad\tilde{\alpha},\tilde{\beta}\,\in\,\mathbb{N}^n_{d\frac{q}{2}}.\]
Define $\mathbf{y}=(y_{\tilde{\alpha}})$, $\tilde{\alpha}\in\mathbb{N}^n_{dq}$, and $\tilde{X}=\vert\mathbf{x}\vert^{1/q}$.
Observe that from (\ref{help}) one may write
\[\mathbf{Hom}^q_d\,:=\,\{\sum_{\tilde{\alpha}\in\mathbb{N}^n_{dq}}\,g_\alpha\,(\vert \mathbf{x}\vert^{\frac{1}{q}})^{\tilde{\alpha}}:\quad (g_\alpha)\in\mathbb{R}^{m(d,q)}\,\}.\]
Let $L_\mathbf{y}:\mathbf{Hom}^q_d\to\mathbb{R}_+$ be the linear mapping defined by
\[g\mapsto\,L_\mathbf{y}(g)\,:=\,\sum_{\tilde{\alpha}\in\mathbb{N}^n_{dq}}g_\alpha\,y_{\tilde{\alpha}}
\,=\,\sum_{\tilde{\alpha}\in\mathbb{N}^n_{dq}}g_\alpha\,\int_{\mathbf{G}^*}\tilde{X}^{\tilde{\alpha}}\,d\mathbf{x}\,=\,
\int_{\mathbf{G}^*}g(\mathbf{x})\,d\mathbf{x}.\]
By an adaptation of Lemma 4.3 in Lasserre and Netzer \cite{netzer}
to the present homogeneous context one has
\[\vert y_{\tilde{\alpha}}\vert\,\leq\,\sup_{i=1,\ldots,n}\,L_\mathbf{y}(\tilde{X}_i^{dq})\,=\,\sup_{i=1,\ldots,n}\,
\int_{\mathbf{G}^*}\vert x_i\vert^{d}\,d\mathbf{x}\,\left(=\,\int_{\mathbf{G}^*}\vert x_1\vert^{d}\,d\mathbf{x}\right),\quad\forall\tilde{\alpha}\in\mathbb{N}^n_{dq}.\]
Indeed in Lemma 4.3 of \cite{netzer} one only uses the Hankel structure of the moment matrix $\mathbf{M}$
and its positive definiteness. Therefore for every $\alpha\in\mathcal{N}^n_{dq}$,
\[\int_{\mathbf{G}^*}\vert\mathbf{x}\vert^\alpha\,d\mathbf{x}\,=\,\int_{\mathbf{G}^*}\tilde{X}^{\tilde{\alpha}}\,d\mathbf{x}\,=\,
 y_{\tilde{\alpha}}\,\leq\,\int_{\mathbf{G}^*}\vert x_1\vert^{d}\,d\mathbf{x},\]
 and so as in the proof of Theorem \ref{th2-ell1}, $g^*$ satisfies the KKT-optimality conditions.
\end{proof}

We obtain the following even more general extension of Theorem \ref{th2-ell1}.
\begin{cor}
\label{cor2}
For every $0<d\in\mathbb{Q}$ the generalized polynomial
\[\mathbf{x}\mapsto g^*(\mathbf{x})\,=\,\sum_{i=1}^n \vert x_i\vert ^{d}\,\]
is the unique optimal solution of
\[\mathbf{P}_1:\qquad \ell_1^*\,=\,\inf_g\:\{\,\Vert g\Vert_1: \:f(g)\,\leq\,\rho_d\,;\quad g\in\mathscr{C}_d\,\}.\]
and (\ref{relationship-q}) holds.
\end{cor}
\begin{proof}
Let $0<d\in\mathbb{Q}$ and suppose that there exists
$g\in\mathscr{C}_d$ such that
${\rm vol}\,(\mathbf{G})=\rho_d$ and $\Vert g\Vert_1\leq n$. Write $d=p_0/q_0$
with $0<p_0,q_0\in\mathbb{N}$. For each non-zero coefficient
$g_\alpha$ one has $\alpha_i=p_i(\alpha)/q_i(\alpha)$ for some integers $0<p_i(\alpha),q_i(\alpha)$. Let
$q=2q'$ with $q'\in\mathbb{N}$ being the least common multiple (l.c.m.) of $\{q_0,(q_i(\alpha)), i=1,\ldots,n, g_\alpha\neq0\}$.
Then  $d\in\mathbb{Z}_{q/2}$ and $g\in\mathbf{Hom}^q_d$. Therefore by Theorem \ref{th3-ell1-q},
$\Vert g\Vert_1>\Vert g^*\Vert_1=n$ where $g^*(\mathbf{x})=\sum_{i=1}^n \vert x_i\vert^d$, in contradiction
with our assumption $\Vert g\Vert_1\leq n$.
\end{proof}

Then again the parsimony property of the $L_d$-unit ball $\mathbf{B}_d$
can be retrieved by minimizing the $\ell_1$-norm
over all nonnegative generalized polynomials $g\in\mathscr{C}_d$ whose associated ball
unit ball $\mathbf{G}$ has finite volume.\\

Next, concerning the $\ell_2$-norm, with $0<q\in\mathbb{N}$ an analogue of problem (\ref{problem-P-11}) now reads:
 \begin{equation}
\label{problem-P-11-q}
\mathbf{P}_{2q}:\qquad \ell^*_2\,=\,\inf_g\:\{\,\Vert g\Vert_2^2: \:f(g)\leq\rho_d\,;\quad g\in\mathbf{Hom}^q_d\,\},
\end{equation}
and we have the following analogue of Theorem \ref{th2}:

 \begin{theorem}
\label{th2-q}
With $0<q\in\mathbb{N}$ and $0<d\in\mathbb{Z}_q$, Problem $\mathbf{P}_{2q}$ in (\ref{problem-P-11-q}) has a unique optimal solution $g^*\in\mathbf{Hom}^q_d$
whose vector of coefficients $\mathbf{g}^*=(g^*_\alpha)\in\mathbb{R}^{m(d,q)}$
satisfies:
\begin{equation}
\label{th2-1-q}
g^*_\alpha\,=\,\ell^*_2\,\frac{n+d}{n}\cdot\frac{\displaystyle\int_{\mathbf{G}^*}\vert\mathbf{x}\vert^\alpha\,d\mathbf{x}}{\displaystyle\int_{\mathbf{G}^*}\,d\mathbf{x}},
\qquad \forall\,\alpha\in\mathcal{N}_{dq},
\end{equation}
where $\mathbf{G}^*=\{\mathbf{x}:g^*(\mathbf{x})\leq1\}$ and ${\rm vol}\,(\mathbf{G}^*)=\rho_d$.
\end{theorem}
We omit the proof as it is again a verbatim copy of that of Theorem \ref{th2}.
But in contrast to the case of polynomials in Theorem \ref{th2},
in the optimal solution $g^*$ of $\mathbf{P}_{2q}$, all coefficients $(g^*_\alpha)$, $\alpha\in\mathcal{N}_{dq}$,
are non-zero! This follows from (\ref{th2-1-q}) and the fact that
all generalized moments
$\int_{\mathbf{G}^*}\vert\mathbf{x}\vert^\alpha\,d\mathbf{x}$, $\alpha\in\mathcal{N}_{dq}$ are non-zero! For instance with
$d=1/2$ and $q=8$,
\[0<\int_\mathbf{G} \vert x_1\vert^{1/2}\,d\mathbf{x}\,;\quad
0<\int_\mathbf{G} \vert x_1\vert^{1/8}\vert x_2\vert^{3/8}\,d\mathbf{x}\,;\quad
0<\int_\mathbf{G} \vert x_1\vert^{1/4}\vert x_2\vert^{1/4}\,d\mathbf{x},\]
\[0<\int_\mathbf{G} \vert x_1\vert^{3/8}\vert x_2\vert^{1/8}\,d\mathbf{x}\,;\quad
0<\int_\mathbf{G} \vert x_2\vert^{1/2}\,d\mathbf{x}.\]
Hence the unique optimal solution $g^*$ of $\mathbf{P}_{2q}$ is not sparse at all. Even more,
with fixed $0<d\in\mathbb{Q}$, the larger is $q$ the more complicated is $g^*$! Therefore
an analogue of Corollary \ref{cor2} for the $\ell_2$-norm cannot exist.

\section{Appendix}

\begin{lem}
\label{lemma-appendix}
Let $d$ be a positive real and let $g:\mathbb{R}^n\to \mathbb{R}$ be the function:
\[\mathbf{x}\mapsto g(\mathbf{x})\,:=\,\sum_{i=1}^n\vert x_i\vert^d\,;\quad \mathbf{G}:=\{\,\mathbf{x}\in\mathbb{R}^n:g(\mathbf{x})\leq\,1\,\}.\]
Then:
\begin{equation}
\label{apen-1}
\int_{\mathbf{G}}\,d\mathbf{x}\,=\,\frac{2^n}{n\,d^{n-1}}\,\frac{\Gamma(1/d)^n}{\Gamma(n/d)};
\quad\int_{\mathbf{G}}\vert x_i\vert^d \,d\mathbf{x}\,=\,
\frac{2^n}{n\,(n+d)\,d^{n-1}}\,\frac{\Gamma(1/d)^n}{\Gamma(n/d)},
\end{equation}
for all $i=1,\ldots,n$.
\end{lem}
\begin{proof}
The function $g$ is positively homogeneous of degree $d$.
Observe that by Theorem \ref{th1}, $\displaystyle\int_{\mathbf{G}}d\mathbf{x}=\frac{1}{\Gamma(1+n/d)}\displaystyle\int_{\mathbb{R}^n}\exp(-g(\mathbf{x}))\,d\mathbf{x}$, and
again by Theorem \ref{th1},
\begin{eqnarray*}
\int_{\mathbb{R}^n}\exp(-g(\mathbf{x}))\,d\mathbf{x}&=&\left(\int_\mathbb{R}\exp(-\vert t\vert ^d)\,dt\right)^n\,=\,\left(\Gamma(1+\frac{1}{d})\int_{\vert t\vert^d\leq1}dt\right)^n
=\left(\frac{2\Gamma(1/d)}{d}\right)^n
\end{eqnarray*}
where we have used the identity $x\Gamma(x)=\Gamma(1+x)$. This yields the result in the
left of (\ref{apen-1}). Similarly, for every $i=1,\ldots,n$,
\begin{eqnarray*}
\int_{\mathbb{R}^n}\vert x_i\vert^d\,\exp(-g(\mathbf{x}))\,d\mathbf{x}&=&\left(\int_\mathbb{R} \vert t\vert^d\,\exp(-\vert t\vert^d)\,dt\right)\,\left(\int_\mathbb{R}\exp(-\vert t\vert^d)\,dt\right)^{n-1}\\
&=&\left(\Gamma(1+\frac{d+1}{d})\int_{\vert t\vert^d\leq1}\vert t\vert ^d \,dt\right)\left(\Gamma(1+\frac{1}{d})\int_{\vert t\vert^d\leq1}dt\right)^{n-1}\\
&=&\left(\frac{2}{d}\Gamma((d+1)/d)\right)\left(\frac{2}{d}\Gamma(1/d)\right)^{n-1}\\
&=&\frac{2^n}{d^{n+1}}\Gamma(1/d)^n.
\end{eqnarray*}
Therefore,
\[\int_{\mathbf{G}}\vert x_i\vert^d \,d\mathbf{x}\,=\,\frac{1}{\Gamma(1+\frac{n+d}{d})}\,\int_{\mathbb{R}^n}\vert x_i\vert^{d}\exp(-g(\mathbf{x}))\,d\mathbf{x}
\,=\,\frac{2^n}{n\,(n+d)\,d^{n-1}}\,\frac{\Gamma(1/d)^n}{\Gamma(n/d)}.\]
\end{proof}

redpajama_set_name: RedPajamaArXiv


text:
package org.elasticsearch.xpack.security.authz;

import org.elasticsearch.Version;
import org.elasticsearch.action.admin.indices.resolve.ResolveIndexAction;
import org.elasticsearch.action.search.SearchAction;
import org.elasticsearch.action.support.PlainActionFuture;
import org.elasticsearch.cluster.metadata.AliasMetadata;
import org.elasticsearch.cluster.metadata.DataStream;
import org.elasticsearch.cluster.metadata.IndexMetadata;
import org.elasticsearch.cluster.metadata.Metadata;
import org.elasticsearch.common.settings.Settings;
import org.elasticsearch.common.util.set.Sets;
import org.elasticsearch.index.Index;
import org.elasticsearch.test.ESTestCase;
import org.elasticsearch.transport.TransportRequest;
import org.elasticsearch.xpack.core.security.authc.Authentication;
import org.elasticsearch.xpack.core.security.authz.AuthorizationEngine;
import org.elasticsearch.xpack.core.security.authz.RoleDescriptor;
import org.elasticsearch.xpack.core.security.authz.RoleDescriptor.IndicesPrivileges;
import org.elasticsearch.xpack.core.security.authz.permission.FieldPermissions;
import org.elasticsearch.xpack.core.security.authz.permission.FieldPermissionsCache;
import org.elasticsearch.xpack.core.security.authz.permission.Role;
import org.elasticsearch.xpack.core.security.authz.privilege.IndexPrivilege;
import org.elasticsearch.xpack.core.security.authz.store.ReservedRolesStore;
import org.elasticsearch.xpack.core.security.index.RestrictedIndicesNames;
import org.elasticsearch.xpack.core.security.user.User;
import org.elasticsearch.xpack.security.authz.store.CompositeRolesStore;

import java.util.List;
import java.util.Set;

import static org.elasticsearch.cluster.metadata.DataStreamTestHelper.createTimestampField;
import static org.elasticsearch.xpack.core.security.test.TestRestrictedIndices.RESTRICTED_INDICES_AUTOMATON;
import static org.hamcrest.Matchers.contains;
import static org.hamcrest.Matchers.containsInAnyOrder;
import static org.hamcrest.Matchers.not;

public class AuthorizedIndicesTests extends ESTestCase {

    public void testAuthorizedIndicesUserWithoutRoles() {
        Set<String> authorizedIndices = RBACEngine.resolveAuthorizedIndicesFromRole(
            Role.EMPTY,
            getRequestInfo(""),
            Metadata.EMPTY_METADATA.getIndicesLookup()
        );
        assertTrue(authorizedIndices.isEmpty());
    }

    public void testAuthorizedIndicesUserWithSomeRoles() {
        RoleDescriptor aStarRole = new RoleDescriptor(
            "a_star",
            null,
            new IndicesPrivileges[] { IndicesPrivileges.builder().indices("a*").privileges("all").build() },
            null
        );
        RoleDescriptor bRole = new RoleDescriptor(
            "b",
            null,
            new IndicesPrivileges[] { IndicesPrivileges.builder().indices("b").privileges("READ").build() },
            null
        );
        Settings indexSettings = Settings.builder().put("index.version.created", Version.CURRENT).build();
        final String internalSecurityIndex = randomFrom(
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_6,
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_7
        );
        Metadata metadata = Metadata.builder()
            .put(new IndexMetadata.Builder("a1").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("a2").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("aaaaaa").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("bbbbb").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(
                new IndexMetadata.Builder("b").settings(indexSettings)
                    .numberOfShards(1)
                    .numberOfReplicas(0)
                    .putAlias(new AliasMetadata.Builder("ab").build())
                    .putAlias(new AliasMetadata.Builder("ba").build())
                    .build(),
                true
            )
            .put(
                new IndexMetadata.Builder(internalSecurityIndex).settings(indexSettings)
                    .numberOfShards(1)
                    .numberOfReplicas(0)
                    .putAlias(new AliasMetadata.Builder(RestrictedIndicesNames.SECURITY_MAIN_ALIAS).build())
                    .build(),
                true
            )
            .build();
        final PlainActionFuture<Role> future = new PlainActionFuture<>();
        final Set<RoleDescriptor> descriptors = Sets.newHashSet(aStarRole, bRole);
        CompositeRolesStore.buildRoleFromDescriptors(
            descriptors,
            new FieldPermissionsCache(Settings.EMPTY),
            null,
            RESTRICTED_INDICES_AUTOMATON,
            future
        );
        Role roles = future.actionGet();
        Set<String> list = RBACEngine.resolveAuthorizedIndicesFromRole(
            roles,
            getRequestInfo(SearchAction.NAME),
            metadata.getIndicesLookup()
        );
        assertThat(list, containsInAnyOrder("a1", "a2", "aaaaaa", "b", "ab"));
        assertFalse(list.contains("bbbbb"));
        assertFalse(list.contains("ba"));
        assertThat(list, not(contains(internalSecurityIndex)));
        assertThat(list, not(contains(RestrictedIndicesNames.SECURITY_MAIN_ALIAS)));
    }

    public void testAuthorizedIndicesUserWithSomeRolesEmptyMetadata() {
        Role role = Role.builder(RESTRICTED_INDICES_AUTOMATON, "role").add(IndexPrivilege.ALL, "*").build();
        Set<String> authorizedIndices = RBACEngine.resolveAuthorizedIndicesFromRole(
            role,
            getRequestInfo(SearchAction.NAME),
            Metadata.EMPTY_METADATA.getIndicesLookup()
        );
        assertTrue(authorizedIndices.isEmpty());
    }

    public void testSecurityIndicesAreRemovedFromRegularUser() {
        Role role = Role.builder(RESTRICTED_INDICES_AUTOMATON, "user_role")
            .add(IndexPrivilege.ALL, "*")
            .cluster(Set.of("all"), Set.of())
            .build();
        Set<String> authorizedIndices = RBACEngine.resolveAuthorizedIndicesFromRole(
            role,
            getRequestInfo(SearchAction.NAME),
            Metadata.EMPTY_METADATA.getIndicesLookup()
        );
        assertTrue(authorizedIndices.isEmpty());
    }

    public void testSecurityIndicesAreRestrictedForDefaultRole() {
        Role role = Role.builder(
            RESTRICTED_INDICES_AUTOMATON,
            randomFrom("user_role", ReservedRolesStore.SUPERUSER_ROLE_DESCRIPTOR.getName())
        ).add(IndexPrivilege.ALL, "*").cluster(Set.of("all"), Set.of()).build();
        Settings indexSettings = Settings.builder().put("index.version.created", Version.CURRENT).build();
        final String internalSecurityIndex = randomFrom(
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_6,
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_7
        );
        Metadata metadata = Metadata.builder()
            .put(new IndexMetadata.Builder("an-index").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("another-index").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(
                new IndexMetadata.Builder(internalSecurityIndex).settings(indexSettings)
                    .numberOfShards(1)
                    .numberOfReplicas(0)
                    .putAlias(new AliasMetadata.Builder(RestrictedIndicesNames.SECURITY_MAIN_ALIAS).build())
                    .build(),
                true
            )
            .build();

        Set<String> authorizedIndices = RBACEngine.resolveAuthorizedIndicesFromRole(
            role,
            getRequestInfo(SearchAction.NAME),
            metadata.getIndicesLookup()
        );
        assertThat(authorizedIndices, containsInAnyOrder("an-index", "another-index"));
        assertThat(authorizedIndices, not(contains(internalSecurityIndex)));
        assertThat(authorizedIndices, not(contains(RestrictedIndicesNames.SECURITY_MAIN_ALIAS)));
    }

    public void testSecurityIndicesAreNotRemovedFromUnrestrictedRole() {
        Role role = Role.builder(RESTRICTED_INDICES_AUTOMATON, randomAlphaOfLength(8))
            .add(FieldPermissions.DEFAULT, null, IndexPrivilege.ALL, true, "*")
            .cluster(Set.of("all"), Set.of())
            .build();
        Settings indexSettings = Settings.builder().put("index.version.created", Version.CURRENT).build();
        final String internalSecurityIndex = randomFrom(
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_6,
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_7
        );
        Metadata metadata = Metadata.builder()
            .put(new IndexMetadata.Builder("an-index").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("another-index").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(
                new IndexMetadata.Builder(internalSecurityIndex).settings(indexSettings)
                    .numberOfShards(1)
                    .numberOfReplicas(0)
                    .putAlias(new AliasMetadata.Builder(RestrictedIndicesNames.SECURITY_MAIN_ALIAS).build())
                    .build(),
                true
            )
            .build();

        Set<String> authorizedIndices = RBACEngine.resolveAuthorizedIndicesFromRole(
            role,
            getRequestInfo(SearchAction.NAME),
            metadata.getIndicesLookup()
        );
        assertThat(
            authorizedIndices,
            containsInAnyOrder("an-index", "another-index", RestrictedIndicesNames.SECURITY_MAIN_ALIAS, internalSecurityIndex)
        );

        Set<String> authorizedIndicesSuperUser = RBACEngine.resolveAuthorizedIndicesFromRole(
            role,
            getRequestInfo(SearchAction.NAME),
            metadata.getIndicesLookup()
        );
        assertThat(
            authorizedIndicesSuperUser,
            containsInAnyOrder("an-index", "another-index", RestrictedIndicesNames.SECURITY_MAIN_ALIAS, internalSecurityIndex)
        );
    }

    public void testDataStreamsAreNotIncludedInAuthorizedIndices() {
        RoleDescriptor aStarRole = new RoleDescriptor(
            "a_star",
            null,
            new IndicesPrivileges[] { IndicesPrivileges.builder().indices("a*").privileges("all").build() },
            null
        );
        RoleDescriptor bRole = new RoleDescriptor(
            "b",
            null,
            new IndicesPrivileges[] { IndicesPrivileges.builder().indices("b").privileges("READ").build() },
            null
        );
        Settings indexSettings = Settings.builder().put("index.version.created", Version.CURRENT).build();
        final String internalSecurityIndex = randomFrom(
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_6,
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_7
        );
        String backingIndex = DataStream.getDefaultBackingIndexName("adatastream1", 1);
        Metadata metadata = Metadata.builder()
            .put(new IndexMetadata.Builder("a1").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("a2").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("aaaaaa").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("bbbbb").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(
                new IndexMetadata.Builder("b").settings(indexSettings)
                    .numberOfShards(1)
                    .numberOfReplicas(0)
                    .putAlias(new AliasMetadata.Builder("ab").build())
                    .putAlias(new AliasMetadata.Builder("ba").build())
                    .build(),
                true
            )
            .put(
                new IndexMetadata.Builder(internalSecurityIndex).settings(indexSettings)
                    .numberOfShards(1)
                    .numberOfReplicas(0)
                    .putAlias(new AliasMetadata.Builder(RestrictedIndicesNames.SECURITY_MAIN_ALIAS).build())
                    .build(),
                true
            )
            .put(new IndexMetadata.Builder(backingIndex).settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(
                new DataStream(
                    "adatastream1",
                    createTimestampField("@timestamp"),
                    List.of(new Index(DataStream.getDefaultBackingIndexName("adatastream1", 1), "_na_"))
                )
            )
            .build();
        final PlainActionFuture<Role> future = new PlainActionFuture<>();
        final Set<RoleDescriptor> descriptors = Sets.newHashSet(aStarRole, bRole);
        CompositeRolesStore.buildRoleFromDescriptors(
            descriptors,
            new FieldPermissionsCache(Settings.EMPTY),
            null,
            RESTRICTED_INDICES_AUTOMATON,
            future
        );
        Role roles = future.actionGet();
        Set<String> list = RBACEngine.resolveAuthorizedIndicesFromRole(
            roles,
            getRequestInfo(SearchAction.NAME),
            metadata.getIndicesLookup()
        );
        assertThat(list, containsInAnyOrder("a1", "a2", "aaaaaa", "b", "ab"));
        assertFalse(list.contains("bbbbb"));
        assertFalse(list.contains("ba"));
        assertFalse(list.contains("adatastream1"));
        assertThat(list, not(contains(internalSecurityIndex)));
        assertThat(list, not(contains(RestrictedIndicesNames.SECURITY_MAIN_ALIAS)));
    }

    public void testDataStreamsAreIncludedInAuthorizedIndices() {
        RoleDescriptor aStarRole = new RoleDescriptor(
            "a_star",
            null,
            new IndicesPrivileges[] { IndicesPrivileges.builder().indices("a*").privileges("all").build() },
            null
        );
        RoleDescriptor bRole = new RoleDescriptor(
            "b",
            null,
            new IndicesPrivileges[] { IndicesPrivileges.builder().indices("b").privileges("READ").build() },
            null
        );
        Settings indexSettings = Settings.builder().put("index.version.created", Version.CURRENT).build();
        final String internalSecurityIndex = randomFrom(
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_6,
            RestrictedIndicesNames.INTERNAL_SECURITY_MAIN_INDEX_7
        );
        String backingIndex = DataStream.getDefaultBackingIndexName("adatastream1", 1);
        Metadata metadata = Metadata.builder()
            .put(new IndexMetadata.Builder("a1").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("a2").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("aaaaaa").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(new IndexMetadata.Builder("bbbbb").settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(
                new IndexMetadata.Builder("b").settings(indexSettings)
                    .numberOfShards(1)
                    .numberOfReplicas(0)
                    .putAlias(new AliasMetadata.Builder("ab").build())
                    .putAlias(new AliasMetadata.Builder("ba").build())
                    .build(),
                true
            )
            .put(
                new IndexMetadata.Builder(internalSecurityIndex).settings(indexSettings)
                    .numberOfShards(1)
                    .numberOfReplicas(0)
                    .putAlias(new AliasMetadata.Builder(RestrictedIndicesNames.SECURITY_MAIN_ALIAS).build())
                    .build(),
                true
            )
            .put(new IndexMetadata.Builder(backingIndex).settings(indexSettings).numberOfShards(1).numberOfReplicas(0).build(), true)
            .put(
                new DataStream(
                    "adatastream1",
                    createTimestampField("@timestamp"),
                    List.of(new Index(DataStream.getDefaultBackingIndexName("adatastream1", 1), "_na_"))
                )
            )
            .build();
        final PlainActionFuture<Role> future = new PlainActionFuture<>();
        final Set<RoleDescriptor> descriptors = Sets.newHashSet(aStarRole, bRole);
        CompositeRolesStore.buildRoleFromDescriptors(
            descriptors,
            new FieldPermissionsCache(Settings.EMPTY),
            null,
            RESTRICTED_INDICES_AUTOMATON,
            future
        );
        Role roles = future.actionGet();
        TransportRequest request = new ResolveIndexAction.Request(new String[] { "a*" });
        AuthorizationEngine.RequestInfo requestInfo = getRequestInfo(request, SearchAction.NAME);
        Set<String> list = RBACEngine.resolveAuthorizedIndicesFromRole(roles, requestInfo, metadata.getIndicesLookup());
        assertThat(list, containsInAnyOrder("a1", "a2", "aaaaaa", "b", "ab", "adatastream1", backingIndex));
        assertFalse(list.contains("bbbbb"));
        assertFalse(list.contains("ba"));
        assertThat(list, not(contains(internalSecurityIndex)));
        assertThat(list, not(contains(RestrictedIndicesNames.SECURITY_MAIN_ALIAS)));
    }

    public static AuthorizationEngine.RequestInfo getRequestInfo(String action) {
        return getRequestInfo(TransportRequest.Empty.INSTANCE, action);
    }

    public static AuthorizationEngine.RequestInfo getRequestInfo(TransportRequest request, String action) {
        final Authentication.RealmRef realm = new Authentication.RealmRef(
            randomAlphaOfLength(6),
            randomAlphaOfLength(4),
            "node0" + randomIntBetween(1, 9)
        );
        return new AuthorizationEngine.RequestInfo(
            new Authentication(new User(randomAlphaOfLength(8)), realm, realm),
            request,
            action,
            null
        );
    }
}

redpajama_set_name: RedPajamaGithub


Deciding on a grey for your walls is rather like choosing a white paint – there are more to sift through than you might ever picture. To get the best look for your space, try out plenty of samples on your walls and observe how they work in various lamps before committing. This delicate grey sits beautifully with luxe cream furniture and comforting textiles, making a harmonious scheme.
Take your look into consideration when planning for a grey colour pallette. If you prefer a modern bedroom, you may want deeper, more dramatic hues of grey. @[Team them with metal and glass for an industrial edge. In a national country, vintage or traditional bedroom scheme, bring in gentle powdery tones of blue or pink to temper the grey. Generate soothing powdery tones of pink or blue to temper the gray. One of the joys of decorating with grey is its sheer versatility – it looks great in absolutely any style of room as you will notice with our grey bedroom ideas below.
, simply click save button to save these photos for your personal computer.
Related Post "Awesome Grey Striped Bedroom Ideas"


Inside his district, though, West says he's proud his friendships with major politicians in Raleigh have helped draw attention to North Carolina's western corner.
West joins seven other members of the House Republican caucus who won't seek reelection next year.
Within hours of West's announcement, Macon County Board of Commissioners Chairman Kevin Corbin announced that he'll seek the seat. Corbin, a Republican, owns an insurance agency and performs in a gospel music group.


text:
Senior class gives back with scholarship
OLIVIA LUECKEMEYER
Filed under Lifestyle
This year's senior class gift is the gift that keeps on giving.
Departing from the tradition of installing a structural addition on campus, this year's seniors have been asked to contribute $20.13 to a scholarship for an incoming freshman. The Senior Class Gift Committee, led by Assistant Director of Annual Giving Allison Hotard, chose a scholarship as the class gift due to the rising cost of tuition.
"This year we wanted to do something different," Hotard said. "We wanted something that could impact a student greatly so that no matter how much money we raised, it would be able to help the student."
In the past, senior class gifts have included physical on-campus additions such as the bicycle racks, the streetcar statue in the Peace Quad and the clock by Monroe Library.
"While the clock is beautiful and a great thing to have, and it will most likely always be there, it won't really serve a purpose if there aren't any students to see that clock because they couldn't afford to come here," Margaret Vienne, English writing senior and member of the Senior Class Gift Committee, said.
The scholarship will be given by Sal Liberto, vice president for enrollment management and associate provost, through the office of admissions. It will be for one-time use and given to an incoming freshman. A criterion has been established to determine which student will receive the scholarship. Once chosen, that student is free to use the money however they see fit, whether that be for books, room and board or to cover part of their tuition.
With tuition increasing, Hotard said the scholarship should help soften the blow.
"I think with people concerned over the cost of tuition rising, it
is a good way to cushion that," Hotard said.
Seniors have mixed feelings about the decision to give a scholarship rather than a material gift. Sociology senior Camille Fiess said she was pleasantly surprised by the change.
"Although past gifts are still present on campus and will technically leave a longer lasting memory of the graduating classes, I ultimately feel that the best way to honor the school is by helping another student join the community," Fiess said.
Although the recommended donation is $20.13, students are encouraged to give any amount, big or small. Students who donated by April 5 were also given the opportunity to name their gift in honor of someone who has made their education at Loyola possible.
Fiess said her biggest incentive to donate was the chance to show her parents her gratitude.
"My parents have supported me throughout my entire education at Loyola, and I feel it is important for me to convey my appreciation to them," Fiess explained. "Plus, I think they will get a kick out of having their names in the graduation program."
Other students prefer to pay respects to their parents in different ways.
"I would rather do something more personal for those people who helped shape my educational career than donate to the class gift," Ally Hodapp, mass communication senior, said.
As of April 11, the donation amount was $1,353.00, with 56 out of 888 graduating seniors having given to the scholarship.
"The amount of donors is up from last year, and I think that has something to do with the type of gift we are doing. More people are willing to donate when they know it is going towards a scholarship," Vienne said.
In order to raise that number before the May 10 deadline, Vienne said the committee plans to continue reaching out to students through tabling in the Danna Student Center and at events where seniors are present. They also plan to continue their social media outreach, specifically through utilizing the twitter hashtag #Igave.
Earlier in the semester the committee participated in a fundraising competition with fellow Jesuit university Spring Hill College. Each university set up a web page for online donations to see who could get the greatest number of senior class gift donors.
"It was a friendly Jesuit competition and we had the majority of online donations," Vienne said.
Perhaps the biggest incentive to donate is one that is in no way related to the senior class gift. In honor of the university's centennial celebration, an anonymous donor recently offered to give $100,000 to Loyola if they can get 2,500 new donors by the end of this semester. A new donor is one that has contributed any amount of money since August 2012. Senior class gift donations will also apply to the Centennial Challenge.
"Even if a senior just gives $5, that is still contributing to the senior class gift that will then contribute to that goal of
2,500 donors. So seniors should know that your little bit will count and hopefully bring in another $100,000," Vienne said.
If the university meets the challenge the donation will go into the Loyola fund, which allows the president to use the money when and where he sees fit. Currently, the amount of donors is 620.
Hotard noted that the scholarship is reflective of the Jesuit incentive of being "men and women for others."
"It is part of the Jesuit tradition of helping others," Hotard said. "It helps instill that in students, and it is a way to leave your legacy for future generations at Loyola."
For many students at Loyola, the scholarships they received are what made their college education possible. The goal of the senior class gift is to continue this tradition.
"I know without the scholarship I would not be at Loyola," Vienne said. "When I think back on my Loyola experience, I want someone to have an experience like mine, or an experience even better, and for some students that is not possible without a scholarship."
Olivia Lueckemeyer can be reached at [email protected]
Two Poems by Fallon Chiasson
2:59 by Emily Gil
A Wish For One by Kaitlyn Cleveland
Five Best Off Campus Study Spots
Horoscopes before Thanksgiving break
Local tour merges the haunted and the historic
How to slay Halloween in New Orleans
Beau helps students through ruff times
Blue Cypress Books: A decade on Oak Street
Gallery: Fall Break expectations in Southern Louisiana

redpajama_set_name: RedPajamaCommonCrawl


Located in the heart of Madrid among the most emblematic museums and hotels in Spain. A space of gastronomic culture, recognized for its Mediterranean cuisine and its Catalan roots, with multiple spaces for each moment.
Informal space to relax after a long day or during the hard day. In this space you can take home our organic products or taste them, as you like.
With capacity for 30 people and with option for cocktail or welcome drinks with capacity up to 50 diners.
With a capacity of 80/90 guests, the ideal space for the lunches of the day to day where the culinary quality and the service will make possible a pleasant experience.
This room has a maximum capacity for 20 people, ideal place to organize from private breakfasts to any unique gastronomic encounter.
Our rustic private room has a capacity between 10 and 24 people. It has a 42 "screen with vga connection for your presentations.
Our private room Winery, named for the views that has the heated winery. This room has a 32 "LCD screen with hdmi connection for your presentations.
Paradis Madrid has the collaboration of the international interior designer; Pascua Ortega in the development of the concept of natural decoration of our spaces.


text:
Trovit House South West England City of Bristol Bristol Bristol house planning permission
Bristol house planning permission
Receive new listings by email bristol house planning permission
Henbury 1
Radford 1
Village 1
Radstock 4
South Molton 3
Devon 20
Cottage 1
Detached 2
Mews 1
Semi Detached 8
Terraced house 7
Similar searches "bristol house planning permission ":
8 bedroom house liverpool
house 5 bedroom falmouth
planning permission land buckinghamshire
house renovation project london
hartshorne swadlincote
semi detached 3 bedroom fishponds
shared ownership cornwall
bovis bristol
detached part exchange exeter
house stones parking bristol
new house poole
house 3 bedroom morton
Planning granted - 2 bed mews
BS3 4AE, Bristol, City of Bristol, South West England
Hollis Morgan. Freehold building plot with planning granted to erect a stylish 2 bed mews house. GDV 275k The Land. A parcel of land adjacent...
Land At Dorester Close, Bristol BS10, 2 bedroom land
BS10 6PB, Brentry, Bristol, City of Bristol, South West England
...granted to build a two bedroom house adjacent to the existing properties. Please see the council planning website for further information.
Peartree Lane, Kingswood, Bristol BS15, 3 bedroom land
BS15 4SG, Bristol, City of Bristol, South West England
A rare opportunity to purchase this three bedroom end of terrace house with generous garden, garage and off street parking. The property has...
Hillside Road, Portishead, Bristol BS20, 4 bedroom detached...
BS20 8LJ, Bristol, City of Bristol, South West England
Guide Price £435,000. Located in a prime position on Portishead Hillside affording views over the Bristol Channel with planning permission...
The Avenue, Patchway, Bristol BS34, 3 bedroom semi-detached...
BS34 6BD, Patchway, Bristol, City of Bristol, South West England
Offered with no onward chain and so much potential to renovate or extend, subject to planning permission. This semi detached home is set...
Property Pigeon 30+ days ago
3 Bed Terraced For Sale Avon Bristol
BS16 4QP, Bristol, City of Bristol, South West England
...to acquire a centre of town traditional fish and chip shop, with owners accommodation and a plot of land for development with planning...
Propertymutual 30+ days ago
4 Bedroom Terraced House For Sale Orchard Street Bristol...
BS1, Bristol, City of Bristol, South West England
...permission for a full width kitchen across the rear of the property. The upper floors boast a further reception with wood burner, three...
£950,000 £1,100,000
Cleeve Hill, Downend, Bristol BS16, 3 bedroom semi-detached...
BS16 6HN, Bristol, City of Bristol, South West England
...permission for a rear extension to create a more contemporary open living layout, with views across the garden. The first floor offers two...
Cabstand, Portishead, Bristol BS20, land
BS20 7HW, Bristol, City of Bristol, South West England
Full planning permission reference 19/P/1852/FUL has been granted to demolish outbuildings and build a substantial bedroom detached house...
Property Pigeon 29 days ago
5 Bed Property For Sale Nordrach Lane Bristol
BS40 6LG, Bristol, City of Bristol, South West England
A superb five bedroom detached family house set within the countryside village of Compton Martin. This Farmhouse offers generous accommodation...
4 Bed End of Terrace For Sale Fiddes Road Bristol
BS6 7TN, Bristol, City of Bristol, South West England
Under Construction. Gregory & Main are delighted to offer to the market this 4 bedroom end of terrace house. Currently being rebuilt from head...
4 Bed Terraced For Sale Grove Park Avenue Bristol
BS4 4JQ, Bristol, City of Bristol, South West England
...floor and to the second floor contains a double bedroom dormer extension complete with an en-suite shower room and containing full planning...
Onedome 30+ days ago
2 bedrooms house for sale
BS30, Bristol, City of Bristol, South West England
...cottage style rear gardens with ample off street parking and stabling with permission to convert to an annexe (planning ref PK16/4628/F)
3 Bed Semi-Detached For Sale Westmead Road Bristol
BS5 8NY, Bristol, City of Bristol, South West England
...requiring some modernisation the property would make a comfortable family home and there is also potential to extend, subject to planning...
Firgrove Crescent, Yate BS37, 3 bedroom semi-detached house...
BS37 7AH, Bristol, City of Bristol, South West England
...station. The property is well presented and offers lots of potential to improve and extend (subject to planning permission). On the ground.
Woollard Lane, Woollard, Publow, Somerset BS14, 3 bedroom...
BS14 0QT, Whitchurch, Bristol, City of Bristol, South West England
...yet only 5.2 miles from Bristol and 8.6 miles from Bath. The vendor says: "We converted the barn about 12 years ago. It had been used for.
...open out onto a patio area, which has been pre-wired for a hot tub, with the rest of the garden laid to low maintenance Astroturf, with planning...
...you will find a generous sized rear garden, front garden and garage with driveway parking. *The property also benefits from having planning...
£425,000 £440,000
TheHouseShop.com 30+ days ago
2 Bed House for Sale
BS16 5RJ, Bristol, City of Bristol, South West England
...The rear garden measures approximately 125ft in length and is mainly laid to lawn. The owner also informs us there was previously planning...
BS16 5UW, Bristol, City of Bristol, South West England
...rear. Further benefits include, gas central heating, double glazing and views across Downend Cricket Club. The owner has also obtained planning...
Grove Park Avenue, Brislington, Bristol BS4, 4 bedroom...
BS4 4JQ, Brislington, Bristol, City of Bristol, South West England
...contains a double bedroom dormer extension complete with an en-suite shower room and containing full planning permission. The property further.
Westmead Road, St George, Bristol BS5, 3 bedroom...
BS5 8NY, St. George, Bristol, City of Bristol, South West England
...the property would make a comfortable family home and there is also potential to extend, subject to planning permission if more space is.
Fidelis Properties 30+ days ago
Uplands Road Saltford, Bristol £635,000
Bath and North East Somerset, South West England
...restaurants. Bath Spa Railway Station provides high speed links to London Paddington (approx. 90 minutes), Bristol Temple Meads and the West
Andrews Online 30+ days ago
3 bedroom, End Terraced House Passage Road, Henbury...
Henbury, Bristol, City of Bristol, South West England
...and superb family bathroom. Planning permission has been granted (Reference 18/00---/F) to create a house on the plot of land to the side.
4 bedroom, Detached House Hurn Lane, Keynsham, Bristol...
Keynsham, Bristol, City of Bristol, South West England
...Bristol & Bath and boasts a thriving High street with an array of shops, cafes and restaurants along with well regarded schools, library and...
Be the first to find out about new listings for bristol house planning permission