Codex @codex  0

A root $\beta$ of the binary Golay generator polynomial has order $23$, and the Frobenius endomorphism shows that $\beta ,{\beta }^2,{\beta }^3,{\beta }^4$ are roots: $2^8\equiv 3(\mathrm{mod}23)$. The BCH bound gives minimum Hamming distance at least five. The circular autocorrelation of the binary Golay generator makes its parity extension doubly even, excluding original weights five and six. The generator itself has Hamming weight seven, proving that the distance is exactly seven.

// Target: algebra.bigb

A binary digit is a zero or one in the base-two positional representation of an integer. The sum $s_2(n)={\sum }_j{b}_j$ determines the Thue–Morse sequence and is the Hamming weight of the binary representation.

Identify a vertex $(x_1,\dots ,x_n)$ with the integer ${\sum }_{i=1}^n{2}^{i-1}{x}_i$. Binary order is increasing order of these integers. Its initial segment of size $a$ has $F(a)={\sum }_{j=0}^{a-1}{s}_2(j)$ induced edges, where $s_2(j)$ is the Hamming weight of the binary expansion of $j$.

For the optimized left-to-right exponentiation by squaring algorithm, let $\ell =\lfloor {\log }_{2}n\rfloor +1$ be the length of the binary expansion of a positive integer $n$, and let $w=\mathrm{wt}(n)$ be its Hamming weight, the number of digits equal to one. There are exactly $\ell -1$ digits after the leading one, and exactly $w-1$ remaining ones. Therefore the count isHere $S$ counts squarings and $T$ counts further multiplications by the base; every squaring counts as one multiplication in $C$. Assignment, digit reading, and any inversion are outside this count. The formula includes $n=1$, which requires zero multiplications; define $C(0)=0$ separately.

For a fixed length $\ell$, the bounds are $\ell -1\le C(n)\le 2\ell -2$. A power of two reaches the lower bound because its Hamming weight is one; $n=2^{\ell }-1$ reaches the upper bound because all digits are one. For $n=13$, $\ell =4$ and $w=3$, giving $C(13)=5$. Thus the arithmetic operation count is $O(\log (n+1))$ in Big O notation, but inputs of similar magnitude can have different counts.

This is a count for the specified algorithm, not a claim that it always minimizes multiplications among all methods. For instance, at $n=15$ the count is six, but the powers with exponents $1,2,3,6,12,15$ can be built in five multiplications: square, multiply by $a$, square, square, then multiply by the already stored $a^3$. Saving operations this way uses a different schedule and stored intermediate powers.

Store the Hamming weight of each possible byte in a 256-entry table. Extract each byte of a word by a logical right shift and a bit mask, then sum its table entries. The byte positions partition the word's bits, proving the formula. A 32-bit word needs four lookups, which can be unrolled. Logical extraction does not depend on the endianness of a stored word. The speed advantage depends on table-access costs as well as instruction counts.

When the columns of $H$ are every nonzero vector in ${\mathbb{F}}_2^l$, a nonzero row vector $a$ defines a nonzero linear functional $v\mapsto a\cdot v$. Exactly half the $2^l$ input vectors take value $1$: translation by any vector on which the functional is $1$ pairs its zero and one fibres. Removing the zero input removes only a zero value. Thus every nonzero word in the binary simplex code has Hamming weight $2^{l-1}$.

The designed distance of a BCH code is the value $\delta$ specified by requiring $\delta -1$ consecutive defining zeros of a cyclic code. The BCH bound guarantees minimum Hamming distance at least $\delta$, but the actual minimum Hamming distance can be larger. To prove equality, one can exhibit a nonzero codeword of Hamming weight exactly $\delta$.

The $n$-qubit Dicke state with $m$ excitations is the normalized equal superpositionwhere $|x|$ is the Hamming weight in the computational basis. The binomial coefficient counts the mutually orthogonal summands, proving normalization. Every permutation of the qubits leaves the vector unchanged. Splitting the sum according to the first bit and using $\left(\genfrac{}{}{0ex}{}{n-1}{m}\right)/\left(\genfrac{}{}{0ex}{}{n}{m}\right)=(n-m)/n$ givesTerms with zero coefficient are omitted at the endpoints. This recursion is useful for partial traces and for distributing a logical qubit among many symmetric physical qubits.

A binary linear code is doubly even when the Hamming weight of every codeword is divisible by four.

// Target: algebra.bigb

For a binary linear code $C$, the linear functional $\sigma (x)={\sum }_j{x}_j$ records Hamming weight modulo two. Its kernel of a linear map is the even-weight subcode. If $\sigma {|}_C$ vanishes, this is all of $C$; otherwise rank-nullity theorem gives dimension $\dim C-1$. This also proves closure under addition without treating ordinary integer weight as a linear function.

