* [65] M. Reed and B. Simon, “II: Fourier Analysis, Self-Adjointness,”, vol. 2.  Elsevier, 1975.
  * [66] M. Riesz, “Sur le problème des moments, Troisième Note,” Ark. Mat. Fys 16, 1–52 (1923).
  * [67] E. Haviland, “On the momentum problem for distribution functions in more than one dimension. II,” American Journal of Mathematics 58, 164–168 (1936).
  * [68] D. Hilbert, “Über die darstellung definiter formen als summe von formenquadraten,” Mathematische Annalen 32, 342–350 (1888).
  * [69] H. W. Gould, “Combinatorial Identities: A standardized set of tables listing 500 binomial coefficient summations,”.  Morgantown, W Va, 1972.
  * [70] D. Zeilberger, “The method of creative telescoping,” Journal of Symbolic Computation 11, 195–204 (1991).
  * [71] U. Leonhardt, “Quantum-state tomography and discrete Wigner function,” Physical Review Letters 74, 4101 (1995).
  * [72] D. Gross, “Hudson’s theorem for finite-dimensional quantum systems,” Journal of mathematical physics 47, 122107 (2006).
  * [73] R. W. Spekkens, “Negativity and contextuality are equivalent notions of nonclassicality,” Physical Review Letters 101, 020401 (2008).
  * [74] N. Delfosse, C. Okay, J. Bermejo-Vega, D. E. Browne, and R. Raussendorf, “Equivalence between contextuality and negativity of the Wigner function for qudits,” New Journal of Physics 19, 123024 (2017).
  * [75] R. Raussendorf, D. E. Browne, N. Delfosse, C. Okay, and J. Bermejo-Vega, “Contextuality and Wigner-function negativity in qubit quantum computation,” Physical Review A 95, 052334 (2017).
  * [76] M. Howard, J. Wallman, V. Veitch, and J. Emerson, “Contextuality supplies the ‘magic’ for quantum computation,” Nature 510, 351 (2014).
  * [77] J. Bermejo-Vega, N. Delfosse, D. E. Browne, C. Okay, and R. Raussendorf, “Contextuality as a resource for models of quantum computation with qubits,” Physical Review Letters 119, 120505 (2017).
  * [78] R. S. Barbosa, T. Douce, P.-E. Emeriau, E. Kashefi, and S. Mansfield, “Continuous-variable nonlocality and contextuality,” arXiv:1905.08267.
  * [79] M. Navascués, S. Pironio, and A. Acín, “A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations,” New Journal of Physics 10, 073013 (2008).
  * [80] R. E. Curto and L. A. Fialkow, “An analogue of the Riesz–Haviland theorem for the truncated moment problem,” Journal of Functional Analysis 255, 2709–2731 (2008).
  * [81] D. Henrion and M. Korda, “Convex computation of the region of attraction of polynomial control systems,” IEEE Transactions on Automatic Control 59, 297–312 (2014).
  * [82] J.-B. Lasserre, “Moments, positive polynomials and their applications,” in Series on Optimization and its Applications, vol. 1.  Imperial College Press, 2009.

##  Appendix A Riesz–Haviland theorem in Laguerre basis

Let $\bm{\nu}=(\nu_{l})_{l\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$. Let us
introduce the Riesz functional

$\displaystyle L_{\bm{\nu}}:\quad\mathbb{R}[x]$
$\displaystyle\longrightarrow\quad\mathbb{R}$ (79) $\displaystyle
P(x)=\sum_{k=0}^{p}p_{k}x^{k}$
$\displaystyle\longmapsto\quad\sum_{k=0}^{p}p_{k}\nu_{k},$

which maps real polynomials to real numbers. Let $K$ be a closed subset of
$\mathbb{R}$. We say that $L_{\bm{\nu}}$ is $K$-non-negative if
$L_{\bm{\nu}}(P)\geq 0$ for all $P\in\mathbb{R}[x]$ non-negative on $K$. We
recall the classical Riesz–Haviland theorem [66, 67] (see, e.g., [80] for a
recent formulation):

######  Theorem 7 (Riesz–Haviland).

The sequence $\bm{\nu}=(\nu_{k})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$
is the sequence of moments $\int_{K}x^{k}d\nu(x)$ of a non-negative
distribution $\nu$ supported on $K$ if and only if $L_{\bm{\nu}}$ is $K$-non-
negative.

We prove a modified version of this result in the basis of Laguerre functions.
To that end, we introduce the following change of basis:

######  Lemma 8.

Let $\bm{\mu},\bm{\nu}\in\mathbb{R}^{\mathbb{N}}$. For all $m\in\mathbb{N}$,
the following conditions are equivalent:

  1. (i)

$\forall k\in\llbracket
0,m\rrbracket,\quad\mu_{k}=\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}$,

  2. (ii)

$\forall l\in\llbracket
0,m\rrbracket,\quad\nu_{l}=\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!$.

As a direct consequence, we retrieve the formula:

$x^{l}=\sum_{k=0}^{l}(-1)^{k}\binom{l}{k}l!L_{k}(x),$ (80)

for all $l\in\mathbb{N}$ and all $x\in\mathbb{R}_{+}$.

###### Proof.

(i)$\Rightarrow$(ii): suppose that

$\forall k\in\llbracket
0,m\rrbracket,\quad\mu_{k}=\sum_{p=0}^{k}\nu_{p}\frac{(-1)^{k+p}}{p!}\binom{k}{p}.$
(81)

Then, for all $l\in\llbracket 0,m\rrbracket$,

$\displaystyle\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!$
$\displaystyle=\sum_{k=0}^{l}\sum_{p=0}^{k}\nu_{p}\frac{(-1)^{k+p}}{p!}\binom{k}{p}\binom{l}{k}l!$
(82)
$\displaystyle=\sum_{p=0}^{l}\nu_{p}\frac{l!}{p!}\binom{l}{p}\sum_{k=p}^{l}(-1)^{k-p}\binom{l-p}{k-p}$
$\displaystyle=\sum_{p=0}^{l}\nu_{p}\frac{l!}{p!}\binom{l}{p}\sum_{q=0}^{l-p}(-1)^{q}\binom{l-p}{q}$
$\displaystyle=\nu_{l},$

where we used Eq. (81) in the first line and the binomial theorem in the last
line which imposes $l=p$.

(ii)$\Rightarrow$(i): suppose that

$\forall l\in\llbracket
0,m\rrbracket,\quad\nu_{l}=\sum_{p=0}^{l}\mu_{p}\binom{l}{p}l!.$ (83)

Then, for all $k\in\llbracket 0,m\rrbracket$,

$\displaystyle\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}$
$\displaystyle=\sum_{l=0}^{k}\sum_{p=0}^{l}\mu_{p}(-1)^{k+l}\binom{l}{p}\binom{k}{l}$
(84)
$\displaystyle=\sum_{p=0}^{k}\mu_{p}(-1)^{k+p}\binom{k}{p}\sum_{l=p}^{k}(-1)^{l-p}\binom{k-p}{l-p}$
$\displaystyle=\sum_{p=0}^{k}\mu_{p}(-1)^{k+p}\binom{k}{p}\sum_{q=0}^{k-p}(-1)^{q}\binom{k-p}{q}$
$\displaystyle=\mu_{k},$

where we used Eq. (83) in the first line and the binomial theorem in the last
line which imposes $k=p$.

∎

We may now prove the Riesz–Haviland theorem in Laguerre basis (Theorem 1 from
the main text):

######  Theorem 1.

Let $\bm{\mu}=(\mu_{k})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$. The
sequence $\bm{\mu}$ is the sequence of Laguerre moments
$\int_{\mathbb{R}_{+}}\mathcal{L}_{k}(x)d\mu(x)$ of a non-negative
distribution $\mu$ supported on $\mathbb{R}_{+}$ if and only if

$\forall m\in\mathbb{N},\forall
g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}),\;\braket{f_{\bm{\mu}},g}\geq 0.$ (85)

###### Proof.

Let $\bm{\mu}=(\mu_{k})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$, and
suppose that the sequence $\bm{\mu}$ is the sequence of Laguerre moments
$\int_{\mathbb{R}_{+}}\mathcal{L}_{k}(x)d\mu(x)$ of a non-negative
distribution $\mu$ supported on $\mathbb{R}_{+}$.

Let $m\geq 0$ and let
$g=\sum_{k=0}^{m}g_{k}\mathcal{L}_{k}\in\mathcal{R}_{m,+}(\mathbb{R}_{+})$.
The distribution $\mu$ is non-negative, so $\braket{\mu,g}\geq 0$. Moreover,

$\displaystyle\braket{f_{\bm{\mu}},g}$
$\displaystyle=\sum_{k=0}^{m}{\mu_{k}g_{k}}$ (86)
$\displaystyle=\int_{\mathbb{R}_{+}}\sum_{k=0}^{m}{g_{k}\mathcal{L}_{k}d\mu}$
$\displaystyle=\braket{\mu,g}.$

Hence, for all $m\in\mathbb{N}$ and all
$g\in\mathcal{R}_{m,+}(\mathbb{R}_{+})$, $\braket{f_{\bm{\mu}},g}\geq 0$.

Conversely, let
$\bm{\mu}=(\mu_{k})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$, and suppose
that for all $m\in\mathbb{N}$ and all $g\in\mathcal{R}_{m,+}(\mathbb{R}_{+})$,
$\braket{f_{\bm{\mu}},g}\geq 0$. We define the sequence
$\bm{\nu}=(\nu_{l})_{l\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$ by

$\nu_{l}:=\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!,$ (87)

for all $l\in\mathbb{N}$.

Let $m\in\mathbb{N}$ and let $P(x)=\sum_{l=0}^{m}p_{l}x^{l}$ be a non-negative
polynomial over $\mathbb{R}_{+}$. By Eq. (80), for all $x\in\mathbb{R}_{+}$,

$\displaystyle P(x)$
$\displaystyle=\sum_{l=0}^{m}p_{l}\sum_{k=0}^{l}(-1)^{k}\binom{l}{k}l!L_{k}(x)$
(88)
$\displaystyle=\sum_{k=0}^{m}(-1)^{k}L_{k}(x)\left(\sum_{l=k}^{m}p_{l}\binom{l}{k}l!\right).$

Let $g_{P}(x):=P(x)e^{-\frac{x}{2}}$, for $x\in\mathbb{R}_{+}$. We have
$g_{P}\in\mathcal{R}_{m,+}(\mathbb{R}_{+})$, so
$\braket{f_{\bm{\mu}},g_{P}}\geq 0$. Moreover, with Eq. (88)

$\displaystyle\braket{f_{\bm{\mu}},g_{P}}$
$\displaystyle=\sum_{k=0}^{m}\mu_{k}\left(\sum_{l=k}^{m}p_{l}\binom{l}{k}l!\right)$
(89)
$\displaystyle=\sum_{l=0}^{m}\left(\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!\right)p_{l}$
$\displaystyle=L_{\bm{\nu}}(P)$

where we used Eq. (87) and the definition of the Riesz functional from Eq.
(79) in the last line. In particular, $L_{\bm{\nu}}(P)\geq 0$, and this holds
for all non-negative polynomials $P$ over $\mathbb{R}_{+}$. By the
Riesz–Haviland theorem (Theorem 7), this implies that $\bm{\nu}$ is the
sequence of moments of a non-negative distribution $\nu$ supported on
$\mathbb{R}_{+}$.

Furthermore, we have that for all $k\in\mathbb{N}$:

$\displaystyle\mu_{k}$
$\displaystyle=\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}$ (90)
$\displaystyle=\sum_{l=0}^{k}\frac{(-1)^{k+l}}{l!}\binom{k}{l}\int_{\mathbb{R}_{+}}x^{l}d\nu(x)$
$\displaystyle=\int_{\mathbb{R}_{+}}(-1)^{k}\sum_{l=0}^{k}\frac{(-1)^{l}}{l!}\binom{k}{l}x^{l}d\nu(x)$
$\displaystyle=\int_{\mathbb{R}_{+}}(-1)^{k}L_{k}(x)d\nu(x)$
$\displaystyle=\int_{\mathbb{R}_{+}}\mathcal{L}_{k}(x)e^{\frac{x}{2}}d\nu(x)$

where we used Lemma 8 in the first line. Hence, $\bm{\mu}$ is the sequence of
Laguerre moments of the distribution $\mu(x):=e^{\frac{x}{2}}\nu(x)$ supported
on $\mathbb{R}_{+}$, which is non-negative since $\nu$ is non-negative.

∎

##  Appendix B Theory for infinite-dimensional linear programs

This appendix is dedicated to expressing formally our linear program as
presented in [61, IV–(6.1)] so that readers unfamiliar with global
optimisation may better understand why (LP${}_{n}^{L^{2}}$) is indeed an
infinite-dimensional linear program and how to derive its dual program. We
will derive it for the problem over square-integrable functions. The exact
same treatment can be applied for the case of optimising over Schwartz
functions which will involve $\mathcal{S}(\mathbb{R}_{+})$ and its dual space
$\mathcal{S}^{\prime}(\mathbb{R}_{+})$, the space of tempered distributions.
We recall our initial program (LP${}_{n}^{L^{2}}$):

$\displaystyle\hskip 113.81102pt\left\\{\begin{aligned}
&&&\underset{(F_{k})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}}{\text{sup}}F_{n}\\\
&\text{subject to}&&\sum_{k}F_{k}=1\\\ &\text{and}&&\forall
k\in\mathbb{N},\quad F_{k}\geq 0\\\ &\text{and}&&\forall
x\in\mathbb{R}_{+},\quad\sum_{k}F_{k}\mathcal{L}_{k}(x)\geq
0.\end{aligned}\right.$ (LP${}_{n}^{L^{2}}$)

Let us introduce the spaces:

  * •

$E_{1}=\ell^{2}\times L^{2}(\mathbb{R}_{+})$999Recall that via expansion on a
basis of $L^{2}(\mathbb{R}_{+})$, $L^{2}(\mathbb{R}_{+})$ and $\ell^{2}$ are
isomomorphic and that the family of Laguerre functions forms a basis of
$L^{2}(\mathbb{R}_{+})$..

  * •

$F_{1}=\ell^{2}\times L^{2}(\mathbb{R}_{+})$101010The spaces
$L^{2}(\mathbb{R}_{+})$ and ${L^{2}}^{\prime}(\mathbb{R}_{+})$ are
isomomorphic by the Radon–Nikodym theorem. We associate a measure in the dual
of ${L^{2}}(\mathbb{R}_{+})$ with the Lebesgue measure on $\mathbb{R}_{+}$
times the corresponding function in $L^{2}(\mathbb{R}_{+})$. the dual space of
$E_{1}$.

  * •

$E_{2}=\mathbb{R}\times L^{2}(\mathbb{R}_{+})$.

  * •

$F_{2}=\mathbb{R}\times L^{2}(\mathbb{R}_{+})$ the dual space of $E_{2}$.

We also define the dualities
$\langle\text{--},\text{--}\rangle_{1}:E_{1}\times
F_{1}\longrightarrow\mathbb{R}$ and
$\langle\text{--},\text{--}\rangle_{2}:E_{2}\times
F_{2}\longrightarrow\mathbb{R}$ as follows:

$\displaystyle\forall e_{1}=((u_{k}),f)\in E_{1},\forall
f_{1}=((v_{k}),\mu)\in F_{1},$ $\displaystyle\langle
e_{1},f_{1}\rangle_{1}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\sum_{k}u_{k}v_{k}+\int_{\mathbb{R}_{+}}{f}{d\mu},$
(91) $\displaystyle\forall e_{2}=(x,f)\in E_{2},\forall f_{2}=(y,\mu)\in
F_{2},$ $\displaystyle\langle
e_{2},f_{2}\rangle_{2}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}xy+\int_{\mathbb{R}_{+}}{f}{d\mu}.$

Let $A\colon E_{1}\longrightarrow E_{2}$ be the following linear
transformation:

$\forall e_{1}=((u_{k}),f)\in E_{1},\quad
A(e_{1})\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\left(\sum_{k}u_{k},x\in\mathbb{R}_{+}\mapsto
f(x)-\sum_{k}u_{k}\mathcal{L}_{k}(x)\right),$ (92)

and $A^{*}\colon F_{2}\longrightarrow F_{1}$ be defined as:

$\forall f_{2}=(y,\mu)\in F_{2},\quad
A^{*}(f_{2})\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\left((y-\int_{\mathbb{R}_{+}}{\mathcal{L}_{k}}{d\mu})_{k\in\mathbb{N}},\mu\right).$
(93)

We can easily verify that $A^{*}$ is the dual transformation of $A$, i.e.,
$\forall e_{1}\in E_{1},\forall f_{2}\in F_{2}$ we have $\langle
A(e_{1}),f_{2}\rangle_{2}=\langle e_{1},A^{*}(f_{2})\rangle_{1}$.

Recall that $L^{2}_{+}(\mathbb{R}_{+})$ is the cone of non-negative functions
in $L^{2}(\mathbb{R}_{+})$ and $\ell^{2}_{+}$ the cone of sequences in
$\ell^{2}$ with non-negative coefficients. We will optimise in the convex
cones $K_{1}=\ell^{2}_{+}\times L^{2}_{+}(\mathbb{R}_{+})\subset E_{1}$ and
$K_{2}=\\{0\\}$. The dual cones are then respectively: $K_{1}^{*}=\\{f_{1}\in
F_{1}:\forall e_{1}\in K_{1},\;\langle e_{1},f_{1}\rangle\geq 0\\}$ and
$K_{2}^{*}=F_{2}$.

We can now rewrite the problem (LP${}_{n}^{L^{2}}$) as a standard linear
program in convex cones. We choose the vector function in the objective to be
$c_{n}=((\delta_{kn})_{k},\mathbf{0})\in F_{1}$ and we also set
$b=(1,\mathbf{0})\in E_{2}$ for the constraints. The standard form of
(LP${}_{n}^{L^{2}}$) in the sense of [61] can be written as follows:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned} &&&\sup_{e_{1}\in
E_{1}}\langle e_{1},c_{n}\rangle_{1}\\\ &\text{subject to}&&A(e_{1})=b\\\
&\text{and}&&e_{1}\geq_{K_{1}}0.\\\ \end{aligned}\right.$ (LP${}_{n}^{L^{2}}$)

The standard form of the dual (D-LP${}_{n}^{L^{2}}$) of problem
(LP${}_{n}^{L^{2}}$) can be expressed as follows:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\operatorname*{\vphantom{p}inf}_{f_{2}\in F_{2}}\langle
b,f_{2}\rangle_{2}\\\ &\text{subject
to}&&A^{*}(f_{2})\geq_{K_{1}^{*}}c_{n},\\\ \end{aligned}\right.$
(D-LP${}_{n}^{L^{2}}$)

which can be expanded as:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}y\in\mathbb{R}\\\
\mu\in{L^{2}}^{\prime}(\mathbb{R}_{+})\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&\forall k\in\mathbb{N},\quad
y\geq\int_{\mathbb{R}_{+}}{\mathcal{L}_{k}}{d\mu}\\\ &\text{and}&&y\geq
1+\int_{\mathbb{R}_{+}}{\mathcal{L}_{n}}{d\mu}\\\ &\text{and}&&\forall f\in
L^{2}_{+}(\mathbb{R}_{+}),\quad\langle\mu,f\rangle=\int_{\mathbb{R}_{+}}fd\mu\geq
0.\\\ \end{aligned}\right.$ (D-LP${}_{n}^{L^{2}}$)

Note that a similar derivation holds for the more general form where one uses
a linear combination of fidelities with Fock states. The displaced Fock states
version can be obtained by classical post-processing as detailed in section
2.2. For $n\in\mathbb{N}^{*}$ and some vector
$\bm{a}=(a_{1},a_{2},\dots,a_{n})\in[0,1]^{n}$, the computation of:

$\omega_{\bm{a}}:=\sup_{\begin{subarray}{c}\rho\in\mathcal{D}(\mathcal{H})\\\
W_{\rho}\geq
0\end{subarray}}\text{Tr}\left(\hat{\Omega}_{\bm{a},0}\rho\right),$ (94)

can be expressed as:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{(F_{k})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}}{\text{sup}}\sum_{k=1}^{n}a_{k}F_{k}\\\
&\text{subject to}&&\sum_{k}F_{k}=1\\\ &\text{and}&&\forall
k\in\mathbb{N},\quad F_{k}\geq 0\\\ &\text{and}&&\forall
x\in\mathbb{R}_{+},\quad\sum_{k}F_{k}\mathcal{L}(x)\geq
0.\end{aligned}\right.$ ($\text{LP}_{\bm{a}}^{L^{2}}$)

Its dual reads:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}y\in\mathbb{R}\\\
\mu\in{L^{2}}^{\prime}(\mathbb{R}_{+})\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&\forall k\leq n\in\mathbb{N},\quad y\geq
a_{k}+\int_{\mathbb{R}_{+}}{\mathcal{L}_{k}}{d\mu}\\\ &\text{and}&&\forall
k>n\in\mathbb{N},\quad y\geq\int_{\mathbb{R}_{+}}{\mathcal{L}_{k}}{d\mu}\\\
&\text{and}&&\forall f\in
L^{2}_{+}(\mathbb{R}_{+}),\quad\langle\mu,f\rangle=\int_{\mathbb{R}_{+}}fd\mu\geq
0.\\\ \end{aligned}\right.$ ($\text{D-LP}_{\bm{a}}^{L^{2}}$)

##  Appendix C Proof of technical lemmas

In this section we prove the technical lemmas from section 5.4. For
completeness, we include the proof of Lemma 3 below:

######  Lemma 3 ([68]).

Let $p\in\mathbb{N}$ and let $P$ be a univariate polynomial of degree $2p$.
Let $X=(1,x,\dots,x^{p})$ be the vector of monomials. Then, $P$ is non-
negative over $\mathbb{R}$ if and only if there exists a sum of squares
decomposition for $P$, i.e., a real $(p+1)\times(p+1)$ positive semidefinite
matrix $Q$ such that for all $x\in\mathbb{R}$,

$P(x)=X^{T}QX.$ (95)

###### Proof.

If for all $x\in\mathbb{R}$, $P(x)=X^{T}QX$ with $X=(1,x,\dots,x^{p})$ for $Q$
positive semidefinite, then $P$ is clearly non-negative over $\mathbb{R}$.

