\documentclass[12pt]{article}
\usepackage{temp-ejc}
\specs{P3.43}{21(3)}{2014}

\title{\bf Proof of the List Edge Coloring Conjecture for Complete Graphs of Prime Degree}

\author{Uwe Schauz\\%\thanks{Thanks to the editors of this wonderful journal!}\\
\small Department of Mathematical Science\\[-0.8ex]
\small X\'ian Jiaotong-Liverpool University\\[-0.8ex] 
\small Suzhou 215123, China\\[-0.8ex]
\small \texttt{uwe.schauz@xjtlu.edu.cn}
}

\date{\dateline{Feb 3, 2014}{Sep 9, 2014}{Sep 18, 2014}\\
\small Mathematics Subject Classifications:
  05C15, 05E18, 05E99, 05A19, 91A43\\[5mm]
\textbf{\textit{Dedicated to the memory of David Cariolaro}}\\[5mm]}
%12. July 1969? - 10. Jan. 2014


%%%%%%%%%%%%%%%%%%
%%%   Pakete   %%%
%%%%%%%%%%%%%%%%%%

%%  Fehlersuche  %%
\usepackage{fixltx2e}
%verbesserte Fehlerkorrektur und -suche (Kompatibel mit 2e-Texten!).
%\usepackage{showkeys}%Verweis-Marken in der DVI-Ausgabe.
%\listfiles%Liste der eingelesenen Dateien am Ende des Log-Bereichs.
%\hfuzz1pc % Do not bother to report overfull boxes if overage is < 1pc
%\vfuzz2pt % Do not report over-full v-boxes if over-edge is small

%%  Eingabe  %%
\usepackage[ansinew]{inputenc}
\usepackage{srcltx}

%%  Sprache,Darstellung  %%
\usepackage{ngerman}
\selectlanguage{USenglish}

%%  Text-Symbole  %%
\usepackage{textcomp}

%%  Grafik  %%
\usepackage{color}
\usepackage{cancel}
\usepackage{hyperref}

%%  Mathematik  %%
\usepackage{amsmath}
\usepackage{amsthm}

%%  Mathematik-Symbole  %%
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{bm}

%%  Tabellen  %%
\usepackage{enumerate}

%%  Sonstiges  %%
\usepackage{afterpage}
\usepackage{xspace}

%%%%%%%%%%%%%%%%%%%%%%%%
%%%   Definitionen   %%%
%%%%%%%%%%%%%%%%%%%%%%%%

%\newtheoremstyle{Theorem}{.7\baselineskip}{1\baselineskip}{\itshape}{}{\bfseries}{.}{ }{}
%\theoremstyle{Theorem}
\theoremstyle{theorem}
\newtheorem{Satz}{Theorem}[section]
\newtheorem{EquiDef}[Satz]{Equivalence and Definition}
\newtheorem{Korollar}[Satz]{Corollary}
\newtheorem{Verallgemeinerung}[Satz]{Generalisation}
\newtheorem{Proposition}[Satz]{Proposition}
\newtheorem{DefinitionProposition}[Satz]{Definition and Proposition}
\newtheorem{Lemma}[Satz]{Lemma}
\newtheorem{Vermut}[Satz]{Conjecture}
\newtheorem{Algorithmus}[Satz]{Algorithm}
\newtheorem{Spiel}[Satz]{Game}

\newtheoremstyle{Definition}{.6\baselineskip}{.8\baselineskip}{}{}{\bfseries}{.}{ }{}
\theoremstyle{Definition}
\newtheorem{Definition}[Satz]{Definition}
\theoremstyle{definition}
\newtheorem{Beispiel}[Satz]{Example}

\theoremstyle{remark}
\newtheorem{Bemerkung}[Satz]{Remark}
\newtheorem*{Notation}{Notation}

