Supersymmetric Latin squares

July 4, 2011

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

Speaking of the Gamma Function…

October 8, 2010

Yesterday I gave a talk to the University of Michigan undergraduate Math Club on extensions and generalizations of the factorial function.  (I talked about in what senses the gamma function is and is not unique as an extension of n!, mentioned the Hadamard gamma and other entire extensions, and for dessert defined Bhargava’s factorials.)  In that talk I told an anecdote (true story, and the “I” of the story really is me) which I actually hadn’t been planning to tell; it just came out.  But the laughter was so great that I thought I’d post it here also.

Speaking of the gamma function, I was teaching a probability class, and it so happened that integrals of the form \int_0^\infty t^{z-1}e^{-t}\/dz came up frequently in the examples and homework.  I overheard two of my students remarking on this phenomenon before class.

“I’ve noticed that integrals like that always come out to factorials,” said the first guy, “1, 2, 6, and so on.”

So now he has my undivided attention.  This kid wasn’t even a math major, and he picked up on the pattern.  He’s clearly not done talking, and I want to know what his next piece of insight is going to be.

“It’s kinda useful,” he went on, “because when I need to figure out a big factorial I don’t know, like 19! or something, I can just write down the integral and do it on my calculator.”

To this day, I consider it one of my greatest accomplishments as an educator that I did not laugh nor spray the coffee I was drinking out my nose.

“Why don’t you just use the factorial button?” asked his friend.

“There’s a factorial button?”

The One Four Puzzle (?!)

August 13, 2010

I spend a couple hours a week with Mel Hochster, chair of the math department here at UMich, for the very serious purpose of doing cryptic crossword puzzles, a shared interest.  We almost never discuss actual math problems, but last week was an exception.  He says this is something he thought of a while back but never made much progress.

Suppose a set of positive integers contains the number 4 and is closed under the maps n\mapsto n! and n\mapsto \lfloor\sqrt{n}\rfloor.  Must the set be all of $\mathbb{Z}^+$?

The motivation comes from that game that almost everyone who likes to play with numbers has played, the four fours game, where you try to express various numbers in terms of four 4s and whatever operations you may wish.

This is the corresponding game with only one 4; accordingly, we only use unary operations, and only those which return integers.  What numbers can be expressed by starting with a 4, using factorials to go up, floored square roots to come down, going back and forth between these as desired.  Mel Hochster has verified by computer that all positive integers up to 1000 are so expressible and conjectures that all positive integers are.

But how to prove it.  He says that he asked Conway, who said something like “It’s hopeless.”  Not encouraging, sure, but I’m a person who spends time working on the Collatz problem, about which Erdős famously said “Mathematics is not ready for such problems.”

Apparently I have no idea when I’m out of my depth.  But it seems an interesting puzzle.  A good place to start seems to be a rather easier question.

Let n be a positive integer.  Let F(n) be the minimal m such that \left\lfloor (m!)^{1/2^{-k}}\right\rfloor = n for some integer k.  Can we get any nontrivial estimates on how F(n) grows?

Comparing Nested Binomial Coefficients

August 13, 2010

Lately I’ve been becoming more and more interested in enumerative combinatorics.  Back in the days of contest math problems, I loved counting problems; they were one of my best strengths.  Until the gorgeous sequence of talks by Richard Stanley at January’s Joint Meetings, I never really realized that enumerative combinatorics was of interest to “real, serious” mathematicians.  Now that I know, I’ve been thinking more and more about these problems.

So last weekend at MathFest, I was pleased to learn of the following inequality involving binomial coefficients.

Let 1<a<b<c be positive integers. \displaystyle \binom{\binom{c}{b}}{a}<\binom{\binom{c}{a}}{b}.

Apparently this inequality has been proven, but only by a lengthy and uninspiring computation involving estimating gamma functions.  There is not yet a combinatorial proof.  What do I mean by a combinatorial proof of an inequality?  I mean an interpretation of each of the nested binomial coefficients as the number of objects in some set, and then an explicit bijection of one set with a proper subset of the other.

