{"id":"cabbb85f-4149-4705-bc09-df759fc35762","arxiv_id":"2502.08424","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"New constructions improve upper bounds on shortest (n,R)-covering sequences and introduce covering 2D-sequences, with near-optimal radius-1 asymptotic behavior and an updated small-parameter table.","lead":"This paper builds long cyclic sequences and two-dimensional arrays in which every short window is close to some codeword of a covering code, and it improves known upper bounds on the shortest such sequences for small parameters. Its constructions use Hamming codes, self-dual sequences, interleaving, folding, and primitive polynomials, with near-optimal radius-1 results asymptotically.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's asymptotic claim is only proved for radius 1; Sections III–VIII give constant-factor constructions only for (2^k−1,1)-CS and (2^k,1)-CS, so the unrestricted 'up to a constant factor' statement overreaches.","rationale":"The reader's strongest_claim correctly identifies the overbroad abstract, but their weakest_assumption is the unverified computer-search data. I think the decisive issue is the former: the advertised central result is a general constant-factor asymptotic theorem, and the body only proves radius-1 cases. If this concern lands, the abstract must be amended; the mathematical content of the radius-1 constructions is not affected. The computer-search concern is real but secondary: the appendices provide explicit codewords and overlap totals, so a determinable check exists and an error would only change individual table entries, not the asymptotic claims. I also note Theorem 24 has a parity typo (it states conditions on n instead of k), which is consistent with an under-polished manuscript but is not the load-bearing issue. My recommendation is unchanged conditional acceptance: the core constructions appear sound, but the paper needs an abstract/scope correction and a verification script for the appendix data.","tokens_in":26732,"tokens_out":12547,"duration_ms":132359,"concrete_test":"Perform a complete survey of every theorem/proposition in the manuscript that states an asymptotic upper bound for (n,R)-CS or C2DS and record the covering radius R it addresses. If the maximum R for which a constant-factor asymptotic bound is proved is 1, then the abstract's unrestricted claim is refuted; the paper should be revised to state the constant-factor result only for radius 1. A quick way to run this check: search for 'within factor' and 'factor' in Sections III–VIII and confirm each occurrence is attached to an explicit radius-1 covering sequence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim in the abstract is that asymptotically there are covering sequences attaining the sphere-covering bound up to a constant factor, with no restriction on R. The body does not prove this. Section III establishes a (2^k−1,1)-CS within a factor 2 of optimal from the Hamming code, and Section IV establishes a (2^k,1)-CS within a factor 1.25 from self-dual sequences; both are radius-1 results for special n. Section V interleaves sequences to obtain larger R, but the lengths are products (Construction 2) or quadratic (Construction 3) of the input lengths, so they do not yield a constant factor over the sphere-covering bound for fixed R≥2. Section VI gives only a single primitive-polynomial bound, and Section VII handles 2D arrays with an O(log mn) factor (Proposition 2). Thus the unrestricted asymptotic claim is unsupported. This matters because the known general upper bound for (n,R)-CS is O(q^n/V_q(n,R) log n) [54]; removing the log factor for all fixed R would be a substantial new theorem, not a corollary of the presented constructions. The abstract should be qualified to radius 1 (or to the specific n=2^k−1/2^k families), otherwise it overstates the paper's contribution.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies (n,R)-covering sequences, their multi-sequence generalization (n,m,R)-covering sequence codes, and a two-dimensional generalization (m×n,R)-covering 2D-sequences. It presents several construction methods: merging codewords of a cyclic covering code through shortest cyclic superstrings (Section III), a self-dual-sequence construction (Section IV), interleaving constructions (Section V), a primitive-polynomial construction (Section VI), and folding/shift constructions for 2D-sequences (Section VII). The paper reports improved upper bounds in Table I for 9≤n≤20 and 1≤R≤3, with explicit codeword lists and overlap computations in the appendices. The asymptotic statements in the body give a Hamming-code based (2^k−1,1)-CS within a factor 2 of the sphere-covering bound and a self-dual based (2^k,1)-CS within a factor 1.25, whereas the abstract claims a general constant-factor asymptotic result for covering sequences.","tokens_in":26995,"tokens_out":5905,"duration_ms":64008,"significance":"The deterministic Hamming-code and self-dual constructions are genuine strengths: for radius one they provide two infinite families whose lengths are within constant factors of the sphere-covering bound, improving on the general O(q^n/V(n,R) log n) upper bound for those parameters. The small-parameter upper bounds and the 2D generalizations are useful contributions, and the codeword lists in the appendices are checkable in principle. However, the main asymptotic claim as stated in the abstract is not supported by the body beyond radius one, and the computational upper bounds are not accompanied by a verifier or code, so the significance of the headline claims is lower than the abstract suggests.","major_comments":[{"comment":"The abstract states: 'We prove that asymptotically there are covering sequences that attain the sphere-covering bound up to a constant factor.' As written, this has no restriction on R. The body proves this only for R=1 and only for the families n=2^k−1 and n=2^k (Section III gives a factor-2 bound and Section IV a factor-1.25 bound for these two families). The interleaving constructions in Section V have lengths that are products or quadratic forms of the input lengths, the primitive-polynomial construction in Section VI gives an exponential ratio for fixed R≥2, and the 2D results in Section VII retain a logarithmic factor (Proposition 2). Thus the unrestricted asymptotic claim is unsupported. The abstract and the conclusion should be qualified to radius 1, or to the specific n families, and the general-R case should be stated as an open problem.","section":"Abstract and Sections III–VIII"},{"comment":"The improved upper bounds in Table I marked 'computer search' rely on the shortest-cyclic-superstring merging described in Section III and on the codeword lists and overlap totals asserted in Appendices A–D. No code, verifier script, or machine-readable certificate is provided, so a single erroneous overlap or non-covering codeword would change an upper bound. Given that these upper bounds are a central contribution, the authors should make the verification reproducible, for example by supplying the search code or a verifier that checks each listed sequence for the claimed covering property and each overlap sum.","section":"Section III and Appendices A–D"},{"comment":"Theorem 24 states the parity condition in terms of n ('If n is even... If n is odd...'), but Construction 5 and the proof of Theorem 24 both make the number of rows depend on k, the length of the input sequence, not on the window length n. As printed, the theorem statement is incorrect; the parity condition should refer to k. This is a local error, but it must be corrected because the theorem as stated would mislead a reader applying Construction 5.","section":"Section VII, Theorem 24"}],"minor_comments":[{"comment":"The proof of Lemma 13 is not written out convincingly: the sentence 'This follows from the fact that after n consecutive ones we should have a zero in such a sequence' is not an argument. The claim follows immediately from c(1) != 0 for a primitive polynomial, so the proof should be replaced by that short argument.","section":"Section VI, Lemma 13"},{"comment":"The construction in Theorem 17 is stated for 'n + 2R + 1' but the surrounding text sometimes refers to 'span n' and 'length 2^n−1' without consistently distinguishing the window length from the recurrence order. Please clarify notation in this section.","section":"Section VI, Theorem 17"},{"comment":"The example says a (10,1)-CS of length 177 yields a (20,2)-CS of length 178·178, but the preceding paragraph says Construction 3 gives k(k+1) or (k+1)^2 depending on parity; the example uses 178^2 for k=177? Please check the parity cases and make the formula and example agree.","section":"Section V, Example 12"},{"comment":"Several appendix entries have minor typographical issues, such as 'The following sequences is a ...' and inconsistent spacing in the codeword lists. These should be cleaned up in the final version.","section":"Appendices A-D"}],"recommendation":"major_revision","confidential_remarks":"The paper is within scope for a combinatorics journal. The main reason for major revision is the mismatch between the abstract's general asymptotic claim and the body's radius-1 results, together with the lack of machine-checkable verification for the computational upper bounds. Both issues are fixable without changing the core constructions. The overlap with the authors' earlier conference paper [9] and with [6] is disclosed in the text, and I do not see a circularity problem. If the authors qualify the asymptotic statement and supply a verifier or code, the paper would be acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"What you should know: the new constructions are real, the table of bounds is useful, and the central proofs mostly hold up. The main problem is the abstract, which claims a constant-factor asymptotic for all radii when the body only proves it for radius 1 at special lengths. That needs to be fixed before this goes out.\n\nWhat is genuinely new: the Hamming-code cyclic construction gives a (2^k-1,1)-CS within a factor of 2 of the sphere-covering bound; the self-dual construction gives a (2^k,1)-CS within a factor of about 1.25; the interleaving, folding, and shift-array methods produce new covering 2D-sequences; and the improved upper-bound table for n <= 20, 1 <= R <= 3 is a concrete contribution. The appendices are also a plus: they list actual codewords, sequences, and overlap totals, so a patient reader can brute-force check much of the table without trusting the authors.\n\nSoft spots, in proportion:\n- The abstract says \"asymptotically there are covering sequences that attain the sphere-covering bound up to a constant factor\" with no radius restriction. Sections III and IV only establish this for R=1, for n = 2^k-1 and n = 2^k. The interleaving constructions for larger R have lengths that are products or squares of the ingredient lengths, so they do not remove the log n factor in Vu's bound for fixed R >= 2. The claim should be qualified to radius 1 or to the specific families.\n- Theorem 24 states the array size based on whether n is even or odd, but the proof branches on k, the length of the input sequence. Example 26 contradicts the theorem as printed. This looks like a typo, but it is not harmless as written.\n- The table entries marked \"computer search\" and the overlap totals in Appendices B-D are asserted without a shipped verifier. One bad overlap total would change an upper bound. This is correctable by providing a checking script or clearly marking which entries are certified.\n- Minor: in Appendix B, the first (10,11,1)-CSC lists a duplicated codeword, even though the totals are consistent with 13 sequences. Another typo to clean up.\n\nThe self-dual construction relies on [6], which overlaps in authorship, but it is an external theorem with an independent statement. I do not see circularity. The proofs otherwise look sound, and I did not find a load-bearing gap beyond the abstract and the parity typo.\n\nThis paper is for people working on covering codes, de Bruijn-type sequences, and robust positioning patterns. It is not a breakthrough, but it advances the known bounds and methods. Send it to peer review. A referee should ask for the abstract fix, the Theorem 24 correction, and preferably a verification script for the table. With those changes, I would be pleased to see it published.","headline":"Worth publishing after fixing an overreaching abstract, a parity typo in Theorem 24, and providing verification data for the computer-assisted table entries.","tokens_in":27511,"tokens_out":5430,"would_cite":true,"duration_ms":53940,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B65","94B25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that covering sequences can be built within a constant factor of the sphere-covering bound, and it improves the known upper bounds for all short lengths up to 20.","keywords":["covering sequences","covering codes","sphere-covering bound","cyclic covering sequence codes","self-dual sequences","Hamming code","covering 2D-sequences","de Bruijn graph"],"falsifier":"Recompute the claimed (16,1)-covering sequence of length 4462: regenerate the 64 self-dual words of Appendix D from Construction 1, merge them with the stated overlap total of 594, and test every 16-bit word against the merged cycle to see whether any word lies at distance greater than 1 from all windows; the same test can be run on the 3516-bit (15,1)-covering sequence of Appendix C.","tokens_in":26552,"feed_emoji":"🔁","tokens_out":8872,"duration_ms":89876,"temperature":0.7,"pith_summary":"A covering sequence is a cyclic binary string whose consecutive length-n windows form a covering code of radius R: every n-bit word is within Hamming distance R of some window. The paper tries to show that such sequences can be nearly as short as the sphere-covering lower bound, and to improve the known shortest lengths for every n from 9 to 20 with radius 1, 2, or 3. Its main asymptotic result is that for radius 1, merging the codewords of the cyclic Hamming code gives a covering sequence within a factor of 2 of optimal, and a construction based on self-dual sequences brings the factor down to 1.25. The same tools are extended to covering sequence codes and to two-dimensional covering arrays whose m-by-n windows cover all matrices.","feed_headline":"Covering cycles reach within 1.25x of the theoretical minimum","feed_subtitle":"Hamming and self-dual constructions shrink upper bounds for lengths up to 20 and extend to 2D arrays.","key_machinery":"The load-bearing objects are cyclic covering sequence codes (CSCs): sets of cyclic words whose length-n windows jointly form an $(n,R)$-covering code. Given a CSC, the paper converts each cyclic codeword into an acyclic word by appending its first $n-1$ bits, then merges all words into one cycle by maximizing prefix-suffix overlaps, using a set-cover approximation for the shortest cyclic superstring problem. The asymptotic bounds come from two specific CSCs: the cyclic Hamming code for $n=2^k-1$, and a recursively defined family of self-dual sequences of the form $[X\\bar{X}]$ for $n=2^k$, whose covering property is delegated to the companion theory of nearly-perfect covering codes. For 2D arrays, the machinery is folding a one-dimensional covering sequence into rows and arranging many cyclic shifts of a covering sequence, guided by de Bruijn sequences of shift indices.","core_discovery":"In the authors' terms, the paper's central claim is that covering sequences can be constructed whose length is only a constant factor above the sphere-covering bound, and that several previously known upper bounds for small parameters can be improved by explicit constructions. For radius 1, Section III reduces the binary Hamming code of length $2^k-1$ to its distinct cyclic shifts and merges them by maximizing overlaps, producing a $(2^k-1,1)$-covering sequence shorter than $2^{2^k-k}$, within a factor of at most 2 of the sphere-covering bound. Section IV uses self-dual sequences of the form $[X\\bar{X}]$ to build a $(2^k,1)$-covering sequence code whose total length equals the size of an optimal $(2^k,1)$-covering code, and then merges its codewords to obtain a $(2^k,1)$-CS of length less than $1.25K$, where $K=2^{2^k-k}$. The paper also generalizes covering sequences to $(n,m,R)$-covering sequence codes and to $(m\\times n,R)$-covering 2D-sequences, giving both a folding construction and a shift-based construction for the latter, and it tabulates improved upper bounds on $L(n,R)$ for $9\\le n\\le 20$ and $1\\le R\\le 3$.","pith_inferences":["If the delegated self-dual proof in reference [6] holds, the same recursive construction may be adaptable to radii 2 and 3 using nearly-perfect or Preparata-type codes, a direction the authors list as future work.","The shortest-cyclic-superstring merge step is heuristic; replacing the set-cover approximation with an exact solver or a tighter bound on overlaps could lower several table entries without changing the underlying covering codes.","The observation that shift-arranged 2D arrays can be smaller in area than the best known one-dimensional covering sequence suggests that 2D covering arrays deserve their own lower bounds rather than being compared only through folding.","For the self-dual construction, the factor 1.25 is obtained by concatenating without computing overlaps; actually computing overlaps—as is done for the small cases in the appendices—would likely reduce the constant further."],"forward_implications":["For binary length $n=2^k-1$, covering sequences exist with length below $2^{2^k-k}$, so the gap to the sphere-covering bound is at most a factor of 2.","For $n=2^k$, covering sequences exist within a factor of 1.25 of the optimal covering-code size, giving the closest known asymptotic match for radius 1.","The table of bounds for $9\\le n\\le 20$ and $1\\le R\\le 3$ improves several upper bounds on the shortest covering sequence length, with entries coming from interleaving, self-dual merges, and primitive-polynomial constructions.","Folding a good one-dimensional covering sequence yields $m\\times n$ covering arrays of area roughly twice the sequence length, while arranging shifts of a covering sequence can produce arrays whose area is smaller than the corresponding one-dimensional covering sequence.","The interleaving construction composes an $(n_1,R_1)$-covering sequence and an $(n_2,R_2)$-covering sequence into an $(n_1+n_2,R_1+R_2)$-covering sequence of length $2k_1k_2$, which is what produces most of the larger-radius entries in the table."],"supporting_citations":[{"why":"Introduces covering sequences (de Bruijn covering codes) and supplies the sphere-covering bound together with several small-case upper bounds used as baselines in Table I.","marker":"[10]"},{"why":"Proves the covering property of the self-dual sequence family that underlies the factor-1.25 asymptotic construction in Section IV.","marker":"[6]"},{"why":"Provides the set-cover approximation algorithm used to merge the codewords of a cyclic covering sequence code into a short cyclic superstring, on which the table's improved upper bounds depend.","marker":"[53]"},{"why":"Establishes the existence of short covering sequences over arbitrary alphabets, which combined with the folding technique yields the asymptotic 2D bound cited in Section VII.","marker":"[54]"},{"why":"Supplies the count of cyclic words with fewer than n distinct shifts, needed to bound the number of codewords in the Hamming-code cyclic covering sequence code.","marker":"[19]"},{"why":"The conference version of this work that first introduced the self-dual construction and proved the 2D existence bound (Proposition 2).","marker":"[9]"}],"fun_headline_variants":["Covering sequences reach constant-factor sphere bound","Tighter covering bounds for n≤20 and 2D arrays","New constructions improve covering sequence upper bounds","Covering cycles and arrays get closer to optimal","Constant-factor gap for covering sequences proven"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The improved small-case upper bounds rest on computer-generated codeword lists and overlap counts printed in the appendices, with no verifier shipped, so a single wrong overlap or non-covering codeword would change a bound; the factor-1.25 asymptotic result likewise depends on the self-dual covering-code family whose proof is delegated to reference [6].","fun_headline_variants_meta":{"raw":{"variants":["Covering sequences reach constant-factor sphere bound","Tighter covering bounds for n≤20 and 2D arrays","New constructions improve covering sequence upper bounds","Covering cycles and arrays get closer to optimal","Constant-factor gap for covering sequences proven"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000364,"raw_usage":{"total_tokens":1975,"prompt_tokens":971,"completion_tokens":1004,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":587,"completion_tokens_details":{"reasoning_tokens":934}},"tokens_in":587,"tokens_out":1004,"duration_ms":10616,"temperature":1.0,"reasoning_tokens":934,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T05:08:50.571895+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Recompute the claimed (16,1)-covering sequence of length 4462: regenerate the 64 self-dual words of Appendix D from Construction 1, merge them with the stated overlap total of 594, and test every 16-bit word against the merged cycle to see whether any word lies at distance greater than 1 from all windows; the same test can be run on the 3516-bit (15,1)-covering sequence of Appendix C.","supporting_citations":[{"cited_title":"C HUNG AND J","cited_arxiv_id":null,"evidence_quote":"Introduces covering sequences (de Bruijn covering codes) and supplies the sphere-covering bound together with several small-case upper bounds used as baselines in Table I."},{"cited_title":"B ORUCHOVSKY , T","cited_arxiv_id":null,"evidence_quote":"Proves the covering property of the self-dual sequence family that underlies the factor-1.25 asymptotic construction in Section IV."},{"cited_title":"V AZIRANI , Approximation algorithms","cited_arxiv_id":null,"evidence_quote":"Provides the set-cover approximation algorithm used to merge the codewords of a cyclic covering sequence code into a short cyclic superstring, on which the table's improved upper bounds depend."},{"cited_title":"V U, De bruijn covering codes with arbitrary alphabets, Advances in Applied Mathematics, 34 (2005) 65–70","cited_arxiv_id":null,"evidence_quote":"Establishes the existence of short covering sequences over arbitrary alphabets, which combined with the folding technique yields the asymptotic 2D bound cited in Section VII."},{"cited_title":"E TZION , Sequences and the de Bruijn Graph: Properties, Constructions, and Applications, London, UK; San Diego, US, Cambridge, US: Elsevier, 2024","cited_arxiv_id":null,"evidence_quote":"Supplies the count of cyclic words with fewer than n distinct shifts, needed to bound the number of codewords in the Hamming-code cyclic covering sequence code."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The conference version of this work that first introduced the self-dual construction and proved the 2D existence bound (Proposition 2)."}],"review_version":1}