{"id":"4a974f6e-af0b-48e2-838e-525ed6bace93","arxiv_id":"2505.09282","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A follow-up theorem claims phase transitions appear in all adequately-balanced decision problems over odd-sized alphabets, but the proof's central alphabet-encoding construction is invalid as written.","lead":"This paper claims that every 'adequately-balanced' decision problem with an odd-sized alphabet also shows a phase transition, extending the author's earlier result for even-sized alphabets. The proof is a transfer argument using mappings between alphabets, but the key mapping construction contains mathematical errors and relies on assumptions built into the definition.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 2's encoding P-isomorphism is not well-defined: θ_Σ uses digits 1..|Σ| while α_Π outputs base-(|Σ|+1) digits 0..|Σ|, so ξ can produce illegal words over Π; Theorem 2's reduction to even alphabets has no valid bridge.","rationale":"Read in good faith, the paper aims to extend Theorem 1 to odd-sized alphabets by transferring odd-alphabet languages through a P-isomorphism to even-alphabet languages. The only offered route is Lemma 3, which depends on Lemma 2, followed by Lemma 6. The reader's weakest assumption is exactly the soundness of the P-isomorphism ξ in Lemma 2, and I agree that this is the most load-bearing point. The failure is concrete, not a philosophical worry: for a tiny alphabet and word, Eqs. B2-B4 produce a string containing the symbol 0, which is not in Π. Consequently, ξ is not a function into Π*, and all subsequent diagrams and reductions in Lemma 3 are undefined. Because Theorem 2 has no independent proof of the odd-to-even reduction, the central claim is unsupported as submitted. I also acknowledge the paper's strengths: Theorem 1 is an independent prior result, and the intended bijective-numeration construction is plausibly repairable, so the issue is with the submitted proof rather than necessarily with the theorem statement. However, the current Lemma 2 alone blocks the argument, so the reader's REJECT verdict remains appropriate; no verdict adjustment is needed.","tokens_in":20172,"tokens_out":9454,"duration_ms":89507,"concrete_test":"Instantiate Lemma 2 with Σ={1,2,3}, Π={1,2,3,4}, and L={121}. Using Eqs. (B2)-(B4), compute θ_Σ('121')=1·1+2·3+1·9=16, then α_Π(16) digitwise: j=0: 16 mod 4 = 0, j=1: floor(16/4) mod 4 = 0, j=2: floor(16/16) mod 4 = 1, so ξ('121')='001'. Since '0'∉Π, ξ is not a map from Σ* to Π*. Then re-run Lemma 3's construction with a corrected bijective-base ξ using digits 1..|Π| and check whether the bounds in Eqs. (B21)-(B26) still hold; if the proof is patched, all downstream steps must be re-verified.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 2 (Appendix B.1) is the bridge that makes Lemma 3 and hence Theorem 2 work, but its ξ is not a map from Σ* to Π*. Def. 18 defines θ_Σ using the symbols 1,...,|Σ| as little-endian base-|Σ| digits; for example, over Σ={1,2,3}, the word '121' receives value 1·3^0 + 2·3^1 + 1·3^2 = 16. Def. 19 defines α_Π(n) by n mod |Π|, i.e. standard base-(|Σ|+1) digits 0,...,|Σ|. But Π={1,...,|Σ|+1} contains no 0. For n=16, the base-4 digits are 0,0,1, so ξ('121')='001', which is not a word over Π. Thus ξ is not a codomain-correct bijection, and the inversion argument in Eqs. B6-B8 cannot even be evaluated on such outputs. Since Lemma 3 constructs H by H={ξ(x): x∈L}, the reduction of odd-alphabet adequately-balanced languages to even-alphabet NAEU languages is not established, so Theorem 2 has no supported proof. This is not a missing edge case but a mismatch in the core representation; a corrected bijective-base encoding would require rewriting Lemma 2, and the current proof does not contain it.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to extend the author's earlier result on phase transitions in decision problems over even-sized alphabets to odd-sized alphabets. It defines a class of languages called 'adequately-balanced' languages, states a definition of phase transitions for decision problems, and proves Theorem 2: every adequately-balanced language over an odd-sized alphabet exhibits a phase transition. Combined with the prior even-alphabet result, this yields Theorem 3: every adequately-balanced language exhibits a phase transition. The main technical bridge is Lemma 2, which proposes a polynomial-time bijection between strings over an alphabet of size |Σ| and strings over an alphabet of size |Σ|+1, and Lemma 3, which uses this bijection to reduce odd-alphabet languages to even-alphabet languages. Lemma 6 is then used to transfer the phase-transition property back along the bijection.","tokens_in":20439,"tokens_out":4300,"duration_ms":46171,"significance":"If the main theorem were correct, it would fill a genuine gap in the author's prior work and strengthen the claim that phase transitions are ubiquitous in decision problems. The paper also takes a natural high-level approach: transfer phase transitions along preserving-P-isomorphisms. However, the significance of the claimed result is undermined by load-bearing technical errors: the central encoding of Lemma 2 is not a bijection, Lemma 6's transferred parameter is not well-typed, and the formal definition of phase transition has an undefined 'fraction of Σ*' in condition 3. The paper currently does not provide a valid proof of its central claim.","major_comments":[{"comment":"The proposed mapping ξ is not a function from Σ* to Π*. Definition 18 interprets strings with symbols 1,...,|Σ| as base-|Σ| numerals, while Definition 19 outputs ordinary base-|Π| digits, which include 0. For Σ={1,2,3}, the word x='121' satisfies θ_Σ(x)=1·3^0+2·3^1+1·3^2=16, and α_Π(16) in base 4 is the string '001', which contains the symbol 0 not in Π. Thus ξ(x) is not a word over Π. Consequently H={ξ(x): x∈L} in Lemma 3 is not a language over Π, and the reduction to the even-alphabet theorem collapses.","section":"Appendix B.1, Lemma 2 and Defs. 18-20"},{"comment":"The algebra used to prove that α_Ξ(θ_Ξ(z)) recovers z is invalid: the sum contains terms |Ξ|^{j-k} with j<k, and negative powers are not handled by the stated modular arithmetic. Dropping the outer floor and claiming the result equals the k-th symbol of z is not justified. This is not a minor typo; it is the formal core of the attempted proof that ξ is invertible.","section":"Appendix B.1, Eq. (B6)"},{"comment":"The transferred parameter γ' is ill-typed. Since γ maps Π* to R and ξ maps Σ* to Π*, the expression (ξ∘γ)(x) is undefined: ξ cannot be applied to a real number. The intended definition must be γ'(x)=γ(ξ(x)), and indeed the subsequent equation (B49) uses that correct form. As written, the definition of the parameter that is supposed to induce the phase transition in L does not make sense.","section":"Appendix B.2, Lemma 6, Eq. (B48)"},{"comment":"Condition 3 of the phase-transition definition refers to 'the fraction of Σ*' that maps into a real interval, but Σ* is infinite and no probability measure is specified. Without a measure, this fraction is undefined, so the exponential-growth condition is not meaningful. This issue is inherited from the prior work but is load-bearing for both Theorem 1 and Theorem 2, since both are stated in terms of Definition 8.","section":"Section I.C, Def. 8, condition 3"},{"comment":"The odd-alphabet portion of the definition of 'adequately-balanced' is not self-contained. Item 1 refers to sets defined using ξ and ξ^{-1} 'as in Def. 20', but Definition 20 appears only inside the proof of Lemma 2, which is supposed to establish the existence and correctness of ξ. If Lemma 2 fails, the definition of adequately-balanced over odd alphabets is underspecified, and even the statement of Theorem 2 lacks a clear domain of quantification.","section":"Section II.A, Def. 16"}],"minor_comments":[{"comment":"The caption states that 1_H is the indicator function of H with domain Σ*, but H⊆Π*; the domain should be Π*.","section":"Fig. 2 caption"},{"comment":"The proof says Theorem 2 'depends most crucially on Theorem 1', but the actual dependence is on the validity of Lemmas 3 and 6; the phrasing obscures where the proof can fail.","section":"Section II.C, proof of Theorem 2"},{"comment":"The diagram-chasing argument in Fig. 5 is not a substitute for a precise proof of the claimed correspondence between the B_ϕ_j and B^{ξ^{-1}∘ϕ∘ξ}_n sets; the displayed equations do not by themselves establish contiguity or the claimed α_j values.","section":"Appendix B.2, Eq. (B29)-(B32)"},{"comment":"There are numerous distracting typographical and referencing errors, including footnote markers that interrupt sentences and captions that do not match the text; a careful editorial pass is needed.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The manuscript depends heavily on the author's own prior and unpublished work, and the central technical construction fails at a basic level. Even if the typographical issues were fixed, Lemma 2's encoding is not a valid bijection and would require a substantially different proof strategy. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper asks the right question - do odd-sized alphabets escape the phase-transition result from the earlier paper? - but the bridge it builds does not hold. Lemma 2's P-isomorphism is not a map to the target alphabet. So Theorem 2, and hence Theorem 3, are not established.\n\nWhat is genuinely nice: the paper is clearly organized, the definitions are careful, and the author is upfront that the odd-alphabet conditions are proof-technical. The transfer strategy via preserving-P-isomorphisms is a natural way to extend the even-alphabet result, and the discussion of why paddability and sparsity conflict is reasonable.\n\nThe soft spots are structural. First, Lemma 2 (Appendix B.1) defines θ_Σ using symbols 1..|Σ| as base-|Σ| digits, while α_Π outputs standard base-(|Σ|+1) digits 0..|Σ|. Since the target alphabet is {1,...,|Σ|+1}, the output can contain the illegal digit 0. Example: Σ={1,2,3}, '121' maps to '001'. That is not a word over Π, so ξ is not a bijection Σ* -> Π*. The proof of Lemma 3 collapses, and Theorem 2 has no base. This is load-bearing, not a typo. A corrected encoding would need bijective numeration or an offset, and it is not in the paper.\n\nSecond, Lemma 6 defines γ'(x) = (ξ∘γ)(x), but ξ : Σ* -> Π* and γ : Π* -> R; the composition is backwards. It should be γ∘ξ. As written, Condition 3 in Def. 8 is also not well-defined: 'the fraction of Σ*' is undefined since Σ* is infinite; one needs a limiting or level-based definition.\n\nI also share the circularity concern. Def. 16's odd-alphabet conditions (alt-NAEU, proportional splitting) already encode the balance needed for the phase transition, so Theorem 2 is close to being true by definition plus the earlier Theorem 1. That doesn't make it wrong, but it lowers the interest level.\n\nWho gets value: someone working on phase transitions in complexity may find the framework and the discussion of adequately-balanced languages useful. But as a proof of the claimed theorem, it fails. I would tell the author to fix Lemma 2 and resubmit; the repair looks conceivable. A serious editor could send it to referees to see if the transfer argument can be made to work with a correct encoding. I would not desk-reject it outright, but I would not accept this version.","headline":"Odd-alphabet extension is a natural question, but the P-isomorphism bridge is broken, so the theorem is unsupported.","tokens_in":20980,"tokens_out":5381,"would_cite":false,"duration_ms":47260,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that every adequately-balanced language over an odd-sized alphabet exhibits a phase transition, so together with the even case every adequately-balanced language does.","keywords":["phase transitions in decision problems","odd-sized alphabets","adequately-balanced languages","paddable languages","P-isomorphism","not-anywhere-exponentially-unbalanced","RoughP","computational complexity"],"falsifier":"Compute the proposed map on one small input: take $\\Sigma=\\{1,2,3\\}$ and $\\Pi=\\{1,2,3,4\\}$, and let $x='121'$. The little-endian base-3 value is $1+2\\cdot 3+1\\cdot 9=16$, and the paper's output rule expresses 16 in base 4 as '001', which contains the symbol 0 and therefore is not a word over $\\Pi$. This single calculation shows $\\xi$ is not a map from $\\Sigma^*$ to $\\Pi^*$ as written; if no corrected digit convention is supplied, the reduction has no first step.","tokens_in":1495,"feed_emoji":"📈","tokens_out":2408,"duration_ms":116149,"temperature":0.7,"pith_summary":"This paper tries to close a parity gap in the theory of phase transitions in decision problems. It claims that every 'adequately-balanced' language over an odd-sized alphabet has a phase transition, meaning there is a polynomial-time parameter along which the accepting fraction tends to 1 in one direction and to 0 in the other, with exponentially concentrated parameter slices near a threshold. Since an earlier result already covered even-sized alphabets, the two claims together imply that every adequately-balanced language over every finite alphabet of at least two symbols exhibits a phase transition. The argument works by mapping the odd alphabet to an even alphabet one symbol larger, transferring the language to the even side, and carrying the phase transition back.","feed_headline":"Odd-sized alphabets also force phase transitions","feed_subtitle":"The even-alphabet result is extended to every adequately-balanced decision problem, closing the parity gap.","key_machinery":"The load-bearing object is the preserving P-isomorphism $\\xi=\\alpha_\\Pi\\circ\\theta_\\Sigma$. Here $\\theta_\\Sigma$ reads a string over the odd alphabet as an integer in little-endian base $|\\Sigma|$, and $\\alpha_\\Pi$ writes that integer as a word over $\\Pi$ in base $|\\Pi|=|\\Sigma|+1$. A preserving P-isomorphism is a polynomial-time bijection between the two string sets that preserves membership in the corresponding languages, so $\\xi$ converts the odd-alphabet language into an even-alphabet language while keeping 'is accepted' unchanged. Because the map is bijective and fast, parameter slices, acceptance fractions, and exponential-growth conditions are carried across in both directions, which is what lets a phase transition on the even side be imported back to the odd side. The additional clauses in the definition of 'adequately-balanced' for odd alphabets are engineered to make the transferred even-alphabet language satisfy the known sufficient conditions.","core_discovery":"The paper's central claim is Theorem 2: any adequately-balanced language over an odd-sized alphabet exhibits a phase transition. The theorem is proved by reduction to the already-established even case. Given an adequately-balanced language $L$ over $\\Sigma$ with $|\\Sigma|$ odd, the author constructs a preserving P-isomorphism $\\xi:\\Sigma^*\\to\\Pi^*$, where $|\\Pi|=|\\Sigma|+1$ is even, and defines $H=\\{\\xi(x): x\\in L\\}$. The proof then tries to show $H$ is paddable and not-anywhere-exponentially-unbalanced, which makes Theorem 1 applicable, and finally uses the fact that membership-preserving bijections push phase transitions forward to conclude $L$ has one. Combined with Theorem 1, this yields Theorem 3: every adequately-balanced language exhibits a phase transition.","pith_inferences":["The proof is existential: it does not exhibit the threshold parameter for any specific language, so actually using these transitions to test or accredit an algorithm would require a separate construction for the parameter.","If the digit mismatch in $\\xi$ is repaired by giving both alphabets the same digit convention, the overall strategy could go through; if it cannot be repaired, the odd-alphabet theorem needs a different reduction than the one presented.","A natural testable next step is to relax the odd-alphabet extra conditions one by one and ask whether the phase transition persists, since the author himself flags those conditions as proof artifacts rather than fundamental restrictions."],"forward_implications":["Phase transitions in decision problems cannot be blamed on alphabet parity: every adequately-balanced language over every alphabet of size at least two has one.","The preservation argument supplies a transfer principle: any phenomenon that is provably present for all even-sized alphabets and is invariant under preserving P-isomorphisms will automatically be present for odd-sized alphabets.","For paddable promise-BQP languages, the phase transition is available as a heuristic check on a quantum device's outputs, the setting sketched in the paper's proposed verification protocol.","Because no paddable language is sparse, the balanced-density requirement does not silently restrict the theorem to a trivial or empty class of languages."],"supporting_citations":[{"why":"Supplies Theorem 1 for even-sized alphabets, the base case that Theorem 2 reduces to, and the formal definition of phase transition used in the paper.","marker":"[16]"},{"why":"Provides the RoughP framework and the theorem that every paddable language is in RoughP, which the proof uses to make the transferred language $H$ satisfy the not-anywhere-exponentially-unbalanced condition.","marker":"[26]"},{"why":"Establishes the formal model of polynomial-time computation in which P-isomorphisms, parameters, and the whole reduction are defined.","marker":"[1]"}],"fun_headline_variants":["Odd alphabets join even: phase transitions inevitable","Phase transitions proven for odd-sized alphabets","Parity gap closed: odd alphabets also phase transition","Odd alphabet decision problems always phase transition","Even-alphabet result extends to odd-sized alphabets"],"cache_read_input_tokens":23040,"weakest_assumption_plain":"The proof rests on a 'P-isomorphism,' a fast and reversible renaming that maps every string over the odd alphabet to a string over the even alphabet. That renaming must actually be reversible and land inside the target alphabet; the proposed rule writes numbers using symbols 1 through $|\\Sigma|$ but decodes them using digits 0 through $|\\Pi|-1$, so the two digit conventions do not line up.","fun_headline_variants_meta":{"raw":{"variants":["Odd alphabets join even: phase transitions inevitable","Phase transitions proven for odd-sized alphabets","Parity gap closed: odd alphabets also phase transition","Odd alphabet decision problems always phase transition","Even-alphabet result extends to odd-sized alphabets"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000271,"raw_usage":{"total_tokens":1549,"prompt_tokens":787,"completion_tokens":762,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":403,"completion_tokens_details":{"reasoning_tokens":691}},"tokens_in":403,"tokens_out":762,"duration_ms":7103,"temperature":1.0,"reasoning_tokens":691,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T21:36:27.676204+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the proposed map on one small input: take $\\Sigma=\\{1,2,3\\}$ and $\\Pi=\\{1,2,3,4\\}$, and let $x='121'$. The little-endian base-3 value is $1+2\\cdot 3+1\\cdot 9=16$, and the paper's output rule expresses 16 in base 4 as '001', which contains the symbol 0 and therefore is not a word over $\\Pi$. This single calculation shows $\\xi$ is not a map from $\\Sigma^*$ to $\\Pi^*$ as written; if no corrected digit convention is supplied, the reduction has no first step.","supporting_citations":[{"cited_title":"Explaining the Ubiquity of Phase Transitions in Decision Problems","cited_arxiv_id":"2501.14569","evidence_quote":"Provides the RoughP framework and the theorem that every paddable language is in RoughP, which the proof uses to make the transferred language $H$ satisfy the not-anywhere-exponentially-unbalanced condition."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the formal model of polynomial-time computation in which P-isomorphisms, parameters, and the whole reduction are defined."}],"review_version":1}