pith. sign in

arxiv: 2605.03589 · v1 · submitted 2026-05-05 · 💻 cs.IT · math.IT

New bounds on the covering radius of orthogonal arrays of even strength

Peter Boyvalenkov , Ferruh Ozbudak , Maya Stoyanova This is my paper

Pith reviewed 2026-05-07 13:39 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords orthogonal arrayscovering radiuslinear programming boundsbinary codesBCH codesMelas codesZetterberg codesalgebraic curves
0
0 comments X

The pith

New linear programming bounds improve on prior estimates for the covering radius of non-tight binary orthogonal arrays of even strength.

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

The paper establishes tighter upper bounds on the covering radius for binary orthogonal arrays of strength 2k that are larger than the minimum Rao size. It considers two geometric cases for the points that achieve the maximum distance: when the farthest array point from a given y is not the antipode of y, and when every such farthest point has its antipode also inside the array. In both cases the new bounds beat the Tietäväinen-Fazekas-Levenshtein bound precisely when the array is non-tight. The authors also construct three infinite families from the duals of BCH, Melas, and Zetterberg codes, obtain lower bounds on their radii via algebraic curves over finite fields, and combine these with the new upper bounds to produce close estimates in several cases.

Core claim

We obtain new linear programming (LP) and constructive bounds for the covering radius of binary orthogonal arrays of strength 2k. Our LP bounds develop in two alternative scenarios. First, if a point y in F_2^n where the covering radius of some orthogonal array C subset F_2^n of strength 2k is realized is such that the farthest point of C to y is not antipodal to y, we obtain a bound which is better than the Tietäväinen (or Fazekas-Levenshtein) bound for non-tight arrays. Second, if all points where the covering radius is realized are such that their antipodes are in C, we obtain a bound which depends on the cardinality of C and is again better whenever the orthogonal array is not tight. We

What carries the argument

The linear programming bounds conditioned on whether points realizing the covering radius are antipodal to each other or not, applied only to non-tight arrays.

If this is right

  • For the three infinite families constructed from dual BCH, Melas, and Zetterberg codes, the combination of algebraic-geometry lower bounds and the new LP upper bounds produces estimates that are close in several cases.
  • Whenever an orthogonal array of even strength exceeds the Rao lower bound, its covering radius is bounded above by a quantity strictly smaller than the Tietäväinen-Fazekas-Levenshtein value under either antipodal condition.
  • The new bounds depend explicitly on the cardinality of the array and therefore become stronger as the array grows while remaining non-tight.
  • Constructive lower bounds derived from algebraic curves over finite fields can be paired with the LP upper bounds to narrow the possible range for the covering radius of each family member.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The antipodal/non-antipodal distinction may suggest a way to partition the space into regions whose distances to the array can be controlled separately.
  • Similar LP conditioning on geometric configurations could be tried for orthogonal arrays over alphabets larger than two.
  • The close estimates obtained for the BCH, Melas, and Zetterberg dual families indicate that exact covering radii may be determinable for additional infinite families by refining the same pair of techniques.

Load-bearing premise

The improved LP bounds require the array to be non-tight and to satisfy one of two specific geometric conditions on the points that realize the covering radius.

What would settle it

Take a small explicit non-tight binary orthogonal array of strength 4, compute its exact covering radius by exhaustive search, and check whether the new LP upper bound is strictly smaller than the Tietäväinen bound.

read the original abstract

