  We show that if a system of degree-$k$ polynomial constraints on~$n$ Boolean
variables has a Sums-of-Squares (SOS) proof of unsatisfiability with at
most~$s$ many monomials, then it also has one whose degree is of the order of
the square root of~$n \log s$ plus~$k$. A similar statement holds for the more
general Positivstellensatz (PS) proofs. This establishes size-degree trade-offs
for SOS and PS that match their analogues for weaker proof systems such as
Resolution, Polynomial Calculus, and the proof systems for the LP and SDP
hierarchies of Lov\'asz and Schrijver. As a corollary to this, and to the known
degree lower bounds, we get optimal integrality gaps for exponential size SOS
proofs for sparse random instances of the standard NP-hard constraint
optimization problems. We also get exponential size SOS lower bounds for
Tseitin and Knapsack formulas. The proof of our main result relies on a
zero-gap duality theorem for pre-ordered vector spaces that admit an order
unit, whose specialization to PS and SOS may be of independent interest.
