{"id":"758bab24-4145-4a53-b9d9-6796c174d0c3","arxiv_id":"2509.05871","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A moment identity over homomorphisms yields candidate low-soundness tests for cyclic, automorphism, and Lie settings, but one headline theorem is stated with an impossible guarantee.","lead":"This paper presents a general framework for testing whether a function between finite groups is close to a homomorphism, using random tuples weighted by algebraic structure. It claims the first constant-query tests in the low-soundness regime for several non-abelian group families, plus improved list-decoding bounds.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.10 is false as stated: at δ=1 it promises agreement >1, and the proof inverts the ζ(2) bound.","rationale":"The reader's weakest assumption identifies the same load-bearing failure, and the arithmetic confirms it: the direction of the zeta bound is exactly reversed in the proof of Theorem 3.10. The false theorem is load-bearing because it is the advertised result for arbitrary cyclic groups and the entry in Table 1. The list-decoding corollary may be salvageable since it only needs an upper bound on γ_3, but the testing theorem as stated is refuted by a function that is already a homomorphism, which must pass with probability 1 and agree with itself with probability 1. This is an internal inconsistency, not a disagreement with external consensus, and it invalidates the central claim for cyclic groups. The rest of the framework may contain interesting ideas, but the headline result needs correction before the paper can be accepted.","tokens_in":32908,"tokens_out":7428,"duration_ms":63029,"concrete_test":"Take G=H=Z_5 and f=id, with k=4. Then δ_4=1; Theorem 3.10 asserts a homomorphism with agreement ≥ ζ(2)^2≈2.705, impossible since agr≤1. Equivalently, re-derive the telescoped bound from Proposition 3.8: γ_4/γ_3 ≥ |G|/ζ(2)^2, giving M ≥ δ_4/ζ(2)^2, the reciprocal of the stated constant.","verdict_should_be":"REJECT","load_bearing_attack":"Theorem 3.10 claims for arbitrary cyclic groups G,H that agreement ≥ (ζ(2)^2·δ_k)^(1/(k-3)). This is impossible even for f a homomorphism: f passes with δ_k=1, and for k=4 the right-hand side is ζ(2)^2≈2.705>1, while agreement is a probability at most 1. The proof's telescoping step requires a lower bound on γ_k/γ_3. Proposition 3.8 gives γ_k≥|G|^k and γ_3≤|G|^3·ζ(2)^2, hence γ_k/γ_3 ≥ |G|^(k-3)/ζ(2)^2. Substituting into M^(k-3) ≥ δ_k·γ_k/(|G|^(k-3)·γ_3) yields M ≥ (δ_k/ζ(2)^2)^(1/(k-3)), the reciprocal of the stated constant. The displayed proof instead cites Corollary 3.3, a prime-power statement, after Lemma 3.6, without deriving the per-prime ratio that would telescope to ζ(2)^2; the zeta factor is entered in the wrong direction. Since this is the headline first result for arbitrary cyclic groups (Table 1, Theorem 3.10), the central claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a general k-query framework for low-soundness homomorphism testing, based on rewriting the kth agreement moment as an expectation over tuples weighted by the kernel of the evaluation map. It claims constant-query tests for homomorphisms between arbitrary cyclic groups, between vector spaces and fields, for automorphisms and inner automorphisms of several non-abelian families, and for lifted character tests, together with improved list-decoding bounds for cyclic groups. The framework is novel in scope and the constants are derived from explicit group-theoretic quantities rather than fitted parameters.","tokens_in":33125,"tokens_out":30529,"duration_ms":267035,"significance":"If the results were correct, this would be a substantial advance: it would give the first low-soundness constant-query tests for non-abelian groups, unify several known tests such as Kiwi's, and improve the cyclic list-decoding bound from O(eps^-105) to O(eps^-2) or O(eps^-3). The moment identity in Lemma 2.1 is elegant and likely reusable, and the framework is self-contained. However, the headline cyclic-group theorem is false as stated, and the vector-space moment computations are internally inconsistent as written; both issues are load-bearing for the paper's central claims.","major_comments":[{"comment":"Theorem 3.10 is false as stated. For k=4, take f to be a homomorphism: the test passes with probability delta_4=1 and agr(f,varphi)=1, but the claimed lower bound is (zeta(2)^2 * 1)^(1/(4-3)) = zeta(2)^2 ≈ 2.705 > 1, which is impossible. The proof is not a valid derivation for arbitrary cyclic groups: it repeats the proof of Theorem 3.4 with an undefined parameter t and an undefined prime p, and it invokes Corollary 3.3, a prime-power statement, after Lemma 3.6 without the per-prime telescoping that would be needed. The available bounds point in the opposite direction: Proposition 3.8 gives gamma_k >= |G|^k and gamma_3 <= |G|^3 zeta(2)^2, hence gamma_k/gamma_3 >= |G|^(k-3)/zeta(2)^2, so the telescoping product can only yield M >= (delta_k / zeta(2)^2)^(1/(k-3)), the reciprocal of the displayed constant. Since Theorem 3.10 is the headline cyclic-group result and is cited by Table 1, Theorem 1.2, and Theorem 6.6, the affected statements must be corrected.","section":"§3.2, Theorem 3.10 and Table 1"},{"comment":"The moment computations for the vector-space test are internally inconsistent as written. Claim 4.2 states Pr[rank(x)=k] ≈ q^(-2n)(1 - q^(k-1)/(q^n(q-1))), which tends to 0, while the proof of the same claim expands the product to 1 - O(q^(k-n)) ≈ 1. Claim 4.4 then writes the leading term of sum_phi agr(f,phi)^k as q^(-n) Pr[rank=k] * q^(n-k), which with Pr[rank=k] approximately 1 is q^(-k), whereas the definition of beta in the proof and Lemma 2.1 give q^(n-k) for a random f. The sums in Claim 4.4 and Corollary 4.7 also involve delta_1, and the binomial identity involves a delta_0 term, although R_1 is empty for k>1 and delta_0 is never defined. Because Corollary 4.7 and Theorem 4.8 depend directly on Claim 4.4, the soundness proof for Hom(F_q^n, F_q) is not verifiable in the submitted form.","section":"§4.1, Claims 4.2 and 4.4"}],"minor_comments":[{"comment":"In the telescoping product, the exponent (1/|G|)^(k-t) should be (1/|G|)^(k-t-1) when multiplying from i=t+2 to k; the subsequent line silently restores the correct exponent.","section":"§3.1, proof of Theorem 3.4"},{"comment":"The manuscript has extensive typesetting corruption, with the tuple variable rendered as a sequence of unusual symbols, and many typos such as 'exstraspecial', 'inverible', 'unitrianguar', and 'Riemmann'; a careful copyedit is needed.","section":"Notation and typos"},{"comment":"The level-j sets R_j are defined for tuples in G^k, but Claim 4.4 evaluates delta_j on G^j and the case j=1 is not handled; the relationship between these R_j should be clarified.","section":"§4.1, Definition 4.1"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern lands: Theorem 3.10 is false as stated and the zeta factor is inverted in the proof. I recommend major revision rather than rejection because the corrected bound M >= (delta_k / zeta(2)^2)^(1/(k-3)) follows readily from the paper's own Proposition 3.8, and the list-decoding claims are independent of this constant. The Section 4 issue is more serious: the authors must re-derive Claim 4.4 carefully and reconcile the displayed probability formulas with the proof. If the moment identity for Hom(F_q^n, F_q) cannot be repaired, the vector-space results should be withdrawn or supported by a different argument."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe paper is worth engaging, but the headline result does not hold as stated. The framework—the kernel-weighted evaluation-map moment identity—is genuinely useful, and the prime-power cyclic results (Theorem 3.4) look plausible. The non-abelian automorphism sections may contain real new tests, though I did not audit them line by line.\n\nThe soft spot is Theorem 3.10, and it is not minor. For G,H arbitrary cyclic, it claims agreement at least (ζ(2)^2·δ_k)^(1/(k-3)). Take f a homomorphism: δ_k=1, and for k=4 the bound exceeds 1. Impossible. The proof misapplies Corollary 3.3, which is only for prime-power G, to general cyclic groups, and the zeta constant enters inverted: Proposition 3.8 gives γ_k/γ_3 ≥ |G|^(k-3)/ζ(2)^2, not |G|^(k-3)·ζ(2)^2. So the first claimed constant-query low-soundness test for arbitrary cyclic groups is unsupported. The list-decoding bound of O(ε^-3) for general cyclic groups is tied to the same flawed argument, so it is also in question, though it could be salvaged with a correct constant.\n\nSection 4 also has moment formulas that look off by a factor of |Hom(G,H)|; taken literally the dimensions do not match. That affects the recovery of Kiwi's result. These are fixable in principle, but they are load-bearing, not typos.\n\nWhat is actually new: the kernel-weighted distribution and the rewriting of Σ_φ agr(f,φ)^k as a test-passing probability is a clean idea, and the prime-power and non-abelian applications demonstrate it has range. If the cyclic section is repaired, this could be a solid paper. As it stands, the advertised first constant-query tests for arbitrary cyclic groups is the part that fails.\n\nWho should read it: property testers and coding theorists. The framework section is worth a look; the cyclic guarantees should not be relied upon until fixed.\n\nMy recommendation: it deserves a serious referee, but the current version should not be accepted. The referee should be pointed at Theorem 3.10 and the Section 4 normalization. If those are fixed, it can be a good paper.","headline":"The kernel-weighted framework is a genuinely useful idea, but the headline arbitrary-cyclic theorem is false as stated and the cyclic section needs major revision before the paper can be trusted.","tokens_in":33693,"tokens_out":2631,"would_cite":false,"duration_ms":22599,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","20D60","94B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single kernel-weighted test gives constant-query homomorphism tests for arbitrary cyclic groups and several non-abelian families.","keywords":["homomorphism testing","low soundness regime","list decoding","cyclic groups","inner automorphisms","character testing","kernel-weighted evaluation map","finite groups"],"falsifier":"Compute $\\gamma_4$ and $\\gamma_3$ exactly for $G=H=\\mathbb{Z}_6$ (or $\\mathbb{Z}_p$ for a small prime $p$). If $\\gamma_4/\\gamma_3<|G|\\zeta(2)^2$, then the claimed $k=4$ guarantee fails as stated, because it would require agreement at least $\\zeta(2)^2\\delta_4$, which exceeds 1 for large $\\delta_4$. This is a finite calculation and can be checked by brute force.","tokens_in":32668,"feed_emoji":"🧮","tokens_out":12841,"duration_ms":103135,"temperature":0.7,"pith_summary":"The paper tries to establish that low-soundness homomorphism testing—where a function passes the test with probability $\\delta$ that may be far below the random passing rate—is governed by one general $k$-query test. For arbitrary cyclic groups $G,H$, it claims that if $f$ passes $\\mathrm{Test}_{\\ker k}$ with probability $\\delta_k$, then some homomorphism agrees with $f$ on at least $(\\zeta(2)^2\\delta_k)^{1/(k-3)}$ of the inputs, and the list of homomorphisms with agreement at least $\\varepsilon$ has size $O(\\varepsilon^{-3})$. The same machinery yields the first constant-query low-soundness tests for non-abelian groups: automorphisms of dihedral and symmetric groups, inner automorphisms of finite simple and extraspecial groups, and characters of $\\mathrm{GL}_n(\\mathbb{F}_q)$ and of Lie algebras over $\\mathbb{F}_q$, and it recovers the known 3-query vector-space test. A sympathetic reader would care because these are the first such tests beyond abelian groups of bounded exponent, and because the proof reduces testing to bounding a group-theoretic constant rather than doing Fourier analysis.","feed_headline":"Constant-query tests for group homomorphisms at any passing rate","feed_subtitle":"One kernel-weighted test covers cyclic groups, non-abelian automorphisms, and cuts cyclic list-decoding lists to ε⁻³.","key_machinery":"The machinery is the evaluation map $\\Gamma_x:\\operatorname{Hom}(G,H)\\to H^k$, $\\Gamma_x(\\varphi)=(\\varphi(x_1),\\dots,\\varphi(x_k))$, which is $N$-to-one on its image with $N=|\\ker\\Gamma_x|$. The test $\\mathrm{Test}_{\\ker k}$ samples $x=(x_1,\\dots,x_k)\\in G^k$ with probability proportional to $|\\ker\\Gamma_x|$ and accepts exactly when $(f(x_1),\\dots,f(x_k))$ lies in the image of $\\Gamma_x$. Lemma 2.1 rewrites the agreement moment as $\\delta_k\\gamma_k/|G|^k$ plus a small error term, where $\\gamma_k=\\sum_\\varphi|\\ker\\varphi|^k$; once $\\gamma_k$ is bounded, the test's soundness and list size follow by telescoping ratios. For automorphisms the same construction replaces kernels by pointwise stabilizers and $\\gamma_k$ by $\\rho_k=\\sum_\\varphi|\\operatorname{Fix}(\\varphi)|^k$, whose inner-automorphism version is the conjugacy-class zeta function $\\sum_C|C|^{1-k}$.","core_discovery":"The paper's central claim is that the $k$-th power moment of agreement, $\\sum_{\\varphi\\in\\operatorname{Hom}(G,H)}\\operatorname{agr}(f,\\varphi)^k$, can be rewritten exactly as the kernel-weighted expectation of the number of homomorphisms consistent with $f$ on a random $k$-tuple. This identity converts soundness analysis into a calculation of $\\gamma_k=\\sum_\\varphi|\\ker\\varphi|^k$. For cyclic groups the paper claims $\\gamma_k\\le |G|^k\\zeta(k-1)^2$ and uses the telescoped ratios to obtain the soundness bound $(\\zeta(2)^2\\delta_k)^{1/(k-3)}$; for prime-power cyclic groups and $p$-rank $t$ abelian targets it obtains agreement roughly $\\delta^{1/(k-t-1)}$ and list size $O(\\varepsilon^{-(t+1)})$. The same moment identity, with pointwise stabilizers replacing kernels, gives inner-automorphism tests, and a lifting lemma extends the tests from a base group to any group projecting onto it, which is how the $\\mathrm{GL}_n(q)$ and Lie-algebra character tests are derived.","pith_inferences":["If the cyclic theorem's constant is corrected (the stated proof needs $\\gamma_k/\\gamma_3\\ge |G|^{k-3}\\zeta(2)^2$, while Proposition 3.8 only upper-bounds that ratio), the $k\\ge 4$ tradeoff would still survive with a different constant, and the list-size improvement would likely survive unchanged.","The kernel-weighted distribution explains why the uniform 3-query product test from the literature fails on cyclic groups: uniform triples with product 1 rarely lie inside the small kernels that dominate the agreement moment, whereas kernel weighting concentrates samples exactly where the evaluation map is many-to-one.","The method should extend to any group family with a controllable bound on the conjugacy-class zeta function $\\sum_C |C|^{1-k}$, such as alternating groups, direct products, or additional Lie-type groups, since the test's logic depends only on that ratio.","A concrete next test: check whether the telescoping argument works for $k=3$ on cyclic groups once the ratio constant is fixed; a successful version would yield a 3-query test matching the known vector-space test's query count."],"forward_implications":["For arbitrary cyclic groups, $k$-query tests with soundness scaling like $\\delta^{1/(k-3)}$ become available for every $k\\ge 4$, giving a smooth query-versus-soundness tradeoff.","Combinatorial list decoding for cyclic-group homomorphisms improves to $O(\\varepsilon^{-2})$ in the prime-power case and $O(\\varepsilon^{-3})$ in the general case, replacing the previous $O(\\varepsilon^{-105})$ bound.","Low-soundness tests now exist for non-abelian groups: automorphisms of dihedral and symmetric groups, and inner automorphisms of finite simple and extraspecial groups, none of which had constant-query tests before.","The lifting theorem yields the first Hamming-metric character tests for $\\mathrm{GL}_n(\\mathbb{F}_q)$ and for finite-dimensional Lie algebras over $\\mathbb{F}_q$, with the same query count and guarantee as the base test.","Because the analysis is moment-based rather than Fourier-based, it applies whenever a bound on $\\gamma_k$ (or $\\rho_k$) is available, including groups where $H$ does not embed into $\\mathbb{C}$."],"supporting_citations":[{"why":"Supplies the known 3-query vector-space test whose guarantee the vector-space section recovers.","marker":"[Kiw03]"},{"why":"Gives the earlier BLR-based agreement guarantee for $\\mathbb{F}_p^n\\to\\mathbb{F}_p$ that the paper's test improves on.","marker":"[HW03]"},{"why":"Defines the basic 3-query linearity test and the agreement setup extended here.","marker":"[BLR90]"},{"why":"Provides the high-soundness BLR theorem and the counterexample showing why the plain BLR test fails on cyclic groups in the low-soundness regime.","marker":"[BOCLR07]"},{"why":"Supplies the previous $O(\\varepsilon^{-105})$ list-decoding bound that the cyclic list-size results improve.","marker":"[DGKS08]"},{"why":"Extends the $\\varepsilon^{-105}$ bound to supersolvable groups and serves as the comparison point for the improved cyclic bounds.","marker":"[GS14]"},{"why":"Bounds the conjugacy-class zeta function of finite simple groups; this supplies the ratio used in inner-automorphism testing.","marker":"[LS05]"},{"why":"Gives minimal-degree or quasirandomness bounds for Lie-type groups, covering the simple groups not included in the preceding result.","marker":"[LS74]"},{"why":"Counts conjugacy classes of extraspecial $p$-groups, giving the exact ratio used for inner-automorphism testing there.","marker":"[Pan04]"},{"why":"Introduces quasirandom groups and the small-subgroup consequence used to bound fixed-point ratios.","marker":"[Gow08]"}],"fun_headline_variants":["Constant-query tests for homomorphisms: cyclic to non-abelian","Moment identity powers low-soundness homomorphism tests","First constant-query tests for non-abelian group automorphisms","List decoding for cyclic groups cut to ε⁻³"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise for the arbitrary-cyclic-group theorem is that the telescoped ratio of kernel counts, $\\gamma_k/\\gamma_3$, is at least $|G|^{k-3}\\zeta(2)^2$, but the paper's stated bound on that ratio goes in the opposite direction and the proof invokes a prime-power estimate for general cyclic groups.","fun_headline_variants_meta":{"raw":{"variants":["Constant-query tests for homomorphisms: cyclic to non-abelian","Moment identity powers low-soundness homomorphism tests","First constant-query tests for non-abelian group automorphisms","List decoding for cyclic groups cut to ε⁻³"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000312,"raw_usage":{"total_tokens":1838,"prompt_tokens":1073,"completion_tokens":765,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":689,"completion_tokens_details":{"reasoning_tokens":692}},"tokens_in":689,"tokens_out":765,"duration_ms":7592,"temperature":1.0,"reasoning_tokens":692,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T16:22:11.076429+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute $\\gamma_4$ and $\\gamma_3$ exactly for $G=H=\\mathbb{Z}_6$ (or $\\mathbb{Z}_p$ for a small prime $p$). If $\\gamma_4/\\gamma_3<|G|\\zeta(2)^2$, then the claimed $k=4$ guarantee fails as stated, because it would require agreement at least $\\zeta(2)^2\\delta_4$, which exceeds 1 for large $\\delta_4$. This is a finite calculation and can be checked by brute force.","supporting_citations":[],"review_version":1}