We obtain new linear programming (LP) and constructive bounds for the covering radius of binary orthogonal arrays of strength $2k$. Our LP bounds develop in two alternative scenarios. First, if a point $y \in F_2^n$, where the covering radius of some orthogonal array $C \subset F_2^n$ of strength $2k$ is realized, is such that the farthest point of $C$ to $y$ is not antipodal to $y$ we obtain a bound which is better than the Tiet{\"a}v{\"a}inen (or Fazekas-Levenshtein) bound for non-tight arrays (i.e., the cardinality strictly exceeds the Rao lower bound). Second, if all points where the covering radius is realized are such that their antipodes are in $C$, we obtain a bound which depends on the cardinality of $C$ and is again better whenever the orthogonal array is not tight. We further describe three infinite families of binary orthogonal arrays related to the duals of BCH, Melas, and Zetterberg codes. For these families, we derive lower bounds on the covering radius by applying techniques from algebraic curves over finite fields, while the improved linear programming methods developed in this paper provide upper bounds, leading in some cases to fairly close estimates.

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

1 major / 0 minor

Summary. The paper derives new linear programming bounds for the covering radius of binary orthogonal arrays of strength 2k under two alternative geometric conditions on points realizing the radius (non-antipodal farthest codeword or all such antipodes included in the array). These are claimed to improve on the Tietäväinen/Fazekas-Levenshtein bound for non-tight arrays. It also constructs three infinite families from duals of BCH, Melas, and Zetterberg codes, obtains algebraic-curve lower bounds on their covering radii, and pairs them with the LP upper bounds to produce close estimates in some cases.

Significance. If the conditional LP improvements apply to the families considered, the work would tighten known covering-radius estimates for these orthogonal arrays and demonstrate a useful combination of linear programming and algebraic-geometry techniques in coding theory. The constructive families and curve-based lower bounds constitute a concrete contribution even if the LP gains require further verification.

major comments (1)
  1. [Abstract and LP-bound derivations] The central claim of strictly improved LP bounds for non-tight arrays rests on the two geometric scenarios (non-antipodal farthest point or antipodes inside C). The manuscript derives the improvement only after imposing these restrictions as hypotheses; it must verify that at least one scenario holds for each of the three infinite families (duals of BCH, Melas, Zetterberg codes) or else the new bounds collapse to the classical Tietäväinen/Fazekas-Levenshtein bound and the claimed advance disappears for those families.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the major comment point by point below and will revise the paper accordingly to strengthen the presentation of the LP bounds and their applicability.

read point-by-point responses

  1. Referee: [Abstract and LP-bound derivations] The central claim of strictly improved LP bounds for non-tight arrays rests on the two geometric scenarios (non-antipodal farthest point or antipodes inside C). The manuscript derives the improvement only after imposing these restrictions as hypotheses; it must verify that at least one scenario holds for each of the three infinite families (duals of BCH, Melas, Zetterberg codes) or else the new bounds collapse to the classical Tietäväinen/Fazekas-Levenshtein bound and the claimed advance disappears for those families.

    Authors: We agree that the improved LP bounds are derived conditionally on the two geometric scenarios and that explicit verification is required to claim strict improvements for the three families. The manuscript presents the bounds under these alternative hypotheses and applies them to obtain the reported estimates, but does not contain a dedicated verification subsection for the families. In the revised version we will add such a subsection. For the duals of extended BCH codes we will show that, for parameters where the covering radius is realized, there exist points y with a non-antipodal farthest codeword, using the known weight distribution and the algebraic structure. For the dual Melas and Zetterberg families we will verify that the antipodes of all radius-realizing points lie inside the array, again exploiting the code properties and, for small lengths, direct enumeration that extends to the infinite case via the curve-based constructions already in the paper. These additions will confirm that at least one scenario holds in each case, so the new bounds apply and yield the claimed improvements over the Tietäväinen/Fazekas-Levenshtein bound. revision: yes

Circularity Check

0 steps flagged

No circularity: conditional LP bounds derived independently under explicit geometric hypotheses

full rationale

The paper derives its new LP bounds by explicitly conditioning on two alternative geometric scenarios for points realizing the covering radius (non-antipodal farthest codeword, or antipodes included in the array). These conditions are stated as hypotheses, and the resulting inequalities are obtained via standard linear programming on the distance distribution of the orthogonal array, improving the Tietäväinen/Fazekas-Levenshtein bound only when the array is non-tight and the scenario applies. No step reduces by construction to a fitted parameter, self-definition, or prior self-citation chain; the algebraic-curve lower bounds for the BCH/Melas/Zetterberg dual families are likewise independent. The derivation chain remains self-contained against external coding-theory benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review prevents identification of specific free parameters, axioms, or invented entities; none are explicitly named in the provided text.

pith-pipeline@v0.9.0 · 5537 in / 1044 out tokens · 48446 ms · 2026-05-07T13:39:35.783254+00:00 · methodology

Review history (2 revisions) →

discussion (0)

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

Reference graph

Works this paper leans on

38 extracted references · 38 canonical work pages

  1. [1]

    Ashikhmin, I

    A. Ashikhmin, I. Honkala, T. Laihonen, S. Litsyn, On relations between covering radius and dual distance,IEEE Trans. Inform. Theory, 45, 1999, 1808–1816

    work page 1999

  2. [2]

    Bannai, Et

    Ei. Bannai, Et. Bannai, T. Ito, R. Tanaka,Algebraic Combinatorics, Berlin, Boston, De Gruyter, 2021

    work page 2021

  3. [3]

    Boyvalenkov, P

    P. Boyvalenkov, P. Dragnev, D. Hardin, E. Saff, M. Stoyanova, On spherical codes with inner products in prescribed interval,Designs Codes Cryptography87, 299–315 (2019)

    work page 2019

  4. [4]

    Boyvalenkov, P

    P. Boyvalenkov, P. Dragnev, D. Hardin, E. Saff, M. Stoyanova, Universal bounds for size and energy of codes of given minimum and maximum distances,IEEE Transactions on Information Theory, ”From Deletion-Correction to Graph Reconstruction: In Memory of Vladimir I. Levenshtein”, 67(6), 2021, 3569-3584 (arXiv:1910.07274)

    work page arXiv 2021

  5. [5]

    Boyvalenkov, M

    P. Boyvalenkov, M. Stoyanova, Linear programming bounds for covering radius of spherical designs,Results in Mathematics, 76, art. 95 (19 pages), 2021

    work page 2021

  6. [6]

    Boyvalenkov, T

    P. Boyvalenkov, T. Marinova, M. Stoyanova, Nonexistence of few binary orthogonal arrays,Discrete Applied Mathematics, 217(P2), 2017, 144–150

    work page 2017

  7. [7]

    Carter, M

    J. Carter, M. Wegman, Universal classes of hash functions.Journal of Computer and System Sciences18, 1979, 143–154

    work page 1979

  8. [8]

    Dawson, E

    E. Dawson, E. Mahmoodian, Orthogonal arrays and ordered threshold schemes,Australasian Journal of Com- binatorics, 8, 1993, 27–44

    work page 1993

  9. [9]

    Delsarte,An Algebraic Approach to the Association Schemes in Coding Theory, Philips Res

    P. Delsarte,An Algebraic Approach to the Association Schemes in Coding Theory, Philips Res. Rep. Suppl. 10, 1973

    work page 1973

  10. [10]

    Delsarte, Four fundamental parameters of a code and their combinatorial significance,Inform

    P. Delsarte, Four fundamental parameters of a code and their combinatorial significance,Inform. Contr.23 (1973) 407-438

    work page 1973

  11. [11]

    The optimal double-error correcting codes of Zetterberg and Dumer–Zinoviev are quasiper- fect,

    S. M. Dodunekov, “The optimal double-error correcting codes of Zetterberg and Dumer–Zinoviev are quasiper- fect,”C.R. de l’Acad´ emie bulgare des Sciences, tome 38, nr. 9, pp. 1121–1123, 1985

    work page 1985

  12. [12]

    Algebraic Decoding of the Zetterberg Codes,

    S. M. Dodunekov and J. E. M. Nilsson, “Algebraic Decoding of the Zetterberg Codes,”IEEE Transactions on Information Theory, vol. 38, no. 5, pp. 1570–1573, Sept. 1992

    work page 1992

  13. [13]

    Fazekas, V

    G. Fazekas, V. I. Levenshtein, On upper bounds for code distance and covering radius of designs in polynomial metric spaces,J. Comb. Theory A, 70, 267-288 (1995)

    work page 1995

  14. [14]

    A. L. Gavrilyuk, S. Suda, Extremal orthogonal arrays, arXiv:2512.23459. BOUNDS ON THE COVERING RADIUS OF ORTHOGONAL ARRAYS 23

    work page arXiv

  15. [15]

    A. L. Gavrilyuk, S. Suda, J. Vidali, On tight 4-designs in Hamming association schemes,Combinatorica, 40 (2020) 345–362

    work page 2020

  16. [16]

    Gopalakrishnan, D

    K. Gopalakrishnan, D. Stinson, Applications of orthogonal arrays to computer science. Ramanujan Mathematical Society, Lecture Notes Series in Mathematics, 7, 2008, 149–164

    work page 2008

  17. [17]

    Weil–Serre Type Bounds for Cyclic Codes,

    C. G¨ uneri, F.¨Ozbudak, “Weil–Serre Type Bounds for Cyclic Codes,”IEEE Transactions on Information Theory, vol. 54, no. 12, pp. 5381–5395, Dec. 2008

    work page 2008

  18. [18]

    Hedayat, N

    A. Hedayat, N. J. A. Sloane, J. Stufken, Orthogonal Arrays: Theory and Applications. Springer-Verlag, New York, 1999

    work page 1999

  19. [19]

    V. I. Levenshtein, Designs as maximum codes in polynomial metric spaces,Acta Appl. Math.25, 1992, 1–82

    work page 1992

  20. [20]

    V. I. Levenshtein, Krawtchouk polynomials and universal bounds for codes and designs in Hamming spaces, IEEE Trans. Inform. Theory41, 1995, 1303–1321

    work page 1995

  21. [21]

    V. I. Levenshtein, Universal bounds for codes and designs, Chapter 6 (499-648) inHandbook of Coding Theory, Eds. V.Pless and W.C.Huffman, Elsevier Science B.V., 1998

    work page 1998

  22. [22]

    Litsyn, P

    S. Litsyn, P. Sol´ e, R. Struik, On the covering radius of an unrestricted code as a function of the rate and dual distance,Discr. Appl. Math., 82, 1998, 177–191

    work page 1998

  23. [23]

    Litsyn,A

    S. Litsyn,A. Tiet¨ av¨ ainen, Upper bounds on the covering radius of a code with a given dual distance,Europ. J. Combin., 17, 1996, 265–270

    work page 1996

  24. [24]

    F. J. MacWilliams and N. J. A. Sloane,The Theory of Error-Correcting Codes, North-Holland Mathematical Library, Vol. 16, North-Holland Publishing Company, Amsterdam–New York–Oxford, 1977

    work page 1977

  25. [25]

    Further results on quasiperfect codes related to Goppa codes,

    O. Moreno, “Further results on quasiperfect codes related to Goppa codes,”Congressus Numerantium, vol. 40, pp. 249–256, 1983

    work page 1983

  26. [26]

    Mukerjee, S

    R. Mukerjee, S. Kageyama, On existence of two symbol complete orthogonal arrays,J. Combin. Theory Ser. A, 66, 1994, 176–181

    work page 1994

  27. [27]

    Noda, On orthogonal arrays of strength 4 achieving Rao’s bound,J

    R. Noda, On orthogonal arrays of strength 4 achieving Rao’s bound,J. London Math. Soc.(2), 19, 1979, 385–390

    work page 1979

  28. [28]

    C. R. Rao, Factorial experiments derivable from combinatorial arrangements of arrays,J. Royal Stat. Soc.89 (1947) 128–139

    work page 1947

  29. [29]

    Hecke Operators and the Weight Distributions of Certain Codes,

    R. Schoof and M. van der Vlugt, “Hecke Operators and the Weight Distributions of Certain Codes,”Journal of Combinatorial Theory, Series A, vol. 57, pp. 163–186, 1991

    work page 1991

  30. [30]

    Sol´ e, Packing radius, covering radius, and dual distance,IEEE Trans

    P. Sol´ e, Packing radius, covering radius, and dual distance,IEEE Trans. Inform. Theory, 41, 1995, 268–272

    work page 1995

  31. [31]

    Sol´ e, P

    P. Sol´ e, P. Stokes, Covering radius, codimension, and dual-distance width,IEEE Trans. Inform. Theory, 39, 1993, 1195–1203

    work page 1993

  32. [32]

    Stichtenoth,Algebraic Function Fields and Codes, Graduate Texts in Mathematics, Vol

    H. Stichtenoth,Algebraic Function Fields and Codes, Graduate Texts in Mathematics, Vol. 254, Springer-Verlag, Berlin–Heidelberg, 2nd ed., 2009

    work page 2009

  33. [33]

    Stinson, Combinatorial techniques for universal hashing,Journal of Computer and System Sciences, 48, 1994, 337–346

    D. Stinson, Combinatorial techniques for universal hashing,Journal of Computer and System Sciences, 48, 1994, 337–346

    work page 1994

  34. [34]

    Tiet¨ av¨ ainen, An upper bound on the covering radius as a function of the dual distance,IEEE Trans

    A. Tiet¨ av¨ ainen, An upper bound on the covering radius as a function of the dual distance,IEEE Trans. Inform. Theory, 36 (1990) 1472–1474

    work page 1990

  35. [35]

    Tiet¨ av¨ ainen, Covering radius and dual distance,Des

    A. Tiet¨ av¨ ainen, Covering radius and dual distance,Des. Codes Cryptogr.1(1991) 31–46

    work page 1991

  36. [36]

    New bounds on cyclic codes from algebraic curves,

    J. Wolfmann, “New bounds on cyclic codes from algebraic curves,” inLecture Notes in Computer Science. New York: Springer-Verlag, 1989, vol. 388, pp. 47–62

    work page 1989

  37. [37]

    Szeg¨ o,Orthogonal polynomials, AMS Col

    G. Szeg¨ o,Orthogonal polynomials, AMS Col. Publ., vol. 23, Providence, RI, 1939

    work page 1939

  38. [38]

    Cyclic codes from irreducible polynomials for correction of multiple errors,

    L. H. Zetterberg, “Cyclic codes from irreducible polynomials for correction of multiple errors,”IRE Trans. Inform. Theory, vol. IT-8, pp. 13–20, 1962. Institute of Mathematics and Informatics, Bulgarian Academy of Sciences, 8 G Bonchev Str., 1113 Sofia, Bulgaria Email address:peter@math.bas.bg Faculty of Engineering and Natural Sciences, Sabancı Universit...

    work page 1962