\documentclass[12pt]{article} \textwidth= 6.25in \textheight= 9.0in \topmargin = -10pt \evensidemargin=10pt \oddsidemargin=10pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 %\newtheorem{lemma}{Lemma} %\newtheorem{corollary}{Corollary} \usepackage{amsmath,amsfonts,amsthm} \newcommand{\sub}[2]{(#1)_{#2}} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\smpar}[1]{\marginpar{\footnotesize #1}} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} %\title{Minimal Zero Sequences of Finite Cyclic Groups} %\author{Vadim Ponomarenko} %\affil{Department of Mathematics, Trinity University,\\ One Trinity %Place, San Antonio, Texas 78212-7200} %\email{vadim@trinity.edu} %\authorrunninghead{Vadim Ponomarenko} %\titlerunninghead{Minimal Zero Sequences of Finite Cyclic Groups} %{\large \begin{center} Draft of May 24, 2005 \end{center}} %\begin{center}Phone: 210-999-8265 Fax: 210-999-8264\end{center}% To conform to AP submission requirements %\abstract{Let $MZS(G,k)$ denote the set of minimal zero sequences %of finite Abelian group $G$. In this paper we investigate the %structure of the elements of this set, and the cardinality of the %set itself. We do this for the class of groups $G=\Bbb{Z}_n$ for %$k$ both small ($k\le 4$) and large ($k> \frac{2n}{3}$). %}% %\keywords{Zero-sum problems, minimal zero sequence} \begin{document} \vspace*{-60pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4 (2004), \#A24} \vskip 50pt \begin{center} \uppercase{\bf Minimal Zero Sequences of Finite Cyclic Groups} \vskip 20pt {\bf Vadim Ponomarenko}\\ {\smallit Department of Mathematics, Trinity University, One Trinity Place, San Antonio, Texas 78212-7200}\\ {\tt vadim@trinity.edu}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 7/7/04, Accepted: 12/14/04, Revised: 12/16/04, Published: 12/22/04} \vskip 30pt \centerline{\bf Abstract} \noindent If $G$ is a finite Abelian group, let $MZS(G,k)$ denote the set of minimal zero sequences of $G$ of length $k$. In this paper we investigate the structure of the elements of this set, and the cardinality of the set itself. We do this for the class of groups $G=\Bbb{Z}_n$ for $k$ both small ($k\le 4$) and large ($k> \frac{2n}{3}$). \footnotesize \noindent {\it Keywords: Zero-sum problems, minimal zero sequence} \normalsize \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 4 (2004), \#A24\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \section*{\normalsize 1. Introduction} \addtocounter{section}{+1} Let $G$ be a finite Abelian group and $X=\{x_1, x_2, \ldots, x_k\}$ a multiset chosen from $G$. This unordered collection of not necessarily distinct elements of $G$ is traditionally called a \emph{sequence}. We say the \emph{length} of $X$ is $k$. If $x_1+x_2+\cdots+x_k=0$ (in $G$), then $X$ is called a \emph{zero-sequence}. We denote the set of all zero sequences of $G$ by $ZS(G)$. If $X$ is in $ZS(G)$ but no proper subsequence of $X$ is in $ZS(G)$, then $X$ is called a \emph{minimal zero sequence}. We denote the set of all minimal zero sequences of $G$ of length $k$ by $MZS(G,k)$, and the set of all minimal zero sequences of $G$ of any length by $MZS(G)$. The maximum $k$ for which $MZS(G,k)$ is nonempty is the well-known Davenport constant of $G$. Notice that Aut$(G)$ acts on $ZS(G)$, on $MZS(G)$, and on $MZS(G,k)$, inducing equivalence relations on these sets. We denote by $E(X)$ the set of sequences equivalent to sequence $X$, as induced in this manner. We express $G$ canonically as $\Bbb{Z}_{n_1}\oplus \Bbb{Z}_{n_2}\oplus\cdots\oplus \Bbb{Z}_{n_r}$, with $n_1|n_2|\cdots|n_r$. We say that zero sequence $X$ is \emph{basic} if $E(X)$ contains a zero sequence whose sum in coordinate $i$ is at most $n_i$ (for $1\le i\le r$), when the sum is viewed as an integer. To avoid confusion, henceforth the symbol `+' shall denote addition as integers, and the symbol $\sum X$ shall denote the sum of the elements of $X$ as integers. If $G$ is cyclic, that is its rank $r=1$, then all basic zero sequences are minimal. If every element of $MZS(G,k)$ is basic, we say that $(G,k)$ is a \emph{basic pair}, otherwise it is a \emph{non-basic pair}. Chapman, Freeze, and Smith \cite{CFS99} have shown that $(\Bbb{Z}_n,5)$ is a non-basic pair for all $n\neq 2,3,4,5,7$; further, for these five values of $n$, $(\Bbb{Z}_n,k)$ is a basic pair for all $k$. This left open the question of which $(\Bbb{Z}_n,k)$ are basic pairs. We offer a partial answer to this question, for all $n\ge 5$ and both very small and large $k$. We show in Theorems \ref{thm0} and \ref{thm-basic} that $(\Bbb{Z}_n,k)$ is a basic pair for $k>\frac{2n}{3}$ and $k\le 3$; whereas $(\Bbb{Z}_n,4)$ is a non-basic pair if $\gcd(n,6)\neq 1$. As an application, we count the number of minimal zero sequences of length greater than $\frac{2n}{3}$. \section*{\normalsize 2. Short Minimal Zero Sequences} \addtocounter{section}{+1} We first consider the question of whether $(\Bbb{Z}_n,k)$ is a basic pair for $n\le 4$. We have evidence to support the converse of the second part of the theorem; that is, we believe that if $\gcd(n,6)=1$, then $(\Bbb{Z}_n,4)$ is a basic pair. This has been verified computationally for $n\le 1000$. \begin{theorem}\label{thm0} Let $n\ge 5$. Then $(\Bbb{Z}_n,k)$ is a basic pair for $k=1,2,3$. If $\gcd(n,6)\neq 1$, then $(\Bbb{Z}_n,4)$ is a non-basic pair. \end{theorem} \begin{proof} The only element of $MZS(\Bbb{Z}_n,1)$ is $\{0\}$, which is basic. Let $X=\{a,b\}\in MZS(\Bbb{Z}_n,2)$. It has $an$, but $a+b+c<3n$, so $a+b+c=2n$. Now, $\phi(y)=n-y$ is an automorphism on $MZS(\Bbb{Z}_n,3)$, and $\phi(X)=\{n-a,n-b,n-c\}$ has $\sum\phi(X)=(n-a)+(n-b)+(n-c)=3n-(a+b+c)=3n-2n=n$. Hence $X$ is, in fact, basic. Suppose now that $n$ is even, so $n=2m$. We will now show that $X=\{1,m,m+1,2m-2\}$ is not basic, and hence that $(\Bbb{Z}_{2m},4)$ is a non-basic pair. First, $X$ sums to a multiple of $n$, but no proper subset does, hence $X$ is a minimal zero sequence. Now, let $\phi$ be any automorphism of $\Bbb{Z}_{2m}$. We must have $\phi(y)=ky$, for $k$ some positive odd integer, different from $m$, less than $n$. We see that $\phi(X)=\{k,km,km+k,k(2m-2)\}$. Reducing modulo $n$, we see that $\phi(X)=\begin{cases}\{k,m,m+k, 2m-2k\} & \text{if $km$.}\end{cases}$\\ In both cases we have $\sum \phi(X) = 2n$. Hence, $X$ is not basic if $n$ is even. Now suppose that $3|n$; that is, $n=3m$. We will now show that $X=\{1,m+1, 2m+1, 3m-3\}$ is not basic, and hence that $(\Bbb{Z}_{n},4)$ is a non-basic pair. First, $X$ sums to a multiple of $n$, but no proper subset does, hence $X$ is a minimal zero sequence. Now, let $\phi$ be any automorphism of $\Bbb{Z}_{n}$. We must have $\phi(y)=ky$, for $k$ some positive integer, less than $n$, relatively prime to $n$. We have $\phi(X)=\{k, km+k, 2km+k, 3km-3k\}$. We next note that $\{km+k,2km+k\}$ are congruent (modulo $n$) to $\{m+k, 2m+k\}$ in some order, depending on whether $k\equiv 1$ or $k\equiv 2$ (modulo 3). We can now reduce modulo $n$, and find $\phi(X)=\begin{cases}\{k,m+k,2m+k, 3m-3k\} & \text{if $k \frac{3n-3}{4}$. We state a theorem that was first proved in \cite{BEN75}, was rediscovered in \cite{Tha02a}, and restated in various forms in \cite{Gg99,Tha02}. \begin{theorem}\label{thm-old} Let $k>\frac{n+3}{2}$, and let $X\in MZS(\Bbb{Z}_n,k)$. Then there is some element $a\in \Bbb{Z}_n$ that appears in $X$ at least $2k-n$ times. \end{theorem} With a stronger restriction on $k$, we can get a bit more. This next result has a stronger hypothesis and conclusion than a similar one found in \cite{GG98a}. It has previously appeared in \cite{Gao00}, with a substantially different proof. \begin{theorem}\label{thm1} Let $k>\text{max}(\frac{n+3}{2},\frac{2n}{3})$, and let $X\in MZS(\Bbb{Z}_n,k)$. Then there is some element $a\in \Bbb{Z}_n$ that appears in $X$ at least $2k-n$ times, whose order is $n$ (in $\Bbb{Z}_n$). \end{theorem} \begin{proof}Applying Theorem \ref{thm-old}, we write $X=\{a^m,b_1,b_2,\ldots,b_j\}$ (where $m$ is the multiplicity of $a$), with $m\ge 2k-n$ and $m+j=k$. Now, suppose that the order of $a$ were less than $n$. Then, we can write $a=a'd$ and $n=n'd$, where $\gcd(a',n')=1$ and $d\ge 2$. However, if $d\ge 3$, we have $n'\le \frac{n}{3}< m$. Hence $X$ contains $n'$ copies of $a$, whose sum is $n'a=n'da'=na'$. But this is a proper zero-sum, which is forbidden. Therefore, we must have $d=2$, $n$ even (since $d|n$), and $m<\frac{n}{2}$ (since $a^m$ is not a zero subsequence). The remainder of the proof develops a contradiction in these circumstances. We now show that there is an automorphism $\phi$ of $G$ with $\phi(a)=2$. Because $\gcd(a',n')=1$, there is some integer $w$ with $wa'\equiv 1$ modulo $n'$. If $w$ is odd, then $\gcd(w,n)=1$ and $\phi(x)=wx$ is the desired automorphism. If $w$ is even, then $n'$ must be odd. In this case, $(w+n')a'\equiv 1$ modulo $n'$. We have $w+n'$ odd, so $\gcd(w+n',n)=1$ and therefore $\phi(x)=(w+n')x$ is the desired automorphism. Henceforth we will assume without loss that $a=2$. We now consider the odd elements of $X$. We pair them arbitrarily and take the residue modulo $n$. The result is $X'=\{2^m,c_1,c_2,\ldots, c_{j'}\}$, where some $c_{i'}$ are equal to an even $b_i$, while others are equal to the reduced sum of two odd elements of $X$. This is still a minimal zero sequence, and all of its terms are even. Further, we have $j'\ge \frac{j}{2}$. Note that $m+j=k> \frac{2n}{3}$, and hence $j'\ge \frac{j}{2}> \frac{n}{3}-\frac{m}{2}> \frac{n}{3}-\frac{n}{4}+\frac{1}{2}=\frac{n}{12}+\frac{1}{2}$. Therefore, in particular, $j'\ge 2$. Now we will show that any proper subsequence of $\{c_1,c_2,\ldots,c_{j'}\}$ has sum at most $n-2m-2$, by induction on the cardinality of the subsequence. For the base case, observe that each singleton $c_i$ must have $c_i\le n-2m-2$, as otherwise $X'$ would not be a minimal zero sequence. Now, let $S$ be a proper subsequence. Write $S=S_1\cup S_2$, the disjoint union of two nonempty subsequences. By the inductive hypothesis, $\sum S_1\le n-2m-2$ and $\sum S_2\le n-2m-2$. Adding, we get $\sum S = \sum S_1+\sum S_2\le 2n-4m-4\le 2n-\frac{4n}{3}-4=\frac{2n}{3}-4 \frac{2n}{3}$, and let $X\in MZS(\Bbb{Z}_n,k)$. Then there is some element $a\in \Bbb{Z}_n$ that appears in $X$ more than $\frac{k}{2}$ times, whose order is $n$ (in $\Bbb{Z}_n$). \end{corollary} \begin{proof} The condition $n\ge 10$ ensures that $\frac{2n}{3}\ge\frac{n+3}{2}$, so that the conditions of Theorem \ref{thm1} are met. As before, we write $X=\{a^m,b_1,b_2,\ldots,b_j\}$. Since $k> \frac{2n}{3}$, we must have $m> 2(\frac{2n}{3})-n=\frac{n}{3}$. We also have $m+j=k$, and hence $m\ge 2k-n=(m+j)+k-n$. Rearranging, we get $j\le n-k< \frac{n}{3}$. Combining these two facts, we get $j< \frac{n}{3}< m$, and hence $m> \frac{k}{2}$. \end{proof} This allows us to conclude that all sufficiently long minimal zero sequences of $\Bbb{Z}_n$ are basic. \begin{theorem}\label{thm-basic} Let $n\ge 10, k> \frac{3n-3}{4}$. Then $MZS(\Bbb{Z}_n,k)$ is a basic pair. \end{theorem} \begin{proof} Let $Y\in MZS(\Bbb{Z}_n,k)$. By Theorem \ref{thm1} and Corollary \ref{cor1}, there is some element $y\in Y$, of order $n$, that appears at least $2k-n$ times. Let $\phi\in Aut(\Bbb{Z}_n)$ be such that $\phi(y)=1$. Let $X=\phi(Y)$. We will show that $\sum X=n$, which proves the theorem. Write $X=\{1^m,x_1,x_2,\ldots,x_j\}$, where $m\ge 2k-n$, $m+j=k$, and each $x_i>1$. First, note that if $j=1$ then $\sum X=m+x_j1$ and we see that each $x_i\le n-m-1$, since otherwise $X$ would properly contain a zero sequence. Now, $x_12\frac{3n-3}{4}-n=\frac{n-3}{2}$. This is impossible, and hence $w=j$ and thus $\sum X=n$. \end{proof} It has come to our attention that a stronger result, with a different proof, has been published in \cite{Gao00}: \begin{theorem}\label{thm-basic} Let $n\ge 10, k> \frac{2n}{3}$. Then $MZS(\Bbb{Z}_n,k)$ is a basic pair. \end{theorem} \section*{\normalsize 4. Counting Minimal Zero Sequences} \addtocounter{section}{+1} The cardinality of $MZS(\Bbb{Z}_n,k)$ has already been computed for small $k$, in \cite{FMPT03a}, as follows. \begin{theorem} $|MZS(\Bbb{Z}_n,2)|=\lfloor\frac{n}{2}\rfloor$. $|MZS(\Bbb{Z}_n,3)|=\frac{1}{6}(n^2-\alpha)$, where $\alpha$ is given by:\\[-15pt] \begin{center}\begin{tabular}{c|llllll} $(n \mod{6}) \equiv$ & 0 & 1 & 2 & 3 & 4 & 5\\ \hline $\alpha = $ & 0 & 1 & 4 & -3 & 4 & 1 \\ \end{tabular}\end{center} \end{theorem} We can find $|MZS(\Bbb{Z}_n,k)|$ for large $k$ with the results of Section \ref{large}. For this purpose, we need the following structure theorem. \begin{theorem}\label{one-only} Let $n\ge 10, k> \frac{2n}{3}$, and let $X\in MZS(\Bbb{Z}_n,k)$ be basic. Then there is exactly one $Y\in E(X)$ with $\sum Y=n$. \end{theorem} \begin{proof} As $X$ is basic, so at least one such $Y$ exists. Suppose $Y$ has $i$ terms of $1$, and the remaining $k-i$ terms are not. Hence $n=\sum Y\ge i+2(k-i)=2k-i$. Hence $i\ge 2k-n> 2k-\frac{3}{2}k=\frac{k}{2}$. Hence over half of the terms of $Y$ are $1$. Suppose that there are $Y,Y'\in E(X)$ with $\sum Y=\sum Y'=n$. Let $\phi\in Aut(\Bbb{Z}_n)$ with $\phi(Y)=Y'$. By the previous, $1$ appears in each more than $\frac{k}{2}$ times. Both $1$, $\phi(1)$ appear more than $|Y'|/2$ times in $Y'$, but there are not enough elements in $Y'$ for these to be different. Hence $\phi(1)=1$, and therefore $\phi$ is the identity and $Y=Y'$. \end{proof} We are now ready to count all minimal zero sequences of sufficiently large length. Computational evidence suggests that the condition $k> \frac{2n}{3}$ can be improved to $k\ge \frac{n+4}{2}$. \begin{theorem} Let $n\ge 10, k> \frac{2n}{3}$. Then $|MZS(\Bbb{Z}_n,k)|=\phi(n)p_k(n)$, where $\phi$ is Euler's totient function and $p_k(n)$ denotes the number of partitions of $n$ into $k$ parts. \end{theorem} \begin{proof} By Theorem \ref{thm-basic}, every minimal zero sequence is basic. Therefore, each equivalence class induced by $Aut(\Bbb{Z}_n)$ includes an element whose sum is $n$. By Theorem \ref{one-only}, each equivalence class contains exactly one element whose sum is $n$. It is clear that the set of minimal zero sequences whose sum is $n$ is exactly the set of partitions of $n$ into $k$ parts. There are therefore $p_k(n)$ equivalence classes. The cardinality of each equivalence class is $|Aut(\Bbb{Z}_n)|=\phi(n)$. \end{proof} \section*{\normalsize Acknowledgements} The author would like to gratefully acknowledge the work of an anonymous referee, whose suggestions improved several of these proofs. \bibliographystyle{plain} \begin{thebibliography}{1} \footnotesize \bibitem{BEN75} J.~D. Bovey, Paul Erd{\H{o}}s, and Ivan Niven, \newblock Conditions for a zero sum modulo {$n$} \newblock {\em Canad. Math. Bull.}, 18(1): 27--29, 1975. \bibitem{CFS99} Scott~T. Chapman, Michael Freeze, and William~W. Smith, \newblock Minimal zero-sequences and the strong {D}avenport constant \newblock {\em Discrete Math.}, 203(1-3): 271--277, 1999. \bibitem{FMPT03a} Bryson~W. Finklea, Terri Moore, Vadim Ponomarenko, and Zachary~J. Turner, \newblock On block monoid atomic structure \newblock In Preparation \bibitem{Gao00} W.~D. Gao, \newblock Zero sums in finite cyclic groups \newblock {\em Integers} {\bf 0}, A12, 7 pp. (electronic), 2000. \bibitem{GG98a} Weidong Gao and Alfred Geroldinger, \newblock On the structure of zerofree sequences \newblock {\em Combinatorica}, 18(4): 519--527, 1998. \bibitem{Gg99} Weidong Gao and Alfred Geroldinger, \newblock On long minimal zero sequences in finite abelian groups \newblock {\em Period. Math. Hungar.}, 38(3): 179--211, 1999. \bibitem{Tha02a} R.~Thangadurai, \newblock Interplay between four conjectures on certain zero-sum problems \newblock {\em Expo. Math.}, 20(3): 215--228, 2002. \bibitem{Tha02} R.~Thangadurai, \newblock Non-canonical extensions of {E}rd{\H o}s-{G}inzburg-{Z}iv theorem \newblock {\em Integers} {\bf 2} , A7, 14 pp. (electronic), 2002. \end{thebibliography} \end{document} Further, we can write $k=2\alpha+1$, for some integer $\alpha$. We reduce $\sum\phi(X)$ modulo $n$ and add to get $\sum \phi(X)=k+(km\text{ mod }n)+(km+k\text{ mod } n)+(2m+k\text{ mod } n)+(2km-2k\text{ mod }n)$. We now repeatedly use the fact that $r\text{ mod }s = r - s\floor{r/s}$, to simplify:\\ $k + (km - n\floor{\frac{km}{n}})+(km+k - n\floor{\frac{km+k}{n}}) + (2km-2k-n\floor{\frac{2km-2k}{n}})\\ = 4km - 2m(\floor{\frac{km}{2m}}+\floor{\frac{km+k}{2m}}+\floor{\frac{2km-2k}{2m}})\\ = 2km-2m( \floor{\frac{2\alpha m+m}{2m}}+\floor{\frac{2\alpha m + m + k}{2m}}+\floor{\frac{-k}{m}})\\ = -2m(-1+\floor{\frac{k+m}{2m}}+\floor{\frac{-k}{m}}) $\\ Whether $km$, we see that $\sum\phi(X)=4m=2n$. Hence, $X$ is basic if $n$ is even. ------------------------------------- Further, we can write $k=3\alpha+\beta$, for integers $\alpha, \beta$ with $1\le \beta\le 2$. We reduce modulo $n$ and add to get $\sum \phi(X)=k+(km+k\text{ mod } n)+(2m+k\text{ mod } n)+(3km-3k\text{ mod }n)$. We now repeatedly use the fact that $r\text{ mod }s = r - s\floor{r/s}$, to simplify:\\ $k + (km+k - n\floor{\frac{km+k}{n}}) + (2km+k-n\floor{\frac{2km+k}{n}}) + (3km-3k-n\floor{\frac{3km-3k}{n}})\\ =6km-n(\floor{\frac{km+k}{n}}+\floor{\frac{2km+k}{n}}+\floor{\frac{3km-3k}{n}})\\ =2n(3\alpha+\beta) -n(\floor{\frac{3\alpha m+\beta m+k}{3m}}+\floor{\frac{6\alpha m+2\beta m+k}{3m}}+\floor{\frac{3(3\alpha+\beta)m-3k}{3m}})\\ =n\beta -n(\floor{\frac{\beta m+k}{3m}}+\floor{\frac{2\beta m+k}{3m}}+\floor{\frac{-3k}{3m}})$.\\ Now we set $k=\gamma m + \delta$, for integers $\gamma, \delta$, with $0\le \gamma\le 2$ and $0< \delta