Supersymmetric Latin squares

Latin squares have long been a staple object of study of combinatorics and recreational mathematics.  A Latin square of size n is an n\times n array of elements of some set of n symbols such that each symbol appears exactly once in each row and in each column.  For our purposes, it will be important to have the set of indices for the rows and columns and the set of symbols be the same set.  For some finite index.  The “obvious” choice for the index sets will be \{1,2,3,\ldots,n\} or \{0,1,2,\ldots,n-1\}, but we could use any finite set.  Whenever I display a Latin square here, I will use one of these sets, with row numbers increasing from left to right and column numbers increasing from top to bottom.

It’s illustrative to move from the graphical definition of a Latin square to something more symbolic.  A Latin square on an index set I is a function f assigning each element of I \times I an element I such that for each fixed a\in I, f(a,-) and f(-,a) realize each value in I exactly once.  Blurring the distinction between (I \times I) \times I) and I \times I \times I, we can recast the above definition in the following way.

Definition.  A Latin square on a (finite) index set I is a subset S of I\times I\times I such that, for any fixed a,b\in I, each of the incomplete triples (a,b, - ), (a, - , b), (-, a, b) can be completed to an element of S in exactly one way.  (That is, a subset of I\times I\times I with size |I|^2 whose projection onto any pair of coordinates is exactly I\times I.)

Notice that “function-ness” and the conditions on the rows and columns are absorbed into one pleasantly symmetric condition.  This explains the mysterious fourth paragraph of this Not About Apples post.  (This definition also generalizes gracefully to orthogonal Latin squares; a list of k orthogonal squares corresponds naturally to a subset of I^{k+2} with size |I|^2 whose projection onto any pair of coordinates is exactly I\times I.)  This symmetry also means that S_3 acts naturally on the set of Latin squares on a particular index set by permuting the coordinates.  This led me to think about the following definition.

Definition. A supersymmetric Latin square (ssLs) is a Latin square which (viewed a subset of I\times I\times I) is closed under permutation of coordinates.

That is, a supersymmetric Latin square is in an orbit by itself under the S_3-action.

Example.

There are three supersymmetric Latin squares on {0,1,2}.

021   102   210
210   021   102
102   210   021

For ordinary Latin squares, there is another kind of symmetry.  Rows can be permuted, columns can be permuted, and the symbols themselves can be permuted.  That is, the symmetric group on the index set acts naturally on the set of Latin squares in three ways, by acting on the first, second, or third coordinate of the triples.  This justifies the common convention of assuming without loss of generality that a Latin square has the symbols listed in order across the first row and down the first column; since each of these actions is free (though the composite action of S_I\times S_I \times S_I is not), we have an instant proof that n! divides the number of Latin squares on a set of n (and if you are a little careful, you can improve this to n!(n-1)! for almost no extra work).

This doesn’t work for supersymmetric Latin squares, though; these actions of S_I are not compatible with the action of S_3 in the definition of supersymmetry.  There does, however, exist a natural action of S_I on the set of supersymmetric Latin squares on I, where a permutation of I acts on all permutation .  In further contrast with the ordinary case, this action is not free; it’s not even faithful.

Example.

The first ssLs listed above is stabilized by all of S_3.  The latter two are stabilized by the even permutations; odd permutations interchange them.

I call two supersymmetric Latin squares on I equivalent if they are in the same orbit of this S_I-action.  Likewise, ssls on I is equivalent to an ssls on J if the latter is the image of the former under some bijection I\to J acting on every component of every triple.  I’m interested in classifying supersymmetric Latin squares of size n, up to equivalence.

For n=1,2,4,5, it’s not hard to check that there are no examples.  (Edit: as noted in the comments, that’s just plain not true.)  For n=3 there are the two already given.  Call them \alpha, \beta in the order they are listed in the first example.

There are infinitely many supersymmetric Latin squares. Let me briefly explain the construction of all the ones I know.