Conversely, suppose the univariate polynomial $P$ of degree $2p$ is non-
negative over $\mathbb{R}$. It can thus be written as a sum of squares of
polynomials of degree at most $p$ (e.g., by considering the factorisation of
$P$ and writing each term in the product as a sum of squares, given that its
zeros on the real line have even multiplicity and that each complex zero is
associated to a conjugate zero with same multiplicity): for all
$x\in\mathbb{R}$,

$P(x)=\sum_{i}S_{i}^{2}(x),$ (96)

for some real polynomials $S_{i}$ of degree at most $p$. Then, for some
vectors of coefficients $\bm{s}_{i}\in\mathbb{R}^{p+1}$ we have

$\displaystyle P(x)$ $\displaystyle=\sum_{i}(\bm{s}_{i}^{T}X)^{2}$ (97)
$\displaystyle=\sum_{i}(X^{T}\bm{s}_{i})(\bm{s}_{i}^{T}X)$
$\displaystyle=X^{T}\left(\sum_{i}\bm{s}_{i}\bm{s}_{i}^{T}\right)X.$

Setting $Q:=\sum_{i}\bm{s}_{i}\bm{s}_{i}^{T}\succeq 0$ completes the proof. ∎

We now turn to the proof of Lemma 4:

######  Lemma 4.

Non-negative polynomials on $\mathbb{R}_{+}$ can be written as sums of
polynomials of the form $\sum_{l=0}^{p}x^{l}\sum_{i+j=2l}y_{i}y_{j}$, where
$p\in\mathbb{N}$ and $y_{i}\in\mathbb{R}$, for all $0\leq i\leq p$.

###### Proof.

Let $P$ be a univariate polynomial of degree $p$ which is non-negative on
$\mathbb{R}_{+}$. Writing $X=(1,x,\dots,x^{p})$, the polynomial $x\mapsto
P(x^{2})$ of degree $2p$ is non-negative on $\mathbb{R}$, so by Lemma 3 there
exists a real positive semidefinite matrix $Q=(Q_{ij})_{0\leq i,j\leq p}$ such
that for all $x\in\mathbb{R}$:

$\displaystyle P(x^{2})$ $\displaystyle=X^{T}QX$ (98)
$\displaystyle=\sum_{k=0}^{2p}x^{k}\sum_{i+j=k}Q_{ij}$
$\displaystyle=\sum_{l=0}^{p}x^{2l}\sum_{i+j=2l}Q_{ij},$

where the last line comes from the fact that $x\mapsto P(x^{2})$ has no
monomial of odd degree. Hence, for all $x\in\mathbb{R}_{+}$,

$P(x)=\sum_{l=0}^{p}x^{l}\sum_{i+j=2l}Q_{ij}.$ (99)

$Q$ is a real $(p+1)\times(p+1)$ positive semidefinite matrix, so via Cholesky
decomposition

$Q=\sum_{k=0}^{p}\bm{y}^{(k)}\bm{y}^{(k)T},$ (100)

where $\bm{y}^{(k)}\in\mathbb{R}^{p+1}$ for all $k\in\llbracket
0,p\rrbracket$. We finally obtain, for all $x\in\mathbb{R}_{+}$,

$\displaystyle P(x)$
$\displaystyle=\sum_{l=0}^{p}x^{l}\sum_{i+j=2l}\sum_{k=0}^{p}\left(\bm{y}^{(k)}\bm{y}^{(k)T}\right)_{ij}$
(101)
$\displaystyle=\sum_{k=0}^{p}\left(\sum_{l=0}^{p}x^{l}\sum_{i+j=2l}\bm{y}_{i}^{(k)}\bm{y}_{j}^{(k)}\right).$

∎

We recall a few definitions from the main text. For
$\bm{s}\in\mathbb{R}^{\mathbb{N}}$, we define the associated formal series of
Laguerre functions:

$f_{\bm{s}}:=\sum_{k\geq 0}s_{k}\mathcal{L}_{k},$ (102)

where for all $x\in\mathbb{R}_{+}$,
$\mathcal{L}_{k}(x)=(-1)^{k}L_{k}(x)e^{-\frac{x}{2}}$, with
$L_{k}(x)=\sum_{l=0}^{k}\frac{(-1)^{l}}{l!}\binom{k}{l}x^{l}$ the $k^{th}$
Laguerre polynomial. For $m\in\mathbb{N}$, we also define the associated
matrix $A_{\bm{s}}$ by

$(A_{\bm{s}})_{0\leq i,j\leq
m}=\begin{cases}\sum_{k=0}^{l}s_{k}\binom{l}{k}l!&\text{when }i+j=2l,\\\
0&\text{otherwise.}\end{cases}$ (103)

For all $m\in\mathbb{N}$, the set of series of Laguerre functions over
$\mathbb{R}_{+}$ truncated at $m$ is denoted
$\mathcal{R}_{m}(\mathbb{R}_{+})$, and $\mathcal{R}_{m,+}(\mathbb{R}_{+})$
denotes its subset of non-negative elements.

######  Lemma 5.

Let $m\in\mathbb{N}$ and let $\bm{s}\in\mathbb{R}^{\mathbb{N}}$. The following
propositions are equivalent:

  1. (i)

$\forall g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}),\;\braket{f_{\bm{s}},g}\geq 0$,

  2. (ii)

$A_{\bm{s}}\succeq 0$.

###### Proof.

By Lemma 4, any non-negative polynomial over $\mathbb{R}_{+}$ of degree less
or equal to $m$ can be expressed as a sum of polynomials of the form
$\sum_{l=0}^{m}x^{l}\sum_{i+j=2l}y_{i}y_{j}$, where
$Y=(y_{0},\dots,y_{m})\in\mathbb{R}^{m+1}$. Hence, any non-negative truncated
Laguerre series (the elements of $\mathcal{R}_{m,+}(\mathbb{R}_{+})$) can be
expressed as as sum of terms of the form
$e^{-\frac{x}{2}}\sum_{l=0}^{m}x^{l}\sum_{i+j=2l}y_{i}y_{j}$. By linearity, it
is sufficient to check that the scalar products with these expressions are
non-negative.

For all $k\in\mathbb{N}$ we have

$s_{k}=\int_{\mathbb{R}_{+}}\mathcal{L}_{k}(x)f_{\bm{s}}(x)dx.$ (104)

Thus,

$\displaystyle A_{\bm{s}}\succeq 0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{m+1},\;Y^{T}A_{\bm{s}}Y\geq 0$ (105)
$\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{m+1},\;\sum_{i,j=0}^{m}y_{i}y_{j}(A_{\bm{s}})_{ij}\geq 0$
$\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{m+1},\;\sum_{l=0}^{m}\sum_{i+j=2l}^{m}y_{i}y_{j}\sum_{k=0}^{l}s_{k}\binom{l}{k}l!\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{m+1},\;\int_{\mathbb{R}_{+}}\sum_{l=0}^{m}\sum_{i+j=2l}^{m}y_{i}y_{j}\sum_{k=0}^{l}\binom{l}{k}l!\mathcal{L}_{k}(x)f_{\bm{s}}(x)dx\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{m+1},\;\int_{\mathbb{R}_{+}}\sum_{l=0}^{m}\sum_{i+j=2l}^{m}y_{i}y_{j}\sum_{k=0}^{l}(-1)^{k}\binom{l}{k}l!L_{k}(x)e^{-\frac{x}{2}}f_{\bm{s}}(x)dx\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{m+1},\;\int_{\mathbb{R}_{+}}\left(e^{-\frac{x}{2}}\sum_{l=0}^{m}x^{l}\sum_{i+j=2l}^{m}y_{i}y_{j}\right)f_{\bm{s}}(x)dx\geq
0$ $\displaystyle\Leftrightarrow\forall Y\in\mathbb{R}^{m+1},\;\left\langle
f_{\bm{s}},x\mapsto
e^{-\frac{x}{2}}\sum_{l=0}^{m}x^{l}\sum_{i+j=2l}^{m}y_{i}y_{j}\right\rangle\geq
0$ $\displaystyle\Leftrightarrow\forall
g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}),\;\braket{f_{\bm{s}},g}\geq 0,$

where we used Eq. (104) in the fourth line and Eq. (80) in the sixth line. ∎

##  Appendix D Dual semidefinite programs

In this section, we detail the derivation of the dual semidefinite programs
$(\text{D-SDP}^{m,\geq}_{n})$ and $(\text{D-SDP}^{m,\leq}_{n})$. The
generalisations for $(\text{SDP}^{m,\geq}_{\bm{a}})$ and
$(\text{SDP}^{m,\leq}_{\bm{a}})$ are straightforward.

A standard form for a semidefinite program is given by [50]:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{X\in\text{Sym}_{N}}{\text{sup}}\text{Tr}(C^{T}X)\\\
&\text{subject to}&&\forall i\in\llbracket
1,M\rrbracket,\quad\text{Tr}(B^{(i)}X)=b_{i}\\\ &\text{and }&&X\succeq
0,\end{aligned}\right.$ (SDP)

where $M,N\in\mathbb{N}$, $\bm{b}=(b_{1},\dots,b_{M})\in\mathbb{R}^{M}$,
$C\in\text{Sym}_{N}$, and $B^{(i)}\in\text{Sym}_{N}$ for all $i\in\llbracket
1,M\rrbracket$. Its dual semidefinite program reads:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\bm{y}\in\mathbb{R}^{M}}{\text{inf}}\bm{b}^{T}\bm{y}\\\
&\text{subject to}&&\sum_{i=1}^{M}y_{i}B^{(i)}\succeq C.\end{aligned}\right.$
(D-SDP)

###  D.1 Dual program for the semidefinite relaxations

We fix $m\geq n$ and we recall below the expression of
$(\text{SDP}^{m,\geq}_{n})$:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A\in\text{Sym}_{m+1}\\\
\bm{F}\in\mathbb{R}^{m+1}\end{subarray}}{\text{sup}}F_{n}\\\ &\text{subject
to}&&\sum_{k=0}^{m}F_{k}=1\\\ &\text{and}&&\forall k\leq m,\;F_{k}\geq 0\\\
&\text{and}&&\forall l\leq m,\forall i+j=2l,\quad
A_{ij}=\sum_{k=0}^{l}F_{k}\binom{l}{k}l!\\\ &\text{and}&&\forall
l\in\llbracket 1,m\rrbracket,\forall i+j=2l-1,\quad A_{ij}=0\\\
&\text{and}&&A\succeq 0.\end{aligned}\right.$ $(\text{SDP}^{m,\geq}_{n})$

To put $(\text{SDP}^{m,\geq}_{n})$ in the standard form (SDP) we set
$N=2\times(m+1)$ and $M=1+(m+1)^{2}$. For all $r\in\mathbb{N}^{*}$ and all
$i,j\in\llbracket 1,r\rrbracket$, let $E^{(i,j)}_{r}$ be the $r\times r$
matrix whose $(i,j)$ entry is $1$ and all other entries are $0$. We set

$\displaystyle X=\text{Diag}_{k=0,\dots,m}(F_{k})\oplus A\in\text{Sym}_{N},$
(106) $\displaystyle C=E^{(n,n)}_{N}=E^{(n,n)}_{m+1}\oplus\mymathbb
0_{m+1}\in\text{Sym}_{N},$
$\displaystyle\bm{b}=(1,0,0,\dots,0)\in\mathbb{R}^{M},$ $\displaystyle
B^{(0)}=\mymathbb 1_{m+1}\oplus\mymathbb 0_{m+1}\in\text{Sym}_{N},$
$\displaystyle\forall i,j\in\llbracket 0,m\rrbracket,\quad
B^{(i,j)}=\begin{cases}\text{Diag}_{k=0,\dots,m}\left(-\binom{l}{k}l!\right)\oplus\left(\frac{1}{2}E^{(i,j)}_{m+1}+\frac{1}{2}E^{(j,i)}_{m+1}\right)&\text{when
}i+j=2l,\\\ \mymathbb
0_{m+1}\oplus\left(\frac{1}{2}E^{(i,j)}_{m+1}+\frac{1}{2}E^{(j,i)}_{m+1}\right)&\text{otherwise,}\end{cases}$

with the convention $\binom{l}{k}=0$ when $k>l$. The matrix $B^{(0)}$
corresponds to the constraint $\sum_{k=0}^{m}F_{k}=1$, and we denote the
corresponding dual variable $y\in\mathbb{R}$. Similarly, the matrices
$B^{(i,j)}$ correspond to the $(m+1)^{2}$ constraints defining the symmetric
matrix $A$, and we denote the corresponding dual variables
$Q_{ij}\in\mathbb{R}$, with $Q_{ij}=Q_{ji}$ for all $i,j\in\llbracket
0,m\rrbracket$. We write $Q=(Q_{ij})_{0\leq i,j\leq m}$. The standard form
(D-SDP) of the dual program $(\text{D-SDP}^{m,\geq}_{n})$ thus reads:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{m+1}\\\
y\in\mathbb{R}\end{subarray}}{\text{inf}}y\\\ &\text{subject
to}&&\text{Diag}_{k=0,\dots,m}\left[y-\sum_{l=0}^{m}\sum_{i+j=2l}Q_{ij}\binom{l}{k}l!\right]\oplus\frac{1}{2}Q\succeq
E^{(n,n)}_{m+1}\oplus\mymathbb 0_{m+1}.\end{aligned}\right.$
(D-SDP${}_{n}^{m,\geq}$)

Due to the block-diagonal structure of the matrices involved, the positive
semidefinite constraint above is equivalent to the following constraints:

$\left\\{\begin{aligned} &y\geq
1+\sum_{l=0}^{m}\sum_{i+j=2l}Q_{ij}\binom{l}{n}l!,\\\ &\forall k\in\llbracket
0,m\rrbracket\setminus\\{n\\},\quad
y\geq\sum_{l=0}^{m}\sum_{i+j=2l}Q_{ij}\binom{l}{k}l!,\\\ &Q\succeq
0.\end{aligned}\right.$ (107)

For $k\in\llbracket 0,m\rrbracket$, we define

$\mu_{k}:=\sum_{l=0}^{m}\sum_{i+j=2l}Q_{ij}\binom{l}{k}l!\in\mathbb{R}.$ (108)

We obtain the program:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{m+1}\\\
y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{m+1}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{n}\\\ &\text{and}&&\forall k\in\llbracket
0,m\rrbracket\setminus\\{n\\},\quad y\geq\mu_{k}\\\ &\text{and}&&\forall
k\in\llbracket
0,m\rrbracket,\quad\mu_{k}=\sum_{l=0}^{m}\sum_{i+j=2l}Q_{ij}\binom{l}{k}l!\\\
&\text{and}&&Q\succeq 0.\end{aligned}\right.$ (D-SDP${}_{n}^{m,\geq}$)

Finally, in order to obtain the form of $(\text{D-SDP}^{m,\geq}_{n})$ from the
main text we prove the following result:

######  Lemma 9.

Let $\bm{u},\bm{v}\in\mathbb{R}^{m+1}$. The following propositions are
equivalent:

  1. (i)

$\forall k\in\llbracket 0,m\rrbracket,\quad
u_{k}=\sum_{l=0}^{m}v_{l}\binom{l}{k}l!$,

  2. (ii)

$\forall l\in\llbracket 0,m\rrbracket,\quad
v_{l}=\sum_{k=l}^{m}\frac{(-1)^{l+k}}{l!}\binom{k}{l}u_{k}$.

###### Proof.

The proof is similar to that of Lemma 8. Note that we could start the first
sum at $l=k$ since $\binom{l}{k}=0$ for $l<k$ but for convenience we start it
at $l=0$.

(i)$\Rightarrow$(ii): suppose that

$\forall k\in\llbracket 0,m\rrbracket,\quad
u_{k}=\sum_{p=0}^{m}v_{l}\binom{p}{k}p!.$ (109)

Then, for all $l\in\llbracket 0,m\rrbracket$,

$\displaystyle\frac{(-1)^{l}}{l!}\sum_{k=l}^{m}(-1)^{k}\binom{k}{l}u_{k}$
$\displaystyle=\frac{(-1)^{l}}{l!}\sum_{k=l}^{m}(-1)^{k}\binom{k}{l}\sum_{p=0}^{m}v_{p}\binom{p}{k}p!$
(110)
$\displaystyle=\sum_{p=0}^{m}v_{p}\frac{p!}{l!}\sum_{k=l}^{m}(-1)^{k+l}\binom{p}{k}\binom{k}{l}$
$\displaystyle=\sum_{p=l}^{m}v_{p}\frac{p!}{l!}\sum_{k=l}^{p}(-1)^{k+l}\binom{p}{k}\binom{k}{l}$
$\displaystyle=\sum_{p=l}^{m}v_{p}\frac{p!}{l!}\sum_{k=l}^{p}(-1)^{k+l}\frac{p!k!}{k!(p-k)!l!(k-l)!}$
$\displaystyle=\sum_{p=l}^{m}v_{p}\frac{p!}{l!}\binom{p}{l}\sum_{q=0}^{p-l}(-1)^{q}\binom{p-l}{q}$
$\displaystyle=v_{l},$

where we used Eq. (109) in the first line, the fact that $\binom{p}{k}=0$ if
$k>p$ in the third line, $q:=k-l$ in the fifth line, and the binomial theorem
in the last line which imposes $p=l$.

(ii)$\Rightarrow$(i): suppose that

$\forall l\in\llbracket 0,m\rrbracket,\quad
v_{l}=\frac{(-1)^{l}}{l!}\sum_{p=l}^{m}(-1)^{p}\binom{p}{l}u_{p}.$ (111)

Then, for all $k\in\llbracket 0,m\rrbracket$,

$\displaystyle\sum_{l=0}^{m}v_{l}\binom{l}{k}l!$
$\displaystyle=\sum_{l=0}^{m}\frac{(-1)^{l}}{l!}\sum_{p=l}^{m}(-1)^{p}\binom{p}{l}u_{p}\binom{l}{k}l!$
(112)
$\displaystyle=\sum_{p=0}^{m}u_{p}(-1)^{p}\sum_{l=0}^{p}(-1)^{l}\binom{p}{l}\binom{l}{k}$
$\displaystyle=\sum_{p=k}^{m}u_{p}(-1)^{p}\sum_{l=k}^{p}(-1)^{l}\binom{p}{l}\binom{l}{k}$
$\displaystyle=\sum_{p=k}^{m}u_{p}(-1)^{p}\sum_{l=k}^{p}(-1)^{l}\frac{p!l!}{l!(p-l)!k!(l-k)!}$
$\displaystyle=\sum_{p=k}^{m}u_{p}(-1)^{p-k}\binom{p}{k}\sum_{q=0}^{p-k}(-1)^{q}\binom{p-k}{q}$
$\displaystyle=u_{k},$

where we used Eq. (111) in the first line, the fact that $\binom{l}{k}=0$ if
$k>l$ in the third line, $q:=l-k$ in the fifth line, and the binomial theorem
in the last line which imposes $p=k$.

∎

Combining Lemma 9 for $u_{k}=\mu_{k}$ and $v_{l}=\sum_{i+j=2l}Q_{ij}$ for all
$k,l\in\llbracket 0,m\rrbracket$ with the previous expression of
(D-SDP${}_{n}^{m,\geq}$) we finally obtain:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{m+1}\\\
y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{m+1}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{n}\\\ &\text{and}&&\forall k\in\llbracket
0,m\rrbracket\setminus\\{n\\},\quad y\geq\mu_{k}\\\ &\text{and}&&\forall
l\in\llbracket
0,m\rrbracket,\quad\sum_{i+j=2l}Q_{ij}=\frac{(-1)^{l}}{l!}\sum_{k=l}^{m}(-1)^{k}\binom{k}{l}\mu_{k}\\\
&\text{and}&&Q\succeq 0.\end{aligned}\right.$ (D-SDP${}_{n}^{m,\geq}$)

Note that the constraint $y\geq 1+\mu_{n}$ implies the constraint
$y\geq\mu_{n}$.

###  D.2 Dual program for the semidefinite restrictions

The derivation is analogous to that of the previous section. We fix $m\geq n$
and we recall below the expression of $(\text{SDP}^{m,\leq}_{n})$:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{m+1}\\\
\bm{F}\in\mathbb{R}^{m+1}\end{subarray}}{\text{sup}}F_{n}\\\ &\text{subject
to}&&\sum_{k=0}^{m}F_{k}=1\\\ &\text{and}&&\forall k\leq m,\;F_{k}\geq 0\\\
&\text{and}&&\forall l\in\llbracket
1,m\rrbracket,\quad\sum_{i+j=2l-1}Q_{ij}=0\\\ &\text{and}&&\forall l\leq
m,\sum_{i+j=2l}Q_{ij}=\frac{(-1)^{l}}{l!}\sum_{k=l}^{m}(-1)^{k}\binom{k}{l}F_{k}\\\
&\text{and}&&Q\succeq 0.\end{aligned}\right.$ $(\text{SDP}^{m,\leq}_{n})$

To put $(\text{SDP}^{m,\leq}_{n})$ in the standard form (SDP) we set
$N=2\times(m+1)$ and $M=1+m+(m+1)$. For all $r\in\mathbb{N}^{*}$ and all
$i,j\in\llbracket 1,r\rrbracket$, recall that $E^{(i,j)}_{r}$ denotes the
$r\times r$ matrix whose $(i,j)$ entry is $1$ and all other entries are $0$.
We set

$\displaystyle X=\text{Diag}_{k=0,\dots,m}(F_{k})\oplus Q\in\text{Sym}_{N},$
(113) $\displaystyle C=E^{(n,n)}_{N}=E^{(n,n)}_{m+1}\oplus\mymathbb
0_{m+1}\in\text{Sym}_{N},$
$\displaystyle\bm{b}=(1,0,0,\dots,0)\in\mathbb{R}^{M},$
$\displaystyle{B^{\prime}}^{(0)}=\mymathbb 1_{m+1}\oplus\mymathbb
0_{m+1}\in\text{Sym}_{N},$ $\displaystyle\forall l\in\llbracket
1,m\rrbracket,\quad{B^{\prime}}^{(l)}=\mymathbb
0_{m+1}\oplus\left(\sum_{i+j=2l-1}E^{(i,j)}_{m+1}\right),$
$\displaystyle\forall l\in\llbracket 0,m\rrbracket,\quad
B^{(l)}=\text{Diag}_{k=0,\dots,m}\left(-\frac{(-1)^{k+l}}{l!}\binom{k}{l}\right)\oplus\left(\sum_{i+j=2l}E^{(i,j)}_{m+1}\right),$

