Alphabeta Math
CounterexampleConstruction: AI-generatedVerification: 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.

A symmetrized acceptance polynomial can exceed one between Hamming layers

Statement refuted

False claim: if an acceptance polynomial takes values in [0,1] on the Boolean cube, then its symmetrized univariate polynomial takes values in [0,1] at every real t between 0 and N.

Facts & Assumptions

Given: The two-bit local query model and the finite permutation average of Symmetrizing a Boolean-cube polynomial gives a Hamming-weight polynomial.

[F1]

Oracle-only bit-query algorithm: a local bit-query algorithm starts independently of the oracle input, can measure with finite instruments, and accepts according to a fixed output subset.

[F2]

Standard bit-flip query convention: at the one-hot address ei, one XOR query toggles its target by the bit xi.

[F3]

Acceptance polynomials and approximate degree on Boolean domains: the acceptance probability on the Boolean cube is represented by a real polynomial.

[F4]

Symmetrizing a Boolean-cube polynomial gives a Hamming-weight polynomial: the average over coordinate permutations gives the univariate polynomial matching the average values on each Hamming-weight layer.

[F5]

The Pauli matrices: in the ordered qubit basis, X=(0110) toggles the computational-basis bit.

Counterexample

1.1givenF1F2F5construct

The Pauli X in [F5] toggles a basis bit and is a fixed unitary because it permutes the two basis vectors. Start at the all-zero address, target, and two-bit output register. In the first round, apply X to the first address bit to set the address to e0, query and measure the target; since it began at zero, the outcome is deterministically x0 by [F2]. If the outcome is 1, apply X to the first output bit and to the target; if it is 0, leave both unchanged. This copies the result and resets the target. Apply X to both address bits to change e0 into e1; repeat the query and measurement, copying the second outcome into the second output bit and resetting the target in the same way. Every outcome-controlled operation is a fixed unitary on its branch by [F1] and [F5]; the output is deterministically (x0,x1). This finite tree uses exactly two queries. Accept on the fixed subset {00,01,10}, so the algorithm computes NAND.

2.1step 1.1F3algebra

The resulting acceptance polynomial is p(X0,X1)=1−X0X1: its values are 1,1,1,0 at 00,01,10,11, respectively, exactly the NAND acceptance law. In particular it lies in [0,1] on the Boolean cube.

3.1step 2.1F4algebra

Averaging p over the two coordinate permutations leaves its constant term 1 fixed and sends X0X1 to itself. By [F4], the associated Hamming-weight polynomial is q(t)=1−(t2)=1−t(t−1)/2, since it takes values 1,1,0 at weights 0,1,2.

4.1step 3.1algebra∎

At the noninteger point t=1/2, q(1/2)=1−((1/2)(−1/2))/2=9/8>1. Thus the symmetrized polynomial is not constrained to remain in [0,1] between integer Hamming weights, refuting the claim.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

25 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