\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 

\usepackage{amsmath, amssymb,amsthm}



\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\theoremstyle{definition}

\newtheorem{definition}[theorem]{Definition}





\def\N{\mathbb N}
\def\Z{\mathbb Z}
\def\R{\mathbb R}
\def\d{\mathsf d}
\def\D{\mathsf D}
\def\e{\mathsf e}
\def\E{\mathsf E}
\def\f{\mathcal F}
\def\ord{\text{\rm ord}}
\def\lcm{\text{\rm lcm}}
\def\s{\sigma}
\def\S{\Sigma}



\begin{document}

\begin{center}
{\bf ON ZERO-SUM SUBSEQUENCES IN FINITE ABELIAN GROUPS}
\vskip 20pt
{\bf Wolfgang A. Schmid}\\
{\smallit  Institut f\"ur Mathematik,
Karl-FranzensUniversit\"at,
Heinrichstrasse 36,
8010 Graz, Austria}
\end{center}
\vskip 30pt
\centerline{\smallit Received: 11/14/00, Revised: 12/11/00,  Accepted: 12/29/00, Published:
1/11/01}
\vskip 30pt

\centerline{\bf Abstract}

\noindent
Let $G$ be a finite abelian group and $k\in\N$ with $k\nmid \exp(G)$.
Then $\E_k(G)$ denotes the smallest integer $l\in\N$ such that every
sequence $S\in\f(G)$ with $|S|\ge l$ has a zero-sum subsequence $T$ with
$k\nmid |T|$.  In this paper we prove that if
$G=C_{n_1}\oplus\dots\oplus C_{n_r}$ is a p-group, $k\in\N$ with
$k\nmid \exp(G)$ and $\gcd(p,k)=1$, then 
\[\E_k(G)=\left\lfloor\frac{k}{k-1}\sum_{i=1}^r (n_i-1)\right\rfloor
+1.\] 

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL
NUMBER THEORY \smalltt 1 (2001), \#A01\hfill}


\thispagestyle{empty} 
\baselineskip=15pt 
\vskip 30pt 

\section*{\normalsize 1. Introduction and Main Result}
\addtocounter{section}{+1}

Let $G$ be an additively written, finite abelian group and let $\exp(G)$ denote its
exponent. We will consider sequences in $G$ and recall some terminology. 
Let $\f(G)$ be the multiplicatively written, free abelian monoid with
basis $G$
and let $S=\prod_{i=1}^l g_i\in\f(G)$ be a {\it sequence} in $G$. We
denote by
$|S|=l\in\N_0$
the {\it length} of $S$ and by $\s(S)=\sum_{i=1}^l g_i\in G$ the {\it
sum} of $S$.
We call the sequence $S$ a {\it zero-sum sequence}, if $\s(S)=0$.
If $\emptyset\not= I\subset \{1,\dots,l\}$, then we call $T=\prod_{i\in
I} g_i\in\f(G)$ a
{\it subsequence} of $S$. If $\s(T)=0$, we call $T$
a {\it zero-sum subsequence} of $S$.



In 1961 P. Erd\H{o}s, A. Ginzburg and A. Ziv (cf. \cite{egz}) proved
that in case $G$ is a cyclic group, $2|G|-1$ is the smallest integer $l$
such that every sequence
$S\in\f(G)$ with $|S|\ge l$ has a zero-sum subsequence with $|T|=|G|$.



This was a starting point to study subsequences of given sequences, that have sum zero and
satisfy some given additional property. Each of the following problems
had its own motivation and 
its own history.


\noindent
{\bf Problem}: Determine the smallest integer $l\in\N$ such that every sequence $S\in\f(G)$
with $|S|\ge l$ has a zero-sum subsequence $T$ such that

\begin{enumerate}
\item $|T|=|G|$ (cf. \cite{car,gao4,hoo}).
\item $|T|=\exp(G)$ (cf. \cite{ad,har,kem}).
\item $1\le |T|\le \exp(G)$ (cf. \cite{gg}).
\item $T$ is a product of $k$ zero-sum subsequences (for given $k\in\N$)
(cf. \cite{hk}).
\end{enumerate}       