with the convention $\binom{k}{l}=0$ when $l>k$. The matrix
${B^{\prime}}^{(0)}$ corresponds to the constraint $\sum_{k=0}^{m}F_{k}=1$ and
we denote the corresponding dual variable $y\in\mathbb{R}$. Similarly, the
matrices ${B^{\prime}}^{(l)}$ correspond to the $m$ constraints
$\sum_{i+j=2l-1}Q_{ij}=0$, and we denote the corresponding dual variables
$\nu_{l}^{\prime}\in\mathbb{R}$. Finally, the matrices $B^{(l)}$ correspond to
the $m+1$ constraints
$\sum_{i+j=2l}Q_{ij}=\frac{(-1)^{l}}{l!}\sum_{k=l}^{m}(-1)^{k}\binom{k}{l}F_{k}$,
and we denote the corresponding dual variables $\nu_{l}\in\mathbb{R}$.

The standard form (D-SDP) of the dual program $(\text{D-SDP}^{m,\leq}_{n})$
thus reads:

$\displaystyle\hskip 91.04872pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}\bm{\nu},\bm{\nu}^{\prime}\in\mathbb{R}^{m+1}\times\mathbb{R}^{m}\\\
y\in\mathbb{R}\end{subarray}}{\text{inf}}y\\\ &\text{subject
to}&&\text{Diag}_{k=0,\dots,m}\left[y-\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}\right]\\\
&&&\quad\oplus\left(\sum_{l=0}^{m}\sum_{i+j=2l}\nu_{l}E^{(i,j)}_{m+1}+\sum_{l=1}^{m}\sum_{i+j=2l-1}\nu_{l}^{\prime}E^{(i,j)}_{m+1}\right)\succeq
E^{(n,n)}_{m+1}\oplus\mymathbb 0_{m+1}.\end{aligned}\right.$
(D-SDP${}_{n}^{m,\leq}$)

Due to the block-diagonal structure of the matrices involved, the positive
semidefinite constraint above is equivalent to the following constraints:

$\left\\{\begin{aligned} &y\geq
1+\sum_{l=0}^{n}\nu_{l}\frac{(-1)^{n+l}}{l!}\binom{n}{l},\\\ &\forall
k\in\llbracket 0,m\rrbracket\setminus\\{n\\},\quad
y\geq\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l},\\\
&\left(\sum_{l=0}^{m}\sum_{i+j=2l}\nu_{l}E^{(i,j)}_{m+1}+\sum_{l=1}^{m}\sum_{i+j=2l-1}\nu_{l}^{\prime}E^{(i,j)}_{m+1}\right)\succeq
0.\end{aligned}\right.$ (114)

Let us define $A=(A_{ij})_{0\leq i,j\leq m}$ by

$A:=\sum_{l=0}^{m}\sum_{i+j=2l}\nu_{l}E^{(i,j)}_{m+1}+\sum_{l=1}^{m}\sum_{i+j=2l-1}\nu_{l}^{\prime}E^{(i,j)}_{m+1},$
(115)

or equivalently

$A_{ij}=\begin{cases}\nu_{l}&\text{when }i+j=2l,\\\
\nu_{l}^{\prime}&\text{when }i+j=2l-1,\end{cases}$ (116)

for all $i,j\in\llbracket 0,m\rrbracket$. For $k\in\llbracket 0,m\rrbracket$,
we also define

$\mu_{k}:=\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}\in\mathbb{R}.$
(117)

By Lemma 8, the following conditions are equivalent:

  1. (i)

$\forall k\in\llbracket
0,m\rrbracket,\quad\mu_{k}=\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}$,

  2. (ii)

$\forall l\in\llbracket
0,m\rrbracket,\quad\nu_{l}=\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!$.

With Eq. (116) we thus have

$A_{ij}=\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!\quad\text{when }i+j=2l,$ (118)

and we obtain the following expression for $(\text{D-SDP}^{m,\leq}_{n})$:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A\in\text{Sym}_{m+1}\\\
y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{m+1}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{n}\\\ &\text{and}&&\forall k\in\llbracket
0,m\rrbracket\setminus\\{n\\},\quad y\geq\mu_{k}\\\ &\text{and}&&\forall l\leq
m,\forall i+j=2l,\quad A_{ij}=\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!\\\
&\text{and}&&A\succeq 0.\end{aligned}\right.$ (D-SDP${}_{n}^{m,\leq}$)

Note that the constraint $y\geq 1+\mu_{n}$ implies the constraint
$y\geq\mu_{n}$.

##  Appendix E Proof of Lemma 6

In this section, we prove the following result:

######  Lemma 6.

For all $m\geq n$, the program $(\text{D-SDP}^{m,\leq}_{n})$ is equivalent to
the following program:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}y\in\mathbb{R}\\\
\bm{\mu}\in\mathcal{S}^{\prime}(\mathbb{N})\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{n}\\\ &\text{and}&&\forall k\neq
n\in\mathbb{N},\;y\geq\mu_{k}\\\ &\text{and}&&\forall
g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}),\;\langle f_{\bm{\mu}},g\rangle\geq
0,\end{aligned}\right.$ (D-SDP${}_{n}^{m,\leq}$)

where $f_{\bm{\mu}}=\sum_{k}\mu_{k}\mathcal{L}_{k}$.

###### Proof.

We first obtain a reformulation of $(\text{SDP}^{m,\leq}_{n})$ and we derive
its dual program. This reformulation is obtained using Stieltjes
characterisation of non-negative polynomials over $\mathbb{R}_{+}$ rather than
Lemma 4:

######  Lemma 10 ([65]).

Let $m\in\mathbb{N}$ and let $P$ be a univariate polynomial of degree $m$. Let
$a_{1}=\left\lfloor\frac{m}{2}\right\rfloor$ and
$a_{2}=\left\lfloor\frac{m-1}{2}\right\rfloor$. For all $q\in\mathbb{N}$, let
$X_{q}=(1,x,\dots,x^{q})$ be the vector of univariate monomials up to degree
$q$. Then, $P$ is non-negative over $\mathbb{R}_{+}$ if and only if there
exist sum of squares polynomials $A_{1}$ and $A_{2}$ of degree $2a_{1}$ and
$2a_{2}$, respectively, such that $P(x)=A_{1}(x)+xA_{2}(x)$ for all
$x\in\mathbb{R}_{+}$ , or equivalently, if and only if there exist real
positive semidefinite matrices $A_{1}$ and $A_{2}$ of size
$(a_{1}+1)\times(a_{1}+1)$ and $(a_{2}+1)\times(a_{2}+1)$, respectively, such
that for all $x\in\mathbb{R}_{+}$,

$P(x)=X_{a_{1}}^{T}A_{1}X_{a_{1}}+xX^{T}_{a_{2}}A_{2}X_{a_{2}}.$ (119)

By Lemma 10, the program $(\text{SDP}^{m,\leq}_{n})$, obtained by imposing
$F_{k}=0$ for $k>m$ in (LP${}_{n}^{L^{2}}$), is equivalent to the following
program:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A_{1},A_{2}\in\text{Sym}_{a_{1}+1}\times\text{Sym}_{a_{2}+1}\\\
\bm{F}\in\mathbb{R}^{m+1}\end{subarray}}{\text{sup}}F_{n}\\\ &\text{subject
to}&&\sum_{k=0}^{m}F_{k}=1\\\ &\text{and}&&\forall k\leq m,\;F_{k}\geq 0\\\
&\text{and}&&\forall l\leq
m,\frac{(-1)^{l}}{l!}\sum_{k=l}^{m}(-1)^{k}\binom{k}{l}F_{k}=\sum_{\begin{subarray}{c}i+j=l\\\
0\leq i,j\leq
a_{1}\end{subarray}}(A_{1})_{ij}+\sum_{\begin{subarray}{c}i+j=l-1\\\ 0\leq
i,j\leq a_{2}\end{subarray}}(A_{2})_{ij}\\\ &\text{and}&&A_{1}\succeq 0\\\
&\text{and}&&A_{2}\succeq 0.\end{aligned}\right.$ $(\text{SDP}^{m,\leq}_{n})$

To put $(\text{SDP}^{m,\leq}_{n})$ in the standard form (SDP) we set
$N=(m+1)+(a_{1}+1)+(a_{2}+1)$ and $M=1+(m+1)$. For all $r\in\mathbb{N}^{*}$
and all $i,j\in\llbracket 1,r\rrbracket$, recall that $E^{(i,j)}_{r}$ denotes
the $r\times r$ matrix whose $(i,j)$ entry is $1$ and all other entries are
$0$. We set

$\displaystyle X=\text{Diag}_{k=0,\dots,m}(F_{k})\oplus A_{1}\oplus
A_{2}\in\text{Sym}_{N},$ (120) $\displaystyle
C=E^{(n,n)}_{N}=E^{(n,n)}_{m+1}\oplus\mymathbb 0_{a_{1}+1}\oplus\mymathbb
0_{a_{2}+1}\in\text{Sym}_{N},$
$\displaystyle\bm{b}=(1,0,0,\dots,0)\in\mathbb{R}^{M},$
$\displaystyle{B}^{(-1)}=\mymathbb 1_{m+1}\oplus\mymathbb
0_{a_{1}+1}\oplus\mymathbb 0_{a_{2}+1}\in\text{Sym}_{N},$
$\displaystyle\forall l\in\llbracket 0,m\rrbracket,\quad
B^{(l)}=\text{Diag}_{k=0,\dots,m}\left(-\frac{(-1)^{k+l}}{l!}\binom{k}{l}\right)\oplus\left(\sum_{\begin{subarray}{c}i+j=l\\\
0\leq i,j\leq
a_{1}\end{subarray}}E^{(i,j)}_{a_{1}+1}\right)\oplus\left(\sum_{\begin{subarray}{c}i+j=l-1\\\
0\leq i,j\leq a_{2}\end{subarray}}E^{(i,j)}_{a_{2}+1}\right),$

with the convention $\binom{k}{l}=0$ when $l>k$. The matrix ${B}^{(-1)}$
corresponds to the constraint $\sum_{k=0}^{m}F_{k}=1$ and we denote the
corresponding dual variable $y\in\mathbb{R}$. Similarly, the matrices
$B^{(l)}$ correspond to the $m+1$ other linear constraints, and we denote the
corresponding dual variable $\bm{\nu}\in\mathbb{R}^{m+1}$. The standard form
(D-SDP) of the dual program $(\text{D-SDP}^{m,\leq}_{n})$ thus reads:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}\bm{\nu}\in\mathbb{R}^{m+1}\\\
y\in\mathbb{R}\end{subarray}}{\text{inf}}y\\\ &\text{subject
to}&&\text{Diag}_{k=0,\dots,m}\left[y-\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}\right]\\\
&&&\quad\oplus\left(\sum_{l=0}^{m}\sum_{\begin{subarray}{c}i+j=l\\\ 0\leq
i,j\leq a_{1}\end{subarray}}\nu_{l}E^{(i,j)}_{a_{1}+1}\\!\right)\\\
&&&\quad\oplus\left(\sum_{l=1}^{m}\sum_{\begin{subarray}{c}i+j=l-1\\\ 0\leq
i,j\leq a_{2}\end{subarray}}\nu_{l}E^{(i,j)}_{a_{2}+1}\\!\right)\succeq
E^{(n,n)}_{m+1}\oplus\mymathbb 0_{a_{1}}\oplus\mymathbb
0_{a_{2}}.\end{aligned}\right.$ (D-SDP${}_{n}^{m,\leq}$)

Due to the block-diagonal structure of the matrices involved, the positive
semidefinite constraint above is equivalent to the following constraints:

$\left\\{\begin{aligned} &y\geq
1+\sum_{l=0}^{n}\nu_{l}\frac{(-1)^{n+l}}{l!}\binom{n}{l},\\\ &\forall
k\in\llbracket 0,m\rrbracket\setminus\\{n\\},\quad
y\geq\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l},\\\
&\sum_{l=0}^{m}\sum_{\begin{subarray}{c}i+j=l\\\ 0\leq i,j\leq
a_{1}\end{subarray}}\nu_{l}E^{(i,j)}_{a_{1}+1}\succeq 0\\\
&\sum_{l=1}^{m}\sum_{\begin{subarray}{c}i+j=l-1\\\ 0\leq i,j\leq
a_{2}\end{subarray}}\nu_{l}E^{(i,j)}_{a_{2}+1}\succeq 0.\end{aligned}\right.$
(121)

For $k\in\llbracket 0,m\rrbracket$, we define

$\mu_{k}:=\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}\in\mathbb{R}.$
(122)

By Lemma 8, the following conditions are equivalent:

  1. (i)

$\forall k\in\llbracket
0,m\rrbracket,\quad\mu_{k}=\sum_{l=0}^{k}\nu_{l}\frac{(-1)^{k+l}}{l!}\binom{k}{l}$,

  2. (ii)

$\forall l\in\llbracket
0,m\rrbracket,\quad\nu_{l}=\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!$.

We thus have

$\forall l\in\llbracket
0,m\rrbracket,\quad\nu_{l}=\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!$ (123)

Let us introduce the moment matrices $M_{\nu}\in\text{Sym}_{a_{1}+1}$ and
$M^{(1)}_{\nu}\in\text{Sym}_{a_{2}+1}$:

$\displaystyle\forall i,j\in\llbracket 0,a_{1}\rrbracket,\;$
$\displaystyle(M_{\nu})_{i,j}:=\nu_{i+j},$ (124) $\displaystyle\forall
i,j\in\llbracket 0,a_{2}\rrbracket,\;$
$\displaystyle(M_{\nu}^{(1)})_{ij}:=\nu_{i+j+1}.$ (125)

The constraints (121) are equivalent to:

$\left\\{\begin{aligned} &y\geq 1+\mu_{n},\\\ &\forall k\in\llbracket
0,m\rrbracket\setminus\\{n\\},\quad y\geq\mu_{l},\\\ &M_{\nu}\succeq 0\\\
&M_{\nu}^{(1)}\succeq 0.\end{aligned}\right.$ (126)

We complete the vector $\bm{\mu}$ with zeros to obtain an element of
$\mathcal{S}^{\prime}(\mathbb{N})$. We have
$f_{\bm{\mu}}=\sum_{k}\mu_{k}\mathcal{L}_{k}\in\mathcal{S}^{\prime}(\mathbb{R}_{+})$.
We prove the following result, analogous to Lemma 5:

######  Lemma 11.

The following propositions are equivalent:

  1. (i)

$\forall g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}),\;\braket{f_{\bm{\mu}},g}\geq
0$,

  2. (ii)

$M_{\nu}\succeq 0$ and $M_{\nu}^{(1)}\succeq 0$.

###### Proof.

The proof is similar to that of Lemma 5: for all $k\in\mathbb{N}$ we have

$\mu_{k}=\int_{\mathbb{R}_{+}}\mathcal{L}_{k}(x)f_{\bm{\mu}}(x)dx.$ (127)

Thus,

$\displaystyle M_{\nu}\succeq 0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;Y^{T}M_{\nu}Y\geq 0$ (128)
$\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;\sum_{i,j=0}^{a_{1}}y_{i}y_{j}(M_{\nu})_{ij}\geq 0$
$\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;\sum_{l=0}^{2a_{1}}\sum_{i+j=l}y_{i}y_{j}\nu_{l}\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;\sum_{l=0}^{2a_{1}}\sum_{i+j=l}y_{i}y_{j}\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;\int_{\mathbb{R}_{+}}\sum_{l=0}^{2a_{1}}\sum_{i+j=l}y_{i}y_{j}\sum_{k=0}^{l}\binom{l}{k}l!\mathcal{L}_{k}(x)f_{\bm{\mu}}(x)dx\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;\int_{\mathbb{R}_{+}}\sum_{l=0}^{2a_{1}}\sum_{i+j=l}y_{i}y_{j}\sum_{k=0}^{l}(-1)^{k}\binom{l}{k}l!L_{k}(x)e^{-\frac{x}{2}}f_{\bm{\mu}}(x)dx\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;\int_{\mathbb{R}_{+}}e^{-\frac{x}{2}}\sum_{l=0}^{2a_{1}}x^{l}\sum_{i+j=l}y_{i}y_{j}f_{\bm{\mu}}(x)dx\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;\int_{\mathbb{R}_{+}}e^{-\frac{x}{2}}\left(\sum_{k=0}^{a_{1}}y_{k}x^{k}\right)^{2}f_{\bm{\mu}}(x)dx\geq
0$ $\displaystyle\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{1}+1},\;\left\langle f_{\bm{\mu}},x\mapsto
e^{-\frac{x}{2}}\left(\sum_{k=0}^{a_{1}}y_{k}x^{k}\right)^{2}\right\rangle\geq
0,$

where we used Eq. (124) in the third line, Eq. (123) in the fourth line, Eq.
(127) in the fifth line and Eq. (80) in the seventh line. Similarly,

$M_{\nu}^{(1)}\succeq 0\Leftrightarrow\forall
Y\in\mathbb{R}^{a_{2}+1},\;\left\langle f_{\bm{\mu}},x\mapsto
e^{-\frac{x}{2}}x\left(\sum_{k=0}^{a_{2}}y_{k}x^{k}\right)^{2}\right\rangle\geq
0.$ (129)

Combining Eq. (128) and Eq. (129) with Lemma 10 we obtain

$M_{\nu}\succeq 0\text{ and }M_{\nu}^{(1)}\succeq 0\Leftrightarrow\forall
g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}),\;\braket{f_{\bm{\mu}},g}\geq 0,$ (130)

by linearity.

∎

Combining Lemma 11 with the constraints (126) finally yields:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}y\in\mathbb{R}\\\
\bm{\mu}\in\mathcal{S}^{\prime}(\mathbb{N})\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&\forall k\neq n\in\mathbb{N},\;y\geq\mu_{k}\\\
&\text{and}&&y\geq 1+\mu_{n}\\\ &\text{and}&&\forall
g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}),\;\langle f_{\bm{\mu}},g\rangle\geq
0.\end{aligned}\right.$ (D-SDP${}_{n}^{m,\leq}$)

∎

##  Appendix F Proof of Lemma 7

We recall the definition of
$\bm{F}^{n}=(F_{k}^{n})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$:

  * •

if $n$ is even:

$\displaystyle F_{k}^{n}:=$
$\displaystyle\begin{cases}\frac{1}{2^{n}}\binom{k}{\frac{k}{2}}\binom{n-k}{\frac{n-k}{2}}&\text{when
}k\leq n,k\text{ even},\\\ 0&\text{otherwise},\end{cases}$ (131)
$\displaystyle F_{k}^{n}:=$
$\displaystyle\begin{cases}\frac{1}{2^{n}}\frac{\binom{n}{\lfloor\frac{n}{2}\rfloor}\binom{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{k}{2}\rfloor}^{2}}{\binom{n}{k}},&\text{when
}k\leq n,\\\ 0&\text{otherwise}.\end{cases}$ (132)

In both cases,

$F_{n}^{n}=\frac{1}{2^{n}}\binom{n}{\lfloor\frac{n}{2}\rfloor}.$ (133)

We extrapolated these analytical expressions from numerical values. Running
$(\text{SDP}^{m,\leq}_{n})$ for several values of $n$ and $m$ allowed us to
deduce these sequences (we acknowledge here the great help from oeis.org).

We start by showing two results, corresponding to $n$ even and $n$ odd,
respectively, where we make use of Zeilberger’s algorithm, a powerful
algorithm for proving binomial identities [70]. Given a holonomic function,
this algorithm outputs a recurrence relation that it satisfies, thus reducing
the proof of identity between binomial expressions to the verification that
the initialisation is correct. A Mathematica notebook is available for the
implementation of Zeilberger’s algorithm [53].

######  Lemma 12.

For $n\in\mathbb{N}$ even:

$\sum_{k=0}^{n}(-1)^{k}F_{k}^{n}L_{k}(x)=\sum_{l=0}^{n}x^{l}\sum_{i+j=2n-2l}p_{n-i}p_{n-j},$
(134)

where:

$\displaystyle p_{n-k}:=$
$\displaystyle\begin{cases}\sqrt{\frac{1}{2^{n}n!}\binom{n}{\frac{n}{2}}},&\text{when
}k=0,\\\
(-1)^{\frac{k}{2}}2^{\frac{k}{2}}(\frac{k}{2})!\binom{\frac{n}{2}}{\frac{k}{2}}^{2}p_{n},&\text{when
}0<k\leq n,\;k\text{ even },\\\ 0,&\text{otherwise}.\end{cases}$ (135)

The coefficients $p_{n-k}$ (and $q_{n-k}$ later on) were found by hand when
looking for an analytical sum of squares decomposition.

###### Proof.

To prove the polynomial equality (134), we start by equating the coefficients
in $x^{l}$ for $l\in\llbracket 0,n\rrbracket$ which gives:

$\displaystyle\frac{(-1)^{l}}{l!}\sum_{k=l}^{n}(-1)^{k}\binom{k}{l}F_{k}^{n}$
$\displaystyle=\sum_{i+j=2n-2l}p_{n-i}p_{n-j}$ (136)
$\displaystyle=\sum_{i=0}^{2n-2l}p_{n-i}p_{n-(2n-2l-i)}$
$\displaystyle=\sum_{i=0}^{n-l}p_{n-2i}p_{n-(2n-2l-2i)},$

where we used $p_{n-i}=0$ for $n-i<0$ in the second line. These are equalities
between holonomic functions of parameters $n$ and $l$ that are trivial for
$l>n$.

  * •

For $l\leq n$ even, because $F^{n}_{k}=0$ for $k$ odd, Eq. (136) becomes:

$\sum_{k=\frac{l}{2}}^{\frac{n}{2}}\frac{1}{l!}\binom{2k}{l}F_{2k}^{n}=\sum_{i=0}^{n-l}p_{n-2i}p_{n-(2n-2l-2i)},$
(137)

that is, taking into account the parity of $l=2s$ and $n=2t$,

$\sum_{k=s}^{t}\frac{1}{(2s)!}\binom{2k}{2s}F_{2k}^{2t}=\sum_{i=0}^{2t-2s}p_{2t-2i}p_{2t-(4t-4s-2i)}.$
(138)

Inserting the expressions from Eq. (131) and Eq. (135), we thus have to check
the identity:

$\sum_{k=s}^{t}\frac{1}{2^{2t}(2s)!}\binom{2k}{2s}\binom{2k}{k}\binom{2t-2k}{t-k}=\sum_{i=0}^{2t-2s}\frac{i!(2t-2s-i)!}{2^{2s}(2t)!}\binom{2t}{t}\binom{t}{i}^{2}\binom{t}{2t-2s-i}^{2},$
(139)

