Латын квадраты мен квазитоптар: комбинаторлық және алгебралық аспектілер
Small Latin squares and quasigroups
Латын квадраттары мен квазитоптар математикалық эквиваленттер. Кішкентай өлшемдердегі мысалдар қарастырылады. Латын квадратын квазитопқа айналдыру жолдары түсіндіріледі.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Латын квадраттары мен квазитоптар эквивалентті математикалық объектілер, бірақ біріншісі комбинаторлық сипатта, ал екіншісі көбірек алгебралық сипатта. Төмендегі тізімде өте кішкентай өлшемдердің мысалдары қарастырылады, бұл квадраттың қабырғасының ұзындығы немесе эквивалентті квазитоптың элементтерінің саны.
Latin squares and quasigroups are equivalent mathematical objects, although the former has a combinatorial nature while the latter is more algebraic. The listing below will consider the examples of some very small orders, which is the side length of the square, or the number of elements in the equivalent quasigroup.
Теңдестік
n элементі бар квазитоп Q берілген болсын, оның Кейли кестесі (көбінесе көбейту кестесі деп аталады) – шекаралары бар (n + 1) × (n + 1) кесте, жоғарғы қатары баған тақырыптарын, ал сол қатары қатар тақырыптарын қамтиды. Шекараларды жою n × n массивті қалдырады, ол латын квадраты болып табылады. Бұл процесті кері қайтаруға болады: латын квадратынан бастап, квазитоптың көбейту кестесін алу үшін шекаралық қатар мен баған қосуға болады. Бұл шекаралау қалай жасалатынына толық еркіндік берілсе де, әртүрлі таңдаулармен алынған квазитоптар кейде төменде көрсетілген мағынада эквивалентті болады.
Given a quasigroup Q with n elements, its Cayley table (almost universally called its multiplication table) is an (n + 1) × (n + 1) table that includes borders; a top row of column headers and a left column of row headers. Removing the borders leaves an n × n array that is a Latin square. This process can be reversed, starting with a Latin square, introduce a bordering row and column to obtain the multiplication table of a quasigroup. While there is complete arbitrariness in how this bordering is done, the quasigroups obtained by different choices are sometimes equivalent in the sense given below.
Изотоптық квазитоптар
(Q,∘) және (R,∗) екі квазитоп болсын. Q-дан R-ға дейінгі біекциялардың реттелген үштігі (f,g,h) (Q,∘) -дан (R,∗) -ға дейінгі изотопизм деп аталады, егер барлық x, y ∈ Q үшін 1 = f(x) ∗ g(y) = h(x ∘ y) орындалса. Мұндай квазитоптар изотоптық деп аталады. Егер жоғарыдағы анықтамада 1 = f = g = h болса, онда квазитоптар изоморфтық деп аталады.
Let (Q,∘) and (R,∗) be two quasigroups. An ordered triple (f,g,h) of bijections from Q onto R is called an isotopism of (Q,∘) onto (R,∗) if 1=f(x) ∗ g(y) = h(x ∘ y) for all x, y in G. Such quasigroups are said to be isotopic. If in the above definition 1=f = g = h then the quasigroups are said to be isomorphic.
Нөмірлік
Латын квадратында (немесе квазитопта) қолданылатын символдар жиынтығы кездейсоқ, ал жеке символдар ешқандай мағынаны білдірмейді, тіпті басқа контексттерде мағынасы болған жағдайда да. Сондықтан, {1,2, …, n} немесе {0,1, …, n − 1} жиындары жиі қолданылатындықтан, осы символдардың сандық мәні жоқ екенін есте ұстау қажет. Бұл мәнді нақтылау үшін, кейде кішкентай латын квадраттары символдар жиынтығы ретінде әріптерді пайдаланады.
The set of symbols used in a Latin square (or quasigroup) is arbitrary and individual symbols carry no meaning, even if they may have a meaning in other contexts. Thus, since it is most common to see the symbol sets {1,2, , n} or {0,1, , n − 1} used, one must remember that these symbols carry no numerical meaning. To stress this point, small Latin squares sometimes use letters of the alphabet as a symbol set.
Изотоптық инварианттар
Латын квадратындағы әр түрлі кіші құрылымдардың саны оларды бір-бірінен ажыратуға көмектеседі. Осы сандардың кейбіреулері латын квадратының барлық изотоптары үшін бірдей болады және изотопиялық инварианттар деп аталады. Мұндай инварианттардың бірі – 2 × 2 кіші квадраттар саны, олар интеркалаттар деп аталады. Тағы бірі – көлденеңдердің жалпы саны, бұл n-ретті латын квадратындағы n позициядан тұратын жиын, әр қатарда және әр бағанда бір позициядан, онда ешбір элемент екі рет қайталанбайды. Осы сандардың мәндері әртүрлі болатын латын квадраттары әртүрлі изотопиялық классқа жатады. Интеркалаттардың саны да негізгі класс инварианты болып табылады.
The counts of various substructures in a Latin square can be useful in distinguishing them from one another. Some of these counts are the same for every isotope of a Latin square and are referred to as isotopy invariants. One such invariant is the number of 2 × 2 subsquares, called intercalates. Another is the total number of transversals, a set of n positions in a Latin square of order n, one in each row and one in each column, that contain no element twice. Latin squares with different values for these counts must lie in different isotopy classes. The number of intercalates is also a main class invariant.
1-ші рет
Бірінші реттік үшін 1 символы бар бір ғана латын квадраты және {1} негізгі жиынтығымен бір квазитоп бар; ол топ, тривиалды топ.
For order one there is only one Latin square with symbol 1 and one quasigroup with underlying set {1}; it is a group, the trivial group.
6-10-тармақтар
Латын квадраттарының саны, реті ұлғайған сайын, комбинаторлық жарылыс деп аталатын құбылысты көрсетеді; тіпті көлемінің аздаған өсуіне де үлкен түрлер саны сәйкес келеді. Негізгі сандар келесі екі кестеде келтірілген, ал Кейли 1890 жылы латын квадраттарының санын бесінші ретке дейін білген. 1915 жылы Макмахон мәселеге басқаша қарасты, бірақ бастапқыда бесінші рет үшін дұрыс емес мән алды. М. Фролов 1890 жылы, ал Тарри 1901 жылы алтыншы реттік қысқартылған квадраттардың санын тапты. М. Фролов жетінші реттік қысқартылған квадраттардың санын дұрыс санамады. Р. А. Фишер мен Ф. Ятс, Э. Шёнхардтың бұрынғы жұмысынан хабарсыз, алтыншы ретке дейінгі изотопия кластарының санын берді. 1939 жылы Х. В. Нортон жетінші реттік 562 изотопия класын тапты, бірақ оның әдісі толық емес екенін мойындады. А. Сад 1951 жылы, бірақ 1948 жылы жеке жарияланған, және П. Н. Саксена көбірек кластар тапты, ал 1966 жылы Д. А. Прийс бұл Нортонның нәтижесін 564 изотопия класына түзетті деп атап өтті. Алайда 1968 жылы Дж. В. Браун 563 дұрыс емес мәнін жариялады, ол жиі қайталанды. Ол сондай-ақ сегізінші реттік изотопия кластарының санын дұрыс көрсетпеді. Сегізінші реттік қысқартылған квадраттардың дұрыс санын М. Б. Уэллс 1967 жылы тапқан, ал изотопия кластарының санын 1990 жылы Г. Колесова, С. В. Х. Лам және Л. Тиль тапты. Тоғызыншы рет үшін қысқартылған квадраттардың санын С. Е. Баммель мен Дж. Ротштейн, оныншы рет үшін Б. Д. Маккей мен Э. Рогойски, ал он бірінші рет үшін Б. Д. Маккей мен И. М. Ванлес анықтады.
The number of Latin squares, as the order increases, exhibits the phenomenon known as combinatorial explosion; for even small increases in size there correspond huge increases in varieties. The basic counts are given in the next two tables, and Cayley in 1890, both knew the number of reduced Latin squares up to order five. In 1915, MacMahon approached the problem in a different way, but initially obtained the wrong value for order five. M. Frolov in 1890, and Tarry in 1901, found the number of reduced squares of order six. M. Frolov gave an incorrect count of reduced squares of order seven. R. A. Fisher and F. Yates, unaware of earlier work of E. Schönhardt, gave the number of isotopy classes of orders up to six. In 1939, H. W. Norton found 562 isotopy classes of order seven, but acknowledged that his method was incomplete. A. Sade, in 1951, but privately published earlier in 1948, and P. N. Saxena found more classes and, in 1966, D. A. Preece noted that this corrected Norton's result to 564 isotopy classes. However, in 1968, J. W. Brown announced an incorrect value of 563, which has often been repeated. He also gave the wrong number of isotopy classes of order eight. The correct number of reduced squares of order eight had already been found by M. B. Wells in 1967, and the numbers of isotopy classes, in 1990, by G. Kolesova, C. W. H. Lam and L. Thiel. The number of reduced squares for order nine was obtained by S. E. Bammel and J. Rothstein, for order 10 by B. D. McKay and E. Rogoyski, and for order 11 by B. D. McKay and I. M. Wanless.