Recently W. D. Gao studied Problem 2 in a series of papers (cf. \cite{gao1,gao2,gao3}). To do so he introduced the following invariant.


\begin{definition}
Let $G$ be a finite abelian group and $k\in\N$ with $k\nmid \exp(G)$.
Then $\E_k(G)$ denotes the smallest integer $l\in\N$ such that every
sequence $S\in\f(G)$ with $|S|\ge l$ has a zero-sum subsequence $T$ with
$k\nmid |T|$.
\end{definition}



W. D. Gao showed how the invariant is related with Problem 2 and he determined $\E_2(G)$ in case
$G$ is a p-group with odd $p$ or $G$ is a cyclic group of odd order (cf.
\cite{gao3}).
In this paper we determine $\E_k(G)$ in case $G$ is a p-group, $k\in\N$
with $k\nmid\exp(G)$ and $\gcd(p,k)=1$.


For some real number $x\in\R$ let $\lfloor x\rfloor =\max\{m\in\Z\mid
m\le x\}$ and for some $n\in\N$ let $C_n$ denote the cyclic group with
$n$ elements.  

The aim of the paper is to prove the following result:



\begin{theorem}\label{ekp}
Let $G=C_{n_1}\oplus\dots\oplus C_{n_r}$ be a p-group, $k\in\N$ with
$k\nmid \exp(G)$ and $\gcd(p,k)=1$. Then 
\[\E_k(G)=\left\lfloor\frac{k}{k-1}\sum_{i=1}^r (n_i-1)\right\rfloor
+1.\] 
\end{theorem}




\section*{\normalsize 2. Proof of the Main Result}
\addtocounter{section}{+1}
\setcounter{theorem}{0}

Throughout, let $G$ denote a finite abelian group and let $k\in\N$ with
$k\nmid \exp(G)$.
If $|G|>1$, then there are uniquely determined $n_1,\dots, n_r\in\N$ with 
$1<n_1|\dots|n_r$ and \[G\cong C_{n_1}\oplus\dots\oplus C_{n_r}.\]
If $|G|=1$, we set $r=n_r=1$. 


