{"id":"70c0d9b3-cb0e-4196-990d-cd5a72469aed","arxiv_id":"2607.14503","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Exact entropy-efficient random sampling with per-sample entropy loss ε requires Ω(log(1/ε)) bits of persistent space, with sharp constants for Bernoulli(1/3) and almost all k-outcome distributions.","lead":"This paper proves that any exact random sampler that comes within ε bits per sample of the information-theoretic entropy limit must use at least Ω(log(1/ε)) bits of persistent memory, with explicit constants for Bernoulli and general i.i.d. outputs. It is the first space lower bound of its kind for entropy-efficient online random sampling, transforming a recently posed conjecture into a theorem with a graph-theoretic proof.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Numerical constant in Thm 1(1.1) rests on unverified [BLS18] bound; if Eq. (39) exponent is wrong, 1/5.116201 changes, though Ω(log 1/ε) holds.","rationale":"I read the paper in good faith. The structural framework—Definitions 4 and 7, Theorems 8–10, and the cycle pigeonhole bound in Theorem 14—is presented in detail and appears sound. The central Ω(log 1/ε) lower bound is robust: it relies only on Baker's theorem for some finite irrationality exponent, not on the specific constant 4.116201. The reader's CONDITIONAL verdict is therefore reasonable. My main concern is the same imported Diophantine bound the reader flagged: Eq. (39) is the sole source of the advertised 1/5.116201 constant. If [BLS18] does not imply that exact exponent, the paper's headline numerical claim is wrong, even though the asymptotic result stands. I do not share the reader's secondary concern about the exactness model excluding samplers with future knowledge: the online model is clearly stated and the lower bound for i.i.d. outputs (Theorem 2) covers the offline-like setting. I additionally noticed a typo in the statement of Theorem 1(1.2), where Bernoulli(1/(2m+1)) is inconsistent with the proof's use of α_m = log(1+2^{-m}); choosing m as powers of two fixes the argument without changing the theorem's truth. No further load-bearing objections emerged. Thus I recommend keeping the verdict CONDITIONAL pending verification of the external constant, i.e., UNCHANGED from the reader's assessment.","tokens_in":18422,"tokens_out":37226,"duration_ms":320639,"concrete_test":"Independently verify [BLS18, Theorem 1] and re-derive Eq. (39) from ν(1,ln2,ln3) ≤ 4.116201. Specifically, check whether the linear-independence measure implies min_{1≤a≤M} ⟨−a log 3⟩ ≥ M^{−4.116201−o(1)} rather than M^{−5.116201−o(1)}. If the correct exponent is the latter, recompute the constant in (1.1) as 1/6.116201 and adjust the abstract.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 1(1.1) derives the constant 1/5.116201 from Eq. (39): min_{1≤a≤M} ⟨−a log 3⟩ ≥ M^{−4.116201−o(1)}, attributed to [BLS18, Thm 1]. This is an imported number-theoretic bound that the manuscript neither proves nor verifies. The reduction from the linear-independence measure ν(1,ln2,ln3) ≤ 4.116201 to the fractional-part bound is sketched in one line and could hide a misplaced exponent or an extra factor (e.g., if the correct exponent is the irrationality exponent 5.116201 from [WW14], the stated constant becomes 1/6.116201). Because the abstract advertises the explicit 1/5.116201, this is a genuine correctness risk for the headline numerical claim. The core Ω(log 1/ε) lower bound does not depend on this constant—Baker's theorem supplies some finite exponent—so the central conjecture survives even if Eq. (39) is off. I also note a separate, fixable typo: Theorem 1(1.2) states Bernoulli(1/(2m+1)), but the proof's α_m = log(1+2^{-m}) only matches Bernoulli(1/(2^m+1)) (or m a power of two). This does not threaten the main theorem, but it should be corrected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves space lower bounds for exact online random sampling. For any sampler that produces exact samples from arbitrary discrete distributions using i.i.d. uniform bits and has expected entropy loss at most ε per sample, the persistent state space S must satisfy log|S| ≥ Ω(log(1/ε)). The two concrete instantiations are: (1.1) if Bernoulli(1/3) is supported, log|S| ≥ (1/5.116201 − o(1)) log(1/ε); (1.2) if infinitely many Bernoulli distributions of the form Bernoulli(1/(2^m+1)) are supported, then |S| ≥ 1/ε. A second theorem gives (1/(k+1) − o(1)) log(1/ε) for almost every k-outcome i.i.d. distribution. The proof introduces a state information content function h, shows via difference constraints and exactness that a nonnegative h exists, then uses a pigeonhole/cycle argument to lower-bound the per-sample entropy loss by a Diophantine quantity Γ_p(|S|). The final bounds come from lower bounds on fractional parts of integer multiples of log-probabilities.","tokens_in":18679,"tokens_out":29430,"duration_ms":266800,"significance":"The central Ω(log(1/ε)) bound is a genuine and notable result: it resolves a conjecture from the authors' earlier work and appears to be the first space lower bound for entropy-efficient random sampling. The structural reduction is clean: exactness rules out negative cycles, the state information content potential is well defined, and the cycle argument is self-contained. A particular strength is that the proof isolates the Diophantine input, so the main logarithmic bound is robust even if the numerical constant from the external number-theory result were to change. The paper also connects the lower bound to existing upper bounds, showing that the space usage of randomness recycling is optimal up to constants. If the numerical issues described below are resolved, this is a strong contribution to the random-variate-generation literature.","major_comments":[{"comment":"The advertised constant 1/5.116201 in Theorem 1(1.1) rests entirely on the imported bound ν(1,ln2,ln3) ≤ 4.116201 attributed to [BLS18, Theorem 1], and the derivation of (39) is only sketched in one sentence. The authors need to (a) quote the exact statement from [BLS18], (b) show explicitly how a linear-independence measure over (1,ln2,ln3) yields the base-2 fractional-part bound min_{1≤a≤M} ⟨−a log 3⟩ ≥ M^{−4.116201−o(1)}, and (c) reconcile the text's assertion that the current best irrationality exponent of log 3 is 5.116201 with the claimed stronger ν ≤ 4.116201. If the constant cannot be confirmed, the theorem should be restated with an unspecified constant from Baker's theorem, which is sufficient for the central Ω(log(1/ε)) claim.","section":"§6.1, Eq. (39)"},{"comment":"The theorem statement says Bernoulli(1/(2m+1)), but the proof uses p_m = Bernoulli(1/(2^m+1)) with α_m = log(1+2^{-m}). For p = 1/(2m+1) the fractional parts of log(1/p(0)) and log(1/p(1)) are not equal, and the proof's reduction to ⟨−a α_m⟩ fails. The statement (and abstract) should be corrected to Bernoulli(1/(2^m+1)). In addition, the displayed implication in Eq. (42), |S| ≥ sup_m (1−|S|α_m)/ε, is not algebraically valid because the right-hand side depends on |S|. The correct step is to rearrange to |S| ≥ 1/(ε+α_m) for each m and then take the supremum as α_m → 0, yielding |S| ≥ 1/ε. The conclusion is right, but the written derivation needs repair.","section":"Theorem 1(1.2) and §6, Eq. (42)"},{"comment":"The proof of Lemma 10 assumes each edge weight A_{i,j} is finite when it writes A_{i,j}+ε, yet the lemma also claims to verify that every A_{i,j} > −∞. As written, the argument is incomplete for the case A_{i,j} = −∞. A rigorous proof should first establish a finite lower bound for every A_{i,j} using reachability and the exactness of a prefix path, or handle −∞ edges separately. The statement is true, but the proof needs an additional paragraph.","section":"Lemma 10, §4"}],"minor_comments":[{"comment":"The symbol M is used both as an integer in (41) and as the infinite set of m in the proof of (1.2). Please use different notation to avoid confusion.","section":"§6, Eq. (41)–(42)"},{"comment":"Typo: 'reuslt' should be 'result'.","section":"§6, proof of Theorem 1"},{"comment":"The irrationality exponent and linear independence measure are defined as the 'minimum' real number satisfying the stated property, but such a minimum may not be attained; the standard formulation uses an infimum or the smallest exponent up to ε. Please make the definitions precise.","section":"Definitions 15–16"},{"comment":"The conversion between natural and base-2 logarithms in Eq. (39) should be stated explicitly. Since [BLS18] concerns ln 2 and ln 3, the bound for ⟨−a log 3⟩ should be derived with the factor ln 2 made explicit; otherwise the reader cannot verify the exponent.","section":"§6.1"}],"recommendation":"major_revision","confidential_remarks":"The core structural argument appears sound, and the Ω(log(1/ε)) lower bound is likely correct. The main risk is the unverified external Diophantine constant and the mismatched statement in Theorem 1(1.2). If the authors can supply a precise citation/derivation for (39) and fix the typo and the algebra in (42), the paper would be acceptable. The editor may want an additional check of the [BLS18] result by someone with expertise in Diophantine approximation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know: this paper proves the Ω(log(1/ε)) persistent-space lower bound for exact entropy-efficient random sampling, resolving a conjecture from the authors' own earlier work, and it does it with a genuinely new proof technique based on state information content and cycle-pigeonhole arguments. The central theorem (Theorem 14) is clean, self-contained, and correct as far as I can see: the no-negative-cycle argument, the telescoping of h(s), and the Γ_p(M) pigeonhole bound all check out. The applications to Bernoulli(1/3) and to almost every k-outcome distribution are straightforward given the Diophantine input.\n\nThe main soft spot is the advertised constant 1/5.116201. It comes from an imported bound ν(1, ln2, ln3) ≤ 4.116201 from [BLS18], which the paper neither proves nor verifies. If that exponent is off, the constant in (1.1) changes. But the Ω(log 1/ε) lower bound does not depend on this constant — Baker's theorem supplies some finite exponent — so the conjecture's resolution is safe. A referee should still double-check the reduction from the linear-independence measure to the fractional-part bound (Eq. 39) and the application of [KM98] in Theorem 2.\n\nThere's also a fixable typo: Theorem 1(1.2) states Bernoulli(1/(2m+1)), but the proof's α_m = log(1+2^{-m}) belongs to Bernoulli(1/(2^m+1)). The argument works with either family (any m with α_m→0), but the statement and proof don't match.\n\nOne conceptual point worth a referee's attention: the exactness model in Definition 4 is the standard one for random generation with a fair coin, and the reachability restriction is WLOG. I don't see a real gap, but it's worth checking that natural samplers with nondeterministic state transitions or side information about future distributions are not unintentionally excluded.\n\nBottom line: this is a solid, significant paper. The proof of the main lower bound is correct, the writing is honest about its open questions and dependence on external results, and the result deserves publication. I'd send it to peer review, with instructions to verify the Diophantine constants and fix the (1.2) typo.","headline":"Genuinely new lower bound: clean proof of Ω(log 1/ε) persistent space for exact entropy-efficient sampling; the advertised 1/5.116201 constant rides on an imported Diophantine bound and there's a fixable typo in (1.2), but the central result stands.","tokens_in":19372,"tokens_out":6149,"would_cite":true,"duration_ms":45120,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","94A17","11J82"],"pacs":[],"model":"deepseek-v4-flash","headline":"Exact random sampling that stays within ε bits per sample of the optimal-entropy lower bound must use at least a logarithmic amount of persistent memory.","keywords":["random sampling","entropy loss","space complexity","online algorithms","Bernoulli distribution","Diophantine approximation","state information content"],"falsifier":"Run a brute-force search for an exact Bernoulli(1/3) sampler with fewer than 3 persistent states that achieves entropy loss below ε = 0.01 per sample; the theorem predicts log|S| ≥ 1.29 bits, i.e., at least 3 states, so such a sampler would refute the bound. A more direct check of the number-theoretic input: compute min_{1≤a≤10^6} ⟨−a log_2 3⟩ and verify it stays above (10^6)^{-4.116201}.","tokens_in":18118,"feed_emoji":"🎲","tokens_out":10300,"duration_ms":84433,"temperature":0.7,"pith_summary":"This paper establishes the first space lower bounds for entropy-efficient random sampling. Its main theorem states that any online sampler which exactly generates arbitrary discrete distributions and consumes at most H + εn + o(n) input bits in expectation — within ε bits per sample of the Shannon entropy lower bound — must use Ω(log(1/ε)) bits of persistent state. The bound is quantitative: a single Bernoulli(1/3) source (a biased coin with probability 1/3) already forces a state space of size at least (1/ε)^(1/5.116201), and handling infinitely many Bernoulli distributions tightens the requirement to at least 1/ε states. A second theorem extends a (1/(k+1)-o(1)) log(1/ε) lower bound to almost every i.i.d. k-outcome distribution. The proof reduces the problem to Diophantine approximation: the required memory is determined by how close integer combinations of log-probabilities can come to integers.","feed_headline":"Random sampling close to optimal entropy forces logarithmic memory","feed_subtitle":"Even a single Bernoulli(1/3) coin enforces the bound; the proof reduces to how well multiples of log 3 approximate integers.","key_machinery":"The load-bearing construction is the state information content h, a nonnegative real value assigned to each state that bounds how much reusable randomness the sampler can carry across rounds; it must satisfy h(s') + log(1/p(x)) ≤ h(s) + |c| for every transition, mirroring a data-processing inequality. The paper proves such a function always exists by showing the associated difference-constraint graph has no negative cycles. A pigeonhole argument over the state space then shows that after M samples, some state repeats, so the information lost around the resulting cycle is at least the fractional part of an integer combination of log-probabilities; this yields the master bound |S| ≥ Γ_p(|S|)/ε","core_discovery":"In the paper's own terms, the central discovery is that persistent memory and entropy efficiency are provably at odds. Theorem 1 proves that an online random sampler that is exact for arbitrary discrete distributions and achieves entropy loss at most ε per sample must have log|S| ≥ Ω(log(1/ε)); specifically, if it can sample Bernoulli(1/3), then log|S| ≥ (1/5.116201 − o(1)) log(1/ε), and if it can sample Bernoulli(1/(2m+1)) for infinitely many m, then |S| ≥ 1/ε. Theorem 2 proves that for almost every distribution on k outcomes, any sampler generating i.i.d. samples with entropy loss ε per sample requires at least (1/(k+1)−o(1)) log(1/ε) bits of persistent state. The route is Theorem 14, whic","pith_inferences":["The reduction to Diophantine approximation suggests a finer taxonomy: distributions whose log-probabilities are rationally dependent might be samplable with less than logarithmic memory; the dyadic case, where zero entropy loss and zero state are possible, is the extreme example.","Almost-everywhere hardness implies the typical k-outcome distribution is as hard as the hardest; constructing a sampler that exploits Diophantine structure (e.g., good rational approximations) is the natural converse direction.","The same cycle/information-content argument may transfer to arithmetic coding, where a precision/redundancy trade-off of the same form is known; unifying these two settings would be a natural next step.","A testable extension: try to realize the (1/ε) bound for Bernoulli(1/(2m+1)) with a concrete sampler family; if the true constant in the infinite-family case can be approached, it would confirm that the Diophantine bound is not only necessary but also achievable."],"forward_implications":["No sampler with constant persistent memory can provide arbitrarily small entropy loss for a non-dyadic distribution; saving ε entropy per sample forces saving log(1/ε) memory.","Even a fixed, single Bernoulli(1/3) source induces the logarithmic lower bound, with the constant 1/5.116201 pinned to how well log 3 resists rational approximation.","Supporting infinitely many Bernoulli(1/(2m+1)) distributions strengthens the bound to |S| ≥ 1/ε, so at least log(1/ε) bits of memory are needed.","For almost every k-outcome distribution, even the static i.i.d. sampling setting (no adaptivity across distributions) requires at least (1/(k+1)−o(1)) log(1/ε) bits of space.","For rational distributions with a bounded denominator d, the existing randomness-recycling sampler achieves O(log(d/ε)) bits of space, so the lower bound is tight up to constant factors in this regime."],"fun_headline_variants":["Exact sampling near entropy lower bound forces logarithmic space","Matching entropy cost in sampling requires Omega(log(1/eps)) memory","Bernoulli(1/3) sampler needs at least log(1/eps) bits of state","Entropy-optimal sampling is impossible with sublogarithmic memory"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof's load-bearing premise is the exactness condition — that the weighted sum over all input strings producing an output string equals the target product probability exactly — together with the imported number-theory bound on how close multiples of log 3 can come to integers.","fun_headline_variants_meta":{"raw":{"variants":["Exact sampling near entropy lower bound forces logarithmic space","Matching entropy cost in sampling requires Omega(log(1/eps)) memory","Bernoulli(1/3) sampler needs at least log(1/eps) bits of state","Entropy-optimal sampling is impossible with sublogarithmic memory"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000216,"raw_usage":{"total_tokens":1357,"prompt_tokens":920,"completion_tokens":437,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":664,"completion_tokens_details":{"reasoning_tokens":368}},"tokens_in":664,"tokens_out":437,"duration_ms":4491,"temperature":1.0,"reasoning_tokens":368,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T01:52:22.064991+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a brute-force search for an exact Bernoulli(1/3) sampler with fewer than 3 persistent states that achieves entropy loss below ε = 0.01 per sample; the theorem predicts log|S| ≥ 1.29 bits, i.e., at least 3 states, so such a sampler would refute the bound. A more direct check of the number-theoretic input: compute min_{1≤a≤10^6} ⟨−a log_2 3⟩ and verify it stays above (10^6)^{-4.116201}.","supporting_citations":[],"review_version":1}