pith. sign in

arxiv: 2604.03784 · v1 · submitted 2026-04-04 · 🧮 math.CO

Length-Maximal Codes with Given Singleton Defect: Structure and Bounds

Tim Alderson This is my paper

Pith reviewed 2026-05-13 17:34 UTC · model grok-4.3

classification 🧮 math.CO
keywords q-ary codesSingleton defectlength-maximal codesGriesmer boundmaximal arcsnonlinear codesSingleton bound
0
0 comments X

The pith

Length-maximal q-ary codes with Singleton defect s must be symbol-uniform with restricted distances and satisfy a divisibility condition.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper determines the longest possible lengths n for q-ary codes of size M equal to q to the k with a fixed Singleton defect s. It defines length-maximal codes as those attaining n equal to (s+1)(q+1) plus k minus 2 and proves they must place each symbol the same number of times in every position, confine pairwise distances to the minimum d together with the largest values from n-k+3 up to n, and obey the rule that s+2 divides q(q+1). These properties produce an improved Singleton-type upper bound on length and a further tightening when s grows relative to q. The work also identifies parameter ranges where nonlinear codes meet the Griesmer bound and proves non-existence for certain near-maximal codes when the alphabet is small.

Core claim

For an (n, M, d)_q code with M equal to q to the k and Singleton defect s, a code is length-maximal precisely when n equals (s+1)(q+1) plus k minus 2; such codes are necessarily symbol-uniform, have pairwise distances confined to the set consisting of d together with n-k+3 through n, and satisfy the divisibility condition that s+2 divides q(q+1). An equivalent statement yields an improved Singleton-type inequality, with further tightening to n at most s(q+1) plus k minus 1 when s is at least 2q and to n at most (s+2-alpha)(q+1) plus alpha plus k minus 3 when alpha q is at most s less than (alpha+1)q.

What carries the argument

The maximal-arc-type bound that limits the length n of a q-ary code in terms of its size M, minimum distance d, and Singleton defect s.

Load-bearing premise

The combinatorial counting arguments that produce the maximal-arc-type bound and the structural properties hold using only the standard definition of codes and the Singleton defect, without any extra geometric or algebraic assumptions on the code.

What would settle it

A single code with M equal to q to the k and length exactly (s+1)(q+1) plus k minus 2 that either fails to be symbol-uniform, contains a pairwise distance outside the allowed set, or has an s where s+2 does not divide q(q+1) would disprove the structural claims.

read the original abstract

We study the maximum length of $q$-ary codes as a function of alphabet size, code size, and Singleton defect. For an $(n, M, d)_q$ code with dimension $\kappa = \log_q M \ge 2$ and Singleton defect $s = n - \lceil\kappa\rceil + 1 - d$, we establish a \emph{maximal-arc-type bound}. For $M = q^k$, we call codes with $n = (s+1)(q+1) + k - 2$ \emph{length-maximal}, and show such codes are necessarily symbol-uniform, have pairwise distances confined to $\{d\} \cup \{n-k+3, \ldots, n\}$, and satisfy the divisibility condition $(s+2) \mid q(q+1)$. An equivalent form yields an improved Singleton-type inequality extending a result of Guerrini, Meneghetti, and Sala for binary systematic codes. When $s \ge 2q$, the bound tightens to $n \le s(q+1)+k-1$; more finely, when $\alpha q \le s < (\alpha+1)q$ for integer $\alpha \ge 2$, it tightens to $n \le (s+2-\alpha)(q+1)+\alpha+k-3$, improving on the main bound by $(\alpha-1)q$. We identify several conditions under which nonlinear codes satisfy the Griesmer bound, including: $d \le q^2$; $s \le q-1$; $s \ge \beta q$ with $d \le \beta q^2$; and a parametric family of binary conditions. We also show that near-length-maximal $A^1$MDS codes of length $k+2q-1$ cannot exist for $k \ge 5$ when $q=2$, nor for $k \ge 7$ when $q=3$. For codes of non-integer dimension $\kappa \in (k, k+1)$, an analogous bound holds but is never attained. This forces the corresponding Singleton-type inequality one unit tighter than the integer-dimension case. For rational non-integer $\kappa$, our bounds specialise to a length bound for additive codes of fractional dimension, complementing recent geometric results on additive codes. Throughout, the results parallel the theory of maximal arcs. Whether length-maximal nonlinear codes can exist for parameter ranges within which no linear length-maximal codes exist is the principal open problem raised by this work.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper studies the maximum length of q-ary codes with a prescribed Singleton defect s = n - ceil(kappa) + 1 - d where kappa = log_q M >= 2. For M = q^k it defines length-maximal codes by the equality n = (s+1)(q+1) + k - 2 and proves that any such code must be symbol-uniform, that its distance set is contained in {d} union {n-k+3, ..., n}, and that (s+2) divides q(q+1). From these structural facts it derives an improved Singleton-type upper bound on n, further tightenings when s is large relative to q, several sufficient conditions under which nonlinear codes meet the Griesmer bound, and non-existence results for near-length-maximal A^1MDS codes when q=2 or 3. An analogous (but unattained) bound is obtained for non-integer kappa, yielding a one-unit tighter inequality; the results are shown to specialize to additive codes of fractional dimension.