In this case, I am thinking of \displaystyle \binom{\binom{c}{b}}{a} as counting the number of ways to choose a different (not necessary disjoint) b-element subsets of a set of c elements.  For definiteness I can take the set of c elements to be \{1,2,3,\ldots, c\}, list the elements of a subset in increasing order, and list the subsets in lexicographical order.  This suggests the following combinatorial formulation of the inequality.

Let 1<a<b<c be positive integers.  Let S be the set of a\times b matrices with entries in \{1,2,3,\ldots, c\}.  Let A consist of those matrices in S for which the elements in each row are strictly increasing, and the rows are lexicographically strictly increasing.  Let B consist of those matrices in S for which the elements in each columns are strictly increasing, and the columns are lexicographically strictly increasing.  Find an explicit bijection of A of some proper subset of B.

Haven’t cracked it yet, but I’m enjoying the attempt.

Progress! (Apollonian Sphere Packings)

August 12, 2010

Since giving the recent talk, I had a bit of a breakthrough.  Two of the problems I mentioned are no longer open!  I now know (and can prove) the following:

Theorem: If a,b,c are nonzero integers, at most one of which is negative, then the numberN_3(a,b,c) of inequivalent occurrences of three mutually tangent spheres of curvature a,b,c is the same as the number of algebraic integers in {\mathbb{Q}}(\sqrt{-3}) with norm (ab+ac+bc), up to multiplication by a unit.  The bijection between algebraic integers with that norm and triples of spheres is natural and explicit.

There is a nice way to compute this number.  Define an arithmetic function \eta on the positive integers as follows.  If p=2 or p\equiv -1\pmod 6, then \eta(p^k)=1 if k is even and \eta(p^k)=0 if k is odd; if p\equiv 1 \pmod 6, then \eta(p^k)=k+1; \eta(3^k)=1 for all k.  Extend \eta to all positive integers by multiplicativity.  Then N_3(a,b,c)=\eta(ab+ac+bc).

Theorem: If a,b are nonzero integers, at most one of which is negative, then the numberN_3(a,b) of inequivalent occurrences of tangent spheres of curvature a,b is given by the formula N_3(a,b) = \left\lceil \frac{1}{12}\left(M_\star+3M_1+3M_3\right)\right\rceil + X.  Here M_\star is the number of solutions (u,v) to the congruence u^2+uv+v^2\equiv ab \pmod{a+b}, M_k is the number of solutions u to the congruence ku^2\equiv ab \pmod{a+b}, and X is 1 if 12|(a+b) and (a+b)|ab, otherwise 0.

(This strange formula comes from an application of Burnside’s Counting Lemma; as always in these problems, the trickiest part is keeping track of which solutions correspond to the same packing.)

The next natural problem in the progression, counting the total number of inequivalent occurrences of a given curvature in integer sphere packings, remains resistant to my current approach.

In the next week, I should have the corresponding result for counting occurrences of a given n-tuple of n-dimensional hyperspheres.  If I’m lucky, my 2- and 3-dimensional techniques will generalize to let me count occurrences of (n-1)-tuples in n dimensions, but I can’t be sure of that part yet.   Beyond that, I currently have no idea how to proceed.

Cap’s MathFest2010 Talk

August 6, 2010

I’m currently in Pittsburgh for the 2010 MathFest conference.  (My probability students must be heart-broken; I had to cancel a class for the endeavour.)  I’ve learned a lot already, and the conference is only half-over.  But I didn’t just come to listen; I also came to give a talk.

You can get the talk slides here.  (Just right-click and select “Save”.)

If you want more in-depth information on Apollonian Circle Packings, the best place to start is probably a sequence of five papers.  (If you want to really know everything, I recommend reading them in the listed order; if your interests are more strictly number-theoretic, then perhaps start with the fourth and jump back to the earlier papers on an as-needed-basis.)  The first four are by Graham, Lagarias, Mallows, Wilks, and Yan.  The fifth is by Erikkson and Lagarias.

