{"id":"23dbffe0-295e-4acd-bc87-8f1b0ed8b214","arxiv_id":"2607.16966","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Min-entropy estimation over k symbols requires Θ(k log k) samples, and integer-order Rényi entropy over the same alphabet requires Θ(α k^{1−1/α}) samples for 2≤α≤c log k.","lead":"Entropy estimation is a basic statistical task, and this paper settles exactly how many samples it takes for two especially important entropy measures. Min-entropy needs about k times log k samples, and integer-order Rényi entropy needs about α times k^(1−1/α) samples, correcting a previously published bound.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the truncation step in Lemma 8.5, though the most delicate link, survives a careful uniformity check.","rationale":"The reader's weakest-assumption analysis correctly identifies the truncated-likelihood second-moment calculation as the least robust part of the Rényi lower bound. I examined this step in detail and found no error: the Poisson tail bound remains negligible even when α is just below an integer, and the second-moment bound is uniform over the claimed range. The min-entropy lower bound is exact and clean. The upper bounds are standard and carefully analyzed. The acknowledged use of ChatGPT does not affect the mathematical content, and the paper honestly states that the noninteger lower bound is not claimed to be sharp. Therefore the reader's ACCEPT verdict should stand without modification.","tokens_in":42994,"tokens_out":29274,"duration_ms":262009,"concrete_test":"Independently re-derive Lemma 8.5 for the worst-case α=m+δ with δ→0+ and τ=C*α, tracking the k^{1−(m+1)/α} factor explicitly; verify that the product (eC*)^{m+1} k^{1−(m+1)/α} remains ≤e^{−40(m+1)} and that the final S(h)/k bound stays below 10^{-6} for all α in [1.001, c0 log k].","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim rests on Theorem 8.1, whose proof hinges on Lemmas 8.4–8.5: the Poisson-tail cutoff at m=floor(α) and the truncated second-moment bound. If either failed for some corner of 1.001≤α≤c0 log k, the Ω(α k^{1−1/α}) lower bound would collapse. I checked the two potential corner cases. First, for α close to an integer from below, m+1−α can be arbitrarily small, so the factor k^{1−(m+1)/α} in the light-coordinate union bound is only ≤1, not necessarily o(1); however, the prefactor (eC*)^{m+1} is ≤e^{−40(m+1)} regardless, so the tail bound stays negligible. Second, in Lemma 8.5's middle range α/2<r≤m, the bound uses ρ log(D/ρ) ≤ 1/2 log(2D) ≤ −20 for ρ∈[1/2,1], which holds because D≤e^{−40}/2; the resulting term is ≤e^{−19α}, uniformly for α≥1.001. The r=0 and r≤α/2 ranges give k^{−7/8} and ≤k^{−3/8} contributions, uniformly. No corner regime breaks the argument. The de-Poissonization step and the TV triangle inequality through the ideal experiments are also internally consistent. Thus the identified delicate point is real but does not constitute a gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper determines the minimax sample complexity of estimating min-entropy and integer-order Rényi entropy over k-symbol alphabets to constant additive accuracy. It proves that min-entropy estimation requires Θ(k log k) samples, in contrast with Θ(k/log k) for Shannon entropy, and explains why the Valiant–Valiant relative-earthmover framework does not apply to min-entropy. For integer orders 2 ≤ α ≤ c0 log k it proves the matching fixed-accuracy rate Θ_{c0}(α k^{1−1/α}) by analyzing a falling-factorial collision estimator and a hidden-heavy-coordinate lower bound; for real orders 1.001 ≤ α ≤ c0 log k it proves the uniform lower bound Ω_{c0}(α k^{1−1/α}). It further transfers the min-entropy bounds to the sufficiently high-order regime α ≳ log k. The proofs use dyadic concentration for the empirical maximum (Section 4), a tuple-overlap variance decomposition for the collision estimator (Section 5), an exact χ² computation for the min-entropy lower bound (Section 7), and a Poissonized truncated likelihood-ratio argument for the Rényi lower bound (Section 8).","tokens_in":43365,"tokens_out":11187,"duration_ms":115954,"significance":"If the results hold, they close genuine gaps left by fixed-order notation. Previous work hid the α dependence in Θ_α(·), and the claimed Θ(k/log k) rate for min-entropy rested on an inapplicable theorem; the paper shows this explicitly with a concrete counterexample in Section 3.2. The main technical contributions are substantial: the dyadic grouping in Section 4 replaces a crude k-factor by 1/p⋆; the light–heavy split in Section 5.4 removes one factor of α relative to prior variance analyses; the exact χ² formula in Lemma 7.5 is a clean, checkable computation; and the hidden-heavy-coordinate construction with truncation at ⌊α⌋ in Section 8 is a novel way to obtain the linear α factor in the lower bound. The proofs are detailed, internally consistent, and derived from first principles, with explicit constants (e.g., C0 = 10^6 in Lemma 5.4). The paper also responsibly states its limitations: the noninteger lower bound is not claimed sharp, and the ε-dependence is not optimized. I see no circularity or unsupported reliance on prior work; Appendices A and B carefully extract the α-dependence from [1] and [2]. The paper is likely to be influential in property testing and information th","major_comments":[],"minor_comments":[{"comment":"Editorial: 'lower bound also hold' should be 'lower bound also holds'; 'non-integers' should be 'non-integer values'. These do not affect content.","section":"Abstract and Section 2"},{"comment":"The accuracy parameter is denoted ϵ in Section 8.1 but ε in Theorem 2.2 and Section 5. Unify the notation to avoid confusion, especially since the same symbol appears in the final bound n ≥ Cϵ α k^{1−1/α}/ε².","section":"§8.1 vs §2.2"},{"comment":"The line 'because ∀η: 2≤e^{−η}+e^η' is correct but terse. The inequality (2−e^{−η}) ≤ e^η follows immediately from e^η+e^{−η}≥2; a one-line expansion would improve readability.","section":"§5.4, Regime 1"},{"comment":"The notation conflict (Δ for accuracy, ε for confidence) is acknowledged in Section A.1, but the appendix remains hard to follow. Consider renaming the accuracy to ε_acc or ρ to align with the main text.","section":"Appendix A"},{"comment":"The noninteger lower bound is stated for fixed ε∈(0,1) with constants C_ε = c1 ε². The paper later notes that the ε-dependence is not optimized; this is fine, but the theorem statement in Section 8.1 could explicitly say that the bound is not claimed to be tight in ε.","section":"§9 and Remark 8.1"}],"recommendation":"accept","confidential_remarks":"To the editor: the only delicate point is the truncated second-moment argument in Lemma 8.5. I checked the two potential corner cases — α close to an integer from below (where k^{1−(m+1)/α} is only ≤1 but the prefactor (eC*)^{m+1} dominates) and the range α/2 < r ≤ m (where ρ log(D/ρ) ≤ −20 uniformly) — and found no gap. The de-Poissonization step and the TV triangle inequality through the ideal experiments are also consistent. No citation-pattern or novelty concerns; the appendices appropriately extract constants from prior work."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: this is a real result, not incremental. It corrects the previously claimed Θ(k/log k) for min-entropy to Θ(k log k), and it pins the growing-order dependence for integer Rényi orders as Θ(α k^{1−1/α}) up to α = c0 log k. The hidden-coordinate lower bound is the substantive novelty: it produces the extra log k for min-entropy and the factor α for Rényi entropy, and the truncated Poisson-likelihood calculation is genuinely different from the fixed-order two-point arguments.\n\nThe paper does several things well. The min-entropy upper bound via dyadic grouping of symbol probabilities is clean and gives the right 1/p* dependence. The exact χ2 computation for the min-entropy lower bound is elegant — you get a closed-form expression and the k log k emerges from balancing diagonal and off-diagonal terms. The Rényi upper bound is a careful variance analysis of the classical falling-factorial estimator, but exploiting the entropy-specific multiplicative window rather than relative error in the power sum is the right idea and provably removes one factor of α. The appendices extracting α-dependence from Acharya et al. and Obremski–Skorski are honest and make the improvement concrete: the prior lower-bound constant is independent of α, while the prior upper bound is O(α^2).\n\nThe soft spots are proportionate. The most delicate link is the truncation at floor(α) in the Rényi lower bound (Sections 8.5–8.6). If the Poisson tail cutoff or the truncated second-moment bound broke for some corner α near an integer or near the log k ceiling, the Ω(α k^{1−1/α}) claim would collapse. I stress-tested the worst cases — integer-adjacent α and the middle range r between α/2 and α — and the constants hold; the C* = e^{-40} choice gives enough slack. Still, this is not machine-checked, and I would want a referee to redo Lemma 8.5 line by line. Second, the noninteger-order lower bound is not claimed tight, and the open problem is stated honestly. Third, the Li–Wu correction depends on showing the Valiant–Valiant framework does not apply; the counterexample in Section 3.2 is valid, so that part is fine.\n\nBottom line: for anyone working on property testing or entropy estimation, this is important. The paper deserves serious refereeing — it is long, but the main claims are supported and the new lower-bound machinery is worth the investment. Send it to peer review.","headline":"The paper genuinely settles min-entropy sample complexity at Θ(k log k) and growing-order Rényi at Θ(α k^{1−1/α}); the proofs are long but the main machinery checks out.","tokens_in":43831,"tokens_out":2583,"would_cite":true,"duration_ms":27917,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A17","62G05","62C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"Estimating min-entropy from samples requires Θ(k log k) samples, and Rényi entropy of order α requires Θ(α k^(1−1/α)) for growing integer α.","keywords":["min-entropy estimation","Rényi entropy","sample complexity","falling-factorial estimator","collision statistics","empirical maximum","property testing","Poissonization"],"falsifier":"Directly compute the exact, untruncated χ² divergence between the two hidden-heavy-coordinate Poisson mixtures for k = 10^4, α = 8, B = e^4, and n = α k^(1−1/α)/4. If the divergence is bounded below by a positive constant rather than vanishing, then the occupancy cutoff ⌊α⌋ discards a non-negligible part of the evidence and the lower-bound argument would need revision.","tokens_in":42889,"feed_emoji":"🧮","tokens_out":5915,"duration_ms":63508,"temperature":0.7,"pith_summary":"Min-entropy estimation at constant additive accuracy has sample complexity Θ(k log k), a Θ(log^2 k) factor more than Shannon entropy, and this paper proves both the upper and lower directions. For Rényi entropy of integer order α between 2 and c0 log k, it proves the tight bound Θ_{c0}(α k^(1−1/α)), exposing a previously hidden factor of α. The min-entropy result corrects a prior Θ(k/log k) claim by showing the standard relative-earthmover continuity argument does not apply to min-entropy. If the bounds hold, entropy estimation in large-alphabet settings—cryptography, property testing, randomness testing—has a precise sample-cost target, and growing-order Rényi entropy is genuinely harder than any fixed-order analysis suggested.","feed_headline":"Min-entropy estimation needs Θ(k log k) samples","feed_subtitle":"Proves Rényi order α costs Θ(α k^(1−1/α)) samples—an exact price hidden in fixed-order bounds.","key_machinery":"Two mechanisms carry the argument. For min-entropy, the plug-in estimator −log max_i(N_i/n) is analyzed via dyadic buckets of symbols by probability scale; bucket sizes are bounded by normalization and upper-tail probabilities decay fast, giving a O(1/p⋆) prefactor. For Rényi entropy, the unbiased falling-factorial estimator bPα = (n)_α^(−1) Σ_x (N_x)_α represents an average of α-way collision indicators; organizing the variance by how many sample positions two indicator tuples share yields the O(α k^(1−1/α)) upper bound. The lower bound's key device is a hidden-coordinate mixture with heavy mass at scale a = k^(−1+1/α), compared against a product-Poisson baseline with a likelihood ratio tru","core_discovery":"The paper's central claim is that worst-case min-entropy estimation is not as cheap as Shannon entropy estimation: with constant additive error and constant failure probability, n = Θ(k log k) samples are necessary and sufficient. The upper bound comes from the empirical maximum bp⋆, with a dyadic grouping of probability scales that controls overtaking by light symbols; the lower bound comes from a distribution chosen uniformly among k coordinates slightly heavier than the rest, which forces an extra log k search cost. For integer Rényi orders, the paper shows the minimax rate is Θ_{c0}(α k^(1−1/α)) throughout 2 ≤ α ≤ c0 log k: an unbiased falling-factorial collision estimator achieves it, a","pith_inferences":["If the truncation analysis is robust, similar truncated likelihood ratios could give tight lower bounds for other extreme-value statistics, such as estimating the size of the largest atom or the support of a near-uniform distribution, where a hidden-coordinate search cost should reappear.","The dyadic-concentration upper bound for the empirical maximum is distribution-dependent and may extend to countable alphabets or heavy-tailed sources, giving local sample complexities governed by 1/p⋆ rather than ambient alphabet size.","A natural next step is an adaptive estimator that chooses between the collision regime and the empirical-maximum regime based on α; the paper supplies both rates but no unified algorithm.","The k log k benchmark suggests practical min-entropy testers should expect a logarithmic search overhead relative to Shannon-entropy tests, which could inform sequential or de-randomized procedures that first locate candidate heavy coordinates."],"forward_implications":["Min-entropy estimation requires Θ(log^2 k) more samples than Shannon entropy estimation, so worst-case predictability is strictly costlier to assess than average uncertainty.","The α factor in the Rényi bound is intrinsic: any estimator that hides α in fixed-order constants misses a linear-order penalty that appears as soon as α grows with k.","In the high-order regime α ≥ 1 + 2 log k/ε, an ε/2-accurate min-entropy estimator becomes an ε-accurate Rényi entropy estimator, giving Θ(k log k) sample complexity there as well.","The failure of relative-earthmover continuity means generic histogram-reconstruction estimators cannot be applied to min-entropy; extreme-value estimators need dedicated concentration arguments.","For real noninteger orders 1.001 ≤ α ≤ c0 log k, the uniform lower bound Ω(α k^(1−1/α)) holds, though the matching upper bound remains open."],"fun_headline_variants":["Min-entropy costs Θ(k log k) samples, not Θ(k/log k)","Rényi entropy exact sample cost: Θ(α k^{1-1/α})","Min-entropy needs Θ(log²k) more samples than Shannon","Tight bounds show min-entropy and Rényi estimation costs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The Rényi lower bound's load-bearing step is the truncation of occupancy counts at ⌊α⌋: the proof must show that the discarded tail of the mixture likelihood ratio is negligible and that the truncated second moment is ≤ 10^(−6); if that cutoff fails anywhere in 1.001 ≤ α ≤ c0 log k, the Ω(α k^(1−1/α)) lower bound does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Min-entropy costs Θ(k log k) samples, not Θ(k/log k)","Rényi entropy exact sample cost: Θ(α k^{1-1/α})","Min-entropy needs Θ(log²k) more samples than Shannon","Tight bounds show min-entropy and Rényi estimation costs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00024,"raw_usage":{"total_tokens":1471,"prompt_tokens":976,"completion_tokens":495,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":720,"completion_tokens_details":{"reasoning_tokens":411}},"tokens_in":720,"tokens_out":495,"duration_ms":5132,"temperature":1.0,"reasoning_tokens":411,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T19:25:22.237186+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Directly compute the exact, untruncated χ² divergence between the two hidden-heavy-coordinate Poisson mixtures for k = 10^4, α = 8, B = e^4, and n = α k^(1−1/α)/4. If the divergence is bounded below by a positive constant rather than vanishing, then the occupancy cutoff ⌊α⌋ discards a non-negligible part of the evidence and the lower-bound argument would need revision.","supporting_citations":[],"review_version":1}