Significance. If the combinatorial counting arguments are correct, the work supplies new structure theorems for length-maximal nonlinear codes and sharpens the Singleton bound in a manner that parallels the theory of maximal arcs. The divisibility condition, the explicit distance restrictions, and the non-attainability statement for non-integer dimension are concrete, falsifiable contributions that could guide future constructions or non-existence proofs. The identification of parameter regimes in which nonlinear codes satisfy the Griesmer bound is also of independent interest.

major comments (2)
  1. [Section 3] The central combinatorial argument establishing symbol-uniformity and the restricted distance set for length-maximal codes (the paragraph following the definition of length-maximal codes) appears to rest on a double-counting of symbol occurrences across codewords; an explicit small-parameter verification (e.g., q=3, s=1, k=2) would strengthen that no case distinctions have been overlooked.
  2. [Section 5] The non-existence claim for near-length-maximal A^1MDS codes when k >= 5 (q=2) or k >= 7 (q=3) is load-bearing for the overall narrative; the proof sketch relies on the divisibility condition together with an auxiliary counting argument on the number of codewords at distance n-k+3. If the auxiliary count is off by one, the non-existence threshold may shift.
minor comments (2)
  1. [Introduction] The notation kappa for log_q M is introduced only in the abstract; a sentence in the introduction repeating the definition would improve readability for readers who begin with the main text.
  2. [Theorem 4.1] In the statement of the improved Singleton-type inequality, the dependence on alpha (when alpha q <= s < (alpha+1)q) is written with an implicit floor; an explicit floor function would remove any ambiguity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive comments. We address each major comment below. We will make revisions to incorporate an explicit verification as suggested.

read point-by-point responses

  1. Referee: [Section 3] The central combinatorial argument establishing symbol-uniformity and the restricted distance set for length-maximal codes (the paragraph following the definition of length-maximal codes) appears to rest on a double-counting of symbol occurrences across codewords; an explicit small-parameter verification (e.g., q=3, s=1, k=2) would strengthen that no case distinctions have been overlooked.

    Authors: The combinatorial argument in Section 3 is based on exhaustive double-counting of symbol occurrences and pairwise distances under the length-maximality assumption, which holds uniformly without requiring case distinctions. Nevertheless, we agree that an explicit check for small parameters can enhance clarity. In the revised version, we will include a verification for q=3, s=1, k=2, confirming that the code must be symbol-uniform with the stated distance restrictions. revision: yes

  2. Referee: [Section 5] The non-existence claim for near-length-maximal A^1MDS codes when k >= 5 (q=2) or k >= 7 (q=3) is load-bearing for the overall narrative; the proof sketch relies on the divisibility condition together with an auxiliary counting argument on the number of codewords at distance n-k+3. If the auxiliary count is off by one, the non-existence threshold may shift.

    Authors: We have carefully re-examined the auxiliary counting argument in Section 5. It follows directly from the symbol-uniformity property and the restricted distance set established earlier, together with the divisibility condition. The number of codewords at distance n-k+3 is exactly determined by these properties, leading to the stated non-existence for the given thresholds. There is no off-by-one discrepancy in the count, as verified through the explicit formulas derived from the maximal length. No changes are needed to the proof. revision: no

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained combinatorial counting

full rationale

The paper defines length-maximal codes via the explicit formula n = (s+1)(q+1) + k - 2 and then applies direct double-counting on symbol frequencies and pairwise distances to derive uniformity, restricted distance sets, and the divisibility (s+2) | q(q+1). These steps begin from the standard Singleton defect s = n - ceil(kappa) + 1 - d and the given n, without any fitted parameters renamed as predictions, self-citation chains that carry the central claim, or ansatzes smuggled from prior work. The maximal-arc-type bound is obtained by the same counting and is not presupposed; later tightenings and non-existence results for non-integer dimension follow identically. No step reduces the claimed result to its input by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard mathematical axioms from combinatorics and coding theory without introducing new fitted parameters or invented entities.

axioms (2)
  • standard math Basic properties of the Hamming distance and the Singleton defect definition s = n - ceil(κ) + 1 - d
    Invoked throughout to define the parameters of the codes under study.
  • domain assumption Existence of finite alphabets of arbitrary size q
    q is treated as a given positive integer parameter.