A reference for Elena Fuchs’ result is here.

Sarnak’s letter to Lagarias (in which is proved the “twin prime conjecture”) is here.

As Morpheus says, time is always against us.  These slides were written for a 15-minute talk, and I could easily have given two 60-minute talks on this topic, and a third on the generalizations I’ve been playing with most recently.

This talk was part of a special session on open and accessible problems in number theory and algebra, and I tailored it accordingly.  You’ll notice that I’ve written a lot more about questions I haven’t answered than questions I have.  My own discoveries were present only “obliquely”.  Upon my return to Michigan, I hope to complement these slides with some more posts including material from my papers-in-progress and my freshest thoughts on this subject.  So there’s more on the way.

Most importantly (and those of you who saw my talk will know this already), if any part of this interests or intrigues you, contact me.  Use comments here, email me, find your way to the Cafe Aroma in Fenton, whatever.  Graduates and undergraduates, I’m talking to you.  There is a lot of accessible stuff here at a lot of levels and with a lot of flavors.  Want to collaborate?  I am friendly, and I will always work with students.  Just want some more information?  Please ask; if I don’t know the answer, I will find someone who does.

Rectangles with an Integral Side Length

August 3, 2010

I was recently reminded of this result, one of my all-time favorites due to its utterly unexpected method of solution.

Theorem.

Call a rectangle semi-integral if it has at least one side of integer length. Suppose that a rectangle is decomposed into a finite collection of smaller rectangles, each of which is semi-integral. Then the original rectangle is semi-integral.

Of course this would be trivial if we were talking about “fully integral” rectangles with both sides of integer length, but as it stands it is far from obvious.  It is certainly possible to decompose a rectangle into a collection of semi-integral rectangles in such a way that some rectangles have non-integral length and others have non-integral width, and based purely on geometric concerns, it seems plausible that a counterexample might exist.  Amazingly (to me), the simplest proof I know is this theorem is through integral calculus (and it is very simple indeed)!

Proof of Theorem.

Orient the rectangles so that the sides are parallel to the coordinate axes, so that every rectangle involved has the form R=[a,b]\times [c,d].  For any real numbers \alpha,\beta, consider the function f(x,y)= \cos(2\pi x+\alpha)\cos(2\pi y+\beta).  The integral of this function over a rectangle, \int_a^b\int_c^d f(x,y) \/dy\/dy is relatively easy to compute: \frac{1}{4\pi^2}\left(\sin(2\pi b + \alpha)-\sin(2\pi a+ \alpha)\right)\left(\sin(2\pi d + \beta)-\sin(2\pi c+ \beta)\right).  By the periodicity of the sine, this integral will vanish for every $\alpha,\beta$ if and only if the rectangle is semi-integral.  If f integrates to 0 on every subrectangle in the decomposition, then f integrates to 0 on the large rectangle. \square.

Note that the proof immediately generalizes to higher dimensions!  If an n-dimensional box is decomposed into a finite union of sub-boxes, each of which has at least one integral side length, then the original box has at least one integral side length.

The mathematician Alain Connes has publicly said that one cannot truly understand the integers if one does not understand this problem.

Idle remarks on the Furstenburg topology

July 10, 2010

There are numerous proofs of the infinitude of primes in the literature, but for my money the “cutest” is the “topological proof” due to Hillel Furstenburg.

Make $\mathbb{Z}$ into a topological space by taking as a neighborhood basis the set of arithmetic progressions $A(a,d):=\{a+nd:n\in\mathbb{Z}\}$ (where d>0, of course).  It’s not hard to check that this really is a topology, and that it has the following interesting properties.

  1. The union of finitely many arithmetic progressions is both closed and open.  (Look modulo the gcd of the various differences in the progressions; this set and its complement are each unions of residue classes.)
  2. Any open set which is not empty is infinite.  (Obvious, since the neighborhoods are all infinite.)
  3. The set S=\bigcup_{p\mbox{ prime}} (p\mathbb{Z}) is open; by 1, it is also closed if there are only finitely many primes.
  4. But \mathbb{Z}\setminus S=\{\pm 1\} is finite, so \mathbb{Z}\setminus S is not open, and S is not closed.

