{"id":"1bf536b3-c4ed-4a4c-be23-b36743a09178","arxiv_id":"2506.16397","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors extend functional lower bound techniques to obtain exponential-size lower bounds for fragments of the Ideal Proof System over large fields of positive characteristic, and give efficient constant-depth refutations for the same instances.","lead":"This paper proves exponential lower bounds for several restricted algebraic proof systems over fields of positive characteristic, extending known characteristic-0 results, and shows these hard instances have short constant-depth refutations. The relevance: such lower bounds are a step toward proving AC0[p]-Frege lower bounds, a long-standing open problem in proof complexity.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Constant-depth lower-bound transfer from [GHT22] is asserted, not verified; hidden char-p dependence is the softest spot.","rationale":"The reader's verdict of ACCEPT with moderate confidence is reasonable: the paper makes a well-scoped advance, the main degree lower bound appears correct, and the large-field caveat is explicit (Remark 1.7). The reader's weakest_assumption was the field-size requirement; that is a real limitation but not a correctness flaw, since the theorems are stated for exactly those fields. My review identifies a distinct risk: the most complex lower bound, Theorem 1.6, is not self-contained. It depends on a transfer of [GHT22]'s proof that the paper asserts 'works out verbatim' without reproducing the full argument. The two characteristic-0 dependencies the paper names (LST21 and the degree lower bound) are plausibly the only ones, and Section 2.5 gives a credible sketch, but the rank lemma and the word-polynomial machinery could contain other uses of characteristic 0 that the randomization does not automatically fix. Because no concrete error was found and the transfer is a standard style of argument in this area, I do not think the verdict should change; however, a line-by-line audit of [GHT22]'s lemma with the substituted ingredients would settle whether Theorem 1.6 is fully proved. The remaining lower bounds, and the upper bounds, are more self-contained and do not raise similar concerns.","tokens_in":44542,"tokens_out":61887,"duration_ms":587869,"concrete_test":"Audit [GHT22]'s proof of its Lemma 6 (rank lower bound) and the surrounding derivation of Theorem 2.11 line by line, substituting Lemma 2.14 for the FSTW21 degree lower bound and For24's Corollary 27 for the LST21 set-multilinearization step. At every step that divides by an integer, for example d! or interpolation coefficients, check whether the coefficient is nonzero in F_p for the parameter sizes used (|w_i| = O(log n), p possibly 2 or 3). If any required coefficient vanishes mod p, test whether the alpha-randomization in ksw,alpha restores the leading-monomial property with high probability; if not, Theorem 1.6 needs a different proof.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central lower bounds are conditional on a large-field assumption that is explicit and not internally inconsistent; the degree lower bound (Lemma 2.2 and Claim 2.3) checks out: the claimed top monomial has exponent 2^{i-1} per variable, and only the V=empty term reaches total degree 2^n-1, so the coefficient survives any characteristic. The least secure link is instead the transfer of the constant-depth lower bound (Theorem 1.6). Section 2.5 states that after replacing [LST21] by [For24] and the degree lower bound by Lemma 2.14, \"the rest of the proof of [GHT22] works out verbatim.\" This is an assertion, not a demonstrated proof. [GHT22]'s rank lemma (Lemma 2.13) and its proof may contain additional latent uses of characteristic 0, for example, invertibility of factorials d! when d >= p, or integrality of interpolation coefficients, that the randomized knapsack polynomial ksw,alpha does not obviously cure. No concrete error is identified, but the paper does not reproduce the argument, so a hidden p-torsion obstruction cannot be excluded. If such a dependency exists, the superpolynomial lower bound for multilinear constant-depth IPSLIN1 in positive characteristic would be unproven rather than false; the remaining lower bounds (sparse, roABP, multilinear-formula) are more self-contained and appear sound.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Ideal Proof System (IPS) over fields of positive characteristic, extending earlier characteristic-0 results of Forbes--Shpilka--Tzameret--Wigderson (FSTW21) and Govindasamy--Hakonomi--Tzameret (GHT22). The main lower bounds state that, for fields of size n^{ω(1)} (or larger), several restricted IPS fragments—sparse-IPSLIN1, roABP-IPSLIN1, multilinear-formula-IPSLIN1, and multilinear constant-depth IPSLIN1—require exponential or superpolynomial refutation size for explicitly given sparse polynomials that are easy to compute. The central technical lemma, Lemma 2.2, proves that for a random linear form Σ α_i x_i with coefficients in a proper subfield F and β outside F, the unique multilinear polynomial that agrees with 1/(Σ α_i x_i - β) on the Boolean cube has full degree n with high probability, with no restriction on the characteristic. The lower-bound proofs plug this degree lower bound into the functional lower-bound machinery of FSTW21 and GHT22, replacing characteristic-0-dependent steps. The paper also proves upper bounds: every sparse polynomial f - β with β outside the coefficient field has a constant-depth IPSLIN refutation of degree O(kpD); every unsatisfiable degree-1 polynomial over F_{p^k} has an IPSLIN refutation of degree O(kp); and every multilinear symmetric system has a constant-depth IPSLIN refutation of size O(m^2 n^5 log n). The large-field requirement is explicitly stated and discussed.","tokens_in":44789,"tokens_out":25751,"duration_ms":238176,"significance":"If the results hold, they extend a substantial body of algebraic proof-complexity lower bounds from characteristic 0 to arbitrary characteristic, providing a further step toward the long-standing open problem of AC0[p]-Frege lower bounds, which is a stated motivation. The hard instances are themselves easy to compute—sparse and of low degree—which is a strength relative to some prior constructions whose hard instances were not efficiently computable. The paper gives a self-contained proof of the central degree lower bound (Lemma 2.2 with Claim 2.3) and provides explicit, detailed constructions for the upper bounds. The bounded-depth symmetric-system upper bound and the non-multilinear upper bounds also shed light on the role of multilinearity in IPS. The main caveat is that the constant-depth lower bound (Theorem 1.6) is obtained by asserting that a published characteristic-0 proof adapts verbatim, rather than by reproducing the adaptation; this is the softest spot in the paper.","major_comments":[{"comment":"Section 2.5: The transfer of the constant-depth lower bound from [GHT22] is the least self-contained part of the paper. The authors claim the proof works verbatim after replacing the degree lower bound and the [LST21] result by [For24], but they do not demonstrate that Lemma 2.13's proof has no hidden characteristic-0 assumption. This is a significant gap in a main theorem.","section":"Section 2.5, Theorem 2.15"}],"minor_comments":[{"comment":"Claim 2.3 is the crux of the main degree lower bound but is proved only via a proof sketch. Please expand it into a complete, self-contained proof, since the uniqueness of the monomial selection is essential for the lemma.","section":"Section 2.1, Claim 2.3"},{"comment":"In the proof of Claim 4.4, the statement that the system of Q_t constraints implies \"for each coordinate i, b_i ≤ n_i\" is false. For example, with p=2, n=4, b=3 (so b_1=1 > n_1=0) the Q_t constraints are still satisfied. The intended conclusion k≤n can be obtained directly by taking t=k when k>n; please correct this step.","section":"Section 4, Claim 4.4"},{"comment":"In the proof of Claim 4.2, the product expressing e_d(a) as a function of e_{p^i}(a) should run over i=0,...,ℓ (including e_1), not i=1,...,ℓ as written. The current indexing omits the p^0 digit.","section":"Section 4, Claim 4.2"},{"comment":"The stated size bound \"poly(s,p)\" in Theorem 1.8 is not supported by the proof, which yields circuits of size O(k(s+p)+sD). Please restate the theorem with the correct bound, or explicitly restrict to instances of constant degree, since the size of the refutation may legitimately depend on the degree of the sparse polynomial.","section":"Theorem 1.8"},{"comment":"Remark 1.10 refers to \"polypn,pq-sized\" refutations from Theorem 1.8, while the theorem statement says \"size polyps,pq\"; please align the two statements.","section":"Section 1.3.2, Remark 1.10"}],"recommendation":"major_revision","confidential_remarks":"The paper makes a solid contribution and most of the technical content appears sound. The main reason for major revision is the unproven transfer of the constant-depth lower bound from [GHT22]; this needs to be either proved in detail or explicitly stated as a conjecture/dependency. The size-bound discrepancy in Theorem 1.8 is a localized fix. The paper is likely suitable for the journal after these points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nHere's my read on Behera et al. The paper does what it says: it takes the FSTW21/GHT22 IPS lower-bound framework and extends it to positive characteristic, at the price of requiring large fields (|F| = n^{ω(1)}). The core new ingredient is Lemma 2.2, a degree lower bound for the multilinear inverse of a random linear form over any characteristic. The proof via the numerator polynomial and Claim 2.3 is explicit and I checked the key step: the top monomial coefficient is 1, so it survives p-torsion. The accompanying union-bound Lemma 2.4 is straightforward and correct.\n\nGiven that lemma, the sparse, roABP, and multilinear-formula lower bounds go through by plugging into the known machinery. Those sections are solid, and the fact that the hard instances are easy to compute (sparse, roABP-computable, multilinear-formula-computable) is a genuine improvement over HLT24. The upper bounds — constant-depth IPSLIN refutations for sparse polynomials with β outside the field, the degree O(kp) Nullstellensatz certificate for linear forms, and the symmetric-instance refutation — are new and nicely complement the lower bounds. Theorem 1.11 looks like the most self-contained result.\n\nThe soft spot is Theorem 1.6, the constant-depth multilinear IPSLIN1 lower bound. Section 2.5 says that after swapping in Forbes' theorem and Lemma 2.14, 'the rest of the proof of [GHT22] works out verbatim.' That is an assertion, not a demonstration. GHT22's rank lemma (Lemma 2.13) uses the degree lower bound in a way that the paper sketches, but I cannot fully verify from this text that every step in that proof is characteristic-free. The paper's own summary says the only char-0 uses were [LST21] and the degree lower bound; if that is accurate, the transfer works. But because the proof is not reproduced, a hidden p-torsion issue in the rank lemma cannot be ruled out. If one exists, the constant-depth result would be unproven rather than false; the other lower bounds stand on their own.\n\nThe field-size requirement is explicit and honest. It is a real limitation, not a flaw: the authors acknowledge small finite fields need different hard instances, and concurrent work covers that case. The citation pattern is proper — Forbes, FSTW21, GHT22 are given credit, and the relation to EGLT25 is stated.\n\nBottom line: this deserves a serious referee. I would accept it with the request that Section 2.5 be expanded or that the authors provide a fuller proof of the constant-depth transfer. The rest of the paper is in good shape. I'd bring it to reading group and would cite it if I worked on algebraic proof complexity.","headline":"Solid large-field positive-characteristic transfer of known IPS lower bounds, with a new degree lemma and useful upper bounds; the constant-depth transfer is the one part I'd want checked.","tokens_in":45324,"tokens_out":2364,"would_cite":true,"duration_ms":22233,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For large fields of any positive characteristic, several restricted algebraic proof systems remain exponentially weak on simple sparse polynomials, while constant-depth IPS refutes those same instances efficiently.","keywords":["ideal proof system","algebraic proof complexity","positive characteristic","functional lower bounds","constant-depth algebraic circuits","multilinear formulas","read-once oblivious algebraic branching programs","Nullstellensatz certificate"],"falsifier":"For $n=3$, set $S = \\mathbb{F}_8$ and $F' = \\mathbb{F}_{64}$, fix any $\\beta \\in \\mathbb{F}_{64} \\setminus \\mathbb{F}_8$, and enumerate all $8^3 = 512$ coefficient vectors $\\alpha \\in S^3$. For each, compute the unique multilinear polynomial agreeing with $1/(\\sum_{i=1}^3 \\alpha_i x_i - \\beta)$ on the Boolean cube. If fewer than 64 of the 512 polynomials have full degree 3, Lemma 2.2's probability bound is violated and the lower-bound arguments collapse.","tokens_in":44343,"feed_emoji":"🧮","tokens_out":9929,"duration_ms":88530,"temperature":0.7,"pith_summary":"This paper tries to show that lower bounds previously known for restricted fragments of the Ideal Proof System (IPS) over characteristic zero survive for fields of any positive characteristic, provided the field is large: size $n^{\\omega(1)}$. It claims that sparse-IPSLIN1, read-once oblivious branching program IPSLIN1, multilinear-formula IPSLIN1, and multilinear constant-depth IPSLIN1 all require exponential or superpolynomial refutation size for explicit sparse polynomials that are themselves easy to compute. The same hard instances admit polynomial-size constant-depth IPSLIN refutations, and every unsatisfiable multilinear symmetric system is refutable in constant depth with polynomial size. This matters because restricted IPS systems are the main current route toward lower bounds for $AC^0[p]$-Frege, and the paper removes the characteristic-zero restriction that previously blocked that route.","feed_headline":"Large fields keep restricted algebraic proofs exponential","feed_subtitle":"Hard sparse instances need exponential refutations, yet constant-depth IPS proves them in polynomial size.","key_machinery":"The load-bearing mechanism is Lemma 2.2, a tight degree lower bound for the multilinear inverse of a random linear form; it replaces the characteristic-zero component in the functional lower bound framework of the prior papers. The framework reduces every restricted IPS refutation to computing $1/f$ on the Boolean cube. On the upper-bound side, the mechanism is the Freshman's Dream identity $(a+b)^p = a^p + b^p$: repeatedly raising the linear constraint $\\sum \\alpha_i x_i - \\beta$ to $p$-th powers expresses the $p^k$-powered version as a multiple of the original modulo the Boolean axioms, and choosing $\\beta$ outside the coefficient field makes the difference between the $p^k$-powered and original linear forms a nonzero constant. That difference directly writes $1$ as a polynomial combination with constant-depth coefficient circuits.","core_discovery":"The central discovery is a degree lower bound for the reciprocal of a random linear form over a large field. Let $F$ be a strict subfield of $F'$, fix $\\beta \\in F' \\setminus F$, and choose $\\alpha = (\\alpha_1,\\dots,\\alpha_n) \\in F^n$ uniformly from a finite set $S \\subseteq F$. With probability at least $1 - (2^n-1)/|S|$, the unique multilinear polynomial that agrees with $1/(\\sum_{i=1}^n \\alpha_i x_i - \\beta)$ on the Boolean cube has full degree $n$. The proof exhibits a numerator monomial with coefficient $1$, so the bound cannot be killed by the characteristic. Substituting this lemma for the older characteristic-zero degree bound, the paper feeds the functional lower bound method of the earlier work: a $C$-IPSLIN1 refutation forces the coefficient polynomial to compute the reciprocal on the Boolean cube, so any lower bound on computing that function becomes a refutation-size lower bound. The same degree lemma also supplies the constant-depth multilinear case, where the field needs only $2^{O((\\log n)^2)}$ size.","pith_inferences":["If Lemma 2.2 were extended to fields of size $O(n)$ instead of $2^{\\Omega(n)}$, every lower bound in this paper would transfer to small finite fields; the field-size condition is the explicit bottleneck in the paper.","The constant-depth refutation of all symmetric multilinear systems suggests symmetry is a structural source of short algebraic proofs in every characteristic; a natural test is whether the $O(m^2 n^5 \\log n)$ bound can be improved to near-linear in the number of terms.","Because the lower bounds target IPSLIN1 while the upper bounds are non-multilinear IPSLIN, the gap isolates multilinearity as the source of hardness; a next step would be to prove lower bounds against multilinear constant-depth IPS without the linear-in-$y$ restriction."],"forward_implications":["Sparse-IPSLIN1 refutations of $\\sum_{i=1}^n \\alpha_i x_i - \\beta$ require size $2^{\\Omega(n)}$ when the coefficient field has size $2^{\\Omega(n)}$.","Fixed-order roABP-IPSLIN1 refutations of $\\sum_{i=1}^n \\alpha_i x_i y_i - \\beta$ require width $2^{\\Omega(n)}$.","Any-order roABP-IPSLIN1 and multilinear-formula-IPSLIN1 refutations of $\\sum_{i<j} \\alpha_{i,j} z_{i,j} x_i x_j - \\beta$ require size $2^{\\Omega(n)}$ and $n^{\\Omega(\\log n)}$ respectively.","Multilinear constant-depth IPSLIN1 refutations of the degree-four subset-sum instance $\\sum_{i<j<k<\\ell} \\alpha_{i,j,k,\\ell} z_{i,j,k,\\ell} x_i x_j x_k x_\\ell - \\beta$ require size $n^{\\omega(1)}$.","The same instances have $\\mathrm{poly}(n,p)$-size constant-depth IPSLIN refutations of degree $O(k p D)$, so the multilinearity and the restricted models are both doing essential work."],"supporting_citations":[{"why":"Introduced the Ideal Proof System and showed that constant-depth IPS over characteristic $p$ can simulate $AC^0[p]$-Frege, motivating the lower-bound question.","marker":"[GP18]"},{"why":"Supplied the functional lower bound method, the coefficient/evaluation dimension tools, and the characteristic-zero degree bound that this paper replaces.","marker":"[FSTW21]"},{"why":"Provided the constant-depth multilinear IPSLIN1 lower-bound framework and the word-polynomial construction that the paper adapts to positive characteristic.","marker":"[GHT22]"},{"why":"Extended the low-depth algebraic circuit lower bounds used by GHT22 to arbitrary fields, removing the characteristic-zero restriction in that step.","marker":"[For24]"},{"why":"Built the word-polynomial and set-multilinear projection framework on which the constant-depth lower bound is based.","marker":"[LST21]"},{"why":"Supplied the multilinear formula size-to-coefficient-dimension lower bound used for the multilinear-formula IPS result.","marker":"[Raz09]"},{"why":"Characterized roABP width by coefficient dimension, used for the roABP-IPSLIN1 lower bounds.","marker":"[Nis91]"}],"fun_headline_variants":["Large fields don't rescue algebraic proofs from exponential lower bounds","Positive characteristic: exponential IPS lower bounds for large fields","Constant-depth IPS proves symmetric cases but exponential gaps persist elsewhere","Reciprocal lemma yields tight IPS bounds over positive characteristic","Exponential lower bounds for IPS over large positive characteristic fields"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound proofs require the coefficient field to be at least $2^{2n}$ (or $2^{O((\\log n)^2)}$ for the constant-depth case) so the union bound over all restrictions succeeds; for small finite fields the same argument guarantees no hard coefficient vector.","fun_headline_variants_meta":{"raw":{"variants":["Large fields don't rescue algebraic proofs from exponential lower bounds","Positive characteristic: exponential IPS lower bounds for large fields","Constant-depth IPS proves symmetric cases but exponential gaps persist elsewhere","Reciprocal lemma yields tight IPS bounds over positive characteristic","Exponential lower bounds for IPS over large positive characteristic fields"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001251,"raw_usage":{"total_tokens":5219,"prompt_tokens":1128,"completion_tokens":4091,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":744,"completion_tokens_details":{"reasoning_tokens":4011}},"tokens_in":744,"tokens_out":4091,"duration_ms":30298,"temperature":1.0,"reasoning_tokens":4011,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:26:44.708964+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $n=3$, set $S = \\mathbb{F}_8$ and $F' = \\mathbb{F}_{64}$, fix any $\\beta \\in \\mathbb{F}_{64} \\setminus \\mathbb{F}_8$, and enumerate all $8^3 = 512$ coefficient vectors $\\alpha \\in S^3$. For each, compute the unique multilinear polynomial agreeing with $1/(\\sum_{i=1}^3 \\alpha_i x_i - \\beta)$ on the Boolean cube. If fewer than 64 of the 512 polynomials have full degree 3, Lemma 2.2's probability bound is violated and the lower-bound arguments collapse.","supporting_citations":[],"review_version":1}