4
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – gradstudent Sep 12 '16 at 13:44
  • $\begingroup$ 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. $\endgroup$ – Andrew Morgan Sep 12 '16 at 14:37
  • $\begingroup$ 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. $\endgroup$ – Andrew Morgan Sep 12 '16 at 14:44
  • $\begingroup$ 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, 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?..) $\endgroup$ – gradstudent Sep 12 '16 at 14:54
  • $\begingroup$ 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. $\endgroup$ – Andrew Morgan Sep 12 '16 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.