Pith. sign in

REVIEW 3 major objections 6 minor 22 references

Linear codes for $b$-symbol read channels attaining the Griesmer bound

T0 review · 3 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves that, for fixed field size q, read length b, and dimension k with k ≥ b, the shortest possible length of a linear b-symbol code equals the Griesmer-type expression $\lceil g_q(k, q^{b-1}d)/[b]_q\rceil$ once the minimum…

desk verdict The main theorem is false as stated (missing the k>=b hypothesis), but the intended version is plausible and the small-dimension results are solid; fix the statement and it deserves a serious referee. read the letter →

arxiv 2507.07728 v1 pith:2ONK7ARH submitted 2025-07-10 cs.IT math.COmath.IT

Sascha Kurz This is my paper · ORCID
classification cs.ITmath.COmath.IT MSC 94B0594B65
keywords b-symbolmetricsymbol-paircodesGriesmerboundlength-optimallinearprojectivesystemsbinarySingercycles
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper tries to establish that the classical Hamming-metric picture—where the Griesmer bound on code length is attained exactly for all sufficiently large minimum distances—also holds for the b-symbol read-channel metric. The claimed result is that the minimum length $n_q^b(k,d)$ of a linear code with dimension $k$ and b-symbol minimum distance $d$ coincides with the Griesmer-type bound $\lceil g_q(k, q^{b-1}d)/[b]_q\rceil$ for every sufficiently large $d$. If this is right, determining optimal b-symbol code lengths becomes a finite check per dimension, field, and block size rather than an infinite optimization problem. The paper also computes the complete exact function for binary pair-symbol codes in dimensions up to five, giving explicit tables and formulas.

What carries the argument

The carrying objects are projective $h-(n,k,s)_q$ systems—multisets of at most $h$-dimensional subspaces of $\mathrm{PG}(k-1,q)$ such that every hyperplane contains at most $s$ elements—together with their faithful variant in which every element has dimension exactly $h$. A b-chain is an ordered list of vectors of length $n+b-1$ over $\mathbb{F}_q^k$ whose consecutive b-tuples generate the b-spaces; gluing chains whose end matches the next chain's start preserves both length and the hyperplane-count parameter $s$ (Lemma 3.12). Lemma 3.14 is the pivotal gluing lemma: using Singer cycles and $\mathrm{GL}(k,q)$ transformations it builds a chain of length $\lambda[k]_q$ connecting any prescribed start and end while maintaining the exact projective system parameters. The Singer-cycle construction of Proposition 3.2 supplies the base codes with $n=[k]_q$ and $d=[b]_q q^{k-b}$, and Lemma 2.11 records the periodicity of the Griesmer expression that turns finitely many residue classes into the asymptotic statement.

What would settle it

Find one parameter set $k\ge b$, $q$, and $b$ together with an infinite sequence of distances $d_i\to\infty$ for which no linear $[\lceil g_q(k,q^{b-1}d_i)/[b]_q\rceil,\,k,\,d_i]_q^b$ code exists; a direct computer search over the residue classes modulo $q^{k-b}[b]_q$ for, say, $q=2$, $b=2$, $k=6$ beyond the ranges covered in the paper would either reproduce the formula or produce such a counterexample. Since the proof also depends on the imported additive-code theorem, independently verifying that theorem is a second potential falsifier: if some residue class lacks the promised faithful projective system, the construction has no starting point.

Watch

Extended reading notes

Core claim

The central claim is Theorem 3.16: given parameters $k$, $q$, and $b$, one has $n_q^b(k,d) = \lceil g_q(k, q^{b-1} d)/[b]_q\rceil$ for all sufficiently large $d$. The intended regime is $k\ge b$, which the proof uses even though the theorem statement does not state it. The construction proceeds by taking a faithful projective $b-(n,k,n-d)_q$ system supplied by the author's earlier result on additive codes attaining the Griesmer bound, interpreting its b-spaces as length-one b-chains, gluing them into a long b-chain with equal start and end using Singer-cycle-based articulations, and then reading the chain back as the columns of a generator matrix of a linear b-symbol code. Periodicity of the Griesmer bound then extends the construction from one representative of each residue class of $d$ modulo $q^{k-b}[b]_q$ to every sufficiently large distance in that class. For $q=b=2$ and $k\le 5$, the paper determines $n_2^2(k,\cdot)$ exactly, with formulas $n_2^2(k,d)=\lceil g_2(k,2d)/3\rceil$ for all $d\ge 2$ when $k=3$, for $d\ge 5$ when $k=4$, and for $d\ge 9$ when $k=5$, plus explicit small-distance exceptional values.

