Alphabeta Math
TheoremStatement: 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.

Boolean-output filtered γ₂ equals the general adversary value

Statement

For every finite nonconstant partial Boolean function, γ2(J−F∣Δ)=Adv⁡±(f). Here F is the same-output mask, J is all ones, and Δ is the family of input-mismatch masks. The equality is exact for Boolean outputs; no larger-alphabet factor is asserted.

Facts & Assumptions

Given: A finite nonconstant partial Boolean function and its output and mismatch masks.

[F1]

Filtered γ₂ factorization norm for query mismatch masks: γ₂(J−F|Δ) is the minimum factorization cost for the all-pairs constraints with target J−F.

[F2]

Finite-dimensional well-definedness of the filtered γ₂ program: this finite factorization program is feasible and attained when its target has zero diagonal.

[F3]

General adversary matrix and spectral bound: Adv± uses real symmetric matrices supported on opposite-output pairs.

[F4]

Dual vector formulation of the general adversary bound: Adv± equals the attained minimum vector-certificate cost with right side J−F.

[F5]

Entrywise products of finite positive semidefinite matrices are positive semidefinite: entrywise products of finite PSD Gram matrices remain PSD.

Proof

1.1givenF1F2F3algebra

For A=J−F, the defining factorization equations for γ₂(A|Δ) are exactly Σ_{i:x_i≠y_i}⟨u_{x,i}|v_{y,i}⟩=1 for opposite outputs and 0 for equal outputs. The target has zero diagonal, so [F2] gives a finite attained value.

2.1givenF1F4step 1.1

The dual-vector theorem [F4] gives the minimum of precisely these equations and the same maximum row/column squared-norm cost. Its single-family form has cost max{C_0,C_1}. Assigning u_{x,i}=w_{x,i} and v_{y,i}=w_{y,i} for every input gives a factorization of identical cost, while the dual-vector proof constructs the single family by taking the row family on D_0 and the column family on D_1, then applying the Boolean output-label code. Therefore the two minima coincide and equal Adv±(f).

3.1givenF4F5step 2.1∎

In the equivalent cross-output-only formulation, tensoring by the two-code label yields equal-output zeros while preserving cross-output constraints. The associated label Gram matrix is PSD, and [F5] confirms its entrywise product with each original Gram matrix is PSD; thus this equivalent realization remains a valid finite Gram factorization with unchanged vector norms. The Boolean output alphabet makes the label inner product exactly 1 on required cross-output mismatches and 0 on same-output mismatches, so there is no output-size loss factor.

Depends on

Used by

Dependency tree · two levels

27 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