And Some Applications

MOLS, TD's, OA's

and some applications

Jeff Dinitz

University of Vermont

USA

Page 5 of MOLS talk

Solving the 9 officer problem:

Ranks: 1, 2, 3

Regiments: a, b, c

We need a 3 x 3 array containing pairs of symbols so that in each row and in each column, each symbol occurs exactly once.

Also requires that each of the 9 pairs from the set of

Ranks x Regiments occurs exactly once.

To visualize, we make a 3 x 3 Rank array and a 3 x 3 Regiment array.

RanksRegiments

Final Array:

Page 2 from MOLS talk

Page 3 from MOLS talk

Enumeration of latin squares

Note that it is easy to make a latin square of any order. Just start with the first row

1 2 3 … n

and then shift this row cyclically to the right by 1, 2, … n 1 positions to construct the remaining n  1 rows.

How many different latin squares are there for a given order?

Say that two latin squares L1 and L2 are equivalent if there L2 can be obtained from L1 by any combination of permutations of the rows, columns or the symbols.

Here is what is currently known:

n / 2 / 3 / 4 / 5 / 6 / 7 / 8 / 9 / 10
# of inequivalent LS / 1 / 1 / 2 / 2 / 22 / 563 / 1,676,267 / 115,618,721,533 / ?

The two inequivalent latin squares of side 4

0 1 2 30 1 2 3

1 0 3 2and1 0 3 2

2 3 0 12 3 1 0

3 2 1 03 2 1 0

This is a good example of the so-called combinatorial explosion.

Back to orthogonal latin squares.

We are interested in finding the maximum number of

mutually orthogonal latin squares (MOLS)

Order 2.

Order 3

Order 4

We saw an example of three mutually orthogonal latin squares or side 4. Can there be a larger set??

Question? For a given n, find the maximum number of mutually orthogonal latin squares of order n, MOLS(n).

Let N(n) denote the maximum number of MOLS(n)

Theorem. 1  N(n) n 1

Proof.

……

If N(n) = n 1 we say that there exists a complete set of MOLS of order n. (We will discuss this in detail later).

We know now that

N(2) = 1,N(3) = 2, and N(4) = 3

We also say that N(1) = 

Euler could not construct a pair of orthogonal latin squares of order 6 (to solve the 36 officer problem), he also couldn't make a pair of orthogonal latin squares of order 2. With this evidence he made the following conjecture.

Euler knew the following theorem.

Theorem: If n is odd, then N(n)  2.

Proof. In Zn the cyclic group of order n, let

L(i,j)= i + j and R(i,j)= i  j

First note that that the addition table of any additive group gives a latin square.

Now note that L and R are orthogonal

See that this construction never works when n is even.

+ 

In fact this generalizes to the following:

Theorem: If G is a group with a unique element of order 2, then the addition table of G (thought of as a latin square) has no orthogonal mate. (Homework)

Slide 8

Slide 9

Constructing MOLS from finite fields

(Background for finite fields)

A finite field is a finite set together with two operations + and 

such that additive and multiplicative operations are an abelian groups and there is a distributive law of multiplication over addition.

Example: Zpis a finite fieldfor every prime p,

But, for example, Z6 or Z9are not finite fields.

Theorem: Let p be a prime and let q = pn for some n  1. (q is called a prime power). Then there exists a finite field with IqI elements. This field is unique and is called GF(q).

The following result is attributed to R.C. Bose in 1938. It was proven independently by Stevens in 1939 and by E.H. Moore in 1896.

It is a generalization of the addition and subtraction table theorem.

Theorem: If q is a prime power, then N(q) = q1.

Claim: The q 1 latin squares so constructed are pairwise orthogonal.

Proof: First show each square is a latin square, then show they are orthogonal. (Homework)

Note: the definition of each square looks like the definition of a line in the plane ???

Example: q = 5.

a = 1 a = 2

a = 3a = 4

So for each prime power q there is a complete set of latin squares of order q.

Slide 11.

Slide 12. (and Bose photo)

Slide 13. (use actual slide)

MacNeish Direct product revisited slide (actual one).

Slide 15

Slide 16

Slide 17

Slide from Raghavarao

MOLS table from 1971 (two slides)

Slide 22 – 23 (Wilson's construction).

Say something about Brouwer MOLS table.

Current MOLS Table

Get slide after #33

Current constructions:

Slide 19-20 and Todorov 3 MOLS(14)

Some applications of MOLS

1) Marching Officers 

2) Magic Squares

3) Design of experiments

4) Cryptography

5) Software testing

6) Design of the schedule of play in a tournament

7) to construct other design theoretic objects

An nth order magic square is an nn array of integers (from 1 to n2) with the property that the sum (magic sum) of the numbers in each row, each column and the main and back diagonal is the same.

Examples:

8888

Magic sum = 15 Magic sum = 34

The square on the left above is the first known magic square. It dates from the 4th century BC China, but legend dates it to the $23rd century BC. It is known as the Lo-Shu. Chinese myth says that the square was first seen by Emperor Yu on the back of a mystic turtle. There was great reverence for the Lo-Shu, and it became the basis for many of the Chinese constructions for

squares of higher orders.

Construction of a nthorder magic square from a pair of orthogonal latin square of side n (almost):

Take 3 times the square on the left and add to the square on the right (plus 1) to get

Latin Square Statistical Designs and Covering Arrays