Load-bearing premise

The proof assumes, rather than proves here, that for every residue class of the target distance there exists a configuration of b-dimensional subspaces hitting the Griesmer bound exactly, a result on additive codes imported from the author's earlier work, and it uses the dimension $k$ being at least $b$ even though the theorem statement does not say so.

Editorial extensions

If this is right

  • The length-optimality problem for linear b-symbol codes reduces, for each fixed $k,q,b$, to checking finitely many small minimum distances; all larger distances are settled by the formula $\lceil g_q(k,q^{b-1}d)/[b]_q\rceil$.
  • The ratio $n_q^b(k,d)/\lceil g_q(k,q^{b-1}d)/[b]_q\rceil$ tends to $1$ as $d\to\infty$, so lengths and the Griesmer-type bound are asymptotically identical.
  • For binary pair-symbol codes, exact optimal lengths are now known for all dimensions $k\le 5$, including the exceptional small distances where the Griesmer formula fails.
  • Concatenation is compatible with the formula: combining codes from Proposition 3.2 and the chain construction via Lemma 3.6 makes lengths and minimum distances additive, which is exactly what the periodicity of the bound requires.
  • For storage applications, reaching a large target b-symbol distance at minimum length can be done by taking finitely many Singer-cycle-type building blocks and concatenating them, with no further search needed in the asymptotic regime.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same proof structure suggests that the finite exceptional set of distances for each $k,q,b$ is periodic modulo $q^{k-b}[b]_q$, so computing one explicit threshold per residue class would turn Theorem 3.16 into an algorithm rather than an existence statement.
  • The b-chain formulation recasts b-symbol code construction as a directed tour problem on projective subspaces; the integer-programming model in the paper could be sharpened with subtour-elimination constraints to compute the exceptional values for larger dimensions.
  • If the imported additive-code existence result fails for some residue class, Theorem 3.16 would still hold for the residue classes where faithful projective systems are attested, so a useful partial version of the theorem survives.
  • A testable extension would be to compute $n_q^b(k,d)$ for $q=2$, $b=2$, $k=6$ using the same ILP-plus-chain method; agreement with the Griesmer formula beyond a small threshold would support the conjecture that the asymptotic regime begins very early.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. The paper studies the minimum length n_q^b(k,d) of linear codes over F_q of dimension k and minimum b-symbol distance d. The main result, Theorem 3.16, claims that for all sufficiently large d, n_q^b(k,d) equals the ceiling of the Griesmer-type bound g_q(k,q^{b-1}d)/[b]_q, i.e. the Griesmer bound is attained. The proof uses a geometric interpretation of b-symbol codes as projective b-(n,k,s)_q systems, a construction of 'b-chains' to realize such systems as actual codes, and an existence theorem for additive codes from a companion preprint. In Section 4 the paper determines the exact values of n_2^2(k,d) for k=3,4,5 for all d, using the Griesmer bound, explicit generator matrices, and two non-existence lemmas.

Significance. If Theorem 3.16 were correct for all parameters, it would reduce the determination of n_q^b(k,·) to finitely many small-distance values, a qualitative analogue of the Solomon-Stiffler result for the Hamming metric. The exact tables for n_2^2(k,·), k≤5, are concrete and likely useful for storage-channel code designers. The paper is clearly written and the geometric framework is elegant. However, the main theorem as stated is false, and the construction relies on an unreviewed preprint; these issues must be fixed before the paper can be accepted.

