1
$\begingroup$

I would like to prove the claim that pandiagonal latin squares, which are of form

                  0        a          2a         3a         ...  (n-1)a
                  b        b+a        b+2a       b+3a       ...   b+ (n-1)a
                  .        .          .
                  .        .          .
                  .        .          .
                  (n-1)b   (n-1)b +a  (n-1)b +2a (n-1)b +3a  ...  (n-1)(b+a)

for some $a,b\in (0,1...n-1)$ cannot exist when the order is divisible by 3.

I think we should be able to show this if we can show that the pandiagonal latin square of order $n$ can only exist iff it is possible to break the cells of a $n \times n$ grid into $n$ disjoint superdiagonals. Then we would show that an $n\times n$ array cannot have a superdiagonal if $n$ is a multiple of $2$ or $3$. I am, however, not able to coherently figure out either part of this proof. Could someone perhaps show me the steps of both parts?

A superdiagonal on an $n \times n$ grid is a collection of $n$ cells within the grid that contains exactly one representative from each row and column as well as exactly one representative from each broken left diagonal and broken right diagonal.

EDIT: Jyrki, could you please explain how the claim follows from #1?

  • 0
    Did I get it right? The claim is that a latin square of this form cannot be pandiagonal, when $n$ is divisible by three? Your title suggests that this is the case, but your first sentence does not really claim anything!2012-07-20
  • 0
    The entries in an $n\times n$ Latin square are supposed to be taken from $1,2,\dots,n$, right? But the entries in the square above are bigger, so how is this a Latin square?2012-07-20
  • 0
    Try the following exercise. Experiment with different values of $a$ and $b$ (reducing all the entries modulo $n=3k$). Try to do it in such a way that 1) some entries on the first row are not divisible by 3, 2) some entries on the first column are not divisible by 3, 3) some entries on the diagonal are not divisible by 3, and last but not least 4) all the broken back-diagonals have entries not divisible by 3. Try it first with $n=6$. Trying things out like this is the way to enlightenment. You will not benefit anything from me spelling out a proof for you.2012-07-20
  • 0
    @Jyrki, the entries are supposed to be reduced modulo $n$, which equals $3k$? Fabulous! I would never have guessed that, and Danielle likes keeping secrets.2012-07-21
  • 0
    @Gerry: You're right,of course. I am just enjoying this game of guessing what the question really is. Sorry to get in the way of your effort to squeeze these bits from OP (particularly in light of me criticizing your recent answer in MO - not my best day).2012-07-21
  • 0
    @Jyrki, your criticism led me to find an answer I like better than what I had before. And I'm just jealous that you were able to figure out what OP wanted here, when I couldn't.2012-07-21

1 Answers 1

2

[Edit: replacing the old set of hints with a detailed answer]

Combining things from the question as well as its title and another recent question by the same use tells me that the question is the following. When $n$ is divisible by three, show that no combination of parameters, $a,b\in R=\mathbb{Z}/n\mathbb{Z}$ in a general recipe $L(i,j)=ai+bj, i,j \in R$ for constructing latin squares, gives rise to a latin square with the extra property (=pandiagonality) that the entries on each broken diagonal parallel to either main or back diagonal are all distinct.

The first thing we observe that $a$ cannot be divisible by three or, more precisely, it cannot belong to the ideal $3R$. For if it were, then all the entries on the first row would also be in the ideal $3R$. Consequently some numbers, for example $1$, would not appear at all on the first row, and the construction would not yield a latin square at all.

Similarly, the parameter $b$ cannot be divisible by three, as then the first column would only contain numbers divisible by three.

So both $a$ and $b$ are congruent to either $1$ or $2$ modulo $3$. We split this into two cases. If $a\equiv b \pmod 3$ (i.e. both congruent to one or both congruent to two), then $a-b$ is divisible by three. When we move one position to the right and one up in the shown diagram, we always add $a-b$ (modulo $n$) to the entry. This means that the entries along an ascending broken diagonal are all congruent to each other modulo three. Again some entries will be missing as the entries are limited to a coset of the ideal $3R$.

The remaining case is that one of $a,b$ is congruent to $1$ modulo $3$ and the other is congruent to $2$ modulo $3$. In that case their sum $a+b$ will be divisible by three. When we move one position to the right and one down on the table, we add $b+a$ (modulo $n$) to the entry. This means that the entries along a descending broken diagonal are all congruent to each other modulo three, and we run into a similar contradiction as earlier.

To summarize: The solution relies on the special property of number three that for all integers $a,b$ the product $ab(a-b)(a+b)$ will be divisible by three, so in one of the four critical directions (horizontal, vertical, descending/ascending diagonal) the entries will always congruent to each other modulo $3$.

  • 0
    How would the claim follow from #1?2012-07-20
  • 0
    @Danielle: All the entries in such a (broken) diagonal will be congruent to each other modulo $3$. Hence they cannot all be distinct.2012-07-20
  • 0
    also, why must a and b be coprime to n? could you prove that?2012-07-20
  • 0
    If they are not, you get repetitions on rows or columns.2012-07-20
  • 0
    I am still not able to get the proof. Could you maybe show me at least part of it if not all?2012-07-20
  • 0
    You might benefit from reviewing elementary number theory: congruences, divisibility and such. I don't have the time now to flesh this out. Will return to this later, unless somebody else helps you out meanwhile.2012-07-20
  • 0
    when you say one of these increments are you referring to a+b and a-b?2012-07-20
  • 0
    Yes. ${}{}{}{}{}$2012-07-20
  • 0
    You say "Here $a$ and $b$ must be comprime to $n$, and in particular neither must be divisble by three." Why must neither be divisible by 3?2012-07-20
  • 0
    @Danielle, try (with for example $n=6$ or $n=9$) what happens with the first row, when $a$ is divisible by $3$.2012-07-21