April 5, 2014 at 17:26Finite algebras, geometries and codes. Lecture by Grigory Kabatyansky in Yandex
Although almost everything in the world around us is of course, until recently, infinite objects dominated in mathematics. A serious interest in finite mathematics arose only half a century ago - with the advent of the first computers. And infinite (continuous) mathematics remains much more familiar and understandable for us.
This lecture is devoted to an amazing turn of history when finite fields (Galois fields), previously unfamiliar even to many professional mathematicians, suddenly became in demand by engineers, and how this changed our knowledge of the theory of finite fields and related objects.
To begin with, let's think about how to plant the maximum number Sp (n) of spiders on an n- dimensional cube so that they do not fight. A spider has n legs - one for each edge, while the length of the legs is equal to the length of the edge of the cube. The fight begins if two spiders reach the same peak. Can we achieve the perfect location: so that there is a spider on each peak? The following tasks can be attributed to the same class:
In three-dimensional space, everything is quite obvious: Sp (3) = 2 ? Since if we put two spiders at the vertices of a three-dimensional cube, then they are necessarily diametrically opposite, and occupy three outgoing vertices with their paws. There is nowhere to put a third spider.
When is the maximum number of spiders known?
Sp (3) = 2, Sp (4) = 2, Sp (5) = 4, Sp (6) = 8, Sp (7) = 16 ... ?
Sp (15) = 2 11 , Sp (14) = 2 10 , Sp (13) = 2 9 , Sp (12) = 2 8
But Sp (8) = 20, Sp (9) = 40, Sp (10) = 72, Sp (11) = 144
That Sp (10) ≥ 72; Sp (11) ≥ 144 was known for a long time, but it was possible to prove equality only in 1999.
We show that ifSp (2 r -1) = 2 2 r -1-r , then this is the perfect arrangement of spiders (or rooks with q = 2). Each spider occupies the top where it sits, and n = 2 r - 1 more vertices, where its paws reach. Total n + 1 = 2 r vertices are occupied by one spider, and their Sp (2 r -1) = 2 2 r -1-r = 2 n-r . Therefore, all the vertices of the cube are occupied - this is the perfect arrangement.
We define the set of C vertices where the spiders sit for n = 7 by a system of three linear equations.
x 1 ⊕ x 3 ⊕ x5 ⊕ x 7 = 0; x 2 ⊕ x 3 ⊕ x 6 ⊕ x 7 = 0; x 4 ⊕ x 5 ⊕ x 6 ⊕ x 7 = 0 , where a ⊕ b is the addition in mod2 , i.e. 1⊕1 = 0 ( mod2 ), and the rest - as usual.
We denote by H the matrix of coefficients of this system of linear equations:
Then this system can be rewritten as Hx T = 0. Note that inth column is a binary representation of i .
We need to prove that any binary 7-dimensional vector y "belongs" to exactly one spider, or, what is the same, the field y beats exactly one rook.
We compute s = Hy T . If s = (0, 0, 0) , then y ∉ C some kind of spider sits there. If s ≠ (0, 0, 0) , then s = h i is the i column of the matrix H for some i , and therefore c = y ⊕ e i ∈ C , where e iIs a vector of all zeros except 1, which is in the i- th coordinate. Then the spider sitting at the vertex c = y ⊕ e i , reaches paw to i -th coordinate axis of the vector y . If a spider sitting at the other vertex c 'would reach the vector y by its paw along the jth coordinate axis , then y = c' ⊕ e j and Hy T = Hc ' T + He j T = h j , which leads to a contradiction , since h i ≠ h j are all columns of the matrix Hare different. If i = j , then c '= c .
Imagine that we have a sequence of zeros and ones that we want to transmit over a channel in which transmission errors may occur in rare cases. When transmitting seven bits, we may either have no errors at all, or one error: one of the transmitted positions will be accepted in the opposite position. It is assumed that we have prepared a list of 16 words with a length of 7 bits. Words can be numbered with binary vectors of length 4. And then it turns out that the receiver will be sent 4 bits of information using 7 bits. This is of course overhead. There is an easier way: we can transmit each bit three times. If the transmission is allowed no more than one error, the incorrectly transmitted bit will be restored. But so we will transmit four bits with the help of twelve. Respectively, transmitting four bits through seven is more economical. Four out of seven bits will transmit information, and the remaining three bits will act as verification ones.
So, a vector of zeros and ones is transmitted. One of sixteen allowed. We do not know for sure whether a transmission error occurred. At the receiver, we need to know if one of the bits has moved to the opposite position. To do this, we take the vector that came out of the channel and insert it into our system of linear equations. If everything is satisfied, then this is a code vector, one of the allowed sixteen, transmission errors did not occur. And if some of the three equations are fulfilled, but some are not, then we write the unfulfilled as 1, and the unfulfilled as 0. We will get the same thing that we considered above: multiplying the matrix by a vector. If s is equal to 0, then the transmission passed without errors, otherwise an error occurred at position i .
Having watched the lecture to the end, you will learn how to determine exactly where the error occurred, about Hamming error correction codes, finite fields, and how all this is connected with ordinary mathematics.
This lecture is devoted to an amazing turn of history when finite fields (Galois fields), previously unfamiliar even to many professional mathematicians, suddenly became in demand by engineers, and how this changed our knowledge of the theory of finite fields and related objects.
To begin with, let's think about how to plant the maximum number Sp (n) of spiders on an n- dimensional cube so that they do not fight. A spider has n legs - one for each edge, while the length of the legs is equal to the length of the edge of the cube. The fight begins if two spiders reach the same peak. Can we achieve the perfect location: so that there is a spider on each peak? The following tasks can be attributed to the same class:
- How many can be placed on an n-dimensional chessboard of size q × q ... × q so that no field beats more than once?
- For what n and q does such a rook arrangement exist on an n- dimensional chessboard of size q × q ... × q such that each field beats once?
About spiders
In three-dimensional space, everything is quite obvious: Sp (3) = 2 ? Since if we put two spiders at the vertices of a three-dimensional cube, then they are necessarily diametrically opposite, and occupy three outgoing vertices with their paws. There is nowhere to put a third spider.
When is the maximum number of spiders known?
Sp (3) = 2, Sp (4) = 2, Sp (5) = 4, Sp (6) = 8, Sp (7) = 16 ... ?
Sp (15) = 2 11 , Sp (14) = 2 10 , Sp (13) = 2 9 , Sp (12) = 2 8
But Sp (8) = 20, Sp (9) = 40, Sp (10) = 72, Sp (11) = 144
That Sp (10) ≥ 72; Sp (11) ≥ 144 was known for a long time, but it was possible to prove equality only in 1999.
We show that ifSp (2 r -1) = 2 2 r -1-r , then this is the perfect arrangement of spiders (or rooks with q = 2). Each spider occupies the top where it sits, and n = 2 r - 1 more vertices, where its paws reach. Total n + 1 = 2 r vertices are occupied by one spider, and their Sp (2 r -1) = 2 2 r -1-r = 2 n-r . Therefore, all the vertices of the cube are occupied - this is the perfect arrangement.
We define the set of C vertices where the spiders sit for n = 7 by a system of three linear equations.
x 1 ⊕ x 3 ⊕ x5 ⊕ x 7 = 0; x 2 ⊕ x 3 ⊕ x 6 ⊕ x 7 = 0; x 4 ⊕ x 5 ⊕ x 6 ⊕ x 7 = 0 , where a ⊕ b is the addition in mod2 , i.e. 1⊕1 = 0 ( mod2 ), and the rest - as usual.
We denote by H the matrix of coefficients of this system of linear equations:
Then this system can be rewritten as Hx T = 0. Note that inth column is a binary representation of i .
We need to prove that any binary 7-dimensional vector y "belongs" to exactly one spider, or, what is the same, the field y beats exactly one rook.
We compute s = Hy T . If s = (0, 0, 0) , then y ∉ C some kind of spider sits there. If s ≠ (0, 0, 0) , then s = h i is the i column of the matrix H for some i , and therefore c = y ⊕ e i ∈ C , where e iIs a vector of all zeros except 1, which is in the i- th coordinate. Then the spider sitting at the vertex c = y ⊕ e i , reaches paw to i -th coordinate axis of the vector y . If a spider sitting at the other vertex c 'would reach the vector y by its paw along the jth coordinate axis , then y = c' ⊕ e j and Hy T = Hc ' T + He j T = h j , which leads to a contradiction , since h i ≠ h j are all columns of the matrix Hare different. If i = j , then c '= c .
Error Correction Codes
Imagine that we have a sequence of zeros and ones that we want to transmit over a channel in which transmission errors may occur in rare cases. When transmitting seven bits, we may either have no errors at all, or one error: one of the transmitted positions will be accepted in the opposite position. It is assumed that we have prepared a list of 16 words with a length of 7 bits. Words can be numbered with binary vectors of length 4. And then it turns out that the receiver will be sent 4 bits of information using 7 bits. This is of course overhead. There is an easier way: we can transmit each bit three times. If the transmission is allowed no more than one error, the incorrectly transmitted bit will be restored. But so we will transmit four bits with the help of twelve. Respectively, transmitting four bits through seven is more economical. Four out of seven bits will transmit information, and the remaining three bits will act as verification ones.
So, a vector of zeros and ones is transmitted. One of sixteen allowed. We do not know for sure whether a transmission error occurred. At the receiver, we need to know if one of the bits has moved to the opposite position. To do this, we take the vector that came out of the channel and insert it into our system of linear equations. If everything is satisfied, then this is a code vector, one of the allowed sixteen, transmission errors did not occur. And if some of the three equations are fulfilled, but some are not, then we write the unfulfilled as 1, and the unfulfilled as 0. We will get the same thing that we considered above: multiplying the matrix by a vector. If s is equal to 0, then the transmission passed without errors, otherwise an error occurred at position i .
Having watched the lecture to the end, you will learn how to determine exactly where the error occurred, about Hamming error correction codes, finite fields, and how all this is connected with ordinary mathematics.