# Posts Tagged ‘Polynomials’

## Two points determine a line, three a quadratic — what has that got to do with CDs?

July 24, 2014 by Jyrki Lahtonen. 4 comments

In this post I describe how simple facts about polynomials are applied in correcting errors, for example scratches on compact disks.  The same technique is used in many other places, e.g. in the 2-dimensional QuickResponse  bar codes.

## Elements

The two facts from algebra that we need are:

Theorem 1. A polynomial of degree $$n$$ has at most $$n$$ zeros.

Theorem 2. If $$(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$$ are $$n$$ points on the $$xy$$-plane such that $$x_i\neq x_j$$ whenever $$i\neq j$$, then there is a unique polynomial $$f(x)$$ of degree $$<n$$ such that $$f(x_i)=y_i$$ for all $$i$$.

So, if $$n=2$$, we want the polynomial $$f(x)$$ to be linear. In that case, the graph $$y=f(x)$$ will be the line passing through the points $$(x_1,y_1)$$ and $$(x_2,y_2)$$. Similarly, when $$n=3$$ we want the polynomial to be (at most) quadratic, and we want its graph to pass through the given three points. Finding the coefficients of such a quadratic is not too arduous an exercise in linear systems of equations. For general $$n$$ there is a known formula for the polynomial $$f(x)$$ called Lagrange’s interpolation polynomial . The uniqueness of such a polynomial follows from Theorem 1. If $$f_1(x)$$ and $$f_2(x)$$ were two different polynomials of degree $$<n$$ passing through all these $$n$$ points, then their difference $$f_1(x)-f_2(x)$$ is also of degree $$<n$$ and vanishes at all the points $$x_i, i=1,2,\ldots,n$$, which is impossible by Theorem 1.

## Extending a message using a polynomial

The applications I discuss are about communication. We have two parties, a transmitter and a receiver. The transmitter wants to send a message to the receiver. We assume that they have in advance agreed upon a method of coding the messages to sequences of numbers $$y_1,y_2,\ldots,y_k$$ for some natural number $$k$$. The simplest way of communicating would be for the transmitter to simply write this list of numbers to a channel that the receiver can later read. The channel could be something like a note that you pass to a classmate or it could be compact disk, where the transmitter just writes the numbers. It could be something fancier like a radio frequency band, or an optical fiber, but we ignore the physical nature of the channel here.

more »