{"id":"1b6b9851-b103-4b21-9de3-ca5da532ee02","arxiv_id":"2411.16744","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper's headline multi-subword counting formula is invalid; a length-3 binary example returns 18 instead of 0.","lead":"A preprint claims new closed-form formulas for counting strings that contain specified subwords a fixed number of times. The single-subword formula is a known inclusion-exclusion identity, and the proposed multiple-subword formula gives wrong numbers on a basic example.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 8's multi-subword formula fails when occurrences of distinct subwords overlap: the proof's independence step is invalid, and a small binary case gives -2 instead of 6.","rationale":"The paper's central promise is a polynomial-time closed-form count for words containing prescribed subwords with prescribed multiplicities. The multi-subword formula, Theorem 8, fails exactly where the proof asserts independence: occurrences of different subwords can share positions in the word, so their placements are not independent. The counterexample uses non-self-intersecting subwords of length 2 over a binary alphabet, a setting within the theorem's stated scope. The formula returns a negative number, impossible for a count, at the only admissible index pair, while brute force gives 6. I also checked the single-subword formula for A=\"01\", t=4, x=1 and found it gives the correct count 10, so the defect is specifically in the multi-subword extension, which is the claimed new advance. The reader's weakest-assumption analysis identifies the same independence issue, and the rejection verdict is justified. No change to the reader's verdict is needed.","tokens_in":7923,"tokens_out":7310,"duration_ms":60538,"concrete_test":"Evaluate Eqs. (23)-(24) for q=2, t=4, D={(\"01\",1),(\"10\",1)} and compare the result with exhaustive enumeration of all 2^4 binary strings. The formula yields -2 (only i1=i2=1 is admissible), while brute force counts 6 strings. Run the same comparison for t=5, and also try the authors' software tool from Section 5.2.3 if available; if the formula output differs from brute force, Theorem 8 is refuted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on Theorem 8, specifically Eqs. (23)-(24). The proof after Eq. (26) asserts that the across-sums for different subwords are independent because they do not share an index, so the counts can be multiplied and then combined by a multinomial factor. This confuses independence of summation indices with independence of placements in the word. Occurrences of distinct subwords can overlap or interleave in the string, and the formula has no hypothesis excluding this. A minimal counterexample uses q=2, t=4, A1=\"01\", A2=\"10\", x1=x2=1. Both subwords are non-self-intersecting, so the stated assumptions are satisfied. Exhaustive enumeration of the 16 binary strings of length 4 gives 6 words containing exactly one occurrence of each subword: 0010, 0100, 0110, 1001, 1011, and 1101. Evaluating Eq. (24) gives only the index pair (i1,i2)=(1,1), whose term is -2. A closed-form count cannot be negative, and the discrepancy is not a boundary case: it is the only admissible term. The limitation note in Section 5.3 acknowledges overlapping subwords as future work, but Theorem 8 as stated does not exclude them, so the acknowledgement does not rescue the theorem. Since the claimed polynomial-time multi-subword counting is the paper's main contribution, this failure is load-bearing.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to derive closed-form formulas for counting words of length t over a q-letter alphabet that contain a given subword A exactly x times (Theorem 5), and then extends this to a list of subwords with prescribed multiplicities (Theorem 8). It further claims that these formulas reduce counting complexity from exponential to polynomial in t, with a polynomial but d-dependent cost for multiple subwords, and it sketches applications to DNA motif counting and password-policy counting. The multi-subword formula is the advertised main contribution.","tokens_in":8213,"tokens_out":9882,"duration_ms":89505,"significance":"If the formulas were correct, the paper would provide a useful polynomial-time counting tool and would extend the single-pattern case to several patterns. The paper contains no fitted parameters and presents explicit, testable closed-form expressions, which is a strength. However, the central multi-subword formula is invalid, so the claimed advance is not established; the polynomial-time multi-pattern counting result is unsupported.","major_comments":[{"comment":"Theorem 8 is false as stated. The proof after Eq. (26) claims that the sums for different subwords are independent because they do not share an index, so the counts can be multiplied and then combined by a multinomial factor. This confuses independence of summation indices with independence of placements in an actual word: occurrences of distinct subwords can overlap or constrain one another. A counterexample satisfying all stated hypotheses is q=2, t=4, A1=\"01\", A2=\"10\", x1=x2=1; both subwords are non-self-intersecting. Exhaustive enumeration of the 16 binary strings of length 4 gives exactly 6 words containing each subword exactly once: 0010, 0100, 0110, 1001, 1011, and 1101. In Eq. (24) the only admissible index pair is (i1,i2)=(1,1), and the term equals (-1)^3 * 2^0 * ((3 choose 0)) * ((1 choose 0))^2 * (2!/(1!1!)) = -2. A count cannot be negative. The limitation note in Section 5.3 says that overlapping subwords are left to future work, but Theorem 8 does not exclude overlaps, so this is not a boundary case but a failure of the theorem's central step.","section":"Section 3.2, Eqs. (23)-(24)"},{"comment":"The proof of Theorem 5 is too sketchy to meet journal standards. Lemma 6 is justified only through informal statements about 'slight rearrangements' and 'simplified in relation to its neighbors,' and the derivation of the final alternating sum from an across-sum is asserted rather than proved. Since Theorem 5 is the foundation for Theorem 8, a complete inclusion-exclusion proof is required. My own spot checks did not contradict Theorem 5, but the current presentation does not provide a rigorous basis for the claimed single-subword result.","section":"Section 3.1, Theorem 5"},{"comment":"The paper gives no numerical verification against brute-force enumeration for any small case. The applications in Sections 5.1 and 5.2 merely display formulas and do not report computed values or compare them with exhaustive counts. A simple brute-force check for the multi-subword example would have exposed the failure of Eq. (24). Any revision must include such machine-checked tables for small t, q, and d.","section":"Section 5, Applications"}],"minor_comments":[{"comment":"The double-parentheses notation for multiset binomial coefficients is never defined; the reader must infer it from context.","section":"Section 3.1, Eq. (5)"},{"comment":"The notation '1∑ p=d' is nonstandard and should be written as a conventional summation, for example ∑_{p=1}^{d}.","section":"Section 3.2, Eqs. (23)-(25)"},{"comment":"The notions of 'unoccupied position' and 'relative position' are informal; the proof assumes an ordering of copies of A that is never defined formally.","section":"Section 3.1, Definitions 1-3"},{"comment":"The set S is defined as a set of multisets of contiguous subwords, but |Y| is used as the number of words; this conflates words with their subword multisets and should be clarified.","section":"Section 3.1, Definition of Y"},{"comment":"The traditional multi-subword complexity is written as O(q^t · t^d), but q^t already dominates all polynomial factors in t, so the t^d factor is misleading.","section":"Section 4.3, Table 1"}],"recommendation":"reject","confidential_remarks":"The counterexample in Section 3.2 is decisive and independent of interpretation. The multi-subword formula is the paper's main advertised contribution, and it returns a negative number for a valid case, so the central claim cannot be repaired by a local correction. A rewrite that restricts to genuinely non-overlapping subwords with a rigorous proof and numerical verification could be considered as a new submission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the single-subword result is a known inclusion-exclusion identity dressed up as new, and the headline multi-subword formula is simply false. I checked the math, and the paper does not survive contact with a small example.\n\nWhat's genuinely useful: the authors correctly identify that counting words by subword multiplicity can be done in polynomial time for fixed subword lengths, and Theorem 5, once you fix the sign convention, matches the standard count for non-self-overlapping patterns. That part is not new—see the classical formula sum_j (-1)^{j-x} C(j,x) q^{t-aj} C(t-(a-1)j, j)—but they do derive it in their own notation.\n\nThe soft spot is load-bearing. Theorem 8 asserts that placements of distinct subwords are independent beyond occupying different positions, so you can multiply counts and correct with a multinomial factor. That is not true: occurrences of different subwords can interleave or overlap. The proof after Eq. (26) claims independence because the sums use different indices, but index independence in a product of sums has nothing to do with equality constraints between subword occurrences in the word.\n\nA minimal counterexample: q=2, t=4, A1='01', A2='10', x1=x2=1. Both subwords are non-self-intersecting, so the theorem's hypotheses are satisfied. Brute force gives 6 strings (0010, 0100, 0110, 1001, 1011, 1101). Eq. (24) gives only the (1,1) term, equal to -2. A count cannot be negative. The limitation note in Section 5.3 says overlapping subwords are future work, but the theorem does not exclude them, and the counterexample isn't a boundary case—it's the only admissible term.\n\nThere are other issues: no brute-force validation anywhere, the abstract claims linear time while Section 4.2.1 says O(t^2), and the proof of Lemma 6 is too sketchy to follow. The single-subword sign handling is ad hoc and not part of the theorem statement as written.\n\nBottom line: the only new contribution is false, and the rest is a known identity presented without attribution. This paper is not ready for review. Send it back without referees.","headline":"The single-subword count is standard; the multi-subword theorem fails a 16-case brute-force check, so the paper's only new claim collapses.","tokens_in":11,"tokens_out":5420,"would_cite":false,"duration_ms":104412,"reading_group":"no","serious_thinker":"no","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A15","05A05","05A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper derives closed-form, polynomial-time formulas for counting words that contain specified subwords exactly a prescribed number of times, replacing exponential brute-force enumeration.","keywords":["permutation with replacement","subword occurrences","closed-form counting","relative positions","binomial coefficient sums","DNA motif counting","password pattern analysis","polynomial-time enumeration"],"falsifier":"Take $t=3$, alphabet $\\{0,1\\}$, and require subword 01 exactly once and subword 10 exactly once; exhaustive listing gives exactly the two words 010 and 101, while the nested sum in Theorem 8 returns zero because it treats the two required copies as occupying four distinct positions. This one computation decides whether the multi-subword formula counts all words or only non-overlapping arrangements.","tokens_in":7761,"feed_emoji":"🧬","tokens_out":11952,"duration_ms":97682,"temperature":0.7,"pith_summary":"This paper claims a closed-form way to count words of length $t$ over a $q$-letter alphabet that contain specified subwords exactly a prescribed number of times. It first gives a single-subword formula as a finite alternating sum, then extends it to multiple subwords with nested sums. If the formulas are right, motif counting in DNA sequences and pattern counting in password policies can be done in polynomial time in $t$ for a fixed number of subwords, instead of checking all $q^t$ sequences. The central idea is to place copies of each subword and distribute the remaining letters among the gaps they create.","feed_headline":"Permutation counting with subword constraints drops to polynomial time","feed_subtitle":"Closed-form sums count words with each subword appearing a prescribed number of times, no brute-force search.","key_machinery":"The load-bearing object is the relative position of an unoccupied letter: after laying down copies of a subword, every remaining position sits in one of the gaps before, between, or after the copies. The multiset coefficient counts how many ways the free letters can be assigned to those gaps, the alternating sum removes overcounts from choosing which copies are counted, and the multinomial factor in the multi-subword case treats copies of different subwords as distinct objects to be ordered. Lemmas 4 and 6 provide the binomial-sum identities that turn these placement counts into the closed forms.","core_discovery":"On its own terms, the paper establishes Theorem 5 for one non-self-intersecting subword: the number of words of length $t$ containing subword $A$ exactly $x$ times is a finite alternating sum over the possible number of copies $i$, with terms $(-1)^{i+1} q^{t-ai}$ times a multiset coefficient distributing the $t-ai$ unoccupied positions among the $i+1$ relative positions around the copies, times $\\binom{i}{i-x}$. Theorem 8 extends this to $d$ subwords by nested sums whose terms multiply the per-subword binomial factors by a multinomial factor $i_t! / \\prod_p i_p!$ that reorders the distinct subword copies. The claimed complexity is $O(t^2)$ for one subword and $O((t/a_{\\min})^d\\,t)$ for $d$ fixed subwords, against $O(q^t)$ for brute-force enumeration.","pith_inferences":["The authors do not pursue counting overlapping copies of different subwords, but that case would require inclusion-exclusion over shared positions; the $t=3$ binary example with subwords 01 and 10 marks the boundary of the current formula.","I infer the practical win is for small fixed $d$: the $(t/a_{\\min})^d$ factor is polynomial in $t$ but exponential in $d$, so the method is not meant for a growing list of motifs.","The same relative-position idea could be adapted to self-intersecting subwords by handling border overlaps directly, a direction the conclusion names as future work."],"forward_implications":["For one non-self-intersecting subword of fixed length, the count is evaluable in $O(t^2)$ time rather than $O(q^t)$.","For a fixed number $d$ of subwords, the nested-sum formula is polynomial in $t$, with the exponential cost confined to $d$.","The same formulas apply directly to counting DNA sequences with prescribed motif multiplicities and passwords meeting multiple pattern constraints.","The results are exact integer counts, so they can serve as standalone checks for randomized or approximate sequence generators."],"supporting_citations":[{"why":"Supplies the alternating row-sum identity used to shorten the binomial sums in Lemma 4.","marker":"[2]"},{"why":"Provides Pascal's identity, which Lemma 6 applies recursively to combine across-sums and diagonals.","marker":"[3]"},{"why":"Gives the permutation-with-repetition count used as the final multinomial factor in Theorem 8.","marker":"[4]"},{"why":"A second source for the multinomial counting formula behind the ordering factor.","marker":"[5]"},{"why":"Defines the subword-occurrence counting problem that serves as the traditional exponential-time baseline.","marker":"[6]"},{"why":"Supplies the further baseline for subword counting that the paper compares against in complexity.","marker":"[7]"}],"fun_headline_variants":["Subword counting jumps from exponential to polynomial","Polynomial time for subword-constrained permutation counting","New closed-form formulas speed up subword permutation counting","From brute force to formulas: subword counting made efficient","Counting subword patterns without exponential blowup"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes copies of different subwords occupy disjoint positions, so the total occupied length is simply the sum of each subword's length times its required count; overlapping placements, such as the word 010 containing both 01 and 10, are outside what the formula counts.","fun_headline_variants_meta":{"raw":{"variants":["Subword counting jumps from exponential to polynomial","Polynomial time for subword-constrained permutation counting","New closed-form formulas speed up subword permutation counting","From brute force to formulas: subword counting made efficient","Counting subword patterns without exponential blowup"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001041,"raw_usage":{"total_tokens":4356,"prompt_tokens":897,"completion_tokens":3459,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":3386}},"tokens_in":513,"tokens_out":3459,"duration_ms":22959,"temperature":1.0,"reasoning_tokens":3386,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:04:15.950925+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $t=3$, alphabet $\\{0,1\\}$, and require subword 01 exactly once and subword 10 exactly once; exhaustive listing gives exactly the two words 010 and 101, while the nested sum in Theorem 8 returns zero because it treats the two required copies as occupying four distinct positions. This one computation decides whether the multi-subword formula counts all words or only non-overlapping arrangements.","supporting_citations":[{"cited_title":"Proof without words: Alternating row sums in pascal’s t riangle","cited_arxiv_id":null,"evidence_quote":"Supplies the alternating row-sum identity used to shorten the binomial sums in Lemma 4."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Pascal's identity, which Lemma 6 applies recursively to combine across-sums and diagonals."},{"cited_title":"Grimaldi","cited_arxiv_id":null,"evidence_quote":"Gives the permutation-with-repetition count used as the final multinomial factor in Theorem 8."},{"cited_title":"An Invitation to Combinatorics","cited_arxiv_id":null,"evidence_quote":"A second source for the multinomial counting formula behind the ordering factor."},{"cited_title":"Counting occurrences of some subword patterns","cited_arxiv_id":"math/0204320","evidence_quote":"Defines the subword-occurrence counting problem that serves as the traditional exponential-time baseline."},{"cited_title":"Counting s ubwords in a partition of a set","cited_arxiv_id":null,"evidence_quote":"Supplies the further baseline for subword counting that the paper compares against in complexity."}],"review_version":1}