Skip to content

The MDS Conjecture

November 22, 2012

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:

  1. Is your number (a) less than 3 (b) between 3 and 5 (c) more than 5?
  2. Is your number (a) 0 mod 3 (b) 1 mod 3 (c) 2 mod 3?
  3. Is your number in (a) {0,5,7} (b) {1,3,8} or (c) {2,4,6}?
  4. 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

G= \begin{bmatrix}1&0&1&2\\ 0&1&1&1\end{bmatrix}

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

H= \begin{bmatrix}2&2&1&0\\1&2&0&1\end{bmatrix}

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 d of a linear code is the smallest Hamming distance between different codewords, and such a linear code can correct \lfloor (d-1)/2\rfloor errors and correct d-1 erasures. In general, there is a simple upper bound for the minimum distance d of a linear code with code length n and dimension k, and it is known as the Singleton bound:

d\le n-k+1.

A linear code over a finite field with parameters [n,k,d] is a maximum distance separable (MDS) code if d=n-k+1. Such codes are optimal in terms of erasures since every subset of n-k+1 coordinate positions is the support of some codeword. Alternatively, the number of parity check symbols is n-k, 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 n-k+1=4-2+1=3 which is also the minimum distance, and so we have an MDS code. The parity check matrix H 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 PG(k-1,q). Now the minimum distance being n-k+1 means

no k points are incident with a common hyperplane.

Such a set of points in known as an arc of of PG(k-1,q), and Bush (1952) showed that if k\ge q+1, then the size n of the arc is at most k+1. Segre (1955) posed the following conjecture for the situation where k \le q.

MDS conjecture

An arc of PG(k -1, q), with k \le q, has size at most q+1, unless q is even and k=3 or k=q-1, in which case it has size at most q+ 2.

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 q is prime. The main results are:

Theorem 1.7. Suppose k\le q. A set S of vectors of the vector space \mathbb{F}_q^k, with the property that every subset of S of size k is a basis, has size at most q + k + 1 -\mathrm{min}(k, p).

Theorem 1.8. If p \ge k then a set S of q+1 vectors of the vector space \mathbb{F}_q^k , with the property that every subset of S of size k is a basis is equivalent to the following normal rational curve:

\{(1,t,t^2,\ldots, t^{k-1}):t\in \mathbb{F}_q\}\cup \{(0,\ldots,0,1)\}.

The latter is a generalisation of Segre’s theorem on ovals of PG(2,q), q odd.

Corollary

  • A linear MDS code of dimension k over \mathbb{F}_q has length at most q + k + 1 - \mathrm{min}(k, p) where k \le q.
  • If p \ge k then a linear MDS code over \mathbb{F}_{q} of dimension k and length q+1 is a Reed-Solomon code.
  • If 2<q-p+1<k<q-2 then a linear MDS code of dimension k over \mathbb{F}_q has length at most q+1. Moreover, in the case of equality the code is a Reed-Solomon code.

Corollary

  • For any k\times (p+2) matrix,with 2\le k\le p and entries from \mathbb{F}_p, there is a set of k columns which are linearly dependent.
  • The uniform matroid E of rank r, with |E| \ge r + 2, is representable over \mathbb{F}_p, p prime, if and only if |E| \le p + 1.

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

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

  • there are k cards chosen by the volunteer and k\le q,
  • the cards are then completed to n cards by the magician,
  • the volunteer can lie n-k times.

Then n\le q+k+1 - \mathrm{min}(k, p). Moreover, If p \ge k and n=q+1, then the code is a Reed-Solomon code.

In the original problem, it equates to having q^k numbers, n questions, and n-k lies allowed.

About these ads
No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 40 other followers

%d bloggers like this: