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

CREATORAmik Raj Behera, Nutan Limaye, Varun Ramanathan, Srikanth Srinivasan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE156 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-16397

Browse the full library · About the Tower of Babel