for all $t\in\mathbb{N}$ and all $s\leq t$ (with the convention
$\binom{k}{j}=0$ for $j>k$). We ran Zeilberger’s algorithm to show that the
right-hand side and the left-hand side of Eq. (138) both satisfy the following
recurrence relation, for all $s,t\in\mathbb{N}$:

$2(t+1)^{2}S(s,t)+(-2s^{2}-4t^{2}+4st+5s-11t-8)S(s,t+1)+(s-t-2)(2s-2t-3)S(s,t+2)=0.$
(140)

It remains to check that the initialisation is correct. For all
$s\in\mathbb{N}$, this recurrence relation in $t$ is of order $2$. Since the
identities in Eq. (139) are trivial when $l>n$, i.e., $s>t$, we thus only need
to check Eq. (139) for $(s,t)=(0,0)$, $(s,t)=(0,1)$, and $(s,t)=(1,1)$, which
is straightforward: we obtain the values $1$, $1$ and $\frac{1}{4}$
respectively, for both sides of Eq. (139).

  * •

For $l\leq n$ odd, Eq. (136) becomes:

$-\sum_{k=\frac{l+1}{2}}^{\frac{n}{2}}\frac{1}{l!}\binom{2k}{l}F_{2k}^{n}=\sum_{i=0}^{n-l}p_{n-2i}p_{n-(2n-2l-2i)},$
(141)

that is, taking into account the parity of $l=2s+1$ and $n=2t$:

$-\sum_{k=s+1}^{t}\frac{1}{(2s+1)!}\binom{2k}{2s+1}F_{2k}^{2t}=\sum_{i=0}^{2t-2s-1}p_{2t-2i}p_{2t-(4t-4s-2i-2)}.$
(142)

Inserting the expressions from Eq. (131) and Eq. (135), we thus have to check
the identity:

$\displaystyle\sum_{k=s+1}^{t}\frac{1}{2^{2t}(2s+1)!}$
$\displaystyle\binom{2k}{2s+1}\binom{2k}{k}\binom{2t-2k}{t-k}$ (143)
$\displaystyle=\sum_{i=0}^{2t-2s-1}\frac{i!(2t-2s-i-1)!}{2^{2s+1}(2t)!}\binom{2t}{t}\binom{t}{i}^{2}\binom{t}{2t-2s-i-1}^{2},$

for all $t\in\mathbb{N}$ and all $s\leq t$ (with the convention
$\binom{k}{j}=0$ for $j>k$). Likewise, we ran Zeilberger’s algorithm to show
that the right-hand side and the left-hand side of Eq. (142) both satisfy the
following recurrence relation, for all $s,t\in\mathbb{N}$:

$2(t+1)^{2}S(s,t)+(-2s^{2}-4t^{2}+4st+3s-9t-6)S(s,t+1)+(s-t-1)(2s-2t-3)S(s,t+2)=0.$
(144)

It remains to check that the initialisation is correct. For all
$s\in\mathbb{N}$, this recurrence relation in $t$ is of order $2$. Since the
identities in Eq. (143) are trivial when $l>n$, i.e., $s\geq t$, we thus only
need to check Eq. (143) for $(s,t)=(0,1)$, which is straightforward: we obtain
the value $1$ for both sides of Eq. (143).

∎

######  Lemma 13.

For $n\in\mathbb{N}$ odd:

$\sum_{k=0}^{n}(-1)^{k}F_{k}^{n}L_{k}(x)=\sum_{l=0}^{n}x^{l}\sum_{i+j=2l}q_{i}q_{j}$
(145)

where:

$\displaystyle q_{n-k}:=$
$\displaystyle\begin{cases}\sqrt{\frac{1}{2^{n}n!}\binom{n}{\lfloor\frac{n}{2}\rfloor}},&\text{when
}k=0,\\\
(-1)^{\frac{k}{2}}2^{\frac{k}{2}}(\frac{k}{2})!\frac{n+1}{n-k+1}\binom{\lfloor\frac{n}{2}\rfloor}{\frac{k}{2}}^{2}q_{n},&\text{when
}0<k<n,\;k\text{ even},\\\ 0.&\text{otherwise}.\end{cases}$ (146)

###### Proof.

Unlike the case where $n$ is even, $\bm{F}^{n}$ is non-zero for $k\leq n$ odd,
and the expression of $F^{n}_{k}$ depends on the parity of $k$. Thus we cannot
use directly Eq. (132) in Zeilberger’s algorithm as we did in the previous
lemma, hence the development below in order to obtain expressions that the
algorithm can take as inputs. We fix $n$ odd and $l\leq n$.

We start by equating coefficents in $x^{l}$ in Eq. (145):

$\displaystyle\frac{(-1)^{l}}{l!}\sum_{k=l}^{n}(-1)^{k}\binom{k}{l}F_{k}^{n}$
$\displaystyle=\sum_{i+j=2n-2l}q_{n-i}q_{n-j}$ (147)
$\displaystyle=\sum_{i=0}^{n-l}q_{n-2i}q_{n-(2n-2l-2i)}.$

  * •

For $l$ even, writing $l=2s$ and $n=2t+1$, the left-hand side of Eq. (147)
becomes:

$\displaystyle\frac{1}{(2s)!}\sum_{k=2s}^{2t+1}$
$\displaystyle(-1)^{k}\binom{k}{2s}F_{k}^{2t+1}$ (148)
$\displaystyle=\frac{1}{(2s)!}\sum_{k=0}^{2t+1-2s}(-1)^{k}\binom{k+2s}{2s}F_{k+2s}^{2t+1}$
$\displaystyle=\frac{1}{(2s)!}\sum_{k=0}^{t-s}\left(\binom{2k+2s}{2s}F_{2k+2s}^{2t+1}-\binom{2k+2s+1}{2s}F_{2k+2s+1}^{2t+1}\right)$
$\displaystyle=\frac{\binom{2t+1}{t}}{2^{2t+1}(2s)!}\sum_{k=0}^{t-s}\left(\frac{\binom{2k+2s}{2s}\binom{t}{k+s}^{2}}{\binom{2t+1}{2k+2s}}-\frac{\binom{2k+2s+1}{2s}\binom{t}{k+s}^{2}}{\binom{2t+1}{2k+2s+1}}\right)$
$\displaystyle=q_{2t+1}^{2}\frac{(2t+1)!}{(2s)!}\sum_{k=0}^{t-s}\frac{\binom{t}{k+s}^{2}\binom{2k+2s}{2s}}{\binom{2t+1}{2k+2s}}\left(1-\frac{(2k+2s+1)^{2}}{(2k+1)(2t-2s-2k+1)}\right).$

With Eq. (146) and Eq. (147), we thus have to check the identity:

$\displaystyle\frac{(2t+1)!}{(2s)!}$
$\displaystyle\sum_{k=0}^{t-s}\frac{\binom{t}{k+s}^{2}\binom{2k+2s}{2s}}{\binom{2t+1}{2k+2s}}\left(1-\frac{(2k+2s+1)^{2}}{(2k+1)(2t-2s-2k+1)}\right)$
(149)
$\displaystyle=\sum_{i=0}^{2t+1-2s}\frac{q_{2t+1-2i}q_{2t+1-(4t+2-4s-2i)}}{q_{2t+1}^{2}}$
$\displaystyle=-\sum_{i=0}^{2t+1-2s}2^{2t-2s+1}\frac{(2t+2)^{2}i!(2t+1-2s-i)!}{(2t-2i+2)(4s+2i-2t)}\binom{t}{i}^{2}\binom{t}{2t-2s-i+1}^{2},$

for all $t\in\mathbb{N}$ and all $s\leq t$ (with the convention
$\binom{k}{j}=0$ for $j>k$). Zeilberger’s algorithm certifies that the right-
hand side and the left-hand side of Eq. (149) both satisfy for all
$s,t\in\mathbb{N}$:

$\displaystyle-32$ $\displaystyle(t+2)^{3}(t+1)^{2}(t+3)S(s,t)$ (150)
$\displaystyle+4(t+3)(t+2)(2s^{2}+4t^{2}-4st-7s+15t+14)S(s,t+1)$
$\displaystyle+(-2s+2t+5)(s-t-2)S(s,t+2)=0.$

It remains to check that the initialisation is correct. For all
$s\in\mathbb{N}$, this recurrence relation in $t$ is of order $2$. Since the
identities in Eq. (149) are trivial when $l>n$, i.e., $s>t$, we thus only need
to check Eq. (149) for $(s,t)=(0,0)$, $(s,t)=(0,1)$, and $(s,t)=(1,1)$, which
is straightforward: we obtain the values $0$, $0$ and $-8$ respectively, for
both sides of Eq. (149).

  * •

For $l$ odd, writing $l=2s+1$ and $n=2t+1$, the left-hand side of Eq. (147)
becomes:

$\displaystyle\frac{-1}{(2s+1)!}\sum_{k=2s+1}^{2t+1}$
$\displaystyle(-1)^{k}\binom{k}{2s+1}F_{k}^{2t+1}$ (151)
$\displaystyle=\frac{-1}{(2s+1)!}\sum_{k=0}^{2t-2s}(-1)^{k+2s+1}\binom{k+2s+1}{2s+1}F_{k+2s+1}^{2t+1}$
$\displaystyle=\frac{1}{(2s+1)!}\sum_{k=0}^{t-s}\left(-\binom{2k+2s}{2s+1}F_{2k+2s}^{2t+1}+\binom{2k+2s+1}{2s+1}F_{2k+2s+1}^{2t+1}\right)$
$\displaystyle=q_{2t+1}^{2}\frac{(2t+1)!}{(2s+1)!}\sum_{k=0}^{t-s}\left(-\frac{\binom{2k+2s}{2s+1}\binom{t}{k+s}^{2}}{\binom{2t+1}{2k+2s}}+\frac{\binom{2k+2s+1}{2s+1}\binom{t}{k+s}^{2}}{\binom{2t+1}{2k+2s+1}}\right)$
$\displaystyle=q_{2t+1}^{2}\frac{(2t+1)!}{(2s+1)!}\sum_{k=0}^{t-s}\frac{\binom{2k+2s}{2s+1}\binom{t}{k+s}^{2}}{\binom{2t+1}{2k+2s}}\left(-1+\frac{(2k+2s+1)^{2}}{2k(2t-2k-2s+1)}\right),$

where we used that $\binom{2k+2s}{2s+1}=0$ for $k=0$ in the third line. Note
that when factorising we introduced an indeterminate form in the last line
that Zeilberger’s algorithm can resolve. This is necessary since the algorithm
cannot deal with differences of binomial terms. With Eq. (146) and Eq. (147),
we thus have to check the identity:

$\displaystyle\frac{(2t+1)!}{(2s+1)!}$
$\displaystyle\sum_{k=0}^{t-s}\frac{\binom{2k+2s}{2s+1}\binom{t}{k+s}^{2}}{\binom{2t+1}{2k+2s}}\left(-1+\frac{(2k+2s+1)^{2}}{2k(2t-2k-2s+1)}\right)$
(152)
$\displaystyle=\sum_{i=0}^{2t-2s}\frac{q_{2t+1-2i}q_{2t+1-(4t-4s-2i)}}{q_{2t+1}^{2}}$
$\displaystyle=\sum_{i=0}^{2t-2s}2^{2t-2s}\frac{(2t+2)^{2}i!(2t-2s-i)!}{(2t-2i+2)(4s+2i-2t+2)}\binom{t}{i}^{2}\binom{t}{2t-2s-i}^{2},$

for all $t\in\mathbb{N}$ and all $s\leq t$ (with the convention
$\binom{k}{j}=0$ for $j>k$). Zeilberger’s algorithm certifies that both the
right-hand side and the left-hand side of Eq. (152) satisfy for all $s\leq t$:

$\displaystyle-32$ $\displaystyle(t+2)^{3}(t+1)^{2}(t+3)S(s,t)$ (153)
$\displaystyle+4(t+3)(t+2)(2s^{2}+4t^{2}-4st-5s+13t+11)S(s,t+1)$
$\displaystyle+(-2s+2t+3)(s-t-2)S(s,t+2)=0.$

It remains to check that the initialisation is correct. For all
$s\in\mathbb{N}$, this recurrence relation in $t$ is of order $2$. Since the
identities in Eq. (152) are trivial when $l>n$, i.e., $s>t$, we thus only need
to check Eq. (152) for $(s,t)=(0,0)$, $(s,t)=(0,1)$, and $(s,t)=(1,1)$, which
is straightforward: we obtain the values $1$, $16$ and $1$ respectively, for
both sides of Eq. (152).

∎

Having derived these identities, we now recall the lemma from the main text we
wish to prove:

######  Lemma 7.

For all $m\geq n$, $\bm{F}^{n}$ is a feasible solution of
$(\text{SDP}^{m,\leq}_{n})$. Moreover, it is optimal when $m=n$.

###### Proof.

The proof has three parts. In the first we focus on $n$ even, and in the
second on $n$ odd. In the last part, we exhibit a feasible solution of
$(\text{D-SDP}^{m,\leq}_{n})$ for $m=n$ with the same optimal value
$F_{n}^{n}$.

#####  $n$ even, $m\geq n$:

we check that $\bm{F}^{n}$ defined in Eq. (131) satisfies all the constraints
of $(\text{SDP}^{m,\leq}_{n})$.

  * •

For all $k\in\mathbb{N}$, $F_{k}^{n}\geq 0$.

  * •

We have

$\displaystyle\sum_{k=0}^{\infty}F_{k}^{n}$
$\displaystyle=\sum_{\begin{subarray}{c}k=0\\\
\text{even}\end{subarray}}^{n}\frac{1}{2^{n}}\binom{k}{\frac{k}{2}}\binom{n-k}{\frac{n-k}{2}}$
(154)
$\displaystyle=\sum_{k=0}^{\frac{n}{2}}\frac{1}{2^{n}}\binom{2k}{k}\binom{n-2k}{\frac{n}{2}-k}$
$\displaystyle=1,$

where the last equality follows from [69, (3.90)].

  * •

We have to show that $x\mapsto\sum_{k=0}^{n}(-1)^{k}F_{k}^{n}L_{k}(x^{2})$ is
a positive function on $\mathbb{R}$. Due to Lemma 3, we aim to find a sum of
squares decomposition for this polynomial. Guided by numerical results, we
look for a polynomial
$P(x)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\sum_{i=0}^{n}p_{i}x^{i}$
such that:

$\displaystyle\sum_{k=0}^{n}(-1)^{k}F_{k}^{n}L_{k}(x^{2})$
$\displaystyle=P^{2}(x^{2})$ (155)
$\displaystyle=\left(\sum_{i=0}^{n}p_{i}x^{2i}\right)^{2}$
$\displaystyle=\sum_{l=0}^{n}\left(\sum_{\begin{subarray}{c}i+j=l\\\ 0\leq
i,j\leq n\end{subarray}}p_{i}p_{j}\right)x^{2l},$

and the sought coefficients are given by Lemma 12, which concludes the first
part of the proof.

#####  $n$ odd, $m\geq n$:

similarly, we check that $\bm{F}^{n}$ defined in Eq. (132) satisfies all the
constraints of $(\text{SDP}^{m,\leq}_{n})$.

  * •

For all $k\in\mathbb{N}$, $F_{k}^{n}\geq 0$.

  * •

Writing $n=2t+1$, from Eq. (132) we have

$\begin{split}&\forall s\leq
t,\;F^{2t+1}_{2s}=\frac{1}{2^{2t+2}}\left(1-\frac{s}{t+1}\right)\binom{2s}{s}\binom{2t+2-2s}{t+1-s}\\\
&\forall s\in\llbracket
1,t+1\rrbracket,\;F^{2t+1}_{2s-1}=\frac{1}{2^{2t+2}}\frac{s}{t+1}\binom{2s}{s}\binom{2t+2-2s}{t+1-s}.\end{split}$
(156)

In particular, for all $s\leq t$ we have

$F^{2t+1}_{2s-1}+F^{2t+1}_{2s}=F^{2t+2}_{2s},$ (157)

where $F^{2t+2}_{2s}$ is defined in Eq. (131). Since $F^{2t+2}_{2s+1}=0$ for
all $s\leq t$, and $F_{k}^{n}=0$ for all $k>n$, we have:

$\displaystyle\sum_{k=0}^{\infty}F_{k}^{n}$
$\displaystyle=\sum_{k=0}^{\infty}F_{k}^{n+1}$ (158) $\displaystyle=1,$

where we used Eq. (154).

  * •

We have to show that $x\mapsto\sum_{k=0}^{n}(-1)^{k}F_{k}^{n}L_{k}(x^{2})$ is
a positive function on $\mathbb{R}$. Due to Lemma 3, we aim to find a sum of
squares decomposition for this polynomial. Guided by numerical results, we
look for a polynomial
$Q(x)\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\sum_{i=0}^{n}q_{i}x^{i}$
such that:

$\displaystyle\sum_{k=0}^{n}(-1)^{k}F_{k}^{n}L_{k}(x^{2})$
$\displaystyle=Q^{2}(x^{2})$ (159)
$\displaystyle=\left(\sum_{i=0}^{n}q_{i}x^{2i}\right)^{2}$
$\displaystyle=\sum_{l=0}^{n}\left(\sum_{\begin{subarray}{c}i+j=l\\\ 0\leq
i,j\leq n\end{subarray}}q_{i}q_{j}\right)x^{2l},$

and the sought coefficients are given by Lemma 13, which concludes the second
part of the proof.

We thus obtained a feasible solution of (LP${}_{n}^{L^{2}}$) for all
$n\in\mathbb{N}^{*}$, which is feasible for $(\text{SDP}^{m,\leq}_{n})$ for
all $m\geq n$.

##### Optimality for $m=n$:

we now find an analytical solution of the dual (D-SDP${}_{n}^{n,\leq}$) with
the same optimal value as the primal (SDP${}_{n}^{n,\leq}$), by finding a
Cholesky decomposition for the matrix appearing in the dual program
$(\text{D-SDP}^{m,\leq}_{n})$ for $m=n$. The coefficients of the Cholesky
decomposition are given by the triangular matrix $L$ with coefficients:

$\begin{split}\forall j\leq i,\quad&l_{2i,2j}=2^{i}i!\binom{i}{j}\\\ \forall
j\leq i,\quad&l_{2i+1,2j+1}=2^{i+1/2}\frac{(i+1)!}{\sqrt{j+1}}\binom{i}{j}\\\
&l_{nn}=0\\\ &l_{ij}=0\quad\text{otherwise}.\end{split}$ (160)

Once again, these analytical expressions were extrapolated from numerical
values. Then, $A=LL^{T}$ is a positive semidefinite matrix given by:

$A_{ij}=\sum_{k=0}^{\min(i,j)}l_{ik}l_{jk}.$ (161)

Now $l_{ij}$ is non-zero only when $i$ and $j$ have the same parity, so for
all $k\in\llbracket 0,\min(i,j)\rrbracket$, $i$ and $j$ must have the same
parity than $k$ for $l_{ik}l_{jk}$ to be non-zero.

  * •

Suppose $i=2i^{\prime}$, $j=2j^{\prime}$, $i^{\prime}\leq j^{\prime}$ and
$(i^{\prime},j^{\prime})\neq(n,n)$. Furthermore let $l=\frac{i+j}{2}$.

$\displaystyle A_{ij}$ $\displaystyle=\sum_{\begin{subarray}{c}k=0\\\ k\text{
even}\end{subarray}}^{i}l_{2i^{\prime},k}l_{2j^{\prime},k^{\prime}}$ (162)
$\displaystyle=\sum_{k=0}^{i^{\prime}}2^{i^{\prime}}i^{\prime}!\binom{i^{\prime}}{k}2^{j^{\prime}}j^{\prime}!\binom{j^{\prime}}{k}$
$\displaystyle=2^{l}i^{\prime}!(l-i^{\prime})!\sum_{k=0}^{i^{\prime}}\binom{i^{\prime}}{k}\binom{l-i^{\prime}}{k}$
$\displaystyle=2^{l}l!.$

  * •

Suppose $i=2i^{\prime}+1$, $j=2j^{\prime}+1$, $i^{\prime}\leq j^{\prime}$ and
$(i^{\prime},j^{\prime})\neq(n,n)$. Furthermore let $l=\frac{i+j}{2}$.

$\displaystyle A_{ij}$ $\displaystyle=\sum_{\begin{subarray}{c}k=0\\\ k\text{
odd}\end{subarray}}^{i}l_{2i^{\prime}+1,k}l_{2j^{\prime}+1,k}$ (163)
$\displaystyle=\sum_{k=0}^{i^{\prime}}2^{i^{\prime}+1/2}\frac{(i^{\prime}+1)!}{\sqrt{k+1}}\binom{i^{\prime}}{k}2^{j^{\prime}+1/2}\frac{(j^{\prime}+1)!}{\sqrt{k+1}}\binom{j^{\prime}}{k}$
$\displaystyle=2^{l}i^{\prime}!(l-i^{\prime})!\sum_{k=0}^{i^{\prime}}\binom{i^{\prime}+1}{k+1}\binom{l-i^{\prime}-1}{k}$
$\displaystyle=2^{l}l!.$

  * •

Suppose $n=2t$:

$\displaystyle A_{nn}$ $\displaystyle=\sum_{k=0}^{t}l_{2t,2k}^{2}$ (164)
$\displaystyle=2^{2t}(t!)^{2}\sum_{k=0}^{t-1}\binom{t}{k}^{2}$
$\displaystyle=2^{n}(t!)^{2}\left(\binom{2t}{t}-1\right)$
$\displaystyle=2^{n}n!\left(1-\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}^{-1}\right).$

  * •

Suppose $n=2t+1$:

$\displaystyle A_{nn}$ $\displaystyle=\sum_{\begin{subarray}{c}k=0\\\ k\text{
odd}\end{subarray}}^{t}l_{2t+1,k}^{2}$ (165)
$\displaystyle=2^{2t+1}(t+1)!^{2}\sum_{k=0}^{t-1}\frac{1}{k+1}\binom{t}{k}^{2}$
$\displaystyle=2^{n}t!(t+1)!\sum_{k=0}^{t-1}\binom{t+1}{k+1}\binom{t}{k}$
$\displaystyle=2^{n}t!(t+1)!\left(\binom{2t+1}{t}-1\right)$
$\displaystyle=2^{n}n!\left(1-\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}^{-1}\right).$

In both cases, $A$ is indeed constructed as:

$(A_{\bm{\mu}})_{i,j}=\begin{cases}\sum_{k=0}^{l}\mu_{k}\binom{l}{k}l!&\text{when
}i+j=2l,\\\ 0&\text{otherwise},\end{cases}$ (166)

