Pith. sign in

REVIEW 1 major objections 3 minor 17 references

Excess Coverage Arrays and Levenshtein's Conjecture

T0 review · 1 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read This paper proves that if a sequence covering array with 7! permutations exists, it can involve at most 9 symbols, settling the strength-7 case of Levenshtein's conjecture except for v=9.

desk verdict Strong progress on Levenshtein's conjecture for t=7, but the main theorem leans on a computer search that needs to be independently auditable before it's fully convincing. read the letter →

arxiv 2411.17145 v1 pith:KLZ7KDRC submitted 2024-11-26 math.CO

Amber E. Gentle , Daniel Horsley , Ian M. Wanless This is my paper · ORCID
classification math.CO MSC 05B3005B4005B15
keywords sequencecoveringarrayexcesscoverageLevenshtein'sconjectureorthogonalperfectmultiplicityvectorcombinatorialsearch
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 takes on the smallest open case of Levenshtein's conjecture, which says that a sequence covering array using the minimum possible number of permutations, $t!$, can only exist on $t$ or $t+1$ symbols. The authors prove that for $t=7$, no such array on $10$ symbols exists, so any minimal array covers at most $9$ symbols. The proof converts a hypothetical $\mathrm{SCA}(7!;7,10)$ into small strength-2 excess coverage arrays, then combines a counting lemma with an exhaustive computation showing the only such array lacks a row the counting lemma would force. If the result is right, the only unresolved question for strength $7$ is whether a $7!$-permutation array on $9$ symbols exists.

What carries the argument

The load-bearing object is the strength-2 excess coverage array $\mathrm{CA}_X(N;2,k,v)$, an $N \times k$ array over $v$ symbols in which every ordered pair of distinct symbols appears at least once in each pair of columns and every equal-symbol pair appears at least twice. The proof uses the standard Construction 3, which turns any $\mathrm{SCA}(t!;t,v)$ into such arrays, together with a new counting lemma: for nonnegative integers $m_0,\dots,m_a$ summing to $v-a$, across all arrays produced by deleting a fixed set of $a$ symbols, exactly $t!$ rows have that multiplicity vector. Applied with $a=5$, $t=7$, $v=10$, the lemma forces a constant row, a row whose entries are all equal, into some $\mathrm{CA}_X(42;2,5,6)$ if the original array existed. The exhaustive enumeration of $\mathrm{CA}_X(42;2,5,6)$ finds this array unique and constant-row-free, which is what yields the contradiction.

What would settle it

Re-run the enumeration independently, for example with a SAT or constraint solver using a different canonical-labelling routine, and look for any $\mathrm{CA}_X(42;2,5,6)$ containing a constant row or any $\mathrm{CA}_X(42;2,6,6)$; finding either would overturn Theorem 2 and with it the proof of Theorem 1.

Watch

Extended reading notes

Core claim

The central result is Theorem 1: if a sequence covering array $\mathrm{SCA}(7!;7,v)$ exists, then $v$ is one of $7,8,9$; in particular, $\mathrm{SCA}(7!;7,10)$ does not exist. The proof combines Lemma 6, which counts multiplicity vectors across all arrays obtained by deleting five symbols from a hypothetical $\mathrm{SCA}(7!;7,10)$, with an exhaustive computation showing there is exactly one strength-2 excess coverage array $\mathrm{CA}_X(42;2,5,6)$ up to isomorphism and that it has no constant row. Since Lemma 6 would force a constant row into one of those arrays, the contradiction rules out $v=10$, and the absence of any $\mathrm{CA}_X(42;2,6,6)$ rules out $v \geqslant 11$. Along the way the paper determines the maximum number of columns for $\mathrm{CA}_X(v(v+1);2,k,v)$ for $2 \leqslant v \leqslant 6$ and classifies binary excess coverage arrays $\mathrm{CA}_X((t+1)!;t,t+1,2)$.

Load-bearing premise