major comments (3)
  1. [Theorem 3.16] The statement is false without the assumption k≥b. For k=1, b=2, q=2, Theorem 4.1 gives n_2^2(1,d)=d for all d≥2, while the Griesmer value is ⌈g_2(1,2d)/3⌉ = ⌈2d/3⌉, which is strictly smaller than d for every d>2. The proof uses k≥b in Lemma 2.6, Proposition 3.2, Lemma 3.5, and the parameter q^{k-b}. Therefore the theorem should be restated with the explicit hypothesis k≥b≥2, and the abstract and conclusion should be amended accordingly.
  2. [Proof of Theorem 3.16] The proof imports [15, Theorem 4] as a black-box existence result, and [15] is an unreviewed arXiv preprint by the same author. This theorem supplies, for every residue class d′ mod q^{k-b}[b]_q, a faithful projective b-system attaining the Griesmer bound. Since this is the main existence input for the asymptotic claim, the paper must provide a precise statement and a proof of this result, or replace it by a peer-reviewed reference (e.g. [1] or [16] if they contain the needed theorem). Without this, the central claim cannot be checked by the reader.
  3. [Proof of Theorem 3.16] The gluing step is only sketched. The proof asserts that the nλ b-spaces of Sλ can be interpreted as b-chains of length 1 and linked via Lemma 3.14 into a single b-chain with the same start and end, and that the resulting projective system has the exact hyperplane count (nλ−dλ)+λ′[k−b]_q. This step is load-bearing: it must explain how ordered bases of the b-spaces are chosen, how the linking chains are arranged, how the final chain is closed, and why the computed minimum distance is exactly d′+(λ+λ′)q^{k-b}[b]_q. The current text is too compressed for a proof of the main theorem.
minor comments (6)
  1. [Proof of Theorem 3.16] The phrase 'he existence of a constant' should read 'the existence of a constant'; also, the parameter h in the cited [15, Theorem 4] should be explicitly identified with b.
  2. [Lemma 3.14] In the inductive step, the condition 'v′i /∈ ⟨v′0,...,v′i, ui+1,...,ub−2⟩' contains v′i itself and is always false; the intended condition is presumably about v′_{i+1} or v′0. Please correct.
  3. [Proof of Theorem 4.4] In the table header, 'g2(8, 8t+2i)' should be 'g2(4, 8t+2i)'.
  4. [Example 3.15] The phrase 'interprete' should be 'interpret', and the list 'v4, v16, v16, v1,,' contains an extra comma and a possible duplicate entry.
  5. [Section 4] The computational claims involving LinCode ('we have enumerated all 10358 even [24,5,10]_2 codes') should be accompanied by a reference to the software or a link to the data files to support reproducibility.
  6. [Lemma 3.5] In the proof, the phrase 'a generator matrix U of an an [n,k,≥d]^b_q code' contains a duplicated 'an'.

Circularity Check

2 steps flagged · score 4.0 of 10

Load-bearing existence theorem is the author's own unpublished additive-code preprint [15]; Theorem 3.16 is also stated without the k≥b hypothesis its proof requires.

  1. self citation load bearing [Section 3, proof of Theorem 3.16 (paragraph beginning 'From [15, Theorem 4] we conclude...')]
    "From [15, Theorem 4] we conclude the existence of a constant λ ∈ N such that there exists a faithful projective h−(nλ, k, nλ − dλ)q system Sλ with dλ = λ·q^{k−b}·[b]_q + d′ and nλ = ⌈g_q(k,q^{b−1}·dλ)/[b]_q⌉."

    [15] is the same author's unpublished arXiv preprint on additive codes attaining the Griesmer bound. The proof of Theorem 3.16 takes from it, as a black box, the very existence of faithful projective b-systems with the Griesmer-type length nλ for every residue class d′; these objects are the only source of codes in the construction. The paper contributes the chain-gluing (Lemmas 3.13-3.14) and periodicity arguments, but without [15, Theorem 4] there is nothing to glue. Since [15] is not machine-checked, code-reproduced, or externally falsifiable in this paper, the central existence claim is carried by a load-bearing self-citation rather than by a self-contained derivation.

  2. other [Theorem 3.16 statement and its proof (range of d′)]
    "Given parameters k, q, and b we have n_q^b(k,d) = ⌈g_q(k, q^{b−1} d)/[b]_q⌉ for all sufficiently large d."

    The statement carries no restriction k ≥ b, but every ingredient of the proof requires it: Lemma 2.6, Lemma 3.5, Proposition 3.2, Lemma 3.14, and the proof's range 1 ≤ d′ ≤ q^{k−b}·[b]_q all assume k ≥ b. The omission is not merely cosmetic: for k=1, b=2 the paper's own Theorem 4.1 proves n_2^q(1,d)=d for all d≥2, while the displayed formula gives (for q=2) ⌈2d/3⌉ < d for every d>2, contradicting the asserted equality for arbitrarily large d. Thus the claimed quantifier is unsupported by the derivation chain.