pith-pipeline@v0.9.0 · 5777 in / 1306 out tokens · 55840 ms · 2026-05-13T17:34:40.883229+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    T. L. Alderson. Bruck nets and 2-dimensional codes.Bull. Inst. Combin. Appl., 52:33– 44, 2008

    work page 2008

  2. [2]

    Sets of subspaces with restricted hyperplane intersection numbers, 2026

    Tim Alderson and Simeon Ball. Sets of subspaces with restricted hyperplane intersection numbers, 2026

    work page 2026

  3. [3]

    Alderson

    Tim L. Alderson. On the weights of general MDS codes.IEEE Trans. Inform. Theory, 66(9):5414–5418, 2020

    work page 2020

  4. [4]

    Alderson and Zhipeng Zhang

    Tim L. Alderson and Zhipeng Zhang. Projective systems and bounds on the length of codes of non-zero defect.Journal of Algebra Combinatorics Discrete Structures and Applications, 2026. To appear

    work page 2026

  5. [5]

    Maximal arcs in Desarguesian planes of odd order do not exist.Combinatorica, 17(1):31–41, 1997

    Simeon Ball, Aart Blokhuis, and Francesco Mazzocca. Maximal arcs in Desarguesian planes of odd order do not exist.Combinatorica, 17(1):31–41, 1997

    work page 1997

  6. [6]

    Simeon Ball, Michel Lavrauw, and T. Popatia. Griesmer type bounds for additive codes over finite fields, integral and fractional mds codes.Designs, Codes and Cryptography, 93(1):175–196, 2025. 24

    work page 2025

  7. [7]

    Sui{k;n}-archi di un piano lineare finito.Boll

    Adriano Barlotti. Sui{k;n}-archi di un piano lineare finito.Boll. Un. Mat. Ital. (3), 11:553–556, 1956

    work page 1956

  8. [8]

    Long QMDS additive code, 2025

    Daniele Bartoli, Alessandro Giannoni, Giuseppe Marino, and Yue Zhou. Long QMDS additive code, 2025. Preprint, submitted toJ. Combin. Theory Ser. A

    work page 2025

  9. [9]

    On the Griesmer bound for nonlinear codes

    Emanuele Bellini and Alessio Meneghetti. On the Griesmer bound for nonlinear codes. InProceedings of the 9th International Workshop on Coding and Cryptography (WCC 2015), Paris, France, 2015

    work page 2015

  10. [10]

    Berlekamp.Algebraic Coding Theory

    Elwyn R. Berlekamp.Algebraic Coding Theory. McGraw-Hill, New York, 1968

    work page 1968

  11. [11]

    Mario A. de Boer. Almost MDS codes.Des. Codes Cryptogr., 9(2):143–155, 1996

    work page 1996

  12. [12]

    R. H. F. Denniston. Some maximal arcs in finite projective planes.J. Combinatorial Theory, 6:317–319, 1969

    work page 1969

  13. [13]

    J. H. Griesmer. A bound for error-correcting codes.IBM Journal of Research and Development, 4(5):532–542, 1960

    work page 1960

  14. [14]

    Guerrini, M

    L. Guerrini, M. Meneghetti, and M. Sala. On optimal nonlinear systematic codes.IEEE Trans. Inform. Theory, 62(6):3103–3112, 2016

    work page 2016

  15. [15]

    University at Buffalo, 2022

    Venkatesan Guruswami, Atri Rudra, and Madhu Sudan.Essential Coding Theory. University at Buffalo, 2022. Last updated August 26, 2025. Licensed under Creative Commons Attribution-NonCommercial-NoDerivs 3.0

    work page 2022

  16. [16]

    R. W. Hamming. Error detecting and error correcting codes.Bell System Technical Journal, 29(2):147–160, 1950

    work page 1950

  17. [17]

    F. J. MacWilliams and N. J. A. Sloane.The Theory of Error-Correcting Codes. North- Holland, Amsterdam, 1977

    work page 1977

  18. [18]

    A. W. Nordstrom and J. P. Robinson. An optimum nonlinear code.Information and Control, 11(5):613–616, 1967

    work page 1967

  19. [19]

    M. Plotkin. Binary codes with specified minimum distance.IRE Transactions on Information Theory, 6(4):445–450, 1960

    work page 1960

  20. [20]

    A metrization for power-sets with applications to combinatorial analysis.Canadian J

    Robert Silverman. A metrization for power-sets with applications to combinatorial analysis.Canadian J. Math., 12:158–176, 1960

    work page 1960

  21. [21]

    R. C. Singleton. Maximum distanceq-ary codes.IEEE Trans. Inform. Theory, 10(2):116–118, 1964

    work page 1964

  22. [22]

    Solomon and J

    G. Solomon and J. J. Stiffler. Algebraically punctured cyclic codes.Information and Control, 8(2):170–179, 1965

    work page 1965

  23. [23]

    Oxford University Press, Oxford, 1988

    Dominic Welsh.Codes and Cryptography. Oxford University Press, Oxford, 1988. 25

    work page 1988