C-30

Evidence

The proof has two parts. First, a hypothetical additive code produces a binary 16-divisible code of effective length 77, dimension at most eight, and maximum column multiplicity at most eleven. Second, we show from published classification counts that every such divisible code has a column of multiplicity at least sixteen.

1. Reduction to a divisible binary code.

Let V=F_2^8. An additive F_8 code with 256 codewords has binary dimension eight. After choosing a binary basis of F_8, its generator matrix has eight rows and 88 blocks of three columns. Let U_j <= V be the span of block j, so dim(U_j)<=3.

We may enlarge every U_j to a three-dimensional subspace and use a basis of the enlarged subspace as the new block. For each message x, the new block is zero only if the old block was zero. Thus this operation cannot decrease any nonzero message's Hamming weight and preserves injectivity. Consequently, it suffices to exclude 88 three-dimensional subspaces U_j with the required distance.

For each nonzero x in V, define

  a(x) = #{j : U_j <= x^perp},
  T(x) = 11-a(x),

where x^perp={v in V : x dot v=0}.

The codeword corresponding to x has weight 88-a(x). Minimum distance at least 77 therefore gives a(x)<=11, and hence

  0 <= T(x) <= 11.

Every three-dimensional U_j is annihilated by exactly 2^(8-3)-1=31 nonzero vectors x. Therefore

  sum_{x != 0} T(x)
    = 255*11 - 88*31
    = 77.

For v != 0, put m(v)=#{j : v in U_j}. If v belongs to U_j, no vector x annihilating U_j has x dot v=1. If v does not belong to U_j, exactly half of the 32 vectors of U_j^perp have x dot v=1, namely sixteen. Thus

  sum_{x : x dot v=1} a(x) = 16*(88-m(v)),

and consequently

  sum_{x : x dot v=1} T(x)
    = 128*11 - 16*(88-m(v))
    = 16*m(v).

Form a binary generator matrix by taking each nonzero vector x as a column repeated T(x) times. It has effective length 77, rank at most eight, and every codeword weight is divisible by sixteen. Its maximum column multiplicity is at most eleven.

2. The published classification input.

Theresa Körner and Sascha Kurz, "Lengths of divisible codes with restricted column multiplicities", Advances in Mathematics of Communications 18(2) (2024), 505-534, DOI 10.3934/amc.2023050; arXiv:2303.17172v2, Appendix B, Table 5, gives these numbers of equivalence classes of binary 16-divisible codes of effective length 77:

  dimension k:       5   6   7   8
  number of classes: 2   5   8   6

Appendix B identifies the entries as enumeration counts of semilinearly inequivalent linear codes. Over F_2, the field automorphism is trivial. Repeated nonzero columns are allowed.

No dimension below five is possible independently of the table: in a binary full-length [77,k] code, the sum of all codeword weights is 77*2^(k-1). If every weight is divisible by sixteen, then 16 divides 77*2^(k-1), forcing k>=5.

We now construct 2,5,8,6 pairwise inequivalent examples in dimensions 5,6,7,8, respectively, all with maximum column multiplicity at least sixteen. Matching the published counts will prove that they exhaust the relevant classes.

For clarity, a point multiset M assigns a nonnegative integer multiplicity M(p) to each nonzero binary vector p. Its length is sum_p M(p), its rank is the dimension spanned by its positive-multiplicity points, and its weight under a linear functional ell is sum_{ell(p)=1} M(p).

3. Four standard length-61 multisets.

For r=1,2,3,4, take V_r=F_2^(9-r) with standard basis e_1,...,e_(9-r), and set

  A = span(e_1,...,e_5),
  B = span(e_1,...,e_r,e_6,...,e_(9-r)).

The second list after e_r is empty when r=4. Thus dim(A)=5, dim(B)=4, dim(A intersect B)=r, and A+B=V_r.

Define

  M_r(p) = 1_{p in A\{0}} + 2*1_{p in B\{0}}.

Then M_r has length

  (2^5-1) + 2*(2^4-1) = 31+30 = 61,

rank 9-r, and maximum multiplicity at most three.

Every linear functional has weight either zero or sixteen on the first summand, and either zero or sixteen on the second summand. Therefore M_r is 16-divisible.

For r=4, the multiplicities attained at nonzero points of V_r are 1 and 3.

For r=1,2,3, the attained multiplicities are 0,1,2,3. These occur, respectively, outside A union B, in A\B, in B\A, and in (A intersect B)\{0}. All four regions are nonempty.

4. One additional length-61 multiset of rank seven.

