Polynomial Calculus Sizes Over the Boolean and Fourier Bases are Incomparable

For every$n > 0$, we show the existence of a CNF tautology over$O(n^{2})$variables of width$O(\log {\it n})$such that it has a Polynomial Calculus Resolution refutation over$\{0,1\}$variables of size$O(n^{3} \text{polylog} (n))$but any Polynomial Calculus refutation over$\{+1, -1\}$variables requires size$2^{\Omega(n)}$. This shows that Polynomial Calculus sizes over the 0, 1 and$\{+1,\ -1\}$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].