Proof of the Alon-Tarsi Conjecture for n = 2^{r}p

Arthur A. Drisko

National Security Agency Fort George G. Meade, MD 20755 arthur.drisko.td.90@aya.yale.edu

Submitted: April 10, 1998; Accepted: May 10, 1998.

Abstract

The Alon-Tarsi conjecture states that for even n, the number of even latin squares of order n differs from the number of odd latin squares of order n. Zappa [6] found a generalization of this conjecture which makes sense for odd orders. In this note we prove this extended Alon-Tarsi conjecture for prime orders p. By results of Drisko [2] and Zappa [6], this implies that both conjectures are true for any n of the form 2^{r}p with p prime.

1 Introduction

A latin square L of order n is an n × n matrix whose rows and columns are permutations of n symbols, say 0, 1, …, n − 1. Rows and columns will also be indexed by 0, 1, …, n − 1. The sign sgn(L) of L is the product of the signs (as permutations) of the rows and columns of L. L is even, respectively odd, if sgn(L) is +1, respectively −1. A fixed diagonal latin square has all diagonal entries equal to 0.

We denote the set of all latin squares of order n by LS(n) and the set of all fixed diagonal latin squares of order n by FDLS(n). We denote the numbers of even, odd, fixed diagonal even, and fixed diagonal odd latin squares of order n by els(n), ols(n), fdels(n), and fdols(n), respectively.

If n ≠ 1 is odd, then switching two rows of a latin square alters its sign, so els(n) = ols(n). On the other hand, Alon and Tarsi [1] conjectured:

Conjecture 1 (Alon-Tarsi) If n is even then els(n) ≠ ols(n).

Equivalently, the sum of the signs of all L ∈ LS(n) is nonzero. This conjecture is related to several other conjectures in combinatorics and linear algebra [3, 5].

Zappa was able to generalize this conjecture to the odd case by defining the Alon-Tarsi constant

AT(n) = \frac{fdels(n) − fdols(n)}{(n − 1)!}.  (1)

MR Subject Classification (1991): 05B15, 05E20, 05A15

Since any latin square can be transformed into a fixed diagonal latin square by a permutation of rows, and since permuting rows does not change the sign of a latin square of even order, we have

els(n) − ols(n) = \begin{cases}n!(n − 1)! AT(n) & if n is even \\ 0 & if n is odd. \end{cases}  (2)

Only a few values of AT(n) are known [4, 6]:

\begin{matrix}n & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ AT(n) & 1 & −1 & 4 & −24 & 2, 304 & 368, 640 & 6, 210, 846, 720 \end{matrix}

Zappa conjectured this generalization of the Alon-Tarsi conjecture:

Conjecture 2 (Extended Alon-Tarsi) For every positive integer n,

AT(n) ≠ 0.

Aside from the table of known values, we have the following information about AT(n) [2, 6]:

Theorem 1 (Drisko) If p is an odd prime, then

els(p + 1) − ols(p + 1) ≡ (−1)^{\frac{p+1}{2}} p^{2} (mod p^{3}).

This implies that AT(p + 1) ≡ (−1)^{\frac{p+1}{2}} (mod p), by (2).

Theorem 2 (Zappa) If n is even, then

AT(n) ≠ 0 ⟹ AT(2n) ≠ 0,

and if n is odd, then

AT(n) ≠ 0 and AT(n + 1) ≠ 0 ⟹ AT(2n) ≠ 0.

Together, these imply the truth of the Alon-Tarsi conjecture for n = 2^{r}(p + 1) for any r ≥ 0 and any odd prime p (and, by the table of known values, for p = 2 also). Our goal here is to prove that AT(p) ≠ 0 for all primes p. This then implies that the extended Alon-Tarsi conjecture is true for all n = 2^{r}p, where r ≥ 0 and p is any prime.

2 The Result

The approach is the same as in [2]. Let S_{n} be the symmetric group on {0, 1, …, n−1} and let ℑ_{n} = S_{n} × S_{n} × S_{n}. This group acts on the set LS(n) of latin squares of order n by permuting the rows, columns, and symbols, and is called the isotopy group.

Let G be any subgroup of ℑ_{n}. We shall call two latin squares L, M of order n G-isotopic if there exists g ∈ G such that Lg = M. The orbit LG of L under G is the G-isotopy class of L. The G-autotopism group 𝔄_{G}(L) of L is the stabilizer of L in G. Clearly

|G| = |LG||𝔄_{G}(L)|  (3)

for any G < ℑ_{n} and any latin square L of order n.

We need one well-known lemma (see [2] or [4]).

Lemma 3 Let L be any latin square of order n and g = (α, β, γ) ∈ ℑ_{n}. Then

sgn(Lg) = sgn(α)^{n}sgn(β)^{n}sgn(γ)^{2n}sgn(L) = sgn(α)^{n}sgn(β)^{n}sgn(L).

We are now ready for our main result.

Theorem 4 Let p be an odd prime. Then

AT(p) ≡ (−1)^{\frac{p−1}{2}} (mod p).  (4)

Proof. Let

