Research · Papers · Exact answers in open problems · MF-193
Contraction censuses and lifting obstructions for CW(112,36)
CW(112,36) contractions: m=7 has 21 (2 orbits), m=8 has 96 (6), m=14 has 126 (3), m=16 has 1152 (24), m=28 has 420 vectors (4 orbits).
Published 2026-09-06
For everyone
Plain summary
A circulant weighing matrix is a circular sequence of 1s, -1s, and 0s that has zero correlation with every non-trivial shift of itself. Whether one exists for length 112 with 36 non-zero entries—known as CW(112,36)—is a long-standing open problem. A standard way to probe candidate sequences is modular compression: summing entries over regular step sizes to build smaller sequences at cyclic lengths like 7, 8, 14, 16, and 28.
This work gives complete censuses of all valid compressed integer sequences for all five divisors without assuming symmetry multipliers. A structural arithmetic barrier proves that several compressed patterns at lengths 14 and 28 can never lift to a full 112-element solution. Table 9 of Arasu-Gordon-Zhang 2021 previously reported the orbit count for length 7 under multiplier assumptions; the multiplier-free counts and lifting barriers here are new. Whether CW(112,36) exists remains open.
Result
Let a = (a_0, a_1, ..., a_111) ∈ {-1, 0, 1}^112 be a candidate first-row sequence for CW(112,36), normalized to sequence sum 6, 21 entries equal to +1, 15 entries equal to -1, and zero periodic autocorrelation at all 111 non-trivial shifts. For divisor m of 112, the m-contraction b = (b_0, b_1, ..., b_(m-1)) with
b_j = sum_{i ≡ j (mod m)} a_i
satisfies sum_{j=0}^{m-1} b_j = 6, sum_{j=0}^{m-1} b_j^2 = 36, and zero periodic autocorrelation over Z_m.
The exact vector counts and orbit counts under Aff(Z_m) across all five intermediate divisors are:
- Modulus m = 7: 21 vectors in 2 orbits.
- Modulus m = 8: 96 vectors in 6 orbits.
- Modulus m = 14: 126 vectors in 3 orbits.
- Modulus m = 16: 1152 vectors in 24 orbits.
- Modulus m = 28: 420 vectors in 4 orbits (all 4 orbits share the class-sum multiset {-3, 3, 3, 3, 0^24}).
A 2-adic lifting obstruction blocks full-length realization: exactly 1 of the 3 mod-14 orbits and 2 of the 4 mod-28 orbits admit no lift to length 112.
Setting and definitions
A circulant weighing matrix CW(n, k) is an n × n circulant matrix W with entries in {-1, 0, 1} satisfying W W^T = k I_n. Equivalently, its first row a ∈ {-1, 0, 1}^n satisfies sum_{i=0}^{n-1} a_i^2 = k and periodic autocorrelation
sum_{i=0}^{n-1} a_i a_{(i+s) mod n} = 0 for all s ∈ {1, 2, ..., n-1}.
For CW(112,36), sequence negation fixes the weight profile at 21 entries of +1, 15 entries of -1, and sum_{i=0}^{111} a_i = 6.
An m-contraction projects a onto Z_m by summing coordinates along residue classes mod m. Contraction orbits are orbits under the affine group Aff(Z_m) = {x ↦ u x + v | u ∈ Z_m^×, v ∈ Z_m}.
Method
Contraction vectors were enumerated with two independent engines:
- Signed recursive backtrack search over integer partitions constrained by periodic autocorrelation.
- A lift tower reconstructing composite modular projections from prime-power contractions.
Both implementations produced identical counts for m ∈ {7, 8, 14, 16, 28}. The lift tower identified the lifting kill by tracking projection compatibility along 2-adic towers, an obstruction invisible to direct modular SAT encodings.
Artifacts and search harnesses reside in lanes/cwm-112-36/BANK-CANDIDATES.md (candidate set CWM-02), VERIFY.md, and invent/ in frontier/cwm/.
Discussion
Arasu-Gordon-Zhang 2021 (Table 9) reported the 2 orbits for m = 7 under numerical multiplier assumptions. The census here proves this count without multiplier assumptions and establishes exact counts for m ∈ {8, 14, 16, 28}.
The 2-adic obstruction eliminates 1 of 3 mod-14 orbits and 2 of 4 mod-28 orbits from consideration for CW(112,36). The existence of CW(112,36) itself remains unsettled (see register entry ML-093).
For everyone — the takeaway
What this means
Testing whether an unknown combinatorial object exists often starts by looking at smaller projections, which act like low-resolution shadows. This work provides an exhaustive catalog of these shadows for CW(112,36) across five divisor scales.
An arithmetic obstacle prevents several of these candidate shadows from ever expanding into a full 112-entry sequence. Pruning them cuts down the remaining search space for CW(112,36) and constrains future searches in design theory.
Attribution and prior art
Prior art: The orbit count 2 for m = 7 was previously reported in Arasu-Gordon-Zhang (2021, Table 9) under a multiplier assumption. The multiplier-free counts presented here are newly verified without that assumption. Sources: Arasu, Gordon, Zhang 2021 (Cryptogr. Commun.) · Tan 2026 · Gordon, circulant weighing matrices table
Register references
- Register entry: MF-193
- Related register entry: ML-093
- Receipt artifacts:
lanes/cwm-112-36/BANK-CANDIDATES.md(CWM-02),VERIFY.md,invent/in boxfrontier/cwm/ - Prior art: Arasu, Gordon, and Zhang (2021), Table 9
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 2 of 2 receipt files bundled (16 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.
- 2026-09-06Independent verification confirms all census counts (m = 1, 2, 4, 7, 8, 14, 16, and mod-28). Clarifying earlier notes, the 2-adic structural kill is a corollary of MF-196, and while only 48 of 1152 ICW(16) vectors are all-even, all 1152 contract to the 24 all-even ICW(8) vectors.