New Bounds for the Ideal Proof System in Positive Characteristic
Amik Raj Behera, Nutan Limaye, Varun Ramanathan, Srikanth Srinivasan · 2025
Read New Bounds for the Ideal Proof System in Positive Characteristic by Amik Raj Behera, Nutan Limaye, Varun Ramanathan, Srikanth Srinivasan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16397.txt.
Description
Amik Raj Behera, Nutan Limaye, Varun Ramanathan, and Srikanth Srinivasan bound the power of an algebraic proof system over fields of positive characteristic, in a 2025 paper. The Ideal Proof System checks polynomial identities as proofs. Its strength over fields where arithmetic wraps around, rather than the zero-characteristic case studied before, was less charted.
The team adapted a functional lower bound method to this setting. They proved exponential-size lower bounds for several fragments of the system, meaning some truths need huge proofs there. They also proved matching upper bounds: the same instances admit short, constant-depth refutations, and a whole class of symmetric instances falls efficiently too. The work matters partly because this proof system's limits connect to a famous open problem about Frege proofs. Field size conditions are stated with care, and a concurrent paper is noted.
Catalog record
| CREATOR | Amik Raj Behera, Nutan Limaye, Varun Ramanathan, Srikanth Srinivasan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 156 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-16397