full rationale

The paper contains no fitted parameters, no definitional equivalences, and no renaming of known results; the lower bound it attains is the external Griesmer-type bound of [16], and the small-distance tables for binary pair-symbol codes are supported by explicit generator matrices and enumeration. The central asymptotic theorem, however, is not self-contained: its main existence input is [15, Theorem 4], an unpublished arXiv preprint by the same author giving the additive-code analogue of the same 'attainment for large d' phenomenon. That makes the self-citation load-bearing, though there is genuine independent work in the chain-gluing construction (Lemma 3.14) that converts additive systems into linear b-symbol codes. I therefore score the circularity at 4, not higher. Separately, the theorem as printed omits the k ≥ b hypothesis used throughout its proof and is false for k=1, b=2; this is a correctness defect rather than a circular step, but it compounds the fragility of the main claim.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper has no fitted numerical parameters. The main assumptions are prior theorems (Griesmer bound, b-symbol bound), the author's unpublished additive-code existence result, the unstated k≥b condition, and the correctness of computer searches.

assumptions (5)
  • standard math Griesmer bound for Hamming metric codes (Inequality (5)) and Solomon-Stiffler attainment for large d
    Used as background in Section 2 to motivate the b-symbol Griesmer-type bound; cited to [10] and [21].
  • domain assumption b-symbol Griesmer-type bound (Inequality (6)) from [16, Theorem 1]
    The whole paper measures optimality against this lower bound; the bound is cited, not re-proved.
  • domain assumption [15, Theorem 4]: existence of faithful projective h-(n,k,s)_q systems attaining the Griesmer bound for additive codes, for all residue classes of d
    Invoked at the start of the proof of Theorem 3.16; this is the author's own unpublished arXiv preprint and is not reproduced in the paper.
  • ad hoc to paper k ≥ b for the construction in Section 3
    Theorem 3.16 is stated without it, but the proof uses q^{k-b} and b-spaces in PG(k-1,q), which require k≥b; the missing condition makes the theorem false for k<b.
  • domain assumption Correctness and exhaustiveness of ILP and LinCode computations in Section 4
    Claims such as 'no partition yields a [8,5,5] code' and the counts in Table 1 depend on computer searches whose code and data are not shipped.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Linear codes for $b$-symbol read channels attaining the Griesmer bound." pith.science (2026). https://pith.science/paper/2ONK7ARH

@misc{pith2026250707728,
  author       = {Pith},
  title        = {Pith review of: Linear codes for $b$-symbol read channels attaining the Griesmer bound},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2ONK7ARH}},
  note         = {Machine review of arXiv:2507.07728}
}
abstract

