From Lasserre maps to pseudo-distributions

Question

Let me define a ``Lasserre map of degree $d$" as a linear map $L : \mathbb{R}_n[x] \rightarrow \mathbb{R}$ i.e a real valued linear map on polynomials over $n$ variables with real coeffients. This is further expected to satisfy, $(1)$ $L(1) =1$ and $(2)$ as $L(P^2) \geq 0$ if $deg(P) \leq \frac{d}{2}$.

On the otherhand a "pseudo-distribution of degree $d$" is defined as a map $D : \{\pm 1\}^n \rightarrow \mathbb{R}$ such that $(1)$ $\sum_{x \in \{\pm 1\}^n } D(x) =1$ and $(2)$ $\sum_{x \in \{\pm 1\}^n } D(x) f(x) \geq 0 $ if $f$ can be written as a sum of squares of polynomials each of degree $\leq \frac{d}{2}$ i.e if $f \in SOS_{\leq d}$ (the cone of sum-of-squares of polynomials of degree at most $\frac{d}{2}$)

It is trivial to see that given a map $D$ of the later type we can always create a map of the first type by defining , $L(Q) := \sum_{x \in \{\pm 1\}^n } D(x) Q(x)$.

• But does every map Lasserre map $L$ induce a pseudo-distribution $D$?

• Can one think of this $\{\pm 1\}^n$ as $\mathbb{F}_2^n$ and then is there any meaning (or use!) to ask for a generalization to $\mathbb{F}_q^n$?

Answer 1

The answer to your first question is yes by some linear algebra. Write down the equations for $L(m) = \sum_{x\in\pm 1} D(x)m(x)$ where $m$ is a monomial of degree at most $d$ (with no squared variables in it). You can write this as $L = MD$ where $M$ is a matrix with rows indexed by the monomials $m$ and columns indexed by the points $x \in \{\pm 1\}$, with values $m(x)$, and $D$ is a vector indexed by the points in $\{\pm 1\}$. $M$ has full rank, so you can find $D$ with $MD = L$ for any $L$. That any such $D$ satisfies the pseudodistribution properties follows from the fact that $L$ satisfies the corresponding properties.

As for your second question, formally, it can be done for prime fields by just using equations like $x^p = 1$ in place of $x^2 = 1$. (I'm not sure what to do for general prime powers.) It might be helpful in characteristics greater than two to generalize the rest of the SOS theory to work over $\mathbb{C}$, since you're working with complex roots of unity. This can be done essentially by replacing "sum of squares" by "sum of products-of-conjugates" and making appropriate adaptations elsewhere.

However, I'm doubtful that it's useful to think of $\{\pm 1\}$ as being "like" $\mathbb{F}_2$ in the context of SOS. Embedding finite fields as roots of unity doesn't jive well with sum of squares: addition in the finite field turns into multiplication over $\mathbb{R}$, and hence SOS requires high degree to reason about sums (in the finite field) of many unknowns, because they translate to products (over the reals) of many variables. An essentially canonical demonstration of this is the lower bound for solving linear equations over $\mathbb{F}_2$ (see section 3.1 here). In particular, you can trick low-degree SOS into believing that a certain system of linear equations over $\mathbb{F}_2$ is completely satisfiable, when in reality at most a $\frac{1}{2}+\epsilon$ fraction of equations can be satisfied by any true assignment.