Exact Fold-and-Lift Enumeration of Low-Weight Codewords in Quasi-Cyclic Codes with Circulant Size 𝐦𝟎 ⋅ 𝟐𝐋: Theory, Algorithms, Certificates and Verification

We give an exact method for enumerating every codeword of weight at most W in the kernel of a block matrix over S[x]/(xM+1), where S is a commutative GF(2)-algebra with a fixed basis and M = m0·2L. The class contains quasi-cyclic codes of any index, block-circulant matrices with several block rows, generalized and bivariate bicycle codes, and two-block group-algebra codes over abelian groups with a cyclic factor of order m0·2L. The method rests on x2m+1 = (xm+1)2 in characteristic two: the kernel folds onto half the length without increasing weight, and every low-weight word is recovered exactly from its fold. The paper proves the recursion in this generality, reduces it to one representative per symmetry orbit, specifies the lift step in full, proves every implementation step and the whole algorithm correct, gives a dimension formula (k = 2 deg gcd(ru, rv, xm+1) for two-block CSS codes) and a certified-distance procedure for CSS codes, degenerate ones included, with certificates checkable by a proof assistant, and a random-code heuristic that predicts where the cost concentrates. A worked [[24,4,4]] example and a case study at length 832 are included: the method certifies d = 15 for a [[832,10]] code in about one second per sector, three separately written implementations agree, and the dimension formula explains the whole tower and proves k = 10. Code. The reference implementation, the tests and the example scripts are in the companion record doi:10.5281/zenodo.23466024. Related records. Case study paper v2.1: doi:10.5281/zenodo.23466181 (version 1.0: doi:10.5281/zenodo.23327681). Verification bundle 1.2.2: doi:10.5281/zenodo.23463892. License. CC BY 4.0. Copyright (c) 2026 Guillaume Lessard.