{"id":"8909f99d-6709-4b32-b876-41a11f79e6ee","arxiv_id":"2502.02389","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Imposing exponentially small identification errors removes the superlinear message growth of deterministic identification and yields linear rates governed by the Minkowski dimension of the channel output set.","lead":"This paper studies how many messages can be identified through a noisy channel when identification mistakes must be extraordinarily rare. It finds that forcing errors to shrink exponentially changes the growth of identifiable messages from slightly superlinear back to linear, with rates tied to the geometric dimension of the channel's output set.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Converse of Theorem 9 proves the 1/2 dM bound only for bad exponent subsets, while the capacity supremum in Eq. (44) ranges over all slowly vanishing exponent sequences; the recovery proof needs an additional argument.","rationale":"The paper's core finite-block-length bounds appear coherent: the packing construction with entropy-typical tests and the covering converse using fidelity/total-variation inequalities check out, and the small-exponent expansions of Corollaries 6 and 8 are consistent. The finite-output restriction is explicitly stated and is necessary for finite packing/covering numbers, so the abstract's 'arbitrary memoryless channels' is broader than the theorems prove, but this does not invalidate the stated results. The most serious concern is the proof of Theorem 9's converse. There, the authors use the bad-subset bound (41) to upper-bound a capacity that is defined as a supremum over all slow-vanishing exponent functions. Because the maximum code size is monotone in the exponents, controlling only a selected bad subset is insufficient unless one shows that any admissible exponent sequence can be replaced or dominated by one in such a subset without reducing the resulting rate. The text does not provide this argument, and the claim that Eb contains E1(n)=E2(n)=C/n is not established. Thus the recovery of the pessimistic linearithmic capacity from [17] is not fully justified by the submitted proof. The reader's conditional verdict is appropriate, though the central concern here differs from the finite-output overclaim; both should be addressed in a revision.","tokens_in":27873,"tokens_out":28137,"duration_ms":306680,"concrete_test":"Re-derive the converse of Theorem 9 for an arbitrary admissible exponent sequence, e.g., E(n)=n^{-a} with 0<a<1, using only Theorem 7 and the universal upper bound in Corollary 8, and compare the resulting liminf of R(n)/log n with (1/2)dM(√eX). In parallel, check whether the particular sequence E(n)=C/n used in the proof can be contained in some bad subset Eb satisfying Eq. (40); if for a finite-output fractal set with dM=0<dM=1 the covering-number ratio at radii sqrt(C/n) is bounded away from 0, while Eb must have limit dM, the step 'take Eb ∋ E1(n)=E2(n)=C/n' is unjustified and the recovery proof requires repair.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The main unproved step is in the converse half of Theorem 9, where the paper claims to recover the pessimistic linearithmic capacity bound ˙CDI(W) ≤ 1/2 dM(√eX). The proof invokes Eq. (41), an improved upper bound valid only when the error exponents E(n) lie in a 'bad' subset Eb such that the covering-number ratio tends to the lower Minkowski dimension. But the capacity in Eq. (44) is a supremum over all error-exponent functions E1(n), E2(n) with Ei(n)→0 and nEi(n)→∞. Since the maximum code size is monotone nonincreasing in the exponents, an upper bound for a specially selected Eb does not automatically bound the supremum over all admissible sequences. The proof asserts that one may take Eb ∋ E1(n)=E2(n)=C/n, but Eb is defined by the limit in Eq. (40), and nothing guarantees that the specific sequence C/n, or an arbitrary optimizing sequence, has that limit. Without a replacement or subsequence argument, the claimed 1/2 dM upper bound on the pessimistic capacity is not derived from the stated lemmas. This does not affect the fixed-positive-E bounds in Theorems 4 and 7, but it leaves the paper's claim to recover the pessimistic capacity result of [17] incomplete.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic identification (DI) over memoryless channels under the constraint that both identification error probabilities decay exponentially in the block length, with reliability exponents E1 and E2. The main results are finite-blocklength lower and upper bounds on the identification rate R(n) in terms of packing and covering numbers of the square-root output probability set sqrt(W(X)) (Theorems 4 and 7). For small exponents these bounds are expanded into asymptotic expressions involving the lower and upper Minkowski dimensions of sqrt(W(X)) (Corollaries 6 and 8). The paper claims that positive error exponents restore linear scaling of the identifiable message number, and that when the exponents vanish slowly the linearithmic capacity results of the authors' earlier paper [17] are recovered (Theorems 9 and 10). It also treats zero-dimensional output sets, asymmetric Stein/Sanov error regimes with an O(log log n) upper bound, and extends the bounds to classical-quantum and product-input quantum channels.","tokens_in":28147,"tokens_out":21801,"duration_ms":249633,"significance":"If the results hold, they provide a genuinely new finite-blocklength perspective on deterministic identification: the geometric packing/covering structure of the output probability set is separated from the error-exponent control, and the known superlinear rates are explained as a small-exponent phenomenon. The fixed-positive-exponent bounds in Theorems 4 and 7 are written out and internally consistent, and the extension to cq and quantum channels together with the zero-dimensional examples are useful additions. The main caveat is that the recovery of the pessimistic capacity upper bound in Theorem 9 is not fully justified as written; this is a load-bearing part of the claim to recover [17], but it appears repairable by a subsequence/monotonicity argument.","major_comments":[{"comment":"The converse half of Theorem 9 does not derive the claimed pessimistic capacity upper bound. Equation (41) is an improved upper bound that holds only for error-exponent sequences E(n) lying in the 'bad' set E_b defined by Eq. (40). However, the capacity in Eq. (44) is a supremum over all admissible sequences with E_i(n) -> 0 and n E_i(n) -> infinity. Since the maximum code size is monotone nonincreasing in the exponents, an upper bound for one specially selected E_b sequence does not automatically control the supremum over all admissible sequences; in particular, taking E_1(n)=E_2(n) >= C/n does not yield a bound for exponents smaller than that sequence, and the sequence C/n need not belong to E_b. A repair would require a subsequence argument: for an arbitrary admissible exponent sequence, one can choose n_k and an E_b-sequence with 1/n_k << E_b(n_k) <= E(n_k) (or <= C/n_k) and apply Eq. (41) on that subsequence to bound the liminf. As written, the claimed recovery of the bound Cdot_DI(W) <= (1/2) d_M(sqrt(eX)) is incomplete. The fixed-positive-exponent results in Theorems 4 and 7 and Corollaries 6 and 8 are not affected.","section":"Theorem 9, Section IV-A, Eqs. (40), (41), (44), (48)"}],"minor_comments":[{"comment":"The abstract states that the paper treats 'arbitrary memoryless channels', but Section I-A explicitly restricts the analysis to finite output alphabets Y for the rest of the paper. The abstract should be aligned with the proved scope, or the finite-output assumption should be stated there.","section":"Abstract and Section I-A"},{"comment":"The proof of Theorem 15 requires a uniform margin lambda_{1,2} < 1 - delta/2 for a fixed delta > 0 when passing from the original channel W to the truncated channel V. The theorem statement only says lambda_1 < 1 in the Stein regime (and lambda_2 < 1 in the Sanov regime), which does not exclude sequences with lambda_1(n) -> 1. Please state explicitly that the bounded error is assumed to be uniformly bounded away from 1 by a positive constant, or provide an additional argument for the case where the bounded error approaches 1.","section":"Section V, Theorem 15, Eqs. (82)-(90)"},{"comment":"In the paragraph after Eq. (88), the sentence 'Therefore, any DI code for V in the Stein error regime is a code for W...' appears to state the reverse of the implication needed for the upper bound. The inequalities in Eqs. (84)-(88) show that a code for W is also a code for V with slightly larger errors, which is the direction required to upper-bound N_W by N_V; the text should be corrected to avoid confusion.","section":"Section V, proof of Theorem 15"},{"comment":"There are several typos and small presentation issues: 'realted' in Section III-C, 'Ann Harbor' in the header should be 'Ann Arbor', 'For the converse can we take' in the proof of Theorem 10 should be 'For the converse we can take', and the abstract phrase 'a certain parametrisation the channel output set' is missing an 'of'. These do not affect the mathematics.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is substantial and the main fixed-exponent results are credible. The incomplete argument in Theorem 9 is localized and likely repairable with the subsequence/monotonicity argument sketched in the report, so I would not recommend rejection. The other points are clarity issues. Please ensure the final version states the finite-output scope accurately and clarifies the Stein/Sanov assumptions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers a real result: for deterministic identification over finite-output channels, requiring both error probabilities to decay exponentially with positive exponents kills the linearithmic scaling and restores linear scaling. The rate-reliability bounds in Theorems 4 and 7 are new and seem correct; the asymptotic expansion via Minkowski dimension is elegant and gives a clean geometric explanation for the earlier Theta(n log n) capacities. The extension to one-sided error regimes (Stein/Sanov) is also interesting, even if the O(log log n) upper bound may be loose.\n\nThe main proofs are written out and internally consistent. The packing/covering arguments are standard but carefully done, and the recovery of [17] in the optimistic direction (Theorem 10) checks out.\n\nThere are soft spots. The abstract overstates the scope by saying \"arbitrary memoryless channels\" while the paper assumes Y finite from Section I-A onward; that is a minor mismatch but should be qualified. More importantly, the converse half of Theorem 9 has a gap. The proof uses the \"bad\" subset Eb and asserts that E1=E2=C/n lies in it. But Eb is defined by a limit condition that C/n need not satisfy. Since the pessimistic capacity is a supremum over all slowly vanishing exponent sequences, an upper bound for a specially selected Eb does not bound the supremum. One can compare any admissible E(n) to C/n eventually because nE(n) tends to infinity, but the bad-subset bound does not apply to C/n unless C/n is in Eb, and nothing guarantees that. So the claimed recovery of the 1/2 dM upper bound is not established by the stated lemmas. This does not affect Theorems 4, 7, or the positive-exponent linear scaling, but it means the paper's claim to recover the pessimistic capacity result of [17] is incomplete. The authors should supply a subsequence or replacement argument.\n\nAlso, the Section V channel approximation has loose constants, and the O(log log n) bound is acknowledged as possibly an artifact; that is acceptable as an upper bound but should be labeled more carefully.\n\nWho is this for: information theorists working on identification, finite-blocklength analysis, and geometric methods in IT. A serious referee should engage with it; the main results are new and the gap in Theorem 9 is fixable. I would ask for a revision rather than reject.","headline":"New rate-reliability results for deterministic identification are solid, but the claimed recovery of the pessimistic capacity bound has a gap that needs a fix.","tokens_in":28636,"tokens_out":5562,"would_cite":true,"duration_ms":54201,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A24","28A80","81P45"],"pacs":[],"model":"deepseek-v4-flash","headline":"Demanding exponentially small error probabilities in deterministic identification restores linear message growth, with the achievable rate set by the Minkowski dimension of the channel's square-root output set.","keywords":["deterministic identification","rate-reliability function","error exponents","Minkowski dimension","packing and covering numbers","linearithmic scaling","memoryless channels","classical-quantum channels"],"falsifier":"For a fixed channel with known Minkowski dimension d_M of sqrt(W(X)), set E1 = E2 = E and compute the maximum rate for block length n, either from an exhaustive search on a small alphabet or from an optimized code construction; if it exceeds the covering-number bound of Theorem 7 the converse fails, and if it falls below the packing bound of Theorem 4 for all sufficiently large n the achievability claim fails. A cleaner test in the small-exponent regime is to measure the slope of R(n)/log(1/E) as E tends to 0 for a one-dimensional output set and check whether it lies between d_M/4 and d_M/2.","tokens_in":27685,"feed_emoji":"🎯","tokens_out":7235,"duration_ms":72298,"temperature":0.7,"pith_summary":"This paper studies deterministic identification, the task in which a receiver checks whether the transmitted message equals one particular message of interest rather than decoding it. For channels with a finite output alphabet, it claims that if both error probabilities must vanish exponentially in the block length, with exponents E1 and E2, then the number of identifiable messages grows only linearly with n, and the rate is a function of the exponents. The central quantitative claim is that this rate is sandwiched between about (1/4)d_M log(1/min{E1,E2}) and (1/2)d_M log(1/min{E1,E2}), where d_M is the Minkowski dimension of the square-root output probability set. That means the earlier superlinear (n log n) identification rates survive only when the exponents tend to zero slowly, and it explains those rates as a geometric, not a purely combinatorial, phenomenon. The paper also shows that requiring only one of the two errors to be exponentially small still destroys the superlinear regime, and it extends the bounds to classical-quantum channels.","feed_headline":"Exponentially small errors kill superlinear identification rates","feed_subtitle":"Deterministic identification's n log n boost survives only when both error probabilities vanish slowly.","key_machinery":"The load-bearing object is the square-root output probability set $\\sqrt$(W(X)) = {$\\sqrt$(W_x) : x in X}, a subset of the non-negative orthant of the unit sphere in R^Y; the paper works in the Euclidean metric on this set. The rate bounds are expressed through the packing number Π_delta, the maximum number of pairwise disjoint delta-balls, and the covering number Γ_delta, the minimum number of delta-balls needed to cover the set, whose log-growth rates as delta approaches 0 define the lower and upper Minkowski dimensions. The coding argument selects letter-wise Euclidean packings of $\\sqrt$(W(X)) and combines them with Hamming-distance separation and conditional typical sets as identification tests, while the converse partitions the input space into covering balls and shows that no two code words can share a ball.","core_discovery":"The paper's central discovery is that the rate-reliability function for deterministic identification is controlled by packing and covering numbers of the set $\\sqrt$(W(X)) = {$\\sqrt$(W_x) : x in X} in the unit sphere of R^Y. Theorem 4 shows a code can achieve rate at least (1-t) log Π_{4th-root(6E/$ct^{2}$)}($\\sqrt$(W(X))) minus entropy and lower-order terms, while Theorem 7 shows any code with error exponents at least E has rate at most log Γ_{1/2 $\\sqrt$(1-$e^{{-E/2}}$)}($\\sqrt$(W(X))). In the asymptotic small-exponent limit, Corollaries 6 and 8 convert these into the sandwich (1/4)d_M log(1/min E) <= R <= (1/2)d_M log(1/min E). Letting E(n) tend to 0 slowly, with omega(1/n) <= E(n) <= o(1), recovers the prior linearithmic capacity bounds 1/4 d_M <= C_DI <= 1/2 d_M. For zero-dimensional output sets, such as a Bernoulli channel whose input set accumulates at a point, the relevant scale becomes n log log n, with capacity 1.","pith_inferences":["Read constructively, the factor-four gap between the 1/4 and 1/2 constants suggests that the true constant may be found by improving either the typical-set packing code or the covering converse; the paper's own discussion of Gaussian channels already points in that direction.","A testable consequence of the sandwich is that for E1 = E2 = E the ratio R(E)/log(1/E) should be asymptotically independent of n but channel-dependent through d_M, so plotting the finite-blocklength bounds for a one-dimensional output set could reveal which constant is approached.","The finite output alphabet assumption is the main scope limitation: for continuous output alphabets one would expect the same picture only if an analogous metric entropy for sqrt(W(X)) is finite, and the paper's results do not by themselves cover that case.","One-sided error regimes may behave very differently depending on zero-probability structure: the O(log log n) bound could be loose, and the authors leave open whether linearithmic rates are possible for cq-channels in the Stein regime."],"forward_implications":["For any finite-output memoryless channel, a DI code with exponentially small errors of both kinds cannot identify more than about 2^{((1/2)d_M log(1/E))n} messages, while at least about 2^{((1/4)d_M log(1/E))n} messages are always possible for small E.","The linearithmic capacity bounds of the earlier dimension-based theory follow as a limit of the new finite-blocklength bounds, with the lower and upper Minkowski dimensions playing the pessimistic and optimistic roles.","If only one error probability is forced to vanish exponentially, the linearithmic regime is lost as well: the rate is at most O(log log n) in general and O(1) when all output probabilities are bounded away from zero.","For zero-dimensional output probability sets, the relevant scale shifts from n log n to n log log n, as illustrated by a Bernoulli channel with inputs accumulating at zero.","The same packing and covering bounds extend to classical-quantum channels and to general quantum channels restricted to product-state inputs, with the Euclidean metric replaced by the Hilbert-Schmidt distance."],"supporting_citations":[{"why":"Supplies the dimension-based linearithmic capacity bounds and the typical-set lemmas that the coding and converse proofs build on.","marker":"[17]"},{"why":"Establishes the first linear and linearithmic deterministic identification results over Gaussian and power-constrained channels, providing the DMC capacity example recovered in Example 12.","marker":"[9]"},{"why":"Introduces identification via channels and the two-error formulation that defines the problem studied here.","marker":"[5]"},{"why":"Shows that deterministic identification without randomization gives only linear scaling for DMCs, the baseline the rate-reliability results refine.","marker":"[8]"},{"why":"Provides the definitions and properties of packing, covering, and Minkowski dimension used to turn the geometric bounds into dimension bounds.","marker":"[22]"},{"why":"Supplies the relation between hypothesis-testing and Rényi relative entropies used in the asymmetric Stein and Sanov converses.","marker":"[28]"}],"fun_headline_variants":["Exponential errors restore linear ID rates","Tight errors strip superlinear gain from deterministic ID","Rate-reliability tradeoff: exponential errors kill n log n","When errors vanish fast, ID rate scales linearly, not n log n","Positive error exponents trade rate for reliability in ID"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Throughout the paper the output alphabet Y is assumed finite, so sqrt(W(X)) is a bounded subset of a finite-dimensional sphere; all packing, covering, and Minkowski-dimension arguments depend on this, and the abstract's phrase 'arbitrary memoryless channels' reaches beyond what is actually proved.","fun_headline_variants_meta":{"raw":{"variants":["Exponential errors restore linear ID rates","Tight errors strip superlinear gain from deterministic ID","Rate-reliability tradeoff: exponential errors kill n log n","When errors vanish fast, ID rate scales linearly, not n log n","Positive error exponents trade rate for reliability in ID"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000263,"raw_usage":{"total_tokens":1649,"prompt_tokens":1046,"completion_tokens":603,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":662,"completion_tokens_details":{"reasoning_tokens":524}},"tokens_in":662,"tokens_out":603,"duration_ms":5961,"temperature":1.0,"reasoning_tokens":524,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T12:20:24.716143+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a fixed channel with known Minkowski dimension d_M of sqrt(W(X)), set E1 = E2 = E and compute the maximum rate for block length n, either from an exhaustive search on a small alphabet or from an optimized code construction; if it exceeds the covering-number bound of Theorem 7 the converse fails, and if it falls below the packing bound of Theorem 4 for all sufficiently large n the achievability claim fails. A cleaner test in the small-exponent regime is to measure the slope of R(n)/log(1/E) as E tends to 0 for a one-dimensional output set and check whether it lies between d_M/4 and d_M/2.","supporting_citations":[{"cited_title":"Deterministic identification over channels with finite output: A dimensional perspective on superlinear rates,","cited_arxiv_id":null,"evidence_quote":"Supplies the dimension-based linearithmic capacity bounds and the typical-set lemmas that the coding and converse proofs build on."},{"cited_title":"Identification via channels,","cited_arxiv_id":null,"evidence_quote":"Introduces identification via channels and the two-error formulation that defines the problem studied here."},{"cited_title":"Identification without randomiza- tion,","cited_arxiv_id":null,"evidence_quote":"Shows that deterministic identification without randomization gives only linear scaling for DMCs, the baseline the rate-reliability results refine."},{"cited_title":"Falconer, Fractal Geometry: Mathematical Foundations and Applications (3rd ed.) Wiley & Sons, 2014","cited_arxiv_id":null,"evidence_quote":"Provides the definitions and properties of packing, covering, and Minkowski dimension used to turn the geometric bounds into dimension bounds."},{"cited_title":"Strong Con- verse Exponents for a Quantum Channel Discrimination Problem and Quantum-Feedback-Assisted Communication,","cited_arxiv_id":null,"evidence_quote":"Supplies the relation between hypothesis-testing and Rényi relative entropies used in the asymmetric Stein and Sanov converses."}],"review_version":1}