Problems in Latin squares

Last updated July 09, 2024

In mathematics, the theory of Latin squares is an active research area with many open problems. As in other areas of mathematics, such problems are often made public at professional conferences and meetings. Problems posed here appeared in, for instance, the Loops (Prague) conferences and the Milehigh (Denver) conferences.

Open problems

Bounds on maximal number of transversals in a Latin square

A transversal in a Latin square of order n is a set S of n cells such that every row and every column contains exactly one cell of S, and such that the symbols in S form {1, ..., n}. Let T(n) be the maximum number of transversals in a Latin square of order n. Estimate T(n).

Proposed: by Ian Wanless at Loops '03, Prague 2003
Comments: Wanless, McKay and McLeod have bounds of the form cⁿ < T(n) < dⁿ n!, where c > 1 and d is about 0.6. A conjecture by Rivin, Vardi and Zimmermann (Rivin et al., 1994) says that you can place at least exp(cn log n) queens in non-attacking positions on a toroidal chessboard (for some constant c). If true this would imply that T(n) > exp(cn log n). A related question is to estimate the number of transversals in the Cayley tables of cyclic groups of odd order. In other words, how many orthomorphisms do these groups have?

The minimum number of transversals of a Latin square is also an open problem. H. J. Ryser conjectured (Oberwolfach, 1967) that every Latin square of odd order has one. Closely related is the conjecture, attributed to Richard Brualdi, that every Latin square of order n has a partial transversal of order at least n − 1.

Characterization of Latin subsquares in multiplication tables of Moufang loops

Describe how all Latin subsquares in multiplication tables of Moufang loops arise.

Proposed: by Aleš Drápal at Loops '03, Prague 2003
Comments: It is well known that every Latin subsquare in a multiplication table of a group G is of the form aH x Hb, where H is a subgroup of G and a, b are elements of G.

Densest partial Latin squares with Blackburn property

A partial Latin square has Blackburn property if whenever the cells (i, j) and (k, l) are occupied by the same symbol, the opposite corners (i, l) and (k, j) are empty. What is the highest achievable density of filled cells in a partial Latin square with the Blackburn property? In particular, is there some constant c > 0 such that we can always fill at least c n² cells?

Proposed: by Ian Wanless at Loops '03, Prague 2003
Comments: In a paper to appear, Wanless has shown that if c exists then c < 0.463. He also constructed a family of partial Latin squares with the Blackburn property and asymptotic density of at least exp(-d(log n)^1/2) for constant d > 0.

Largest power of 2 dividing the number of Latin squares

Let $L_{n}$ be the number of Latin squares of order n. What is the largest integer $p(n)$ such that $2^{p(n)}$ divides $L_{n}$ ? Does $p(n)$ grow quadratically in n?

Proposed: by Ian Wanless at Loops '03, Prague 2003
Comments: Of course, $L_{n}=n!(n-1)!R_{n}$ where $R_{n}$ is the number of reduced Latin squares of order n. This immediately gives a linear number of factors of 2. However, here are the prime factorizations of $R_{n}$ for n = 2, ...,11:

2	3	4	5	6	7	8	9	10	11
1	1	2²	2³7	2⁶37²	2¹⁰35*1103	2¹⁷31361291	2²¹3²5231*3824477	2²⁸3²53137*547135293937	2³⁵3⁴528012206499*62368028479

This table suggests that the power of 2 is growing superlinearly. The best current result is that

R_{n}

is always divisible by f!, where f is about n/2. See (McKay and Wanless, 2003). Two authors noticed the suspiciously high power of 2 (without being able to shed much light on it): (Alter, 1975), (Mullen, 1978).

Related Research Articles

In mathematics, especially in abstract algebra, a quasigroup is an algebraic structure resembling a group in the sense that "division" is always possible. Quasigroups differ from groups mainly in that the associative and identity element properties are optional. In fact, nonempty associative quasigroup equals group.

<span class="mw-page-title-main">Latin square</span> Square array with symbols that each occur once per row and column

In combinatorics and in experimental design, a Latin square is an n × n array filled with n different symbols, each occurring exactly once in each row and exactly once in each column. An example of a 3×3 Latin square is

<span class="mw-page-title-main">Magic square</span> Sums of each row, column, and main diagonals are equal

In recreational mathematics, a square array of numbers, usually positive integers, is called a magic square if the sums of the numbers in each row, each column, and both main diagonals are the same. The "order" of the magic square is the number of integers along one side (n), and the constant sum is called the "magic constant". If the array includes just the positive integers $, the magic square is said to be "normal". Some authors take "magic square" to mean "normal magic square".$

<span class="mw-page-title-main">Heat equation</span> Partial differential equation describing the evolution of temperature in a region

