<p>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.</p>

<p>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.</p>

<p>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 <a href="http://www.boazbarak.org/sos/prev/files/all-notes.pdf" rel="nofollow">here</a>). 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.</p>

CC BY-SA 3.0
2016-09-12T13:44:54.713Z
Could you kindly say some more about this statement, "addition in the finite field turns into multiplication over $\mathbb{R}$". I know this argument in section $3.1$ as you point out. There the number of variables don't increase when Barak implicitly by a change of variables passes on to a description of the equations over $\mathbb{R}$ rather than working with linear equations over $\mathbb{F}_2$.
gradstudent
CC BY-SA 3.0
2016-09-12T14:37:46.583Z
Addition in $\mathbb{F}_2$ is where you do things like 0+1=1, 1+1=0, etc. The representation you're asking about represents this in $\mathbb{R}$ as $\pm 1$ with multiplication. $-1 \cdot +1 = -1$, $-1 \cdot -1 = +1$ are the analogues of the above equations. When you go to generalize this over $F_3$ or $F_5$ say, you would use 3rd and 5th roots of unity. So 1+2=0 in $F_3$ translates to $\omega \cdot \omega^2 =1$. Of course, this requires thinking over the complex numbers, not just the reals, and I was definitely being imprecise when I said "over \mathbb{R}$", but it was just an analogy.
Andrew Morgan
CC BY-SA 3.0
2016-09-12T14:44:39.480Z
And while the result presented in section 3.1 is for 3-LIN (hence all the equations turn into degree 3 equations over the reals), the point is that over the course of solving those equations, one has to use terms where many variables are involved, and SOS can't reason about these intermediate quantities.
Andrew Morgan
CC BY-SA 3.0
2016-09-12T14:54:49.193Z
So isn't there an advantage in thinking of the hypercube as $\{0,1\}^n$ rather than $\{-1,1\}^n$ because in former case the natural addition and multiplication operations of $\mathbb{R}$ when restricted to this cube replicate the $\mathbb{F}_2$ addition and multiplication? (...now I wonder if this is why these papers, https://www.cs.cmu.edu/~odonnell/papers/2lin-Z.pdf,  want to think of the equations as over $\mathbb{Z}_q$ rather than $\mathbb{F}_q$..is it?..)
gradstudent
CC BY-SA 3.0
2016-09-12T15:26:51.450Z
Choosing between $\{0,1\}^n$ and $\{\pm1\}^n$ (as subsets of $\mathbb{R}^n$) is just a matter of convenience. From the point of view of SOS, they're basically the same (formally: there is an affine linear map that sends one set to the other and vice-versa). Your reasoning toward $\{0,1\}^n$ having an advantage is flawed, since $\{0,1\}^n$ (the set in $\mathbb{R}^n$) does *not* have the same additive structure as $\mathbb{F}_2^n$. I don't know enough about those works to answer your last question.
Andrew Morgan
CC BY-SA 3.0
2016-09-12T15:45:05.330Z
Yes! Sorry. 1+1 = 2 and not 0 and hence it doesn't get the additive structure. So both $\{0,1\}^n$ and $\{\pm 1\}^n$ seem to be getting the multiplicative structure of $\mathbb{F}_2^n$ right but to get the same for $\mathbb{F}_q^n$ one is forced to look at complex numbers. (..But even for linear equations over $\mathbb{Z}_q$ there doesn't seem to be a natural embedding of $\mathbb{Z}_q^n$ sitting inside $\mathbb{R}^n$ s.t the natural addition arithmetic will carry over. So even to reproduce just the additive structure we would still need complex numbers?..)
gradstudent
CC BY-SA 3.0
2016-09-12T03:20:09.760Z
2016-09-12T03:20:09.760Z
Andrew Morgan
<p>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}$.  </p>

<p>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}$) </p>

<p>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)$. </p>

<ul>
<li><p>But does every map Lasserre map $L$ induce a pseudo-distribution $D$? </p></li>
<li><p>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$? </p></li>
</ul>

<cc.complexity-theory><np-hardness><approximation-hardness><sum-of-squares>
From Lasserre maps to pseudo-distributions
gradstudent
# From Lasserre maps to pseudo-distributions

(Asked by: username_0 on 2016-09-11)

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$?

**Tags:** cc.complexity-theory, np-hardness, approximation-hardness, sum-of-squares


---

## 1 answers

### Answer by username_1 on 2016-09-12. Score: 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](http://www.boazbarak.org/sos/prev/files/all-notes.pdf)). 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.

> **Comments:**
> **username_0**: Could you kindly say some more about this statement, "addition in the finite field turns into multiplication over $\mathbb{R}$". I know this argument in section $3.1$ as you point out. There the number of variables don't increase when Barak implicitly by a change of variables passes on to a description of the equations over $\mathbb{R}$ rather than working with linear equations over $\mathbb{F}_2$.  
> **username_1**: Addition in $\mathbb{F}_2$ is where you do things like 0+1=1, 1+1=0, etc. The representation you're asking about represents this in $\mathbb{R}$ as $\pm 1$ with multiplication. $-1 \cdot +1 = -1$, $-1 \cdot -1 = +1$ are the analogues of the above equations. When you go to generalize this over $F_3$ or $F_5$ say, you would use 3rd and 5th roots of unity. So 1+2=0 in $F_3$ translates to $\omega \cdot \omega^2 =1$. Of course, this requires thinking over the complex numbers, not just the reals, and I was definitely being imprecise when I said "over \mathbb{R}$", but it was just an analogy.  
> **username_1**: And while the result presented in section 3.1 is for 3-LIN (hence all the equations turn into degree 3 equations over the reals), the point is that over the course of solving those equations, one has to use terms where many variables are involved, and SOS can't reason about these intermediate quantities.  
> **username_0**: So isn't there an advantage in thinking of the hypercube as $\{0,1\}^n$ rather than $\{-1,1\}^n$ because in former case the natural addition and multiplication operations of $\mathbb{R}$ when restricted to this cube replicate the $\mathbb{F}_2$ addition and multiplication? (...now I wonder if this is why these papers, https://www.cs.cmu.edu/~odonnell/papers/2lin-Z.pdf,  want to think of the equations as over $\mathbb{Z}_q$ rather than $\mathbb{F}_q$..is it?..)  
> **username_1**: Choosing between $\{0,1\}^n$ and $\{\pm1\}^n$ (as subsets of $\mathbb{R}^n$) is just a matter of convenience. From the point of view of SOS, they're basically the same (formally: there is an affine linear map that sends one set to the other and vice-versa). Your reasoning toward $\{0,1\}^n$ having an advantage is flawed, since $\{0,1\}^n$ (the set in $\mathbb{R}^n$) does *not* have the same additive structure as $\mathbb{F}_2^n$. I don't know enough about those works to answer your last question.  
> **username_0**: Yes! Sorry. 1+1 = 2 and not 0 and hence it doesn't get the additive structure. So both $\{0,1\}^n$ and $\{\pm 1\}^n$ seem to be getting the multiplicative structure of $\mathbb{F}_2^n$ right but to get the same for $\mathbb{F}_q^n$ one is forced to look at complex numbers. (..But even for linear equations over $\mathbb{Z}_q$ there doesn't seem to be a natural embedding of $\mathbb{Z}_q^n$ sitting inside $\mathbb{R}^n$ s.t the natural addition arithmetic will carry over. So even to reproduce just the additive structure we would still need complex numbers?..)  

---

