{"id":"arxiv/2611.07280","url":"https://arxiv.org/abs/2611.07280","tags":["cs.CC","cs.LO","math.LO"],"score":0,"title":"Degree profiles of uniform polynomial consequences: Linear lower bounds for Nullstellensatz and Polynomial Calculus","domain":"cs.CC","source":"arxiv","authors":["Søren Riis"],"reviews":0,"subject":"cs.CC","summary":"This paper proves asymptotically optimal linear degree lower bounds for Nullstellensatz and Polynomial Calculus, yielding a four-way polynomial-versus-exponential proof-size classification for uniform polynomial consequences over fields of positive characteristic. The size bounds use full, explicit coefficient lists, including zeros. Apart from a fixed finite initial range, exactly one of four cases occurs: $\\mathrm T_1$, bounded degree; $\\mathrm T_2$, degree at least linear in the universe size $n$; $\\mathrm T_3$, constant degree on some residue classes and at least linear degree on the…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-05","reactions":{}}