Reading channels where $b$-tuples of adjacent symbols are read at every step have e.g.\ applications in storage. Corresponding bounds and constructions of codes for the $b$-symbol metric, especially the pair-symbol metric where $b=2$, were intensively studied in the last fifteen years. Here we determine the optimal code parameters of linear codes in the $b$-symbol metric assuming that the minimum distance is sufficiently large. We also determine the optimal parameters of linear binary codes in the pair-symbol metric for small dimensions.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 19 canonical work pages

  1. [15]

    S. Kurz. Additive codes attaining the Griesmer bound. arXiv preprint 2412.14615, 2024. 26

    arXiv 2024

  2. [1]

    S. Ball, M. 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. 25

    work page 2025

  3. [16]

    G. Luo, M. F. Ezerman, C. G ¨uneri, S. Ling, and F. ¨Ozbudak. Griesmer bound and constructions of linear codes in b-symbol metric. IEEE Transactions on Information Theory, 70(11):7840–7847, 2024

    work page 2024

  4. [2]

    Bouyukhev, D

    I. Bouyukhev, D. B. Jaffe, and V . Vavrek. The smallest length of eight-dimensional binary linear codes with prescribed minimum distance. IEEE Transactions on Infor- mation Theory, 46(4):1539–1544, 2000

    work page 2000

  5. [3]

    Cassuto and M

    Y . Cassuto and M. Blaum. Codes for symbol-pair read channels. IEEE Transactions on Information Theory, 57(12):8011–8020, 2011

    work page 2011

  6. [4]

    Y . M. Chee, L. Ji, H. M. Kiah, C. Wang, and J. Yin. Maximum distance separable codes for symbol-pair read channels. IEEE Transactions on Information Theory , 59(11):7259–7267, 2013

    work page 2013

  7. [5]

    Chen and H

    B. Chen and H. Liu. New bounds on the code size of symbol-pair codes. IEEE Transactions on Information Theory, 69(2):941–950, 2023

    work page 2023

  8. [6]

    B. Ding, G. Ge, J. Zhang, T. Zhang, and Y . Zhang. New constructions of MDS symbol-pair codes. Designs, Codes and Cryptography, 86:841–859, 2018

    work page 2018

Show all 22 references
  1. [7]

    B. Ding, T. Zhang, and G. Ge. Maximum distance separable codes for b-symbol read channels. Finite Fields and Their Applications, 49:180–197, 2018

    2018

  2. [8]

    Dodunekov and J

    S. Dodunekov and J. Simonis. Codes and projective multisets. The Electronic Jour- nal of Combinatorics, 5:1–23, 1998

    1998

  3. [9]

    Govaerts

    P. Govaerts. Classifications of blocking set related structures in Galois geometries . PhD thesis, Ghent University, 2003

    2003

  4. [10]

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

    1960

  5. [11]

    M. D. Hestenes. Singer groups. Canadian Journal of Mathematics, 22(3):492–513, 1970

    1970

  6. [12]

    Huang, Q

    D. Huang, Q. Liao, G. Tang, and S. Zhu. On the b-symbol weights of linear codes for large b. Finite Fields and Their Applications, 107:102647, 2025

    2025

  7. [13]

    X. Kai, S. Zhu, and P. Li. A construction of new MDS symbol-pair codes. IEEE Transactions on Information Theory, 61(11):5828–5834, 2015

    2015

  8. [14]

    X. Kai, S. Zhu, Y . Zhao, H. Luo, and Z. Chen. New MDS symbol-pair codes from repeated-root codes. IEEE Communications Letters, 22(3):462–465, 2018

    2018

  9. [17]

    G. Luo, M. F. Ezerman, S. Ling, and X. Pan. New families of MDS symbol- pair codes from matrix-product codes. IEEE Transactions on Information Theory , 69(3):1567–1587, 2022

    2022

  10. [18]

    Ma and J

    J. Ma and J. Luo. On symbol-pair weight distribution of MDS codes and simplex codes over finite fields. Cryptography and Communications, 13:101–115, 2021

    2021

  11. [19]

    Ma and J

    J. Ma and J. Luo. Constructions of MDS symbol-pair codes with minimum distance seven or eight. Designs, Codes and Cryptography, 90(10):2337–2359, 2022

    2022

  12. [20]

    Ma and J

    J. Ma and J. Luo. MDS symbol-pair codes from repeated-root cyclic codes. Designs, Codes and Cryptography, pages 1–17, 2022

    2022

  13. [21]

    Solomon and J

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

    1965

  14. [22]

    Yaakobi, J

    E. Yaakobi, J. Bruck, and P. H. Siegel. Constructions and decoding of cyclic codes over b-symbol read channels. IEEE Transactions on Information Theory , 62(4):1541–1551, 2016. 27

    2016

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.