On The Spectrum Of R-Self-Orthogonal Latin Squares And Its Applications

Suppose that L = (l_ij) is a Latin square of order v with entries from set X and M = (m_ij) is a Latin square of order v with entries from set Y. We say that L and M are orthogonal provided that, their superposition produces exactly n² distinct ordered pairs, that isMany works are devoted to the investigation of the properties of orthogonal Latin squares.In parallel with the investigation of orthogonality, various weaker versions of the concept have been proposed and studied. Thus, L. Euler, having failed to construct a pair of orthogonal Latin squares of order 6, himself constructed an incomplete graeco-Latin square comprising 34 = 6² - 2 different ordered pairs and two vacant cells in 1782. Since then, other weaker versions such as "near orthogonal", "incomplete orthogonal", "perpendicular" Latin squares were investigated by many authors.Two Latin squares of order v, L = (l_ij) and M = (m_ij), are said to be r-orthogonal if their superposition produces exactly r distinct ordered pairs, that isBelyavskaya first systematically treated the following question in 1976: For which integers v and r does a pair of r-orthogonal Latin squares of order v exist? Until 2002, Zhu and Zhang solved the problem completely.In a pair of r-orthogonal Latin squares of order v, L and M, if M is the transpose of L, we say that L is an r-self-orthogonal Latin square and denoted by r-SOLS(v).In the last paper on r-orthogonal Latin squares, Zhu and Zhang conjectured that there is an integer v0 such that for any v > v0, there exists an r-SOLS(V) for any r e [v,v2] \{v + l,v2 - 1}.In this thesis, we show that vq < 27 and give an almost complete solution for the existence of r-self-orthogonal Latin squares. The main results are:(1) For any integer v > 27, there exists an r-SOLS(/u) if and only if v < r < v2 and r (ï¿¡ {v + l,v2 — 1}.(2) Suppose that v is an integer. There exist r-SOLS(f) for v < r < v2, r ^ {v + l,v2 — 1} with 26 genuine exceptions and 26 possible exceptions.In this thesis, we also investigate the applications of r-self-orthogonal Latin squares in the design of stream ciphers and the construction of frame self-orthogonal Mendelsohn triple systems.The whole thesis is divided into eight chapters.Chapter 1 In this chapter, we introduce the backgrounds and developments of the investigation of r-orthogonal Latin squares, present the concept of r-self-orthogonal Latin squares and the known results.Chapter 2 In this chapter, we give some basic recursive constructions of r-self-orthogonal Latin squares, include filling in holes, inflation constructions with and without transversals; we also introduce some "ingredients" for using these constructions.Chapter 3 In this chapter, we give complete and incomplete r-self-orthogonal Latin squares with small r and specific distinct ordered pairs set. They will be used in the next two chapters as input designs. The methods we used here are computer searching and two special recursive constructions.Chapter 4 We investigate the existence of r-self-orthogonal Latin squares of order v for 9 < v < 26. The direct constructions we used in this chapter are mainly starter-adder type construction, permutating the rows of a certain r-self-orthogonal Latin square, and order-2-interchanges, and all of them are done by computer.Chapter 5 We investigate the existence of r-self-orthogonal Latin squares oforder v for v > 27 in this chapter. The main construction we used here are inflation construction and generalized inflation constructions. We give a complete solution of the existence of r-self-orthogonal Latin squares of v for v > 27.Chapter 6 In this chapter, we give an application of r-self-orthogonal Latin squares in cryptography. Since the set of distinct ordered pairs of an r-SOLS keeps unchanged under the same permutation give to the rows as well as the columns, we can design a kind of stream cipher by using an r-SOLS and a keystream consisted by a sequence of permutations.Chapter 7 As a special case of r-self-orthogonal Latin square, self-orthogonal Latin squares have been very useful in the construction of various combinatorial designs. We give an application of self-orthogonal Latin squares in the construction of frame self-orthogonal Mendelsohn triple systems in this and the next chapters. We give several constructive methods of frame self-orthogonal Latin squares in this chapter. The main construction is a inflation construction using enhanced self-orthogonal Latin squares.Chapter 8 We give the spectrum of frame self-orthogonal Latin squares in this chapter. Many other combinatorial structures such as group divisible designs, transversal designs, double group divisible designs, incomplete group divisible designs, etc. are used. And many complex recursive constructions are employed in this chapter.