Polynomial Calculus Sizes Over the Boolean and Fourier Bases are Incomparable

For every <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n &gt; 0$</tex>, we show the existence of a CNF tautology over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n^{2})$</tex> variables of width <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\log {\it n})$</tex> such that it has a Polynomial Calculus Resolution refutation over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{0,1\}$</tex> variables of size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(n^{3} \text{polylog} (n))$</tex> but any Polynomial Calculus refutation over <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{+1, -1\}$</tex> variables requires size <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$2^{\Omega(n)}$</tex>. This shows that Polynomial Calculus sizes over the {0, 1} and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\{+1,\ -1\}$</tex> bases are incomparable (since Tseitin tautologies show a separation in the other direction) and answers an open problem posed by Sokolov [1] and Razborov [2].