🔢 mathematics

Optimal Codes for Deterministic Identification over Gaussian Channels: Closing the Capacity Gap

This paper resolves a fundamental open problem in deterministic identification over Gaussian channels by constructing an optimal code that closes the long-standing gap between lower and upper bounds, thereby establishing the linearithmic capacity as 1/2 and demonstrating the existence of a universal code that achieves this capacity without requiring channel parameter knowledge.

Original authors: Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter

Published 2026-04-14

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Pau Colomer, Christian Deppe, Holger Boche, Andreas Winter

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding a Needle in a Haystack vs. Asking "Is it this Needle?"

Imagine you are at a massive party with millions of people.

The Old Way (Shannon Transmission):
You want to tell a specific friend, "Bob," a secret message. To do this, you have to describe Bob's face, his clothes, and his voice perfectly so he can identify himself among the crowd. You have to send a long, detailed description. This is like Shannon's classic communication: you are trying to transmit all the data so the receiver can reconstruct the whole picture.

The New Way (Deterministic Identification):
Now, imagine you don't need to send a description of Bob. Instead, you just want to ask the room a simple question: "Is Bob here?"
The receiver doesn't need to know who Bob is or what he looks like. They just need to answer "Yes" or "No" to that specific question.

The Magic: Because you only need to answer a "Yes/No" question, you can ask this about billions of different people using the same amount of time and energy it takes to describe just one person. This is the power of Identification.

The Problem: The "Gap" in the Rules

For a long time, scientists knew there was a theoretical limit to how many people you could check for in this "Yes/No" game over a noisy channel (like a radio with static).

The Upper Limit (The Ceiling): Math said, "You can check up to $X$ people."
The Lower Limit (The Floor): The best codes (strategies) scientists had built could only check up to $0.75 \times X$ people.

There was a gap between what was theoretically possible and what they could actually build. It was like knowing a bridge could hold 100 tons, but the best bridge engineers could build only held 75 tons. No one knew how to build the bridge to hold the full 100.

The Solution: A "Russian Nesting Doll" Strategy

The authors of this paper finally built that perfect bridge. They did it by changing how they look at the problem.

1. The Old Strategy: "Typicality" (The Blurry Photo)

Previously, scientists tried to identify messages by looking at the "average" behavior of the noise.

Analogy: Imagine trying to find a friend in a foggy park. You say, "My friend is usually wearing a red hat." If you see a red hat in the fog, you guess it's them.
The Flaw: In a very crowded park (high dimensions), many people might look like they are wearing a red hat just by accident. The "fog" (noise) makes it hard to distinguish between friends who are standing close together. This method hit a ceiling (the 3/8 limit).

2. The New Strategy: "Projective Layers" (The Target Practice)

The authors invented a new geometric way to organize the messages. They stopped looking at the whole picture and started looking at specific angles.

The Metaphor: Imagine a giant, multi-layered Russian Nesting Doll.
- Layer 1: You have a huge sphere. You place a few big dots on it. These are your "Main Groups."
- Layer 2: Inside the space around each big dot, you place a smaller sphere with more dots.
- Layer 3: Inside those, even smaller spheres with even more dots.
- The Trick: The authors realized that if you arrange these dots carefully, you can use projections (like shining a flashlight from a specific angle) to tell them apart.
How it works:
Instead of asking, "Is this the whole picture?", the receiver asks a series of very specific questions:
1. "Is the signal pointing roughly in Direction A?" (Yes/No)
2. "If yes, is it pointing in Direction B within Direction A?" (Yes/No)
3. "If yes, is it pointing in Direction C within Direction B?" (Yes/No)
Because the noise (static) usually pushes the signal sideways rather than forward/backward, checking these specific angles allows the receiver to ignore the noise and find the exact "dot" they are looking for, even if the dots are packed very tightly together.

The Result: Closing the Gap

By stacking these layers of "direction checks" (mathematically called angle-dense arrangements), the authors showed they could pack the messages as tightly as the laws of physics allow.

