\documentclass[12pt]{article} \usepackage{e-jc} \title{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 Xi’an Jiaotong-Liverpool University\\[-0.8ex] \small Suzhou 215123, China\\[-0.8ex] \small \texttt{uwe.schauz@xjtlu.edu.cn} } \date{\dateline{January 21, 2014}{\llap{--------------\ }% Version: \printday \Zeit{}\,.}\\%{January 21, 2014}{January 21, 2014}\\ \small Mathematics Subject Classifications: 05C15, 05E18, 05E99, 05A19, 91A43\\[1cm] \textbf{\textit{Dedicated to the memory of David Cariolaro}}\\[5mm]} %12. July 1969? - 10. Jan. 2014 %------------------------------------------------------------------------------ \addtolength\marginparsep{-2pt} %%%%%%%%%%%%%%%%%% %%% 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}%ß als Eingabe statt "s u.s.w. \usepackage{srcltx}%DVI inverse search. Last comilatin: \usepackage[inactive]{srcltx} %% Sprache,Darstellung %% \usepackage{datetime}%definiert \xxivtime, \ampmtime, ... .(Muss vor ngerman kommen) \usepackage{ngerman}%neue Trennregeln. \selectlanguage{USenglish} \nonfrenchspacing%geringfügig größere Leerzeichenabstände der Satzzeichen. %% Text-Symbole %% %\usepackage{eurosym}%DIN-Euro \euro \EUR1.20 \usepackage{textcomp}%TS1-Zeichencodierung z.B. \textdollar $. %\usepackage{url} %\usepackage{mathrsfs} %% Grafik %% %\usepackage{epic} %\usepackage{eepic} %\usepackage[dvips,debugshow]{graphicx} \usepackage{color} \usepackage{cancel} %% Mathematik %% \usepackage{amsmath} %\addtolength{\topsep}{.2\baselineskip} \usepackage{amsthm} %\addtolength{\topsep}{-.2\baselineskip} %\usepackage{accents}%\accentset{*}{G} %\usepackage{amscd}%einfache Umgebung f�r kommutative Diagramme (CD). %\usepackage[boxruled,lined,longend]{algorithm2e} %% Mathematik-Symbole %% \usepackage{amssymb}%z.B. $\Box$ ,enth�lt die latexsym-Zeichen. \usepackage{stmaryrd}%z.B. $\llbracket$ \usepackage{bm}%more general and robust implementation of \boldsymbol. %% Tabellen %% %\usepackage{booktabs} \usepackage{enumerate} %optionales Argument 1,i,I,a,A (z.B.[{I}tem (i):]) f�r \enumerate. %% Sonstiges %% \usepackage{afterpage} \usepackage{xspace} %definiert \xspace =passendes Leerzeichen nach selbst definierten Makros. %\usepackage{datetime}%definiert \xxivtime, \ampmtime, ... --> vor ngerman %\usepackage{hyperref} %%%%%%%%%%%%%%%%%%%%%%%% %%% Definitionen %%% %%%%%%%%%%%%%%%%%%%%%%%% %% Z�hler,L�ngen %% \setlength\mathsurround{.2em} \emergencystretch.03\textwidth%zus�tzlicher Leerraum bei schwierigen Umbr�chen 1em="M" %% Umgebungen %% %\theoremstyle{plain}%This is the default \newtheoremstyle{Theorem}{.7\baselineskip}{1\baselineskip}{\itshape}{}{\bfseries}{.}{ }{} \theoremstyle{Theorem} \newtheorem{Satz}{Theorem}[section] \newtheorem{EquiDef}[Satz]{Equivalence and Definition} \newtheorem{Korollar}[Satz]{Corollary} \newtheorem{Verallgemeinerung}[Satz]{Generalisation} \newtheorem{Verschaerfung}[Satz]{Verschärfung} \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}}} %% Abk�rzungen %% %\newcommand\V{Vierfarbenproblem\xspace} %% 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{\kern 1pt}%0.08em=1.44mu \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} %Zeilenanfang-->\noms \def\rand #1"#2"{\mathRand{\(#2\)}#1#2} %\rand muss auserhalb von $.".".$ stehen! %Zeilenanfang-->\noms, Altrnative: \mbox{}\rand %Seitenumbruch vor \rand$$ möglich, benutze xxx% \rand$$ \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}} \newcommand\ä{\alpha} \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} %%%%%%%%%%%%%%%%%% %%% Inhalt %%% %%%%%%%%%%%%%%%%%% %\small Mathematics Subject Classifications: %%90C35 Programming involving graphs or networks %%94C11 Switching Theory (Bolean) %%94B25 Combin. Codes %%94B05 Lin Codes generel %%51E20 Combinatorial structures in finite projective spaces %%51E22 Linear codes and caps in Galois spaces %%68Rxx Discrete mathematics in relation to computer science %%68R10 Graph theory %%05A19 Combinatorial identities %%05C35 Extremal problems %% 05D05 Extremal set theory %% 05D10 Ramsey theory % 41A05, %Interpolation %%13Bxx Ring extensions and related topics %%13B25, %Polynomials over commutative rings [See also 11C08, 13F20, 13M10] %%13Fxx Arithmetic rings and other special rings %%13F20, %Polynomial rings and ideals; rings of integer-valued polynomials %%13Mxx Finite commutative rings {For number-theoretic aspects, see 11Txx} %%13M10, %Polynomials %%13Pxx Computational aspects of commutative algebra [See also 68W30] % 13P10, %Polynomial ideals, Gr�bner bases [See also 13F20] %%11Txx, %Finite fields and commutative rings (number-theoretic aspects) %%11T06, %Polynomials %%11Cxx Polynomials and matrices %%11C08 Polynomials [See also 13F20] %%05Exx, %Algebraic Combinatorics % 05E99, %None of the above, but in this section %%11Axx Elementary number theory {For analogues in number fields, see 11R04} %%11A07 Congruences; primitive roots; residue systems %%11Bxx Sequences and sets %%11B75 Other combinatorial number theory %%11Cxx Polynomials and matrices % 11C08, %Polynomials [See also 13F20] %%11Dxx Diophantine equations [See also 11Gxx, 14Gxx] %%11D72 Equations in many variables [See also 11P55] % 11D79, %Congruences in many variables % 05C15, %Colorings % 05C21, %Flows %% 05C50, %Graphs and Lin. Alg. (Matrices) % 15A15%, %$\det,\per$ %%05C20, %Directed G. (tournaments) %%05C45, %Euler G., (Hamilton G.) %%05C10 %Topol. GT. (embeddings) %%91A43%, %Games involving graphs %%05C57%, %Games on graphs %} %\addtolength{\normalbaselineskip}{3pt} %\newcommand{\mybaselinestretch}{1.055} %\renewcommand{\baselinestretch}{\mybaselinestretch} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%% Dokument %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\journal{Discrete Mathematics} \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 $id_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^\ä$ and the graphs $K_{p^\ä+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