for $\bm{\mu}=(F_{n}^{n},F_{n}^{n},\dots,F_{n}^{n},1-F_{n}^{n})$ with
$F_{n}^{n}=\frac{1}{2^{n}}\binom{n}{\left\lfloor\frac{n}{2}\right\rfloor}$,
and this provides a feasible solution of $(\text{D-SDP}^{m,\leq}_{n})$ for
$m=n$, with value $F_{n}^{n}$. This shows the optimality of $\bm{F}^{n}$ for
(SDP${}_{n}^{n,\leq}$) (and the fact that strong duality holds between the
programs (SDP${}_{n}^{n,\leq}$) and (D-SDP${}_{n}^{n,\leq}$), which we already
knew from Theorem 2).

∎

For $(\text{D-SDP}^{m,\leq}_{n})$, we see numerically that the optimal
solution is the same as for (D-SDP${}_{n}^{n,\leq}$), for a few values of $m$
greater than $n$. However, this is no longer the case for higher values, for
example when $n=3$ and $m=10$.

##  Appendix G Strong duality between (LP${}_{n}^{L^{2}}$) and
(D-LP${}_{n}^{L^{2}}$)

Theorem 6 shows that the optimal values of (LP${}_{n}^{L^{2}}$) and
(D-LP${}_{n}^{L^{2}}$) are equal, i.e., that we have strong duality between
those programs both when they are expressed in the search space
$L^{2}(\mathbb{R}_{+})$ and $\mathcal{S}(\mathbb{R}_{+})$.

In this section we give another proof of strong duality between these linear
programs as usually done in the literature of infinite-dimensional
optimisation [81, 82], when they are expressed in the search space
$L^{2}(\mathbb{R}_{+})$.

Note that this result itself is not enough to provide the convergence of our
hierarchy of semidefinite programs, hence the need for another proof
technique: strong duality directly results from the fact the feasible set of
(LP${}_{n}^{L^{2}}$) is closed when it is expressed over the search space
$L^{2}(\mathbb{R}_{+})$.

We use notations from Appendix D. From [61, IV–(7.2)], there is no duality gap
between (LP${}_{n}^{L^{2}}$) and (D-LP${}_{n}^{L^{2}}$) if there is a primal
feasible plan and the cone:

$\displaystyle\mathcal{K}$ $\displaystyle=\Big{\\{}\Big{(}A(e_{1}),\langle
e_{1},c\rangle_{1}\Big{)}:e_{1}\in K_{1}\Big{\\}}$ (167)
$\displaystyle=\Big{\\{}\Big{(}\sum_{k}u_{k},x\in\mathbb{R}_{+}\mapsto
f(x)-\sum_{k}u_{k}\mathcal{L}_{k}(x),F_{n}\Big{)}:((u_{k}),f)\in
K_{1}\Big{\\}}$

is closed in $E_{2}\oplus\mathbb{R}$ (for the weak topology).

###### Proof.

The null sequence provides a feasible plan for the primal problem.

Next, we consider a sequence
$(e_{1j})_{j}=(((u_{k}^{j})_{k})_{j},(f_{j})_{j})\in
K_{1}^{\mathbb{N}}=\ell^{2}(\mathbb{N})\times
L^{2}_{+}(\mathbb{R}_{+})^{\mathbb{N}}$111111Because we are dealing with a
sequence of sequences, we use the upper index to refer to the embracing
sequence. and we want to show that the accumulation point
$(b,g,a)=\lim_{j\rightarrow\infty}(A(e_{1j}),\langle e_{1j},c\rangle_{1})$
belongs to $\mathcal{K}$ where $a,b\in\mathbb{R}$ and $g\in
L^{2}(\mathbb{R}_{+})$.

For all $j\in\mathbb{N}$, $(u_{k}^{j})_{k}\in\ell^{2}$ and for all
$k\in\mathbb{N}$, $u_{k}^{j}$ is bounded. Thus, for all $k\in\mathbb{N}$, the
sequence $(u_{k}^{j})_{j}$ is bounded and via diagonal extraction there exists
$\phi:\mathbb{N}\rightarrow\mathbb{N}$ strictly increasing such that
$(u_{k}^{j})_{\phi(j)}$ converges. We denote $\tilde{u}_{k}$ its limit. Since
$\ell^{2}$ is closed, the sequence $(\tilde{u}_{k})_{k}$ belongs to $\ell^{2}$
and we have $b=\sum_{k}\tilde{u}_{k}$ and $a=\tilde{u}_{n}$.

Now $f_{j}-\sum_{k}u_{k}^{j}\mathcal{L}_{k}\longrightarrow g$ so that
$f_{j}\longrightarrow g+\sum_{k}\tilde{u}_{k}\mathcal{L}_{k}\in
L^{2}_{+}(\mathbb{R}_{+})$ since $L^{2}_{+}(\mathbb{R}_{+})$ is closed. Thus,
for
$\tilde{e}_{1}=((\tilde{u}_{k})_{k},g+\sum_{k}\tilde{u}_{k}\mathcal{L}_{k})\in
K_{1}$, $(b,g,a)=(A(\tilde{e}_{1}),\langle\tilde{e}_{1},c\rangle_{1})$ and
$(b,g,a)\in\mathcal{K}$. ∎

##  Appendix H Multimode case

In this section, we provide the technical background for proving the
convergence of the hierarchies of semidefinite programs in the multimode
setting. The results obtained are summarised in Fig. 6.

###  H.1 Multimode notations and definitions

We use bold math for multi-index notations. The main advantage of these
notations is that the proofs of most technical results are easily extended to
the multimode setting by replacing standard notations by multi-index
notations.

Let $M$ denote the number of modes. We consider $M$ copies
$\mathcal{H}^{\otimes M}$ of a separable Hilbert space $\mathcal{H}$. We
denote the corresponding multimode orthonormal Fock basis by
$\\{\ket{\bm{n}}\\}_{\bm{n}\in\mathbb{N}^{M}}$. For all
$\bm{\alpha}=(\alpha_{1},\dots,\alpha_{M})\in\mathbb{C}^{M}$,
$\bm{k}=(k_{1},\dots,k_{M})\in\mathbb{N}^{M}$,
$\bm{n}=(n_{1},\dots,n_{M})\in\mathbb{N}^{M}$ and $m\in\mathbb{N}$, we
introduce the notations:

$\displaystyle\bm{0}$ $\displaystyle=(0,\dots,0)\in\mathbb{N}^{M}$ (168)
$\displaystyle\bm{1}$ $\displaystyle=(1,\dots,1)\in\mathbb{N}^{M}$
$\displaystyle m\bm{1}$ $\displaystyle=(m,\dots,m)$ $\displaystyle m\bm{k}$
$\displaystyle=(mk_{1},\dots,mk_{M})$ $\displaystyle\pi_{\bm{k}}$
$\displaystyle=\prod_{i=1}^{M}(k_{i}+1)$ $\displaystyle\hat{D}(\bm{\alpha})$
$\displaystyle=\hat{D}(\alpha_{1})\otimes\cdots\otimes\hat{D}(\alpha_{M})$
$\displaystyle\ket{\bm{k}}$
$\displaystyle=\ket{k_{1}}\otimes\cdots\otimes\ket{k_{M}}$
$\displaystyle\bra{\bm{k}}$
$\displaystyle=\bra{k_{1}}\otimes\cdots\otimes\bra{k_{M}}$
$\displaystyle\bm{k}\leq\bm{n}$ $\displaystyle\Leftrightarrow\,k_{i}\leq
n_{i}\quad\forall i=1,\dots,M$ $\displaystyle L_{\bm{k}}(\bm{\alpha})$
$\displaystyle=L_{k_{1}}(\alpha_{1})\cdots L_{k_{M}}(\alpha_{M})$
$\displaystyle\mathcal{L}_{\bm{k}}(\bm{\alpha})$
$\displaystyle=\mathcal{L}_{k_{1}}(\alpha_{1})\cdots\mathcal{L}_{k_{M}}(\alpha_{M})$
$\displaystyle|\bm{k}|$ $\displaystyle=k_{1}+\cdots+k_{M}$
$\displaystyle\bm{\alpha}^{\bm{k}}$
$\displaystyle=\alpha_{1}^{k_{1}}\cdots\alpha_{M}^{k_{M}}$
$\displaystyle\bm{k}!$ $\displaystyle=k_{1}!\cdots k_{m}!$
$\displaystyle\binom{\bm{n}}{\bm{k}}$
$\displaystyle=\binom{n_{1}}{k_{1}}\cdots\binom{n_{M}}{k_{M}}$
$\displaystyle\bm{k}+\bm{n}$ $\displaystyle=(k_{1}+n_{1},\dots,k_{M}+n_{M})$
$\displaystyle e^{\bm{\alpha}}$ $\displaystyle=e^{\alpha_{1}}\cdots
e^{\alpha_{M}}.$

A multivariate polynomial of degree $p\in\mathbb{N}$ may then be written in
the compact form $P(\bm{x})=\sum_{|\bm{l}|\leq p}p_{\bm{l}}\bm{x}^{\bm{l}}$,
where the sum is over all the tuples $\bm{l}\in\mathbb{N}^{M}$ such that
$|\bm{l}|\leq m$, also known as the weak compositions of the integer $m$.
There are $\binom{M+m}{m}$ such tuples. In what follows, we will also consider
sums over all the tuples $\bm{l}\in\mathbb{N}^{M}$ such that
$\bm{l}\leq\bm{k}$, for $\bm{k}=(k_{1},\dots,k_{M})\in\mathbb{N}^{M}$. There
are $\pi_{\bm{k}}$ such tuples. In particular, for all
$\bm{x}\in\mathbb{R}_{+}^{M}$ and all $\bm{k}\in\mathbb{N}^{M}$,

$L_{\bm{k}}(\bm{x})=\sum_{\bm{l}\leq\bm{k}}\frac{(-1)^{|\bm{l}|}}{\bm{l}!}\binom{\bm{k}}{\bm{l}}\bm{x}^{\bm{l}}\quad\text{and}\quad\bm{x}^{\bm{k}}=\sum_{\bm{l}\leq\bm{k}}(-1)^{|\bm{l}|}\binom{\bm{k}}{\bm{l}}\bm{k}!L_{\bm{l}}(\bm{x}).$
(169)

We extend a few definitions from the single-mode case.

For
$\bm{s}=(s_{\bm{k}})_{\bm{k}\in\mathbb{N}^{M}}\in\mathbb{R}^{\mathbb{N}^{M}}$,
we define the associated formal series of multivariate Laguerre functions:

$f_{\bm{s}}:=\sum_{\bm{k}}s_{\bm{k}}\mathcal{L}_{\bm{k}},$ (170)

where $\bm{s}$ is the so-called sequence of Laguerre moments of $f_{\bm{s}}$.
For $m\in\mathbb{N}$, we also define the associated
$\binom{M+m}{m}\times\binom{M+m}{m}$ matrix $A_{\bm{s}}$ by

$(A_{\bm{s}})_{\bm{i},\bm{j}}=\begin{cases}\sum_{\bm{k}\leq\bm{l}}s_{\bm{k}}\binom{\bm{l}}{\bm{k}}\bm{l}!&\text{when
}\bm{i}+\bm{j}=2\bm{l},\\\ 0&\text{otherwise,}\end{cases}$ (171)

where $\bm{i},\bm{j}\in\mathbb{N}^{M}$ with $|\bm{i}|\leq m$ and $|\bm{j}|\leq
m$.

The multimode Laguerre functions
$(\mathcal{L}_{\bm{k}})_{\bm{k}\in\mathbb{N}^{M}}$ form an orthonormal basis
of the space $L^{2}(\mathbb{R}_{+}^{M})$ of real square-integrable functions
over $\mathbb{R}_{+}^{M}$ equipped with the usual scalar product:

$\braket{f,g}=\int_{\mathbb{R}_{+}^{M}}{f(\bm{x})g(\bm{x})d\bm{x}},$ (172)

for $f,g\in L^{2}(\mathbb{R}_{+}^{M})$. We denote by
$L^{2}_{+}(\mathbb{R}_{+}^{M})$ its subset of non-negative elements. The space
$L^{2}(\mathbb{R}_{+}^{M})$ is isomorphic to its dual space
${L^{2}}^{\prime}(\mathbb{R}_{+}^{M})$: elements of
${L^{2}}^{\prime}(\mathbb{R}_{+}^{M})$ can be identified by the Lebesgue
measure on $\mathbb{R}_{+}^{M}$ times the corresponding function in
$L^{2}(\mathbb{R}_{+}^{M})$.

Moreover, the elements of the space $\mathcal{S}(\mathbb{R}_{+}^{M})$ of
Schwartz functions over $\mathbb{R}_{+}^{M}$, i.e., the space of $C^{\infty}$
functions that go to $0$ at infinity faster than any inverse polynomial, as do
their derivatives, can be written as series of Laguerre functions with a
sequence indexed by $\mathbb{N}^{M}$ of rapidly decreasing coefficients (which
go to $0$ at infinity faster than any inverse $M$-variate polynomial). Its
dual space $\mathcal{S}^{\prime}(\mathbb{R}_{+}^{M})$ of tempered
distributions over $\mathbb{R}_{+}^{M}$ is characterised as the space of
formal series of Laguerre functions with a slowly increasing sequence indexed
by $\mathbb{N}^{M}$ of coefficients (sequences that are upper bounded by an
$M$-variate polynomial) [64]. We also extend the definition of the duality
$\braket{\text{--},\text{--}}$ in Eq. (172) to these spaces.

For all $m\in\mathbb{N}$, the set of series of Laguerre functions over
$\mathbb{R}_{+}^{M}$ truncated at $m$ is denoted
$\mathcal{R}_{m}(\mathbb{R}_{+}^{M})$. This is the set of $M$-variate
polynomials $P(\bm{x})=\sum_{|\bm{k}|\leq m}p_{\bm{k}}\bm{x}^{\bm{k}}$ of
degree at most $m$ multiplied by the function $\bm{x}\mapsto
e^{-\frac{\bm{x}}{2}}$. Let $\mathcal{R}_{m,+}(\mathbb{R}_{+}^{M})$ denotes
its subset of non-negative elements where the polynomial $P$ is such that
$\bm{x}\mapsto P(\bm{x}^{2})$ has a sum-of-squares decomposition.

Similarly, for $\bm{m}\in\mathbb{N}^{M}$, the set of truncated series of
Laguerre functions over $\mathbb{R}_{+}^{M}$ with monomials smaller than
$\bm{m}$ is denoted $\mathcal{R}_{\bm{m}}(\mathbb{R}_{+}^{M})$. This is the
set of $M$-variate polynomials
$P(\bm{x})=\sum_{\bm{k}\leq\bm{m}}p_{\bm{k}}\bm{x}^{\bm{k}}$, multiplied by
the function $\bm{x}\mapsto e^{-\frac{\bm{x}}{2}}$. Let
$\mathcal{R}_{\bm{m},+}(\mathbb{R}_{+}^{M})$ denotes its subset of non-
negative elements where the polynomial $P$ is such that $\bm{x}\mapsto
P(\bm{x}^{2})$ has a sum-of-squares decomposition.

We recall here the expressions of the linear program (LP${}_{\bm{n}}^{L^{2}}$)
and its dual (D-LP${}_{\bm{n}}^{L^{2}}$):

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{(F_{\bm{k}})_{\bm{k}\in\mathbb{N}^{M}}\in\ell^{2}(\mathbb{N}^{M})}{\text{sup}}F_{\bm{n}}\\\
&\text{subject to}&&\sum_{\bm{k}}F_{\bm{k}}=1\\\
&\text{and}&&\forall\bm{k}\in\mathbb{N}^{M},\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\forall\bm{x}\in\mathbb{R}_{+}^{M},\quad\sum_{\bm{k}}F_{\bm{k}}\mathcal{L}_{\bm{k}}(\bm{x})\geq
0,\end{aligned}\right.$ (LP${}_{\bm{n}}^{L^{2}}$)

where the optimisation is over real sequences indexed by elements of
$\mathbb{N}^{M}$. Its dual linear program reads

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}y\in\mathbb{R}\\\
\mu\in{L^{2}}^{\prime}(\mathbb{R}_{+}^{M})\end{subarray}}{\text{inf}}y\\\
&\text{subject
to}&&\forall\bm{k}\neq\bm{n}\in\mathbb{N}^{M},\;y\geq\int_{\mathbb{R}_{+}^{M}}{\mathcal{L}_{\bm{k}}}{d\mu}\\\
&\text{and}&&y\geq 1+\int_{\mathbb{R}_{+}^{M}}{\mathcal{L}_{\bm{n}}}{d\mu}\\\
&\text{and}&&\forall f\in
L^{2}_{+}(\mathbb{R}_{+}^{M}),\;\langle\mu,f\rangle\geq
0.\end{aligned}\right.$ (D-LP${}_{\bm{n}}^{L^{2}}$)

We also recall the expression or (LP${}_{\bm{n}}^{\mathcal{S}}$) and
(D-LP${}_{\bm{n}}^{\mathcal{S}}$):

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{(F_{\bm{k}})_{\bm{k}\in\mathbb{N}^{M}}\in\
\mathcal{S}(\mathbb{N}^{M})}{\text{sup}}F_{\bm{n}}\\\ &\text{subject
to}&&\sum_{\bm{k}}F_{\bm{k}}=1\\\
&\text{and}&&\forall\bm{k}\in\mathbb{N}^{M},\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\forall\bm{x}\in\mathbb{R}_{+}^{M},\quad\sum_{\bm{k}}F_{\bm{k}}\mathcal{L}_{\bm{k}}(\bm{x})\geq
0,\end{aligned}\right.$ (LP${}_{\bm{n}}^{\mathcal{S}}$) $\displaystyle\hskip
79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}y\in\mathbb{R}\\\
\mu\in\mathcal{S}^{\prime}(\mathbb{R}_{+}^{M})\end{subarray}}{\text{inf}}y\\\
&\text{subject
to}&&\forall\bm{k}\neq\bm{n}\in\mathbb{N}^{M},\;y\geq\int_{\mathbb{R}_{+}^{M}}{\mathcal{L}_{\bm{k}}}{d\mu}\\\
&\text{and}&&y\geq 1+\int_{\mathbb{R}_{+}^{M}}{\mathcal{L}_{\bm{n}}}{d\mu}\\\
&\text{and}&&\forall f\in
L^{2}_{+}(\mathbb{R}_{+}^{M}),\;\langle\mu,f\rangle\geq
0.\end{aligned}\right.$ (D-LP${}_{\bm{n}}^{\mathcal{S}}$)

###  H.2 Multimode semidefinite programs

01$\omega_{\bm{n}}^{m\bm{1},\leq}$$\omega_{\bm{n}}^{L^{2}}$$\omega_{\bm{n}}^{\mathcal{S}}$$\omega_{\bm{n}}^{m\bm{1},\geq}$$(\text{SDP}^{m\bm{1},\geq}_{\bm{n}})$(D-SDP${}_{\bm{n}}^{m\bm{1},\geq}$)(LP${}_{\bm{n}}^{L^{2}}$)(D-LP${}_{\bm{n}}^{L^{2}}$)(LP${}_{\bm{n}}^{\mathcal{S}}$)(D-LP${}_{\bm{n}}^{\mathcal{S}}$)(SDP${}_{\bm{n}}^{m\bm{1},\leq}$)$(\text{D-SDP}^{m\bm{1},\leq}_{\bm{n}})$$\begin{subarray}{c}\text{Theorem}\leavevmode\nobreak\
\ref{th:sduppermulti}\\\
=\joinrel=\end{subarray}$$\begin{subarray}{c}\text{Theorem}\leavevmode\nobreak\
\ref{th:sdLPmulti}\\\
=\joinrel=\end{subarray}$$\begin{subarray}{c}\text{Theorem}\leavevmode\nobreak\
\ref{th:sdLPmulti}\\\
=\joinrel=\end{subarray}$$\begin{subarray}{c}\text{Theorem}\leavevmode\nobreak\
\ref{th:sdlowermulti}\\\
=\joinrel=\end{subarray}$$\begin{subarray}{c}\text{Theorem\leavevmode\nobreak\
\ref{th:upperCVmulti}}\\\ \hskip
20.0pt\big{\downarrow}m\rightarrow\infty\end{subarray}$$\begin{subarray}{c}\hskip
20.0pt\big{\uparrow}m\rightarrow\infty\\\ \text{Theorem\leavevmode\nobreak\
\ref{th:lowerCVmulti}}\end{subarray}$$\begin{subarray}{c}\text{Theorem\leavevmode\nobreak\
\ref{th:upperCVmulti}}\\\ \hskip
20.0pt\big{\downarrow}m\rightarrow\infty\end{subarray}$$\begin{subarray}{c}\hskip
20.0pt\big{\uparrow}m\rightarrow\infty\\\ \text{Theorem\leavevmode\nobreak\
\ref{th:lowerCVmulti}}\end{subarray}$ Figure 6: Multimode hierarchies of
semidefinite relaxations and restrictions converging to the linear program
(LP${}_{\bm{n}}^{L^{2}}$), together with their dual programs. The upper index
$m$ denotes the level of the relaxation or restriction. On the left are the
associated optimal values. The equal sign denotes strong duality, i.e.,
equality of optimal values, and the arrows denote convergence of the
corresponding sequences of optimal values. The hierarchies
$(\text{SDP}^{m,\geq}_{\bm{n}})$ and $(\text{SDP}^{m,\leq}_{\bm{n}})$ in the
main text are different from the ones appearing in the figure, but equivalent
by Lemma 17. The question of whether
$\omega_{\bm{n}}^{L^{2}}=\omega_{\bm{n}}^{\mathcal{S}}$ is left open.

Hereafter, we state without proofs the technical results used to derive the
semidefinite programs in section 6 and their dual programs. It is a
straightforward exercise to obtain the proofs from their single-mode version
by using multi-index notations.

There are two natural ways to obtain relaxations and restrictions by replacing
constraints on non-negative functions by constraints on non-negative
polynomials: either by considering polynomials $P(\bm{x})=\sum_{|\bm{k}|\leq
m}p_{\bm{k}}\bm{x}^{\bm{k}}$ of degree at most $m$ for $m\in\mathbb{N}$, or by
considering polynomials
$P(\bm{x})=\sum_{\bm{k}\leq\bm{m}}p_{\bm{k}}\bm{x}^{\bm{k}}$ with monomials
smaller than $\bm{m}$ for $m\in\mathbb{N}^{M}$. Note that when $M=1$ these two
are equivalent.

All the results below containing conditions of the form $|\bm{k}|\leq m$ for
$m\in\mathbb{N}$ are also valid when replaced by conditions of the form
$\bm{k}\leq\bm{m}$ for $\bm{m}=(m_{1},\dots,m_{M})\in\mathbb{N}^{M}$, with the
same proofs, by replacing $\binom{M+m}{m}$ by
$\pi_{\bm{m}}=\prod_{i=1}^{M}(m_{i}+1)$.

######  Lemma 14 (Equivalent of Lemma 3).

Let $p\in\mathbb{N}$ and let $P$ be a multivariate polynomial of degree $2p$.
Let $\bm{X}=(\bm{x}^{\bm{k}})_{|\bm{k}|\leq p}$ be the vector of monomials.
Then, $P$ has a sum-of-squares decomposition if and only if there exists a
real ${\binom{M+p}{p}}\times{\binom{M+p}{p}}$ positive semidefinite matrix $Q$
such that for all $x\in\mathbb{R}^{M}$,

$P(\bm{x})=\bm{X}^{T}Q\bm{X}.$ (173)

######  Lemma 15 (Generalisation of Lemma 4).

Let $P$ be a non-negative polynomial over $\mathbb{R}_{+}^{M}$ such that
$\bm{x}\mapsto P(\bm{x}^{2})$ has a sum-of-squares decomposition. Then, $P$
can be written as a sum of polynomials of the form $\sum_{|\bm{l}|\leq
p}\bm{x}^{\bm{l}}\sum_{\bm{i}+\bm{j}=2\bm{l}}y_{\bm{i}}y_{\bm{j}}$ for
$p\in\mathbb{N}$ and $y_{\bm{i}}\in\mathbb{R}$ for all
$\bm{i}\in\mathbb{N}^{M}$ such that $|\bm{i}|\leq p$.

######  Lemma 16 (Generalisation of Lemma 5).

Let $m\in\mathbb{N}$ and let
$\bm{s}=(s_{\bm{k}})_{\bm{k}\in\mathbb{N}^{M}}\in\mathbb{R}^{\mathbb{N}^{M}}$.
The following propositions are equivalent:

  1. (i)

$\forall g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}^{M}),\;\braket{f_{\bm{s}},g}\geq
0$,

  2. (ii)

$A_{\bm{s}}\succeq 0$.

Using Lemma 16 we obtain the semidefinite relaxations:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A\in\text{Sym}_{\binom{M+m}{m}}\\\
\bm{F}\in\mathbb{R}^{\binom{M+m}{m}}\end{subarray}}{\text{sup}}F_{\bm{n}}\\\
&\text{subject to}&&\sum_{|\bm{k}|\leq m}F_{\bm{k}}=1\\\
&\text{and}&&\forall|\bm{k}|\leq m,\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\forall|\bm{l}|\leq m,\forall\bm{i}+\bm{j}=2\bm{l},\quad
A_{\bm{i}\bm{j}}=\sum\limits_{\bm{k}\leq\bm{l}}F_{\bm{k}}\binom{\bm{l}}{\bm{k}}\bm{l}!\\\
&\text{and}&&\forall|\bm{r}|\leq
2m,\bm{r}\\!\neq\\!2\bm{l},\forall|\bm{l}|\leq
m,\forall\bm{i}+\bm{j}=\bm{r},\;A_{\bm{i}\bm{j}}=0\\\ &\text{and}&&A\succeq
0.\end{aligned}\right.$ $(\text{SDP}^{m,\geq}_{\bm{n}})$

for all $m\geq|\bm{n}|$. We denote its optimal value by
$\omega_{\bm{n}}^{m,\geq}$. The corresponding dual programs are given by:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{\binom{M+m}{m}}\\\
y\in\mathbb{R},\bm{\mu}\in\mathbb{R}^{\binom{M+m}{m}}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{\bm{n}}\\\ &\text{and}&&\forall|\bm{k}|\leq
m,\bm{k}\neq\bm{n},\quad y\geq\mu_{\bm{k}}\\\ &\text{and}&&\forall|\bm{l}|\leq
m,\quad\sum_{\bm{i}+\bm{j}=2\bm{l}}Q_{\bm{i}\bm{j}}=\sum_{\bm{k}\geq\bm{l}}\frac{(-1)^{|\bm{k}|+|\bm{l}|}}{\bm{l}!}\binom{\bm{k}}{\bm{l}}\mu_{\bm{k}}\\\
&\text{and}&&Q\succeq 0,\end{aligned}\right.$ (D-SDP${}_{\bm{n}}^{m,\geq}$)

for all $m\geq|\bm{n}|$. Similarly, using Lemma 14 we obtain the semidefinite
restrictions:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{\binom{M+m}{m}}\\\
\bm{F}\in\mathbb{R}^{\binom{M+m}{m}}\end{subarray}}{\text{sup}}F_{\bm{n}}\\\
&\text{subject to}&&\sum_{|\bm{k}|\leq m}F_{\bm{k}}=1\\\
&\text{and}&&\forall|\bm{k}|\leq m,\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\forall|\bm{l}|\leq
m,\quad\sum_{\bm{i}+\bm{j}=2\bm{l}}Q_{\bm{i}\bm{j}}=\sum_{\bm{k}\geq\bm{l}}\frac{(-1)^{|\bm{k}|+|\bm{l}|}}{\bm{l}!}\binom{\bm{k}}{\bm{l}}F_{\bm{k}}\\\
&\text{and}&&\forall|\bm{r}|\leq 2m,\bm{r}\neq 2\bm{l},\forall|\bm{l}|\leq
m,\quad\sum_{\bm{i}+\bm{j}=\bm{r}}Q_{\bm{i}\bm{j}}=0\\\ &\text{and}&&Q\succeq
0,\end{aligned}\right.$ (SDP${}_{\bm{n}}^{m,\leq}$)

for all $m\geq|\bm{n}|$. We denote its optimal value by
$\omega_{\bm{n}}^{m,\leq}$. The corresponding dual programs are given by:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A\in\text{Sym}_{\binom{M+m}{m}}\\\
y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{\binom{M+m}{m}}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{\bm{n}}\\\ &\text{and}&&\forall|\bm{k}|\leq
m,\bm{k}\neq\bm{n},\quad y\geq\mu_{\bm{k}}\\\ &\text{and}&&\forall|\bm{l}|\leq
m,\forall\bm{i}+\bm{j}=2\bm{l},\quad
A_{\bm{i}\bm{j}}=\sum\limits_{\bm{k}\leq\bm{l}}\mu_{\bm{k}}\binom{\bm{l}}{\bm{k}}\bm{l}!\\\
&\text{and}&&A\succeq 0,\end{aligned}\right.$
$(\text{D-SDP}^{m,\leq}_{\bm{n}})$

for all $m\geq|\bm{n}|$. Like in the single-mode case, note that without loss
of generality the condition $y\leq 1$, and thus $\mu_{\bm{k}}\leq 1$ for all
$\bm{k}$, can be added to the optimisation, since setting $A=0$, $y=1$ and
$\bm{\mu}=0$ gives a feasible solution with objective value 1.

These are the relaxations and restrictions of (LP${}_{\bm{n}}^{L^{2}}$)
obtained by considering polynomials of degree less or equal to $m$, where the
optimisation is over matrices and vectors indexed by elements of
$\mathbb{N}^{m}$ with sum of coefficients lower that $m$. Alternatively, we
may also consider the relaxations and restrictions obtained by considering
polynomials with monomials smaller than $\bm{m}\in\mathbb{N}^{M}$, where the
optimisation is over matrices and vectors indexed by elements of
$\mathbb{N}^{m}$ lower that $\bm{m}$. Recalling the notation
$\pi_{\bm{m}}=\prod_{i=1}^{M}(m_{i}+1)$, the corresponding semidefinite
relaxations are given by

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A\in\text{Sym}_{\pi_{\bm{m}}}\\\
\bm{F}\in\mathbb{R}^{\pi_{\bm{m}}}\end{subarray}}{\text{sup}}F_{\bm{n}}\\\
&\text{subject to}&&\sum_{\bm{k}\leq\bm{m}}F_{\bm{k}}=1\\\
&\text{and}&&\forall\bm{k}\leq\bm{m},\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\forall\bm{l}\leq\bm{m},\forall\bm{i}+\bm{j}=2\bm{l},\quad
A_{\bm{i}\bm{j}}=\sum\limits_{\bm{k}\leq\bm{l}}F_{\bm{k}}\binom{\bm{l}}{\bm{k}}\bm{l}!\\\
&\text{and}&&\forall\bm{r}\leq
2\bm{m},\bm{r}\\!\neq\\!2\bm{l},\forall\bm{l}\leq\bm{m},\forall\bm{i}+\bm{j}=\bm{r},\;A_{\bm{i}\bm{j}}=0\\\
&\text{and}&&A\succeq 0.\end{aligned}\right.$
$(\text{SDP}^{\bm{m},\geq}_{\bm{n}})$

for all $\bm{m}\geq\bm{n}$. We denote its optimal value by
$\omega_{\bm{n}}^{\bm{m},\geq}$. The corresponding dual programs are given by:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{\pi_{\bm{m}}}\\\
y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{\pi_{\bm{m}}}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{\bm{n}}\\\
&\text{and}&&\forall\bm{k}\leq\bm{m},\bm{k}\neq\bm{n},\quad
y\geq\mu_{\bm{k}}\\\
&\text{and}&&\forall\bm{l}\leq\bm{m},\quad\sum_{\bm{i}+\bm{j}=2\bm{l}}Q_{\bm{i}\bm{j}}=\sum_{\bm{k}\geq\bm{l}}\frac{(-1)^{|\bm{k}|+|\bm{l}|}}{\bm{l}!}\binom{\bm{k}}{\bm{l}}\mu_{\bm{k}}\\\
&\text{and}&&Q\succeq 0,\end{aligned}\right.$
(D-SDP${}_{\bm{n}}^{\bm{m},\geq}$)

for all $\bm{m}\geq\bm{n}$. Similarly, the semidefinite restrictions are given
by:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{\pi_{\bm{m}}}\\\
\bm{F}\in\mathbb{R}^{\pi_{\bm{m}}}\end{subarray}}{\text{sup}}F_{\bm{n}}\\\
&\text{subject to}&&\sum_{\bm{k}\leq\bm{m}}F_{\bm{k}}=1\\\
&\text{and}&&\forall\bm{k}\leq\bm{m},\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\forall\bm{l}\leq\bm{m},\quad\sum_{\bm{i}+\bm{j}=2\bm{l}}Q_{\bm{i}\bm{j}}=\sum_{\bm{k}\geq\bm{l}}\frac{(-1)^{|\bm{k}|+|\bm{l}|}}{\bm{l}!}\binom{\bm{k}}{\bm{l}}F_{\bm{k}}\\\
&\text{and}&&\forall\bm{r}\leq 2\bm{m},\bm{r}\neq
2\bm{l},\forall\bm{l}\leq\bm{m},\quad\sum_{\bm{i}+\bm{j}=\bm{r}}Q_{\bm{i}\bm{j}}=0\\\
&\text{and}&&Q\succeq 0,\end{aligned}\right.$ (SDP${}_{\bm{n}}^{\bm{m},\leq}$)

for all $\bm{m}\geq\bm{n}$. We denote its optimal value by
$\omega_{\bm{n}}^{\bm{m},\leq}$. The corresponding dual programs are given by:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A\in\text{Sym}_{\pi_{\bm{m}}}\\\
y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{\pi_{\bm{m}}}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{\bm{n}}\\\
&\text{and}&&\forall\bm{k}\leq\bm{m},\bm{k}\neq\bm{n},\quad
y\geq\mu_{\bm{k}}\\\
&\text{and}&&\forall\bm{l}\leq\bm{m},\forall\bm{i}+\bm{j}=2\bm{l},\quad
A_{\bm{i}\bm{j}}=\sum\limits_{\bm{k}\leq\bm{l}}\mu_{\bm{k}}\binom{\bm{l}}{\bm{k}}\bm{l}!\\\
&\text{and}&&A\succeq 0,\end{aligned}\right.$
$(\text{D-SDP}^{\bm{m},\leq}_{\bm{n}})$

for all $\bm{m}\geq\bm{n}$.

The programs $(\text{SDP}^{m,\geq}_{\bm{n}})$ and (SDP${}_{\bm{n}}^{m,\leq}$)
respectively provide hierarchies of relaxations and restrictions of
(LP${}_{\bm{n}}^{L^{2}}$), since the set of $M$-variate polynomials of degree
$m$ is included in the set of $M$-variate polynomials of degree $m+1$. On the
other hand, there is no natural ordering in $\mathbb{N}^{M}$ of the
relaxations $(\text{SDP}^{\bm{m},\geq}_{\bm{n}})$ or the restrictions
(SDP${}_{\bm{n}}^{\bm{m},\leq}$) (consider for instance $\bm{m}=(2,1)$ and
$\bm{m}^{\prime}=(1,2)$). In order to obtain proper hierarchies of
semidefinite programs, we thus consider the subset of these programs where the
tuple $\bm{m}$ is of the form $m\bm{1}=(m,\dots,m)\in\mathbb{N}^{M}$, for
$m\in\mathbb{N}$. We have $\pi_{m\bm{1}}=(m+1)^{M}$, and the relaxations are
then given by

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A\in\text{Sym}_{(m+1)^{M}}\\\
\bm{F}\in\mathbb{R}^{(m+1)^{M}}\end{subarray}}{\text{sup}}F_{\bm{n}}\\\
&\text{subject to}&&\sum_{\bm{k}\leq m\bm{1}}F_{\bm{k}}=1\\\
&\text{and}&&\forall\bm{k}\leq m\bm{1},\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\forall\bm{l}\leq m\bm{1},\forall\bm{i}+\bm{j}=2\bm{l},\quad
A_{\bm{i}\bm{j}}=\sum\limits_{\bm{k}\leq\bm{l}}F_{\bm{k}}\binom{\bm{l}}{\bm{k}}\bm{l}!\\\
&\text{and}&&\forall\bm{r}\leq
2m\bm{1},\bm{r}\\!\neq\\!2\bm{l},\forall\bm{l}\leq
m\bm{1},\forall\bm{i}+\bm{j}=\bm{r},\;A_{\bm{i}\bm{j}}=0\\\
&\text{and}&&A\succeq 0.\end{aligned}\right.$
$(\text{SDP}^{m\bm{1},\geq}_{\bm{n}})$

for $m\geq\max_{i}n_{i}$. We denote its optimal value by
$\omega_{\bm{n}}^{m\bm{1},\geq}$. The corresponding dual programs are given
by:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{(m+1)^{M}}\\\
y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{(m+1)^{M}}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{\bm{n}}\\\ &\text{and}&&\forall\bm{k}\leq
m\bm{1},\bm{k}\neq\bm{n},\quad y\geq\mu_{\bm{k}}\\\
&\text{and}&&\forall\bm{l}\leq
m\bm{1},\quad\sum_{\bm{i}+\bm{j}=2\bm{l}}Q_{\bm{i}\bm{j}}=\sum_{\bm{k}\geq\bm{l}}\frac{(-1)^{|\bm{k}|+|\bm{l}|}}{\bm{l}!}\binom{\bm{k}}{\bm{l}}\mu_{\bm{k}}\\\
&\text{and}&&Q\succeq 0,\end{aligned}\right.$
(D-SDP${}_{\bm{n}}^{m\bm{1},\geq}$)

for $m\geq\max_{i}n_{i}$. Similarly, the restrictions are given by:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}Q\in\text{Sym}_{(m+1)^{M}}\\\
\bm{F}\in\mathbb{R}^{(m+1)^{M}}\end{subarray}}{\text{sup}}F_{\bm{n}}\\\
&\text{subject to}&&\sum_{\bm{k}\leq m\bm{1}}F_{\bm{k}}=1\\\
&\text{and}&&\forall\bm{k}\leq m\bm{1},\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\forall\bm{l}\leq
m\bm{1},\quad\sum_{\bm{i}+\bm{j}=2\bm{l}}Q_{\bm{i}\bm{j}}=\sum_{\bm{k}\geq\bm{l}}\frac{(-1)^{|\bm{k}|+|\bm{l}|}}{\bm{l}!}\binom{\bm{k}}{\bm{l}}F_{\bm{k}}\\\
&\text{and}&&\forall\bm{r}\leq 2m\bm{1},\bm{r}\neq 2\bm{l},\forall\bm{l}\leq
m\bm{1},\quad\sum_{\bm{i}+\bm{j}=\bm{r}}Q_{\bm{i}\bm{j}}=0\\\
&\text{and}&&Q\succeq 0,\end{aligned}\right.$
(SDP${}_{\bm{n}}^{m\bm{1},\leq}$)

for $m\geq\max_{i}n_{i}$. We denote its optimal value by
$\omega_{\bm{n}}^{m\bm{1},\leq}$. The corresponding dual programs are given
by:

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\begin{subarray}{c}A\in\text{Sym}_{(m+1)^{M}}\\\
y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{(m+1)^{M}}\end{subarray}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{\bm{n}}\\\ &\text{and}&&\forall\bm{k}\leq
m\bm{1},\bm{k}\neq\bm{n},\quad y\geq\mu_{\bm{k}}\\\
&\text{and}&&\forall\bm{l}\leq m\bm{1},\forall\bm{i}+\bm{j}=2\bm{l},\quad
A_{\bm{i}\bm{j}}=\sum\limits_{\bm{k}\leq\bm{l}}\mu_{\bm{k}}\binom{\bm{l}}{\bm{k}}\bm{l}!\\\
&\text{and}&&A\succeq 0,\end{aligned}\right.$
$(\text{D-SDP}^{m\bm{1},\leq}_{\bm{n}})$

for $m\geq\max_{i}n_{i}$.

The programs $(\text{SDP}^{m\bm{1},\geq}_{\bm{n}})$ and
(SDP${}_{\bm{n}}^{m\bm{1},\leq}$) are the relaxations and restrictions of
(LP${}_{\bm{n}}^{L^{2}}$) obtained by considering polynomials of individual
degree in each variable less or equal to $m$. These programs respectively
provide hierarchies of relaxations and restrictions of
(LP${}_{\bm{n}}^{L^{2}}$), since the set of $M$-variate polynomials with
monomials lower than $m\bm{1}$ is included in the set of $M$-variate
polynomials with monomials lower than $(m+1)\bm{1}$.

Note that these hierarchies of programs obtained by setting $\bm{m}$ of the
form $m\bm{1}$ capture the behaviour of all bounds that can be obtained from
the more general family of programs indexed by $\bm{m}=(m_{1},\dots,m_{M})$,
since $\bm{m}\leq(\max_{i}m_{i})\bm{1}$, i.e., the bound obtained by
considering the program indexed by $(\max_{i}m_{i})\bm{1}$ supersedes the
bound obtained by considering the program indexed by $\bm{m}$. Formally, for
all $\bm{m}=(m_{1},\dots,m_{M})\in\mathbb{N}^{M}$,

$\omega_{\bm{n}}^{\bm{m},\geq}\geq\omega_{\bm{n}}^{(\max_{i}m_{i})\bm{1},\geq}\quad\text{and}\quad\omega_{\bm{n}}^{\bm{m},\leq}\leq\omega_{\bm{n}}^{(\max_{i}m_{i})\bm{1},\leq}.$
(174)

Finally, we show that both ways of defining the hierarchies are equivalent:

######  Lemma 17.

For all $m\in\mathbb{N}$,

$\omega_{\bm{n}}^{m,\geq}\geq\omega_{\bm{n}}^{m\bm{1},\geq}\geq\omega_{\bm{n}}^{Mm,\geq},$
(175)

and

$\omega_{\bm{n}}^{m,\leq}\leq\omega_{\bm{n}}^{m\bm{1},\leq}\leq\omega_{\bm{n}}^{Mm,\leq}.$
(176)

###### Proof.

For all $\bm{k}\in\mathbb{N}^{M}$ and all $m\in\mathbb{N}$ we have

$|\bm{k}|\leq m\quad\Rightarrow\quad\bm{k}\leq
m\bm{1}=(m,\dots,m)\quad\Rightarrow\quad|\bm{k}|\leq Mm.$ (177)

We thus obtain the corresponding inclusions between sets of $M$-variate
polynomials:  (i) $M$-variate polynomials of degree less or equal to $m$ have
all their monomials lower than $m\bm{1}$, and  (ii) all $M$-variate
polynomials with monomials lower than $m\bm{1}$ have degree less or equal to
$Mm$.  Hence,

$\mathcal{R}_{m,+}(\mathbb{R}_{+}^{M})\overset{(\text{i})}{\subset}\mathcal{R}_{m\bm{1},+}(\mathbb{R}_{+}^{M})\overset{(\text{ii})}{\subset}\mathcal{R}_{Mm,+}(\mathbb{R}_{+}^{M}).$
(178)

In particular, $(\text{SDP}^{m,\geq}_{\bm{n}})$ is a relaxation of
$(\text{SDP}^{m\bm{1},\geq}_{\bm{n}})$ which is itself a relaxation of
$(\text{SDP}_{\bm{n}}^{Mm,\geq})$, and (SDP${}_{\bm{n}}^{m,\leq}$) is a
restriction of (SDP${}_{\bm{n}}^{m\bm{1},\leq}$) which is itself a restriction
of $(\text{SDP}_{\bm{n}}^{Mm,\leq})$. ∎

This result implies that the two versions of the hierarchies of relaxations
are interleaved (Eq. (175)), and that the two versions of the hierarchies of
restrictions are also interleaved (Eq. (176)). As such, for any bound obtained
with one version of the hierarchy at some fixed level, a better bound can be
obtained with the other version at some other level. While this means that the
hierarchies are equivalent, note that in practice it may be simpler to solve
numerically the version where the parameter space is smaller.

###  H.3 Convergence of the multimode hierarchies

For $\bm{n}=(n_{1},\dots,n_{M})\in\mathbb{N}^{M}$, the sequences
$(\omega_{\bm{n}}^{m,\geq})_{m\geq|\bm{n}|}$ and
$(\omega_{\bm{n}}^{m\bm{1},\geq})_{m\geq\max_{i}n_{i}}$ (resp.
$(\omega_{\bm{n}}^{m,\leq})_{m\geq|\bm{n}|}$ and
$(\omega_{\bm{n}}^{m\bm{1},\leq})_{m\geq\max_{i}n_{i}}$) are decreasing (resp.
increasing) sequences, lower bounded (resp. upper bounded) by
$\omega_{\bm{n}}^{L^{2}}$ (resp. $\omega_{\bm{n}}^{\mathcal{S}})$). Hence,
these sequences are converging.