The Achievement: They proved the capacity is exactly 1/2 (in their specific math units). They closed the gap between the theoretical ceiling and the practical floor.
The "Universal" Bonus: Even cooler, they built a code that works without knowing the noise level.
- Analogy: Imagine a universal remote control that works on any TV, even if you don't know the brand or the volume settings. Usually, you need to tune your radio to the exact frequency of the station. This new code works perfectly even if you don't know how "loud" the static is.

Why Does This Matter?

Efficiency: In a world with billions of IoT devices (smart fridges, sensors, cars), we can't send full messages to everyone. We just need to know: "Is the fridge broken?" or "Is the car near the intersection?" This method allows us to check for millions of specific events instantly.
Reliability: They also proved that this method doesn't just work for the average case; it works even when we demand very high reliability (low error rates).
Simplicity: The math is complex, but the idea is surprisingly simple: Don't try to see the whole forest; just check if the trees are in the right rows.

Summary

The paper solves a 20-year-old puzzle in communication theory. By organizing messages like a multi-layered target practice system rather than a blurry photo, the authors built a code that is perfectly efficient for identifying specific messages over noisy channels, and it works even if you don't know exactly how noisy the channel is. They closed the gap, proving that the theoretical limit is achievable in the real world.

1. Problem Statement

The paper addresses the fundamental limits of Deterministic Identification (DI) over Additive White Gaussian Noise (AWGN) channels.

Context: Unlike Shannon's transmission paradigm (where the goal is to reconstruct the entire message, allowing a message set size $M \sim e^{nR}$ ), DI focuses on goal-oriented communication where the receiver only needs to decide if a specific message $m$ was sent or not. This allows for a much larger set of identifiable messages $N$ , potentially growing as $N \sim e^{e^{nR}}$ (double exponential) for stochastic encoders.
The Gap: While stochastic DI over Gaussian channels allows for linearithmic scaling ( $\log N \sim n \log n$ $lo g N \sim n lo g n$ ), the paper focuses on deterministic DI (no randomization allowed).
- Previous work established an upper bound on the linearithmic capacity $\dot{C}_{DI}(G) \leq 1/2$ .
- The best known lower bound was $\dot{C}_{DI}(G) \geq 3/8$ (achieved by a complex "galaxy" construction combining typicality and projection).
- Open Problem: A persistent gap existed between the lower bound ( $3/8$ ) and the upper bound ( $1/2$ ) for the linearithmic capacity and the rate-reliability tradeoff.

2. Methodology

The authors propose a novel, purely geometric construction based on orthogonal projections to close this gap. The methodology evolves through three stages:

A. Geometric Intuition: Projection vs. Typicality

Typicality-based approaches: Rely on the total norm of the noise vector. They require a minimum pairwise distance of order $O(n^{1/4})$ , limiting the rate to $1/4$ .
Projection-based approaches: Leverage the property that in high dimensions, a random Gaussian noise vector is almost orthogonal to any fixed direction. By testing projections onto specific directions rather than the total norm, the required separation can be reduced, allowing for denser packing.

B. The Multi-Layer Hierarchical Construction

The core innovation is a recursive, multi-layer geometric structure:

Layering: The code is constructed as a hierarchy of $L$ $L$ layers.
- Layer 1: Points are arranged on the surface of a high-dimensional ball (radius $r_1$ ) in a $d$ -angle-dense arrangement.
- Layer 2: Around each point in Layer 1, a new $d$ -angle-dense arrangement is placed on a smaller ball (radius $r_2 = \sqrt{r_1}$ ) embedded in the subspace orthogonal to the path vector connecting the origin to the Layer 1 point.
- Recursive Step: This continues for $L$ layers, with each subsequent layer residing in a subspace orthogonal to all previous path vectors.
Orthogonality Trick: By confining each layer to a subspace orthogonal to the "path vectors" of previous layers, the authors ensure that the projection of a point from a "wrong" branch (a different parent node) onto the current layer's path vector is negligible (bounded by $\delta \approx \sqrt{d}$ ). This prevents false identification between different branches of the hierarchy.
Decoding: The decoder performs a sequence of projection tests. For a message to be accepted, the received vector's projection onto the path vector of every layer must fall within a small threshold ( $\sigma \log n$ ) of the expected center.