The exhaustive computer search reported in Section 3 is complete and bug-free: there is exactly one $\mathrm{CA}_X(42;2,5,6)$ up to isomorphism, it has no constant rows, and no $\mathrm{CA}_X(42;2,6,6)$ exists; if the search missed a non-isomorphic array or misclassified constant rows, Theorem 1 loses its support.

Editorial extensions

If this is right

  • The existence question for $\mathrm{SCA}(7!;7,v)$ is settled for every $v$ except $v=9$; a positive or negative answer for $v=9$ resolves Levenshtein's conjecture at strength $7$.
  • Since no $\mathrm{CA}_X(42;2,6,6)$ exists, the lower bound $\mathrm{SCAN}(7,11) \geqslant 5160$ follows, along with $\mathrm{SCAN}(4,7) \geqslant 26$, $\mathrm{SCAN}(5,9) \geqslant 126$, and $\mathrm{SCAN}(6,11) \geqslant 744$.
  • The column bound $k \leqslant v+2$ for $\mathrm{CA}_X(v(v+1);2,k,v)$ now holds for $v=2,3$ as well as for $v \geqslant 4$; among $2 \leqslant v \leqslant 6$, only $v=2$ attains it.
  • Binary excess coverage arrays $\mathrm{CA}_X((t+1)!;t,t+1,2)$ are fully classified: there are $\lfloor t/2 \rfloor! \lceil t/2 \rceil! + 1$ distinct arrays, with the stated isomorphism classes for odd and even $t$.
  • For every $t \leqslant 17$, an array $\mathrm{CA}_X((t+1)!;t,2t,2)$ exists, so the existing upper bound $v \leqslant 2t-1$ on symbols in an $\mathrm{SCA}(t!;t,v)$ cannot be improved by this counting method for $t \leqslant 18$.

Reading between the lines

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

  • The same multiplicity-vector test could in principle be run at $t=8$, but the paper's own counts for $\mathrm{CA}_X(56;2,3,7)$ and $\mathrm{CA}_X(56;2,4,7)$ suggest exhaustive cataloguing becomes prohibitive; a proof for $t \geqslant 8$ likely needs a structural description of these arrays rather than brute-force enumeration.
  • Because the unique $\mathrm{CA}_X(42;2,5,6)$ is constant-row-free, Lemma 6 implies that if an $\mathrm{SCA}(7!;7,10)$ existed, the forced constant row would have to belong to a different, non-isomorphic $\mathrm{CA}_X(42;2,5,6)$; an independent search for such an array is therefore a direct stress-test of the computational uniqueness claim.
  • The binary classification shows that multiplicity-symmetric linear systems are too permissive, admitting solutions up to $t=17$; ruling out $\mathrm{SCA}(t!;t,2t-1)$ for larger $t$ will require constraints beyond interaction counts, such as automorphism or row-level conditions.
  • The appearance of a $6 \times 6$ Latin square with many transversals inside the unique $\mathrm{CA}_X(42;2,5,6)$ suggests a possible translation of the remaining $v=9$ question into Latin-square language, where existing tools might apply.
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

1 major / 3 minor

Summary. The paper proves Theorem 1: if an SCA(7!;7,v) exists, then v ∈ {7,8,9}. This eliminates the v=10 case of Levenshtein's conjecture for t=7. The proof connects sequence covering arrays to strength-2 excess coverage arrays via a deletion construction. Lemma 6 gives a counting condition: if an SCA(7!;7,10) exists, then across the arrays obtained by deleting 5 symbols there must be exactly 7! rows with any prescribed multiplicity vector, in particular a constant row. The paper then invokes a computer search (Theorem 2) to show that, up to isomorphism, there is a unique CAX(42;2,5,6) and it contains no constant rows. The contradiction proves Theorem 1. The paper also reports exhaustive computational results on maximum numbers of columns of CAX(v(v+1);2,k,v) for v ≤ 6, studies the relation between these arrays and orthogonal arrays, and analyzes binary excess coverage arrays.

