Problem sheet 9 2004, March. 18

MT361 Error correcting codes

Ex. 1 Prove that A_{q}(4, 3) = q^{2} if and only if there exists a pair of orthogonal Latin Squares of order q.

Ex. 2 Construct 4 MOLS of order q = 5. Show that there cannot be 5 MOLS of order 5.

{Ex. 3 \atop i)}Construct pairs of mutually orthogonal Latin squares for n = 6. Well, they don’t exist, but try a bit to get a feeling that it is not an easy problem to prove that they cannot exist.

ii) Try the same for n = 10. Well, they exist, and were found after a long time of computer search. It is unlikely that you find any, but convince yourself that an exhaustive search would just take a very long time.

iii) Try to find two MOLS of order 10, either by using the internet or by using an appropriate book.

iv) Try to find three MOLS of order 10. (This is an open research problem.

If you solve it you will become very famous!) Hand in the solutions to iii). Actually, finding information, when you only know some key words is one of the most important things in your later life. At University you have very privileged access like broadband, access to databases or books.

Ex. 4 Show that the Latin squares L_{1} and L_{3} of order 4 are not orthogonal. Construct two orthogonal Latin Squares of order 4 as follows: Construct the field of 4 elements by taking all polynomials with coefficients 0 and 1, and reduce modulo x^{2} + x + 1. Show that the 4 elements are: 0, 1, x, x + 1. Write down the addition and multiplication table of this field. From this find two MOLS of order 4. Bring them into standard form.

Hand in solutions at the beginning of the lecture on Thursday of the next week.

Note: since next Thursday is the last session: you will get it marked. You can either fetch it from the marker (Maura Paterson in office 348) or next term. If you have any questions that should be addressed in the last week, ask! Once the time schedule of the exams is out, make suggestions for a time of a revision class (end of April or early in May, for example).