# The MDS Conjecture

I will begin with a couple of games you can play with the ternary [4,2]-Hamming code, in much the same way Peter Cameron describes here and in a previous post of mine for a different Hamming code.

Choose a number between 0 and 8 (inclusive). I will ask you four questions, you can answer ‘a’, ‘b’ or ‘c’ and you are allowed to lie at most once. Here are my questions:

- Is your number
**(a)**less than 3**(b)**between 3 and 5**(c)**more than 5? - Is your number
**(a)**0 mod 3**(b)**1 mod 3**(c)**2 mod 3? - Is your number in
**(a)**{0,5,7}**(b)**{1,3,8} or**(c)**{2,4,6}? - Is your numberin
**(a)**{0,4,8}**(b)**{1,5,6} or**(c)**{2,3,7}?

From these questions, I can easily determine your number.

The reason why I can do this is because the code I am using has minimum distance 3 and so can correct 1 error. But there is something else this code can do: it can correct 2 erasures. If you tell me that you lied twice, and you tell me which of the four questions you lied, then I can still find your number.

The generator matrix for the ternary [4,2]-Hamming code is

Perhaps a card trick is more compelling?

I have only Hearts, Diamonds and Spades: no Clubs. I also have a knowledgeable assistant who is not in the room and does not know what we are doing. I ask you to deal out two cards from my deck … you deal out

4 of Hearts, King of Spades

I then place two cards besides your’s, so now we see

4 of Hearts, King of Spades, Ace of Spades, 7 of Spades

I then ask you to change one of the cards to another card from the deck:

4 of Hearts, King of Spades,** Queen of Diamonds**, 7 of Spades

The assistant walks into the room and says “I do not know what your old card was, but I do know that you changed a Spade for this Queen of Diamonds!”

How does this work?

Associate 0 to Hearts, 1 to Diamonds and 2 to Spades. Then the first two cards you dealt give us the string

(0,2).

Now multiply this vector by G to obtain a codeword in our code: (0, 2, 2, 2). That is why I placed another two spades down next to your cards. You now changed the suit of one of the cards (normally a volunteer will change the suit) and so the codeword has been changed to (0, 2, 1, 2). We now use the check matrix

and multiply our codeword by it (on the left): we arrive at (2,0).

By doing some basic syndrome decoding, the assistant can say that the associated coset leader is (0,0,2,0) and that the third card was a Spade. Perhaps more impressively, you could change two of the cards, and by knowing their positions, the assistant would know the suits of the cards that you changed. If you know syndrome decoding, you can try this at home. The coset leaders are accordingly:

Syndrome | Coset Leader |

00 | 0000 |

01 | 0001 |

02 | 0002 |

10 | 0010 |

11 | 0200 |

12 | 2000 |

20 | 0020 |

21 | 1000 |

22 | 0100 |

The minimum distance of a linear code is the smallest Hamming distance between different codewords, and such a linear code can correct errors and correct erasures. In general, there is a simple upper bound for the minimum distance of a linear code with code length and dimension , and it is known as the* Singleton bound:*

A linear code over a finite field with parameters [n,k,d] is a maximum distance separable (MDS) code if . Such codes are optimal in terms of erasures since every subset of coordinate positions is the support of some codeword. Alternatively, the number of parity check symbols is , and so the number of symbol errors that MDS codes can correct is maximal. So for example, the ternary [4,2]-Hamming code above has which is also the minimum distance, and so we have an MDS code. The parity check matrix has the property that every 2 columns are linearly independent, which means that we can correct 2 erasures.

We can also view MDS codes geometrically. The columns of the generator matrix can be realised directly as projective points of the projective space . Now the minimum distance being means

*no points are incident with a common hyperplane.*

Such a set of points in known as an ** arc** of of , and Bush (1952) showed that if , then the size of the arc is at most . Segre (1955) posed the following conjecture for the situation where .

## MDS conjecture

An arc of , with , has size at most , unless is even and or , in which case it has size at most .

Recently, a phenomenal paper by Simeon Ball has radically advanced what we know about MDS codes, and his work will appear in the Journal of the European Mathematical Society: *“On sets of vectors of a finite vector space in which every subset of basis size is a basis”*. He has shown that the MDS Conjecture is true when is prime. The main results are:

**Theorem 1.7.** Suppose . A set S of vectors of the vector space , with the property that every subset of S of size k is a basis, has size at most .

**Theorem 1.8. **If then a set S of vectors of the vector space , with the property that every subset of S of size is a basis is equivalent to the following normal rational curve:

.

The latter is a generalisation of Segre’s theorem on ovals of , odd.

#### Corollary

- A linear MDS code of dimension k over has length at most where .
- If then a linear MDS code over of dimension k and length is a Reed-Solomon code.
- If then a linear MDS code of dimension over has length at most . Moreover, in the case of equality the code is a Reed-Solomon code.

#### Corollary

- For any matrix,with and entries from , there is a set of columns which are linearly dependent.
- The uniform matroid of rank , with , is representable over , prime, if and only if .

So what does the MDS Conjecture mean for the card trick?

If we can design a successful card trick with a prime power of suits, like the one above based on a linear code, such that

- there are cards chosen by the volunteer and ,
- the cards are then completed to cards by the magician,
- the volunteer can lie times.
Then . Moreover, If and , then the code is a Reed-Solomon code.

In the original problem, it equates to having numbers, questions, and lies allowed.