We show in what follows that
$(\omega_{\bm{n}}^{m\bm{1},\geq})_{m\geq\max_{i}n_{i}}$ (resp.
$(\omega_{\bm{n}}^{m\bm{1},\leq})_{m\geq\max_{i}n_{i}}$) converges to
$\omega_{\bm{n}}^{L^{2}}$ (resp. $\omega_{\bm{n}}^{\mathcal{S}}$). By Lemma
17, this implies that the sequence
$(\omega_{\bm{n}}^{Mm,\geq})_{m\geq\max_{i}n_{i}}$ (resp.
$(\omega_{\bm{n}}^{Mm,\leq})_{m\geq\max_{i}n_{i}}$) also converges to
$\omega_{\bm{n}}$. Since this is a subsequence of the converging sequence
$(\omega_{\bm{n}}^{m,\geq})_{m\geq|\bm{n}|}$ (resp.
$(\omega_{\bm{n}}^{m,\leq})_{m\geq|\bm{n}|}$), it implies that the sequence
$(\omega_{\bm{n}}^{m,\geq})_{m\geq|\bm{n}|}$ (resp.
$(\omega_{\bm{n}}^{m,\leq})_{m\geq|\bm{n}|}$) also converges to
$\omega_{\bm{n}}^{L^{2}}$ (resp. $\omega_{\bm{n}}^{\mathcal{S}}$).

With similar proofs to the single-mode case using multi-index notations, we
obtain the following result:

######  Theorem 8 (Generalisation of Theorem 1).

Let
$\bm{\mu}=(\mu_{\bm{k}})_{\bm{k}\in\mathbb{N}^{M}}\in\mathbb{R}^{\mathbb{N}^{M}}$.
Then, $\bm{\mu}$ is the sequence of Laguerre moments
$\int_{\mathbb{R}_{+}^{M}}\mathcal{L}_{\bm{k}}(\bm{x})d\mu(\bm{x})$ of a non-
negative distribution $\mu$ supported on $\mathbb{R}_{+}^{M}$ if and only if
$\forall m\in\mathbb{N},\forall
g\in\mathcal{R}_{m,+}(\mathbb{R}_{+}^{M}),\;\braket{f_{\bm{\mu}},g}\geq 0$.

The proof of this theorem is identical to the univariate case, with the use of
Riesz–Haviland theorem over $\mathbb{R}_{+}^{M}$ [67] rather than
$\mathbb{R}_{+}$.

With Eq. (178), the proof of convergence of the multimode hierarchy of upper
bounds is then obtained directly from its single-mode counterpart using multi-
index notations:

######  Theorem 9 (Generalisation of Theorem 4).

The decreasing sequence of optimal values $\omega^{m\bm{1},\geq}_{\bm{n}}$ of
$(\text{SDP}^{m\bm{1},\geq}_{\bm{n}})$ converges to the optimal value
$\omega_{\bm{n}}^{L^{2}}$ of (LP${}_{\bm{n}}^{L^{2}}$):

$\lim_{m\rightarrow+\infty}\omega^{m\bm{1},\geq}_{\bm{n}}=\omega_{\bm{n}}^{L^{2}}.$
(179)

With Lemma 17, we also obtain

$\lim_{m\rightarrow+\infty}\omega^{m,\geq}_{\bm{n}}=\omega_{\bm{n}}^{L^{2}}.$
(180)

On the other hand, the proof of convergence of the single-mode hierarchy of
lower bounds crucially exploits analytical feasible solutions of the programs
$(\text{SDP}^{m,\leq}_{n})$ in order to obtain two results:

  * •

Strong duality between programs $(\text{SDP}^{m,\leq}_{n})$ and
$(\text{D-SDP}^{m,\leq}_{n})$ (Theorem 2).

  * •

The fact that the feasible set of $(\text{D-SDP}^{m,\leq}_{n})$ is compact
with coefficients bounded independently of $m$ (Eq. (63)).

In what follows, we generalise these two results to the multimode setting by
obtaining multimode analytical feasible solutions from products of single-mode
ones.

######  Lemma 18.

For $m,n\in\mathbb{N}$ with $m\geq n$, let $Q(m,n)\in\text{Sym}_{m+1}$ and
$\bm{F}(m,n)=(F_{k}(m,n))_{k}\in\mathbb{R}^{m+1}$ be feasible solutions of
$(\text{SDP}^{m,\leq}_{n})$. Let $\bm{m}=(m_{1},\dots,m_{M})\in\mathbb{N}^{M}$
and $\bm{n}=(n_{1},\dots,n_{M})\in\mathbb{N}^{M}$ with $\bm{m}\geq\bm{n}$. Let
$Q:=Q(m_{1},n_{1})\otimes\dots\otimes
Q(m_{M},n_{M})\in\text{Sym}_{\pi_{\bm{m}}}$ and
$\bm{F}=(F_{\bm{k}})_{\bm{k}\leq\bm{m}}\in\mathbb{R}^{\pi_{\bm{m}}}$, where
for all $\bm{k}=(k_{1},\dots,k_{M})\leq\bm{m}$,
$F_{\bm{k}}:=\prod_{i=1}^{M}F_{k_{i}}(m_{i},n_{i})$. Then, $(Q,\bm{F})$ is a
feasible solution of (SDP${}_{\bm{n}}^{\bm{m},\leq}$). Moreover, if
$(Q(m_{i},n_{i}),\bm{F}(m_{i},n_{i}))$ is strictly feasible for all
$i=1,\dots,M$ then $(Q,\bm{F})$ is a strictly feasible solution of
(SDP${}_{\bm{n}}^{\bm{m},\leq}$).

###### Proof.

With the notations of the Lemma, we show the feasibility of $(Q,\bm{F})$
(resp. strict feasibility). We have $Q\succeq 0$, $F_{\bm{k}}\geq 0$ (resp.
$Q\succ 0$, $F_{\bm{k}}>0$) for all $\bm{k}\leq\bm{m}$, and
$Q_{\bm{i}\bm{j}}=\prod_{p=1}^{M}Q_{i_{p}j_{p}}(m_{p},n_{p})$ for all
$\bm{i}=(i_{1},\dots,i_{M})\leq\bm{m}$ and
$\bm{j}=(j_{1},\dots,j_{M})\leq\bm{m}$. Hence, for all
$\bm{r}=(r_{1},\dots,r_{M})\leq 2\bm{m}$,

$\displaystyle\sum_{\bm{i}+\bm{j}=\bm{r}}Q_{\bm{i}\bm{j}}$
$\displaystyle=\sum_{i_{1}+j_{1}=r_{1},\dots,i_{M}+j_{M}=r_{M}}\prod_{p=1}^{M}Q_{i_{p}j_{p}}(m_{p},n_{p})$
(181)
$\displaystyle=\prod_{p=1}^{M}\sum_{i_{p}+j_{p}=r_{p}}Q_{i_{p}j_{p}}(m_{p},n_{p}).$

In particular, if $\bm{r}\neq 2\bm{l}$ for all $\bm{l}\leq\bm{m}$, then at
least one coefficient $r_{p}$ is odd, and the corresponding sum gives $0$
since $(Q(m_{p},n_{p}),\bm{F}(m_{p},n_{p}))$ is feasible for
$(\text{SDP}_{n_{p}}^{m_{p},\leq})$. In that case,
$\sum_{\bm{i}+\bm{j}=\bm{r}}Q_{\bm{i}\bm{j}}=0$. Otherwise, for all
$\bm{l}=(l_{1},\dots,l_{M})\leq\bm{m}$,

$\displaystyle\sum_{\bm{i}+\bm{j}=2\bm{l}}Q_{\bm{i}\bm{j}}$
$\displaystyle=\prod_{p=1}^{M}\sum_{i_{p}+j_{p}=2l_{p}}Q_{i_{p}j_{p}}(m_{p},n_{p})$
(182) $\displaystyle=\prod_{p=1}^{M}\sum_{k_{p}\geq
l_{p}}\frac{(-1)^{k_{p}+l_{p}}}{l_{p}!}\binom{k_{p}}{l_{p}}F_{k_{p}}(m_{p},n_{p})$
$\displaystyle=\sum_{l_{1}\leq k_{1}\leq m_{1},\dots,l_{M}\leq k_{M}\leq
m_{M}}\prod_{p=1}^{M}\frac{(-1)^{k_{p}+l_{p}}}{l_{p}!}\binom{k_{p}}{l_{p}}F_{k_{p}}(m_{p},n_{p})$
$\displaystyle=\sum_{\bm{k}\geq\bm{l}}\frac{(-1)^{|\bm{k}|+|\bm{l}|}}{\bm{l}!}\binom{\bm{k}}{\bm{l}}F_{\bm{k}},$

where we used the feasibility of $(Q(m_{p},n_{p}),\bm{F}(m_{p},n_{p}))$ in the
second line. Finally,

$\displaystyle\sum_{\bm{k}\leq\bm{m}}F_{\bm{k}}$
$\displaystyle=\sum_{k_{1}\leq m_{1},\dots,k_{M}\leq
m_{M}}\prod_{i=1}^{M}F_{k_{i}}(m_{i},n_{i})$ (183)
$\displaystyle=\prod_{i=1}^{M}\sum_{k_{i}=0}^{m_{i}}F_{k_{i}}(m_{i},n_{i})$
$\displaystyle=1,$

since $\sum_{k=0}^{m}F_{k}(m,n)=1$ for all $m,n\in\mathbb{N}$ with $m\geq n$.
This shows that $(Q,\bm{F})$ is a feasible solution of
(SDP${}_{\bm{n}}^{\bm{m},\leq}$) (resp. strictly feasible). ∎

A direct consequence of this construction is the following result:

######  Theorem 10 (Generalisation of Theorem 2).

Strong duality holds between the programs (SDP${}_{\bm{n}}^{\bm{m},\leq}$) and
$(\text{D-SDP}^{\bm{m},\leq}_{\bm{n}})$.

###### Proof.

The proof of Theorem 2 gives a strictly feasible solution
$(Q(m,n),\bm{F}(m,n))$ of $(\text{SDP}^{m,\leq}_{n})$ for all $m\geq n$. By
Lemma 18, the program (SDP${}_{\bm{n}}^{\bm{m},\leq}$) thus has a strictly
feasible solution, for all $\bm{m}\geq\bm{n}$. By Slater condition, this
implies that strong duality holds between the programs
(SDP${}_{\bm{n}}^{\bm{m},\leq}$) and $(\text{D-SDP}^{\bm{m},\leq}_{\bm{n}})$.
∎

In particular, strong duality holds between the programs
(SDP${}_{\bm{n}}^{m\bm{1},\leq}$) and
$(\text{D-SDP}^{m\bm{1},\leq}_{\bm{n}})$. Note that the multimode
generalisation of Theorem 3 is a direct consequence of Theorem 10:

######  Theorem 11 (Generalisation of Theorem 3).

Strong duality holds between the programs
$(\text{SDP}^{\bm{m},\geq}_{\bm{n}})$ and (D-SDP${}_{\bm{n}}^{\bm{m},\geq}$).

###### Proof.

the strictly feasible solution of (SDP${}_{\bm{n}}^{\bm{m},\leq}$) derived in
the proof of Theorem 10 yields a strictly feasible solution for
$(\text{SDP}^{\bm{m},\geq}_{\bm{n}})$. With Slater condition, this shows again
that strong duality holds between the programs
$(\text{SDP}^{\bm{m},\geq}_{\bm{n}})$ and (D-SDP${}_{\bm{n}}^{\bm{m},\geq}$).
∎

In particular, strong duality holds between the programs
$(\text{SDP}^{m\bm{1},\geq}_{\bm{n}})$ and
(D-SDP${}_{\bm{n}}^{m\bm{1},\geq}$).

We recall the following definition from the main text: for all
$n\in\mathbb{N}$,
$\bm{F}^{n}=(F_{k}^{n})_{k\in\mathbb{N}}\in\mathbb{R}^{\mathbb{N}}$ where
$\bullet$ if $n$ is even:

$F_{k}^{n}:=\begin{cases}\frac{1}{2^{n}}\binom{k}{\frac{k}{2}}\binom{n-k}{\frac{n-k}{2}}&\text{when
}k\leq n,k\text{ even},\\\ 0&\text{otherwise},\end{cases}$ (184)

$\bullet$ if $n$ is odd:

$F_{k}^{n}:=\begin{cases}\frac{1}{2^{n}}\frac{\binom{n}{\lfloor\frac{n}{2}\rfloor}\binom{\lfloor\frac{n}{2}\rfloor}{\lfloor\frac{k}{2}\rfloor}^{2}}{\binom{n}{k}},&\text{when
}k\leq n,\\\ 0&\text{otherwise}.\end{cases}$ (185)

Let us define, for all $\bm{n}=(n_{1},\dots,n_{M})\in\mathbb{N}^{m}$,
$\bm{F}^{\bm{n}}=(F_{\bm{k}}^{\bm{n}})_{k\in\mathbb{N}^{M}}\in\mathbb{R}^{\mathbb{N}^{M}}$
where

$F_{\bm{k}}^{\bm{n}}:=\begin{cases}\prod_{i=1}^{M}F_{k_{i}}^{n_{i}}&\text{when
}\bm{k}\leq\bm{n},\\\ 0&\text{otherwise.}\end{cases}$ (186)

By (60), for all $n\in\mathbb{N}$, $F_{n}^{n}\geq\frac{1}{n+1}$, so for all
$\bm{n}=(n_{1},\dots,n_{M})\in\mathbb{N}^{M}$,

$F_{\bm{n}}^{\bm{n}}\geq\frac{1}{\pi_{\bm{n}}}.$ (187)

Like in the single-mode case, the program (SDP${}_{\bm{n}}^{\bm{m},\leq}$) is
equivalent to

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{\bm{F}\in\mathbb{R}^{\pi_{\bm{m}}}}{\text{sup}}F_{\bm{n}}\\\
&\text{subject to}&&\sum_{\bm{k}\leq\bm{m}}F_{\bm{k}}=1\\\
&\text{and}&&\forall\bm{k}\leq\bm{m},\quad F_{\bm{k}}\geq 0\\\
&\text{and}&&\sum_{\bm{k}\leq\bm{m}}F_{\bm{k}}\mathcal{L}_{\bm{k}}\in\mathcal{R}_{\bm{m},+}(\mathbb{R}_{+}^{M}),\end{aligned}\right.$
(SDP${}_{\bm{n}}^{\bm{m},\leq}$)

with the dual program given by

