Quantum and CircuitsReading edition

The finite evaluation-span dual in full

Reading tools
Reading libraryFind statementsInspect Lean
Switch work

Saved reading

Read side by side

Start reading

Resources & source

Original TeX with line links · Download TeX

The wording and mathematics follow the retained manuscript. This reading format does not add a proof review or extend Lean coverage.

Skip contents and start reading

The finite evaluation-span dual in full

Fix a positive \(v\) and integer \(d\ge0\). Let

\[ v_d(x)=(x^S)_{S\subseteq[n],\ |S|\le d},\qquad U=f^{-1}(0),\qquad N={\operatorname{span}}_{{\mathbb F}_2}\{v_d(u):u\in U\}. \]

The constant monomial \(S=\varnothing\) is included. Degree-\(d\) coefficient covectors form the finite dual of this evaluation space. A covector is safe exactly when it annihilates \(N\).

If \(v_d(v)\in N\), every safe covector vanishes at \(v\). If \(v_d(v)\notin N\), extend a basis of \(N\) by \(v_d(v)\) and then to a basis of the full space. Assign zero to the \(N\) basis and one to \(v_d(v)\). The resulting covector is a safe detector. Hence

\[ \boxed{\beta_v(f)>d\quad\Longleftrightarrow\quad v_d(v)\in N.} \]

Choose a basis of \(N\) from negative evaluation rows. A span representation of the positive row gives a subset \(W\subseteq U\) with

\[ v_d(v)=\sum_{u\in W}v_d(u),\quad |W|\text{ odd},\quad |W|\le\sum_{j=0}^{\min(d,n)}\binom nj. \]

It is a replayable finite obstruction to every safe degree-\(d\) detector.

At \(d=0\), a negative exists exactly when the constant-one detector is unsafe. At \(d\ge n\), the full evaluation rows are independent and no positive row lies in the negative span. This matches \(\beta_v\le n\) from point indicators. For \(f=0\), there is no positive \(v\) and the separate convention is \(\beta(0)=0\).

Fresh enumeration checked all 278 functions on zero through three inputs, all positives, and every \(d=0,\ldots,n\): 4,201 primal/dual checks agree. Those bounded checks support the independently supplied universal proof.

Source and conversion record

Source SHA-256: 488075fae27e7db2e4bcee68c08f93b659a12536c807e5e419d6e8e166317763

Unsupported prose commands stop the build. The mathematical expression sequence is checked against the source, with manuscript macros expanded for display.

Conversion records

Notation in Quantum and Circuits

Look up a symbol without leaving this chapter. Select text before opening help to search for it.

Search this work’s notation.

    Symbols can have different meanings in different passages. Read each result in its own context.

    Open the full notation index