{"id":"0fdc9386-3113-41da-88c3-f0b9c34c6ce0","arxiv_id":"2412.11091","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Identification capacity of the q-ary noisy permutation channel is (q-1)/2 for full-rank strictly positive noise, with matching achievability and strong converse up to log factors.","lead":"This paper determines how many messages can be identified when a transmitted string is randomly shuffled and then passed through a noisy memoryless channel. The answer, expressed as an identification rate, matches the ordinary communication capacity for full-rank noise, with gaps only when the noise matrix is rank-deficient.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Converse proof undercounts M-type quantizations: inequality (43) is algebraically false for q≥2, and with the M_i required by Proposition 2 the number of quantized distributions exceeds the message count for q≥4, so the pigeonhole step—and Theorem 2(ii)—do not follow.","rationale":"The paper's central claim is Theorem 2(ii), the strong converse for stochastic encoding at the stated message sizes. The proof of that theorem rests on a channel-resolvability argument whose final pigeonhole step requires the number of M-type quantizations to be smaller than the number of messages. I checked the counting chain (41)–(43) and found a concrete algebraic error: the factor (q-1) is dropped, and the inequality (43) would require 1+log n ≤ log n, which is impossible. With the M_i value actually needed for the quantization error to vanish (as fixed by Proposition 2 and equation (135)), the crude upper bound |N|^{M_i} has exponent (q-1)c_i n^{(q-1)/2}(log n)^{1+A}, already larger than the message exponent for q≥2; the more accurate binomial count still exceeds the message count for q≥4. Thus the converse does not follow for general q. The reader's stated weakest assumptions (Lemma 4/11 rate, Lemma 14 endpoint, and stochastic-decoder versus deterministic proof) are real but secondary: Lemma 14's proof appears typo-fixable, and the decoder mismatch can be repaired by restricting the statement. The counting flaw is not a minor fix—it indicates the proposed quantization/resolvability framework cannot support the claimed strong converse at the stated exponent for q≥4. The achievability part (Theorem 2(i)) and the deterministic results (Theorem 3) appear structurally independent of this flaw, so the paper contains partial value, but the main stochastic-encoding converse is not established.","tokens_in":40759,"tokens_out":30355,"duration_ms":216124,"concrete_test":"Recompute the counting step for q=4, n=10^6, c_n = log log n, with M_i = c_n n^{3/2} (log n)^3 and |N_{4,n}| ≈ n^3/6. Use the exact number of M_i-type distributions, binom(M_i+|N|-1, |N|-1) ≤ (e(|N|+M_i)/|N|)^{|N|}, or for M_i << |N| use (e|N|/M_i)^{M_i}. Compare log_2 of this count with the message size exponent log_2 L = c_n n^{3/2} (log n)^4. If log_2(count) > log_2 L, the pigeonhole step fails. Algebraically, verify that (43) requires (q-1)(1+log n) ≤ log n; for any q≥2 this is false, so the inequality as written cannot be repaired by adjusting constants.","verdict_should_be":"REJECT","load_bearing_attack":"Section VI, proof of Theorem 2(ii), equations (41)–(43). Proposition 2 forces M_i = c_i n_i^{(q-1)/2} (log n_i)^{(q-1)(q-2)/2} to make the quantization error δ_i vanish (see (135) and (38)–(40)). The number of M_i-type distributions on N_{q,n_i} is at most |N_{q,n_i}|^{M_i} ≤ ((2n_i)^{q-1})^{M_i} = 2^{(q-1) M_i (1+log n_i)} = 2^{(q-1) c_i n_i^{(q-1)/2} (log n_i)^{(q-1)(q-2)/2} (1+log n_i)}. Inequality (43) claims this is ≤ 2^{c_i n_i^{(q-1)/2} (log n_i)^{1+(q-1)(q-2)/2}}, which would require (q-1)(1+log n_i) ≤ log n_i — false for every q≥2 and all large n_i. The factor (q-1) is dropped between (41) and (42). Even using the sharper binomial count for M-type distributions, log(#M-types) ≈ ((q-1)/2) c_i n_i^{(q-1)/2} (log n_i)^{1+A}, which for q≥4 exceeds the message-size exponent c_i n_i^{(q-1)/2} (log n_i)^{1+A}. Hence there are more quantized distributions than messages; two messages are not forced to share the same M-type distribution, and the key inequality d_TV(Q_op,j,Q_op,k) ≤ 2δ_i for some j≠k is not obtained. The strong converse for all q≥2 is therefore unproven. This is distinct from the Lemma 14 endpoint issue and the stochastic-decoder mismatch, and it strikes at the central claim of the paper.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies message identification over q-ary noisy permutation channels, where an input vector is uniformly permuted and then passed through a DMC with strictly positive transition probabilities. The main claims are: (i) for any ε_n→0, codes with 2^{ε_n(n/log n)^{(r-1)/2}} messages can be identified with vanishing errors, where r is the rank of the DMC; (ii) for full-rank strictly positive U, any code with roughly 2^{c_n n^{(q-1)/2}(log n)^{1+(q-1)(q-2)/2}} messages and c_n→∞ has Type-I plus Type-II error at least 1 asymptotically, giving identification capacity (q-1)/2; and (iii) analogous achievability and converse statements for deterministic encoders. The proof introduces a q-ary noisy composition channel (q-NCC) and a two-stage deterministic quantization scheme that approximates input distributions by M-type distributions while controlling the total-variation distortion of the output distributions. The paper also contains supporting sensitivity bounds for multinomial distributions and a packing argument for the deterministic-encoder converse.","tokens_in":41045,"tokens_out":22972,"duration_ms":195381,"significance":"If the results are correct, they settle the identification capacity of noisy permutation channels with full-rank strictly positive DMCs and give tight exponents up to log factors for general rank. The identification-size exponents and the proposed channel-resolvability-style converse are nontrivial, and the two-stage quantization of composition distributions is an interesting technique that could be reused. The paper is also honest about the gap between achievability and converse when U is rank-deficient. However, several load-bearing steps in the current manuscript are not yet established: the pigeonhole counting in the strong converse contains a false inequality, the strong-converse proof is written for deterministic decoders while the theorem states stochastic decoders, and Lemma 1 is asserted without proof. These issues are fixable in principle, but they prevent the main converse claim from being accepted as written.","major_comments":[{"comment":"The counting step in the pigeonhole argument is algebraically wrong. Since |N_{q,n_i}| ≤ (2n_i)^{q-1}, the logarithm of the crude M-type count is (q-1)M_i(1+log n_i), not M_i(1+log n_i). With M_i = c_i n_i^{(q-1)/2}(log n_i)^{(q-1)(q-2)/2} as used in (135), this is (q-1)c_i n_i^{(q-1)/2}(log n_i)^{1+(q-1)(q-2)/2}(1+o(1)), which is a factor (q-1) larger than the message-size exponent in Γ_i. Hence the transition from (41) to (43) drops the factor (q-1), and the claimed inequality is false for every q≥2 and all large n_i. Even replacing the crude bound by the exact count binom(M_i+|N_{q,n_i}|-1, |N_{q,n_i}|-1) of M-type distributions does not rescue the argument as written: for q≥4 the leading exponent is ((q-1)/2)c_i n_i^{(q-1)/2}(log n_i)^{1+(q-1)(q-2)/2}, which still exceeds the message exponent. The conclusion in (44) that two messages share the same quantized distribution therefore does not follow, and Theorem 2(ii) is not proved. This is load-bearing; a correction requires either a smaller scaling of M_i that still tends to infinity so that δ_i vanishes, or a substantially sharper count with the constants aligned.","section":"Section VI, Eqs. (41)–(43)"},{"comment":"Theorem 2(ii) is stated for identification codes with stochastic decoders, but the proof in Section VI begins by considering 'a sequence of ... ID codes with deterministic decoders', and Lemma 2 is proved only for deterministic decoders. The reduction from a stochastic decoder for Σ_{n,U} to a stochastic decoder for q-NCC is not supplied. The gap is likely fixable by averaging the stochastic decision rule over each output type class, i.e. defining P_i'(1|w) = (1/|C_w|)∑_{y∈C_w} P_i(1|y), and checking that the error expressions coincide, but this extension must appear in the paper for the stated theorem to be covered by the proof.","section":"Section VI and Lemma 2"},{"comment":"Lemma 1 is asserted without proof. The cited capacity theorem of [21], [34] identifies the reliable-communication capacity in the asymptotic rate sense, which alone gives message sizes n^{(r-1)/2-o(1)}, not the precise scale (n/(c log n))^{(r-1)/2} with a logarithmic loss. This exact scale is used in the exponents of Theorems 2(i) and 3(i), so the achievability results are conditional on an unproved refinement. The paper should either give a proof of Lemma 1 or cite a result that proves exactly this statement.","section":"Section III, Lemma 1"},{"comment":"In the transition from an odd slice x to the next slice x+1, the next slice is traversed in reverse order by construction, so the first element of slice x+1 is the endpoint g^{(m-1,s-x-1)}(|V|), not the start g^{(m-1,s-x-1)}(1) used in (106)–(107). With the printed formulas, for example m=2, s=5, x=1, the two consecutive points differ by (1,-3) in L1 norm, violating the adjacency conditions (92)–(93). This invalidates the bound (94) and hence the distortion estimate (130) that depends on it. The lemma itself is plausible and the error appears local, but the proof must be corrected before Proposition 2 can be used.","section":"Section IX-C, proof of Lemma 14, Case I"}],"minor_comments":[{"comment":"The constants C_4, C_4^1, and C_1^4 are used inconsistently; please unify the notation for the constants appearing in Proposition 2 and in the proof of that proposition.","section":"Notation throughout"},{"comment":"The abstract writes message sizes as 2^{R_n(n/log n)^{(r-1)/2}}, while Theorem 2(i) uses ε_n in place of R_n and the converse uses c_i; please align the notation.","section":"Abstract and Section IV"},{"comment":"The definition of ε'_n includes the terms 1/N and 1/(N log N), but the subsequent lower bound for L appears to neglect the subtraction of 1+log N in the exponent; the algebra should be checked.","section":"Section V, Eq. (23)"},{"comment":"The displayed chain 'L ≥ 2^{ε'_n N -1-\\log N} = 2^{ε_n N (r-1)! c^{(r-1)/2}} = 2^{ε_n(n/\\log n)^{(r-1)/2}}' drops a factor (r-1)! in the last equality; as a lower bound the inequality direction is harmless, but the equality is not exact.","section":"Section V"},{"comment":"There is a typo in the final sentence of Lemma 2: 'determnistic' should be 'deterministic'.","section":"Lemma 2"}],"recommendation":"major_revision","confidential_remarks":"In my assessment the main claims are likely true and the gaps are repairable, but the false counting inequality in the strong converse is serious: as written it breaks the pigeonhole step for all q≥2 and is not rescued by the exact M-type count for q≥4. I would ask the authors to repair the pigeonhole step, extend Lemma 2 to stochastic decoders, supply the proof of Lemma 1, and correct the endpoint error in Lemma 14. Once these points are fixed, the paper would be a solid contribution to identification theory over permutation channels."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The main converse doesn't go through as written. Inequality (43) is false: substitute M_i from (135) into (42), and you get an extra factor (q-1) on the left that the right side cannot absorb. So the pigeonhole step that forces two messages to share the same quantized M-type distribution is not available, and Theorem 2(ii) is unproven for q≥4 and likely for q=3 as well. This is a load-bearing gap, not a typo. The stochastic-decoder mismatch (statement says stochastic decoders, proof only develops deterministic decoders) and the unproved Lemma 1 log-factor refinement are secondary, and Lemma 14's endpoint calculation also looks inconsistent.\n\nWhat's genuinely new and worth credit: the q-NCC reduction and the two-stage deterministic M-type quantization scheme. That quantization idea is a real technical contribution, even if its application here is compromised. The achievability (Theorem 2(i)) is standard — reliable code plus Ahlswede–Dueck — and likely correct. The deterministic encoding results in Theorem 3 have a clean packing argument and may survive intact. The multinomial sensitivity bounds (Lemmas 3, 4, 11) are carefully derived and appear solid.\n\nThe paper is for permutation-channel and identification-theory researchers. It deserves a serious referee because the problem is real and the toolkit is promising, but the current version should not be accepted. The gap may be fixable, e.g. with a finer count of M-types (the sharper binomial count might rescue q=2 and q=3) or by adjusting the message-size exponent, but that is a substantial revision.\n\nIf I were the editor, I would send it to review with a clear instruction to check the pigeonhole count, and flag the decoder mismatch and missing Lemma 1 proof. I would not desk-reject it, but I also would not let the current proof through.","headline":"The strong converse in Theorem 2(ii) rests on an algebraically false pigeonhole bound; the central claim is unproven as written, though the achievability and deterministic results look salvageable.","tokens_in":41682,"tokens_out":10092,"would_cite":false,"duration_ms":69322,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A24","94A15","60C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The number of messages identifiable over a shuffled noisy channel grows at a rate set by the rank of the noise matrix, and for full-rank noise a strong converse matches it.","keywords":["identification via channels","noisy permutation channel","q-ary composition channel","channel resolvability","M-type distributions","strong converse","total variation distance","multinomial distributions"],"falsifier":"Compute $d_{TV}(W_{(x,a)},W_{(x,b)})$ for a concrete strictly positive $U$ and $q=3$ at large finite $n$; if the decay is slower than $C(\\log n)^{1/2}/\\sqrt{n}$, Lemma 4 fails. Separately, test Lemma 14 by evaluating its recursion for small $m$ and $s$: the final listed endpoint $(s-m+1,1,\\dots,1)$ must be adjacent to its predecessor in the Gray-like order, and the currently written endpoint calculation should be checked for that adjacency.","tokens_in":40424,"feed_emoji":"🔀","tokens_out":9084,"duration_ms":78030,"temperature":0.7,"pith_summary":"This paper asks how many messages can be identified, rather than reliably decoded, when a q-ary block is randomly permuted and then passed through a discrete memoryless channel U with strictly positive entries. The paper establishes that with stochastic encoding, the number of identifiable messages grows as $2^{\\epsilon_n (n/\\log n)^{(r-1)/2}}$ for any $\\epsilon_n\\to 0$, where $r$ is the rank of $U$. For full-rank $U$, it proves a matching strong converse: any sequence of codes with $2^{R_n n^{(q-1)/2}(\\log n)^{1+(q-1)(q-2)/2}}$ messages and $R_n\\to\\infty$ must have Type-I plus Type-II error probability approaching 1. This fixes the identification capacity of the full-rank noisy permutation channel at $(q-1)/2$, the same second-order growth rate as reliable communication over that channel. If true, it settles the identification picture for a channel class relevant to DNA storage and multipath routing.","feed_headline":"Shuffled noisy channels: rank sets identification size","feed_subtitle":"For full-rank noise the identification rate equals (q-1)/2; past that size, both error types must add to 1.","key_machinery":"The load-bearing object is the q-ary noisy composition channel, denoted q-NCC$_{n,U}$: its input and output alphabets are the set of compositions of n-length q-ary vectors, and its transition probability is the probability that a vector of composition t, after passing through the DMC U, has output composition w. The argument then runs through a deterministic two-stage quantization scheme: partition the composition simplex into cubic cells of side a, redistribute probability mass inside each cell so that all but one mass per cell become multiples of 1/M, and then sweep residual masses through the cells in a Gray-like order. This machinery approximates any input distribution by an M-type distribution whose output over the composition channel is within vanishing total-variation distance, which is exactly what channel resolvability needs to force a pigeonhole collision among codeword output distributions. The engine that makes the TV bound small is Lemma 4: moving one unit of mass between neighboring compositions changes the output distribution by at most $C(\\log n)^{(q-2)/2}/\\sqrt{n}$.","core_discovery":"The central discovery is that the composition of the transmitted block, the vector of symbol counts, is the only information that survives the permutation stage, and that this reduction exactly determines identification performance. The paper proves that an identification code for the noisy permutation channel is equivalent to an identification code for the q-ary noisy composition channel, whose inputs and outputs are compositions and whose transition law is the convolution of multinomials. On this reduced channel it shows that $2^{\\epsilon_n (n/\\log n)^{(r-1)/2}}$ messages are identifiable with vanishing error, and that for strictly positive full-rank $U$ any code family whose message size grows as $2^{R_n n^{(q-1)/2}(\\log n)^{1+(q-1)(q-2)/2}}$ with $R_n\\to\\infty$ has sum error probability approaching 1. The achievability and converse meet in identification rate, giving capacity $(q-1)/2$ for full-rank channels. The same framework also yields tight achievability and converse bounds for deterministic encoders and decoders, with message sizes of order $(n/(c\\log n))^{(r-1)/2}$ and converses at $R\\,n^{(q-1)/2}(\\log n)^{(q-1)(q-2)/2}$.","pith_inferences":["The same quantization plus pigeonhole strategy should yield a matching converse for rank-deficient $U$ if the output-perturbation bound can be made to depend on $r$ instead of $q$; the paper states this as an open problem and already phrases several lemmas for arbitrary rank.","For $q=2$, the main theorem reduces to a statement about Hamming-weight distributions under a bit-flip channel, and the quantization algorithm is fully explicit; one could numerically verify the $1/\\sqrt{n}$ sensitivity of the output Hamming-weight distribution as a binary shadow of the main claim.","The deterministic two-stage quantization scheme is a channel-dependent alternative to randomized resolvability, and it is natural to try the same cell-then-Gray-order construction for other channels whose output distributions are Lipschitz in small shifts of the input type.","Because the achievability and converse message sizes differ only by powers of $\\log n$, a finer second-order analysis could pin down the exact logarithmic exponents; the paper's multinomial tail bounds and convolution estimates are the ingredients such an analysis would need."],"forward_implications":["For strictly positive full-rank $U$, the identification capacity is exactly $(q-1)/2$: message sizes below $2^{\\epsilon_n(n/\\log n)^{(q-1)/2}}$ with $\\epsilon_n\\to 0$ are achievable, and larger sizes force the sum of both error probabilities to 1.","For rank $r