G = {(σ, σ, τ) : σ, τ ∈ S_{p}, 0τ = 0}.  (5)

G acts on FDLS(p). By Lemma 3, sgn(Lg) = sgn(L) for any L of order p and any g ∈ G. Let R be any set of representatives of the orbits of G in FDLS(p), and let S be a set of representatives of those orbits of size not divisible by p. Then

fdels(p) − fdols(p) = ∑_{L∈FDLS(p)} sgn(L),  (6)
= ∑_{L∈R} |LG|sgn(L),  (7)
≡ ∑_{L∈S} |LG|sgn(L) (mod p).  (8)

Since |G| = p!(p − 1)!, |LG| is not divisible by p if and only if p divides |𝔄_{G}(L)|.

Suppose p divides |𝔄_{G}(L)| for some L. Then there is some G-autotopism g = (σ, σ, τ) of L of order p. Since τ ∈ S_{p} fixes 0, τ^{p} = e implies that τ = e. Since g is not the identity, σ^{p} = e implies that σ is a p-cycle, so that ρ^{−1}σρ = (0 1 ⋯ p − 1) for some ρ ∈ S_{p}. Then M = L(ρ, ρ, e) is G-isotopic to L and has G-autotopism ((0 1 ⋯ p − 1), (0 1 ⋯ p − 1), e). It is clear that such an M must have constant diagonals (that is, M_{i,j} = M_{i+1,j+1} for all i, j, taken mod p). But then there is some μ ∈ S_{p}, fixing 0, such that N = M(e, e, μ), where N is the square given by N_{i,j} = i−j (mod p). Hence any L with G-autotopism group divisible by p is G-isotopic to N, so there is only one isotopy class in the sum (8), and its size is not divisible by p. Therefore,

fdels(p) − fdols(p) ≡ |NG|sgn(N) (mod p).  (9)

Now, the columns of N, as permutations, are powers of the p-cycle ϕ = (0 1 ⋯ p−1), so they all have positive sign. Each row, as a permutation, consists of one fixed point and (p − 1)/2 transpositions, and there are an odd number of rows, so

sgn(N) = (−1)^{\frac{p−1}{2}} .  (10)

To determine |NG|, let g = (σ, σ, τ) ∈ 𝔄_{G}(N). We know that h = (ϕ, ϕ, e) ∈ 𝔄_{G}(N), so for some k, gh^{k} = (σϕ^{k}, σϕ^{k}, τ) ∈ 𝔄_{G}(N) and σϕ^{k} fixes 0. Then

iτ = N_{i,0}τ
= N_{iσϕ^{k},0σϕ^{k}}
= N_{iσϕ^{k},0}
= iσϕ^{k}

for all i, so gh^{k} = (τ, τ, τ). But then for all i, j ∈ Z_{p}, the cyclic group of order p, we have

(i − j)τ = N_{i,j}τ
= N_{iτ,jτ}
= (iτ − jτ),

so τ must be an automorphism of Z_{p}. Hence every G-autotopism of N is an automorphism of Z_{p} times a power of h and we have

|𝔄_{G}(N)| = p|Aut(Z_{p})| = p(p − 1),  (11)

and combining this with (3), we get

\begin{aligned}|NG| & = \frac{p!(p − 1)!}{p(p − 1)} \\ & = (p − 1)!(p − 2)! . \end{aligned}  (12)

Finally, combining (9), (10), and (12), we have

AT(p) = \frac{fdels(p) − fdols(p)}{(p − 1)!}

≡ (−1)^{\frac{p−1}{2}} [\frac{(p − 1)!(p − 2)!}{(p − 1)!}] (mod p)

≡ (−1)^{\frac{p−1}{2}} (p − 2)! (mod p)

≡ (−1)^{\frac{p−1}{2}} (mod p),

(13)

since (p − 2)! ≡ 1 (mod p), by Wilson’s theorem. □

Let us record the known cases of the extended Alon-Tarsi conjecture as

Corollary 5 Let p be any prime and r any nonnegative integer. Then

AT(2^{r}p) ≠ 0 and AT(2^{r}(p + 1)) ≠ 0.

Although the truth of the extended conjecture is still unknown for n = 9, the first even value of n which is not of the form given in Corollary 5 is 50, whereas the previous first unknown case of the original Alon-Tarsi conjecture was n = 22.

References

[1] N. Alon and M. Tarsi, Coloring and orientations of graphs, Combinatorica 12 (1992), 125–143

[2] A. A. Drisko, On the number of even and odd latin squares of order p+1, Adv. Math. 128 (1997), 20–35.

[3] R. Huang and G.-C. Rota, On the relations of various conjectures on Latin squares and straightening coefficients, Discrete Math. 128 (1994), 237–245.

[4] J. C. M. Janssen, On even and odd latin squares, J. Combin. Theory Ser. A 69 (1995), 173–181.

[5] S. Onn, A colorful determinantal identity, a conjecture of Rota, and latin squares, Amer. Math. Monthly 104 (1997), 156–159.

[6] P. Zappa, The Cayley determinant of the determinant tensor and the Alon-Tarsi conjecture, Adv. Appl. Math. 19 (1997), 31–44.