14 - Polynomials of finite codes

Summary

There is a noncommutative polynomial canonically associated with a finite code: it is the sum of the codewords, minus 1. When the code is maximal, this polynomial has some striking factorization properties, which reflect probabilistic and combinatorial properties of the code, such as the property of being prefix, suffix or synchronizing. When the code is prefix, the factorization is directly related to the tree representation of the code. When the code is bifix, one has even more combinatorial evidence for the factorization, as described in Chapter 6. In the general case, the factorization of the polynomial has no direct combinatorial interpretation, but is related via the factorization conjecture to a kind of coset decomposition of the free monoid with respect to the submonoid generated by the code. The factorization conjecture is the main open problem in the theory of codes.

The chapter is organized as follows. In Section 14.1 we define positive factorizations. In Section 14.2, we state the factorization theorem (Theorem 14.2.1), which is the main result of this chapter. Section 14.3 presents some results on noncommutative polynomials which are used in the proof of the factorization theorem. Section 14.4 contains the proof of the theorem. Section 14.5 presents some applications of the factorization theorem.

Section 14.6 introduces another equivalence, called the commutative equivalence. It is conjectured that any finite maximal code is commutatively equivalent to a prefix code. This is a consequence of the factorization conjecture. Indeed, it is shown that any positively factorizing maximal code is commutatively prefix (Corollary 14.6.6).