Alphabeta Math
ExampleConstruction: AI-generatedVerification: AI-adaptedPipeline-generatedprecheck passaudited 2026-09-30
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 single equality edge through robust composition

Example

Let G be the graph with two vertices v,w, alphabet {0,1} and the single edge e=(v,w) carrying the equality relation Re={(0,0),(1,1)}. For the satisfying labeling (1,1) both endpoint blocks are set to WH⁡1(1)=(0,1), the edge circuit accepts, every constraint of the composed tester gadget can be satisfied, and the binary-star conversion of that gadget has zero violated edges. The graph G itself also has value one and unsatisfaction zero.

Facts & Assumptions

Given: The two-vertex, one-edge equality graph G, its value-one labeling σ(v)=σ(w)=1, the code of Shared codeword blocks and edge acceptance circuits, and the composition H=G∘P of Composition of an edge system with an assignment tester.

[F1]

For u∈F2n, the Walsh–Hadamard table is indexed lexicographically by masks r∈F2n and evaluates r↦u⋅r; in dimension one the masks are 0,1. (Walsh–Hadamard encoding and relative Hamming distance)

[F2]

For the alphabet {0,1} of size W=2, the code uses k=⌈log⁡2W⌉=1 and ℓ=2k=2: the first two codewords are C(0)=WH⁡1(0)=(0,0) and C(1)=WH⁡1(1)=(0,1). The edge circuit accepts exactly the pairs of valid blocks whose decoded labels lie in the edge relation, with loops tested diagonally. (Shared codeword blocks and edge acceptance circuits)

[F3]

Graph value is the maximum satisfied edge fraction; for a graph with at least one edge a labeling has value one exactly when it satisfies every edge relation. (Constraint graph and labeling value)

[F4]

For the composition H=G∘P, if val⁡(G)=1 then val⁡(H)=1, with value one on an empty constraint list. (Composition preserves perfect satisfiability)

[F5]

If E(G)≠∅, every edge of G contributes exactly M constraints of H, where M=lcm⁡{qe} over the positive local gadget sizes; with a single edge M=qe and each local constraint is copied once. (Composition of an edge system with an assignment tester)

[F6]

The conversion of a Boolean constraint system into a binary graph has perfect completeness: a labeling satisfying every input constraint extends to a graph labeling satisfying every output edge. It creates at most q edges per listed constraint. (Bounded-arity Boolean constraints become binary graph constraints)

Verification

technique · direct calculation
1.1F1F2givenalgebra

By [F1] the dimension-one table is evaluated at masks 0 and 1, so WH⁡1(1)=(1⋅0, 1⋅1)=(0,1) with length ℓ=21=2, in agreement with the code selection of [F2].

1.2F3givenalgebra

The labeling σ(v)=σ(w)=1 is a graph labeling, and its ordered endpoint pair (1,1) lies in Re={(0,0),(1,1)}; since the equality edge is the only edge, val⁡σ(G)=1 and val⁡(G)=1, so UNSAT⁡(G)=0 by [F3].

2.1F1F2step 1.1step 1.2algebra

The block assigned to both endpoints is Bv=Bw=C(1)=(0,1) by [F2]. Both blocks are valid codewords and decode uniquely to the labels 1,1, whose ordered pair lies in Re; hence the robust edge circuit accepts the displayed input by [F2].

2.2F4F5step 1.2algebra

Since val⁡(G)=1, [F4] gives val⁡(H)=1: some assignment to the variables of H satisfies every constraint of H. By [F5], the single edge contributes M=qe constraints, namely the constraints of the local two-piece tester copied once each; therefore one assignment satisfies every tester gadget constraint simultaneously.

3.1F6step 2.2algebradischarge-construct∎

Apply the conversion of [F6] to H. The satisfying assignment of step 2.2 extends to a labeling of the output graph that satisfies every output edge, so the output has value one and unsatisfaction zero: the number of violated edges is 0. The conversion creates at most 6M edge records and uses the fixed 66-symbol alphabet {B(0),B(1)}⊔{0,1}6, so this is a concrete instance of the composition and conversion maps with no random or infinite selection anywhere.

Remarks

This is the smallest nontrivial instance of the completeness direction of Composition preserves perfect satisfiability: a satisfiable one-edge graph over the two-symbol alphabet, whose block code has length two. It illustrates that the composition and the binary-star conversion reproduce a satisfying labeling rather than merely preserving a value bound. The numeric verification uses only the displayed dot products and the two listed relation pairs; no claim is made about rejection probabilities, which require the separate soundness direction.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

13 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