Extended Nullstellensatz proof systems

For a finite set $\mathcal{F}$ of polynomials over fixed finite prime field of size $p$ containing all polynomials $x^2-x$ a Nullstellensatz proof of the unsolvability of the system $$f=0,allf\in \mathcal{F}$$ in the field is a linear combination ${\sum }_{f\in \mathcal{F}}{h}_f\cdot f$ that equals to $1$ in the ring of polynomails. The measure of complexity of such a proof is its degree: ${\max }_{f}deg(h_{f}f)$. We study the problem to establish degree lower bounds for some {\em extended} NS proof systems: these systems prove the unsolvability of $\mathcal{F}$ by proving the unsolvability of a bigger set $\mathcal{F}\cup \mathcal{E}$, where set $\mathcal{E}$ may use new variables $r$ and contains all polynomials $r^p-r$, and satisfies the following soundness condition: – - Any $0,1$-assignment $\bar{a}$ to variables $\bar{x}$ can be appended by an assignment $\bar{b}$ to variables $\bar{r}$ such that for all $g\in \mathcal{E}$ it holds that $g(\bar{a},\bar{b})=0$. We define a notion of pseudo-solutions of $\mathcal{F}$ and prove that the existence of pseudo-solutions with suitable parameters implies lower bounds for two extended NS proof systems ENS and UENS defined in Buss et al. (1996/97). Further we give a combinatorial example of $\mathcal{F}$ and candidate pseudo-solutions based on the pigeonhole principle.