Research · Papers · Exact answers in open problems · MF-196
Residue-class parity theorem for circulant weighing matrices
For CW(n=2^e q, k) with q odd, e ≥ 1, k even: support S in F_2[Z_n] satisfies (x+1)^(2^(e-1)) | S, so S mod (x^(2^(e-1)) - 1) = 0
Published 2026-09-06
For everyone
Plain summary
A circulant weighing matrix is a square grid where each row shifts the row above it by one step, every entry is 0, 1, or -1, and distinct rows are orthogonal. Its weight is the number of nonzero entries per row. When both the grid size and weight are even, these nonzero entries follow a strict parity rule: writing the dimension as 2^e q with odd q and e >= 1, the nonzero entries distribute evenly across every residue class modulo 2^(e-1).
This rule rules out candidate configurations before starting a search. Related 2-adic and parity methods appear in papers by Arasu, Leung, Ma, and Schmidt, though this exact residue-class statement has not been verified in prior publications.
Result
Let CW(n,k) denote a circulant weighing matrix of order n and weight k, with n = 2^e q, q odd, e >= 1, and k even. Let A in Z[Z_n] represent the first row of CW(n,k), and let S = A mod 2 in F_2[Z_n] be its support.
Then (x+1)^(2^(e-1)) divides S in F_2[Z_n], which implies:
S mod (x^(2^(e-1)) - 1) = 0
Equivalently, every residue class modulo 2^(e-1) contains an even number of nonzero entries in the first row.
For CW(112,36), where n = 112 = 2^4 * 7 (e = 4) and k = 36, the modulo-8 contraction of the support is even in every coordinate.
Setting and definitions
A circulant weighing matrix CW(n,k) is an n x n circulant matrix with entries in {-1, 0, 1} satisfying M M^T = k I_n. Representing the first row as A(x) = sum_(i=0)^(n-1) a_i x^i in Z[Z_n] = Z[x]/(x^n - 1), the matrix equation is:
A(x) A(x^(-1)) = k in Z[x]/(x^n - 1)
The support polynomial S(x) in F_2[Z_n] is S(x) = sum_(i=0)^(n-1) (a_i mod 2) x^i, with involution S*(x) = S(x^(-1)).
Method
The proof evaluates the local structure of F_2[Z_n]:
- Reduction modulo 2: Reducing A(x) A(x^(-1)) = k modulo 2 gives S(x) S*(x) = 0 in F_2[Z_n], as k is even.
- Local decomposition: Over F_2, x^n - 1 = (x^q - 1)^(2^e). F_2[Z_n] decomposes into a direct product of local rings F_2[x]/(f(x)^(2^e)) for each irreducible factor f(x) of x^q - 1, each with nilpotency index 2^e.
- Valuation invariance: Because q is odd, f(x) = x + 1 is an irreducible factor of x^q - 1 of multiplicity 1. The involution x -> x^(-1) preserves the (x+1)-adic component via x^(-1) + 1 = x^(-1)(1 + x), which shares the valuation of x + 1.
- Valuation inequality: The identity S S* = 0 forces 2 v_(x+1)(S) >= 2^e, giving v_(x+1)(S) >= 2^(e-1).
- Residue-class vanishing: Over F_2, (x + 1)^(2^(e-1)) = x^(2^(e-1)) + 1 = x^(2^(e-1)) - 1. Thus (x^(2^(e-1)) - 1) divides S(x), and S(x) vanishes modulo x^(2^(e-1)) - 1.
The theorem was found independently by Conway ("Theorem A") and Hilbert ("T2") and re-proved by a clean-room verifier. Checking Gordon's table produced zero violations across all 21 witness matrices with 8 | n and even k.
Receipts:
lanes/cwm-112-36/verify-invent/VERDICTS.mdinvent/conway.mdinvent/hilbert.mdreceipts/cwm.json
Discussion
The theorem provides an algebraic filter on the support of any CW(n,k) with even weight k and order n = 2^e q.
For CW(112,36), projecting any valid row support onto Z_8 requires an even count in all 8 residue classes. This eliminates 8 of the 12 candidate contraction cubes without invoking a SAT solver.
Prior art notes: Parity arguments and 2-adic valuation bounds for CW(2^e q, k) appear throughout work by Arasu, Leung, Ma, and Schmidt. Whether this exact residue-class parity formulation appeared previously remains unverified.
For everyone — the takeaway
What this means
When an even-sized circulant weighing matrix has an even number of nonzeros per row, those nonzeros cannot land randomly. They divide into equal-parity bins across modular slices of the row. Search pipelines can use this property to discard impossible row patterns immediately.
Attribution and prior art
Prior art: Prior work by Arasu, Leung, Ma, and Schmidt contains parity and 2-adic results for CW(2^e q, k). However, it remains unverified whether this exact residue-class statement appears in their published literature. Sources: Arasu, Gordon, Zhang 2021 · Gordon, circulant weighing matrices table
Register references
- Entry ID: MF-196
- Receipts:
lanes/cwm-112-36/verify-invent/VERDICTS.md,invent/conway.md,invent/hilbert.md,receipts/cwm.json - Prior art: Arasu / Leung / Ma / Schmidt literature; Gordon's table (empirical verification on 21 witnesses)
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 4 of 4 receipt files bundled (127 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.