Polar Code ARE Fractal!

This is a post about very recent work that has not yet been reviewed, but is publicly available on arXiv. This is not science by press conference, but hopefully encouraging discussions and comments from other researchers in the field.

At least, that is what I found out -- I'm pretty confident of the correctness of the results, but, you know, mistakes happen all the time. If you feel that some of my derivations may have flaws, I'd be happy if you could contact me!

Alright, regarding the questions in one of my previous blog post, what have I found out? Here's the short version, for more details please take a look at the paper on arXiv:

• The set of good channel $\mathcal{G}$ is Lebesgue measurable, and its Lebesgue measure is $I(W)$, the capacity of the (unpolarized) channel. This is intuitive in the sense that a fraction of $I(W)$ channels will be polarized to perfect channels. From this immediately follows that the Hausdorff dimension of this set is one.
• The dyadic rationals are good and bad. This is because dyadic rationals have two possible binary expansions, one terminating (with infinitely many zeros) and one repeating (with infinitely many ones). While the former polarizes the channel to a useless one, the latter polarizes it to a perfect one.
• Even if we do not take into account the dyadic rationals, the good channels still form a dense subset of the unit interval. The reason is that between any two dyadic rationals we can find a rational number (with repeating binary expansion) which leads to a good channel. For the binary erasure channel we can also find a rational number leading to a bad channel, so we can say a little more about BECs.
• And finally, the set of good channels is indeed self-similar, in the sense that it is a subset of its (scaled and shifted) right half (and left half for BECs). This can be most easily explained by a picture:

This picture (generated by the following code, polynomial composition from this forum) shows the thresholds on the Bhattacharyya parameter for some values inside the unit interval: If the Bhattacharyya parameter is smaller than the threshold, then the channel will polarize to a perfect channel. It can be seen that the right half (top) is an upper bound on the original set (center), which is (for BECs) an upper bound on its left half (bottom).

The most useful tools to derive these results were results about the binary expansion of real numbers, about fixed points of dynamical systems, and the Tal-Vardy polar code construction technique.