ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 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.

A random evaluation test that separates the zero polynomial from x^2-y^2

Example

Take the polynomial $f (x, y) = x^{2} - y^{2}$ over $Q$ , and sample uniformly from the grid $S \times S$ with $S = {0, 1, 2}$ . Then $f$ vanishes on exactly three of the nine grid points, so one random evaluation misses its nonzeroness with probability $1 / 3$ .

Facts & Assumptions

Given: the polynomial $f (x, y) = x^{2} - y^{2}$ and the sample set $S = {0, 1, 2}$ .

[L1]

PIT tests whether a represented polynomial is identically zero by random evaluation in an admissible representation (Polynomial identity testing).

[L2]

The Schwartz-Zippel lemma bounds the vanishing probability of a nonzero polynomial on a finite grid (The Schwartz-Zippel lemma).

[L3]

Under the usual degree and evaluation assumptions, PIT lies in coRP (Polynomial identity testing is in coRP).

Verification

technique · direct

1.1

The equality $x^{2} - y^{2} = 0$ on $S \times S$ is equivalent to $x = y$ because all elements of $S$ are nonnegative rationals and squaring is injective there. Hence the roots on the grid are exactly $(0, 0)$ , $(1, 1)$ , and $(2, 2)$ .

givenalgebra

2.1

So a random point of $S \times S$ makes $f$ vanish with probability $3 / 9 = 1 / 3$ . This is consistent with [L2], since the total degree is $2$ and $2 / ∣ S ∣ = 2 / 3$ . Using the random-evaluation viewpoint from [L1], this is exactly the one-sided coRP behavior asserted in [L3], because the zero polynomial would vanish on every sample point.

L1L2L3step 1.1algebra∎

Depends on

Used by

Nothing in the library uses this result yet.

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)