Significance. If the computational classification is correct, the main theorem is a genuine advance on the smallest open case of Levenshtein's conjecture, reducing the admissible orders for t=7 from {7,...,13} to {7,8,9}. The reduction via Lemma 6 is elegant and gives a necessary condition that is both simple and powerful. The paper also provides useful data (Tables 1–3) and a nice connection between excess coverage arrays and orthogonal arrays (Lemmas 10–11). The chief weakness is that the central contradiction depends on an exhaustive computer search whose completeness is not independently auditable from the manuscript: no code, certificates, or detailed isomorphism-pruning protocol are supplied. This is the main risk to the central claim.

major comments (1)
  1. [Section 3, Theorem 2 and proof of Theorem 1] The exhaustive enumeration of CAX(42;2,5,6) is the load-bearing premise of the proof, but the paper does not provide enough information to certify its completeness. The recursive search using placements and partitions is plausible, but the description leaves unspecified the canonical labelling, the isomorphism invariants used for screening, and the exact search order. No code, certificates, or data files are shipped. If the search missed any non-isomorphic CAX(42;2,5,6) with a constant row, the contradiction in Theorem 1 collapses. I recommend that the authors make the search code and the unique array available in machine-readable form, or provide independent completeness certificates, or at minimum give a detailed algorithmic specification (including all pruning and isomorphism rejection rules) sufficient for reproduction.
minor comments (3)
  1. [Section 2, Lemma 4] The statement that every C ∈ C_a(X) is a CAX(|C|; 2, v−t+2, t−1) is only correct for a = t−2; the proof actually establishes that C is a CAX(|C|; t−a, v−a, a+1) for arbitrary a. The sentence before the lemma also says 'every sequence of length t−a is covered by exactly t!/a!' which should read 'every sequence of length a'. These typos should be corrected; they do not affect the proof of Theorem 1, but they make the general framework incorrect as written.
  2. [Section 5, Theorem 14] The formula for the number of isomorphism classes in the even t case fails for t=2: the expression ⌊t/2⌋!⌈t/2⌉!/2 is not an integer, and the claimed singleton class does not exist because the condition x_{t/2}=x_{t/2+1} has no integer solution when t=2. The proof should handle this exceptional case separately or state the condition under which the singleton class exists.
  3. [Figure 2] The unique CAX(42;2,5,6) is displayed as 14 lines of 15 entries each; it would be clearer to present it explicitly as 42 rows of 5 columns, or to add a note explaining the compact format.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 follows from a definitional counting argument and an independent exhaustive enumeration.

full rationale

I traced the derivation of the central result, Theorem 1. The paper defines SCA(N;t,v) and CAX(N;2,k,v) independently, and Lemma 6 derives a necessary condition for an SCA(t!;t,v) purely from the definition: across all arrays obtained by deleting a symbols from the permutations, every multiplicity vector occurs exactly t! times. The contradiction for v=10 is then obtained by combining this necessary condition with the computational classification in Theorem 2, which says there is exactly one CAX(42;2,5,6) up to isomorphism and it has no constant rows. The computational search is described as a recursive enumeration with necessary and sufficient extension conditions; it does not assume the existence of the SCA whose impossibility it proves. No parameter is fitted to the target conclusion, and no quantity called a prediction is constructed from data that includes the target statement. The paper does cite Chee et al. [3], which shares a co-author, for the concept of excess coverage arrays and some prior bounds, but the key connection used here is re-proved in Lemma 4, and the decisive uniqueness result is the authors' own computation, not an imported theorem. Thus the cited prior work is not load-bearing for the main contradiction. The exhaustive search is not independently audited because no code or certificates are included, but that is a reproducibility and verification concern, not circularity. No self-definitional reduction, fitted-input-as-prediction, or smuggling of an ansatz via citation is present. Overall, the derivation chain is self-contained apart from an unverified but non-circular computational assertion.

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

No free parameters or invented entities are introduced. The proof relies on two kinds of input: standard combinatorial counting, which is proved in the text, and the correctness and completeness of the computer search. The search is the only part not independently auditable from the paper, since no code or certificate is provided.