That’s the whole proof.  Once you introduce the topology, the theorem practically proves itself!

(If someone has written about this topology and given it an official name, then I don’t know about it; “Furstenburg topology” seems as good a name as any for now.)

Read the rest of this entry »

Counting Problems in Apollonian Circle Packings

July 8, 2010

I’ve spent most of the last year and a half contemplating pretty pictures like the one that follows. These pictures, called Apollonian circle packings, have captivated me since I heard Sarnak speak on them at the 2009 Joint Meetings.

Apollonian circle packing with root quadruple (-1,2,2,3)Apollonian circle packing with root quadruple (-1,2,2,3)

Pictures such as these are constructed by inscribing a triple of three circles inside a larger circle, inscribing a circle in each lune created, and iterating the process. The numbers labelling the circles are the curvatures (1/radius). (The exterior circle has radius 1, but because it is exterior we say that it’s curvature is -1 by convention.) To a number theorist, the amazing fact is that if the four circles we begin with have integral curvature (in the figure, the starting circles have curvature -1, 2, 2, 3), or indeed if any four mutually tangent circles in such a packing have integral curvature, all the rest of the circles automatically have integral curvature. Such pictures are called integer Apollonian circle packings (IACPs).

One question I like to think about, the one that got me into the subject, is to think about which numbers appear in IACPs. That is, think about all PACPs at once. How many times does a given curvature appear? What pairs of numbers can appear? How often? All of my counting is up to symmetry; the picture above, for example, accounts for only one occurrence of 6, not four, and only one occurrence of the pair (2,3).

It turns out that answers to these counting problems can be unexpectedly elegant.

(Note: as the “Out[56]” which I clumsily left in the picture suggests, I generated this diagram and all my other Apollonian pictures using Mathematica 7; please contact me if you’re interested in methods for constructing pictures of this sort.)

0. Some basics

Four numbers (a,b,c,d) are the curvatures of four mutually tangent circles iff they satisfy the Descartes equation a^2+b^2+c^2+d^2=2(ab+ac+ad+bc+bd+cd).

Given a triple of mutually tangent circles with curvatures (a,b,c), the possible curvatures of a fourth circle are the roots of the above equation, viewed as a quadratic in d; in general there are two possibilities, a+b+c\pm\sqrt{ab+ac+bc}. In particular, their sum is 2(a+b+c). If we know one curvature d, then the “other” possibility is d'=2(a+b+c)-d.

A nice upshot of this is that, if we know the curvatures of four mutually tangent circles in a packing, we can compute all the rest using only addition and subtraction!

Read the rest of this entry »

Hello world, mathematically.

July 8, 2010

One of my favorite things to do as a mathematician is to drop in on one of my colleagues and ask them about what they’re working on at the moment.  Mathematics is a big place, and what’s second nature to someone else may be quite novel to you.

That’s the idea behind Cap’s Whiteboard.  This blog is offered as your way to drop in on me and hear about the mathematics that I’m learning, that I’m thinking about, that I’m doing. Think of these posts as what might happen if you asked me about my office blackboard, or one of my home whiteboards.  Expect some combination of my latest research, problems I’m chewing on, particularly interesting articles I’ve read, and my idiosyncratic perspectives on “familiar” mathematics.

This is intended as blog written by a mathematician for other mathematicians, and I’m not making any promises that individual posts will be self-contained. Some stuff will be suitable for strong math majors, some for graduates, and likely some will only be for number theorists.  Please feel free and encouraged, though, to ask me (by email or, preferably, in comments) for references if you want some background on anything you see here.

Posts are on no set schedule, and the amount of time between posts will probably have a high variance, depending on what else is going on for me mathematically.  I expect to average about a significant post a week, not counting links and the like.


%d bloggers like this: