Pith. sign in

REVIEW 2 major objections 4 minor 29 references

Covering Sequences and Covering-Sequences Codes

T0 review · 2 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash

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

Pith's one-line read The paper claims a method for building covering sequences over any finite field whose length exceeds the sphere-covering lower bound by at most the constant factor q/(q−1).

desk verdict Solid q-ary generalization of binary covering-sequence constructions, but the headline optimality factor is only proved for repunit-prime lengths; the composite case is asserted without the promised orbit census. read the letter →

arxiv 2607.14840 v2 pith:36HOVZ43 submitted 2026-07-16 cs.IT math.IT

Tuvi Etzion This is my paper
classification cs.ITmath.IT MSC 94B6094B1594A55
keywords coveringsequencecovering-sequencescodeconstacyclicHammingsphere-coveringbounddeBruijninterleavingself-dual
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

The paper sets out to construct covering sequences—cyclic strings whose sliding n-tuples cover every word over the field F_q within Hamming distance R—as short as possible. Its central claim is that for radius 1, the cyclic Hamming code H_q(r), viewed as a constacyclic code, yields covering sequences over any prime-power alphabet with length within the constant factor q/(q−1) of the sphere-covering lower bound. The same construction produces covering-sequences codes (CSCs), sets of cyclic sequences whose n-tuples form a covering code, which the paper argues are the natural building blocks for this problem. A parallel interleaving operation on parity-check matrices lifts the construction to radius 2 and beyond, again within a small constant factor.

What carries the argument

The central mechanism is Construction MC (merging cycles): a way to concatenate cyclic sequences from a covering-sequences code, overlapping suffixes and prefixes so that every n-tuple of every codeword remains an n-tuple of one merged cyclic sequence. The other half is the constacyclic representation of H_q(r): writing the parity-check columns as α^0, α^1, …, α^{n−1} makes the code closed under shifts that multiply by γ=α^n, a primitive element of F_q, giving orbit length (q−1)n and hence the CSCs used by the construction.

What would settle it

Compute the exact number of full-period cycles of the constacyclic Hamming code H_q(r) for a small composite n=(q^r−1)/(q−1), such as q=3, r=4 (n=40) or q=2, r=6 (n=63), and compare the resulting covering-sequence length to the sphere-covering bound; if the length exceeds q^{n−r}·q/(q−1), the claimed constant factor fails for composite n.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is that the parity-check matrix of the Hamming code over F_q can be written with columns α^i for a primitive α in F_{q^r}, which makes the code constacyclic: a cyclic shift multiplies a codeword by a primitive element γ=α^n of F_q. The cycles of this constacyclic code, each of length up to (q−1)n = q^r−1, form an (n, m, 1)_q-CSC with m = q^r−1. By merging these cycles through a concatenation procedure (Construction MC), one obtains a cyclic sequence whose consecutive n-tuples cover F_q^n within radius 1, with length at most q^{n−r} · q/(q−1), i.e., within a constant factor of the sphere-covering bound for the smallest possible covering code. The binary

Load-bearing premise

In Section IV, the claimed q/(q−1) optimality factor for composite n rests on an unproved assertion that the orbit count for the constacyclic Hamming code is the same as in the repunit-prime case—the paper provides no proof or enumeration for composite n.

Editorial extensions

If this is right

  • For every prime power q and positive integer r, there exists an (n,1)_q-covering sequence with n=(q^r−1)/(q−1) whose length is within the factor q/(q−1) of the sphere-covering bound.
  • The cycles of the constacyclic Hamming code form an (n, q^r−1, 1)_q-CSC, providing a dense set of reusable building blocks for longer covering sequences.
  • Interleaving R copies of the parity-check matrix of a cyclic or constacyclic code produces an (Rn, Rm, R)_q-CSC; applying this to H_q(r) yields radius-2 covering sequences within a constant factor of optimality.
  • For binary alphabets, the self-dual-sequence construction yields an (2^r,1)_2-CS within a factor of 1.25 of the optimal covering-code size.
  • When n=(q^r−1)/(q−1) is a repunit prime, the size of the CSC is exactly q(q^{n−r−1}−1)/(q^r−1)+2, giving an explicit formula for the resulting sequence length.

Reading between the lines

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

  • If the unperformed 'slightly more complicated analysis' for composite n is completed, the q/(q−1) constant factor would hold for all lengths of the form (q^r−1)/(q−1), making the optimality claim uniform rather than conditional on repunit primality.
  • The orbit-counting problem for composite n is an enumerative question the paper leaves open; a full treatment would require counting cycles whose periods are proper divisors of q^r−1, connecting to known counts of necklaces and cyclic codes.
  • The interleaving construction suggests a general template: applying Construction MC to interleaved parity-check matrices may give radius-R CSCs whose density beats earlier probabilistic constructions, something worth testing for R≥3.
  • The binary fact that all degenerated words are Hamming codewords fails for q>2, so the non-binary setting needs genuinely new orbit analysis; mapping which periods appear in constacyclic Hamming cycles for composite n would also clarify the structure of de Bruijn covering arrays.
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

2 major / 4 minor

Summary. The paper introduces and studies (n,R)_q-covering sequences (CSs) and (n,m,R)_q-covering-sequences codes (CSCs), extending binary constructions to non-binary alphabets. A general cycle-merging construction (Construction MC) is described, and binary results from earlier work are reviewed. The main new result is in Section IV, where the Hamming code H_q(r), represented as a constacyclic code, is used to construct an (n, q^r-1, 1)_q-CSC and an (n,1)_q-CS of length within a factor q/(q-1) of the sphere-covering lower bound, for n=(q^r-1)/(q-1). This is proved by an explicit orbit count only when n is a repunit prime; for composite n the paper asserts without proof that a similar analysis gives the same factor. Section V gives an interleaving construction for parity-check matrices to obtain codes with larger radii, with several examples.

Significance. If the Section IV claim holds for all r, the paper provides explicit non-binary covering sequences of radius 1 whose length is within a fixed constant factor of optimality, improving and generalizing the binary results in [2], [3]. The idea of using the constacyclic representation of H_q(r) to form CSCs is natural and promising. The paper also introduces the CSC concept as a unifying framework and gives a clean proof of the interleaving construction in Lemma 4. The main technical gap, however, is the unproved orbit-counting assertion for composite n, which is load-bearing for the claimed optimality factor. The paper would be a solid contribution if that gap is closed or if the claims are restricted to repunit primes.

major comments (2)
  1. [Section IV, orbit-count paragraph] The claimed q/(q-1) optimality factor for general r rests entirely on the sentence 'Slightly more complicated analysis achieves the same result when n is not a prime.' The preceding calculation is carried out only for n prime, where all nonzero codewords lie on full-period orbits of length (q-1)n except for the q codewords in two degenerate orbits. For composite n, codewords may lie in orbits of smaller period, and the number M of distinct orbits enters the constructed CS length as M(q^r-1+n-1) plus degenerate-orbit terms. If many codewords lie in shorter orbits, M is larger than (q^{n-r}-q)/(q^r-1), and the length can exceed q^{n-r} * q/(q-1). An upper bound on M, or a direct estimate of the total length over all orbit lengths, is needed. Since repunit primes are not known to be infinite, the general claim in the abstract and in the opening of Section IV is unsupported as written.
  2. [Section V, after Example 1] The paper states that Lemma 4 'can be implemented for example on H_q(r) to obtain (n,2)_q-CSs whose length is within a constant factor of optimality' and later says that similarly to Example 1 one can give such non-binary constructions. However, no orbit count or length bound is given for q>2, and Example 1 itself relies on orbit-counting assertions for the interleaved binary code. Since the paper advertises constructions for larger radii as one of its four goals, this claim needs at least a concrete bound or a reference to a detailed computation.
minor comments (4)
  1. [Section III-A, Proof of Lemma 2] In the line 'Since 0<r<n, it follows that α^r ≠ 1', the symbol r should be the period π, not the redundancy r. The proof otherwise is correct for the binary Hamming code.
  2. [Section IV, constacyclic shift derivation] The expression 'γ^{q-2} c_{t-2}' should read 'γ^{q-2} c_{n-2}'.
  3. [Section IV, paragraph on smaller-order γ] The phrase 'CSCs whose length is (2r-1)/t, where t divides 2r-1' appears to contain a typo: it should presumably be (q^r-1)/(q-1) or q^r-1, not 2r-1. Please correct and clarify.
  4. [General] The paper contains no numbered equations, which makes it difficult to refer to the orbit-count formula and the length bound. Numbering the displayed formulas would improve readability. Also, in the non-binary sections, 'bits' should be 'symbols' when describing the length of sequences over F_q.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the non-binary optimality derivation is self-contained, though the composite-n extension is an omitted proof, not a circular step.

full rationale

Construction MC (Sec. II, Theorem 1) is proved directly from the definition of an (n,m,R)_q-CSC; it does not define a covering sequence in terms of the quantity it later claims to bound, and no parameter is fitted. The Section IV optimality claim compares the constructed length with q^{n-r}, the sphere-covering bound for radius 1, which is external to the construction; the orbit census for the repunit-prime case is a count from the constacyclic representation of H_q(r), not a fitted input. The binary constructions quoted from [1],[3] are self-citations, but they are presented as review and the non-binary q/(q-1) result does not rely on them. The only load-bearing weakness is the sentence 'Slightly more complicated analysis achieves the same result when n is not a prime.' This is an omitted proof rather than a circular reduction: no equation in the paper defines the constructed length in terms of the claimed q/(q-1) factor, and the composite-n orbit enumeration is left open in the paper's own Problem 3. Hence the derivation chain is free of circularity; the composite-n gap should be assessed as a correctness/rigor risk, not as circularity.

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

Ledger: no free parameters; the paper's constants are construction parameters (q,r) and the optimality denominator is the sphere-covering lower bound. The main unproved input is the composite-n orbit-count assertion; standard facts about Hamming/Golay codes and the sphere-covering bound are imported. No invented entities.

assumptions (4)
  • standard math Sphere-covering lower bound |C| ≥ q^n/V_q(n,R) and the existence of codes approaching it (Krivelevich–Sudakov–Vu).
    Used in Section IV to define optimality factor; standard.
  • standard math Hamming code H_q(r) over F_q with parity-check matrix [α^0 ... α^{n−1}], n=(q^r−1)/(q−1), is a perfect 1-error-correcting code with q^{n−r} codewords and covering radius 1.
    Core building block; standard theorem imported without proof.
  • ad hoc to paper For n composite, the orbit count of the constacyclic Hamming code still yields a CSC whose merged sequence is within factor q/(q−1) of optimal.
    Stated in Section IV as 'Slightly more complicated analysis achieves the same result' but not demonstrated; carries the general claim.
  • domain assumption The cited codes in Examples 4–6 (binary and ternary Golay codes, constacyclic ternary quasi-perfect code [8]) have the stated lengths, dimensions, and covering radii and are cyclic/constacyclic.
    Relied on to instantiate the interleaving construction; taken from references.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Covering Sequences and Covering-Sequences Codes." pith.science (2026). https://pith.science/paper/36HOVZ43

@misc{pith2026260714840,
  author       = {Pith},
  title        = {Pith review of: Covering Sequences and Covering-Sequences Codes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/36HOVZ43}},
  note         = {Machine review of arXiv:2607.14840}
}
abstract

An $(n,R)_q$-covering sequence is a cyclic sequence, over the finite field $\F_q$, whose consecutive $n$-tuples form a code of length $n$ and covering radius $R$. An $(n,m,R)_q$-covering-sequences code is a set of cyclic sequences of length $m$, over $\F_q$, whose consecutive $n$-tuples form a code of length $n$ and covering radius $R$. These codes are the best building blocks for $(n,R)_q$-covering sequences. We show, for small radii, how cyclic codes and constacyclic codes with small covering radius, can be used to construct such sequences of short length and such codes with a relatively small number of sequences and a total number of codewords in the associated covering code. Sequences with small radius whose length approaches asymptotically to optimality are constructed, especially for an alphabet of prime power size large enough. With the same construction, interesting codes are also constructed for larger radii.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 1 canonical work pages

  1. [2]

    Y. M. CHEE, T. ETZION, H. TA,ANDV. K. VU,On de Bruijn Covering Sequences and Arrays,inProceedings IEEE Symposium on Information Theory,Athens, Greece 2024, pp. 1343–1348

    2024

  2. [3]

    Y. M. CHEE, T. ETZION, H. TA,ANDV. K. VU,Construction of covering sequences and 2D-sequences,Designs, Codes, and Crypto., doi.org/10.1007/s10623-025-01726-5

    work page doi:10.1007/s10623-025-01726-5

  3. [1]

    BORUCHOVSKY, T

    A. BORUCHOVSKY, T. ETZION,ANDR. M. ROTH,On nearly perfect covering codes,IEEE Trans. Inf. Theory,71 (2025) 2494–2504

    2025

  4. [4]

    B. CHEN, Y. FAN, L. LIU, H. LIU,Constacyclic codes over finite fields,Finite Fields and Their Applications,18 (2012) 1217–1231

    2012

  5. [5]

    B. CHEN, S. LING,ANDG. ZHANG,Application of constacyclic codes to quantum MDS codes,IEEE Trans. on Infor. Theory,61 (2015) 1474–1484

    2015

  6. [6]

    CHEN ANDY

    H. CHEN ANDY. WU,Cyclic and negacyclic codes with optimal and best known minimum distances,IEEE Trans. on Infor. Theory70 (2024) 8628–8635

    2024

  7. [7]

    CHUNG ANDJ

    F. CHUNG ANDJ. N. COOPER,De bruijn cycles for covering codes,Random Structures & Algorithms,25 (2004) 421—431

    2004

  8. [8]

    DODUNEKOV,ANDD

    D, DANEV, S. DODUNEKOV,ANDD. RADKOVA,A family of constacyclic ternary quasi-perfect codes with covering radius 3,Designs, Codes, and Crypto.,59 (2011) 111–118

    2011

