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.


See the question [Given g1(x), g2(x) minimize over p(x) Hamming weight of [p(x)g1; p(x)g2(x) ] ? (Or how to find minimal distance of convolutional code?)](https://mathoverflow.net/questions/102434/given-g1x-g2x-minimize-over-px-hamming-weight-of-pxg1-pxg2x-o)




---


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.



Multiplication by polynomials x^2+1 ; x^2+x+1. Does minimal Hamming norm of image equal to 5 ? 
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.