C. Universal Code Construction

The authors refine the construction to create a universal code.

Challenge: Standard capacity-achieving codes usually require knowledge of channel parameters (noise variance $\sigma^2$ and power constraint $P$ ).
Solution: The authors redefine the radii and decoding thresholds to depend only on the block length $n$ (e.g., $r_\ell \sim n^{(1-b)/2^\ell}$ and threshold $\sim \log n$ ) rather than $\sigma$ or $P$ .
Result: They prove that for sufficiently large $n$ , these parameter-free codes still satisfy the power constraint and achieve the same asymptotic capacity, regardless of the specific channel parameters.

3. Key Contributions

Closing the Capacity Gap: The paper constructs an optimized code that achieves the linearithmic rate $\dot{R} = 1/2$ , matching the known upper bound. This definitively proves that the deterministic identification capacity of the Gaussian channel is $\dot{C}_{DI}(G) = 1/2$ .
Simplification of Prior Work: The proposed construction achieves the previous best rate of $3/8$ using a simple single-layer projection code (replacing the complex multi-layer "galaxy" structure of prior work) and then extends this to $1/2$ using a clean recursive multi-layer approach.
Universal Capacity-Achieving Codes: The paper demonstrates the existence of a universal DI code for Gaussian channels that does not require knowledge of the signal-to-noise ratio (SNR) or power constraints, yet achieves capacity. This contrasts sharply with Shannon transmission, where universal capacity-achieving codes generally do not exist without feedback.
Rate-Reliability Tradeoff: The authors analyze the tradeoff between rate and error probability. They show that their construction matches the known upper bound on the rate-reliability function to the first order in the regime of small error exponents (where errors vanish slowly, enabling superlinear scaling).

4. Key Results

Capacity: $\dot{C}_{DI}(G) = 1/2$ . The number of identifiable messages scales as $\log N \approx \frac{1}{2} n \log n$ .
Error Performance:
- Missed Identification: Bounded by $L \cdot 2\Phi(-\log n)$ , which vanishes as $n \to \infty$ .
- False Identification: Bounded by $2\Phi(-\log n)$ , also vanishing.
Rate-Reliability: For an error exponent $E(n)$ , the achievable rate is $R(n) \geq \frac{1}{2} \log \frac{1}{E(n)} + O(1)$ . This matches the converse bound derived in previous literature for small error exponents.
Universality: The code achieves the capacity $1/2$ without the encoder or decoder knowing $\sigma$ or $P$ .

5. Significance

Theoretical Breakthrough: This work resolves a long-standing open problem in Post-Shannon information theory, proving that the gap between lower and upper bounds for deterministic identification over Gaussian channels is non-existent.
Paradigm Shift: It establishes that projection-based geometric decoding is superior to typicality-based decoding for DI over continuous channels. Typicality is shown to be a fundamental limitation for achieving the full capacity in this context.
Practical Implications:
- Scalability: The linearithmic scaling implies that for large $n$ , one can identify an exponentially larger number of messages compared to transmission, which is crucial for massive IoT and 6G networks where devices need to be identified rather than fully communicated with.
- Robustness: The existence of universal codes suggests that identification systems can be deployed in environments with unknown or varying channel conditions without performance degradation in the asymptotic limit.
Future Directions: The paper suggests extending these geometric projection methods to channels with continuous inputs and discrete outputs (e.g., Poisson channels) and investigating the computational complexity of the decoding algorithm (which appears to be polynomial time).

In summary, the paper provides a rigorous geometric framework that not only closes the capacity gap for deterministic identification over Gaussian channels but also introduces robust, universal coding schemes that are optimal in both rate and reliability.