Lower Bounds for Polynomial Calculus: Nonbinomial Case

We generalize recent linear lower bounds for Polynomial Calculus based on binomial ideals. We produce a general hardness criterion (that we call immunity), which is satisfied by a random function, and prove linear lower bounds on the degree of PC refutations for a wide class of tautologies based on immune functions. As applications of our techniques, we introduce mod$_p$. Tseitin tautologies in the Boolean case (e.g. in the presence of axioms $x_i^2=x_i$), prove that they are hard for PC over fields with characteristic different from $p$, and generalize them to the flow tautologies that are based on the majority function and are proved to be hard over any field. We also prove the $\Omega(n)$ lower bound for random $k$-CNFs over fields of characteristic 2.