Latin squares provide a efficient way to test for two way interaction among several variables.

Example: Suppose there are n varieties of wheat to be tested with n fertilizers and n insecticides. Then there are n3 variety-fertilizer-insecticide triples to be tested. To reduce experimental cost we can use a Latin Square Design.

Let the symbols of an n n latin square correspond to the wheat varieties varieties.
Let the rows correspond to the n fertilizers
Let the columns correspond to the n insecticides

Can test each variety of wheat with each of the fertilizers and insecticides in n2 tests.

n = 4

i1 i2 i3 i4

Note that wheat variety 1 is matched with the four

fertilizer-insecticide pairs (1,1), (2,3), (3,4) and (4,2), so is tested once with each fertilizer and each insecticide.

An analysis of variance can determine the significance of the data and whether or not one of the fertilizers or insecticides is better than the others.

This can easily be generalized to more than three variables by using orthogonal latin squares.

Write the 16 tests in a 3 16 array:

rows

columns

symbols

This is called an Orthogonal Array. This one is anOA(3,4)

Fact: The existence of k MOLS(n) is equivalent to the

existence of an OA(k,n).

OA’s have been generalized to Covering Arrays.

(Basically, these are arrays that cover all pairs of variables)

An example (Cohen, Dalal, et. al. (1996)):

ATT is testing a telephone network service called AIN (Advanced Intellegent Network). This is an automated phone service.

There are four parameters:

Type of announcement – this has three values
None
Interruptible
Noninterruptible

User input of digits
No digits
Fixed number of digits
Variable number of digits terminated by the # key

Make a billing record
Yes
no

User access
Local phone
Long-distance trunk

(none for announcement and none for the number of digits is not permitted)

Note that to test all pairwise interactions among the 4 parameters would take 32 = (3  3  2  2)  4 tests.

The following covering array shows that all pairwise combinations of the parameter values can be tested for in 8 tests (a 75% reduction in experimental cost)

Test / 1 / 2 / 3 / 4 / 5 / 6 / 7 / 8
Announce. / none / none / inter. / inter. / inter. / non-int / non-int / non-int
Digits wanted / fixed / var / none / fixed / var / none / fixed / var
Billing / no / yes / no / yes / yes / yes / yes / no
Access type / line / trunk / trunk / trunk / line / line / trunk / trunk

Much research has been done to design good covering arrays

Cryptography – Authentication Codes

When Alice sends a message to Bob (encrypted or not), how can Bob be sure that it was Alice who sent the message, and how does he know that the message was not altered by someone else during its transmission.

This points to the need for an authentication code.

The mathematical setting:

There are three participants: Alice, Bob, and Oscar.

Alice and Bob want to communicate over an insecure channel (e.g., by e-mail, fax, or cell-phone). Oscar (the ``bad guy'') has the ability to introduce his own messages into the channel and/or to modify existing messages.

Consider two types of attacks by Oscar.
When Oscar places a (new) message m' into the channel, it is called impersonation. When Oscar sees a message m and changes it to a (different) message m' m, it is called substitution.
As an example, suppose that Bob is Alice's stockbroker. When Alice sends a message to Bob, such as "buy 1000 shares of Acme stock'', she would not be very happy if Oscar changed buy to sell!

The goal of an authentication code is to allow Bob to detect
with high probability when such an attack has taken place.

Definition: An authentication code is a four-tuple (S, A, K, E), where the following conditions are satisfied.

S is a finite set of source states
A is a finite set of authenticators.
K is a finite set of keys.
For each kK, there is an authentication rule ekE,

where ek: S  A.

How an authentication code works:

Alice and Bob jointly choose a secret key kK at random and ahead of time.

A source state is just the information that Alice wants to
communicate to Bob (e.g., ``buy 100 shares … '').

When Alice wants to communicate the source state sS to Bob, she uses the authentication rule ek to construct the authenticator

a = ek(s) .

The messagem is formed by concatenating s and a, i.e., m = (s,a).

The message m is then sent over the channel.

When Bob receives m , he verifies that a = ek(s) to authenticate the source state s . If a  ek(s), then Bob is able to detect that an attack has taken place.

Let P0 denote the probability that Oscar can deceive Bob by impersonation (sending a message in Alice's name)
Let P1 denote the probability that Oscar can deceive Bob by substitution (changing Alice's sent message)

Theorem: Suppose there is are m MOLS(n). Then there is an authentication code for m source states, having n authenticators and n2 keys, in which P0 = P1 = 1/n.

Note that this is the best possible with n authenticators.

Example:

Suppose that Alice and Bob want at least 300 source states (so they need at least 300 MOLS). Now suppose that they want a security level of 1/5000. This says that they want MOLS of order n  5000.

The easiest way to satisfy these requirements is to take n to be the smallest prime greater than 5000. This is 5003. They construct 300 MOLS(5003) (we saw how to do this earlier).

Call these L1, L2, …, L300.

They also have a previously agreed upon secret key k – this will be an ordered pair of numbers from 1 to 5003 (say k = (1244, 346)).

Then, say if Alice wants to send the source message s = 219 (this could stand for "buy 219 shares of Acme).

Alice computes her authenticator

a = e(1244, 346) (219) = L219(1244, 346),

and sends the message m = (219, a) to Bob. Bob can check the authenticity of m by looking at the (1244,346) cell of the L219.

If it is not a then he knows that something is wrong.