Extended Nullstellensatz proof systems

• Published in: arXiv.org 2023-09
• Main Author: Krajicek, Jan
• Format: Article
• Language: English
• Subjects: Combinatorial analysis; Lower bounds; Polynomials
• ISSN: 2331-8422
• DOI: 10.48550/arxiv.2301.10617

For a finite set \(\cal 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\ ,\ \mbox{ all } f \in {\cal F} $$ in the field is a linear combination \(\sum_{f \in {\cal 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 \(\cal F\) by proving the unsolvability of a bigger set \({\cal F}\cup {\cal E}\), where set \(\cal E\) may use new variables \(r\) and contains all polynomials \(r^p - r\), and satisfies the following soundness condition: -- - Any \(0,1\)-assignment \(\overline a\) to variables \(\overline x\) can be appended by an assignment \(\overline b\) to variables \(\overline r\) such that for all \(g \in {\cal E}\) it holds that \(g(\overline a, \overline b) = 0\). We define a notion of pseudo-solutions of \(\cal 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 \(\cal F\) and candidate pseudo-solutions based on the pigeonhole principle.