Pith. sign in

REVIEW 3 major objections 5 minor 1 cited by

Galaxy Codes: Advancing Achievability for Deterministic Identification via Gaussian Channels

T0 review · 3 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Deterministic identification over power-constrained Gaussian channels is achievable at every rate below 3/8, improving the previous 1/4 lower bound.

desk verdict 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. read the letter →

arxiv 2501.12548 v1 pith:CMRWPXFF submitted 2025-01-22 cs.IT math.IT

Holger Boche , Christian Deppe , Safieh Mahmoodi , Golamreza Omidi This is my paper · ORCID
classification cs.ITmath.IT MSC 94A1594A24
keywords deterministicidentificationGaussianchannelgalaxycodessphericalachievabilityboundcapacityboundspowerconstraintsuperexponentialgrowth
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section V, Theorem 6 proof] 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.
  2. [Section V, Theorem 6 proof] 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.
  3. [Section IV, Definition 1] 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.
minor comments (5)
  1. [Section VI] 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.
  2. [Section IV] 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.
  3. [Definition 1] 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.
  4. [Notation 1] 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.
  5. [Section V-A] 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.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the Galaxy-code rate bound is derived from the construction and standard packing arguments; prior-group citations are contextual only.

full rationale

I walked the claimed derivation chain. Theorem 3's lower bound CDI(G) >= 3/8 is obtained by building Galaxy codes and counting codewords. The number of codewords is N = |M| M(n,theta)^t with t = ceil((1/4-b) log n / log k), and Claim 1 bounds |M| by a volume-packing argument. Lemma 1 converts these into a lower bound on the identification rate R. Section VI substitutes theta = 2 arcsin(2/sqrt(k-2)), so sin(theta) < 4/sqrt(k), and expands the bound; after taking b -> 0 and k -> infinity the constant 3/8 emerges from 1/2 - (1/4)(1/2) = 3/8. No fitted parameter is set to the target rate, and no definition of the code presupposes the achievability of 3/8. The error analysis is self-contained: type I uses chi-square concentration (Theorem 7), type II for different galaxies uses the distance lower bound of Lemma 3 and Corollary 2, and type II for same-galaxy codewords uses the projection bounds in Lemma 2, Theorems 5-6 and Corollary 1. References [4] and [6], which include overlapping authors, are cited only as prior bounds (Theorems 1 and 2) and are not used as premises of Theorem 3; hence they are not load-bearing. I also checked the skeptic's concern: it identifies a proof gap, not circularity. Corollary 1 is stated with (sin(theta/2)-1/(k-1))^2 > 1/(k-1), while Theorem 6's proof appears to require the stronger condition (sin(theta/2)-1/(k-1))^2 > 2/(k-1), and the inequality k^(2(t-1))/(k^t-1) >= 1 fails when t(u1,u2)=1. That is an omitted or incorrect intermediate step in the written proof, but it does not reduce the conclusion to its input: the target 3/8 is not assumed in any form. The construction and counting are independent of any self-citation, so the circularity score is 1 only to acknowledge the presence of contextual self-citations; the derivation itself is self-contained.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

The central claim rests on standard geometric and probabilistic bounds plus two asymptotic construction parameters (b and k) that are taken to their limits. No new physical entities, fitted constants, or circular normalization are introduced.

free parameters (2)
  • b = 0 in limit
    Radius exponent r=n^b. The code construction and error bounds require b>0 for the projection distance lower bound 4n^b >= 2σ log n; the rate tends to its 3/8 limit as b -> 0.
  • k = ∞ in limit
    Hierarchy scaling factor; the spherical code angle θ = 2 arcsin(2/sqrt(k-2)) depends on k, and the rate tends to 3/8 as k -> ∞.
assumptions (4)
  • standard math Chabauty-Shannon-Wyner spherical code lower bound M(n,θ) >= (1/sin^n θ)
    Used in Section V.A to lower-bound |A^t_o(r,θ)| = M(n,θ)^t; the paper needs this asymptotic bound to compute the code size.
  • standard math Volume-based packing bound for centers with mutual distance >= 2n^{b+1/4}
    Used in Claim 1 to bound the number of galaxy centers inside the power sphere of radius √(nP).
  • standard math Gaussian tail bounds (Mill's inequality) and chi-square central limit approximation
    Used in Appendices A and B to bound P(S_u|u), P(S_u|v), and projection probabilities.
  • domain assumption Deterministic identification capacity definition with 2^{nR log n} scaling
    The entire capacity statement is made in this scaling, inherited from prior work [4].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Galaxy Codes: Advancing Achievability for Deterministic Identification via Gaussian Channels." pith.science (2026). https://pith.science/paper/CMRWPXFF

@misc{pith2026250112548,
  author       = {Pith},
  title        = {Pith review of: Galaxy Codes: Advancing Achievability for Deterministic Identification via Gaussian Channels},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CMRWPXFF}},
  note         = {Machine review of arXiv:2501.12548}
}
read the original abstract

