WorksComputer Science
Polarization on Bounded Euclidean Spaces and More General Compact Groups
Abstract
We establish polarization for memoryless sources taking values on the unit-perimeter circle, or on more general compact groups, under Arıkan's polar transform. For sources with finite differential entropy, all but an fraction of the conditional differential entropies in successive cancellation order lie within any fixed positive distance of zero, where is the block length. Examples indicate that the true polarization rate is indeed very slow: an inverse-logarithmic rate does not underestimate the polarization speed at moderate block lengths.
Introduction
Given a source string consisting of independent and identically distributed (i.i.d.) source symbols taking values in some finite alphabet , a polarizing transform is a bijection that maps to a sequence whose conditional entropies,
approach either 0 or the logarithm of the alphabet size for all but a vanishing fraction of indices as grows. Arıkan [1, 2] identified a rich class of polarizing transforms for Bernoulli sources and introduced a linear construction with a recursive structure that admits a low-complexity implementation.
Polarization has since been studied for sources over larger discrete alphabets. The linear transform proposed by Arıkan, with addition defined modulo the alphabet size, has been shown [18] to be polarizing for prime alphabet sizes, and other polarizing transforms have also been identified [15, 17] for non-prime alphabet sizes. Further analysis on the speed of polarization for prime alphabet sizes has shown that the fraction of indices whose conditional entropies remain a fixed distance away from both extreme values decays at least polynomially fast in the block length [7].
In the case of continuous sources, the polarization phenomenon remains poorly understood. Distributions over the real numbers do not lend themselves to an unambiguous definition of polarization analogous to the discrete case, as the conditional differential entropies are unbounded in both directions; see [3] for a discussion on generalizing the notion of polarization to various continuous settings and the challenges involved.
We study polarization for sources taking values in bounded continuous spaces such as the circle , which we identify with the interval ; cf. [3 Example 5]. This is motivated in part by recent work that constructs lossy compression schemes by combining channel simulation [13] with nonlinear transform coding [5], with the channel simulation being performed using polar codes [19]. Nonlinear transform coding and related autoencoding-type architectures are known to struggle with compressing sources with 1-D group structure [6] when the latent variables are real-valued. One potential remedy is to use latent variables that themselves have a 1-D group structure. Doing so would require a channel simulator, say using polar codes, that simulates channels with this structure (cf. [19]).
Our main theoretical result here (Theorem 1 in § 2) establishes polarization for sources taking values in the circle or in more general compact groups. Specifically, we show that under the standard polar transform proposed by Arıkan, the fraction of transformed variables whose conditional differential entropy is bounded away from zero vanishes as the block length grows. Thus, most of the indices become nearly uninformative, with most of the information in the source concentrated in the remaining vanishing fraction of variables (cf. [3 Example 5]).
Moreover, we provide an explicit bound on the speed of polarization, showing that the vanishing fraction of informative indices is
where, throughout, denotes the natural logarithm and all familiar information-theoretic functionals are expressed in nats. While we certainly do not claim (or believe) that this bound is optimal, empirical evidence discussed in § 1 and § 4 suggests that the actual rate of polarization is indeed extremely slow, being comparable to .
Our analysis relies on a recent “entropy-jump” inequality for random variables on compact groups [10], which can be viewed as a stability result for an underlying entropy power inequality (EPI). The EPI-polarization connection is described in the following section; see also [9, 14] for related recent entropy lower bounds.
Entropy Inequalities on Compact Groups
For binary random variables, a particularly strong entropy-jump inequality follows from Mrs. Gerber’s lemma [20]. From Şaşoğlu [17, Lemma 2.2]} and Guruswami and Xia [12 (11)-(12)] we have that for i.i.d. on ,
with
where is the binary entropy function. This quantitative entropy jump is a key ingredient in the latter’s analysis of the speed of polarization. By a bootstrapping method similar to [4], it yields that for ,
where is the Bhattacharyya parameter of the -th sub-channel, is the mutual information of the channel, and the probability is over the uniformly selected index .
Interestingly, the later -ary analogue of Guruswami and Velingker [11] yields, for prime ,
but the quantitative value of furnished by their proof is extremely weak. In fact, already for , the quantitative estimate resulting from their general argument is vastly weaker than the sharp binary estimate based on Mrs. Gerber’s lemma. In the present work we use the entropy-jump inequality of [10 Theorem 2.10]. That estimate is significantly weaker but much more general than the entropy jump of the binary case (2). In addition, the related entropy-jump obtained in [10 Theorem 1.4] involves an extremely weak constant, with a value no greater than . Although we do not know whether sharper estimates exist, it is worth noting that the actual speed of polarization in the continuous setting seems to be quite slow as we discuss in § 4.
Main Result
Let be a standard Borel space, and let be a connected, compact, metrizable abelian topological group, equipped with its Borel -algebra. Let denote the normalized Haar measure on , so that . All familiar information-theoretic functionals are defined in terms of . For example, suppose takes values in and has law . If has a density with respect to , then the (differential) entropy is defined as ; otherwise, we set . In particular, the uniform distribution on has zero entropy and all entropies are nonpositive.
Let be a joint distribution on . We will refer to the corresponding marginal as the source distribution and the induced kernel as the channel. For any such joint distribution, we will assume throughout that the mutual information associated with the channel is finite and in fact that
Given i.i.d. pairs , we define the polar domain representation [2] as
where is the bit-reversal permutation. Our main contribution is the following finite- result.
Theorem 1. For all and ,
where .
Proof
We begin by examining a single recursive step of the polar transform.
Definition 2 (Pairwise polarizing transform). Let and be independent random variables with distribution on some standard Borel space . Given an arbitrary channel and conditionally independent channel outputs and , define their polar domain representations
For an arbitrary measurable subset of , define the transformed channels
and
We will denote this transform by
For a channel together with its induced input-output pair , we use the abbreviation
In particular,
We further write
for the pointwise output entropy corresponding to the input .
Starting from the channel , we define a binary tree in the usual fashion:
where and each . We then draw i.i.d. uniform Bernoulli samples to construct a random walk on the tree, with respect to which we can define the stochastic process
We can express our objective in terms of :
Lemma 3. The process is a martingale that converges almost surely.
Proof. The martingale property of follows from the fact that every pairwise polarizing transform is a entropy-preserving transform. Since the uniform distribution over is the maximum entropy distribution, it follows that . Convergence then follows from Doob’s supermartingale convergence theorem.
We consider the case where
since the bound in (8) holds trivially otherwise. We begin by defining two thresholds and ,
The condition from (25) ensures that
We also define the stopping times
and the stopped martingales and . We then have
Next, we derive upper bounds for each of the quantities in (32).
a) Upper bound on : For all , using the orthogonality of martingale increments,
The lower bound from Lemma 5 below gives
From the definition of the stopping time, it follows that . Therefore,
and hence,
Now, observe that
Applying Markov’s inequality with , we obtain
where the second step follows from (36).
b) Upper bound on : For all , we have
Taking expectations and rearranging, we obtain
for all , and hence,
Upper bound on
Markov’s inequality gives
Since we have that for all , it follows that , which in turn implies that , and therefore,
Substituting this in (42), we obtain
Using the above upper bounds in (32), gives
And substituting the definitions from (26) and (27) yields
completing the proof of the theorem. □
Remark 4. The results of Lemma 3 and Theorem 1 imply that the martingale converges to 0 almost surely:
On the other hand, whenever ,
therefore is not uniformly integrable and does not converge in . See the discussion and conjecture in [3 Example 5].
Lemma 5. Given , let be a binary string such that
Then, the transformed channels
satisfy
Proof. For almost surely-any pair of inputs and to the channels , applying the entropy-jump inequality in [10 Theorem 2.10] yields
where
Averaging over independent realizations of and and observing that, for ,
we obtain, using Jensen’s inequality,
Now, we can further bound,
From Jensen’s inequality we have that the entropy jump is nonnegative:
Using this and the identity
gives
Substituting (59) in (55), we obtain
The function is convex on the whole real line. Its supporting-line inequality at therefore gives
Rearranging terms,
which is the required result. □
Examples
Given a uniform source on the circle identified as the interval with modulo-1 addition, consider the additive cosine channel
where the noise is independent of and has density
for some . Under the polar transform in (7) applied to independent copies of and , we compute the subchannel densities using their Fourier parameterization [8] as
This representation includes the original channel density and is preserved under every recursive update in (9)-(10).
For several values of and , Figure 1 shows Monte Carlo estimates of the subchannel mutual informations
Figure 1. Mutual information per subchannel, as defined in (66), for the example in § 4. For any , the fraction of subchannels for which the mutual information exceeds tends to zero slowly with . The dotted line shows the mutual information of the unpolarized channel in (63). Note that the mutual information of the best subchannel increases without bound.
Each estimate is averaged over 100 independent trials, and the subchannels are ordered by their estimated mutual information. Figure 2 plots the fraction of the unpolarized channels, defined here as the fraction of indices for which nats, for increasing values of . The upper bound on the polarization rate from Theorem 1 is vacuous for the small values of considered here and is thus omitted from the plot. The reference curve in the figure suggests that the actual rate of polarization in this example is closer to .
Figure 2. The fraction of subchannels whose mutual information exceeds nats plotted against the function .
It is easy to see that the rate of polarization can be no faster than in the worst case. Suppose and is uniformly distributed over . Then for , the component with the smallest conditional entropy, , has a conditional distribution given that is uniformly distributed over an interval of approximate width with high probability. Thus we have
and
Since the average conditional entropy satisfies
it follows a fraction of the subchannels must have entropy bounded away from zero.
Thus one cannot hope to achieve fast polarization in general using Arıkan’s polar transform. Whether the polarization can be accelerated using other transforms, at least in examples of interest in applications, is a subject of ongoing work.
AI Statement
OpenAI’s ChatGPT 6.0 [16] was used to assist with editing the manuscript, exploring proof techniques, and developing the code for the simulations in § 4. In particular, the argument for the lower bound in equations (56)–(59) was suggested by ChatGPT. The authors take full responsibility for the contents in this manuscript.
References
- [1]Erdal Arıkan. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels. IEEE Transactions on Information Theory, 55(7):3051–3073, 2009.DOI
- [2]Erdal Arıkan. Source polarization. In 2010 IEEE International Symposium on Information Theory, pages 899–903. IEEE, 2010.DOI
- [3]Erdal Arıkan. Entropy polarization in butterfly transforms. Digital Signal Processing, 119:103207, 2021.DOI
- [4]Erdal Arıkan and Emre Telatar. On the rate of channel polarization. In 2009 IEEE International Symposium on Information Theory, pages 1493–1495. IEEE, 2009.
- [5]Jona Ballé, Philip A Chou, David Minnen, Saurabh Singh, Nick Johnston, Eirikur Agustsson, Sung Jin Hwang, and George Toderici. Universal transform coding. IEEE Journal of Selected Topics in Signal Processing, 15(2):339–353, 2020.
- [6]Sourbh Bhadane, Aaron B. Wagner, and Jona Ballé. Do neural networks compress manifolds optimally? In 2022 IEEE Information Theory Workshop (ITW), pages 582–587, 2022.arxiv.org/abs/2205.08518
- [7]Jarosław Błasiok, Venkatesan Guruswami, Preetum Nakkiran, Atri Rudra, and Madhu Sudan. General strong polarization. ACM Journal of the ACM (JACM), 69(2):1–67, 2022.
- [8]Alfredo De la Fuente, Saurabh Singh, and Jona Ballé. Fourier basis density model. In 2024 Picture Coding Symposium (PCS), pages 1–5. IEEE, 2024.
- [9]Lampros Gavalakis, Marcel K. Goh, and Ioannis Kontoyiannis. Entropy lower bounds and sum-product phenomena. arXiv e-prints, 2604.02333 [math.CO], April 2026.
- [10]Lampros Gavalakis, Ioannis Kontoyiannis, Sharang M. Sriramu, and Aaron Wagner. Entropy power inequalities in compact groups. arXiv preprint arXiv:2608.22534, 2026.arxiv.org/abs/2608.22534
- [11]Venkatesan Guruswami and Ameya Velingker. An entropy sunset inequality and polynomially fast convergence to shannon capacity over all alphabets. In 30th Conference on Computational Complexity (CCC 2015), volume 33 of Leibniz International Proceedings in Informatics (LIPIcs), pages 42–57. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015.
- [12]Venkatesan Guruswami and Patrick Xia. Polar codes: Speed of polarization and polynomial gap to capacity. IEEE Transactions on Information Theory, 61(1):3–16, January 2015.
- [13]Cheuk Ting Li. Channel simulation: Theory and applications to lossy compression and differential privacy. Foundations and Trends® in Communications and Information Theory, 21(6):847–1106, 2024.DOI
- [14]Rupert Li, Lampros Gavalakis, and Ioannis Kontoyiannis. Entropic additive energy and entropy inequalities for sums and products. IEEE Transactions on Information Theory, 72(3):1553–1568, March 2026.
- [15]Ryuhei Mori and Toshiyuki Tanaka. Source and channel polarization over finite fields and reed–solomon matrices. IEEE Transactions on Information Theory, 60(5):2720–2736, 2014.
- [16]OpenAI. ChatGPT. https://chatgpt.com/, 2026.
- [17]Eren Şaşoğlu. Polarization and polar codes. Foundations and Trends in Communications and Information Theory, 8(4):259–381, 2012.DOI
- [18]Eren Şaşoğlu, Emre Telatar, and Erdal Arıkan. Polarization for arbitrary discrete memoryless channels. In 2009 IEEE Information Theory Workshop, pages 144–148. IEEE, 2009.arxiv.org/abs/0908.0302
- [19]Sharang M. Sriramu, Rochelle Barsz, Elizabeth Polito, and Aaron B. Wagner. Fast channel simulation via error-correcting codes. Advances in Neural Information Processing Systems, 37:107932–107959, 2024.DOI
- [20]Aaron D. Wyner and Jacob Ziv. A theorem on the entropy of certain binary sequences and applications: Part I. IEEE Transactions on Information Theory, 19(6):769–772, November 1973.DOI