\newenvironment{sequation}{\begin{small}\begin{equation}}{\end{equation}\end{small}}
\newenvironment{sequation*}{\begin{small}\begin{equation*}}{\end{equation*}\end{small}}
\newenvironment{Beweis}[1][Proof]{\begin{proof}[#1]}{\end{proof}}
\newcommand\ps{\small}
\newenvironment{proofsize}[1]{\begin{small}#1}{\end{small}}
  %setzt eine Box am folgenden Zeilenanfang, damit kein Leerzeichen folgt:
  %"\end{proofsize}%" %!
\newcommand\psize[1]{\begin{proofsize}#1\end{proofsize}}
\newcommand\spsize[1]{\footnotesize{#1}}
\newcommand\textps[1]{\text{\psize{#1}}}
\newcommand\textsps[1]{\text{\spsize{#1}}}

%%  nichtmathematische Befehle  %%
\definecolor{dred}{rgb}{0.9,0,0}
\newcommand\red{\color{dred}}
\newcommand\blue{\color{blue}}
\newcommand\Index[1]{\index{#1}#1}
\newcommand\dashed[1]{\hbox{-- }#1\hbox{ --}\xspace}
\newcommand\ms{\hspace{\mathsurround}}
\newcommand\noms{\hspace{-\mathsurround}}
\newcommand\vsp{\vspace{1ex}}
\newcommand\vspp{\vspace{3ex}}
\newcommand\printday{\today\xspace}
\newcommand\Zeit{\xxivtime\xspace}%oder \ampmtime
\newcommand\Rand[1]{%\mbox{}
  \marginpar{\raggedleft\scriptsize\hspace{0pt}#1}}%
  %Randbemerkungen mit Trennung und korrekter Positionierung.
\newcommand\tRand[1]{\Rand{#1}#1}
\newcommand\Emph[1]{\Rand{\emph{#1}}\emph{#1}}


%%  Mathematik-Befehle  %%
\renewcommand{\(}{\noms$}
\renewcommand{\)}{\noms$}
\renewcommand\frac[2]{\genfrac{}{}{.4pt}{}{#1}{#2}}%EJC erzeugt zu breite Linien.
\renewcommand\tfrac[2]{\genfrac{}{}{.4pt}{1}{#1}{#2}}
\renewcommand\dfrac[2]{\genfrac{}{}{.4pt}{0}{#1}{#2}}
\renewcommand\atop[2]{\genfrac{}{}{0pt}{}{#1}{#2}}
\newcommand\mathRand[1]{\hspace{\mathsurround}\Rand{#1}\nolinebreak\noms}
\def\rand #1"#2"{\mathRand{\(#2\)}#1#2}
\def\randd #1"#2"#3\randd#4"#5"{\mathRand{\(#2\), \(#5\)}#1#2#3#4#5}

\newcommand\eqby[2][=]%
  {\ensuremath{\overset{\makebox[0pt]{\ensuremath{\smash[t]{\scriptstyle#2}}}}{#1}}}

\renewcommand\o{\emptyset}%\varnothing}
\newcommand\K{\mathbb{K}}
\newcommand\F[1][\ ]{\mathbb{F}_{\!#1}}
\newcommand\C{\mathbb{C}}
\newcommand\R{R}%{\mathcal{R}}
\newcommand\Rn[1][n]{\R\,\n[#1]}
\newcommand\Rl{\mathbb{R}}
\newcommand\Q{\mathbb{Q}}
\newcommand\Z{\mathbb{Z}}
\newcommand\N{\mathbb{N}}
\renewcommand\L{\mathcal{L}}
\newcommand\M{\mathcal{M}}

\renewcommand\sb{\subseteq}%vorher: XX\sb{index}=XX_{index}
\renewcommand\sp{\supseteq}%vorher: XX\sb{ex}=XX^{ex}
\newcommand\nin{\notin}
\newcommand\nni{\not\ni}
\newcommand\sm{\setminus}
\newcommand\ssm{\textup{\texttt{\char92}}}
\newcommand\Ssm{\textup{\texttt{\char92\!\!\char92}}}
\newcommand\down{\downharpoonright}
\newcommand\up{{\upharpoonright}}
\newcommand\mto{\mapsto}
\newcommand\lmto{\longmapsto}
\newcommand\lto{\longrightarrow}
\newcommand\To{\Rightarrow}
\newcommand\lTo{\Longrightarrow}
\newcommand\Eqi{\Leftrightarrow}
\newcommand\lEqi{\Longleftrightarrow}
\newcommand\nach{\mathbin\circ}%\triangleleft}
\newcommand\vor{\mathbin\triangleright}
\newcommand\fa{\forall\,}
\newcommand\ex{\exists\,}
\newcommand\nex{\nexists\,}
\newcommand\DP{\colon\discretionary{\!\kern -.17em}{}{}}
% ":" als Interp.-zeichen mit Trennst.
\newcommand\mitsymbol{\textup{\textbrokenbar}}
\renewcommand\mit{\,\ \discretionary{\mitsymbol}{}{}\mitsymbol\ \,}
%\mit{} war altes \mathit{}
\newcommand\eqn[1][\neq]{\mathrel{\equiv\joinrel#1}}
\renewcommand\div{\mathrel{\bigm\lfloor\!\!\!\bigm\lfloor}}
\newcommand\vid{\mathrel{\bigm\rfloor\!\!\!\bigm\rfloor}}
\newcommand\ndiv{\mathrel{\;\!\div\hspace{-12pt}\kern0pt\lower2pt%
  \hbox{\ensuremath{^\diagup}}\!}}
\newcommand\ndivps{\mathrel{\;\!\div\hspace{-9pt}\kern0pt\lower2pt%
  \hbox{\ensuremath{^\diagup}}\!}}
\newcommand\n[1][n]{{\phantom{|}}^{\!\!\!\!#1}}
\newcommand\nvid{\mathrel{\;\!\vid\hspace{-12pt}\kern0pt\lower2pt%
  \hbox{\ensuremath{^\diagup}}\!}}
\newcommand\nvidps{\mathrel{\;\!\vid\hspace{-9pt}\kern0pt\lower2pt%
  \hbox{\ensuremath{^\diagup}}\!}}
\providecommand\abs[1]{\lvert#1\rvert}
\providecommand\Abs[1]{\bigl\lvert#1\bigr\rvert}
\newcommand\spn[1]{\langle#1\rangle}
\newcommand\Spn[1]{\bigl\langle#1\bigr\rangle}

\newcommand\cC{\mathcal{C}}
\newcommand\cS{\mathcal{S}}
\renewcommand\d{\delta}
\DeclareMathOperator\sgn{sgn}
\DeclareMathOperator\Fix{Fix}
\DeclareMathOperator\ISLS{ISLS}
\DeclareMathOperator\USLS{USLS}
\DeclareMathOperator\RUSLS{RUSLS}

\newcommand\e{\varepsilon}
\newcommand\E{\lozenge}
\newcommand\cop[1]{\lfloor#1\rfloor}
\newcommand\sel[1]{\lceil#1\rceil}

\begin{document}
\maketitle
\begin{abstract}
We prove that the list-chromatic index and paintability index of $K_{p+1}$ is $p,$ for all odd
primes $p.$ This implies that the List Edge Coloring Conjecture holds for complete graphs
with less than 10 vertices. It also shows that there exist arbitrarily big complete graphs for
which the conjecture holds, even among the complete graphs of class 1. Our proof
combines the Quantitative Combinatorial Nullstellensatz with the Paintability Nullstellensatz
and a group action on symmetric Latin squares. It displays various ways of using different
Nullstellensätze. We also obtain a partial proof of a version of Alon and Tarsi's Conjecture
about even and odd Latin squares.
\end{abstract}


\section{Introduction}\label{sec.int}
Given a graph $G=(V,E)$ and a nonempty \emph{list} (set) $L_e$ for every edge $e\in E,$
we set \rand$"L":=\prod_{e\in E}L_e$ and say that $G$ is \emph{\(L\)-list-edge colorable} or
\emph{edge \(L\)-choosable} if it is possible to assign to each edge $e\in E$ a \emph{color}
(an element) from the list $L_e$ in such a way that any two adjacent edges of $G$ receive
different colors. We call the Cartesian product $L$ a \emph{\(k\)-list product} if
$\abs{L_e}=k$ for all $e\in E.$ If $G$ is edge \(L\)-choosable for every \(k\)-list product $L,$
we say $G$ is \emph{\(k\)-list-edge colorable} or \emph{edge \(k\)-choosable}. The
\textit{list-chromatic index} of $G,$ denoted by \rand$"\chi'_\ell"(G),$ is the smallest positive
integer $k$ such that $G$ is \(k\)-list-edge colorable.

Obviously, $\chi'_\ell(G)\geq \chi'(G),$ where \rand$"\chi'"(G)$ is the (ordinary) chromatic
index of $G,$ refereing to the special situation of equal lists, $L_e=\{1,2,\ldots, k\}$ for all
$e\in E.$ The opposite, i.e.\ that $\chi'_\ell(G)\leq \chi'(G),$ was conjectured independently
by several researchers \cite[Section\,12.20]{jeto}:

\begin{Vermut}[List Coloring Conjecture]\label{LCC}
$\chi'_\ell(G)=\chi'(G)$ for every multigraph $G.$
\end{Vermut}


The List Coloring Conjecture is a long standing open conjecture. The biggest partial success
was achieved by Galvin, who could prove it for all bipartite graphs in \cite{ga}. It also holds
asymptotically in some sense \cite{ka}. However, even for relatively small single graphs it can
be very difficult to find a proof. Problems with small complete graphs like $K_6$ may
surprise even more, since complete graphs, as complement of empty graphs, do not carry
any structure. These difficulties might indicate that the core of the problem does not lie in
the graph theoretic structure. Certainly, a complicated graph structure will not make things
easier but there could be a more primal problem contained in the List Coloring Conjecture.
This combinatorial problem may occur in its purest form in the study of complete graphs as
graphs without structure. Therefore, it seems reasonable to investigate the List Coloring
Conjecture for complete graphs first. Moreover, the study of this special case is of interest in
its own right, too. For example, it has applications in time scheduling of complete
tournaments, as described in \cite{schPAT}. The purpose of this paper is to present some
progress in this direction.

It is well known (see e.g.\ \cite{FW}) that the chromatic index of the complete graph
\rand$"K_n"$ on $n>1$ vertices is given by
\begin{equation}
\chi'(K_n)\,=\,\begin{cases}
 n-1&\text{if $n$ is even,}\\
 n&\text{if $n$ is odd.}
\end{cases}
\end{equation}
Hence, restricted to complete graphs, Conjecture\,\ref{LCC} states that the list-chromatic
index of $K_n$ should equal the quantity indicated above. For complete graphs of class 2
(odd $n$) this was proven by H\"{a}ggkvist and Janssen, who presented the following upper
bound for all $n\in\Z^+\!$ in \cite{haja} (the generalization to paintability can be found in
\cite{schPAT}):

\begin{Satz} %[H\"{a}ggkvist and Janssen, 1997]\label{HJ}
$\chi'_\ell(K_n)\leq n$ for every positive integer $n.$
\end{Satz}

This result leaves the question open for complete graphs of even order only, the complete
graphs of class 1. For even $n,$ H\"{a}ggkvist and Janssen's inequality would need to be
improved by one. To clarify the task, we state this case separately, as a special case of the
List Coloring Conjecture:

\begin{Vermut}\label{CG}
$\chi'_\ell(K_{2m})=2m-1$ for every positive integer $m.$
\end{Vermut}

Note that the H\"{a}ggkvist-Janssen Theorem can easily be deduced from
Conjecture\,\ref{CG}, because $\chi'_\ell(H)\leq\chi'_\ell(G)$ if $H\sb G,$ and $K_{2m-1}\sb
K_{2m}.$ However, previously known are only the cases $m=1,2,3$ of Conjecture\,\ref{CG}.
The case $m=1$ is trivial. The case $m=2$ follows from the fact that every \(1\)-factorable
planar graph satisfies Conjecture\,\ref{LCC}, a fact established by Ellingham and Goddyn in
\cite{elgo}. A short elementary proof of the case $m=2$ was also given by David Cariolaro
and Ko-Wei Lih in \cite{CL}. The case $m=3$ was proven by David Cariolaro et al.\ in
\cite{ccss}. The author of the present paper has tried to prove Conjecture\,\ref{CG} before
he became colleague and friend of David Cariolaro, but had already given up after many
attempts. It was then David Cariolaro who encouraged us to try it again, and we wrote the
paper \cite{ccss} together. Sadly, after his tragic early death, we cannot show him the
newest progress anymore. We dedicate the current paper to his memory.

Our main objective in this paper is to prove Conjecture\,\ref{CG} for $K_{p+1}$ ($2m=p+1$),
($2m=p+1$), for all odd primes $p,$ i.e.\ to prove the following theorem:

\begin{Satz}\label{sz.p+1}
$\chi'_\ell(K_{p+1})=p$ for every odd prime $p.$
\end{Satz}

Together with the observations and results mentioned above, this implies that the List
Coloring Conjecture (Conjecture\,\ref{LCC}) holds for complete graphs with less than 10
vertices. It also shows that there exist arbitrarily big complete graphs for which the
conjecture holds, even among the complete graphs of class 1. Moreover, we can easily
generalize Theorem\,\ref{sz.p+1} to \emph{paintability}, a concept that we introduced in
\cite{schPC} and \cite{schT}, and that later also was called \emph{on-line list coloring}. In the
concept of paintability, the lists can be modified during an interactive coloration process. We
explain this briefly for vertex colorings:

The idea is that, if only positive numbers are allowed as colors, we may try to use color $1$
at first, of course, only for vertices $v$ whose lists $L_v$ contain color $1.$ Afterwards, we
allow changes of the remaining lists $L_v\!\sm\!\{1\}$ that do not change their cardinalities,
before we extend the partial coloring with color $2.$ This extension process is then repeated
with color $3,$ color $4$ and so forth, where in between, the remaining tails of the color lists
may be altered in arbitrary, possible unfortunate ways. Surprisingly, the great majority of all
list coloring theorems in graph theory could already be generalized to paintability, see e.g.\
\cite{ca,hks,hwz,rs,schPC,schPAT,schPCN,zhu}. Our generalization is interesting for
theoretical reasons, but might find practical applications in time scheduling as well, as
discussed in \cite{schPAT} in connection with complete tournament graphs. An elegant
recursive way to define \(k\)-paintability might even improve clarity in some proofs of list
coloring theorems. Again, if one colors edges and not vertices, the smallest number $k$ for
which \(k\)-paintability is given is called \emph{index} -- the \emph{paintability index} --
denoted \rand$"\chi'_P"(G).$ We will prove the following strengthening of
Theorem\,\ref{sz.p+1}:


\begin{Satz}\label{sz.p+1P}
$\chi'_P(K_{p+1})=p$ for every odd prime $p.$
%Change
\end{Satz}

The general polynomial approach to coloring problems is explained in the next section,
Section\,\ref{sec.edp}. There, we also provide some useful corollaries of the Combinatorial
Nullstellensatz and explain how to use them. This will lead us to the consideration of a
certain ``leading coefficient'', in a certain polynomial associated to $K_{p+1}.$ This
coefficient is then reinterpreted in Section\,\ref{sec.ItC} as the number of so called
idempotent symmetric Latin squares (with some of them counted negative).
Theorem\,\ref{sz.imp} will accumulate these reinterpretations and will provide a sufficient
condition to Conjecture\,\ref{CG}. Eventually, we will show in Section\,\ref{sec.GA} that this
sufficient condition is fulfilled if $p$ is an odd prime. To achieve this, we have to count the
idempotent symmetric Latin squares. Actually, we will count only modulo $p,$ which will allow
us to ignore the nontrivial orbits under a certain group action. Hence, we will only have to
count the symmetric Latin squares that are fixed under that group action. We found this
crucial trick in \cite{dr} (see also \cite{stwa}), where Drisko used it to give a partial proof of
Alon and Tarsi's Conjecture about even and odd Latin squares. The main result of
Section\,\ref{sec.GA}, Theorem\,\ref{sz.fix}, may be seen as a partial proof of a version of
this conjecture, which is stated explicitly at the end of the paper. Theorem\,\ref{sz.fix} will
yield, in combination with Theorem\,\ref{sz.imp}, our main results, Theorem\,\ref{sz.p+1} and
Theorem\,\ref{sz.p+1P}.


%------------------------------------------------------------------------------

\section{The Polynomial Approach}\label{sec.edp}

In this section, we introduce the edge distance polynomial of graphs and some
Combinatorial Nullstellensätze (plural of Nullstellensatz, a German expression meaning Root
Theorem). We explain how they can be used to detect graph colorings.

To prove that $\chi'_\ell(K_{p+1})=p$ for odd primes $p,$ we will examine the edge distance
polynomial \rand$"P_{L(K_{p+1})}"$ of the line graph $L(K_{p+1})$ of $K_{p+1}.$ Here the
edge distance polynomial $P_{G}$ of a graph $G$ on vertices $v_1,v_2,\dotsc,v_n$ is a
polynomial in the variables $x_1,x_2,\dotsc,x_n,$ with one variable $x_i$ for each vertex
$v_i.$ It is defined as the product over all differences $x_i-x_j$ with $v_iv_j\in E(G)$ and
$i<j.$ It is also called the graph polynomial and was introduced in \cite{pe}. We may view it
as a polynomial over any integral domain \rand$"R".$ If $P_G$ is non-zero at a point
$(x_1,x_2,\dotsc,x_n)$ then the assignment $v_i\mto x_i$ is a proper vertex coloring of
$G.$ If $P_{L(G)}$ is non-zero at a point $(x_1,x_2,\dotsc,x_m)$ then the assignment
$e_i\mto x_i$ is a proper edge coloring of $G.$ If the colors $x_i$ are supposed to lie in
certain lists $L_{e_i},$ or $L_i$ for short, then the point $(x_1,x_2,\dotsc,x_m)$ just has to
be taken from the list product $L_1\times L_2\times\dotsm\times L_m.$ Here, we simple
need to assume that the sets $L_i$ lie in $R,$ or in an extension ring of $R.$ This is no
restriction, as one can easily embed the color lists (and their full union $\bigcup_iL_i$) into
any big enough ring $R.$ We might just take $R=\Z.$

To prove that $K_{p+1}=(V,E)$ is edge \(p\)-choosable if $p$ is prime, we will show that the
coefficient of the monomial $\prod_{e\in E}X_e^{p-1}$ in $P_{L(K_{p+1})}$ is non-zero. The
famous \emph{Combinatorial Nullstellensatz}\,\cite{al2} will then guarantee a non-zero in any
\(p\)-list product $L.$ This Nullstellensatz can elegantly be formulated as follows:

\begin{Satz}[Combinatorial Nullstellensatz]\label{sz.CN}
If $x_1^{d_1}x_2^{d_2}\dotsm x_n^{d_n}$ occurs as a monomial of maximal degree in a
polynomial $P=P(x_1,x_2,\dotsc,x_n)$ over a field $\F[],$ then \rand$"P"$ has a non-zero in
any domain $L:=L_1\times L_2\times\dotsb\times L_n\sb\F[]^n$ with $\abs{L_j}>d_j$ for
$j=1,2,\dotsc,n.$
\end{Satz}

In this theorem, the monomial $x^d:=x_1^{d_1}x_2^{d_2}\dotsm x_n^{d_n}$ (with given
exponents \rand$d_j\in"\N":=\{0,1,2\dotsc\}$) has maximal degree in
\rand$P=\sum_{\d\in\N^n}"P_\d" x^\d\,\in\,\R[x_1,\dotsc,x_n]$ if
\begin{equation}
\deg(P)\leq d_1+d_2+\dotsb+d_n.
\end{equation}
This condition is usually easy to verify. However, $x^d$ must occur in $P$ in the first place,
i.e.\ the coefficient $P_d$ of $x^d$ must be nonzero,
\begin{equation}
P_d\,\neq\,0.
\end{equation}
The calculation of $P_d$ is the difficult part in all known applications (except in proofs of
non-uniqueness, where one better uses \cite[Corollary 3.4 or 3.5]{schAlg}). Astonishingly,
this main hypothesis of the Combinatorial Nullstellensatz can sometimes be calculated by
another application of the Combinatorial Nullstellensatz. More precisely, the Quantitative
Combinatorial Nullstellensatz \cite{schAlg,schT} is needed here:

\begin{Satz}[Quantitative Combinatorial Nullstellensatz]\label{sz.QCN}
Let $L_1,L_2,\dotsc,L_n$ be finite nonempty subsets of a field $\F[]$ and $L:=L_1\times
L_2\times\dotsm\times L_n.$ Define $d:=(d_1,d_2,\dotsc,d_n)$ via
\rand$"d"_j:=\abs{L_j}-1\in\N.$ For every fixed polynomial
\rand\rand$"P"=\sum_{\d\in\N^n}"P_\d" x^\d\,\in\,\F[][x_1,\dotsc,x_n]$ of total degree
$\deg(P)\leq\sum_j\,d_j,$
$$
P_d\,=\,\sum_{x\in L}\,N(x)^{-1}P(x),
$$
where
 \rand$$
"N(x)"\,:=\,\prod_{j=1}^n\,\prod_{\xi\in L_j\sm\{x_j\}\!\!\!\!\!\!\!\!\!}(x_j-\xi).
$$
\end{Satz}

One easily spots the Combinatorial Nullstellensatz as corollary of Theorem\,\ref{sz.QCN}. If
$P_d\neq0,$ the sum in the Quantitative Combinatorial Nullstellensatz is nonzero, so that at
least one summand must be nonzero and $P$ cannot vanish at all points of $L.$ However,
as said, we will us this formula to calculate the ``leading coefficient'' $P_d$ first. This
calculation simplifies if we chose the domain $L$ cleverly. A sufficient simplification can
already be obtained by choosing equal lists, $L_1=L_2=\dotsb=L_n.$ This will allow us to
express $P_d$ as the number of usual edge colorings of $K_{p+1},$ but with some
colorings counted negative.

The next task is to count the edge colorings of $K_{p+1}.$ Unfortunately, the set of all edge
colorings of $K_{p+1}$ with $p$ colors is not known. Therefore, we continue by
reinterpreting colorings as certain Latin squares and, eventually, as certain permutations. To
prove that the number of these permutation (with odd ones counted negative) does not
vanish, we want to use Theorem\,\ref{sz.QCN} again, but need to simplify it further, at first.
In \cite{schAlg}, we calculated the function $N(x)$ in that formula for important domains $L.$
If all $L_j$ are finite fields, then $N(x)$ is constant and equal to $(-1)^n\!,$ by
\cite[Lemma\,1.4(iv)]{schAlg}. In particular, this yields the following very well known special
case of Theorem\,\ref{sz.QCN}:

\begin{Satz}\label{sz.qCN}
Let $\F[p]$ be the prime field with $p$ elements, $P=\sum_{\d\in\N^n}P_\d X^\d$ a
polynomial over a field extension of $\F[p]$ and $d:=(p{-}1,p{-}1,\dotsc,p{-}1).$ If
$\deg(P)\leq n(p-1),$ then
$$
P_d\,=\,(-1)^n\sum_{x\in\F[p]\n}\,P(x).
$$
\end{Satz}

With an additional double application of this simplified Quantitative Nullstellensatz, and some
other tricks, we will be able to prove that $P_d\neq0.$ After that, a single application of the
usual Combinatorial Nullstellensatz will yield our main result, Theorem\,\ref{sz.p+1}. The
disadvantage in using Theorem\,\ref{sz.qCN} is that it restricts us to primes $p$ and the
graphs $K_{p+1}.$ Therefore, we prefer to use Theorem\,\ref{sz.QCN} as long as possible
and switch to the simpler more special version Theorem\,\ref{sz.qCN} only in the last
section, where we do not see another way. Actually, we hope that the general Quantitative
Combinatorial Nullstellensatz can be used to generalize our results. In the literature, e.g.\ in
\cite{wi} and \cite{su}, one can find generalizations from prime characteristic to prime power
characteristic in results around Chevaley and Warning's Theorem and Olson's Theorem.
The generalized polynomials in \cite{schPol} can also be used to achieve such
generalizations. However, the situation in the present paper seems to be complicated. We
could not yet generalize our results, not even to prime powers $p^\alpha$ and the graphs
$K_{p^\alpha+1}.$

In \cite{schPCN}, we also provided a paintability version of the Combinatorial Nullstellensatz.
If we use this version in the very last step of our calculation, instead of the usual
Combinatorial Nullstellensatz, we obtain Theorem\,\ref{sz.p+1P} instead of the weaker
Theorem\,\ref{sz.p+1}. The alternative usage of the Paintability Nullstellensatz does not
provide any additional difficulty. The formulation of that Theorem only requires the
generalization of the painting concept from graphs to polynomials, as described in
\cite{schPCN}. It can then be stated as follows, where, for simplicity, $k$ is just a constant
here:

\begin{Satz}[Paintability Nullstellensatz]\label{sz.PN}
If $x_1^{d_1}x_2^{d_2}\dotsm x_n^{d_n}$ occurs as a monomial of maximal degree in a
polynomial $P(x_1,x_2,\dotsc,x_n),$ then $P$ is \(k\)-paintable for every $k>\max_jd_j.$
\end{Satz}

%------------------------------------------------------------------------------

\section{Interpreting the Coefficient}\label{sec.ItC}

At the end of this section, we provide with Theorem\,\ref{sz.imp} a result that in combination
with Theorem\,\ref{sz.fix} proves our main theorems, Theorem\,\ref{sz.p+1P} and
Theorem\,\ref{sz.p+1}. In the whole section, \rand$"p"$ is only required to be an odd integer
greater then $1.$ Let
 \rand\begin{equation}
"\bar I_p"\,:=\,\{\E,0,1,\dotsc,p-1\}
\end{equation}
be the set of vertices of $K_{p+1},$ where \rand$"\E"$ is just a symbol. The edges of
$K_{p+1}$ can be written as
 \rand\begin{equation}
"ij"\,=\,ji:=\,\{i,j\},\ \text{with $i,j\in\bar I_p$ and $i\neq j.$}
\end{equation}
These edges are also the vertices of the line graph
 \rand\rand\begin{equation}
L(K_{p+1})=:("V","E").
\end{equation}
Hence, the variables of the edge distance polynomial
 \rand\begin{equation}
"P"\,:=\,P_{L(K_{p+1})}\,\in\,\Z[x_e\!\mit\!e\in V]
\end{equation}
can be written as
 \rand\begin{equation}
"x_{ij}"\,=\,x_{ji},\ \text{with $ij=ji\in V$\ (\,i.e.\ with $i,j\in\bar I_p,$ $i\neq j$).}
\end{equation}
Since
\begin{equation}
\deg(P)\,=\,\abs{V}(p-1),
\end{equation}
we only have to show that the coefficient $P_d$ of the monomial
\begin{equation}
x^d\,=\,\prod_{e\in V}x_e^{p-1}\qquad\bigl(\,d:=(p-1,p-1,\dotsc,p-1)\,\bigr)
\end{equation}
inside $P$ is non-zero, as explained in Section\,\ref{sec.edp}.

To calculate $P_d,$ we use Theorem\,\ref{sz.QCN} with $\abs{V}=\tbinom{p+1}{2}$ identical
lists $L_v$ of cardinality $p.$ We write \rand$"L_0"$ for such a list, so that the appropriate
corresponding domain of $P$ is
 \rand\begin{equation}
"L"\,:=\,L_0^V.
%L\,:=\,\{0,1,\dotsc,p-1\}^V.
\end{equation}
By the definition of $P$\!, a point $x=(x_e)_{e\in V}\in L$ is a non-zero of $P$ if and only if
$e\lmto x_e$ a proper edge coloring of $K_{p+1}.$ Therefore, we may restrict the
summation range in the Quantitative Combinatorial Nullstellensatz to the set
\rand$"\cC_p"\sb L$ of these colorings. As in a proper edge coloring $x\in\cC_p$ every color
occurs $(p+1)/2$ many times, we can calculate $N(x)$ in Theorem\,\ref{sz.QCN} without
further information about $x\in\cC_p.$ Up to the sign, the function $N(x)$ in
Theorem\,\ref{sz.QCN}, as function on $\cC_p,$ is equal to the $(p+1)^{\text{th}}$ power of
 \rand\begin{equation}
"N_0"\,:=\,\prod_{\atop{\zeta,\xi\in L_0}{\zeta\,>\,\xi}}(\zeta-\xi) \,\neq\,0,
\end{equation}
where $>$ is any strict linear order on $L_0.$ With that
\begin{equation}
P_d\,=\,\sum_{x\in L}\,N(x)^{-1}P(x)\,=\,\pm N_0^{-(p+1)}\sum_{x\in\cC_p}\,P(x).
\end{equation}

Now, for every fixed $x\in\cC_p,$
\begin{equation}\label{eq.PN}
P(x)\,=\,\pm N_0^{p+1}.
\end{equation}
This is easy to see. Indeed, the line graph of $K_{p+1}$ is the edge disjoint union of $p+1$
many copies of $K_p,$ one copy for every vertex $i\in\bar I_p$ of $K_{p+1}.$ Hence, $P$
factors accordingly,
\begin{equation}
P\,=\,\pm\prod_{i\in\bar I_p}P_i
\end{equation}
where \rand$"P_i"$ is the edge distance polynomial of the complete graph on the vertex set
$$\{i\E,i0,i1,\dotsc,\cancel{ii},\dotsc,i(p-1)\}\sb V,$$
\begin{equation}
P_i\,:=\,P_{K_p}(x_{i\E},x_{i0},x_{i1},\dotsc,\cancel{x_{ii}},\dotsc,x_{i(p-1)}).
\end{equation}
Here, for every fixed $x\in\cC_p,$
\begin{equation}
P_i(x_{i\E},x_{i0},x_{i1},\dotsc,\cancel{x_{ii}},\dotsc,x_{i(p-1)})\,=\,\pm N_0,
\end{equation}
which explains Equation\,\eqref{eq.PN}.

Our findings also gives rise to the definitions
 \rand\begin{equation}
"\sgn_i"(x)\,:=\,N_0^{-1}P_i(x_{i\E},x_{i0},x_{i1},\dotsc,\cancel{x_{ii}},\dotsc,x_{i(p-1)})\,\in\,\{+1,-1\},
\end{equation}
for $i=\E,0,1,\dotsc,p-1,$ and
 \rand\begin{equation}
"\sgn"(x)\,:=\,\prod_{i\in\bar I_p}\sgn_i(x).
\end{equation}
Here the functions $\sgn_i\DP\cC_p\lto\{+1,-1\}$ also can be expressed independently from
$P$\!, up to a neglectable constant factor of $\pm1.$ This is not difficult, but, to simplify
notation, we assume additionally that, from here on,
 \rand\rand\begin{equation}
"L_0"\,:=\,"I_p"\,:=\,\{0,1,\dotsc,p-1\}\,\sb\,\Z.
\end{equation}
Then
\begin{equation}\label{eq.sgni}
\sgn_i(x)\,=\,\pm\sgn
\begin{pmatrix}
 0&1&2&\dotsc&i&i+1&\dotsc&p-1\\
 x_{i\E}&x_{i0}&x_{i1}&\dotsc&x_{i(i-1)}&x_{i(i+1)}&\dotsc&x_{i(p-1)}
\end{pmatrix},
\end{equation}
where the sign $\pm$ before the function $\sgn$ does not depend on $x.$ The sign $\pm$
is constant, it is either $+$ for all $x\in\cC_p$ or $-$ for all $x\in\cC_p.$ Indeed, both sides
of this equation have absolute value $1,$ depend only on the $p$ (different) values of
$x_{i\E},$ $x_{i0},$ $x_{i1},\dotsc,\cancel{x_{ii}},\dotsc,x_{i(p-1)}$ and react in the same
way if we permute these values. Hence, if we choose the prefixed sign in such a way that
the equation holds in one point $x,$ then it holds for all $x\in\cC_p.$ Now, with our new
definitions, we can write
\begin{equation}
P_d\,=\,\pm\sum_{x\in\cC_p}\sgn(x).
\end{equation}
Our calculations show that, in order to guarantee edge \(p\)-choosability (and edge
\(p\)-paint"|ability) of $K_{p+1},$ we only have to verify that
\begin{equation}
\sum_{x\in\cC_p}\sgn(x)\,\neq\,0.
\end{equation}
In fact, this insight can even be formulated for arbitrary \(p\)-regular graphs in the place of
$K_{p+1}.$ This is a straight forward generalization. It was first observed using another
approach in \cite{al}. We include this calculation here since it explains the central position of
the function $\sgn(x)$ in this paper. (Remarkably, the $\sgn(x)$ takes the same value for all
edge colorings $x$ if the regular graph is additionally planar, \cite{elgo},
\cite[Theorem\,3.12]{schPAT}.)

Next, we write the proper edge colorings $x\in\cC_p$ of $K_{p+1}$ as \emph{symmetric
Latin squares} \rand$"M"=M(x),$ i.e.\ as symmetric \((p+1)\times(p+1)\)-matrices in which
every row and every column contains every symbol of $\bar I_p$ exactly once. We define
$M(x)=(M_{i,j})\in\bar I_p^{\bar I_p\times\bar I_p}$ via
\begin{equation}
M_{i,j}\,:=\,\begin{cases}
\,x_{ij}&\text{if $i\neq j,$}\\
\,\E&\text{if $i=j,$}
\end{cases}
\end{equation}
where we view $\E$ as first index, corresponding to the first row and the first column of
$M,$ $0$ as second index, etc. Obviously, $M$ is a \emph{unipotent} symmetric Latin
square, i.e.\ it has the symbol $\E$ in all diagonal cells. If we write \rand$"\USLS_p"$ for the
set of these Latin squares in $\bar I_p^{\bar I_p\times\bar I_p}\!,$ then the map
\begin{equation}
\cC_p\,\lto\,\USLS_p,\ x\lmto M(x)
\end{equation}
is bijective. The \emph{row sign} $\sgn(M)$ of $M=(M_{i,j})\in\USLS_p$ is the product of the
signs of its rows \rand$"M_{i,*}"$ as permutations of the symbols $\E,0,1,\dotsc,p-1$ in their
usual order. Hence, $\sgn(M)$ is the product over the $p+1$ many signs
\begin{equation}
\sgn(M_{i,*}):=\,\,\sgn
\begin{pmatrix}
\E&0&1&\dotsc&i-1&i&i+1&\dotsc&p-1\\
 x_{i\E}&x_{i0}&x_{i1}&\dotsc&x_{i(i-1)}&\ \ \,\E\,\ \ &x_{i(i+1)}&\dotsc&x_{i(p-1)}
\end{pmatrix}
\end{equation}
with $i=\E,0,1,\dotsc,p-1.$ Here we see that
\begin{equation}
\begin{split}
\sgn(M_{i,*})\,=&\,\,\pm\sgn
\begin{pmatrix}
 \,\,\E\,&0&1&\dotsc&i-1&i&i+1&\dotsc&p-1\\
 \,\,\E\,&x_{i\E}&x_{i0}&\dotsc&x_{i(i-2)}&x_{i(i-1)}&x_{i(i+1)}&\dotsc&x_{i(p-1)}
\end{pmatrix}\\[2pt]
 \,=&\,\,\pm\sgn
\begin{pmatrix}
 0&1&\dotsc&i-1&i&i+1&\dotsc&p-1\\
 x_{i\E}&x_{i0}&\dotsc&x_{i(i-2)}&x_{i(i-1)}&x_{i(i+1)}&\dotsc&x_{i(p-1)}
\end{pmatrix}\\[2pt]
\,\eqby{\eqref{eq.sgni}}&\,\,\pm\sgn_i(x),
\end{split}
\end{equation}
where, again, $\pm$ is always $+$ or always $-,$ independently of $x.$ Hence, our bijection
preserves the sign, up to a neglectable constant factor of $\pm1,$
\begin{equation}
\sgn(M(x))\,=\,\pm\sgn(x),
\end{equation}
and
\begin{equation}
P_d\,=\,\pm\!\!\sum_{M\in\USLS_p}\sgn(M).
\end{equation}

We even go a bit further. We call a Latin square $M=(M_{i,j})$ over $\bar I_p$
\emph{reduced} if its first row is
\begin{equation}
M_{\E,*}\,=\,[\E,0,1,\dotsc,p-1].
\end{equation}
We write \rand$"\RUSLS_p"$ for the set of all reduced unipotent symmetric Latin squares
over $\bar I_p.$ We always can bring an $M\in\USLS_p$ into reduced form by applying an
appropriate permutation of the $p$ elements in $ I_p$ to all entries of $M.$ The set
$\USLS_p$ is partitioned into the orbits under this group action, and $\RUSLS_p$ is a
transversal of this partition. Moreover, the described group action preserves the sign.
Indeed, if we apply any permutation to all entries of an $M\in\USLS_p,$ the signs of the
rows will either all change or all remain unchanged, so that the product over all even many
row signs will not change. This yields
\begin{equation}
\sum_{M\in\USLS_p}\sgn(M)\,=\ p!\!\!\!\!\sum_{M\in\RUSLS_p}\!\!\!\sgn(M).
\end{equation}

To study the reduced unipotent symmetric Latin Squares over $\bar I_p,$ we will use a
bijection $\varphi$ from the set $\RUSLS_p$ of these Latin squares into the set
\rand$"\ISLS_p"$ of \emph{idempotent} symmetric Latin squares over
$I_p=\{0,1,\dotsc,p-1\},$ which are the symmetric Latin squares $M=(M_{i,j})\in I_p^{
I_p\times I_p}$ with
\begin{equation}
M_{i,i}=i\quad\text{for all $i\in I_p.$}
\end{equation}
Our bijection \rand$"\varphi"$ is given by
\begin{equation}
\begin{bmatrix}
\E\,\,&0&1&2&\ \ \cdots&p-1\\[6pt]
0\,\,&\E&*&*&\ \ \cdots&*\\
1\,\,&*&\E&*&\ \ \cdots&*\\
2\,\,&*&*&\E&\ \ \cdots&*\\
\vdots\,\,&\vdots&\vdots&\vdots&&\vdots\\
p-1\,\,&*&*&*&\ \ \cdots&\E
\end{bmatrix}
\ \eqby[\lmto]{\varphi}\
\begin{bmatrix}
0&*&*&\ \ \cdots&*\\
*&1&*&\ \ \cdots&*\\
*&*&2&\ \ \cdots&*\\
\vdots&\vdots&\vdots&&\vdots\\
*&*&*&\ \ \cdots&p-1
\end{bmatrix},
\end{equation}
where the first row and the first column are deleted, but their elements take the place of the
old diagonal elements $\E.$ The off-diagonal entries behind the stars $*$ remain
unchanged. If we define the sign of a Latin square over $I_p$ in the same way as for Latin
squares over $\bar I_p,$ we see that, for $i\in I_p,$
\begin{equation}
\begin{split}
\sgn(M_{i,*})\,\,=&\quad\ \,\sgn
\begin{pmatrix}
\E&0&1&\dotsc&i-1&i&i+1&\dotsc&p-1\\
x_{i\E}&x_{i0}&x_{i1}&\dotsc&x_{i(i-1)}&\ \ \,\E\,\ \ &x_{i(i+1)}&\dotsc&x_{i(p-1)}
\end{pmatrix}\\[2pt]
 \,=&\,\,\,-\sgn
\begin{pmatrix}
\,\,\E\,&0&1&\dotsc&i-1&i&i+1&\dotsc&p-1\\
\,\,\E\,&x_{i0}&x_{i1}&\dotsc&x_{i(i-1)}&\ \,x_{i\E}\,\ &x_{i(i+1)}&\dotsc&x_{i(p-1)}
\end{pmatrix}\\[2pt]
 \,=&\,\,\,-\sgn
\begin{pmatrix}
0&1&\dotsc&i-1&i&i+1&\dotsc&p-1\\
x_{i0}&x_{i1}&\dotsc&x_{i(i-1)}&\ \,x_{i\E}\,\ &x_{i(i+1)}&\dotsc&x_{i(p-1)}
\end{pmatrix}\\[2pt]
\,=&\,\,\,-\sgn\bigl(\varphi(M)_{i,*}\bigr).
\end{split}
\end{equation}
Therefore, and because the sign of the first row of a reduced matrix is $1,$
\begin{equation}
\sgn(M)\,=\,-\sgn(\varphi(M)).
\end{equation}

Summarizing, all this yields
\begin{equation}
P_d\,=\,\pm p!\!\!\sum_{M\in\ISLS_p}\!\!\sgn(M).
\end{equation}
Therefore, in order to prove Conjecture\,\ref{CG}, it remains to show that
\begin{equation}
\sum_{M\in\ISLS_p}\!\!\sgn(M)\,\neq\,0.
\end{equation}
We will do this for odd primes $p$ in the next section, in Theorem\,\ref{sz.fix}, by showing
that this sum is not dividable by $p.$ This will entail Theorem\,\ref{sz.p+1} and
Theorem\,\ref{sz.p+1P}. We conclude this section by summarizing its main content:

\begin{Satz}\label{sz.imp}
For every odd $p>1,$
$$
\sum_{M\in\ISLS_p}\!\!\sgn(M)\,\neq\,0
\quad\lTo\quad\chi'_P(K_{p+1})\,=\chi'_\ell(K_{p+1})\,=\,p.
$$
\end{Satz}

To be very precise, this theorem and its underlying definitions do not really depend on any
structure on the set $L_0= I_p$ of symbols, one can replace it with any other set of $p$
symbols.


%------------------------------------------------------------------------------

\section{A group action on Latin squares}\label{sec.GA}

At the end of this section, we provide with Theorem\,\ref{sz.fix} a result about symmetric
Latin squares that, in combination with Theorem\,\ref{sz.imp}, proves our main theorems,
Theorem\,\ref{sz.p+1P} and Theorem\,\ref{sz.p+1}. To accomplish this task, we investigate
some group action and apply Theorem\,\ref{sz.qCN} twice. From here on \rand$"p"$ always
denotes a fixed odd prime. We examine the \(p{\times} p\)-matrices
\rand$"M"\in\Z_p^{\Z_p\times\Z_p}$\!\!, where
 \rand\begin{equation}
"\Z_p"\,=\,\{0,1,\dotsc,p-1\}\,:=\,\Z/p\Z.
\end{equation}
Here, in contrast to the situation in the last section, it will become important that the set
$\Z_p$ of symbols caries the algebraic structure of a field, as we will see later. The
symmetric group \rand$"S_{\Z_p}"$ on the set $\Z_p$ acts on the set
$\Z_p^{\Z_p\times\Z_p}$ of all matrices $M$ by simultaneous permutation of rows, columns
and symbols. More precisely, for $g\in S_{\Z_p},$ the image
\rand\rand$"g(M)"="M^g"=(M_{i,j}^g)$ of $M=(M_{i,j})$ under $g$ is the matrix with the
entries
\begin{equation}
M_{i,j}^g\,:=\,g\bigl(M_{g^{-1}(i),\,g^{-1}(j)}\bigr).
\end{equation}
If $g$ is the cyclic permutation $(0,1,\dotsc,p-1)$ then
\begin{equation}
g(M)\,=\,
\begin{bmatrix}
M_{p-1,p-1}+1\,&M_{p-1,0}+1&M_{p-1,1}+1&\ \ \cdots\ \ &M_{p-1,p-2}+1\\[5pt]
M_{0,p-1}+1\,&M_{0,0}+1&M_{0,1}+1&\ \ \cdots\ \ &M_{0,p-2}+1\\
M_{1,p-1}+1\,&M_{1,0}+1&M_{1,1}+1&\ \ \cdots\ \ &M_{1,p-2}+1\\
\vdots\,&\vdots&\vdots&&\vdots\\
M_{p-2,p-1}+1\,&M_{p-2,0}+1&M_{p-2,1}+1&\ \ \cdots\ \ &M_{p-2,p-2}+1
\end{bmatrix}.
\end{equation}
Apparently, a matrix $M$ is fixed under $(0,1,\dotsc,p-1),$ and under the subgroup
 \rand\begin{equation}
"G"\,:=\,\spn{(0,1,\dotsc,p-1)}\,\leq\,S_{\Z_p}
\end{equation}
generated by $(0,1,\dotsc,p-1),$ if and only if it is diagonally cyclic (see \cite{wa}), i.e.\ of the
form \Rand{\(M(x_0,\dotsc)\)}
\begin{equation}
M(x_0,x_1,\dotsc,x_{p-1})\,:=\,
\begin{bmatrix}
x_0&x_1&x_2&\ \ \cdots\ \ &x_{p-1}\\
x_{p-1}+1&x_0+1&x_1+1&\ \ \cdots\ \ &x_{p-2}+1\\
x_{p-2}+2&x_{p-1}+2&x_0+2&\ \ \cdots\ \ &x_{p-3}+2\\
%x_{p-3}+3&x_{p-2}+3&x_{p-1}+3&x_0+3&\ \ \cdots\ \ &x_{p-4}+3\\
%x_{p-4}+4&x_{p-3}+4&x_{p-2}+4&x_{p-1}+4&x_0+4&\ \ \cdots\ \ &x_{p-5}+4\\
\vdots&\vdots&\vdots&&\vdots\\
x_1+p-1&x_2+p-1&x_3+p-1&\ \ \cdots\ \ &x_0+p-1
\end{bmatrix}.\!
\end{equation}
This even holds for non-prime $p.$

Obviously, $M(x_0,x_1,\dotsc,x_{p-1})$ is symmetric if and only if
\begin{equation}
x_{p-i}\,=\,x_i-i\quad\text{for $i=1,2,\dotsc,p-1.$}
\end{equation}
In this system of equations, the first equation and the last equation are the same, and also
the second and the second to the last, etc. Hence, with the abbreviation
 \rand\begin{equation}
"\check p"\,:=\,(p-1)/2,
\end{equation}
we can rewrite the requirement for symmetry as
\begin{equation}
x_{p-i}\,=\,x_i-i\quad\text{for $i=1,2,\dotsc,\check p.$}
\end{equation}
Every row of $M(x_0,x_1,\dotsc,x_{p-1})$ is a permutation of the sequence
${0,1,\dotsc,p-1}$ if and only if the sequence $x_0,x_1,\dotsc,x_{p-1}$ is a permutation of
the sequence $0,1,\dotsc,p-1.$ Hence, if $M(x_0,x_1,\dotsc,x_{p-1})$ is additionally
symmetric, then its columns are also permutations of the sequence $0,1,\dotsc,p-1,$ i.e.\
$M(x_0,x_1,\dotsc,x_{p-1})$ is a Latin square. We write \rand$"J_p"$ for the set of all tuples
$(x_0,x_1,\dotsc,x_{p-1})$ over $\Z_p$ with the corresponding two necessary and sufficient
properties
\begin{enumerate}[\quad(a)]
  \item $x_i\neq x_j$ for $\,i\neq j,$
  \item $x_{p-i}=x_i-i$ for $\,i=1,2,\dotsc,\check p.$
\end{enumerate}\vsp
Obviously, the set $\ISLS_p$ of idempotent symmetric Latin squares $M$ over $\Z_p$
($M_{i,i}=i$ for all $i\in\Z_p$) is invariant under the action of $G$ and can be decomposed
into the different orbits under the group action of $G.$ As $\abs{G}=p,$ these orbits either
have length $p$ or length $1.$ The orbits of length $1$ are basically given by the set of
fixpoints \rand$"\Fix_G"(\ISLS_p)$ in $\ISLS_p.$ We have seen that
\begin{equation}
\Fix_G(\ISLS_p)\,=\,\bigl\{M(0,x_1,\dotsc,x_{p-1})\mit
(0,x_1,\dotsc,x_{p-1})\in J_p\bigr\},
\end{equation}
where $x_0$ is replaced by $0$ to guarantee idempotence.

Next, we examine the row sign \rand$"\sgn(M)"$ of Latin squares $M,$ i.e.\ the product of
the signs of its rows as permutations of the symbols in their usual order. This sign is
invariant under the action of $G$ (even under the action of $S_{\Z_p}$), which is easy to
check. Therefore, all elements in any given orbit of $G$ have the same sign. Since the
non-trivial orbits have length $p,$ this yields
\begin{equation}\label{eq.mod}
\sum_{M\in\ISLS_p}\sgn(M)\,\,\equiv\sum_{M\in\Fix_G(\ISLS_p)}\!\!\!\!\sgn(M)\pmod{p}.
\end{equation}
If the Latin square $M$ is of the form $M(0,x_1,x_2,\dotsc,x_{p-1}),$ then all its rows have
the same sign. That is because the $(i+1)^{\text{th}}$ row can be obtained from the
$i^{\text{th}}$ row by, first, applying the cyclic permutation $(0,1,\dotsc,p-1)$ to each
element in the $i^{\text{th}}$ row and, second, permuting the positions of these $p$
modified entries cyclically. One does not even need to know that the cyclic permutation
$(0,1,\dotsc,p-1)$ is even to see that this transformation does not change the sign. All rows
have the same sign as the first row (see also \cite[Theorem\,12]{wa}). Since $p$ is odd, it
follows that
\begin{equation}
\sgn(M(0,x_1,\dotsc,x_{p-1}))\,\,=\,\,\sgn
\begin{pmatrix}
 0&1&\dotsc&p-1\\
 0&x_1&\dotsc&x_{p-1}
\end{pmatrix}\,\,=\,\,\sgn
\begin{pmatrix}
 1&\dotsc&p-1\\
 x_1&\dotsc&x_{p-1}
\end{pmatrix}.
\end{equation}
Hence,
\begin{equation}\label{eq.Lx}
\sum_{M\in\Fix_G(\ISLS_p)}\!\!\!\!\sgn(M)\,=
\sum_{(0,x_1,\dotsc,x_{p-1})\in J_p}\!\!\!\!\sgn
\begin{pmatrix}
 1&2&\dotsc&p-1\\
 x_1&x_2&\dotsc&x_{p-1}
\end{pmatrix}.
\end{equation}
Now, we also can prove the following lemma:
\begin{Lemma}\label{lem.isl}
$$
p\ \ \text{does not divide}\sum_{(0,x_1,\dotsc,x_{p-1})\in J_p}\!\!\!\!\sgn
\begin{pmatrix}
 1&2&\dotsc&p-1\\
 x_1&x_2&\dotsc&x_{p-1}
\end{pmatrix}.
$$
\end{Lemma}

\begin{Beweis}
For \randd$"a"\in\Z_p$ and \randd$"s,t"\in\Z^+$\!, we set
 \rand\begin{equation}
"A"_a(x_1,\dots,x_t\,;\,y_1,\dots,y_t) \,:=\,\prod_{1\leq i<j\leq t}(y_j-x_i-a), \quad A\,:=\,A_0,
\end{equation}
 \rand\begin{equation}
"B"(x_1,\dots,x_t\,;\,y_1,\dots,y_t)
\,:=\,%(-1)^t
A(x_1,\dots,x_t\,;\,y_1,\dots,y_t)A(y_1,\dots,y_t\,;\,x_1,\dots,x_t),
\end{equation}

 \rand\begin{equation}
"C"_a(x_1,\dots,x_s)\,:=\,A_a(x_1,\dots,x_s\,;\,x_1,\dots,x_s), \quad C\,:=\,C_0\,\
\end{equation}
and
 \rand\begin{equation}
"D"_a(x_1,\dots,x_t\,;\,y_1,\dotsc,y_t)
\,:=\,C_a(x_1,\dots,x_t)B(x_1,\dots,x_t\,;\,y_1,\dots,y_t)C_{-a}(y_1,\dots,y_t).
\end{equation}
It is easy to see that, with $D:=D_0,$
\begin{equation}\label{eq.D1}
D(x_1,\dots,x_t\,;\,y_1,\dotsc,y_t)\prod_{i=1}^t(y_i-x_i)
\,=\,\pm C(x_1,\dots,x_t\,,\,y_1,\dotsc,y_t),
\end{equation}
where the polynomial on the right side is the \(C\)-polynomial in $s=2t$ variables (while the
\(C\)-polynomials inside $D$ on the left side have $s=t$ many variables). We further have
that
\begin{equation}
B(x_1,\dots,x_t\,;\,x_1,\dotsc,x_t)\,=\,C^2(x_1,\dots,x_t)\,\
\end{equation}
and
\begin{equation}\label{eq.D2}
D_a(x_1,\dots,x_t\,;\,x_1,\dotsc,x_t)
\,=\,C^2(x_1,\dots,x_t)C_a(x_1,\dots,x_t)C_{-a}(x_1,\dots,x_t).
\end{equation}

With these polynomials, we can go back to the sign of the permutation in the lemma. If $m$
denotes its number of inversions, so that $(-1)^m$ is its sign, then
\begin{equation}\label{eq.sgnC}
\sgn\begin{pmatrix}
 1&2&\dotsc&p-1\\
 x_1&x_2&\dotsc&x_{p-1}
\end{pmatrix}
\,=\,(-1)^m\,=\,\dfrac{C(x_1,x_2,\dotsc,x_{p-1})}{C(1,2,\dotsc,p-1)}.
\end{equation}
As $C(1,2,\dotsc,p-1)\neq0$ in $\Z_p,$ this leaves us with the calculation of the sum
\begin{equation}
\sum_{(0,x_1,\dotsc,x_{p-1})\in J_p}\!\!\!\!\!\!\!\!C(x_1,x_2,\dotsc,x_{p-1}).
\end{equation}
However, if $(0,x_1,\dotsc,x_{p-1})\in J_p$ then, by Equation\,\eqref{eq.D1} and Property
\((a)\) and \((b)\) of $J_p,$
\begin{equation}
\begin{split}
C(x_1,x_2,\dotsc,x_{p-1})
\,&=\,\pm\tfrac{1}{(p-1)!}
  C(x_1,x_2\dotsc,x_{\check p}\,,\,x_{p-1},x_{p-2},\dotsc,x_{\check p+1})
  \prod_{i=1}^{p-1}x_i\\
\,&=\,\pm\tfrac{1}{(p-1)!}
  C(x_1,x_2\dotsc,x_{\check p}\,,\,x_1-1,x_2-2,\dotsc,x_{\check p}-\check p)
  \prod_{i=1}^{\check p}x_i(x_i-i)\\
\,&=\,\pm\tfrac{\check p!}{(p-1)!}D(x_1,x_2\dotsc,x_{\check p}
  \,;\,x_1-1,x_2-2,\dotsc,x_{\check p}-\check p) \prod_{i=1}^{\check p}x_i(x_i-i)\\
\,&=\,\pm\tfrac{\check p!}{(p-1)!}\widehat D(x_1,x_2\dotsc,x_{\check p}),
\end{split}
\end{equation}
where
 \rand\begin{equation}
"\widehat D"(x_1,\dotsc,x_{\check p}) \,:=\,D(x_1,x_2\dotsc,x_{\check
p}\,;\,x_1-1,x_2-2,\dotsc,x_{\check p}-\check p)\prod_{i=1}^{\check p}x_i(x_i-i).
\end{equation}
Now, $\widehat D(x_1,\dotsc,x_{\check p})$ is non-zero at a point $(x_1,\dotsc,x_{\check
p})$ of the domain
 \rand\begin{equation}
"L"\,:=\,\Z_p^{\check p}
\end{equation}
only if $(0,x_1,x_2\dotsc,x_{\check p}\,,\,x_{\check p}-\check p,\dotsc,x_2-2,x_1-1)\in J_p.$
This follows from the definition of $D$ and from the insight that the additional factor
$\prod_{i=1}^{\check p}x_i(x_i-i)$ guarantees that all $x_i,$ all $x_{p-i}:=x_i-i$ and all
differences $x_{p-i}-x_i=i$ are non-zero for $i=1,2,\dotsc,\check p.$ It follows that
\begin{equation}\label{eq.dH}
\sum_{(0,x_1,\dotsc,x_{p-1})\in J_p}\!\!\!\!\!\!\!\!C(x_1,x_2,\dotsc,x_{p-1})
\,=\,\pm\tfrac{\check p!}{(p-1)!}\!\!\!\sum_{(x_1,x_2,\dotsc,x_{\check p})\in L}\!\!\!\!\!
 \widehat D(x_1,\dotsc,x_{\check p})\,=\,\pm\tfrac{\check p!}{(p-1)!}\widehat D_d,
\end{equation}
where $\widehat D_d$ denotes the coefficient of
 $x^d=x_1^{p-1}x_2^{p-1}\dotsm x_{\check p}^{p-1}$ in
$\widehat D(x_1,\dotsc,x_{\check p}).$ Here, for the last equality in that line, we actually had
to know that $p$ is prime to be able to use Theorem\,\ref{sz.qCN}. To calculate $\widehat
D_d,$ as required, we change the polynomial $\widehat D$ slightly, but without changing its
homogenous component of maximal degree. We set
 \rand\begin{equation}
"\widetilde D"(x_1,\dotsc,x_{\check p})
\,:=\,D_1(x_1,x_2\dotsc,x_{\check p}\,;\,x_1-0,x_2-0,\dotsc,x_{\check p}-0)
 \prod_{i=1}^{\check p}x_i(x_i-1).
\end{equation}
With that, again by Theorem\,\ref{sz.qCN},
\begin{equation}\label{eq.dT}
\widehat D_d\,=\,\widetilde D_d\,=\,\pm\!\!\!\!\!\sum_{(x_1,x_2,\dotsc,x_{\check p})\in L}\!\!\!\!\!
 \widetilde D(x_1,\dotsc,x_{\check p}),
\end{equation}
and this sum can be calculated easily. Using Equation\,\eqref{eq.D2}, we see that
\begin{equation}
\widetilde D(x_1,\dotsc,x_{\check p})
\,=\,C^2(x_1,\dots,x_{\check p})C_1(x_1,\dots,x_{\check p})C_{-1}(x_1,\dots,x_{\check p})\prod_{i=1}^{\check p}x_i(x_i-1)
\end{equation}
is non-zero in $L$ only if all $x_i$ are different from $0$ and from each other by more than
$1.$ This leaves only one possibility open for the set of the $\check p$ many $x_i.$
Necessarily, if $\widetilde D(x_1,\dotsc,x_{\check p})\neq0,$
\begin{equation}
\{x_1,x_2,\dotsc,x_{\check p}\}\,=\,\{2,4,6,\dotsc,p-1\}.
\end{equation}
Thus, we have $\check p!$ many ways to choose the $x_i.$ However, if we permute the
$x_i$ in $\widetilde D(x_1,\dotsc,x_{\check p})$ then the value of $\widetilde
D(x_1,\dotsc,x_{\check p})$ does not change, because the factor
$C^2(x_1,\dotsc,x_{\check p})$ does not change, and the factor
\begin{equation}
C_1(x_1,\dots,x_{\check p})C_{-1}(x_1,\dots,x_{\check p})
\,=\,\prod_{1\leq i<j\leq \check p}((x_j-x_i)^2-1)
\end{equation}
does not change either. Therefore,
\begin{equation}\label{eq.SdT}
\sum_{(x_1,x_2,\dotsc,x_{\check p})\in L}\!\!\!\!\!\widetilde D(x_1,\dotsc,x_{\check p})
\,=\,\check p!\,\widetilde D(2,4,\dotsc,p-1)
\,\neq\,0\,\in\,\Z_p.
\end{equation}
This concludes our calculation. We only have to check our main steps \eqref{eq.sgnC},
\eqref{eq.dH}, \eqref{eq.dT} and \eqref{eq.SdT} to confirm that the lemma holds.
\end{Beweis}

Lemma\,\ref{lem.isl} together with Equation\,\eqref{eq.Lx} and Congruence\,\eqref{eq.mod}
yields the following theorem:

\begin{Satz}\label{sz.fix}
For every odd prime $p,$
$$
p\ \ \text{does not divide}\sum_{M\in\ISLS_p}\!\!\sgn(M).
$$
\end{Satz}

This theorem about the row signs of idempotent symmetric Latin squares shows that the
sum $\sum_{M\in\ISLS_p}\sgn(M)$ is nonvanishing for odd primes $p.$ To encourage
further research, we make the following conjecture:

\begin{Vermut}\label{con.fix}
For every odd number $p\in\N,$
$$
\sum_{M\in\ISLS_p}\!\!\sgn(M)\,\neq\,0.
$$
\end{Vermut}

Obviously, the restriction to odd numbers $p$ in Conjecture\,\ref{con.fix} is necessary. The
set $\ISLS_p$ is just empty for even $p,$ because idempotence and symmetry together
imply that every symbol occurs odd many times in a matrix $M,$ so that there also must be
odd many rows and columns if $M$ shall be a Latin square.

\bigskip
\noindent\textbf{Acknowledgement:} Thanks to Detlef Schauz for some proof-reading.

%-------------------------------------------------------------------------------

\begin{thebibliography}{CCSS}
\bibitem[Al]{al}
  N.\,Alon: \textit{Restricted Colorings of Graphs.} 
  In: Surveys in combinatorics, 1993.
  London Math.\ Soc.\ Lecture Notes Ser.\ 187, 
  Cambridge Univ.\ Press, Cambridge 1993, 1--33.
\bibitem[Al2]{al2}
  N.\,Alon: \textit{Combinatorial Nullstellensatz.} 
  Combin.\ Probab.\ Comput.\ 8, No.\ 1--2 (1999), 7--29.
\bibitem[CCSS]{ccss}
  D.\,Cariolaro, G.\,Cariolaro, U.\,Schauz, X.\,Sun: 
  \textit{The List-Chromatic Index of $K_6$.} Discrete Mathematics 322 (2014), 15--18.
\bibitem[CaLi]{CL}
    D.\,Cariolaro and K.-W.\,Lih: \textit{The Edge-Choosability of the Tetrahedron.} 
    Math.\ Gazette, 92:525 (2008), 543--546.
\bibitem[Ca]{ca}
  J.\,Carraher, S.\,Loeb, T.\,Mahoney, G.\,Puleo, M.-T.\,Tsai, D.\,West: 
  \textit{Extending Graph Choosability Results to Paintability.} Manuscript 2011.
\bibitem[Dr]{dr}
  A.\,A.\,Drisko: \textit{On the Number of Even and Odd Latin Squares of Order p+1.} 
  Advances in Mathematics 128 (1997), 20--35.
\bibitem[ElGo]{elgo}
  M.\,N.\,Ellingham, L.\,Goddyn: \textit{List Edge Colourings of Some 1-Factorable Multigraphs.}   Combinatorica 16 (1996), 343--352.
\bibitem[FiWi]{FW}
    S.\,Fiorini and R.\,J.\,Wilson: \textit{Edge-Colourings of Graphs.} 
    Research Notes in Mathematics, Pitman, 1977.
\bibitem[Ga]{ga}
    F.\,Galvin: \textit{The List Chromatic Index of a Bipartite Multigraph.} 
    J.\,Combin.\ Theory Ser.\ B 63 (1995), 153--158.
\bibitem[H\"{a}Ja]{haja}
    R.\,H\"{a}ggkvist  and J.\,Janssen: \textit{New Bounds on the List-Chromatic Index
    of the Complete Graph and Other Simple Graphs.} 
    Combin.\ Probab.\ Comput.\ 6 (1997), 295--313.
\bibitem[HKS]{hks}
  J.\,Hladk\'{y}, D.\,Kr\'{a}l', U.\,Schauz: \textit{Brooks' Theorem via the Alon-Tarsi Theorem.} 
  Discrete Mathematics 310 (2010), 3426--3428.
\bibitem[HWZ]{hwz}
  P.-Y.\,Huang, T.-L.\,Wong, X.\,Zhu: \textit{Application of Polynomial Method to On-Line List Colouring of Graphs.}
  European Journal of Combinatorics 33(5) (2012), 872--883.
\bibitem[JeTo]{jeto}
  T.\,R.\,Jensen, B.\,Toft: \textit{Graph Coloring Problems.}   Wiley, New York 1995.
\bibitem[Ka]{ka}
  J.\,Kahn: \textit{Asymptotically Good List-Colorings.} 
  J.\ Comb.\ Theory, Ser.\ A 73(1) (1996), 1--59.
\bibitem[Pe]{pe}
  J.\,Petersen: \textit{Die Theorie der regularen Graphs.}   Acta Math.\ 15 (1891), 193--220.
\bibitem[RiSch]{rs}
  A.\,Riasat, U.\,Schauz: \textit{Critically Paintable, Choosable or Colorable Graphs.} 
  Discrete Mathematics 312 (2012), 3373--3383.
\bibitem[Sch1]{schT}
  U.\,Schauz: \textit{Doctoral Thesis: Algebraically Solvable Problems.} 
    \url{https://publikationen.uni-tuebingen.de/xmlui/handle/10900/49068}
\bibitem[Sch2]{schAlg}
  U.\,Schauz: \textit{Algebraically Solvable Problems: 
  Describing Polynomials as Equivalent to Explicit Solutions} 
  The Electronic Journal of Combinatorics 15 (2008), \#R10.
\bibitem[Sch3]{schPC}
  U.\,Schauz: \textit{Mr.\ Paint and Mrs.\ Correct.} 
  The Electronic Journal of Combinatorics 15 (2008), \#R145.
\bibitem[Sch4]{schPAT}
  U.\,Schauz: \textit{Flexible Color Lists in Alon and Tarsi's Theorem, 
  and Time Scheduling with Unreliable Participants.} 
  The Electronic Journal of Combinatorics 17/1 (2010), \#R13.
\bibitem[Sch5]{schPCN}
  U.\,Schauz: \textit{A Paintability Version of the Combinatorial Nullstellensatz, 
  and List Colorings of \(k\)-partite \(k\)-uniform Hypergraphs.} 
  The Electronic Journal of Combinatorics 17/1 (2010), \#R176.
\bibitem[Sch6]{schPol}
  U.\,Schauz: \textit{Classification of Polynomial Mappings between Commutative Groups.} 
  Journal of Number Theory 139 (2014), p. 1--28.
\bibitem[StWa]{stwa}
  D.\,S.\,Stones, I.\,M.\,Wanless: \textit{How Not to Prove the Alon-Tarsi Conjecture.} 
  Nagoya Math.\ J.\ 205 (2012), 1--24.
\bibitem[Su]{su}
  Z.\,W.\,Sun: \textit{Zero-Sum Problems for Abelian $p$-Groups and Covers of the Integers
  by Residue classes.} Israel J.\ Math.\ 170 (2009), 235--252.
\bibitem[Wa]{wa}
  I.\,M.\,Wanless: \textit{Diagonally Cyclic Latin Squares.} 
  European Journal of Combinatorics, 25 (2004), 393--413.
\bibitem[Wi]{wi} M.\,Wilson: \textit{A Lemma on Polynomials Modulo $p^m$ and
    Applications to Coding Theory.} Discrete Mathematics 306 (23) (2006), 3154--3165.
\bibitem[Zhu]{zhu}
  Xuding Zhu: \textit{On-Line List Colouring of Graphs.} 
  The Electronic Journal of Combinatorics 16/1 (2009), \#R127.
\end{thebibliography}
\end{document}