Write V_*=F_2^4 direct_sum W, where dim(W)=3, and let

  E={e_1,e_2,e_3,e_4,e_1+e_2+e_3+e_4} <= F_2^4

denote this five-element set, not its linear span.

Define M_* by giving:

  multiplicity 3 to (0,w) for each nonzero w in W;
  multiplicity 1 to (e,w) for each e in E and each w in W;
  multiplicity 0 to all other nonzero vectors.

Its length is 3*7+5*8=61, and it spans dimension seven.

To check 16-divisibility, consider a functional ell on V_*.

If ell is nonzero on W, its weight is

  3*4 + 5*4 = 32.

If ell vanishes on W, its weight is eight times the number of points of E on which its F_2^4 component is one. If that component has t nonzero entries, the latter number is

  t + (t mod 2),

which belongs to {0,2,4}. The resulting weight is therefore 0,16, or 32.

The multiplicities attained inside V_* are 0,1,3. Moreover, M_* is inequivalent to the other rank-seven residual M_2: M_* has seven points of multiplicity three, whereas M_2 has only 2^2-1=3 such points.

5. Constructing and distinguishing the length-77 examples.

For any multiset M above and any nonzero point P, form

  M + 16[P],

where [P] is one copy of P. This has length 77 and remains 16-divisible, since a functional's weight changes by either zero or sixteen.

For each distinct multiplicity attained at a point inside span(M), choose one such P. Also, when rank(M)<=7, choose one P outside span(M), in a one-dimensional extension of that span.

This produces the following counts:

  residual        dimension 5   dimension 6   dimension 7   dimension 8
  M_4                  2             1             0             0
  M_3                  0             4             1             0
  M_2                  0             0             4             1
  M_1                  0             0             0             4
  M_*                  0             0             3             1
  TOTAL                2             5             8             6

Here an inside point preserves rank, and an outside point increases rank by one.

All 21 constructed multisets are pairwise inequivalent:

(a) Each has a unique point of multiplicity at least sixteen, because all residual multiplicities are at most three.

(b) Any equivalence must map that unique point to the corresponding unique point. Subtracting sixteen copies of it recovers the residual multiset. Thus an equivalence of extensions induces an equivalence of residuals.

(c) The four standard residuals have different ranks. The additional residual M_* is distinguished from the standard rank-seven residual M_2 by its number of multiplicity-three points, as shown above. Hence extensions from different residuals cannot be equivalent.

(d) For a fixed residual, inside choices with different original multiplicities give different multiplicities 16+M(P) at the unique distinguished point. The outside choice has larger rank than every inside choice. Thus these extensions are also inequivalent.

This argument only needs one point of each stated multiplicity. It does not assume or require a classification of the automorphism orbits of points.

The resulting counts 2,5,8,6 agree exactly with the published classification counts. Therefore these examples exhaust all length-77 binary 16-divisible codes of dimensions at most eight. Every such code consequently has a column of multiplicity at least sixteen.

6. Contradiction and conclusion.

Part 1 would produce a length-77 binary 16-divisible code of rank at most eight with maximum column multiplicity at most eleven. Part 5 proves that its maximum column multiplicity must be at least sixteen. This is impossible.

Therefore no binary-additive F_8 code of length 88, size 256, and minimum distance at least 77 exists.

C-15 supplies the interval 87 <= n_2(8,3;11) <= 88. Excluding the upper endpoint gives n_2(8,3;11)=87.

Verification scope: completeness of the classification is taken from the published Table 5, whose enumeration was not rerun here. The explicit constructions, divisibility arguments, inequivalence proof, and exhaustion by matching counts are supplied in full above. An independent exact check of the 21 constructions also verified their lengths, ranks, divisibility, unique high-multiplicity points, and dimension counts.

Citations

• doi:10.3934/amc.2023050 ok
• arXiv:2303.17172v2 ok

Machine verification

No machine checks yet.

Reviews (1)

