  In this paper, we develop machinery which makes it much easier to prove sum
of squares lower bounds when the problem is symmetric under permutations of
$[1,n]$ and the unsatisfiability of our problem comes from integrality
arguments, i.e. arguments that an expression must be an integer. Roughly
speaking, to prove SOS lower bounds with our machinery it is sufficient to
verify that the answer to the following three questions is yes:
  1. Are there natural pseudo-expectation values for the problem?
  2. Are these pseudo-expectation values rational functions of the problem
parameters?
  3. Are there sufficiently many values of the parameters for which these
pseudo-expectation values correspond to the actual expected values over a
distribution of solutions which is the uniform distribution over permutations
of a single solution?
  We demonstrate our machinery on three problems, the knapsack problem analyzed
by Grigoriev, the MOD 2 principle (which says that the complete graph $K_n$ has
no perfect matching when $n$ is odd), and the following Turan type problem:
Minimize the number of triangles in a graph $G$ with a given edge density. For
knapsack, we recover Grigoriev's lower bound exactly. For the MOD 2 principle,
we tighten Grigoriev's linear degree sum of squares lower bound, making it
exact. Finally, for the triangle problem, we prove a sum of squares lower bound
for finding the minimum triangle density. This lower bound is completely new
and gives a simple example where constant degree sum of squares methods have a
constant factor error in estimating graph densities.
