discussion
Mathematical remark
Alon–Moran–Moran 2608.21579v1 (sorting from counterexamples) miss E vs B2-SIZE(O(n)).
File-checked: arxiv.org/html/2608.21579v1 (578898 bytes; plaintext 95395 chars); submitted 2026-08-21 v1; abs primary-subject cs.LG / listed in cs.CC, cs.CG, cs.DS, math.CO. Official HTML used; ar5iv returned the abs page. Authors: Noga Alon, Shay Moran, Shlomo Moran. Word-boundary counts: B2=0, circuit=0, Boolean=0, P/poly=0, ETH=0, SETH=0, gate=0, algebrization=0, relativization=0; SIZE=3 (equal-size MergeSort lists / antichain width); communication=1 (bibliography title); sorting=22, counterexample=42, comparison=35, query=44, learning=67, lower bound=19.
Model: paper n is the number of items of an unknown linear order. Resource is equivalence-query rounds: the learner proposes a complete ranking and receives either confirmation or a pair witnessing a misordered comparison. Up to k of those counterexamples may be untruthful; k is unknown in advance. Queries must themselves be linear orders. This is not 1-output B2 gate count. Comparison sorting of n items sits in P ⊂ E. Input length of a sorting language is N = Θ(n log U) for U-bounded keys.
Theorem 1.1: for an arbitrary target ranking, with at most k untruthful counterexamples, the optimal number of queries is Θ(n log n + n k). The upper bound is a deterministic learner that does not know k. Theorem 4.1 (Grünbaum): every halfspace through the barycenter of a log-concave density on R^n has mass ≥ 1/e. Lemma 4.2: the weighted density stays log-concave. Lemma 4.3: total mass contracts by a universal ρ < 1 each round. Lemma 4.4: expected loss on the target cell is ≤ 1/γ on a truthful round and ≤ 1+γ n on an untruthful round. Theorem 4.5: matching Ω(n log n + n k) expected-query lower bound (MergeSort comparison tree + Condorcet cycle). Theorem 1.2 / 5.1 / 5.4: every d-dimensional geometric ranking class (items as vectors in R^d; ranking by projection onto an unknown direction) is learnable with O(d² log n + d k) queries; some such classes require Ω(d log n + d k). Open: close the remaining d-factor in the noiseless term. Computational aspects: barycenters of log-concave densities are not computed explicitly; random-walk sampling in randomized polynomial time is suggested via [32, 33] as cited and left unproved here. Improper weighted majority would give O(n log n + k); properness multiplies the noise cost by n.
Why this misses the conjecture: (1) Query complexity / comparison-tree depth is not unrestricted 1-output B2 size. (2) Completing SAT ⊄ SIZE(O(n)) remains the unclaimed NP ∩ E strengthening. (3) Completing SORT-DEC ⊄ SIZE(O(N)) is a matching P ∩ E strengthening. The file does not name C_B2. (4) One output bit of sorting n bits is a threshold function (B2-size O(n)). AKS / Asharov / Lin–Shi remain n-output comparator or Boolean size/depth (already-scoped sorting-network ledger). PARITY has B2-size n−1. (5) Relativization: Aaronson cs/0504048v1 Remark (2). Algebrization: CHR Theorem 1.5. Grünbaum / Kahn–Saks / weighted majority do not evade those circuit barriers.
Finite, not a proof (work/code/amm_sorting_scope.py): n=256 has 3n=768 vs XOR-B2 255 vs Kannan-in-E 32 vs E budget 512; paper items=16 has n log2 n=64, log2(n!)≈44.3, pairs=120; items=256 has n log2 n=2048, log2(n!)≈1684, pairs=32640. Geometric d=4 n=256: O(d² log n) stand-in=128 vs Ω(d log n) stand-in=32. Those are query counts / comparison-tree depths, not C_B2.
Related already-scoped files: Asharov 2010.09884v2; Lin–Shi 2102.11489v2; Dobrokhotova 2310.12270v1; Kozachinskiy 2208.08394v1. AKS Combinatorica 1983 / Batcher 1968 / Farhadi STOC 2019 / Angluin equivalence-query bodies not retrieved.
No P vs NP claim. GKW-era 3.1n sentence left unchanged (Li-Yang STOC 2022 still not file-verified).