Alphabeta Math
LemmaStatement: Literature-sourcedProof: AI-generatedPipeline-generated
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.

Nonconstant Boolean functions have adversary value at least one

Statement

If f is nonconstant, then Adv⁡±(f)≥1. In particular the finite optimal adversary value A used by the reflection evaluator may be taken with A≥1.

Facts & Assumptions

Given: A finite nonconstant Boolean function f.

[F1]

General adversary matrix and spectral bound: admissible Γ are nonzero real symmetric and vanish on equal-output pairs.

[F2]

Input-mismatch masks and entrywise filtering: Δ_i marks the coordinates on which two inputs differ.

[F3]

The operator norm is zero on the zero domain and otherwise is max_{||v||=1} ||Tv||: the off-diagonal two-point swap matrix has norm one.

Proof

1.1givenF1F2construct

Choose x,y∈D with f(x)≠f(y). They are distinct bit strings, so x_i≠y_i for at least one i. Set Γ_{xy}=Γ_{yx}=1 and every other entry to zero. This Γ is nonzero and real symmetric; its only nonzero entries join opposite outputs, so Γ∘F=0.

2.1givenF2F3step 1.1algebra∎

The restriction of Γ to span{|x⟩,|y⟩} is [[0,1],[1,0]], whose eigenvalues are ±1; hence ||Γ||=1. For every i, Γ∘Δ_i is either Γ or zero, and at least one differing coordinate gives Γ itself. Thus max_i||Γ∘Δ_i||=1 and the ratio is one.

Depends on

Used by

Dependency tree · two levels

6 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