{"id":"86052ab6-06f0-4d38-9525-848dfd895d53","arxiv_id":"2411.17145","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For strength 7, a sequence covering array with exactly t! permutations can only have 7, 8, or 9 symbols.","lead":"A new proof shows that any sequence covering array that covers all orderings of seven symbols with the minimum 5,040 permutations can contain at most nine symbols, so ten or more is impossible. This narrows Levenshtein's conjecture for the first unresolved case to a single open question, whether a 7-strength, 9-symbol array exists.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 rests on an unverified complete enumeration: if the search missed any CAX(42;2,5,6) with a constant row, the contradiction in the proof collapses; an independent re-enumeration is needed.","rationale":"The central claim of the paper is conditional on the completeness and correctness of the computer search, exactly as the reader identified. My review of Lemma 4 and Lemma 6 found no mathematical flaw: the counting argument is self-contained, and the use of multiplicity vectors to force a constant row in some CAX(42;2,5,6) is sound if an SCA(7!;7,10) exists. Therefore the entire weight of Theorem 1 sits on Theorem 2. The search description gives a reasonable recursive extension method, but the lack of released code or certificates means the uniqueness claim cannot be independently checked from the manuscript. The Theorem 14 parity error for t=2 is a separate issue and does not change the verdict on the main theorem, but it reinforces that the computational aspects should be made auditable. I agree with the reader's conditional verdict: accept the reasoning provisionally, but require an independent check of the enumeration before treating Theorem 1 as fully established.","tokens_in":14859,"tokens_out":9951,"duration_ms":89741,"concrete_test":"Independently enumerate all CAX(42;2,5,6): start from the unique CAX(42;2,2,6), add columns by an exact-cover or SAT model with constraints that every nonconstant pair is covered once and every constant pair twice, canonicalise the resulting arrays with nauty, and count isomorphism classes. If the count is not exactly one, or if any found array has a constant row, the proof of Theorem 1 fails. This directly verifies the load-bearing computation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing point is not the surrounding mathematics but the computational assertion in Theorem 2: up to isomorphism, CAX(42;2,5,6) is unique and has no constant rows. Lemma 6 is a clean counting argument: for fixed a and a fixed multiplicity vector, each of the t! permutations in an SCA(t!;t,v) contributes exactly one row with that multiplicity vector across the arrays C_a(X). Thus an SCA(7!;7,10) would force some CAX(42;2,5,6) to contain a constant row. The only way to get the contradiction in Theorem 1 is therefore the exhaustive search result. The recursive search description in Section 3 is plausible: the placement and partition conditions are necessary and sufficient for adding a column to a strength-2 excess coverage array. However, no code, no certificates, and no detailed canonical-labelling or isomorphism-pruning protocol are included, so completeness cannot be audited from the manuscript. A missed non-isomorphic array with a constant row would invalidate the central theorem. The small parity error in Theorem 14 for t=2 is real but independent of Theorem 1 and does not affect the main argument.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15078,"tokens_out":20969,"duration_ms":166256,"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":[{"comment":"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.","section":"Section 3, Theorem 2 and proof of Theorem 1"}],"minor_comments":[{"comment":"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.","section":"Section 2, Lemma 4"},{"comment":"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.","section":"Section 5, Theorem 14"},{"comment":"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.","section":"Figure 2"}],"recommendation":"major_revision","confidential_remarks":"The central theorem is conditional on an unverified exhaustive search. I would encourage the editor to require a reproducibility statement, code, or certificates (or at least a detailed algorithmic description) before acceptance. The errors in Lemma 4 and Theorem 14 are local and fixable, but they should not be left in the published version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Real progress on Levenshtein's conjecture. For t=7, the paper improves the known upper bound on v from 13 to 9, and the main argument is mostly clean. Lemma 6 is the key new tool: it forces, for any SCA(t!;t,v), the correct number of rows with each multiplicity vector in the associated CAX arrays. That turns the computational non-existence of a CAX(42;2,5,6) with a constant row into a proof that SCA(7!;7,10) does not exist. The reduction is sound and the paper is honest that SCA(7!;7,9) remains open.\n\nThe computational work is also a contribution in its own right: the tables giving the maximum number of columns for v≤6 and the counts by constant rows will be useful to anyone studying strength-2 excess coverage arrays. The orthogonal array connection in Section 4 is a neat observation.\n\nThe soft spot is exactly where the reader put it. Theorem 2, which carries the whole proof, is an exhaustive enumeration that is described in prose but not backed by code, certificates, or a detailed isomorphism-handling protocol. The placement/partition conditions are plausible and likely correct, but uniqueness up to isomorphism is a brittle property; a missed array with a constant row would collapse Theorem 1. This is not a fatal flaw by itself—the description is specific enough that a referee could re-implement the search—but it should be a condition of acceptance that the computation be made auditable.\n\nMinor issue: Theorem 14 counts isomorphism classes for even t, and the formula gives a non-integer for t=2 (1/2). The number of arrays is correct, but the isomorphism class statement needs fixing. This is independent of the main theorem.\n\nBottom line: for anyone working on sequence covering arrays or perfect SCAs, this paper is worth reading. The mathematics is honest and the result is meaningful. I would send it to a serious referee, but with a request for reproducible computational evidence.","headline":"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.","tokens_in":15609,"tokens_out":7687,"would_cite":false,"duration_ms":61567,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05B30","05B40","05B15"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["sequence covering array","excess coverage array","Levenshtein's conjecture","covering array","orthogonal array","perfect sequence covering array","multiplicity vector","combinatorial search"],"falsifier":"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.","tokens_in":67,"feed_emoji":"🧩","tokens_out":11915,"duration_ms":150824,"temperature":0.7,"pith_summary":"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.","feed_headline":"5040-permutation covering arrays cap out at 9 symbols","feed_subtitle":"A uniqueness computation forces the last open strength-7 case down to a single choice of symbol count.","key_machinery":"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.","core_discovery":"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)$.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Introduces excess coverage arrays, the Construction 3 link from sequence covering arrays, and the column bound k ≤ v+2 used to restrict to small cases.","marker":"[3]"},{"why":"States Levenshtein's conjecture that an SCA(t!;t,v) exists only for v=t or v=t+1, the target of this paper.","marker":"[10]"},{"why":"Proves the existence of SCA(t!;t,t+1), showing the conjectured arrays are real and fixing the t! minimum.","marker":"[11]"},{"why":"Provides the known order-6 counterexample at t=4 and confirms the conjecture for t≤6, leaving t=7 as the next open case.","marker":"[12]"},{"why":"Establishes the analogous non-existence of SCA(4!;4,7), a model for the exclusion proved here.","marker":"[8]"}],"fun_headline_variants":["Levenshtein conjecture: strength-7 case settled at v≤9","Proof: No 5040-permutation array for 10 symbols","Sequence covering arrays: v=10 impossible for strength 7","Excess coverage arrays: a uniqueness proof caps symbols at 9","Levenshtein's conjecture: v≤9 for SCA(7!;7,v)"],"cache_read_input_tokens":17792,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Levenshtein conjecture: strength-7 case settled at v≤9","Proof: No 5040-permutation array for 10 symbols","Sequence covering arrays: v=10 impossible for strength 7","Excess coverage arrays: a uniqueness proof caps symbols at 9","Levenshtein's conjecture: v≤9 for SCA(7!;7,v)"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000867,"raw_usage":{"total_tokens":3842,"prompt_tokens":1118,"completion_tokens":2724,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":734,"completion_tokens_details":{"reasoning_tokens":2625}},"tokens_in":734,"tokens_out":2724,"duration_ms":17239,"temperature":1.0,"reasoning_tokens":2625,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T12:29:06.957930+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces excess coverage arrays, the Construction 3 link from sequence covering arrays, and the column bound k ≤ v+2 used to restrict to small cases."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States Levenshtein's conjecture that an SCA(t!;t,v) exists only for v=t or v=t+1, the target of this paper."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Proves the existence of SCA(t!;t,t+1), showing the conjectured arrays are real and fixing the t! minimum."},{"cited_title":"Mathon and Tran Van Trung, Directed t-packings and directed t-Steiner systems, Des","cited_arxiv_id":null,"evidence_quote":"Provides the known order-6 counterexample at t=4 and confirms the conjecture for t≤6, leaving t=7 as the next open case."},{"cited_title":"Klein, On perfect deletion-correcting codes , J","cited_arxiv_id":null,"evidence_quote":"Establishes the analogous non-existence of SCA(4!;4,7), a model for the exclusion proved here."}],"review_version":1}