Deterministic identification offers an efficient solution for scenarios where decoding entire messages is unnecessary. It is commonly used in alarm systems and control systems. A key advantage of this approach is that the capacity for deterministic identification in Gaussian channels with power constraints grows superexponentially, unlike Shannon's transmission capacity. This allows for a significantly higher number of messages to be transmitted using this event-driven method. So far, only upper and lower bounds for deterministic identification capacity have been established. Our work introduces a novel construction: galaxy codes for deterministic identification. Using these codes, we demonstrate an improvement in the achievability bound of 1/4 to 3/8, representing a previously unknown advance that opens new possibilities for efficient communication.

Figures

Figures reproduced from arXiv: 2501.12548 by the authors.

Figure 1
Figure 1. Projection of point and vector [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Illustration of a Galaxy of depth 1 and 2, when [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Illustration of a Galaxy of depth 3, when [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Rate-reliability tradeoff for deterministic identification

    cs.IT 2025-02 conditional novelty 7.0 of 10

    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.

Reference graph

Works this paper leans on

17 extracted references · 14 canonical work pages · cited by 1 Pith paper

  1. [1]

    Ahlswede and G

    R. Ahlswede and G. Dueck, ``Identification via channels,'' IEEE Trans. Inf. Theory, vol. 35, no. 1, pp. 15--29, 1989

    work page 1989

  2. [2]

    C. E. Shannon, ``A mathematical theory of communication,'' Bell System Technical Journal, vol. 27, pp. 379--423, 623--656, July, October 1948

    work page 1948

  3. [3]

    JaJa, ``Identification is easier than decoding,'' in 26th Annual Symposium on Foundations of Computer Science (sfcs 1985)

    J. JaJa, ``Identification is easier than decoding,'' in 26th Annual Symposium on Foundations of Computer Science (sfcs 1985). 1em plus 0.5em minus 0.4em IEEE, 1985, pp. 43--50

    work page 1985

  4. [4]

    M. J. Salariseddigh, U. Pereg, H. Boche, and C. Deppe, ``Deterministic identification over channels with power constraints,'' IEEE Transactions on Information Theory, vol. 68, no. 1, pp. 1--24, 2021

    work page 2021

  5. [6]

    Vorobyev, C

    I. Vorobyev, C. Deppe, and H. Boche, ``Deterministic identification codes for fading channels,'' 2024. [Online]. Available: https://arxiv.org/abs/2404.02723

    arXiv 2024

  6. [7]

    Chabauty, Resultats sur l'empilement de calottes egales sur une périsphere de R^ n et correction a un travail anterieur , 1953, vol

    C. Chabauty, Resultats sur l'empilement de calottes egales sur une périsphere de R^ n et correction a un travail anterieur , 1953, vol. 236, mR0053975

    work page 1953

  7. [8]

    C. E. Shannon, ``Probability of error for optimal codes in a gaussian channel,'' Bell System Technical Journal, vol. 38, pp. 611--656, 1959, mR0103137

    work page 1959

  8. [9]

    A. D. Wyner, ``Capabilities of bounded discrepancy decoding,'' Bell System Technical Journal, vol. 44, pp. 1061--1122, 1965, mR0180417

    work page 1965

Show all 17 references
  1. [10]

    Deterministic Identification Over Fading Channels,

    M. J. Salariseddigh, U. Pereg, H. Boche and C. Deppe, "Deterministic Identification Over Fading Channels," 2020 IEEE Information Theory Workshop (ITW), Riva del Garda, Italy, 2021, pp. 1-5, doi: 10.1109/ITW46852.2021.9457587

    2020

  2. [11]

    Chabauty, C.[1953] Resultats sur l'empilement de calottes egales sur une p'erisphere de R^ n et correction a un travail anterieur. C. R. Acad. Sci. Paris 236 (1953) 1462-1464. MR0053975

    1953

  3. [12]

    379-423, 623-656, July, October 1948

    C.E.Shannon, A mathematical theory of communication, Bell System Technical Journal, vol.27, pp. 379-423, 623-656, July, October 1948

    1948

  4. [13]

    Shannon, C. E. [1959] Probability of error for optimal codes in a Gaussian channel. Bell System Tech. J. 38 (1959) 611-656. MR0103137, DOI 10.1002/j.1538-7305.1959.tb03905.x

    1959

  5. [14]

    Deterministic Identification Codes for Fading Channels

    Ilya Vorobyev, Christian Deppe, Holger Boche, 2024. Deterministic Identification Codes for Fading Channels. preprint

    2024

  6. [15]

    Sphere packing bounds via spherical codes

    Cohn, H., Zhao, Y. Sphere packing bounds via spherical codes. Duke Math. J. 163(10), 1965-2002 (2014)

    2014

  7. [16]

    Wyner, A. D. [1965] Capabilities of bounded discrepancy decoding. Bell Systems Tech. J. 44 (1965) 1061-1122. MR0180417, DOI 10.1002/j.1538-7305.1965.tb04170

    1965

  8. [17]

    Identification via channels

    R. Ahlswede and G. Dueck, "Identification via channels", IEEE Trans. Inf. Theory, vol. 35, no. 1, pp. 15-29, 1989

    1989

  9. [18]

    Deterministic identification over channels with power constraints

    M. J. Salariseddigh, U. Pereg, H. Boche and C. Deppe, "Deterministic identification over channels with power constraints", IEEE Intl Conf. Commun. (ICC), 2020, [online] Available: https://arxiv.org/pdf/2010.04239.pdf

    2020 arXiv

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.