Let $\D(G)$ denote {\it Davenport's constant}, which is defined as the
smallest integer $l\in\N$ such that every sequence $S\in\f(G)$ with
$|S|\ge l$ contains a zero-sum subsequence. 
Furthermore, let $\mathsf s(G)$ denote the invariant arising from Problem
2, i.e. the smallest integer $l\in\N$ such that every sequence
$S\in\f(G)$ with $|S|\ge l$ has a zero-sum subsequence $T$ such that
$|T|=\exp(G)$.
We start with a simple lemma showing relations between $\D(G)$, $\mathsf
s(G)$ and $\E_k(G)$ 



\begin{lemma}
\hskip 20pt
1. $\D(G)\le \E_k(G)\le \mathsf s (G)$.

\hskip 77pt 2. If $\D(G)<k$, then $\D(G)=\E_k(G)$.


\end{lemma}

\begin{proof}
The inequality $\D(G)\le \E_k(G)$ holds by definition. The inequaltiy
$\E_k(G)\le \mathsf s (G)$ holds, since $k\nmid \exp(G)$ and therefore a
zero-sum subsequence
of length $\exp(G)$ is as well a zero-sum subsequence of length not
divisible by $k$.\\
To prove $\D(G)=\E_k(G)$, in case $\D(G)<k$, it suffices to prove
$\E_k(G)\le\D(G)$.
Let $T\in\f(G)$ with $|T|=\D(G)$. By definition $T$ has a zero-sum
subsequence $Z$. Since $|Z|\le|T|<k$, we have $k\nmid |T|$. Therefore
every $S\in\f(G)$ with
$|S|\ge \D(G)$,
has a zero-sum subsequence of length not divisible by $k$. This implies
$\E_k(G)\le \D(G)$.
\end{proof}



In various problems involving zero-sum sequences it has turned out to be useful to reformulate the original problem into an equivalent one involving zerofree sequences (as usual, we call a sequence {\it zerofree}, if it has no zero-sum subsequence). This procedure proved successful in all investigations on the generalized Davenport's constant (cf. Problem 4 of the Introduction)  and in all investigations on the cross number of sequences (cf. \cite{ge94,gs96}).
Although the above reformulation of the given problem is quite simple in
many cases, we regard this as a key idea which we are going to apply for
investigating $\E_k(G)$.



We need some further notations. Let $\d(G)$ denote the largest integer $l\in\N$ such that there exists a sequence $S\in\f(G)$ which is zerofree and has length $l$.     
It is well known that 
\[\D(G)=\d(G)+1 \qquad \text{and}\qquad \sum_{i=1}^r (n_i-1)\le \d(G).\]

\begin{definition}
Let $\e_k(G)$ denote the largest integer $l\in\N$ such that there exists
a sequence $S\in\f(G)$ with $|S|=l$ and $k\mid |T|$ for all zero-sum
subsequences $T$ of $S$.  
\end{definition}

The following will show that there are relations among $\E_k(G)$ and $\e_k(G)$, which are similar to those among $\D(G)$ and $\d(G)$.



\begin{lemma}\label{ee+1}
\[\E_k(G)=\e_k(G)+1.\]
\end{lemma}

\begin{proof}
By definition, $\e_k(G)<\E_k(G)$. Indeed, there exists a sequence
$S\in\f(G)$ of length $\e_k(G)$ such that $k$ divides the lengths of all
zero-sum subsequences of $S$. On the other hand, the maximality of
$\e_k(G)$ implies that every sequence with length greater $\e_k(G)$ has a
zero-sum subsequence with length not divisible by $k$. Therefore
$\E_k(G)\le \e_k(G)+1$, and the
equality follows.
\end{proof}



\begin{lemma}\label{ekast}
\[\left\lfloor\frac{k}{k-1}\sum_{i=1}^r (n_i-1)\right\rfloor\le \e_k(G).\]
\end{lemma}

\begin{proof}
The proof is done by construction of a sequence of length
$\left\lfloor\frac{k}{k-1}\sum_{i=1}^r (n_i-1)\right\rfloor$ such that
$k$ divides the length of every zero-sum subsequence. Let
$e_1,\dots,e_r\in G$ such that 
\[G=\langle e_1\rangle \oplus \dots \oplus \langle e_r\rangle\]
and $\ord(e_i)=n_i$ for all $i\in\{1,\dots,r\}$.

If $S'=\prod_{i=1}^r (-e_i)^{(n_i-1)}$, then $S'$ is zerofree and it
remains to construct a sequence $S''$ of length
$\lfloor\frac{\sum_{i=1}^r (n_i-1)}{k-1}\rfloor $ such that $k\mid |Z|$
for every zero-sum subsequence $Z$ of $S'S''$. 
We consider the sequence $T=\prod_{i=1}^r e_i^{(n_i-1)}$, which is
zerofree and we write it as a product of sequences $B_1,\dots ,B_l$ of
length $k-1$ and a rest $R$ of length less than $k-1$:
\[T=(\prod_{i=1}^l B_i)R\]
with $|B_i|=k-1$ for all $i\in\{1, \dots ,l\}$ and $0\le |R|<k-1$.
We define                 
\[S''=\prod_{i=1}^l \s(B_i).\] 
It follows that $S''$ is zerofree and has length
$|S''|=l=\lfloor\frac{|T|}{k-1}\rfloor=\lfloor\frac{\sum_{i=1}^r
(n_i-1)}{k-1}\rfloor $.
Therefore $|S'S''|=\left\lfloor\frac{k}{k-1}\sum_{i=1}^r
(n_i-1)\right\rfloor$, and it remains to show that $k$ divides the length
of every zero-sum subsequence. Let $Z$ denote an arbitrary zero-sum
subsequence of $S'S''$. Since $S'$ and $S''$ are both zerofree, $Z$ can
be written as $Z'Z''$ with subsequences $Z'$ of $S'$ and $Z''$ of $S''$.  
Every element $z''$ of $Z''$ can be written in the form
$z''=\sum_{j=1}^{k-1} e_{i_j}$ with suitable $i_j\in\{1,\dots,r\}$. Since
$Z$ is a
zero-sum sequence, we get
$\prod_{j=1}^{k-1}(-e_{i_j})|Z'$.
The zero-sum sequence
$z''(\prod_{j=1}^{k-1}(-e_{i_j}))$ is of length $k$ and $Z$
can be written as a product of sequences of this form. Therefore $k$
divides $|Z|$.
\end{proof}



\begin{lemma}\label{ek12}
If $G=G_1\oplus G_2$, then
\[ \e_k(G_1)+\e_k(G_2)\le \e_k(G).\] 
\end{lemma}



\begin{proof}
Since $\exp(G)=\lcm(\exp(G_1),\exp(G_2))$
and $k\nmid \exp(G)$, it follows that $k\nmid \exp(G_1)$ and $k\nmid
\exp(G_2)$. Therefore $\e_k(G_1)$ and $\e_k(G_2)$ are
well-defined. 
For $i\in\{1,2\}$ let $S_i\in\f(G_i)$ be a sequence with
$|S_i|=\e_k(G_i)$ such that for every zero-sum subsequence $T_i$ of
$S_i$, $k$ divides $|T_i|$.
We define $S=S_1S_2\in\f(G)$.
For every zero-sum subsequence $T$ of $S$,
there exist $T_i\in\f(G_i)$  for $i\in\{1,2\}$ such that $T=T_1T_2$.
Since $T$
has sum zero, the sequences $T_1$ and $T_2$ have sum zero too.
Due to the definition of $S_1$ and $S_2$, we have $k\mid |T_1|$ and
$k\mid |T_2|$.
Therefore $k\mid |T_1|+|T_2|=|T|$ and $S$
is a sequence in $G$ of length $\e_k(G_1)+\e_k(G_2)$,
for which every zero-sum subsequence has a length divisible by $k$.
By definition of $\e_k(G)$, we have 
\[\e_k(G_1)+\e_k(G_2)=|S_1|+|S_2|=|S|\le \e_k(G).\] 
\end{proof}



For the proof of Theorem \ref{ekp} we need two results on p-groups.
The first result has been proved independently by D. Kruyswijk and J. E.
Olson (cf. \cite{emde, ols1})



\begin{theorem}\label{dg}
If $G$ is a p-group, then $\d(G)=\sum_{i=1}^r (n_i-1)$.
\end{theorem}



Theorem \ref{dg} implies that for two p-groups $G$ and $H$ 
\[\d(G)+\d(H)=\d(G\oplus H).\]
The second result is due to W. D. Gao.
For convenience we repeat its short proof.



\begin{lemma}\cite{gao3}\label{gpn}
Let $G$ be a p-group. Then there exists a p-group $H$ such that
$D(G\oplus H)$ is a power of $p$.
\end{lemma}



\begin{proof}
Let $G=\bigoplus_{i=1}^r C_{p^{m_i}}$ with $m_i\in\N$ and
$M=\prod_{i=1}^r m_i$. 
Then $G$ is a direct summand of
\[\bar{G}=C_{p^M}^{p^M-r+1}\oplus \bigoplus_{i=1}^r
C_{p^{m_i}}^{\frac{p^M-1}{p^{m_i}-1}}\]
and by Theorem \ref{dg}
\[\begin{split}
\D(\bar{G})= & 1+\d(\bar{G})=
1+(p^M+1-r)(p^M-1)+\sum_{i=1}^r\frac{p^M-1}{p^{m_i}-1}(p^{m_i}-1)=\\
& 1+(p^M+1)(p^M-1)=p^{2M}.\end{split}\]
\end{proof}


Now we are ready to prove Theorem \ref{ekp}.



\begin{proof}[Proof of Theorem \ref{ekp}]
By Lemma \ref{ee+1} and Lemma \ref{ekast} it suffices to prove 
\[\e_k(G)\le \left\lfloor\frac{k}{k-1}\sum_{i=1}^r (n_i-1)\right\rfloor.\]
The proof is done in three steps. In the first and the second step the
proof is given for special groups. In the third step the general case is
proved, by using the result for the groups of special type.

\begin{enumerate}
\item Suppose that there exists some $n\in\N$ such that
$\d(G)=(k-1)(p^n-1)$.\\
Let $S\in\f(G)$ with $|S|=\left\lfloor\frac{k}{k-1}\sum_{i=1}^r
(n_i-1)\right\rfloor+1$. We shall prove that $S$ possesses a zero-sum
subsequence $T$ such that $k\nmid |T|$. 
This implies that 
\[\e_k(G)=\E_k(G)-1\le |S|-1\le \left\lfloor\frac{k}{k-1}\sum_{i=1}^r
(n_i-1)\right\rfloor.\] 
We consider the map 
\[\zeta:\begin{cases} G \rightarrow G\oplus C_{p^n} \\ 
g\mapsto g+e \end{cases}\]
where $G\oplus C_{p^n}=G\oplus\langle e\rangle$. For $W=\prod_{i=1}^l
g_i\in\f(G)$ we set $\zeta(W)=\prod_{i=1}^l \zeta(g_i)\in\f(G\oplus
C_{p^n})$.
By Theorem \ref{dg} we get
\[|S|=\frac{k}{k-1}\d(G)+1=\d(G)+1+(p^n-1)=k(p^n-1)+1 < kp^n\]
and 
\[\d(G\oplus C_{p^n})=\d(G)+(p^n-1)=k(p^n-1)<|S|=|\zeta(S)|.\]
Therefore, again by Theorem \ref{dg}, there exists a subsequence $T$ of
$S$ such that $\s(\zeta(T))=0$. 
By construction $\s(T)=0$, $p^n\mid |T|$ and, since $|T|\le |S|<k p^n$,
we have $k\nmid |T|$.
\item Suppose that $(k-1)$ divides $\d(G)$. \\
By Lemma \ref{gpn} there exists a p-group $H$
and an integer $n\in\N$ such that
$\d(G\oplus H)=p^n-1$. If $ H'=G^{k-2}\oplus
H^{k-1}$, then  $\d(G\oplus H')=\d((G\oplus H)^{k-1})=(k-1)\d(G\oplus
H)=(k-1)(p^n-1)$. Since $\d(H')=\d((G\oplus H)^{k-1})-\d(G)$, we also get
$(k-1)|\d(H')$.  
From the previous step we obtain 
\[\begin{split}
& \frac{k}{k-1}\d((G\oplus H)^{k-1}) =\frac{k}{k-1}\d(G\oplus H')
=\frac{k}{k-1}\d(G)+\frac{k}{k-1}\d(H')\le\\
&  \e_k(G)+\e_k(H')\le \e_k(G\oplus H')=\e_k((G\oplus
H)^{k-1})=\frac{k}{k-1}\d((G\oplus H)^{k-1}), 
\end{split}\]
where the first inequality holds by Lemma \ref{ekast}, Theorem \ref{dg}
and the fact that $(k-1)|\d(G)$ and $(k-1)|\d(H')$.
In this chain of inequalities equality holds and therefore 
\[\e_k(G)=\frac{k}{k-1}\d(G)=\left\lfloor\frac{k}{k-1}\sum_{i=1}^r
(n_i-1)\right\rfloor.\]
\item Assume to the contrary that $\left\lfloor\frac{k}{k-1}\sum_{i=1}^r
(n_i-1)\right\rfloor+1\le \e_k(G)$.\\
Since $k-1$ divides $(k-1)\d(G)=\d(G^{k-1})$, we obtain by the previous
step and Lemma
\ref{ek12}:
\[
\begin{split}
& k\,\d(G)= \\
&  (k-1)(\frac{k}{k-1}\d(G)-1)+(k-1)<(k-1)
\left\lfloor\frac{k}{k-1}\d(G)\right\rfloor
+(k-1)= \\
&  (k-1)(\left\lfloor\frac{k}{k-1}\d(G)\right\rfloor
+1)=(k-1)(\left\lfloor\frac{k}{k-1}\sum_{i=1}^r
(n_i-1)\right\rfloor+1)\le \\
& (k-1)\e_k(G)\le \e_k(G^{k-1})= k\,\d(G), 
\end{split}\]
a contradiction. Therefore we have
$\e_k(G)\le\left\lfloor\frac{k}{k-1}\sum_{i=1}^r (n_i-1)\right\rfloor$.
\end{enumerate} 
\end{proof}





\begin{thebibliography}{99}

\bibitem{ad}
\textsc{N. Alon and M. Dubiner}, Zero-sum sets of prescribed size, in: 
\textsl{Combinatorics, Paul
Erd\H{o}s is Eighty}, Vol. 1, J. Bolyai Math. Soc., 1993, 33-50.





\bibitem{car}
\textsc{Y. Caro}, Remarks on a Zero-Sum Theorem,
\textsl{J. Combin. Th. Ser. A}, \textbf{76} (1996), 315-322.

\bibitem{emde}
\textsc{P. van Emde Boas}, A combinatorial problem on finite abelian
groups II,  \textsl{Report ZW-1969-007, Math. Centre, Amsterdam}.

\bibitem{egz} \textsc{P. Erd\H{o}s,
A. Ginzburg and A. Ziv}, A theorem in additive number theory, 
\textsl{Bull. Research Council Israel} \textbf{10F} (1961), 41-43. 



\bibitem{gao4} \textsc{W. D. Gao}, A Combinatorial Problem on Finite
Abelian Groups, \textsl{J. Number Th.} \textbf{58} (1996), 100-103.


\bibitem{gao1} \textsc{W. D. Gao}, On zero-sum subsequences of restricted
size, \textsl{J. Number Th.} \textbf{61} (1996), 97-102.

\bibitem{gao2} \textsc{W. D. Gao}, On zero-sum subsequences of restricted
size II.


\bibitem{gao3} \textsc{W. D. Gao}, On zero-sum subsequences of restricted
size III, \textsl{Ars Combinatoria}.


\bibitem{gg} \textsc{W. D. Gao and A. Geroldinger}, On Long Minimal Zero
Sequences in Finite Abelian Groups, \textsl{Periodica Mathematica
Hungarica} \textbf{38 (3)} (1999), 179-211.


\bibitem{ge94} \textsc{A. Geroldinger}, The Cross Number of Finite
Abelian Groups, \textsl{J. Number Th.} \textbf{48} (1994), 219-223.


\bibitem{gs96} \textsc{A. Geroldinger and R. Schneider}, The cross number
of finite abelian groups III, \textsl{Discrete Mathematics} \textbf{150}
(1996), 123-130.  


\bibitem{hk} \textsc{F. Halter-Koch}, A Generalisation of Davenport's
Constant and its Arithmetical Applications, \textsl{Colloquium
Mathematicum}  \textbf{63} (1992), 203-210. 


\bibitem{hoo} \textsc{Y. O. Hamidoune, O. Ordaz and A. Ortunio}, On a
Combinatorial Theorem of Erd\H{o}s, Ginzburg and Ziv,
\textsl{Combinatorics, Probability and Computing} \textbf{7} (1998),
403-412.


\bibitem{har} \textsc{H. Harborth}, Ein Extremalproblem f\"ur
Gitterpunkte, \textsl{J. Reine Angew. Math.} \textbf{262/263} (1973),
356-360.




\bibitem{kem} \textsc{A. Kemnitz}, On a lattice point problem, \textsl{Ars
Combinatoria} \textbf{16-B} (1983), 151-160.




\bibitem{ols1} \textsc{J. E. Olson}, A combinatorial problem on finite
abelian
groups, I, \textsl{J. Number Th.} \textbf{1} (1969), 8-10.


\end{thebibliography}


\end{document}