We give new lower bounds for the fragments of the Ideal Proof System (IPS) introduced by Grochow and Pitassi (JACM 2018). The Ideal Proof System is a central topic in algebraic proof complexity developed in the context of Nullstellensatz refutation (Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994) and simulates Extended Frege efficiently. Our main results are as follows. 1. mult-IPS_{Lin'}: We prove nearly quadratic-size formula lower bound for multilinear refutation (over the Boolean hypercube) of a variant of the subset-sum axiom polynomial. Extending this, we obtain a nearly matching qualitative statement for a constant degree target polynomial. 2. IPS_{Lin'}: Over the fields of characteristic zero, we prove exponential-size sum-of-ROABPs lower bound for the refutation of a variant of the subset-sum axiom polynomial. The result also extends over the fields of positive characteristics when the target polynomial is suitably modified. The modification is inspired by the recent results (Hakoniemi, Limaye, Tzameret, STOC 2024 and Behera, Limaye, Ramanathan, Srinivasan, ICALP 2025). The mult-IPS_{Lin'} lower bound result is obtained by combining the quadratic-size formula lower bound technique of Kalorkoti (SICOMP 1985) with some additional ideas. The proof technique of IPS_{Lin'} lower bound result is inspired by the recent lower bound result of Chatterjee, Kush, Saraf and Shpilka (CCC 2024).
翻译:我们为Grochow和Pitassi(JACM 2018)提出的理想证明系统(IPS)片段给出了新的下界。理想证明系统是在零化子反驳(Beame, Impagliazzo, Krajicek, Pitassi, Pudlak, FOCS 1994)背景下发展起来的代数证明复杂性核心课题,并能高效模拟扩展弗雷格系统。我们的主要结果如下:1. mult-IPS_{Lin'}:针对子集和公理多项式的一个变体,我们证明了在布尔超立方上的多重线性反驳存在近二次规模的公式下界。通过扩展该结果,我们针对常数次目标多项式获得了近乎匹配的定性结论。2. IPS_{Lin'}:在特征为零的域上,我们证明了子集和公理多项式变体反驳的ROABP和存在指数规模下界。当目标多项式经过适当修改时,该结果也可推广至正特征域。此修改受到近期研究成果(Hakoniemi, Limaye, Tzameret, STOC 2024 以及 Behera, Limaye, Ramanathan, Srinivasan, ICALP 2025)的启发。mult-IPS_{Lin'}下界结果是通过将Kalorkoti(SICOMP 1985)的二次规模公式下界技术与若干新思路相结合而获得的。IPS_{Lin'}下界结果的证明技术则受到Chatterjee, Kush, Saraf和Shpilka(CCC 2024)近期下界成果的启发。