Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Let us consider polynoms over $F_2$. Consider the linear SUBSPACE of polynoms divisible by $x^{16}+x^{12}+x^5 +1$ and of degree less or equal $N$ (e.g. 40).

Question: How many k-nomials belong to this subspace ?

By k-nomials I mean polynom containing only $k$ monomials, e.g. x^2+x - is 2-nomial.


Motivation and more general question

$g = x^{16}+x^{12}+x^5 +1$ is generating polynom for the CRC-16-CCITT error-correcting code. I am intersting about the Hamming weight distribution for the code-words, it is important characteristics of the code.

Question More generally we can take other "generating polynoms" and ask a similar questions, what is known about it ?


Examples

k =1 , answer = 0, rather obviously for all N.

k = 2 , answer = 0, (Wrong as Douglas Zare pointed in his answer)

k= 3 , answer = 0 , AFAIU (=as far as I understand)

k= 4 , answer N-15 , AFAIU (Wrong as Douglas Zare pointed in his answer)

Some guess based on numerical experiments

it seems the distribution is Gaussian like near its maximum - it seems that it does not depend much on polynomial (only tails depends), so we can take polynomial to be just g=x^16, for which the answer is obviusly binomial coefficient (N-16, k), which behaves like Gaussian by central limit theorem.

Questions Is this guess reasonable ? It is is correct what is the deviation of real distribution and gaussian ? What happens with tails ?

share|improve this question
    
Why is the subspace property important? I would have thought that if it were essential, you would mention the case $k=0$ in your list of examples. –  S. Carnahan Jul 5 '12 at 9:00
    
May be I should not use upper case for "subspace"... Error-correcting code is just "subset" if this subset is subspace it is caller "linear". If it is linear all codewords (elements of the subspace) have the same probability to be misdecoded. –  Alexander Chervov Jul 5 '12 at 9:47
    
P(x)=0 is divisible by anything so it is "codeword" Code is good if distance between codewords is big, distance between P(x)=0 and some f(x) is exactly number of monoms in f(x). So this number characterizes the quality of the code –  Alexander Chervov Jul 5 '12 at 10:11
    
AFAIK this is a bit of a black art, but as the selection of the best CRC-polynomial is important, a lot of effort has been spent on it. I know very little about this topic, but will testify that there is no simple answer to this question. The first google hit springerlink.com/content/7231510310uk7767 does sound promising, and probably contains references to more basic results/algorithms. –  Jyrki Lahtonen Jul 5 '12 at 11:52
    
@Jyrki Lahtonen I made numeric experiments. It seems that the distribution is Gaussian with mean at codelenght/2, which I think is natural. Probably the hard thing is analysis of tails of the distribution ... –  Alexander Chervov Jul 5 '12 at 12:35
show 1 more comment

1 Answer

Your examples are wrong for large $N$. For large $N$, you can classify and count the polynomials with few terms divisible by $g$ by considering the powers of $x$ in $F_2[x]/g$. By the pigeonhole principle, some $x^a \equiv x^b \mod \langle g,2 \rangle$, which implies there are binomials divisible by $g$ for any $g$. In particular, $(x^{16}+x^{12}+x^5+1) ~|~ x^{32767} + 1 = x^{2^{15}-1}+1$. If the polynomial is chosen well, then $x$ may be primitive in $F_2[x]/g$, which would mean that the only binomials would be ones where $(2^{\deg g}-1) | (a-b)$.

Since $x^{16}+x^{12}+x^5+1$ has an even number of terms it is divisible by $x+1$, which can't divide any trinomial or other polynomial with an odd number of terms, so $x^{16}+x^{12}+x^5+1$ can't either. If $g$ were irreducible with $x$ primitive in $F_2[x]/g$, then for any $0 \le a \lt b \lt 2^{\deg g}-1$, there is a unique $0 \le c \lt 2^{\deg g}-1$ so that $x^a + x^b + x^c$ is divisible by $g$, and $c$ can't equal $a$ or $b$. It is possible when $x$ is not primitive that there don't have to be any trinomials divisible by $g$, e.g., $g = x^4 + x^3 + x^2 + x + 1$ does not divide any trinomials.

Similarly, if $g$ is irreducible and $x$ is primitive in $F_2[x]/g$ then $4$-nomials divisible by $g$ of degree up to $2^{\deg g}-1$ correspond to sums $\vec{v_1} + \vec{v_2}+\vec{v_3}+\vec{v_4} = 0$ where the $\vec{v_i}$ are distinct nonzero vectors in a $(\deg g)$-dimensional vector space over $F_2$, and these can be counted by inclusion-exclusion.

Your $g = (x+1)g_{15}$, where $g_{15} = x^{15}+x^{14}+x^{13}+x^{12}+x^4+x^3+x^2+x+1$ is an irreducible degree $15$ polynomial so that $x$ is primitive in $f_2[x]/g_{15}$. So, there are many $4$-nomials which are divisible by $g_{15}$ hence by $g$ which are not just $x^n \times g$. For example, $x^{16}+x^{12}+x^5+1 ~|~ x^{12496} + x^2 + x + 1$.

share|improve this answer
    
@Douglas Zare thank you very much ! Indeed I was wrong. I added some guess about the distribtion. I would be happy if you comment on this. The guess is simple - distribution is the "same" as for g=x^16, for which it is obviously binomial coefficient (N-16,k) –  Alexander Chervov Jul 6 '12 at 9:52
    
If $g$ is divisible by $x+1$ then there is a parity issue, but perhaps other than that the distribution could look roughly Gaussian near the center. In other words, perhaps the probability that a random polynomial of weight $k$ is divisible by $g$ is roughly constant. You can prove that there are many polynomials with weights close to $N/2$ which are divisible by $g$ since there are many multiples of $g$, and not so many polynomials with weights far from $N/2$. –  Douglas Zare Jul 6 '12 at 19:41
    
This is, of course, correct. But for exactly this reason (any polynomial over $GF(2)$ is a factor of a binomial) all the CRC-polynomials come together with a maximum length for the data packet that you can protect it with. The range of interesting values of $N$ has an upper bound. I'm afraid I don't remember what it is for this particular CRC-polynomial. –  Jyrki Lahtonen Jul 7 '12 at 7:45
    
As this polynomial has an irreducible primitive factor of degree 15, we must impose a restriction $N<2^{15}-1$. –  Jyrki Lahtonen Jul 7 '12 at 7:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.