拉丁方陣 摘要：拉丁方陣是什麼? 交大應數系 傅恆霖.

Presentation on theme: "拉丁方陣 摘要：拉丁方陣是什麼? 交大應數系 傅恆霖."— Presentation transcript:

1 拉丁方陣 摘要：拉丁方陣是什麼? 交大應數系 傅恆霖

2 A Latin square of order n is an n×n array based on an n-set S such that each element of S occurs exactly once in each row and each column. We can let S = {0, 1, …, n-1} = Zn. A Latin square of order 3

3 A Latin square of order 3 defines a quasigroup on 3 elements and vice versa.
<S,*> is a quasigroup if <S,*>is a groupoid and have unique solution respectively for all a and b in S

4 Group and quasigroup A group is a quasigroup, but a quasigroup may not be a group. A quasigroup with associative law is a group. (Can you prove this statement?) 0*(1*2) = 0 (0*1)*2 = 3 * 1 2 3

5                                                       A typical Sudoku puzzle                                

6                                 Example of Sudoku

7 Two Latin squares and of order n are orthogonal if 。
Two orthogonal Latin squares of order 4

8 How? Two fingers principle!
If you have two fingers, then you can prove that the above two Latin squares are orthogonal. How? Two fingers principle!

9 The first paper in combinatorial designs
Can you arrange the 16 aces, kings, queens and jacks from a regular 52 card deck of playing cards in a 4x4 array so that no suit occurs twice in a row or column, and no single kind of a card occurs twice in any row or column?

10 are mutually orthogonal Latin squares of order n (MOLS(n)), if for 。
Theorem Let n be a prime power and n≠2 . Then there exists n-1 mutually orthogonal Latin squares (best possible!) of order n.

11 (＊) 令α為的一個排列，β也是排列， 則 ， 其中 (**) There do not exist two orthogonal Latin squares of order 2 and 6. (***) Order 2 is easy to see, but not order 6.

12 Product theorem If there exists a pair of orthogonal Latin squares of order m1 and order m2, then there exists a pair of Latin squares of order m1m2. Euler’s conjecture (1782) There does not exist a pair of orthogonal Latin squares of order n where n  2 (mod 4).

13 Disproof Theorem (B.S.P., 1959)
There exists a pair of orthogonal Latin squares of order n for all n which is not 1, 2 or 6. Theorem (?) There do not exist 9 mutually orthogonal Latin squares of order 10.

14 　　我們可以選 n 為Prime Power, 如此N(n)，互相垂直的n階拉丁方陣數(max)，自然是最大N(n) = n-1。
更明確地說 [T. Beth, Abh. Math. Sem. Hamburg 53(1983)]

15 Conjecture A collection of n-1 mutually orthogonal Latin squares of order n exists if and only if n is a prime power and n  2. ( ) The proof follows by using the existence of a finite field of order n. (Exercise!)

16 How many distinct Latin squares?
Two Latin squares are distinct if they are different in at least one corresponding entry. We use L(n) to denote the number of distinct Latin squares of order n. L(1) = 1, L(2) = 2, L(3) = 12, L(4) = 576, L(5) = ? (Exercise)

17 Standard Latin squares
A Latin square of order n is called standard (標準型) if the first row and the first column are in increasing order 0, 1, 2, …, n-1. 1 2 3 4 5

18 不同大小的 n × n 的拉丁方陣的數量 n 拉丁方陣的標準型的數量 所有拉丁方陣的數量 1 2 3 12 4 576 5 56 161280 6 9408 7 8 9 10 11

19 More algebra We may assign more properties to a quasigroup.
For example, is there a quasigroup (G,*) satisfying a*a = a for each a in G? How about a*(b*a) = b? Or even a*[(b*c)*(b*a)] = c?

20 Well-known one A quasigroup (G,*) of order n satisfying (1) a*a =a, (2) a*(a*b) = b, and (3) (a*b)*b = a, for all a, b in G, exists if and only if n  1 or 3 (mod 6). The existence of this quasigroup is equivalent to the existence of a Steiner triple system of order n.