In mathematics and physics, the heat equation is a certain partial differential equation. Solutions of the heat equation are sometimes known as caloric functions. The theory of the heat equation was first developed by Joseph Fourier in 1822 for the purpose of modeling how a quantity such as heat diffuses through a given region.

The abc conjecture is a conjecture in number theory that arose out of a discussion of Joseph Oesterlé and David Masser in 1985. It is stated in terms of three positive integers and that are relatively prime and satisfy . The conjecture essentially states that the product of the distinct prime factors of is usually not much smaller than . A number of famous conjectures and theorems in number theory would follow immediately from the abc conjecture or its versions. Mathematician Dorian Goldfeld described the abc conjecture as "The most important unsolved problem in Diophantine analysis".

In mathematics, the Birch and Swinnerton-Dyer conjecture describes the set of rational solutions to equations defining an elliptic curve. It is an open problem in the field of number theory and is widely recognized as one of the most challenging mathematical problems. It is named after mathematicians Bryan John Birch and Peter Swinnerton-Dyer, who developed the conjecture during the first half of the 1960s with the help of machine computation. Only special cases of the conjecture have been proven.

In combinatorial mathematics, two Latin squares of the same size (order) are said to be orthogonal if when superimposed the ordered paired entries in the positions are all distinct. A set of Latin squares, all of the same order, all pairs of which are orthogonal is called a set of mutually orthogonal Latin squares. This concept of orthogonality in combinatorics is strongly related to the concept of blocking in statistics, which ensures that independent variables are truly independent with no hidden confounding correlations. "Orthogonal" is thus synonymous with "independent" in that knowing one variable's value gives no further information about another variable's likely value.

In mathematics, a Moufang loop is a special kind of algebraic structure. It is similar to a group in many ways but need not be associative. Moufang loops were introduced by Ruth Moufang. Smooth Moufang loops have an associated algebra, the Malcev algebra, similar in some ways to how a Lie group has an associated Lie algebra.

In combinatorics, the Dinitz theorem is a statement about the extension of arrays to partial Latin squares, proposed in 1979 by Jeff Dinitz, and proved in 1994 by Fred Galvin.

Legendre's conjecture, proposed by Adrien-Marie Legendre, states that there is a prime number between $and for every positive integer . The conjecture is one of Landau's problems (1912) on prime numbers, and is one of many open problems on the spacing of prime numbers.$

Combinatorial design theory is the part of combinatorial mathematics that deals with the existence, construction and properties of systems of finite sets whose arrangements satisfy generalized concepts of balance and/or symmetry. These concepts are not made precise so that a wide range of objects can be thought of as being under the same umbrella. At times this might involve the numerical sizes of set intersections as in block designs, while at other times it could involve the spatial arrangement of entries in an array as in sudoku grids.

A Markov number or Markoff number is a positive integer x, y or z that is part of a solution to the Markov Diophantine equation

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.

In the mathematical field of abstract algebra, isotopy is an equivalence relation used to classify the algebraic notion of loop.

The Millennium Prize Problems are seven well-known complex mathematical problems selected by the Clay Mathematics Institute in 2000. The Clay Institute has pledged a US$1 million prize for the first correct solution to each problem.

In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmetic, is the system of arithmetic with the usual elementary properties of 0, 1, +, ×, $, together with induction for formulas with bounded quantifiers.$

In graph theory, the Graham–Pollak theorem states that the edges of an $-vertex complete graph cannot be partitioned into fewer than complete bipartite graphs. It was first published by Ronald Graham and Henry O. Pollak in two papers in 1971 and 1972, in connection with an application to telephone switching circuitry.$

Hunter Snevily (1956–2013) was an American mathematician with expertise and contributions in Set theory, Graph theory, Discrete geometry, and Ramsey theory on the integers.

References

Alter, Ronald (1975), "How many latin squares are there?", Amer. Math. Monthly, 82 (6), Mathematical Association of America: 632–634, doi:10.2307/2319697, JSTOR 2319697 .
McKay, Brendan; Wanless, Ian (2005), "On the number of latin squares", Ann. Comb., 9 (3): 335–344, doi:10.1007/s00026-005-0261-7, S2CID 7289396 .
Mullen, Garry (1978), "How many i-j reduced latin squares are there?", Amer. Math. Monthly, 85 (9), Mathematical Association of America: 751–752, doi:10.2307/2321684, JSTOR 2321684 .
Rivin, Igor; Vardi, Ilan; Zimmerman, Paul (1994), "The n-queens problem", Amer. Math. Monthly, 101 (7), Mathematical Association of America: 629–639, doi:10.2307/2974691, JSTOR 2974691 .

External links

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.