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.

✓ 3 results · all verified · 2 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 1 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Randomized Complexity and Amplification: Examples and Counterexamples

1 · Prerequisites

2 · Summary

These examples instantiate the three main computational lessons of the page: how a concrete majority vote inherits an explicit Chebyshev error bound, how a single random evaluation witnesses the coRP behavior of PIT, and why reusing one coin string destroys the independence that amplification needs.

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12Open item page →

A concrete majority-vote error estimate from Chebyshev's inequality

Example

If $25$ independent trials are each correct with probability $3 / 4$ , then the majority vote is wrong with probability at most $9 / 25$ .

Facts & Assumptions

Given: $25$ independent Bernoulli trials, each correct with probability $3 / 4$ .

[L1]

The Chebyshev majority bound gives $P (S \leq k / 2) \leq 9 / k$ whenever each trial has success probability at least $2 / 3$ (Chebyshev bounds the majority error of repeated Bernoulli trials).

Verification

technique · direct

1.1L1given

The hypotheses of [L1] hold with $k = 25$ because $3 / 4 \geq 2 / 3$ .

2.1L1step 1.1algebra∎

Therefore the majority error probability is at most $9 / 25$ . This is a concrete instance of the general $O (1 / k)$ estimate.

ExampleConstruction: AI-generatedVerification: AI-generatedprecheck passaudited 2026-09-12Open item page →

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.1givenalgebra

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)$ .

2.1L1L2L3step 1.1algebra∎

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.

CounterexampleConstruction: AI-generatedVerification: AI-generatedprecheck passjudge pass (gpt-5.6-terra)audited 2026-09-12Open item page →

Repeating a randomized test with the same coin string gives no amplification

Statement refuted

Reusing the same random bits amplifies success.

Facts & Assumptions

Given: a randomized test whose output depends only on its first random bit.

[L1]

The false statement being refuted is exactly the claim above (FALSE: reusing the same random bits amplifies success).

Counterexample

technique · direct

1.1L1given

Consider the randomized test that accepts exactly when its first random bit is $1$ . Its success probability is $1 / 2$ , so it is a legitimate witness against the statement in [L1] if repetition with the same randomness leaves that probability unchanged.

2.1step 1.1algebra∎

If the same random string is reused in two, ten, or one hundred repetitions, every repetition produces the same answer as the first one. So the majority outcome is still accept with probability $1 / 2$ and reject with probability $1 / 2$ . No amplification occurs at all, and the statement is refuted.

Randomized Complexity and Amplification: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

A concrete majority-vote error estimate from Chebyshev's inequality

Example

Facts & Assumptions

Verification

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

Example

Facts & Assumptions

Verification

Repeating a randomized test with the same coin string gives no amplification

Statement refuted

Facts & Assumptions

Counterexample

Sources