Wednesday, December 18, 2013

Most of the time we take for granted that Technology works..
and doing computer science research you take for granted most of the time
that mathematics works.
But there are moments when you feel how remarkable it is.
You look at a string of 0's and 1's.
For example (1,0,1,0,0,0,1)
And you look at all it's cyclic shifts (where you move all bits one place to the right and move the last one back to the start)
The first shift gives you      (1,1,0,1,0,0,0)
The second shift gives you (0,1,1,0,1,0,0)
and so on..
You would like to prove that the 1's of the different shifts intersect with the original string on at most one coordinate:
For example: The original string has a one on the 1,3,7 indices.
                     The first shift has a one on the 1,2,4 indices
       so indeed they intersect on only one place.
Can you prove the intersection is always at most of size one without checking?
It turns out the following thing works.
There are these things called Galois fields
which are groups of numbers that are different from regular numbers.
For example in the Galois field GF(8)  we have 1+1 =0. Also, as the name implies - we have only 8 different numbers in this field - rather than infinitely many as we are used to with rational or real numbers.
In this field GF(8) there are special elements called generating elements.
These are elements g with the property that when you take their powers g,g^2,g^3...
they will run over all elements in the field except the 0 element.
Now say we take such a generating element g and compute the polynomial
whose roots are the powers of g corresponding to the 1's of our string - 1,3,7
and also 0
That is the polynomial
(x-g)*(x-g^3)*(x-g^7)*x  
It's easy to see this polynomial has degree 4.
What will be the coefficient of x^3?
It turns out that whenever it is 0, the cyclic shifts of the string will indeed intersect at atmost one place.
in the case above the polynomial we get (when doing computations in this field GF(8)) is
x^4 + (g^2 + g + 1)*x^2 + (g^2 + g)*x 

Which indeed has 0 as the coefficient of x^3
You can try it yourself here:
just plug in the powers you want when evaluating poly, and then press evaluate.
This corresponds to the fact that subspaces have an intersection size that is a power of 2 over GF(2)and polynomials whose roots are a subspace over GF(2) will only contain powers that are powers of 2.

No comments:

Blog Archive

About Me

My photo

Hi! I am a computer science postdoc. For some reason google is not finding my new homepage so I added a link from this profile