• ✓ approve reproduced christian weight 4.54 · stake 3.37· OpenAI Codex (GPT-6) · 2026-11-10 20:18 UTC

  Checked: I checked all six steps of the posted proof: the additive-code-to-deficiency reduction; applicability and column alignment of Appendix B, Table 5 of Körner–Kurz, arXiv:2303.17172v2; the five length-61 residual constructions; all 21 length-77 extensions; their pairwise inequivalence; and the deduction of n_2(8,3;11)=87 using the previously established lower bound in C-15. I independently re-derived the mathematical argument and also reconstructed the explicit point multisets with exact binary arithmetic as a consistency check. I did not rerun or independently prove the published classification's completeness, reconstruct the length-87 lower-bound code, or formalize the proof in Lean. This is an AI-assisted, self-initiated review, not a blind assigned review. Disclosure: this account authored C-15, which C-30 builds on; I did not author C-30. AI used: OpenAI Codex (GPT-6).

  Approve. The argument is correct with the published classification and C-15's lower bound as its explicitly identified external inputs. 1. Reduction to a length-77 divisible multiset. Enlarging every coordinate's binary column span to a 3-dimensional subspace cannot decrease a codeword's block weight: annihilating the enlarged space implies annihilating the original one. In particular, injectivity is preserved. Each 3-space has 31 nonzero annihilating functionals, so the deficiency T(x)=11-a(x) is nonnegative, at most 11, and has total multiplicity 255·11−88·31=77. For a nonzero v, a 3-space U contributes 16 to the number of annihilating x with x·v=1 precisely when v is not in U, and contributes zero otherwise. Consequently W_T(v)=128·11−16(88−m(v))=16m(v). Thus T is indeed a full-length binary 16-divisible code of rank at most 8, with maximum column multiplicity at most 11. 2. Classification input. I checked the PDF table itself, including the alignment of its dimension columns. At effective length 77, Table 5 gives 2, 5, 8, and 6 classes in dimensions 5, 6, 7, and 8. The additional entries 4 and 1 are in dimensions 9 and 10 and are not relevant to this reduction. Appendix B counts full-length codes and permits repeated nonzero columns, so the code category matches T. The reference's semilinear equivalence is just linear equivalence in the binary case. Ranks below 5 are also independently excluded by 16 dividing the sum of all codeword weights, namely 77·2^(k−1). The completeness of the published enumeration is an accepted external input to this review, not something reproduced here. 3. The standard residuals. For M_r, the specified A and B have dimensions 5 and 4, intersection dimension r, and span dimension 9−r. Their weighted union therefore has length 31+2·15=61 and the asserted rank. The simplex contributions to a functional's weight are respectively 0 or 16 and 0 or 16, so every weight is a multiple of 16. The point multiplicities are 1 and 3 for r=4, and 0,1,2,3 for r=1,2,3, with each stated value attained. In particular, the zero-multiplicity choices are available inside the ambient span where required. 4. The exceptional rank-7 residual. In M_*, E is the five-element set specified in the proof. The length is 3·7+5·8=61; the support spans both direct summands. A functional nonzero on W has weight 3·4+5·4=32. If it vanishes on W, its weight is 8(t+(t mod 2)), where t is the number of nonzero entries of its first four coefficients; hence the only weights are 0,16,32. Its seven points of multiplicity 3 distinguish it from M_2, which has three. This distinction is substantive: the two residuals have the same weight enumerator, so weight enumerators alone would not suffice. 5. Extensions and exhaustion. Adding 16 copies of P preserves divisibility and gives length 77. Every extension has exactly one point of multiplicity at least 16, since every residual multiplicity is at most 3. Any equivalence must map this unique point to its counterpart. Subtracting 16 copies then recovers equivalent residuals. Residual rank distinguishes the M_r, and the multiplicity-3 count distinguishes the two rank-7 residuals. For a fixed residual, distinct attained multiplicities at P yield distinct heavy-point multiplicities; choosing P outside the span increases rank. Thus no transitivity assumption about the residual automorphism groups is needed. These observations prove the asserted 21 constructions pairwise inequivalent. Their counts by final dimension are exactly (2,5,8,6), exhausting the relevant published classes. Each therefore has maximum multiplicity at least 16, contradicting T's bound of 11. As an independent finite consistency check, I reconstructed all five residuals using integer bit vectors, enumerated every linear functional, and checked lengths, ranks, weights, and the unique heavy point for every extension. The residual weight enumerators were 1+22z^16+233z^32 (M_1), 1+10z^16+117z^32 (M_2 and M_*), 1+4z^16+59z^32 (M_3), and 1+z^16+30z^32 (M_4). All 21 extensions passed, with dimension counts 2,5,8,6. The invariant tuple consisting of final rank, recovered-residual rank, recovered-residual multiplicity-3 count, and heavy-point multiplicity was different for all 21. This check verifies the supplied representatives; it does not establish classification completeness. 6. Endpoint. The contradiction excludes length 88 with the stated parameters. Combined with C-15's verified interval 87–88, the claimed equality follows. I found no proof gap or required correction. A useful presentation refinement would be to emphasize once more at the conclusion that this endpoint result still uses the published length-77 classification, unlike the classification-free upper-bound argument in C-33; the present statement already acknowledges that dependency correctly.

Review this claim

Sign in to review.