1
$\begingroup$

Consider polynoms f(x) g(x) of degree at most n. (I am mostly interested about F_2[x]).

Let us multiply them by arbitrary polynoms p(x) i.e. consider ideal (p f , p g) in $F_2[x]\oplus F_2[x]$.

Let us delete zero from this ideal and calculate N(f,g) - Hamming distance of I$\backslash${0} to {0}. (Here Hamming distance is just the number of non-zero monoms).

Questions What is Max_{f,g of degree n} N(f,g) ? (Or at least some bounds on it ?) What polynoms give this max ?


What seems not trivial:

It is clear that N(f,g) <= |f| + |g| (take p(x) =1 ) .

So it seems that we should take |f| and |g| of maximal possible Hamming norm i.e. g = f = x^n+x^{n-1} + ... x^2 +x +1

But it clear that N(f,g) =4 for this choice of f,g - i.e. very small. (Proof - just multiply them by p(x) = (x+1)).

So these two effects are fighting each other - we want to take |f| , |g| big, but multiplication by x+1 will spoil N(f,g) if these norms are too big....


Related question

Find polynoms f,g such that for any polynom p(x): |fp|+|gp|>= |f|+|g| ? Where |*| is number of non-zero monoms.


From coding theory viewpoint

map: p(x) -> (p f , p g) is encoder (non-recursive convolutional code of rate 1/2).

I am asking what is "best possible" code for deg f,g


Examples

if n = 2, then f=x^2 +1 , g= x^2+x+1 gives max which equal to 5

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

If n=3 then max N(f,g) = 6 and can be realized by many choices e.g. f=x^3+x^2+1, g=x^3+x+1 or f=x^3+x^2+x+1, g=x^3+x+1 (if I am not mistaking).

If n=4, then possibly(?) max N(f,g) = 8 for e.g. f=(x+1)(x^3+1) ; g=(x+1)(x^3+x+1) ------ NOT TRUE : take p(x)=x^2+x+1, we get N(f,g)<=6 for these pols. It might that max N(f,g) = 7. achieved on e.g. f=x^4+x^3+x^2+1 g=x^4+x+1

$\endgroup$
2
  • $\begingroup$ Related question math.stackexchange.com/questions/177465/… $\endgroup$ Aug 1, 2012 at 10:27
  • 1
    $\begingroup$ Alexander Vardy showed in 1997 that computing the minimum distance of a binary linear code is a NP-hard problem, and Daniele Micciancio, Ilya Dumer and Madhu Sudan showed in 2003 that computing the minimum distance approximately (to within a constant factor) is also NP-hard. I would suspect, and will not at all be surprised if I am told that it already has been proven, that the same would apply to your problem, which is essentially that of computing the free distance of a convolutional code. $\endgroup$ Aug 1, 2012 at 13:43

1 Answer 1

3
$\begingroup$

The following simple (suboptimal) bound will get you started. It is easier to give a lower bound for the degree $n$ of the polynomials in terms of the minimum distance $d$, so I will do that. Feel free to turn this into an upper bound on $d$ :-)

From the theory of biinary linear block codes we recall the so called Griesmer bound. It states that if a binary linear code has dimension $k$, minimum distance $d$ and length $N$, then we have the inequality $$ N\ge\sum_{j=0}^{k-1}\lceil\frac{d}{2^j}\rceil. $$

We apply this to convolutional codes of the type that you describe as follows. Consider the subspace gotten by restricting the multiplier $p(x)$ to be of degree $\le m$. The dimension of this subspace is $k=m+1$. The degrees of $pf$ and $pg$ are both at most $n+m$, so the pairs $(pf,pg)$ have $N=2(n+m+1)$ coefficients. Thus Griesmer bound gives us the inequality $$ 2(n+m+1)\ge\sum_{j=0}^m\lceil\frac{d}{2^j}\rceil. $$

How to select $m$? When we increase $m\to m+1$, the l.h.s. increases by two, and the r.h.s. increases by $\lceil d2^{-m-1}\rceil$. Therefore we get the tightest bound on $n$, when $m$ is the largest natural number with the property $d>2^{m+1}$, because this is the largest $m$ such that all the terms on the r.h.s. are larger than two.

As examples consider $d=5$. Then we select $m=1$, and get the bound $$ 2(n+2)\ge 5+3\implies n\ge 2. $$ This bound is attained with the well known pair $f(x)=1+x^2$, $g(x)=1+x+x^2$. If we used $d=6$ instead, we would get $n\ge3$, so we can conclude that $d=5$ is the best we can do with quadratic $(f,g)$.

If we want $d=9$, then we can select $m=2$, and $$ 2(n+3)\ge 9+5+3=17\implies n\ge 6 $$ (bearing in mind that $n$ is an integer). We see that $d=10$ also gives $n\ge 6$, but $d=11$ would give $n\ge 7$. This implies that with sextic $(f,g)$ the best we can hope for is $d=10$. This bound is actually achieved by the pair $$ f(x)=1+x+x^3+x^4+x^6,\qquad g(x)=1+x^3+x^4+x^5+x^6. $$ IIRC this code was used during the Voyager mission to transmit data (e.g. the pretty images) back to Earth.

The above bound is not always accurate. There are several reasons for this. When $k$ increases, the Griesmer bound is no longer tight. Also, there is no reason to think that the type of binary linear codes by limiting the degree of $p$ would be optimal binary linear codes. Bounds like this will give you an idea, what to expect, and then you can start developing a search heuristic. If there is a precise answer to your question, then it will need to use some new machinery.

$\endgroup$
14
  • $\begingroup$ Thank you for the answer ! I need to some time to think. By the way what is "IIRC" ? $\endgroup$ Jul 30, 2012 at 11:25
  • 1
    $\begingroup$ "If I Recall/Remember Correctly" $\endgroup$ Jul 30, 2012 at 11:26
  • $\begingroup$ Is it known how Max N(f,g) grows with n? Obvious bound is 2n + 2 but it is not achievable. So is growth linear with respect to n? If yes what is slope? $\endgroup$ Jul 30, 2012 at 13:00
  • $\begingroup$ When I first posted this comment, I accidentally reversed the inequality sign, sorry! I think that this bound shows that the slope is at most 1. I don't know, if a non-zero lower bound for the slope is known. According to the tables in Johannesson & Zigangirov dfree>n when $n\le24$. Assuming $(f,g)$ were chosen optimally, of course. $\endgroup$ Jul 30, 2012 at 15:08
  • $\begingroup$ The brackets which you use [ ] is it floor ceiling or round? Comment. If m=1 the inequality is the same as my N(f g)<norm f + norm g. $\endgroup$ Jul 30, 2012 at 16:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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