CorollaryStatement: Literature-sourcedProof: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Polynomial identity testing is in coRP

Statement

For every PIT representation that permits polynomial-time evaluation and polynomial-time construction of a finite sample set $S \subseteq F$ with $∣ S ∣ \geq \max (1, 2 d)$ , where $d$ is the input's degree bound, the corresponding polynomial identity testing problem lies in coRP.

Facts & Assumptions

Given: a represented polynomial $f$ in a PIT model with a computable degree bound $d$ and a computable sample set $S$ satisfying $∣ S ∣ \geq \max (1, 2 d)$ .

[L1]

RP and coRP are the one-sided-error probabilistic classes (The classes RP, coRP, ZPP, BPP, and PP).

[L2]

PIT asks whether the represented polynomial is identically zero, and the representation supports polynomial-time evaluation at chosen points (Polynomial identity testing).

[L3]

A nonzero polynomial of degree at most $d$ vanishes on at most a $d / ∣ S ∣$ fraction of the points of $S^{n}$ (The Schwartz-Zippel lemma).

Proof

technique · direct

1.1

On input the representation of $f$ , compute its degree bound $d$ , compute the sample set $S$ , choose a uniformly random point of $S^{n}$ , evaluate $f$ at that point using [L2], and reject immediately if the value is nonzero; otherwise accept. The runtime is polynomial by the assumptions packaged into [L2].

L2givenconstruct

2.1

If $f$ is the zero polynomial, every evaluation is zero, so the algorithm accepts with probability $1$ . If $f$ is nonzero, [L3] gives $P (f (a) = 0) \leq d / ∣ S ∣ \leq 1 / 2$ . So on no-instances the algorithm rejects with probability at least $1 / 2$ .

L3step 1.1algebra

3.1

Step 2.1 is exactly the coRP condition from [L1]. Therefore PIT is in coRP for every representation satisfying the stated assumptions.

L1step 2.1∎

Depends on

Used by

A random evaluation test that separates the zero polynomial from x²-y² Example

Dependency tree · two levels

10 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
Eric Blais, Models of Computation, 15. P vs. BPP (standard reference, not scraped)