{"id":"e70e9704-36e8-4ba2-9d42-c3a728650c3e","arxiv_id":"1908.03890","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Poly-rational sequences are exactly the sequences of polynomially ambiguous weighted automata, of copyless cost-register automata, and of linear recurrences whose eigenvalues are roots of rational numbers.","lead":"This paper defines poly-rational sequences, a subclass of linear recurrence sequences built from arithmetic and geometric sequences, and proves they coincide with five existing classes: polynomially ambiguous weighted automata, copyless cost-register automata, and rational formal series with poles at roots of rationals.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 9's proof asserts a false polynomial factorization; the decomposition on which Theorem 15 rests is not established as written.","rationale":"The reader's weakest assumption is the reliance on [14, Proposition 1] for CCRA normal form. That is a reasonable concern, but it is less load-bearing: it affects only one of the five equivalences and rests on a published result. The false assertion in Lemma 9 affects both directions of Theorem 15 and the inclusion PolyWA⊆PolyRat, and it is a direct mathematical error in the text rather than an external dependency. The proposed concrete test settles whether the error is repairable: if every irreducible factor of Q divides some 1−λx^m, the conclusion of Lemma 9 follows by partial fractions, so the theorem remains true after a proof revision. Since the paper as written contains a false step in a central lemma, the conditional verdict is appropriate; no change in verdict is needed, but the concern is more fundamental than the one flagged by the reader.","tokens_in":13152,"tokens_out":25411,"duration_ms":262138,"concrete_test":"Take Q(x)=1+2x^2+4x^4. First, replace the erroneous factorization claim by the divisibility argument: since every root α of Q satisfies α^6=1/8, Q divides 1−8x^6, so 1/Q=(1−2x^2)/(1−8x^6), which is already a summand R/(1−λx^ℓ). Then attempt to find the claimed polynomial product representation of Q using undetermined coefficients; show no finite product ∏(1−λ_i x^{ℓ_i})^{k_i} over Q equals Q. If the divisibility argument succeeds, Lemma 9's conclusion holds and Theorem 15 is salvageable; if it fails for some other irreducible factor, the theorem needs re-examination.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Lemma 9 contains the claim that 'any polynomial whose roots are roots of rational numbers can be written as a product of mutually prime polynomials of the form (1−λx^ℓ)^k.' This is false. Q(x)=1+2x^2+4x^4 is irreducible over Q, its roots α satisfy α^6=1/8, yet Q cannot be factored into such polynomials over Q: a coefficient comparison excludes (1−λx^2)^2 and (1−λ1x^2)(1−λ2x^2), and any factor with ℓ≠2 introduces unwanted degree terms. Lemma 9 is used in both directions of Theorem 15 and in PolyWA⊆PolyRat; if the decomposition into sums R/(1−λx^ℓ)^k fails, the central equivalence LRS(eigenvalues roots of rationals)=PolyRat collapses. The conclusion of Lemma 9 is nevertheless plausibly true: each irreducible factor q of Q divides some 1−λx^m (indeed Q divides 1−8x^6), so after multiplying numerator and denominator the series can be put in the required sum form. But the proof as written has a false step, not a mere typo, and the theorem's proof is incomplete without a corrected argument.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces poly-rational sequences (PolyRat), defined as the smallest class containing arithmetic and geometric sequences and closed under sum, Hadamard product, shift, and shuffle. The central claim is that PolyRat is robust: it coincides with the classes of sequences recognised by polynomially ambiguous weighted automata (PolyWA), copyless cost-register automata (CCRA), rational formal series P/Q with Q having only roots that are roots of rational numbers, and linear recurrence sequences whose eigenvalues are roots of rational numbers. The authors also use this equivalence to show that the Fibonacci sequence is not in PolyRat and to place the Skolem problem for the class in NP-hard and decidable.","tokens_in":13400,"tokens_out":12208,"duration_ms":140903,"significance":"If the main theorem holds, this is a clean and useful robustness result: it connects four independently motivated notions—expression classes, ambiguity-bounded automata, register automata with a copyless restriction, and an algebraic condition on eigenvalues. The paper gives constructive, elementary translations between the characterisations and derives a concrete separation (Fibonacci is excluded), which strengthens the known separation of CCRA from LCRA. The paper's strengths are the breadth and simplicity of the proposed characterisations, and the fact that several equivalences are proved by explicit constructions rather than by invoking heavy machinery. However, the current proof contains a false step in a key lemma, and another lemma relies on an unstated linearity assumption; these must be repaired before the main theorem can be considered established.","major_comments":[{"comment":"The proof of Lemma 9 contains a false assertion: it claims that any polynomial whose roots are roots of rational numbers can be written over Q as a product of mutually prime polynomials of the form (1 - lambda x^ell)^k. This is not true. The polynomial Q(x) = 1 + 2x^2 + 4x^4 is irreducible over Q, its roots alpha satisfy alpha^6 = 1/8, yet Q cannot be proportional to any (1 - lambda x^ell)^k: a binomial factor has at most two nonzero terms, and direct comparison for ell = 2, k = 1, 2 and ell = 4 fails. Since Lemma 9 is used in both directions of Theorem 15 and in the proof of PolyWA subset PolyRat in Section 3, the central equivalence is not proved as written. The statement of Lemma 9 may be salvageable by a different argument, namely that every irreducible factor q of Q divides some x^m - c with c in Q, so that P/Q can be put in the required partial-fraction form; but the proof in the manuscript must be replaced by a correct argument.","section":"Section 5, Lemma 9"},{"comment":"Lemma 14 is stated for every copyless substitution in normal form, but its proof assumes that sigma(x) is a linear expression, writing sigma(x) as sum_i a_i x_i. The definition of CCRA given in Section 4 allows products of registers in substitutions. The paper cites [12] for the fact that CCRA is a subclass of linear CRA, but it does not show that the linearisation preserves copylessness and normal form, which are essential hypotheses of Lemma 14. Without such a preservation result, the proof of CCRA subset PolyRat only covers linear copyless substitutions, and Theorem 13 is not fully supported. Please either prove the needed reduction to linear copyless normal form, or extend the argument of Lemma 14 to polynomial copyless substitutions.","section":"Section 4, proof of Lemma 14"},{"comment":"The decomposition of polynomially ambiguous automata into a union of chained loops is load-bearing for Theorem 6 and for the formal-series characterisation, but the proof is only sketched. In particular, the claim that a state contained in two loops induces exponential ambiguity is stated without proof, and the asserted bijection between runs of A and runs of the union of all induced chained loops is not demonstrated. Please give a formal graph-theoretic proof, making explicit how runs are decomposed into a simple path with repetitions of unique simple loops, and how the weights of the original run match the value in the union of chained loops.","section":"Section 3, Lemma 7"}],"minor_comments":[{"comment":"The displayed expansion in the proof of Lemma 10 uses the binomial coefficient binom(n+k-1, k), but the coefficient of x^n in (1-x)^{-k} is binom(n+k-1, k-1). The subsequent argument only needs that the coefficient sequence is polynomial in n, so the error is not fatal, but the formula should be corrected.","section":"Section 3, Lemma 10"},{"comment":"The paper imports [14, Proposition 1] (existence of an equivalent CCRA in normal form) as a black box. Since this result is central to the CCRA subset PolyRat direction and comes from the authors' own prior work, please state the theorem precisely and, ideally, include a proof or a detailed reference statement in an appendix.","section":"Section 4, paragraph on normal form"},{"comment":"The proofs of the first three items of Lemma 12 are omitted. These items establish the strict inclusions in the ambiguity hierarchy, which is a stated application of the paper; please include at least sketches of these proofs.","section":"Section 3, Lemma 12"},{"comment":"In the shift construction for a = 0, the text should state explicitly that the new initial state q0 is not final and that the original initial weights are moved to the new outgoing transitions; as written, the value of the length-zero run is left implicit.","section":"Section 3, proof of Theorem 6, shift construction"},{"comment":"The phrase 'effectively equivalent' is used without a precise definition. Please clarify that the reductions are computable, and state whether any complexity bound is intended.","section":"Theorem 2"}],"recommendation":"major_revision","confidential_remarks":"The central theorem is plausible and the paper is well suited to the journal, but the false factorization in Lemma 9 is a genuine gap in the proof of the main equivalence, and the linearity assumption in Lemma 14 needs clarification. Both seem repairable without changing the claimed results, so I recommend major revision rather than rejection. The reliance on [12] and [14] should also be checked carefully for self-citation policy."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know about arXiv:1908.03890. The paper defines poly-rational sequences and proves a five-way equivalence: the same class is captured by polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series whose denominator roots are roots of rational numbers, and LRS whose eigenvalues are roots of rational numbers. The genuinely new piece is the equality CCRA = PolyWA; prior work only had CCRA strictly inside all weighted automata.\n\nWhat's good: the class is natural and the four characterizations are proved by elementary constructions. The paper is clearly written and the definitions are memorable. Lemma 14's induction for copyless substitutions is the nicest part of the paper. If the main theorem is correct, it gives a useful algorithmic fragment: the Skolem problem is decidable for the class, with known NP-hardness.\n\nThe soft spots are in the proofs, not the statements. Lemma 9's proof asserts that any polynomial whose roots are roots of rational numbers is a product of mutually prime polynomials (1−λx^ℓ)^k. That's false. Take Q(x)=1+2x^2+4x^4: it's irreducible, every root α satisfies α^6=1/8, but Q cannot be factored into such polynomials over Q. The lemma's conclusion is still true—each irreducible factor of Q divides some 1−λx^m, so partial fractions give the desired sum—but the proof needs a different argument. Since Lemma 9 is used in both directions of Theorem 15 and in PolyWA⊆PolyRat, the authors must fix this.\n\nSmaller issues: Lemma 10's displayed expansion has the wrong binomial coefficient (C(n+k−1,k) should be C(n+k−1,k−1)); Lemma 7's chained-loop decomposition is sketched, and the claim that a state is in at most one loop needs a fuller argument; Lemma 12's strictness examples are explicitly omitted. The normal form for CCRA is imported from the authors' own JCSS paper; that's legitimate, but the current paper depends on it.\n\nMy read: the central claim is almost certainly correct and repairable. The paper deserves a serious refereeing cycle, not a desk reject. I'd want the Lemma 9 proof rewritten and the smaller gaps patched before publication, but this is a real contribution to the automata/LRS literature.","headline":"A genuinely new five-way equivalence for poly-rational sequences, but the proof of Lemma 9 contains a false factorization claim; the gap is repairable and the paper deserves a serious referee.","tokens_in":13924,"tokens_out":7893,"would_cite":true,"duration_ms":68338,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11B37","68Q45"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper introduces poly-rational sequences and proves they coincide with polynomially ambiguous weighted automata, copyless cost-register automata, and linear recurrence sequences whose eigenvalues are roots of rational numbers.","keywords":["poly-rational sequences","linear recurrence sequences","weighted automata","cost-register automata","formal series","polynomial ambiguity","copyless substitutions","eigenvalues"],"falsifier":"Factor the reduced formal series of any polynomially ambiguous weighted automaton: the paper predicts every irreducible factor of the denominator has the form $1-\\lambda x^\\ell$. One automaton whose denominator contains an irreducible factor such as $x^2-x-1$—the Fibonacci characteristic polynomial—would refute Theorem 15; the mirror test is a copyless cost-register automaton whose eigenvalues include a number like $(1+\\sqrt{5})/2$.","tokens_in":12978,"feed_emoji":"🔢","tokens_out":11564,"duration_ms":102276,"temperature":0.7,"pith_summary":"This paper carves out a tractable subclass of linear recurrence sequences and shows that the same subclass emerges from four very different definitions. The class, called poly-rational sequences, is the smallest family containing arithmetic and geometric sequences and closed under sum, componentwise product, shift, and shuffle. The authors prove it equals the sequences recognised by polynomially ambiguous weighted automata, by copyless cost-register automata, and by linear recurrences whose eigenvalues are roots of rational numbers—equivalently, formal series $P/Q$ whose denominator roots are roots of rationals. If the paper is right, this gives a clean boundary inside linear recurrences: the Fibonacci sequence, whose eigenvalues involve $\\sqrt{5}$, falls outside, and decidability and hardness results for one presentation transfer to all the others.","feed_headline":"Poly-rational sequences equal four known classes","feed_subtitle":"The equivalence unifies weighted automata, cost registers, formal series, and eigenvalue-restricted recurrences.","key_machinery":"The central object is the class $\\mathrm{PolyRat} = \\mathrm{Rat}[\\mathrm{Arith}\\cup\\mathrm{Geo}, +, \\times, \\mathrm{shift}, \\mathrm{shuffle}]$, the smallest family containing arithmetic and geometric sequences and closed under sum, Hadamard product, shift, and shuffle. The argument is carried by two decompositions: Lemma 7 splits any polynomially ambiguous weighted automaton into a union of chained loops—paths whose states each belong to at most one loop—and Lemma 8 computes the formal series of a chained loop as sums and Cauchy products of $\\alpha/(1-\\lambda x^\\ell)$. For copyless cost-register automata, the load-bearing mechanism is a normal-form theorem for copyless substitutions, which turns every register update into either a stabilising constant or a one-dimensional affine recurrence $u(n+1)=a\\,u(n)+b$, and both forms are poly-rational. These mechanisms convert each machine model into an explicit rational formal series, and back again.","core_discovery":"The paper's central claim is Theorem 15: poly-rational sequences are exactly the linear recurrence sequences whose eigenvalues are roots of rational numbers, equivalently those whose formal series are $P/Q$ with $P,Q$ rational polynomials and all roots of $Q$ roots of rational numbers. Together with Theorems 6 and 13 this yields a five-way effective equivalence among poly-rational expressions, polynomially ambiguous weighted automata, copyless cost-register automata, rational formal series of that restricted kind, and eigenvalue-restricted linear recurrences. The proof route is explicit: a polynomially ambiguous weighted automaton decomposes into chained loops, each contributing a series of the form $\\alpha/(1-\\lambda x^\\ell)$, and sums and Cauchy products of these are precisely the rational series whose denominator roots are roots of rational numbers; conversely, each such series is built inside PolyRat by Lemma 10. A notable consequence is that the Fibonacci sequence is not poly-rational, since its eigenvalues $(1\\pm\\sqrt{5})/2$ are not roots of rational numbers.","pith_inferences":["One testable extension is to grade the class by the degree of the radical: eigenvalues that are roots of rationals of bounded degree might yield a hierarchy of tractable subclasses, with roots of unity at the bottom.","If the one-letter-alphabet restriction is essential, as the authors conjecture, the clean boundary identified here is a property of unary sequences rather than of general weighted automata.","The chained-loop normal form suggests a concrete algorithm for the Skolem problem on poly-rational sequences: reduce to checking whether a finite sum of terms $c\\,\\lambda^n n^k$ with $\\lambda$ a root of a rational ever vanishes, which is a Diophantine condition that may be decidable by elementary arguments."],"forward_implications":["The Fibonacci sequence is not poly-rational, since its eigenvalues are not roots of rational numbers; hence it cannot be recognised by a polynomially ambiguous weighted automaton or a copyless cost-register automaton.","The Skolem problem—whether a given sequence hits zero—is decidable and NP-hard for poly-rational sequences, transferring the known lower bound for eigenvalues that are roots of unity to all four equivalent presentations.","The ambiguity hierarchy of weighted automata is strict: deterministic, finitely ambiguous, polynomially ambiguous, and unrestricted weighted automata form a strictly increasing chain, with explicit separating sequences for each strict inclusion.","PolyRat is closed under Cauchy product even though that closure was not immediate from its definition; closure follows from the equivalence with rational formal series."],"supporting_citations":[{"why":"Supplies Proposition 1, the normal-form theorem for copyless cost-register automata on which the CCRA ⊆ PolyRat direction rests.","marker":"[14]"},{"why":"Provides the classical fact (Lemma 16) that every linear recurrence sequence has rational formal series P/Q, used in both directions of Theorem 15.","marker":"[8]"},{"why":"Defines rational expressions and the classical equivalence between rational expressions and linear recurrence sequences that motivates the poly-rational fragment.","marker":"[19]"},{"why":"Introduces cost-register automata and establishes the linear-CRA model that the copyless variant extends in Section 4.","marker":"[3]"},{"why":"Supplies the weighted-automata formalism and background used throughout Section 3 for the PolyWA characterisation.","marker":"[6]"},{"why":"Shows copyless cost-register automata form a subclass of linear cost-register automata, situating CCRA inside the known landscape.","marker":"[12]"}],"fun_headline_variants":["Poly-rational sequences match four known classes exactly","Eigenvalue-restricted recurrences are exactly poly-rational","Poly-rational sequences unify weighted automata, cost registers, and series","Five-way equivalence: poly-rational, automata, cost registers, series"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The inclusion CCRA ⊆ PolyRat relies on the cited theorem that every copyless cost-register automaton can be put into normal form, with registers updated in a fixed order and no register copied; if that structural theorem failed, the equivalence would lose one of its five directions.","fun_headline_variants_meta":{"raw":{"variants":["Poly-rational sequences match four known classes exactly","Eigenvalue-restricted recurrences are exactly poly-rational","Poly-rational sequences unify weighted automata, cost registers, and series","Five-way equivalence: poly-rational, automata, cost registers, series"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001236,"raw_usage":{"total_tokens":5002,"prompt_tokens":798,"completion_tokens":4204,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":414,"completion_tokens_details":{"reasoning_tokens":4130}},"tokens_in":414,"tokens_out":4204,"duration_ms":32680,"temperature":1.0,"reasoning_tokens":4130,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:59:32.746222+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Factor the reduced formal series of any polynomially ambiguous weighted automaton: the paper predicts every irreducible factor of the denominator has the form $1-\\lambda x^\\ell$. One automaton whose denominator contains an irreducible factor such as $x^2-x-1$—the Fibonacci characteristic polynomial—would refute Theorem 15; the mirror test is a copyless cost-register automaton whose eigenvalues include a number like $(1+\\sqrt{5})/2$.","supporting_citations":[{"cited_title":"Copyless cost-register automata: Structure, expressiveness, and closure properties","cited_arxiv_id":null,"evidence_quote":"Supplies Proposition 1, the normal-form theorem for copyless cost-register automata on which the CCRA ⊆ PolyRat direction rests."},{"cited_title":"Graham, Donald E","cited_arxiv_id":null,"evidence_quote":"Provides the classical fact (Lemma 16) that every linear recurrence sequence has rational formal series P/Q, used in both directions of Theorem 15."},{"cited_title":"Maximal partition logic: Towards a logical characterization of copyless cost register automata","cited_arxiv_id":null,"evidence_quote":"Shows copyless cost-register automata form a subclass of linear cost-register automata, situating CCRA inside the known landscape."}],"review_version":1}