$\displaystyle\hskip 79.6678pt\left\\{\begin{aligned}
&&&\underset{y,\bm{\mu}\in\mathbb{R}\times\mathbb{R}^{\pi_{\bm{m}}}}{\text{inf}}y\\\
&\text{subject to}&&y\geq 1+\mu_{\bm{n}}\\\
&\text{and}&&\forall\bm{k}\leq\bm{m},\bm{k}\neq\bm{n},\quad
y\geq\mu_{\bm{k}}\\\ &\text{and}&&\forall
g\in\mathcal{R}_{\bm{m},+}(\mathbb{R}_{+}^{M}),\left\langle\sum_{\bm{k}\leq\bm{m}}\mu_{\bm{k}}\mathcal{L}_{\bm{k}},g\right\rangle\geq
0,\end{aligned}\right.$ $(\text{D-SDP}^{\bm{m},\leq}_{\bm{n}})$

for all $\bm{m}\geq\bm{n}$. Moreover, adding the condition $\mu_{\bm{k}}\leq
1$ for all $\bm{k}\leq\bm{m}$ does not change the optimal value of the
program. We enforce this condition in what follows. With Lemma 7 and Lemma 18,
we thus obtain the following result:

######  Lemma 19 (Generalisation of Lemma 7).

For all $\bm{m}\geq\bm{n}$, $\bm{F}^{\bm{m}}$ (defined in Eq. (186)) is a
feasible solution of (SDP${}_{\bm{n}}^{\bm{m},\leq}$).

In particular, for all $\bm{m}\in\mathbb{N}^{M}$,
$\sum_{\bm{k}\leq\bm{m}}F_{\bm{k}}^{\bm{m}}\mathcal{L}_{\bm{k}}\in\mathcal{R}_{\bm{m},+}(\mathbb{R}_{+}^{M})$.
For $\bm{m},\bm{n}\in\mathbb{N}^{M}$ with $\bm{m}\geq\bm{n}$, let
$\bm{\mu}\in\mathbb{R}^{\pi_{\bm{m}}}$ be a feasible solution of
$(\text{D-SDP}^{\bm{m},\leq}_{\bm{n}})$. Then, for all $\bm{l}\leq\bm{m}$

$\left\langle\sum_{\bm{k}\leq\bm{m}}\mu_{\bm{k}}\mathcal{L}_{\bm{k}},\sum_{\bm{k}\leq\bm{l}}F_{\bm{k}}^{\bm{l}}\mathcal{L}_{\bm{k}}\right\rangle\geq
0,$ (188)

so that

$\sum_{\bm{k}\leq\bm{l}}\mu_{\bm{k}}F_{\bm{k}}^{\bm{l}}\geq 0.$ (189)

Hence, for all $\bm{l}\geq\bm{m}$,

$\displaystyle\mu_{\bm{l}}$
$\displaystyle\geq-\frac{1}{F_{\bm{l}}^{\bm{l}}}\sum_{\begin{subarray}{c}\bm{k}\leq\bm{l}\\\
\bm{k}\neq\bm{l}\end{subarray}}\mu_{\bm{k}}F_{\bm{k}}^{\bm{l}}$ (190)
$\displaystyle\geq-\frac{1}{F_{\bm{l}}^{\bm{l}}}\sum_{\begin{subarray}{c}\bm{k}\leq\bm{l}\\\
\bm{k}\neq\bm{l}\end{subarray}}F_{\bm{k}}^{\bm{l}}$
$\displaystyle=1-\frac{1}{F_{\bm{l}}^{\bm{l}}}$ $\displaystyle\geq
1-\pi_{\bm{l}},$

where we used $F_{\bm{l}}^{\bm{l}}>0$ in the first line, $\mu_{\bm{k}}\leq 1$
and $F_{\bm{k}}^{\bm{l}}\geq 0$ in the second line,
$\sum_{\bm{k}\leq\bm{l}}F_{\bm{k}}^{\bm{l}}=1$ in the third line, and Eq.
(187) in the last line.

With these additional results, the proof of convergence of the multimode
hierarchy of lower bounds (SDP${}_{\bm{n}}^{m\bm{1},\leq}$) is then obtained
directly from its single-mode counterpart using multi-index notations:

######  Theorem 12 (Generalisation of Theorem 5).

The increasing sequence of optimal values $\omega^{m\bm{1},\leq}_{\bm{n}}$ of
(SDP${}_{\bm{n}}^{m\bm{1},\leq}$) converges to the optimal value
$\omega_{\bm{n}}^{\mathcal{S}}$ of (LP${}_{n}^{\mathcal{S}}$):

$\lim_{m\rightarrow+\infty}\omega^{m\bm{1},\leq}_{\bm{n}}=\omega_{\bm{n}}^{\mathcal{S}}.$
(191)

With Lemma 17, we also obtain

$\lim_{m\rightarrow+\infty}\omega^{m,\leq}_{\bm{n}}=\omega_{\bm{n}}^{\mathcal{S}}.$
(192)

Like in the single-mode case, Theorem 9 and Theorem 12 imply strong duality
between the linear programs:

######  Theorem 13 (Generalisation of Theorem 6).

Strong duality holds between the programs (LP${}_{\bm{n}}^{L^{2}}$) and
(D-LP${}_{\bm{n}}^{L^{2}}$) and between programs
(LP${}_{\bm{n}}^{\mathcal{S}}$) and (D-LP${}_{\bm{n}}^{\mathcal{S}}$).

##  Appendix I Bounds on threshold values of several witness for $n=3$

Below, we provide tables of numerical upper bounds and lower bounds obtained
on the threshold values for witnesses of the form:

$\hat{\Omega}_{(a_{1},a_{2},a_{3})}=a_{1}\ket{1}\\!\bra{1}+a_{2}\ket{2}\\!\bra{2}+a_{3}\ket{3}\\!\bra{3}$
(193)

where $\forall i\in\\{1,2,3\\},\,0\leq a_{i}\leq 1$ and $\max_{i}a_{i}=1$. We
focused on these particular witnesses for experimental considerations as it is
challenging to obtain fidelities with higher Fock states. We vary each $a_{i}$
from $0$ to $1$ with a step of $0.1$.

$a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
1.0 | 0.0 | 0.0 | 0.500 | 0.529 | 1.0 | 0.3 | 0.8 | 0.589 | 0.590 | 1.0 | 0.7 | 0.5 | 0.705 | 0.715
1.0 | 0.0 | 0.1 | 0.500 | 0.529 | 1.0 | 0.3 | 0.9 | 0.606 | 0.610 | 1.0 | 0.7 | 0.6 | 0.718 | 0.720
1.0 | 0.0 | 0.2 | 0.500 | 0.529 | 1.0 | 0.3 | 1.0 | 0.626 | 0.633 | 1.0 | 0.7 | 0.7 | 0.735 | 0.738
1.0 | 0.0 | 0.3 | 0.500 | 0.529 | 1.0 | 0.4 | 0.0 | 0.610 | 0.615 | 1.0 | 0.7 | 0.8 | 0.754 | 0.758
1.0 | 0.0 | 0.4 | 0.500 | 0.529 | 1.0 | 0.4 | 0.1 | 0.610 | 0.615 | 1.0 | 0.7 | 0.9 | 0.774 | 0.781
1.0 | 0.0 | 0.5 | 0.500 | 0.528 | 1.0 | 0.4 | 0.2 | 0.610 | 0.615 | 1.0 | 0.7 | 1.0 | 0.795 | 0.805
1.0 | 0.0 | 0.6 | 0.500 | 0.529 | 1.0 | 0.4 | 0.3 | 0.610 | 0.615 | 1.0 | 0.8 | 0.0 | 0.739 | 0.751
1.0 | 0.0 | 0.7 | 0.500 | 0.529 | 1.0 | 0.4 | 0.4 | 0.610 | 0.615 | 1.0 | 0.8 | 0.1 | 0.739 | 0.751
1.0 | 0.0 | 0.8 | 0.500 | 0.529 | 1.0 | 0.4 | 0.5 | 0.610 | 0.615 | 1.0 | 0.8 | 0.2 | 0.739 | 0.751
1.0 | 0.0 | 0.9 | 0.500 | 0.530 | 1.0 | 0.4 | 0.6 | 0.610 | 0.615 | 1.0 | 0.8 | 0.3 | 0.739 | 0.751
1.0 | 0.0 | 1.0 | 0.500 | 0.563 | 1.0 | 0.4 | 0.7 | 0.614 | 0.615 | 1.0 | 0.8 | 0.4 | 0.739 | 0.751
1.0 | 0.1 | 0.0 | 0.526 | 0.529 | 1.0 | 0.4 | 0.8 | 0.629 | 0.631 | 1.0 | 0.8 | 0.5 | 0.742 | 0.751
1.0 | 0.1 | 0.1 | 0.526 | 0.529 | 1.0 | 0.4 | 0.9 | 0.648 | 0.653 | 1.0 | 0.8 | 0.6 | 0.759 | 0.761
1.0 | 0.1 | 0.2 | 0.526 | 0.529 | 1.0 | 0.4 | 1.0 | 0.669 | 0.677 | 1.0 | 0.8 | 0.7 | 0.777 | 0.780
1.0 | 0.1 | 0.3 | 0.526 | 0.529 | 1.0 | 0.5 | 0.0 | 0.640 | 0.649 | 1.0 | 0.8 | 0.8 | 0.796 | 0.801
1.0 | 0.1 | 0.4 | 0.526 | 0.529 | 1.0 | 0.5 | 0.1 | 0.640 | 0.649 | 1.0 | 0.8 | 0.9 | 0.816 | 0.824
1.0 | 0.1 | 0.5 | 0.526 | 0.529 | 1.0 | 0.5 | 0.2 | 0.640 | 0.649 | 1.0 | 0.8 | 1.0 | 0.837 | 0.848
1.0 | 0.1 | 0.6 | 0.526 | 0.529 | 1.0 | 0.5 | 0.3 | 0.640 | 0.649 | 1.0 | 0.9 | 0.0 | 0.773 | 0.790
1.0 | 0.1 | 0.7 | 0.526 | 0.529 | 1.0 | 0.5 | 0.4 | 0.640 | 0.649 | 1.0 | 0.9 | 0.1 | 0.773 | 0.790
1.0 | 0.1 | 0.8 | 0.526 | 0.529 | 1.0 | 0.5 | 0.5 | 0.640 | 0.649 | 1.0 | 0.9 | 0.2 | 0.773 | 0.790
1.0 | 0.1 | 0.9 | 0.526 | 0.528 | 1.0 | 0.5 | 0.6 | 0.640 | 0.649 | 1.0 | 0.9 | 0.3 | 0.773 | 0.790
1.0 | 0.1 | 1.0 | 0.542 | 0.563 | 1.0 | 0.5 | 0.7 | 0.654 | 0.655 | 1.0 | 0.9 | 0.4 | 0.773 | 0.790
1.0 | 0.2 | 0.0 | 0.552 | 0.555 | 1.0 | 0.5 | 0.8 | 0.671 | 0.673 | 1.0 | 0.9 | 0.5 | 0.783 | 0.790
1.0 | 0.2 | 0.1 | 0.552 | 0.555 | 1.0 | 0.5 | 0.9 | 0.690 | 0.696 | 1.0 | 0.9 | 0.6 | 0.800 | 0.803
1.0 | 0.2 | 0.2 | 0.552 | 0.555 | 1.0 | 0.5 | 1.0 | 0.711 | 0.719 | 1.0 | 0.9 | 0.7 | 0.818 | 0.822
1.0 | 0.2 | 0.3 | 0.552 | 0.555 | 1.0 | 0.6 | 0.0 | 0.672 | 0.682 | 1.0 | 0.9 | 0.8 | 0.838 | 0.844
1.0 | 0.2 | 0.4 | 0.552 | 0.555 | 1.0 | 0.6 | 0.1 | 0.672 | 0.682 | 1.0 | 0.9 | 0.9 | 0.858 | 0.867
1.0 | 0.2 | 0.5 | 0.552 | 0.555 | 1.0 | 0.6 | 0.2 | 0.672 | 0.682 | 1.0 | 0.9 | 1.0 | 0.879 | 0.891
1.0 | 0.2 | 0.6 | 0.552 | 0.555 | 1.0 | 0.6 | 0.3 | 0.672 | 0.683 | 1.0 | 1.0 | 0.0 | 0.809 | 0.830
1.0 | 0.2 | 0.7 | 0.552 | 0.555 | 1.0 | 0.6 | 0.4 | 0.672 | 0.682 | 1.0 | 1.0 | 0.1 | 0.809 | 0.830
1.0 | 0.2 | 0.8 | 0.552 | 0.555 | 1.0 | 0.6 | 0.5 | 0.672 | 0.682 | 1.0 | 1.0 | 0.2 | 0.809 | 0.830
1.0 | 0.2 | 0.9 | 0.565 | 0.567 | 1.0 | 0.6 | 0.6 | 0.678 | 0.682 | 1.0 | 1.0 | 0.3 | 0.809 | 0.830
1.0 | 0.2 | 1.0 | 0.584 | 0.594 | 1.0 | 0.6 | 0.7 | 0.694 | 0.696 | 1.0 | 1.0 | 0.4 | 0.809 | 0.830
1.0 | 0.3 | 0.0 | 0.581 | 0.585 | 1.0 | 0.6 | 0.8 | 0.712 | 0.716 | 1.0 | 1.0 | 0.5 | 0.824 | 0.830
1.0 | 0.3 | 0.1 | 0.581 | 0.585 | 1.0 | 0.6 | 0.9 | 0.732 | 0.739 | 1.0 | 1.0 | 0.6 | 0.841 | 0.845
1.0 | 0.3 | 0.2 | 0.581 | 0.584 | 1.0 | 0.6 | 1.0 | 0.753 | 0.762 | 1.0 | 1.0 | 0.7 | 0.860 | 0.865
1.0 | 0.3 | 0.3 | 0.581 | 0.584 | 1.0 | 0.7 | 0.0 | 0.705 | 0.716 | 1.0 | 1.0 | 0.8 | 0.879 | 0.887
1.0 | 0.3 | 0.4 | 0.581 | 0.584 | 1.0 | 0.7 | 0.1 | 0.705 | 0.715 | 1.0 | 1.0 | 0.9 | 0.900 | 0.910
1.0 | 0.3 | 0.5 | 0.581 | 0.584 | 1.0 | 0.7 | 0.2 | 0.705 | 0.715 | 1.0 | 1.0 | 1.0 | 0.922 | 0.934
1.0 | 0.3 | 0.6 | 0.581 | 0.584 | 1.0 | 0.7 | 0.3 | 0.705 | 0.715 |  |  |  |  |
1.0 | 0.3 | 0.7 | 0.581 | 0.584 | 1.0 | 0.7 | 0.4 | 0.705 | 0.715 |  |  |  |  |
Table 2: Upper and lower bounds on the threshold values of witnesses of the form $\hat{\Omega}_{(1,a_{2},a_{3})}$. $a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0.0 | 1.0 | 0.0 | 0.500 | 0.546 | 0.3 | 1.0 | 0.4 | 0.594 | 0.603 | 0.6 | 1.0 | 0.8 | 0.767 | 0.779
0.0 | 1.0 | 0.1 | 0.500 | 0.551 | 0.3 | 1.0 | 0.5 | 0.617 | 0.629 | 0.6 | 1.0 | 0.9 | 0.792 | 0.806
0.0 | 1.0 | 0.2 | 0.500 | 0.546 | 0.3 | 1.0 | 0.6 | 0.642 | 0.655 | 0.6 | 1.0 | 1.0 | 0.817 | 0.849
0.0 | 1.0 | 0.3 | 0.500 | 0.546 | 0.3 | 1.0 | 0.7 | 0.667 | 0.683 | 0.7 | 1.0 | 0.0 | 0.680 | 0.701
0.0 | 1.0 | 0.4 | 0.517 | 0.546 | 0.3 | 1.0 | 0.8 | 0.693 | 0.712 | 0.7 | 1.0 | 0.1 | 0.680 | 0.702
0.0 | 1.0 | 0.5 | 0.543 | 0.559 | 0.3 | 1.0 | 0.9 | 0.719 | 0.741 | 0.7 | 1.0 | 0.2 | 0.680 | 0.702
0.0 | 1.0 | 0.6 | 0.569 | 0.588 | 0.3 | 1.0 | 1.0 | 0.747 | 0.789 | 0.7 | 1.0 | 0.3 | 0.691 | 0.702
0.0 | 1.0 | 0.7 | 0.597 | 0.618 | 0.4 | 1.0 | 0.0 | 0.570 | 0.603 | 0.7 | 1.0 | 0.4 | 0.710 | 0.714
0.0 | 1.0 | 0.8 | 0.625 | 0.650 | 0.4 | 1.0 | 0.1 | 0.570 | 0.600 | 0.7 | 1.0 | 0.5 | 0.729 | 0.735
0.0 | 1.0 | 0.9 | 0.654 | 0.682 | 0.4 | 1.0 | 0.2 | 0.579 | 0.603 | 0.7 | 1.0 | 0.6 | 0.750 | 0.759
0.0 | 1.0 | 1.0 | 0.683 | 0.740 | 0.4 | 1.0 | 0.3 | 0.600 | 0.607 | 0.7 | 1.0 | 0.7 | 0.772 | 0.782
0.1 | 1.0 | 0.0 | 0.505 | 0.551 | 0.4 | 1.0 | 0.4 | 0.622 | 0.631 | 0.7 | 1.0 | 0.8 | 0.794 | 0.806
0.1 | 1.0 | 0.1 | 0.505 | 0.551 | 0.4 | 1.0 | 0.5 | 0.644 | 0.653 | 0.7 | 1.0 | 0.9 | 0.817 | 0.830
0.1 | 1.0 | 0.2 | 0.505 | 0.551 | 0.4 | 1.0 | 0.6 | 0.667 | 0.679 | 0.7 | 1.0 | 1.0 | 0.842 | 0.870
0.1 | 1.0 | 0.3 | 0.517 | 0.551 | 0.4 | 1.0 | 0.7 | 0.692 | 0.705 | 0.8 | 1.0 | 0.0 | 0.722 | 0.744
0.1 | 1.0 | 0.4 | 0.542 | 0.556 | 0.4 | 1.0 | 0.8 | 0.717 | 0.733 | 0.8 | 1.0 | 0.1 | 0.722 | 0.744
0.1 | 1.0 | 0.5 | 0.567 | 0.583 | 0.4 | 1.0 | 0.9 | 0.743 | 0.763 | 0.8 | 1.0 | 0.2 | 0.722 | 0.744
0.1 | 1.0 | 0.6 | 0.593 | 0.610 | 0.4 | 1.0 | 1.0 | 0.769 | 0.813 | 0.8 | 1.0 | 0.3 | 0.724 | 0.744
0.1 | 1.0 | 0.7 | 0.619 | 0.641 | 0.5 | 1.0 | 0.0 | 0.604 | 0.632 | 0.8 | 1.0 | 0.4 | 0.741 | 0.745
0.1 | 1.0 | 0.8 | 0.647 | 0.671 | 0.5 | 1.0 | 0.1 | 0.604 | 0.638 | 0.8 | 1.0 | 0.5 | 0.760 | 0.764
0.1 | 1.0 | 0.9 | 0.675 | 0.701 | 0.5 | 1.0 | 0.2 | 0.610 | 0.632 | 0.8 | 1.0 | 0.6 | 0.779 | 0.786
0.1 | 1.0 | 1.0 | 0.704 | 0.750 | 0.5 | 1.0 | 0.3 | 0.629 | 0.635 | 0.8 | 1.0 | 0.7 | 0.800 | 0.809
0.2 | 1.0 | 0.0 | 0.519 | 0.556 | 0.5 | 1.0 | 0.4 | 0.650 | 0.658 | 0.8 | 1.0 | 0.8 | 0.822 | 0.832
0.2 | 1.0 | 0.1 | 0.519 | 0.556 | 0.5 | 1.0 | 0.5 | 0.672 | 0.681 | 0.8 | 1.0 | 0.9 | 0.844 | 0.857
0.2 | 1.0 | 0.2 | 0.522 | 0.556 | 0.5 | 1.0 | 0.6 | 0.694 | 0.705 | 0.8 | 1.0 | 1.0 | 0.867 | 0.891
0.2 | 1.0 | 0.3 | 0.544 | 0.556 | 0.5 | 1.0 | 0.7 | 0.717 | 0.729 | 0.9 | 1.0 | 0.0 | 0.765 | 0.787
0.2 | 1.0 | 0.4 | 0.567 | 0.578 | 0.5 | 1.0 | 0.8 | 0.742 | 0.756 | 0.9 | 1.0 | 0.1 | 0.765 | 0.787
0.2 | 1.0 | 0.5 | 0.592 | 0.605 | 0.5 | 1.0 | 0.9 | 0.767 | 0.784 | 0.9 | 1.0 | 0.2 | 0.765 | 0.787
0.2 | 1.0 | 0.6 | 0.617 | 0.633 | 0.5 | 1.0 | 1.0 | 0.793 | 0.831 | 0.9 | 1.0 | 0.3 | 0.765 | 0.787
0.2 | 1.0 | 0.7 | 0.643 | 0.660 | 0.6 | 1.0 | 0.0 | 0.641 | 0.665 | 0.9 | 1.0 | 0.4 | 0.774 | 0.787
0.2 | 1.0 | 0.8 | 0.669 | 0.690 | 0.6 | 1.0 | 0.1 | 0.641 | 0.665 | 0.9 | 1.0 | 0.5 | 0.791 | 0.795
0.2 | 1.0 | 0.9 | 0.697 | 0.722 | 0.6 | 1.0 | 0.2 | 0.641 | 0.665 | 0.9 | 1.0 | 0.6 | 0.810 | 0.815
0.2 | 1.0 | 1.0 | 0.725 | 0.770 | 0.6 | 1.0 | 0.3 | 0.660 | 0.665 | 0.9 | 1.0 | 0.7 | 0.829 | 0.836
0.3 | 1.0 | 0.0 | 0.542 | 0.575 | 0.6 | 1.0 | 0.4 | 0.679 | 0.685 | 0.9 | 1.0 | 0.8 | 0.850 | 0.860
0.3 | 1.0 | 0.1 | 0.542 | 0.575 | 0.6 | 1.0 | 0.5 | 0.700 | 0.708 | 0.9 | 1.0 | 0.9 | 0.872 | 0.883
0.3 | 1.0 | 0.2 | 0.550 | 0.575 | 0.6 | 1.0 | 0.6 | 0.722 | 0.732 | 0.9 | 1.0 | 1.0 | 0.894 | 0.913
0.3 | 1.0 | 0.3 | 0.572 | 0.580 | 0.6 | 1.0 | 0.7 | 0.744 | 0.756 |  |  |  |  |
Table 3: Upper and lower bounds on the threshold values of witnesses of the form $\hat{\Omega}_{(a_{1},1,a_{3})}$. $a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$ | $a_{1}$ | $a_{2}$ | $a_{3}$ | $\omega_{\bm{a}}^{\leq}$ | $\omega_{\bm{a}}^{\geq}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
0.0 | 0.0 | 1.0 | 0.377 | 0.428 | 0.3 | 0.4 | 1.0 | 0.529 | 0.547 | 0.6 | 0.8 | 1.0 | 0.734 | 0.752
0.0 | 0.1 | 1.0 | 0.401 | 0.437 | 0.3 | 0.5 | 1.0 | 0.561 | 0.583 | 0.6 | 0.9 | 1.0 | 0.775 | 0.793
0.0 | 0.2 | 1.0 | 0.429 | 0.452 | 0.3 | 0.6 | 1.0 | 0.594 | 0.621 | 0.7 | 0.0 | 1.0 | 0.463 | 0.521
0.0 | 0.3 | 1.0 | 0.458 | 0.474 | 0.3 | 0.7 | 1.0 | 0.628 | 0.657 | 0.7 | 0.1 | 1.0 | 0.490 | 0.522
0.0 | 0.4 | 1.0 | 0.488 | 0.510 | 0.3 | 0.8 | 1.0 | 0.667 | 0.694 | 0.7 | 0.2 | 1.0 | 0.521 | 0.542
0.0 | 0.5 | 1.0 | 0.519 | 0.533 | 0.3 | 0.9 | 1.0 | 0.707 | 0.733 | 0.7 | 0.3 | 1.0 | 0.555 | 0.580
0.0 | 0.6 | 1.0 | 0.550 | 0.572 | 0.4 | 0.0 | 1.0 | 0.426 | 0.480 | 0.7 | 0.4 | 1.0 | 0.594 | 0.615
0.0 | 0.7 | 1.0 | 0.583 | 0.605 | 0.4 | 0.1 | 1.0 | 0.451 | 0.485 | 0.7 | 0.5 | 1.0 | 0.635 | 0.653
0.0 | 0.8 | 1.0 | 0.616 | 0.642 | 0.4 | 0.2 | 1.0 | 0.480 | 0.501 | 0.7 | 0.6 | 1.0 | 0.676 | 0.692
0.0 | 0.9 | 1.0 | 0.649 | 0.678 | 0.4 | 0.3 | 1.0 | 0.511 | 0.528 | 0.7 | 0.7 | 1.0 | 0.717 | 0.733
0.1 | 0.0 | 1.0 | 0.390 | 0.440 | 0.4 | 0.4 | 1.0 | 0.543 | 0.567 | 0.7 | 0.8 | 1.0 | 0.758 | 0.774
0.1 | 0.1 | 1.0 | 0.414 | 0.448 | 0.4 | 0.5 | 1.0 | 0.576 | 0.602 | 0.7 | 0.9 | 1.0 | 0.800 | 0.815
0.1 | 0.2 | 1.0 | 0.441 | 0.464 | 0.4 | 0.6 | 1.0 | 0.610 | 0.637 | 0.8 | 0.0 | 1.0 | 0.475 | 0.535
0.1 | 0.3 | 1.0 | 0.471 | 0.486 | 0.4 | 0.7 | 1.0 | 0.649 | 0.674 | 0.8 | 0.1 | 1.0 | 0.504 | 0.535
0.1 | 0.4 | 1.0 | 0.501 | 0.519 | 0.4 | 0.8 | 1.0 | 0.689 | 0.713 | 0.8 | 0.2 | 1.0 | 0.537 | 0.562
0.1 | 0.5 | 1.0 | 0.532 | 0.549 | 0.4 | 0.9 | 1.0 | 0.729 | 0.752 | 0.8 | 0.3 | 1.0 | 0.576 | 0.597
0.1 | 0.6 | 1.0 | 0.565 | 0.588 | 0.5 | 0.0 | 1.0 | 0.439 | 0.494 | 0.8 | 0.4 | 1.0 | 0.617 | 0.633
0.1 | 0.7 | 1.0 | 0.597 | 0.623 | 0.5 | 0.1 | 1.0 | 0.464 | 0.497 | 0.8 | 0.5 | 1.0 | 0.658 | 0.672
0.1 | 0.8 | 1.0 | 0.631 | 0.659 | 0.5 | 0.2 | 1.0 | 0.494 | 0.513 | 0.8 | 0.6 | 1.0 | 0.700 | 0.713
0.1 | 0.9 | 1.0 | 0.665 | 0.696 | 0.5 | 0.3 | 1.0 | 0.525 | 0.544 | 0.8 | 0.7 | 1.0 | 0.742 | 0.754
0.2 | 0.0 | 1.0 | 0.402 | 0.453 | 0.5 | 0.4 | 1.0 | 0.558 | 0.583 | 0.8 | 0.8 | 1.0 | 0.784 | 0.808
0.2 | 0.1 | 1.0 | 0.426 | 0.460 | 0.5 | 0.5 | 1.0 | 0.592 | 0.617 | 0.8 | 0.9 | 1.0 | 0.825 | 0.849
0.2 | 0.2 | 1.0 | 0.454 | 0.476 | 0.5 | 0.6 | 1.0 | 0.631 | 0.655 | 0.9 | 0.0 | 1.0 | 0.488 | 0.549
0.2 | 0.3 | 1.0 | 0.484 | 0.499 | 0.5 | 0.7 | 1.0 | 0.671 | 0.693 | 0.9 | 0.1 | 1.0 | 0.518 | 0.549
0.2 | 0.4 | 1.0 | 0.515 | 0.530 | 0.5 | 0.8 | 1.0 | 0.711 | 0.732 | 0.9 | 0.2 | 1.0 | 0.559 | 0.578
0.2 | 0.5 | 1.0 | 0.547 | 0.570 | 0.5 | 0.9 | 1.0 | 0.752 | 0.773 | 0.9 | 0.3 | 1.0 | 0.600 | 0.613
0.2 | 0.6 | 1.0 | 0.579 | 0.604 | 0.6 | 0.0 | 1.0 | 0.451 | 0.506 | 0.9 | 0.4 | 1.0 | 0.642 | 0.652
0.2 | 0.7 | 1.0 | 0.613 | 0.640 | 0.6 | 0.1 | 1.0 | 0.477 | 0.509 | 0.9 | 0.5 | 1.0 | 0.684 | 0.693
0.2 | 0.8 | 1.0 | 0.646 | 0.676 | 0.6 | 0.2 | 1.0 | 0.507 | 0.527 | 0.9 | 0.6 | 1.0 | 0.726 | 0.736
0.2 | 0.9 | 1.0 | 0.685 | 0.714 | 0.6 | 0.3 | 1.0 | 0.540 | 0.564 | 0.9 | 0.7 | 1.0 | 0.768 | 0.779
0.3 | 0.0 | 1.0 | 0.414 | 0.466 | 0.6 | 0.4 | 1.0 | 0.573 | 0.598 | 0.9 | 0.8 | 1.0 | 0.810 | 0.821
0.3 | 0.1 | 1.0 | 0.439 | 0.505 | 0.6 | 0.5 | 1.0 | 0.613 | 0.635 | 0.9 | 0.9 | 1.0 | 0.852 | 0.866
0.3 | 0.2 | 1.0 | 0.467 | 0.488 | 0.6 | 0.6 | 1.0 | 0.653 | 0.673 |  |  |  |  |
0.3 | 0.3 | 1.0 | 0.497 | 0.513 | 0.6 | 0.7 | 1.0 | 0.693 | 0.712 |  |  |  |  |
Table 4: Upper and lower bounds on the threshold values of witnesses of the
form $\hat{\Omega}_{(a_{1},a_{2},1)}$.