4
$\begingroup$

Special task from NASA to best MSE minds (joking:).

Consider two polynoms over $F_2$

$$ f(x)=1+x+x^3+x^4+x^6,\qquad g(x)=1+x^3+x^4+x^5+x^6 $$

Prove or disprove that for any polynom $p(x) \in F_2[x]\setminus\{0\}$ $$ |pf|+|pg|\ge 10,$$ where $|\cdot|$ is number of non-zero monoms.

Remark 1: Clearly bound is sharp - take $p(x)=1$ we get $|f|+|g|=10$

Remark 2: See this discussion for motivation, history, etc.

Remark 3: This question is more for fun, I think it is quite nice since it is "everyone can understand" but demonstrates real problems in the theory of convolutional codes, so might be used as exercise in teaching, that it is why I would like to share it. I am afraid that there is no nice solution exists - one should consider many cases... What would be really great to find some "idea-based and short" solution to this puzzle, but may be there is no such... (Some solution (probably not nice) should be somewhere in the literature on convolutional codes).

P.S.

All good in question is from Jyrki Lahtonen, all bad from me.

P.S.P.S.

The sense of the question is about: prove that certain error-correcting code is "good".

Think of coefficients of $p(x)$ as information bits you want to transmit. Encoder sends $p(x)$ to pair $(pf, pg)$ so you add redundancy bits before transmission. If equality is true means that code is able to correct $4$ errors ($4+4<10$).

Gossips say that this code has been used in Voyager mission to transmit these pretty pictures. Thanks for "draks" for link to pictures.

  • 1
    How is Voyager related? And which Voyager: Voyager 1&2, [Voyager 6](http://en.wikipedia.org/wiki/Star_Trek:_The_Motion_Picture#Plot), Star Trek:Voyager ...2012-08-01
  • 0
    @draks Quote from http://mathoverflow.net/questions/103497/what-are-best-polynoms-fx-gx-of-degree-n-i-e-ideal-generated-by-them-is/103509#103509 "IIRC this code was used during the Voyager mission to transmit data (e.g. the pretty images) back to Earth"2012-08-01
  • 0
    Ah ok, I didn't see...but I remember the [pretty pictures](http://en.wikipedia.org/wiki/Pale_Blue_Dot)...2012-08-01
  • 1
    A teaser is that $g(x)$ is a factor of $x^{15}+1$ and $f(x)$ is a factor $x^{63}+1$, so a suitable choice of $p$ will make $|pf|$ or $|pg|$ equal to two.2012-08-01
  • 2
    I hazard a guess that [these pictures](http://voyager.jpl.nasa.gov/image/saturn.html) were also transmitted using this code.2012-08-01
  • 0
    Look for algorithms for finding the _free distance_ of a convolutional code. In most cases, substantial computation is required, and there are no easy answers or proofs, and no _useful_ bounds that are easy to compute. I definitely recommend against using this as an _exercise_ in teaching, unless the intent is to get the students to develop their own algorithms for the task.2012-08-01
  • 0
    @DilipSarwate Thank you for yours comment. May be you right, exercise a bad word, may be complicated puzzle is better... What is not quite clear for me about "no easy answers or proofs, and no useful bounds " is that - is it known that any bound will be complicated or just this is open problem to find good bound ? E.g. may I ask you to look at http://mathoverflow.net/questions/103497/what-are-best-polynoms-fx-gx-of-degree-n-i-e-ideal-generated-by-them-is/103509#103509 any comments are welcome !2012-08-01
  • 0
    @Alexander Chervov See my answer on mathoverflow. For linear binary _block_ codes, finding the minimum distance (even approximately, i.e. to within a constant factor) is a NP-hard problem. The same should presumably be true of the free distance problem.2012-08-01
  • 0
    @DilipSarwate Thank you for yours comments ! Probably a part of my question is complicated and may be NP, but there is the following YES/NO sub-question: Is it true that Max_{f,g, deg = n} MinDist(f,g) > n ? I think yes, what is sharper bound ? may be n +log(n) or n+sqrt(n) ? What is known about it ?2012-08-01

1 Answers 1

4

Apologies for providing the opposite of the "idea-based and short" solution you asked for: A computer search shows that, as you suspected, $|pf| + |pg| \ge 10$ for all non-zero $p\in\mathbb F_2[x]$.

Assume that $p\in\mathbb F_2[x]$ is a counterexample. Then we can divide by the lowest power of $x$ and still have a counterexample, so without loss of generality we can assume that $p$ has a constant term (which implies that both $pf$ and $pg$ have a constant term). We can then search the decision tree of coefficients of increasing powers; each decision about a coefficient determines the corresponding coefficients of the products, which are not influenced by later decisions about coefficients of higher powers. Thus, in searching the decision tree depth-first, we can keep track of the number of non-zero coefficients that will no longer change, and give up on a branch as soon as it reaches $10$.

The search tree only has $1065$ leaves, at a maximal depth of $23$. The code can be tested somewhat by replacing $10$ by $11$, which causes it to descend down the tree indefinitely with $p=1$.

  • 0
    Thank you for answer ! No need for excuse any idea is welcome. But I do not quite understand. How do you restrict the search to finite number ? What means "We can then search the decision tree of coefficients of increasing powers; each decision about a... " . Please can you comment that your method will NOT work in case we ask same question about only "f" or "g" , I mean there exists p: |pf|<|f|.2012-08-01
  • 1
    +1 Sounds like joriki independently discovered the use of modified Viterbi algorithm [also described here](http://mathoverflow.net/questions/102434/given-g1x-g2x-minimize-over-px-hamming-weight-of-pxg1-pxg2x-o/102673#102673). At least something very similar.2012-08-01
  • 0
    @Alexander: Have you taken a look at the code? That might help. Let $p=1+c_1x+c_2x^2+\dotso$. The code branches for the two possibilities $c_1=0$ and $c_1=1$. In either case, $c_1$ determines the linear coefficients in the products. If $c_1=0$, then $pf$ has a linear term, and if $c_1=1$, then $pg$ has a linear term. This is independent of the remaining coefficients $c_2,\dotsc$. So on both branches the search continues with a count of $3$ (two for the constant terms in both $pf$ and $pg$, one for the linear term in one of them). Once it reaches $10$, the branch can no longer yield a solution.2012-08-01
  • 0
    @Alexander: Regarding your question about only $f$ or $g$: If you're only minimizing the number of monomials in a single product, you can go on indefinitely without ever producing a single unalterable non-zero coefficient (except the constant term) -- in this case the search would descend down the tree indefinitely, independent of whether there is in fact a solution.2012-08-01
  • 0
    @joriki so do you mean that you do not a'priori know that you alg. will stop at finite time ? "The search tree only has leaves, at a maximal depth of " is this outcome of algorithm or you know this a'priory ?2012-08-01
  • 0
    @Alexander: This is the outcome of the algorithm, and yes, I don't know *a priori* whether it will stop in finite time -- in fact, as I wrote, it doesn't if you bound with $11$ instead of $10$. It will descend indefinitely (or rather run out of stack space) if there is a solution (and in some cases even if there isn't one), but if the search terminates, that means there's no solution. (In case you're wondering, I didn't include the code to count the leaves and determine the maximal depth, to keep the code short; it's just a couple of lines to add.)2012-08-01
  • 0
    @joriki Thank you ! It is more clear now.2012-08-01