There is a natural product on Latin squares.  If S (resp. S’) is a Latin square on I (resp. I’), then we define S\times S', a Latin square on I\times I', by \left\{((a,a'),(b,b'),(c,c'))\in (I\times I')^3~:~(a,b,c)\in S , (a',b',c')\in S'\right\}.  I leave to the reader the verification that this is fact a Latin square, and that it is supersymmetric if S and S’ are.

Since we have two ssLs’s of size 3, we can construct ssLs’s of size 9.  There are four possibilities to consider: \alpha\times \alpha, \alpha\times\beta, \beta\times\alpha, \beta\times\beta.  All will be supersymmetric, of course, but they cannot all be inequivalent.  The middle two are certainly equivalent, since the product operation is commutative up to equivalence.  Now we can just write out  \alpha\times \alpha, \alpha\times\beta, \beta\times\beta.  (In order to write the squares in my preferred way, I have to choose a bijection between \{0,1,2\}^2 and \{0,1,2,3,4,5,6,7,8\}; here I use the one provided by base 3 notation.)

021687354   102768435   435102768
210876543   021687354   354021687
102768435   210876543   543210876
687354021   768435102   102768435
876543210   687354021   021687354
768435102   876543210   210876543
354021687   435102768   768435102
543210876   354021687   687354021
435102768   543210876   876543210

It’s not obvious, but the second and third squares are actually equivalent under e.g. the permutation (0)(14562873).

The same approach enables us to construct two supersymmetric Latin squares \alpha^k=\alpha\times\cdots \times \alpha and \beta^k=\beta\times\cdots \times \beta of size 3^k for k=1,2,3,\ldots.  Any mixed product of \alpha‘s and \beta‘s is equivalent to \beta^k, so we have found all the ssLs’s which arise as products of the ones we know.  These two are inequivalent, because \alpha^k contains all triples of the form (a,a,a) and \beta^k contains no such triples.

Questions.

  1. Do supersymmetric Latin squares exist of any size which is not a power of 3?
  2. For size any positive power of 3, we have found two inequivalent ssLs’s.  Is this a complete list?
  3. We could also consider less strict symmetry conditions, requiring only that the Latin square be invariant under some subgroup of S_3.  If the subgroup is generated by a transposition, then this boils down to considering Latin squares which are symmetric (in the sense of symmetric matrices).  But what about requiring only A_3-symmetry, that the square be invariant under cyclic shifts.  (I haven’t really thought about this yet, but it seems potentially interesting.)
Advertisements

Tags: , ,

13 Responses to “Supersymmetric Latin squares”

  1. Vincent van der Noort Says:

    I was thinking about what you call sslss when I found your blog. I am very happy to find out that I’m not the only one thinking about this, since I don’t seem to get anywhere. Your product construction is very beautiful!

    I’m a bit confused though about your remark that no ssls exists for order 2, 4, 5. What about the following construction:

    Take any abelian group G of order k and an element g in G. Consider the function “addition” from G x G x G to G. The g-level set (i.e. the set {(a, b, c): a + b + c = g} \subset G x G x G forms a Latin square (exactly because of your beautiful definition of a Latin square) and it is supersymmetric due to the group being abelian. This yields at least k sslss of order k for any k (not considering equivalence).

    Where do I go wrong?

    As you write there are only 3 sslss of order 3. They correspond to the three level sets for addition in the only abelian group of order 3. In particular the construction above gives all sslss of order 3. The question I was thinking about when I turned to the internet for help and found your blog was: does the construction also yield all examples for higher orders or are there more?

  2. Cap Khoury Says:

    Vincent! Thank you for your interest.

    As for where you go wrong, you do not go wrong! I made a very careless mistake when I was checking latin squares for supersymmetry which imposed an extraneous condition on the diagonal entries. I thank you for the correction!

    Have you noticed that, if you use your construction to obtain the squares (G,g) (that is, the level set of g in the group G) and (H,h), then (G,g) x (H,h) = (GxH, (g,h))? (The product on the left is my square product, that on the right is the direct product of groups.)

    I suspect that your construction does give all supersymmetric Latin squares, in the sense that given a ssls, we could use it to define a group. But I haven’t nailed down the details.

    And this beautiful connection between groups and Latin squares suggests many more questions… If an ssls DOES come from your construction, is the group G uniquely determined (to isomorphism) by the ssls? Given G and the square (up to equivalence), to what extent is k determined? Given a finite abelian group of order n, we get n different (but not necessarily inequivalent) squares; how many or how few equivalence classes might be represented? Could we actually enumerate all the equivalence classes of sslss?

    You also have provided some leverage on the Latin squares which have only the A3 symmetry that I mentioned at the end of my post. We could construct squares like that by taking groups which need not be abelian, and doing the same construction (except that now we need k to be in the center of the group)! Do we get all such squares in this way?

    You and I should really talk this through more. There is stuff here worth thinking harder about.

    • Vincent Says:

      Yes yes we should really talk this through more! I don’t know if it is better to do it through email or through this webpage. Anyway, I noticed about the products (but only after posting). I am not sure however if I do believe my conjecture that all ssl squares come from groups in this way. Main reason to believe it is that it works for n = 3 and that I am not able to think of other ways to construct sslss. What bugs me however is the fact that if n is prime the conjecture implies that entire square is determined by any single entry while for n non-prime it is not. This seems a bit odd to me, I don’t see where divisors of n come into the story. (Although I vaguely remember that there is some sort of construction of Latin squares using finite fields, so maybe prime numbers do have a special role in this theory after all.)

      Originally I was thinking about maximal subsets of I x I x … x I (d copies) such that an element of this set is determined by any d-1 of its coordinates. (I’ll write the full motivation somewhen later.) I like to think about elements of these sets as rooks in d-dimensional chess that can move in straight lines back and forth in all d directions over the n by n by n by … by n chess board. (So traditionally d=2, n =8.) The sets we’re looking at are then sets of n^(d-1) rooks that do all not threaten eachother. A nice picture, however it was only after a friend pointed out that the d=3 case are Latin squares I could start looking for what is known about this. Oddly there is very little info on the internet about rook configurations it seems. (Or I’m not good at finding information)

      The reason that I bring this up is that in the d=2 case the rook picture makes it clear that for n >=3 the conjecture is obviously false. On the other hand one could hope that the influence of the group S_d becomes stronger and stronger as d increases and it might still be true for d >= 3. I would definitely be happy if that is the case, but as you see I’m ambivalent.

      Now for the question if you can reconstruct the group and the level from the Latin square, yes you can, but in a somewhat anoying way.

      Lets call the zero element in the group e. There are n possibilities: e = 0, e = 1 etc. For each of these situations we can just assume that it is the case and build the multiplication table of the (supposed) group as follows: to find a + b look up the element (say c) in position (a, b). Then look at the element in position (c, e), which (if our assumption on the value of e is correct and the ssls is coming from a group in this way) equals a + b by virtue of k – ((k – (a + b)) + 0) = a + b. (Pretty much like the definition of the group structure on an elliptic curve.)

      Having built all n alledged multiplication tables we can check which ones do actually yield groups. This can be more than one, as seen in the leftmost example of an n=3 ssls where all three choices e=0, e=1, e=2 are consistent. (And all yield k = e.)

      Now none of your ‘real’ questions are answered by this construction, they are just reformulated:

      *Are the groups obtained this way all the same?
      *Are the k’s (upto automorphism of the group) all the same? (Note that once you pick e you can read off the level k (if it exists) as the entry on position (e, e).)
      * Is it possible that none of the constructed ‘multiplication tables’ are actually multiplication tables of groups?

      By its case checking nature the construction does not seem to answer these questions intrinsically, that’s why I call it annoying. However it raises a new question that might be interesting in itself: suppose some of the n tables constructed in this way are NOT coming from groups. Are they still Latin squares?

      I think the natural thing to do right now is have a computer find all sslss for some small values of n and check if they come from groups in the above way (or a smarter one if we can come up with that.)

  3. Vincent Says:

    Hmmm, thinking about it, I think that my remark that for n prime the ssls is determined by one entry is wrong. It is determined by one entry and the choice of a bijection between the group with n elements and the index set. That probably means that it is determined up to your notion of equivalence by one entry, which still gives a special role to prime numbers, but it anihilates my earlier remark that the analogous statement for d=2 is false. So I’m a bit more optimistic about the conjecture now. Nice…

  4. Cap Khoury Says:

    Interesting… I had not thought about these higher-dimensional generalizations, so I need to think more before I can address them. Clearly there is much to do here.

    Regarding supersymmetric Latin squares and your construction, I do have some new results. I’m going to do another post on this topic in the next couple days, and I’ll include the proofs there, but I wanted to get these facts to your attention without delay.

    Let S(G,g) be the square which arises as the set of triples of elements of G which sum to g, and call a supersymmetric Latin square “group-type” if it is equivalent to some S(G,g).

    THEOREM. Suppose 3 does not divide n. Then there is a one-to-one correspondence between equivalence classes of group-type ssls’s of order n and isomorphism classes of abelian groups of order n. That is, S(G,g) and S(H,h) are equivalent iff G is isomorphic to H.

    THEOREM. Not all ssls are group-type. In particular, the square

    AFEDCB
    FBDCEA
    EDCBAF
    DCBAFE
    CEAFBD
    BAFEDC

    is not group-type. Up to equivalence, this is the only ssls of order at most 6 which is not group-type.

  5. Vincent Says:

    Wow fantastic!

  6. Vincent Says:

    Ok, I verified your first theorem, and it cleary extends to any dimension d greater than 3 (replacing n not divisible by 3 by n not divisible by the dimenison). Even though in hindsight the proof is essentially 2 lines, the if part of your statement completely surprised me. Intuitively I had expected that the zero-section could be told apart from the other ones, but apparently it can not. Really great to see how these Latin squares are full of surprises!

    Your non-group-type example fascinates me. How did you find it?

    Here is a new question inspired by your theorems:

    The statement that the ssls contains a unique element of the form (x, x, x) (i.e. entry x in position (x, x)) iff n is not divisible by 3
    is true for group-type squares. (Similarly for elements of the form (x, x, …, x) in the d-dimensional case if n is not divisible by d). Is it true for all sslss?

  7. Vincent Says:

    It turns out that the answer to my last question is ‘no’.

    Here is an example with n = 7 and 4 elements of the form (x, x, x) (unless I made a mistake and this thing is not supersymmetric after all):

    0654321
    6145230
    5426103
    4563012
    3210654
    2301546
    1032465

    So it seems the role of group-type sslss is not as big as the n=3 case suggests. Pity, but still interesting!

    • Vincent Says:

      And here is another example with 7 elements of the form (x,x,x).

      0654321
      6132540
      5321604
      4213065
      3560412
      2406153
      1045236

      I find it a bit disturbing how easy it is to find these examples. There is no clever reasoning behind it, I just wrote the first few numbers and then the puzzle essentially solved itself, like an extra simple sudoku-puzzle. Still I like to believe that these sslss (due to their rich symmetry) ‘come from’ some other ‘special’ object in some unified way…

  8. Vincent Says:

    Hi, sorry for the long silence. After the last few examples I felt that a classification of sslss would be completely out of reach. Later however I realized that my very last example is nothing else than the Fano plane encoded in a somewhat unnatural way and I got some hope that maybe we would be able to find a classification of sslss of order n with n orbits of length 1 and no orbits of length 3, i.e. with the numbers 1 to n on the diagonal.

    Via some detours I found out that these special sslss (or actually the orbits of length 6) already exist under a different name: steiner triple systems. Apparently in the 19th century it has been proven that such systems and hence sslss with numbers 1 to n on the diagonal exist if and only if n is congruent 1 or 3 mod 6.

    Their number growth rather fast: http://oeis.org/A030129

    In particular there are apparently 2 sslss of this type of order 13, although I was not able to find them. I get the impression that the number of Steiner triple systems of order 21 is yet unknown, although we can construct one from the sslss of order 3 and 7 using your construction.

  9. Vincent Says:

    Here I am again. In one of my earlier comments about generalizing your theorem to higher dimensions d there is a mistake: “not divisible by d” should be coprime to d. Nevertheless I will talk about higher d’s some more.

    The above shows I think that there are to many sslss to handle. Hence a different question. Let’s call a ssls ‘rigid’ if it is its own orbit under your equivalence relation. One might also call them hypersymmetric since they have even bigger symmetry groups than ‘ordinary’ supersymmetric latin squares. In d=3 (so latin squares) the only example is in your origional post (n = 3) and it is not hard to show that there are no others. My question is: can we classify all rigid supersymmetric latin (d-1)-cubes for all d?

  10. Vincent Says:

    What I found so far:

    if d odd there are either one or zero solutions depending on whether d is divisible by 3 or not. (Not counting solutions with n = 1 or n = 0). The proof rests on 4 more general but easy results:
    1) For a rigid supersymmertic latin (d-1)-cube, we have that n is at most 1 + the smallest prime divisor of (d – 1).
    2) For n = 2 and n = 3 every supersymmetric latin hypercube for d greater than or equal to 3 is of group type. (This can be shown by induction on d)
    3) For n = 3 the ‘zero section’ group type sslhc is rigid if and only if d is divisible by 3 and the other two are never rigid.
    4) n can not be a divisor of d-1

    Now the question is what happens for d even. Some additional results:

    5) For n = 2 both group type supersymmetric latin hypercubes are rigid if d is even and neither one is when d is odd;
    6) For n = 4 the zero section group type sslhc coming from the Klein four group is rigid if and only if d is even

    So for d = 4 we expect at least 3 solutions and for d = 6 we expect at least 4 solutions. I checked by hand that there are no others for these values of d. In particular all examples I saw so far are of group type. However,I don’t know what to think of that. For the cyclic group of four elements and for every group of five or more elements it is easy to see that no group type sslhc is rigid.

    In semi-related news: statement 2) does not extend to n = 4 and higher; an example of a (non-rigid) non-group type supersymmetric latin cube (d = 4, n =4) is given by the supersymmetric orbits of
    (AAAA),
    (AABB), (AACC),
    (BBDD), (CCDD)
    (AADD), (ABCD)
    (BBBC), (CCCB)
    (DDDD)

    So… I don’t really see why rigid sslhc’s should be group type, but as I said, I know no counterexamples. Do you?

    Hapy holidays,

    Vincent

  11. Vincent Says:

    Bweegh, just found out something that makes this problem a lot less interesting: no matter d, n can be at most 4.

    Suppose n greater/equal 5. Look at the entry in position (0, …, 0, 1, 2) with d – 3 zero’s. There is no value possible that doesn’t violate the combination of supersymmetry and rigidity.

    Of course there is still some question about what happens if n = 4, but the problem is not as interesting anymore as I thought yesterday, I’m sorry.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: