{"id":"7d004097-732f-4d84-9bcd-f5146b777dd7","arxiv_id":"2501.12548","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A hierarchical spherical code construction raises the deterministic identification achievability bound for Gaussian channels from 1/4 to 3/8.","lead":"A new 'galaxy code' construction improves the achievable rate for deterministic identification over Gaussian channels from 1/4 to 3/8. This is a theoretical advance for an information-theory problem about detecting event messages rather than decoding full data.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Same-galaxy type II error bound in Theorem 6/Corollary 1 is not established as written: the condition is stated too weakly and the t=1 case breaks the final inequality.","rationale":"The paper's central claim is an improved achievability bound C_DI(G) ≥ 3/8, and the main construction is a hierarchical galaxy code. The rate calculation is coherent: the number of codewords from packing centers, the spherical-code bound, and the choice t ≈ (1/4−b)log n/log k lead to a rate whose n→∞ limit approaches 3/8 as b→0 and k→∞. The type I error analysis is also standard, using concentration of the chi-square distribution and the projection lemma. The genuine soft spot is the same-galaxy type II error analysis, which is the part of the argument that is specific to the new code. As the reader noted, Theorem 6 is proved under a stronger condition than Corollary 1 states, and the error analysis in Section V-C relies on the weaker corollary. I additionally find that the final inequality in Theorem 6 fails for t(u1,u2)=1, the case of two codewords sharing only a depth-1 galaxy. This is not merely cosmetic: the same-galaxy type II event is the only place where the hierarchical separation is actually used, and an unproven bound there would leave the error probability uncontrolled. However, the defect appears repairable: the chosen θ satisfies the stronger condition, and the t=1 case still yields a projection-distance lower bound growing like n^b, which is eventually larger than any fixed multiple of log n. The power-constraint violation is also present but minor and fixable by a standard rescaling. Therefore the 3/8 claim is plausible and likely correct, but the manuscript as written does not fully establish it. A conditional verdict is appropriate, and no verdict change is needed from this stress-test pass.","tokens_in":13294,"tokens_out":11025,"duration_ms":102326,"concrete_test":"Independently re-derive the chain of inequalities in Theorem 6 from Theorems 4 and 5, keeping explicit the factor (k−1)((sin(θ/2)−1/(k−1))^2 − 1/(k−1)) and the term k^{2(t−1)}/(k^t−1). Check whether the condition > 1/(k−1) suffices or whether > 2/(k−1) is required. Then test t=1 explicitly, where k^{2(t−1)}/(k^t−1) = 1/(k−1), and verify that the resulting bound still exceeds 2σ log n for the chosen θ = 2 arcsin(2/√(k−2)) and fixed b>0.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 3 depends on controlling P(P_{o,u1}|u2) for two codewords u1,u2 in the same galaxy. This control is supplied by Theorem 6 and Corollary 1 in Section V. Theorem 6's proof requires (sin(θ/2)−1/(k−1))^2 > 2/(k−1) to pass from the projection-distance lower bound to the term 4r, because the factor (k−1)((sin(θ/2)−1/(k−1))^2 − 1/(k−1)) must be at least 1. Corollary 1, however, is stated with the weaker condition > 1/(k−1), and the error analysis in Section V-C invokes only Corollary 1. The chosen θ = 2 arcsin(2/√(k−2)) likely satisfies the stronger condition for all admissible k, so the gap is repairable, but the written proof is incomplete. A second, independent gap appears in the same inequality: the step k^{2(t−1)}/(k^t−1) ≥ 1 fails when t(u1,u2)=1, where the ratio is 1/(k−1). For two codewords sharing only a depth-1 galaxy this is exactly the case that must be checked. A direct computation with the chosen θ gives a bound of order r/k = n^b/k rather than 4r, which still tends to infinity for fixed k and b>0, so the conclusion remains plausible; but the proof as written does not cover it. The power-constraint violation (codeword norms exceeding nP by roughly n^{1/4}/(k−1)) is secondary and also repairable by shrinking the centers, so the single load-bearing concern is the same-galaxy type II bound.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces galaxy codes, a hierarchical spherical-code construction for deterministic identification (DI) over the Gaussian channel with power constraints. The main result, Theorem 3, claims the DI capacity satisfies C_DI(G) ≥ 3/8, improving the previous lower bound of 1/4. The construction organizes codewords as leaves of a depth-t galaxy built recursively from θ-spherical codes; decoding is performed by intersecting projection-based half-spaces and a shell constraint. The proof contains a rate computation (Claim 1, Lemma 1), distance bounds (Theorems 4 and 5), and type I/type II error analyses.","tokens_in":13668,"tokens_out":12778,"duration_ms":118189,"significance":"If correct, the 3/8 lower bound is a genuine advance: it narrows the gap between the previous lower bound 1/4 and the known upper bound 1/2 for deterministic identification capacity of the Gaussian channel. The hierarchical galaxy construction is novel and likely to be of independent interest for other identification problems. The paper also gives a fairly detailed derivation, and the rate calculation and the cross-galaxy error bound are coherent. However, several load-bearing steps in the same-galaxy type II error analysis and in the power-constraint compliance of the code need repair; with those repaired, the result would be a notable contribution.","major_comments":[{"comment":"The proof of Theorem 6 requires the stronger condition (sin(θ/2) − 1/(k−1))^2 > 2/(k−1) in order to pass from the projection-distance lower bound to the term 4r, since the factor (k−1)((sin(θ/2)−1/(k−1))^2 − 1/(k−1)) must be at least 1. Corollary 1, however, is stated with the weaker condition > 1/(k−1), and the same-galaxy error analysis in Section V-C invokes only Corollary 1. As written, therefore, the same-galaxy type II error bound is not established under the stated hypotheses. This gap is repairable because the chosen θ = 2 arcsin(2/√(k−2)) appears to satisfy the stronger condition for all admissible k, but the proof must state and verify this explicitly.","section":"Section V, Theorem 6 proof"},{"comment":"The step k^{2(t(u1,u2)−1)}/(k^{t(u1,u2)} − 1) ≥ 1 fails when t(u1,u2) = 1, where the ratio equals 1/(k−1) < 1. This is exactly the case of two codewords lying in the same depth-1 galaxy, which the same-galaxy analysis must cover. Direct computation with the chosen θ gives a bound of order r/k = n^b/k rather than 4r; this may still be at least 2 log n for fixed k and b>0, so the conclusion is plausible, but the written chain of inequalities is invalid in this case and the proof needs an additional argument for t(u1,u2)=1.","section":"Section V, Theorem 6 proof"},{"comment":"The constructed codewords do not satisfy the power constraint as stated. By Theorem 4, ∥u − o_i∥₂ ≤ r(k^t − 1)/(k − 1), and with t = ⌈(1/4−b) log n / log k⌉ and r = n^b, this upper bound is at most k n^{1/4}/(k−1). Thus a codeword attached to a center o_i with ∥o_i∥₂ = √(nP) has ∥u∥₂² ≥ nP + Θ(n^{3/4}), exceeding the allowed nP for large n. Simply shrinking the centers by a constant multiple of n^{1/4} does not repair this when b>0, because the required inter-center separation n^{b+1/4} grows faster than n^{1/4}; the centers must be placed inside a sphere of radius √(nP) − n^{b+1/4} (or a similar adjustment), and the packing estimates in Claim 1 would need to be reworked accordingly. The asymptotic rate appears unaffected, but the code as defined is not a valid DI code under the power constraint.","section":"Section IV, Definition 1"}],"minor_comments":[{"comment":"The algebraic passage to 3/8 skips the combination of the 1/2 term with the −1/8 that emerges from expanding the logarithmic rate expression; adding one line would improve clarity.","section":"Section VI"},{"comment":"The parameter b is introduced as 'a very small real number' but must be positive so that r = n^b grows and so that Lemma 3's bound n^{b+1/4}/2 meets the n^{1/4} log n threshold required by Corollary 2. The paper should state b > 0.","section":"Section IV"},{"comment":"The power-constraint formula '∥ui∥2 2 = nP k=1 u2 ik ≤ nP' contains a typo; it should read ∑_{k=1}^n u_{ik}^2 ≤ nP.","section":"Definition 1"},{"comment":"The notation for the projection sets is inconsistent: Notation 1 defines P_{o,u}, while Corollary 1 and Section V-C use P_{¯o,u} and P_{¯oi,u} interchangeably. Please define the notation once and use it consistently.","section":"Notation 1"},{"comment":"The lower bound on M(n,θ) is written as a chain ending with ≥ 1/sin^n(θ); the intermediate use of s_n(θ) and the logarithmic factor is not fully explained, though the bound is standard and the conclusion is correct.","section":"Section V-A"}],"recommendation":"major_revision","confidential_remarks":"The three major issues above are all repairable within the manuscript's scope. The same-galaxy type II error gap (Theorems 6 and Corollary 1, plus the t=1 failure) is the most serious and must be fixed with a correct condition and a separate treatment of t=1. The power-constraint violation requires reworking the center packing but appears not to change the asymptotic rate. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, here's the gist. Galaxy Codes claims to push the deterministic identification achievability bound over Gaussian channels from 1/4 to 3/8 using a hierarchical spherical code it calls a galaxy code. That is a real, if modest, quantitative advance, and the construction is new. The different-galaxy error analysis and the rate calculation are coherent, and the authors properly credit the earlier bounds they build on.\n\nThe soft spots are concentrated in the same-galaxy type II error proof. Theorem 6's proof needs (sin(θ/2)-1/(k-1))^2 > 2/(k-1) to push a factor to at least 1, but Corollary 1 is stated with the weaker > 1/(k-1). The chosen θ = 2 arcsin(2/√(k-2)) actually satisfies the stronger condition for large k, so this is a mismatch in the statement, not a fundamental flaw. Second, the inequality k^{2(t-1)}/(k^t-1) ≥ 1 fails when t=1, which is precisely the shallowest divergence between two codewords. In that case the bound degrades to n^b/k, which still tends to infinity for fixed k and b>0, so the conclusion likely survives, but the written proof does not cover it. There's also a minor power-constraint violation: codeword norms can exceed nP by roughly n^{1/4}/(k-1); shrinking the centers fixes it.\n\nNone of these are fatal, but they are load-bearing gaps in the manuscript as written. The paper deserves a serious referee and, if the authors tighten the same-galaxy argument, it will be a solid contribution. I'd send it to peer review rather than desk reject.","headline":"Plausible improvement of the DI lower bound to 3/8, but the same-galaxy type II proof has a repairable condition mismatch and a t=1 gap.","tokens_in":14193,"tokens_out":4654,"would_cite":true,"duration_ms":43173,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94A15","94A24"],"pacs":[],"model":"deepseek-v4-flash","headline":"Deterministic identification over power-constrained Gaussian channels is achievable at every rate below 3/8, improving the previous 1/4 lower bound.","keywords":["deterministic identification","Gaussian channel","galaxy codes","spherical codes","achievability bound","capacity bounds","power constraint","superexponential growth"],"falsifier":"Take the parameter choices from Section VI and check whether $(\\sin(\\theta/2) - 1/(k-1))^2 > 2/(k-1)$ holds for large $k$; if it fails, Theorem 6 does not cover the constructed code and the same-galaxy type II bound lacks a proof. A numerical check of the projection distance for two codewords whose first split is at the top level would also settle whether the bound $4r \\ge 2\\log n$ is met.","tokens_in":13098,"feed_emoji":"🌌","tokens_out":8116,"duration_ms":75114,"temperature":0.7,"pith_summary":"Deterministic identification asks a receiver to test whether a particular message was sent, rather than decode the whole transmission. This paper introduces a coding construction called galaxy codes for the Gaussian channel with a power constraint, and uses it to prove that the deterministic identification capacity is at least 3/8 in the $2^{nR\\log n}$ scale, improving the previous best lower bound of 1/4. The capacity is still bounded above by 1/2, so the new result cuts the known gap in half. If correct, it means a Gaussian channel can identify a superexponential number of messages, far more than Shannon transmission, using deterministic encoding. The construction is hierarchical: codewords sit on nested spheres, and the receiver zooms from galaxy to star system to planet to moon before saying yes or no.","feed_headline":"Galaxy codes lift identification rate from 1/4 to 3/8","feed_subtitle":"Hierarchical spherical codes let receivers test for a message without decoding it, narrowing the gap to the 1/2 upper bound.","key_machinery":"The load-bearing object is the galaxy code $G_n(\\theta,b,k)$. It is a $t$-level hierarchy of spherical codes: at the top, message centers are packed in the power sphere; around each center, $M(n,\\theta)$ points are placed on a sphere of radius $k^{t-1}r$ with minimum angular separation $\\theta$; around each such point another $M(n,\\theta)$ points on radius $k^{t-2}r$, and so on down to the finest level at radius $r$. This gives $M(n,\\theta)^t$ codewords per message center. The decoder assigns to each codeword $u$ the set $D_u = S_u \\cap Q_u$, where $S_u$ is a thin spherical shell around $u$ capturing the output energy, and $Q_u$ is the intersection of sets $\\{y : \\|u - \\mathrm{proj}_{o_i u}(y)\\| \\le \\sigma \\log n\\}$ along the radial lines of the codeword's ancestors. The angular separation at each level keeps projections of other codewords at distance roughly $4r$ from the decision boundary, so Gaussian tail bounds make the type II error small. The rate calculation combines the spherical-code size lower bound with the volume packing of message centers, and the parameter choice $\\sin(\\theta) < 4/\\sqrt{k}$ drives the achievable rate to $3/8$ as $k$ grows and a small radius parameter $b$ tends to zero.","core_discovery":"The paper's central claim is Theorem 3: for a Gaussian additive white noise channel with input power constraint, the deterministic identification capacity satisfies $C_{DI}(G) \\ge 3/8$. In concrete terms, for every allowed error probabilities $\\lambda_1, \\lambda_2 > 0$ and every rate $R < 3/8$, there is a deterministic identification code with $N = 2^{nR\\log n}$ codewords and block length $n$ large enough that both type I and type II error probabilities are below $\\lambda_1$ and $\\lambda_2$. The previous achievability result gave 1/4, and the best upper bound is 1/2; this paper moves the lower bound to within 1/8 of that upper bound.","pith_inferences":["The same nested-projection idea may transfer to other isotropic noise channels, such as fading or molecular channels, where only the shell probability calculation would change; the paper does not make this claim.","If the same-galaxy angular condition can be relaxed, the construction might support rates above $3/8$; checking whether the stronger inequality used in Theorem 6 actually holds for the chosen parameters would settle whether that route is open.","A numerical simulation of the projection rule for moderate block lengths could reveal whether the asymptotic error bounds are conservative, which would guide whether the hierarchy should be made deeper or the angles larger."],"forward_implications":["Every rate $R < 3/8$ is achievable for deterministic identification on the Gaussian channel with power constraint, so the known achievable region grows from $1/4$ to $3/8$.","The number of messages scales as $N = 2^{nR\\log n}$, which is superexponential in the usual Shannon scale, so identification remains qualitatively far larger than transmission.","The encoding is deterministic, so the superexponential gain does not require shared randomness between sender and receiver.","The gap to the known upper bound $1/2$ shrinks from $1/4$ to $1/8$, leaving a single interval of rates unresolved."],"supporting_citations":[{"why":"Establishes the $2^{n\\log n}$ scale and the 1/4 lower bound that this paper improves.","marker":"[4]"},{"why":"Gives the 1/2 upper bound that the new 3/8 lower bound moves toward.","marker":"[6]"},{"why":"Supplies the lower bound on the size $M(n,\\theta)$ of $\\theta$-spherical codes used to count codewords in each galaxy level.","marker":"[7]"},{"why":"Provides the spherical-packing bound on the Gaussian sphere used in the code-size estimate.","marker":"[8]"},{"why":"Gives the bounded-discrepancy spherical-code bound used in the same counting argument.","marker":"[9]"},{"why":"Introduces identification via channels and the double-exponential message growth that motivates the identification capacity notion.","marker":"[1]"}],"fun_headline_variants":["Galaxy codes: Deterministic ID hits 3/8","From 1/4 to 3/8: Galaxy codes narrow the gap","Galaxy codes boost Gaussian ID bound to 3/8","No decoding needed: Galaxy codes achieve 3/8","Galaxy codes push deterministic ID rate to 3/8"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument that the decoder does not confuse two codewords in the same galaxy needs a larger minimum angle between their separating ancestors than the corollary quoted in the paper proves, and the 3/8 rate is reached only as a small tuning parameter goes to zero.","fun_headline_variants_meta":{"raw":{"variants":["Galaxy codes: Deterministic ID hits 3/8","From 1/4 to 3/8: Galaxy codes narrow the gap","Galaxy codes boost Gaussian ID bound to 3/8","No decoding needed: Galaxy codes achieve 3/8","Galaxy codes push deterministic ID rate to 3/8"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000383,"raw_usage":{"total_tokens":1972,"prompt_tokens":831,"completion_tokens":1141,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":447,"completion_tokens_details":{"reasoning_tokens":1052}},"tokens_in":447,"tokens_out":1141,"duration_ms":10161,"temperature":1.0,"reasoning_tokens":1052,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T17:05:37.978721+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the parameter choices from Section VI and check whether $(\\sin(\\theta/2) - 1/(k-1))^2 > 2/(k-1)$ holds for large $k$; if it fails, Theorem 6 does not cover the constructed code and the same-galaxy type II bound lacks a proof. A numerical check of the projection distance for two codewords whose first split is at the top level would also settle whether the bound $4r \\ge 2\\log n$ is met.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the $2^{n\\log n}$ scale and the 1/4 lower bound that this paper improves."},{"cited_title":"Chabauty, Resultats sur l'empilement de calottes egales sur une périsphere de R^ n et correction a un travail anterieur , 1953, vol","cited_arxiv_id":null,"evidence_quote":"Supplies the lower bound on the size $M(n,\\theta)$ of $\\theta$-spherical codes used to count codewords in each galaxy level."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the spherical-packing bound on the Gaussian sphere used in the code-size estimate."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the bounded-discrepancy spherical-code bound used in the same counting argument."},{"cited_title":"Ahlswede and G","cited_arxiv_id":null,"evidence_quote":"Introduces identification via channels and the double-exponential message growth that motivates the identification capacity notion."}],"review_version":1}