Finite algebras, geometries and codes. Lecture by Grigory Kabatiansky in Yandex
Although almost everything in the world around us, of course, until recently infinite objects dominated in mathematics. 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 clearer to us.
This lecture is devoted to an amazing reversal of history, when finite fields (Galois fields), previously unfamiliar even to many professional mathematicians, were suddenly demanded by engineers, and how this changed our knowledge of the theory of finite fields and related objects.
')
To begin with, we will think about how to spread the maximum number Sp (n) of spiders on an n- dimensional cube so that they do not fight. The spider n legs - one for each edge, with the length of the legs equal to the length of the edges of the cube. A fight begins if two spiders reach the same vertex. Can we achieve perfect location: so that there is a spider on each vertex?
In addition to the class can be attributed, and the following two tasks:
In three-dimensional space, everything is quite obvious: Sp (3) = 2 ? Since if we put two spiders on the vertices of a three-dimensional cube, then they are necessarily diametrically opposed, and they occupy three outgoing vertices with their paws. The third spider has nowhere to put.
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
The fact that Sp (10) ≥ 72; Sp (11) ≥ 144 was known for a long time, but it was not until 1999 that the equality was proved.
We show that if Sp (2 r -1) = 2 2 r -1-r , then this is the perfect spider layout (or rooks with q = 2). Each spider occupies the top where it sits, and also n = 2 r - 1 peaks, 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 nr . Therefore, all the vertices of the cube are occupied - this is the perfect arrangement.
Let us set the set C of vertices where the spiders sit, for n = 7 by a system of three linear equations.
x 1 ⊕ x 3 ⊕ x 5 ⊕ 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 addition modulo 2 , i.e. 1⊕1 = 0 ( mod2 ), and the rest - as usual.
Let H denote the matrix of coefficients of this system of linear equations:
Then this system can be rewritten as Hx T = 0. Note that the i-th column is a binary representation of the number i .
We need to prove that any binary 7-dimensional vector y "belongs" to exactly one spider, or, equivalently, the field y beats with exactly one rook.
Calculate s = Hy T. If s = (0, 0, 0) , then y ∉ C there is some kind of spider sitting 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 ⊕ i i ∈ C , where e i is a vector of all zeros, except 1, standing in the i -th coordinate. Then the spider sitting at the c = y ⊕ e i vertex reaches its i- th coordinate axis of the vector y with its paw. If the spider sitting at the other vertex c ' reached up with its paw along the j -th coordinate axis to the vector y , 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 - all columns of the matrix H are different. If i = j , then c '= c .
Imagine that we have a sequence of zeros and ones that we want to transmit through a channel in which transmission errors can occur in rare cases. When transmitting seven bits, we may either have no errors at all, or one error: one of the transferred 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 recipient will be sent 4 bits of information using 7 bits. This is of course overhead. There is an easier way: we can transmit every bit three times. If the transfer 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, transfer of four bits through seven leaves more economically. Four bits of the seven will transmit information, and the remaining three bits will act as test data.
So, a vector of zeros and ones is transmitted. One of the sixteen permitted. We do not know for sure if an error occurred during transmission. 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, no transmission error occurred. And if some of the three equations are fulfilled, and some are not, then we write the unfulfilled as 1, and the unfulfilled - as 0. We get the same thing that we considered above: multiplying the matrix by a vector. If s is equal to 0, the transmission passed without errors, otherwise an error occurred in position i .
After completing the lecture to the end, you will learn how to determine exactly where the error occurred, about Hamming codes that correct errors, the final fields, and how all this is connected with ordinary mathematics.
This lecture is devoted to an amazing reversal of history, when finite fields (Galois fields), previously unfamiliar even to many professional mathematicians, were suddenly demanded by engineers, and how this changed our knowledge of the theory of finite fields and related objects.
')
To begin with, we will think about how to spread the maximum number Sp (n) of spiders on an n- dimensional cube so that they do not fight. The spider n legs - one for each edge, with the length of the legs equal to the length of the edges of the cube. A fight begins if two spiders reach the same vertex. Can we achieve perfect location: so that there is a spider on each vertex?
In addition to the class can be attributed, and the following two tasks:
- How much can you put on an n-dimensional chessboard of size q × q ... × q so that no field beats more than once?
- For which n and q there is such an arrangement of rooks on an n- dimensional chessboard of size q × q ... × q , that each field beats once?
About spiders
In three-dimensional space, everything is quite obvious: Sp (3) = 2 ? Since if we put two spiders on the vertices of a three-dimensional cube, then they are necessarily diametrically opposed, and they occupy three outgoing vertices with their paws. The third spider has nowhere to put.
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
The fact that Sp (10) ≥ 72; Sp (11) ≥ 144 was known for a long time, but it was not until 1999 that the equality was proved.
We show that if Sp (2 r -1) = 2 2 r -1-r , then this is the perfect spider layout (or rooks with q = 2). Each spider occupies the top where it sits, and also n = 2 r - 1 peaks, 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 nr . Therefore, all the vertices of the cube are occupied - this is the perfect arrangement.
Let us set the set C of vertices where the spiders sit, for n = 7 by a system of three linear equations.
x 1 ⊕ x 3 ⊕ x 5 ⊕ 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 addition modulo 2 , i.e. 1⊕1 = 0 ( mod2 ), and the rest - as usual.
Let H denote the matrix of coefficients of this system of linear equations:
Then this system can be rewritten as Hx T = 0. Note that the i-th column is a binary representation of the number i .
We need to prove that any binary 7-dimensional vector y "belongs" to exactly one spider, or, equivalently, the field y beats with exactly one rook.
Calculate s = Hy T. If s = (0, 0, 0) , then y ∉ C there is some kind of spider sitting 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 ⊕ i i ∈ C , where e i is a vector of all zeros, except 1, standing in the i -th coordinate. Then the spider sitting at the c = y ⊕ e i vertex reaches its i- th coordinate axis of the vector y with its paw. If the spider sitting at the other vertex c ' reached up with its paw along the j -th coordinate axis to the vector y , 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 - all columns of the matrix H are 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 through a channel in which transmission errors can occur in rare cases. When transmitting seven bits, we may either have no errors at all, or one error: one of the transferred 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 recipient will be sent 4 bits of information using 7 bits. This is of course overhead. There is an easier way: we can transmit every bit three times. If the transfer 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, transfer of four bits through seven leaves more economically. Four bits of the seven will transmit information, and the remaining three bits will act as test data.
So, a vector of zeros and ones is transmitted. One of the sixteen permitted. We do not know for sure if an error occurred during transmission. 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, no transmission error occurred. And if some of the three equations are fulfilled, and some are not, then we write the unfulfilled as 1, and the unfulfilled - as 0. We get the same thing that we considered above: multiplying the matrix by a vector. If s is equal to 0, the transmission passed without errors, otherwise an error occurred in position i .
After completing the lecture to the end, you will learn how to determine exactly where the error occurred, about Hamming codes that correct errors, the final fields, and how all this is connected with ordinary mathematics.
Source: https://habr.com/ru/post/217487/
All Articles