assumptions (2)
  • domain assumption The recursive placement search in Section 3 is complete: every CAX(v(v+1);2,k,v) with k>=2 can be obtained by adding one column to some array in the catalogue of k-column arrays.
    The proof of Theorem 1 depends on the exhaustiveness of this search. The paper states that it recursively found all ways but provides no formal completeness proof and no code or certificate.
  • domain assumption The reported computations are correct as executed, in particular the uniqueness of CAX(42;2,5,6) up to isomorphism and the nonexistence of CAX(42;2,6,6).
    These computational outputs are the load-bearing facts in the proof of Theorem 1. No machine-checkable artifact is shipped.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Excess Coverage Arrays and Levenshtein's Conjecture." pith.science (2026). https://pith.science/paper/KLZ7KDRC

@misc{pith2026241117145,
  author       = {Pith},
  title        = {Pith review of: Excess Coverage Arrays and Levenshtein's Conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KLZ7KDRC}},
  note         = {Machine review of arXiv:2411.17145}
}
abstract

A sequence covering array, denoted \textsf{SCA}$(N;t,v)$, is a set of $N$ permutations of $\{0, \dots, v-1 \}$ such that each sequence of $t$ distinct elements of $\{0, \dots, v-1\}$ reads left to right in at least one permutation. The minimum number of permutations such a sequence covering array can have is $t!$ and Levenshtein conjectured that if a sequence covering array with $t!$ permutations exists, then $v \in \{t,t+1\}$. In this paper, we prove that if an \textsf{SCA}$(7!;7,v)$ exists, then $v \leq 9$. We do this by analysing connections between sequence covering arrays and a special kind of covering array called an excess coverage array. A strength 2 excess coverage array, denoted \textsf{CA}$_{X}(N;2,k,v)$, is an $N \times k$ array with entries from $\{0, \dots, v - 1\}$ such that every ordered pair of distinct symbols appear at least once in each pair of columns and all other pairs appear at least twice. We demonstrate computationally that there is a unique \textsf{CA}$_{X}(42;2,5,6)$, and we prove that this array alone does not satisfy necessary conditions we establish for the existence of an \textsf{SCA}$(7!;7,10)$. Furthermore, we find the maximum possible number of columns for strength 2 excess coverage arrays with symbol sets of sizes between 2 and 6, and more broadly investigate binary excess coverage arrays.

Figures

Figures reproduced from arXiv: 2411.17145 by the authors.

Figure 1
Figure 1. A CAX(6; 2, 4, 2). exist. By Lemma 4, this already shows that an SCA(7!; 7, 11) does not exist. As stated in Theorem 2, there is a unique CAX(42; 2, 5, 6). We can use this array and Lemma 6 to do better and prove Theorem 1. Proof of Theorem 1. Our computations found exactly one CAX(42; 2, 5, 6) up to iso￾morphism. This is given in [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. The unique CAX(42; 2, 5, 6). Lemma 8. For integers v, k > 2, CAN(2, k, v) 6 CANX(2, k, v) 6 CAN(2, k, v) + v. Proof. A CAX(N; 2, k, v) is also a CA(N; 2, k, v) so the first inequality holds. Let N = CAN(2, k, v) and let N′ = CAN(2, k, v) + v. Let C be a CA(N; 2, k, v) and let D be a v × k array such that D[i, j] = i for i ∈ [v] and j ∈ [k]. Then, every 2-way interaction is covered at least once in C and every consta… view at source ↗
Figure 3
Figure 3. A CAX(42; 2, 4, 6). Although it does not contain an orthogonal array, the deletion of any column forms a CAX(42; 2, 3, 6) that does contain an orthogonal array. 0 2 3 5 4 1 2 3 0 4 1 5 1 0 4 3 5 2 3 5 2 1 0 4 5 4 1 0 2 3 4 1 5 2 3 0 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Latin square obtained by deleting 2 columns from th [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Banbara, N

    M. Banbara, N. Tamura and K. Inoue, Generating event-sequence test cases by answer set programming with the incidence matrix , Technical Communications of the 28th International Conference on Logic Programming, (2 012), 86—97

    work page

  2. [2]

    Brain, E

    M. Brain, E. Erdem, K. Inoue, J. Oetsch, J. P¨ uhrer, H. Tom pits, and C. Yilmaz, Event-sequence testing using answer-set programming, Int. J. Adv. Softw., 5 (2012), 237-–251

    work page 2012

  3. [3]

    Y. M. Chee, C. J. Colbourn, D. Horsley and J. Zhou, Sequence covering arrays , SIAM J. Disc. Math., 27 (2013), 1844–1861

    work page 2013

  4. [4]

    Gentle, A polynomial construction of perfect sequence covering arr ays, Algebr

    A. Gentle, A polynomial construction of perfect sequence covering arr ays, Algebr. Comb., 6 (2023), 1383–1394. 13

    work page 2023

  5. [5]

    Gentle and I

    A. Gentle and I. M. Wanless, On perfect sequence covering arrays , Ann. Comb., 27 (2023), 539–564

    work page 2023

  6. [6]

    A. S. Hedayat, N. J. A. Sloane and J. Stufken. Orthogonal arrays, Springer Series in Statistics, Springer-Verlag, New York, (1999)

    work page 1999

  7. [7]

    Iurlano, Growth of the perfect sequence covering array number , Des

    E. Iurlano, Growth of the perfect sequence covering array number , Des. Codes. Cryptogr., 91 (2023), 1487–1494

    work page 2023

  8. [8]

    Klein, On perfect deletion-correcting codes , J

    A. Klein, On perfect deletion-correcting codes , J. Combin. Des., 12 (2004), 72–77

    work page 2004

Show all 17 references
  1. [9]

    D. R. Kuhn, J. M. Higdon, J. F. Lawrence, R. N. Kacker and Y. Lei, Combinato- rial methods for event sequence testing , Proceedings of the IEEE 5th International Conference on Software Testing, Verification and Validatio n, (2012), 601–609

    2012

  2. [10]

    V. I. Levenshtein, Perfect deletion-correcting codes as combinatorial desig ns, II In- ternational Workshop Algebraic and Combinatorial Coding T heory, (1990), 137– 140

    1990

  3. [11]

    V. I. Levenshtein, Perfect codes in the metric of deletions and insertions , Diskret. Mat., 3 (1991), 3–20

    1991

  4. [12]

    Mathon and Tran Van Trung, Directed t-packings and directed t-Steiner systems, Des

    R. Mathon and Tran Van Trung, Directed t-packings and directed t-Steiner systems, Des. Codes Cryptogr., 18 (1999), 187–198

    1999

  5. [13]

    P. C. Murray and C. J. Colbourn, Sequence covering arrays and linear exten- sions, Combinatorial Algorithms, Lecture Notes in Computer Scie nce volume 8986, Springer, Cham., (2015), 274–285

    2015

  6. [14]

    J. Na, J. Jedwab and S. Li, A group-based structure for perfect sequence covering arrays, Des. Codes Crypt. 91 (2023), 951–970

    2023

  7. [15]

    Spencer, Minimal scrambling sets of simple orders , Acta Math

    J. Spencer, Minimal scrambling sets of simple orders , Acta Math. Acad. Sci. Hun- gar., 22 (1971), 349–353

    1971

  8. [16]

    Torres-Jimenez, D

    J. Torres-Jimenez, D. O. Ramirez-Acuna, B. Acevedo-Ju ´ arez and H. Avila-George, New upper bounds for sequence covering arrays using a 3-stage approach, Expert Systems with Applications, 207 (2022), 118022

    2022

  9. [17]

    Yuster, Perfect sequence covering arrays, Des

    R. Yuster, Perfect sequence covering arrays, Des. Codes Cryptogr., 88 (2020), 585– 593. 14

    2020

Pith tools

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