21 Inside a Latin square Given a Latin square of order n, how many distinct entries can we find from the square by choosing at most one entry from each row and each column. 1 2 3 4 5 5 ?

22 Ryser’s Conjecture For each Latin square of order n, there are at least n-1 distinct entries which are in “transversal” positions (no two are in a row or column). If n is odd, then we can find n distinct entries as a transversal. The best result obtained so far is very far from expected value.

23 Good works A short proof by D. Woolbright shows that we can find at least n – n1/2 distinct entries. The best result was proved by Peter Shor (well-known for Quantum computing), he prove that we can find at least n – O(log2n) entries. This is a great problem to work.

24 Partial Latin squares A partial Latin square of order n based on S is an nxn array such that each element of S occurs in each row and respectively each column at most once. The size of a partial Latin square is the number of entries in the square.

25 Completing the partial Latin square
A partial Latin square of order n is said to be completable if we can extend the partial Latin square into a Latin square of order n (by filling the empty entries with proper elements). Examples of Sudoku can always be completed.

26 Can’t be completed 1 2 3 4 1

27 Which one is possible? Theorem If a partial Latin square is of size at most n-1, then it can be completed. (Evan’s conjecture) Theorem If a partial Latin square is of size n, then it can be completed except some exceptions (such as two examples of last page).

28 Now, we consider a special class of partial Latin squares which are very useful in applications.

29 A critical set C in a Latin square L is a partial Latin square obtained from L with the following two properties： 1. L is the only Latin square of order n which C can be completed；and 2. no proper subset of C has property (1). A critical set

30 例 　　上面圈出的三個位置，任兩個都會形成一個臨界集(Critical Set)。少了，或多了都不是臨界集；然而多了(3個)也可以繼續填成唯一的拉丁方陣。

31 Critical sets, n=5

32 A critical set C of a Latin square L provides minimal infos from which L can be reconstructed.
Deciding whether a partial Latin square is a critical set is NP-complete. (From completion point of view.) Denote the minimum size of a critical set of order n by M(n). Then M(n) is at least [n2/4] [D. Curran & G.H.J.van Rees, Cong. Numer. 1979] (Conjecture!)

33 Applications in Cryptography

34 An (s,t)-secret sharing scheme is a system where s pieces of information called shares or shadows of a secret key K are distributed so that each participant has a share such that: 1. the key K can be reconstructed from knowledge of any t or more shares; and 2. the key K can not be reconstructed from knowledge of fewer than t shares.

35 A sharing scheme Key: A Latin square L
From L we design a critical set C for the time being. (This critical set can be changed.) The shares are partial Latin squares which are contained in C.

36 分散模式解 (Sharing Scheme)
　　在近代有很多重大的決定，為了確保決策過程沒有暇疵，通常會採用由多個人都同意的情況下才執行；例如開金庫，發射核彈…。所以，建立一個系統使得較小的人數無法開啟是有它的必要性。

37 臨界集的選擇有很多！ ↑ 對於臨集的了解不多。 ↓ 增加破解難度

38 Latin square changes my life
It is a story now! I went to Auburn University (1977) with a teaching assistantship to learn Topology which I felt very interesting when I was an undergraduate student (as a 學弟 of 薛老師). Auburn was a power house of General Topology in 70’s. (Not Football)

39 Fortunate or unfortunate
They did not have enough students to open the class of Topology that year, they need at least three. I was informed to take another class besides Algebra (I) and Analysis (I) which I have chosen already. I did have many courses to choose. So, it comes “Combinatorics”.

40 The first subject I learned
The first subject I learned from Prof. C. C. Lindner was “Latin square”. He claims that Latin square is the most important combinatorial configuration in combinatorics. It took more than one month to complete his lectures on Latin square at that year.

41 From C. C. Lindner Do whatever you enjoy the most not others.
No one can stop your research unless you don’t want to do it anymore. He is 75 now and he is working as hard as any young researchers.

42 Keep moving forward!