CounterexampleConstruction: Literature-sourcedVerification: AI-generatedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

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.

Public-coin and private-coin SMP are different models

Statement

For each n≥1, a shared uniformly random pair r₁,r₂∈𝔽₂ⁿ lets Alice send (r₁·x,r₂·x) and Bob send (r₁·y,r₂·y); the referee accepts equality iff both bits match. Equal inputs always match and unequal inputs collide with probability 1/4. The shared seed has 2n bits and is a separately declared public resource; independent private seeds do not give this guarantee.

Facts & Assumptions

Given: Equality inputs $x, y \in F_{2}^{n}$ , where $n \geq 1$ .

[F1]

Equality communication problem: Equality requires output $1$ when $x = y$ and $0$ when $x \neq y$ .

[F2]

Finite communication problem and protocol model: Shared randomness is a separately declared resource, and transmitted bits are counted as communication.

Proof

technique · explicit construction and counterexample

1.1givenF1F2choosealgebra

Let public shared seeds $r_{1}, r_{2}$ be independent uniform vectors in $F_{2}^{n}$ . Alice sends $(r_{1} \cdot x, r_{2} \cdot x)$ and Bob sends $(r_{1} \cdot y, r_{2} \cdot y)$ ; the referee outputs equality exactly when both bits match. If $x = y$ , both match surely. If $z = x + y \neq 0$ , choose a coordinate $k$ with $z_{k} = 1$ ; flipping $r_{k}$ pairs seeds bijectively with opposite values of $r \cdot z$ , so each $r_{i} \cdot z$ is uniform, and independence gives collision probability $1 / 4$ . The protocol uses two transmitted bits per sender and a shared seed of $2 n$ bits, which [F2] keeps separate from communication.

2.1step 1.1F1algebra∎

If the parties instead use independent private seed pairs, take the equal input $x = y = e_{1}$ . Each sender's two-bit message is uniform on $F_{2}^{2}$ , independently of the other's, so the messages disagree with probability $3 / 4$ . This violates any bounded-error Equality guarantee such as error at most $1 / 3$ , showing that the common seed is doing real work.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 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

Ronald de Wolf, Quantum Computing: Lecture Notes, arXiv:1907.09415v6 (standard reference, not scraped)
Harry Buhrman, Richard Cleve, John Watrous, Ronald de Wolf, Quantum Fingerprinting (standard reference, not scraped)