Show all 29 references
  1. [9]

    G.DEBRUIJN,A combinatorial problem,Nederl

    N. G.DEBRUIJN,A combinatorial problem,Nederl. Akad. Wetensch.,49 (1946) 713–764

    1946

  2. [10]

    COHEN, I

    G. COHEN, I. HONKALA, S. LITSYN,ANDA. LOBSTEIN,Covering Codes,North-Holland, Amsterdam, 1997

    1997

  3. [11]

    G. D. COHEN, M. G. KARPOVSKY, H. F. MATTSONJR.,ANDJ. R. SCHATZ,Covering radius - survey and recent results,IEEE Trans. on Infor. Theory,31 (1985) 328–343

    1985

  4. [12]

    G. D. COHEN, A. C.LOBSTEIN,ANDN. J. A. SLOANE,Further results on the covering radius of codes,IEEE Trans. on Infor. Theory, 32 (1986) 680–694

    1986

  5. [13]

    ETZION,Perfect Codes and Related Structures,World Scientific, 2022

    T. ETZION,Perfect Codes and Related Structures,World Scientific, 2022

    2022

  6. [14]

    ETZION,Sequences and the de Bruijn Graph: Properties, Constructions, and Applications,London, UK; San Diego, US, Cambridge, US: Elsevier, 2024

    T. ETZION,Sequences and the de Bruijn Graph: Properties, Constructions, and Applications,London, UK; San Diego, US, Cambridge, US: Elsevier, 2024

    2024

  7. [15]

    ETZION,Binary and non-binary self-dual sequences and maximum period single-track Gray codes,inProceedings IEEE Symposium on Information Theory,Guangzhou, China 2026, pp

    T. ETZION,Binary and non-binary self-dual sequences and maximum period single-track Gray codes,inProceedings IEEE Symposium on Information Theory,Guangzhou, China 2026, pp. 1343–1348

    2026

  8. [16]

    ETZION,Constructions and properties of self-dual sequences,in preparation

    T. ETZION,Constructions and properties of self-dual sequences,in preparation

  9. [17]

    ETZION ANDA

    T. ETZION ANDA. LEMPEL,Construction of de Bruijn sequences of minimal complexity,IEEE Trans. on Infor. Theory,30 (1984) 705–709

    1984

  10. [18]

    ETZION ANDG

    T. ETZION ANDG. GREENBERG,Constructions for perfect mixed Codes and other covering codes,IEEE Trans. on Infor. Theory,39 (1993) 209–214

    1993

  11. [19]

    ETZION ANDB

    T. ETZION ANDB. MOUNITSQuasi-perfect codes with small distance,IEEE Trans. on Infor. Theory51 (2005) 3938–3946

    2005

  12. [20]

    ETZION, V

    T. ETZION, V. WEI,ANDZ. ZHANG,Bounds on the sizes of constant weight covering codes,Designs, Codes, and Crypto.,5 (1995) 117–239

    1995

  13. [21]

    R. L. GRAHAM ANDN. J. A. SLOANE,On the covering radius of codes,IEEE Trans. on Infor. Theory,31 (1985) 385–401

    1985

  14. [22]

    FREDRICKSEN,A survey of full length nonlinear shift register cycle algorithms,SIAM Review,24 (1982) 195–221

    H. FREDRICKSEN,A survey of full length nonlinear shift register cycle algorithms,SIAM Review,24 (1982) 195–221

    1982

  15. [23]

    W. C. HUFFMAN ANDV.PLESS,Fundamentals of Error-Correcting Codes,Cambridge University Press, 2003

    2003

  16. [24]

    KAI ANDS

    X. KAI ANDS. ZHU,New quantum MDS codes from negacyclic codes,IEEE Trans. on Infor. Theory59 (2012) 1193–1197

    2012

  17. [25]

    KRIVELEVICH, B

    M. KRIVELEVICH, B. SUDAKOV,ANDV. H. VU,Covering codes with improved density,IEEE Trans. on Infor. Theory,49 (2003) 1812–1815

    2003

  18. [26]

    C. D. ROSIN,Using reasoning models to generate search heuristics that solve open instances of combinatorial design problemss, https://arxiv.org/abs/2505.23881 (2025)

    2025 arXiv

  19. [27]

    R. M. ROTH,Introduction to Coding Theory,Cambridge, U.K.: Cambridge Univ. Press, 2006

    2006

  20. [28]

    STRUIK,Covering codes,Ph.D

    R. STRUIK,Covering codes,Ph.D. thesis, Eindhoven University of Technology, Eindhoven, The Netherlands, 1994

    1994

  21. [29]

    VU,De Bruijn covering codes with arbitrary alphabets,Advances in Applied Mathematics,34 (2005) 65–70

    V. VU,De Bruijn covering codes with arbitrary alphabets,Advances in Applied Mathematics,34 (2005) 65–70

    2005

Pith tools

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