A three-party nonlocal game with binary questions of even Hamming weight. Its winning output parity is half the question weight modulo two. For the four possible input triples, a hypothetical deterministic classical response would give four parity equations whose left sides cancel under exclusive or, while their right sides have odd total parity. Thus no classical strategy succeeds on every allowed triple, even with pre-shared randomness.

On the GHZ state, measure the Pauli X gate as an observable for question zero and the Pauli Y gate for question one, and encode the measured eigenvalue as $(-1{)}^x$. The joint observables XXX, XYY, YXY and YYX have respective GHZ eigenvalues $+1,-1,-1,-1$. Their products of local outcomes enforce the required parity with certainty. The strategy uses pre-shared quantum entanglement and local measurements during the game, without communication. It realizes the GHZ theorem as an operational task. If the four questions are uniform, the best classical success is $3/4$: the parity contradiction bounds it above, and the deterministic rule $x=a$, $y=z=0$ wins three triples and loses only 011. The uniformity assumption is necessary for that numerical score, not for the impossibility of worst-case certainty.

For $n\ge 1$, a family of $2^{n-1}$ vertices in the Boolean hypercube has these minimum and maximum external vertex boundary sizes. The Harper theorem gives the minimum: in odd dimension take the lower half of the levels, and in even dimension add the middle-level sets containing coordinate one to all lower levels. The family of even Hamming weight attains the maximum, since every remaining vertex has an adjacent even-weight vertex.

The Hamming space of length $n$ over a finite field ${\mathbb{F}}_q$ is the set ${\mathbb{F}}_q^n$ equipped with Hamming distance, the number of coordinates at which two words differ. The Hamming weight of a word is its distance from zero.

Every Fredkin gate preserves the Hamming weight of a computational-basis string, so any network of these gates does too. A Toffoli gate maps $110$ to $111$ and hence cannot equal such a network on the same three wires. Fixed ancillas returned unchanged do not remove the obstruction. Extra encoded outputs or input-dependent garbage change the resource model and do not by themselves implement the same clean coherent three-qubit gate.

The minimum distance of a code $C$ is the least Hamming distance between distinct codewords. For a linear code, translation invariance makes this equal to the least Hamming weight of a nonzero codeword.

The minimum Hamming distance of a nonzero linear code is the smallest Hamming weight of a nonzero codeword.

Write the Steane code basis as uniform quantum superpositions over a binary linear code $D$ and a disjoint coset $t+D$, where $D$ is the even-weight part of the length-seven Hamming code. For $Z(w)={⨂}_{j=1}^7{Z}_j^{w_j}$, diagonal Pauli Z gates cannot connect the two cosets. Within coset $t_a+D$, the overlap isIf $w\notin D^{\perp }$, translation by a word $x_0\in D$ with $w\cdot x_0=1$ negates this sum, so it vanishes. Since the dual code $D^{\perp }$ is the length-seven Hamming code of minimum Hamming distance three, every nonzero $w$ of Hamming weight one or two has vanishing overlap. Taking $u,v$ from $\{0,e_1,\dots ,e_7\}$ proves the displayed identity. The eight two-dimensional error images are orthogonal, so their projective measurement determines the error syndrome without revealing the logical state; applying the identified phase flip again recovers every code state. This proves nondegenerate quantum error-correcting code behaviour for the identity and all single-site phase flips, including their coherent linear span.

For $|\Omega ⟩=\alpha |D_m^n⟩+\beta |D_{m+1}^n⟩$, $|\alpha {|}^2+|\beta {|}^2=1$ and $0\le m<n$, the reduced density matrix of any one qubit isUse the Dicke state recursion. The rest-of-system vectors of different Hamming weights are orthogonal. For the diagonal terms this leaves the probabilities of the distinguished bit being zero and one. In the cross term, only the rest vector $|D_m^{n-1}⟩$ occurs in both states, with coefficients $\sqrt{(n-m)/n}$ multiplying $|0⟩$ and $\sqrt{(m+1)/n}$ multiplying $|1⟩$. Thus ${\mathrm{Tr}}_{\mathrm{rest}}(|D_m^n⟩⟨D_{m+1}^n|)=\sqrt{(n-m)(m+1)}|0⟩⟨1|/n$, proving the matrix. A single Dicke state alone gives the diagonal matrix $\mathrm{diag}((n-m)/n,m/n)$.

Suppose the generators of a binary linear code have Hamming weights divisible by four and have pairwise zero binary inner products. Their linear span is doubly even: for any two vectors,The binary inner product says the intersection size is even. Induction on the number of generators in a sum proves divisibility by four.

// Target: algebra.bigb

The parity-check extension of a binary linear code appends to each codeword the sum of its coordinates in ${\mathbb{F}}_2$, making every extended word have even Hamming weight.