# Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ?

Everything over F_2. Let us define Hamming norm of polynom |p(x)| = number of non-zero monoms.

Respectivly for a pair of polynoms |[p ; g]| = |p| +|g|.

Consider linear map $F_2[x] \to F_2[x] \oplus F_2[x]$ given by $p(x) \mapsto [ p(x)(x^2+1) ; p(x) (x^2+x+1)]$.

Question Is it true that minimal Hamming norm in the image of the map above equal to 5 ? Of course, delete [0; 0] from the image.

It is clearly not more than 5, since take p(x)=1, then $1 \mapsto [ x^2+1; x^2+x+1]$. and $|x^2+1| =2$ $x^2+x+1 = 3$ , So 2+3 =5.

By brute force search for p(x): deg p <16 the answer is 5.

On the other hand it is clearly more than 4. Since when multiply any two non-monoms we will get non-monom and hence norm of each product is not less than 2.

However if I take x+1, x^2+x+1 the corresponding answer will be 4, because take p(x)= x+1, we will get:

[(x+1)(x+1); (x+1) (x^2+x+1)] = [x^2 + 1; x^3+1] - only 4 monoms so norm is 4.

This is toy model for convolutional error correcting codes.

PS

The answer can be obtained by Viterbi algorithm as Jyrki Lahtonen suggests. However the question is so much down-to earth that probably some simple reason may exist

PSPS

Here is distribution of Hamming weights of image for p(x) deg p(x)<17

0, 0, 0, 0, 17, 31, 56, 100, 176, 409, 850, 1627, 2888, 4713, 7202, 10109, 13080, 15442, 16232, 15514, 13673, 10729, 7664, 5230, 2992, 1309, 630, 315, 70, 7, 6, 0, 0, 0, 0, 0, 0, 0, 0, 0,

It is like Gaussian.

-
You can get the weight distribution of such words that enter the zero state of the trellis only at the beginning and at the end from a suitable generating function. –  Jyrki Lahtonen Jul 25 '12 at 6:40
Related question: math.stackexchange.com/questions/177465/… –  Alexander Chervov Aug 1 '12 at 10:28
add comment

## 1 Answer

Yes. Without loss of generality, we can assume $p(x)$ is not divisible by $x$. Then $p(x)(x^2+1)$ and $p(x)(x^2+x+1)$ both have constant term $1$, so the combined Hamming weight is at least $4$ from the constant and leading terms. The only way it could be $4$ is if they were $x^n+1$ and $x^m+1$ for some $n$ and $m$. However, $p(x)(x^2+1)$ and $p(x)(x^2+x+1)$ have the same degree and are not equal to each other, so this cannot be the case.

-
Ah... Thank you very much ! I should think more before asking... Well, any way the bigger question behind is the following : can we generate some other examples of g1(x) g2(x), such that we can guarantee that norm of image is |g1|+|g2| ? How to describe all such g ? –  Alexander Chervov Jul 24 '12 at 13:35
Maybe you should post that as a new question. –  Gerry Myerson Jul 25 '12 at 5:55
–  Alexander Chervov Jul 26 '12 at 13:56
Related question math.stackexchange.com/questions/177465/… –  Alexander Chervov Aug 1 '12 at 10:28
add comment