{"id":"e44d4d64-b34f-43bb-8d63-3060c748ac89","arxiv_id":"2504.19777","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"Fitting-free group isomorphism is in AC^3 with multiplication tables and GI-hard with permutation generators, but the paper's FO O(log log n)-variable identification proof uses a false lemma.","lead":"This paper gives fast parallel circuits for comparing Fitting-free groups from multiplication tables, and shows the compact permutation-input version is at least as hard as Graph Isomorphism. Its third headline claim, about short first-order logic descriptions, rests on a lemma that appears to be false.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 9.12(a) is refuted by G=H=A5×A5: the factor-swap automorphism gives Duplicator a consistent response, so Theorem 9.1/9.2 is unsupported as written.","rationale":"The paper's main contributions are threefold. The AC^3 algorithm (Theorem 1.1) and the GI-hardness reduction (Theorem 1.2) have detailed proofs, and I did not find a comparable flaw in them. The descriptive-complexity claim, Theorem 9.1, is a central result stated in the abstract and is the sole basis for the claimed contrast with Abelian groups. Its proof depends entirely on Theorem 9.2, which in turn relies on Lemma 9.12. The A5 × A5 factor-swap example is a minimal, internally consistent counterexample: because pi is an automorphism, the partial map is a genuine isomorphism of the two structures, so no finite sequence of Spoiler moves can refute it. The error is not merely a missing 'non-isomorphic factors' assumption; the lemmas explicitly allow factors to be non-isomorphic, and even when all factors are isomorphic, a permutational automorphism of the direct product is a legal Duplicator strategy. Thus the correct disposition is to keep the reader's CONDITIONAL verdict: the FO section needs repair or removal, while the remaining main results appear sound. I agree with the reader that this is the weakest load-bearing assumption in the paper, and no further objection is needed.","tokens_in":39759,"tokens_out":13607,"duration_ms":141667,"concrete_test":"Instantiate the lemma with G = H = A5 × A5, generators chosen as in Definition 9.10, and fix Duplicator's response to pi, the factor swap. For every Spoiler move in the proof of Lemma 9.12(a) — including the initial g in S_1 and the seven s_{1,j} — verify that the partial map is the restriction of pi and therefore satisfies the winning condition; if so, Lemma 9.12(a) collapses. The equivalent analytical check is to recompute Case 1 with h'_1 = pi(s_{a,1}) and p'_m = pi(p_m) and observe that the two weights are equal, so Lemma 9.11 cannot be applied.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 9.2's Lemma 9.12(a) claims that if Spoiler pebbles g in S_a and Duplicator replies h in S'_b with a != b, then Spoiler can win with O(1) additional pebbles and O(log log n) rounds, assuming the weight hypotheses from Definition 9.10. This is false. Take G = H = A5 × A5, so k = 2 and the pebbling strategy has ell = 1. Let pi be the automorphism swapping the two factors. Spoiler first pebbles x_1,...,x_7 and p_1 (for k = 2, p_1 = x_1); Duplicator answers x'_j = pi(x_j) and p'_1 = pi(p_1). All hypotheses of the lemma hold: all weights match, and the elements s'_{i,j} are exactly the H-components of pi(x_j). Now Spoiler pebbles g in S_1 and Duplicator replies h = pi(g) in S'_2. The whole pebbled configuration is a restriction of the isomorphism pi, so the partial map preserves equality and multiplication; Duplicator can keep responding via pi and wins. The proof break is in Case 1 of Lemma 9.12(a): with h'_1 = pi(s_{a,1}) and p'_m = pi(p_m), we have wt(p_m · s_{a,1}^{-1}) = wt(p'_m · (h'_1)^{-1}), so Lemma 9.11 supplies no contradiction. Since Lemma 9.12 is the step forcing Duplicator's factor-wise responses to align with the chosen generators, the proof of Theorem 9.2, and hence Theorem 9.1, is unsupported as written. Remark 9.13 suggests a different route via socle generation, but that route is not the argument submitted.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the complexity of isomorphism testing for Fitting-free groups. In the Cayley-table model, the authors give a uniform AC^3 algorithm (depth O(log^2 n * poly(log log n)) and size poly(n)) that decides Fitting-freeness and isomorphism, generalizing the polynomial-time algorithm of Babai, Codenotti, and Qiao. In the permutation-generator model, they show that Linear Code Equivalence and Graph Isomorphism are polynomial-time reducible to isomorphism testing of Fitting-free permutation groups. Finally, the paper claims that every Fitting-free group of order n is identified by a first-order formula without counting that uses O(log log n) variables, strengthening a prior result of Brachter that used counting. The first two results appear to be supported by the submitted arguments, but the FO identification claim rests on a false lemma (Lemma 9.12(a)) and is not established as written.","tokens_in":40168,"tokens_out":11652,"duration_ms":109437,"significance":"If the parallel and hardness results are correct, they are significant: the AC^3 upper bound is a substantial improvement over the previous polynomial-time bound for Fitting-free groups in the Cayley model, and the reduction from Linear Code Equivalence to isomorphism of Fitting-free permutation groups is a strong new lower-bound result. The claimed FO identification theorem would also be a noteworthy strengthening of Brachter's counting-WL result, but the proof currently contains a false lemma and the theorem is therefore unsupported. The manuscript also contains useful technical contributions, including a careful depth analysis of Luks's Coset Intersection algorithm for small domains and a parallel treatment of the reduction to Twisted Code Equivalence.","major_comments":[{"comment":"Lemma 9.12(a) is false. Take G = H = A5 × A5, so k = 2 and ℓ = 1. Let π be the automorphism swapping the two factors. Suppose Spoiler first pebbles x_1,...,x_7 and p_1 according to Definition 9.10, and Duplicator answers with x'_j = π(x_j) and p'_1 = π(p_1). Because π is an automorphism, all weight hypotheses of Lemma 9.12 hold. Now Spoiler pebbles g ∈ S_1; Duplicator responds with h = π(g) ∈ S'_2, which satisfies condition (a) with a ≠ b. Nevertheless, Duplicator can continue to respond with π to every subsequent pebble, keeping the entire partial map a restriction of an isomorphism, so Spoiler cannot force a win. The proof of Case 1 fails because for this π, wt(p_1 · s_{1,1}^{-1}) = wt(p'_1 · (h'_1)^{-1}), so Lemma 9.11 gives no contradiction; Case 3 fails because h and h'_1 both lie in S'_2, so their product has weight 1, not 2 as the proof assumes. Since Lemma 9.12 is the step that forces Duplicator's factor-wise alignment, the derivations of Theorem 9.2, Theorem 9.1, and Corollary 9.4 are unsupported as written.","section":"Section 9.2, Lemma 9.12(a)"},{"comment":"Footnote 5 states that [CL24, Lemma 6.10], which assumes h ∉ Soc(H), can be extended to the case wt(h) > 1, citing that the proof shows the stronger statement. This is an unproved extension of a prior result and is used in Lemma 9.9 and in the proof of Theorem 9.2. The claim is plausible but needs a proof; as written, it is an additional gap in the FO section, even though the falsity of Lemma 9.12(a) already breaks the argument.","section":"Section 9.1, footnote 5"},{"comment":"The proof of Theorem 9.2 uses Lemma 9.12 to conclude that Duplicator's responses to the seven generators of each simple factor must lie in the corresponding factor and must induce an isomorphism S_i ≅ S'_i. Because Lemma 9.12(a) is false, this conclusion is not justified, and the final argument that the induced isomorphism of the socle extends to G → H collapses. Remark 9.13 outlines an alternative route via O(log log n)-generation of the socle, but that route is not developed into a proof and the remark explicitly leaves open whether count-free WL can achieve the stated bounds; it therefore does not repair the submitted proof.","section":"Section 9.2, proof of Theorem 9.2"}],"minor_comments":[{"comment":"The notation x_i is used in the definition of p_1 (e.g., p_1 := ∏_{i=1}^{k/2} x_i), but x_i is never defined; only x_{i,j} and x_j are introduced. Please clarify the intended meaning of x_i.","section":"Definition 9.10"},{"comment":"The bound |PISO(G,H)| ≤ |G|·c^{2m} refers to an unspecified constant c; the proof should state explicitly that c is an absolute constant.","section":"Theorem 6.13"},{"comment":"The abstract contains the typo 'Nor mal' in 'Abelian Nor mal Subgroups'; it should be 'normal'.","section":"Abstract"}],"recommendation":"major_revision","confidential_remarks":"The FO identification section relies heavily on prior same-author results ([CL24, GL23a, GL23b]) and on an unproved extension of one of them; this creates a nontrivial verification burden. The false Lemma 9.12(a) is a load-bearing error in a headline theorem, so the manuscript cannot be accepted in its present form. The remaining results (Sections 3-8) appear sound, which suggests that a revision that either repairs Section 9 or removes the unsupported FO claims could be appropriate for the journal."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper has three main results, and two of them are genuinely good. The AC^3 isomorphism test for Fitting-free groups (Theorem 1.1) is a real improvement over the previous P bound, and the depth analysis in Sections 3–7 is careful and plausible. The hardness result for the permutation input model (Theorem 1.2), reducing Linear Code Equivalence and GI to Fitting-free permutation group isomorphism, is clean and, as far as I know, new. Those two results alone make the paper worth engaging with seriously.\n\nThe FO result (Theorem 9.1/9.2) is a different story. Lemma 9.12(a) is false as stated. The stress-test example is correct: take G = H = A5 × A5, and let pi be the factor-swapping automorphism. All the weight hypotheses of Lemma 9.12 hold, but if Spoiler pebbles g in S_1 and Duplicator responds with pi(g) in S_2, the whole configuration remains consistent with pi, so Duplicator can win indefinitely. The proof's Case 1 fails precisely because the weights on both sides are equal. Since Lemma 9.12 is the step that forces Duplicator's factor-wise responses to align, the proof of Theorem 9.2, and with it Theorem 9.1, is unsupported as written.\n\nThe paper's own Remark 9.13 suggests an alternative route via O(log log n)-generation of the socle, but that is not the submitted argument. So the FO claim might be true, but the current proof does not establish it.\n\nThe citation pattern is heavy on the authors' own prior work, but that is not a problem here because the parallel and hardness results are built on independently published algorithms (Luks, BCQ12, Codenotti). The FO section's reliance on unproven extensions of prior same-author results is a real burden, but it is secondary to the concrete false lemma.\n\nBottom line: this paper should be sent to peer review. The AC^3 and hardness theorems have real substance and the depth analysis is detailed enough to check. The FO section needs to be repaired with a correct proof or removed. I would not depend on Theorem 9.1 until that is fixed, but I am fairly confident the rest is solid.\n\nRecommendation: serious peer review, conditional on the authors addressing the FO section.","headline":"Strong new AC^3 and hardness results for Fitting-free groups, but the FO section's key lemma is false; the first two theorems look solid and deserve a serious referee.","tokens_in":40688,"tokens_out":1645,"would_cite":true,"duration_ms":19862,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q19","20B40","03C13"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper places Fitting-free group isomorphism in AC^3 for multiplication-table inputs, proves permutation-input versions at least as hard as graph isomorphism and linear code equivalence, and claims identification of every such group…","keywords":["group isomorphism","Fitting-free groups","AC^3 circuits","parallel complexity","Weisfeiler-Leman","first-order logic","linear code equivalence","permutation groups"],"falsifier":"The FO claim would be settled by running the count-free WL Version I pebble game with O(log log n) pebbles on candidate pairs of Fitting-free groups; in particular, checking the factor-swap configuration in $G = H = A_5 \\times A_5$ tests Lemma 9.12(a), since if Duplicator can survive with the swapped response, the proof of Theorem 9.1 collapses even though the theorem itself might still hold via a different argument.","tokens_in":39532,"feed_emoji":"⚡","tokens_out":10520,"duration_ms":103133,"temperature":0.7,"pith_summary":"This paper argues that Fitting-free groups—finite groups with no nontrivial Abelian normal subgroups, the quotients left after removing the solvable radical—have a three-way complexity profile for isomorphism testing. When groups are given by multiplication tables, isomorphism is decidable in the small-depth circuit class $AC^{3}$ (unbounded fan-in gates, depth O($log^{3}$ n), polynomial size), improving the known polynomial-time bound. When the same groups are given by generating permutations, the problem becomes at least as hard as Graph Isomorphism and Linear Code Equivalence, the latter having no known subexponential-time algorithm. In addition, the paper claims every Fitting-free group of order n is identified, up to isomorphism, by a first-order formula using only O(log log n) variables, in sharp contrast to Abelian families that require O(log n) variables. These results matter because Fitting-free groups are the natural bottleneck case left after decomposing a group by its solvable radical, so the $AC^{3}$ algorithm and the FO bound are stepping stones toward the general group isomorphism problem.","feed_headline":"Fitting-free group isomorphism drops to AC^3","feed_subtitle":"Cayley-table tests run at small circuit depth, while permutation-input tests stay at least as hard as graph isomorphism.","key_machinery":"The load-bearing object is the permutation representation of G/PKer(G) on the non-Abelian simple factors of the socle, which has degree O(log n); here PKer(G) is the kernel of the conjugation action on those factors. The representation reduces isomorphism of Fitting-free groups to Twisted Code Equivalence, a variant of linear code equivalence in which coordinate permutations are accompanied by symbol twists from fixed groups, between codes of total length O(log n). The paper shows that the standard parallel Coset Intersection procedure, the structure-tree enumeration of small-domain transitive permutation groups, and the Twisted Code Equivalence dynamic program can all be implemented by uniform AC circuits of depth poly(log log n) with polynomial size. For the FO theorem, the mechanism is a count-free Weisfeiler–Leman pebble game, a color-refinement game that characterizes first-order logic without counting; because each non-Abelian simple factor has a generating set of seven elements with O(log n)-length words, Spoiler can pebble seven column products and O(log log n) binary-search products across the direct factors, forcing Duplicator's responses to pin down each factor and each element.","core_discovery":"The central discovery is that the group-theoretic structure of Fitting-free groups—specifically the small permutation representation obtained by letting G act on the non-Abelian simple factors of its socle and factoring out the kernel PKer(G)—converts the isomorphism problem into an instance of Twisted Code Equivalence of total length O(log n). Starting from the multiplication table, the paper implements each subroutine of the previous polynomial-time algorithm, including the standard parallel Coset Intersection procedure and the structure-tree machinery, with AC circuits of depth poly(log log n), and it solves the resulting code-equivalence instance in additional depth O($log^{2}$ n · poly(log log n)). The matching hardness direction embeds any binary linear code C into a group G_C = $π^{{-1}}$(C) inside a wreath product of alternating groups, so that code equivalence becomes group isomorphism; because this embedding is $AC^{0}$-computable and the group is Fitting-free, Graph Isomorphism and Linear Code Equivalence reduce to the permutation-generator version. The descriptive-complexity result asserts that O(log log n) variables suffice in first-order logic without counting, by pebbling seven short-word generators per simple factor and using a binary-search strategy on the number of socle factors to force Duplicator to match factors and then elements.","pith_inferences":["If the FO proof is repaired, the same binary-search pebbling strategy may identify any group whose socle is a direct product of non-Abelian simple groups even when the group is not itself Fitting-free, because the argument never uses the quotient beyond the unique-extension lemma.","The AC^3 algorithm's depth is dominated by the Twisted Code Equivalence solver; replacing that subroutine by a group-theoretic normalizer computation could plausibly lower the bound toward AC^1 or L, which the paper leaves open.","The hardness construction produces groups of order about 240^n from codes of length n, so the right parameter for the permutation-group problem may be the number of simple factors rather than the order; testing isomorphism of Fitting-free groups with few simple factors might still be tractable.","A natural testable extension is to check whether the O(log log n) variable bound holds for count-free WL Version II as well as Version I, since the paper's remark on the socle being O(log log n)-generated suggests a generator-socle route that may generalize."],"forward_implications":["If Theorem 1.1 is right, Fitting-free group isomorphism in the multiplication-table model moves from polynomial time down to AC^3, giving one of the strongest known parallel upper bounds for a class that is a bottleneck for general group isomorphism.","Because Lemma 7.11 decides Fitting-freeness in AC^0, the same circuit family can both certify membership in the class and solve isomorphism for all inputs.","The AC^0 reduction from Linear Code Equivalence means a polynomial-time algorithm for Fitting-free permutation-group isomorphism would imply the same for Linear Code Equivalence; in particular, the practical permutation-group approach cannot have a polynomial worst case unless code equivalence does.","The O(log log n)-variable FO identification directly contrasts with infinite families of Abelian groups that require O(log n) variables, so variable count separates these two natural classes.","Corollary 9.4 gives an ∃^{log n log log n} FOLL decision procedure for isomorphism between a Fitting-free group and an arbitrary group, simulated by quasiFOLL circuits of size n^{O(log log n)}."],"supporting_citations":[{"why":"Supplies the polynomial-time isomorphism test for Fitting-free groups that this paper parallelizes, and the reduction to Twisted Code Equivalence that the AC^3 algorithm implements.","marker":"[BCQ12]"},{"why":"Gives the full proofs of the structure-tree enumeration, permutational isomorphism, and Twisted Code Equivalence procedures that the parallel algorithm adapts.","marker":"[Cod11]"},{"why":"Provides the parallel Coset Intersection procedure whose recursive depth analysis yields poly(log log n)-depth circuits on small domains.","marker":"[Luk99]"},{"why":"Provides the NC permutation-group toolkit (order, membership, stabilizers, Schreier generators) that runs in FOLL^{O(1)} when the domain has size O(log n).","marker":"[BLS87]"},{"why":"Establishes the diagonal-product framework for isomorphisms of socles and the code-equivalence connection that both the AC^3 algorithm and the hardness construction rely on.","marker":"[BCGQ11]"},{"why":"Provides seven generators per non-Abelian simple factor with word length O(log |S|), which keeps the FO pebbling strategy within O(log log n) rounds.","marker":"[BKL89]"},{"why":"Supplies the reduction from Graph Isomorphism to Linear Code Equivalence over F2 that the permutation-group hardness result composes.","marker":"[PR97]"},{"why":"Gives the L-computable socle decomposition into non-Abelian simple factors used by the algorithm, and the Abelian-group lower bound that the FO result contrasts with.","marker":"[GL23b]"}],"fun_headline_variants":["Fitting-free group isomorphism: AC^3 tables, GI-hard generators","Small-depth AC^3 isomorphism for Fitting-free groups; permutation case is GI-hard","Fitting-free groups: AC^3 isomorphism from tables, GI-hard from permutations","Fitting-free groups identified by O(log log n) first-order variables"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The FO-identification theorem rests on Lemma 9.12(a), which asserts that a Duplicator response that places a socle element in the wrong direct factor can be punished by Spoiler in O(1) extra pebbles and O(log log n) extra rounds; if that factor-isolation guarantee fails, the O(log log n) variable bound does not follow from the submitted proof.","fun_headline_variants_meta":{"raw":{"variants":["Fitting-free group isomorphism: AC^3 tables, GI-hard generators","Small-depth AC^3 isomorphism for Fitting-free groups; permutation case is GI-hard","Fitting-free groups: AC^3 isomorphism from tables, GI-hard from permutations","Fitting-free groups identified by O(log log n) first-order variables"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001105,"raw_usage":{"total_tokens":4673,"prompt_tokens":1080,"completion_tokens":3593,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":3509}},"tokens_in":696,"tokens_out":3593,"duration_ms":24252,"temperature":1.0,"reasoning_tokens":3509,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:49:55.438181+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The FO claim would be settled by running the count-free WL Version I pebble game with O(log log n) pebbles on candidate pairs of Fitting-free groups; in particular, checking the factor-swap configuration in $G = H = A_5 \\times A_5$ tests Lemma 9.12(a), since if Duplicator can survive with the swapped response, the proof of Theorem 9.1 collapses even though the theorem itself might still hold via a different argument.","supporting_citations":[],"review_version":1}