\documentclass[12pt]{article} \usepackage{e-jc} \specs{P1.17}{24(1)}{2017} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \def\|{\Big |} \def\({\Big (} \def\){\Big )} \def\[{\Big[} \def\]{\Big]} \def\be{\begin{equation}} \def\bel{\begin{equation}\label} \def\ee{\end{equation}} \def\bt{\begin{theorem}} \def\bcd{\begin{condition}} \def\ecd{\end{condition}} \def\et{\end{theorem}} \def\bc{\begin{corollary}} \def\ec{\end{corollary}} \def\bde{\begin{definition}} \def\ede{\end{definition}} \def\bl{\begin{lemma}} \def\el{\end{lemma}} \def\bp{\begin{proposition}} \def\ep{\end{proposition}} \def\br{\begin{remark}} \def\er{\end{remark}} \def\ba{\begin{array}} \def\ea{\end{array}} \def\ed{\end{document}} \def\pmod #1{\ ({\rm{mod}}\ #1)} \def\Z{\Bbb Z} \def\N{\Bbb N} \def\G{\Bbb G} \def\Q{\Bbb Q} \def\zp{\Z^+} \def\R{\Bbb R} \def\C{\Bbb C} \def\F{\Bbb F} \def\r{\right} \def\bg{\bigg} \def\t{\text} \def\f{\frac} \def\mo{{\rm{mod}\ }} \def\lcm{\rm{lcm}} \def\ord{{\rm ord}} \def\exp{{\rm exp}} \def\sgn{{\rm sgn}} \def\cs{\ldots} \def\ov{\overline} \def\ls{\leqslant} \def\gs{\geqslant} \def\se {\subseteq} \def\sm{\setminus} \def\bi{\binom} \def\al{\alpha} \def\be{\beta} \def\ga{\gamma} \def\ve{\varepsilon} \def\lr{\Leftarrow} \def\ra{\rightarrow} \def\Lr{\leftrightarrow} \def\ar{\Rightarrow} \def\Ar{\Leftrightarrow} \def\eq{\equiv} \def\Da{\Delta} \def\da{\delta} \def\la{\lambda} \def\La{\Lambda} \def\ta{\theta} \def\AP{\rm{AP}} \def\va{\varphi} \def\supp {\rm supp} \def\colon{{:}\;} \def\mod #1{\ {\rm mod}\ #1} \def\ord{{\rm ord}} \def\floor #1{\lfloor{#1}\rfloor} \def\ceil #1{\left\lceil{#1}\right\rceil} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf On a permutation problem\\ for finite abelian groups} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Fan Ge\\ \small Department of Mathematics \\[-0.8ex] \small University of Rochester\\[-0.8ex] \small Rochester, NY-14627, USA\\ \small\tt fange.math@gmail.com\\ \and Zhi-Wei Sun\thanks{Supported by the National Natural Science Foundation (grant 11571162) of China.}\\ \small Department of Mathematics\\[-0.8ex] \small Nanjing University\\[-0.8ex] \small 210093, People's Republic of China\\ \small\tt zwsun@nju.edu.cn } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Feb 4, 2016}{Jan 19, 2017}{Feb 3, 2017}\\ \small Mathematics Subject Classifications: 05E15, 11B75, 11A07, 11P70, 20K01.} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} Let $G$ be a finite additive abelian group with exponent $n>1$, and let $a_1,\ldots,a_{n-1}$ be elements of $G$. We show that there is a permutation $\sigma\in S_{n-1}$ such that all the elements $sa_{\sigma(s)}\ (s=1,\ldots,n-1)$ are nonzero if and only if $$\left|\left\{1\ls s1$ is an integer and $m_1,\ldots,m_k$ are integers with $k\ls n-1$ then there is a permutation $\sigma\in S_k$ such that $1+m_{\sigma(1)},\ldots,k+m_{\sigma(k)}$ are pairwise distinct modulo $n$. This was confirmed by A. E. K\'ezdy and Snevily \cite{KS} in the case $k\ls(n+1)/2$, and an application to tree embeddings was also given in \cite{KS}. Let $n>1$ and $m_1,\ldots,m_{n-1}$ be integers. When is there a permutation $\sigma\in S_{n-1}$ such that none of the $n-1$ numbers $sm_{\sigma(s)}\ (s=1,\ldots,n-1)$ is congruent to $0$ modulo $n$? If there is such a permutation $\sigma$, then for each positive divisor $d$ of $n$ we have $$|\{1\ls c1$ be an integer. If $m_1,m_2,\ldots,m_{n-1}$ are integers satisfying $(\ref{1.1})$, then there exists a permutation $\sigma$ on $\{1,\ldots,n-1\}$ such that $n\nmid sm_{\sigma(s)}$ for all $s=1,\ldots,n-1$. \end{conjecture} In this paper we aim to prove an extension of this conjecture for finite abelian groups. For a finite multiplicative group $G$, its exponent $\exp(G)$ is defined to be the least positive integer such that $x^n=e$ for all $x\in G$, where $e$ is the identity of $G$. For a finite abelian group $G$, $\exp(G)$ is known to be $\max\{o(x):\ x\in G\}$, where $o(x)$ denotes the order of $x$. If $G$ is an additive group, then for $k\in\Z^+$ and $a\in G$ we write $ka$ for the sum $a_1+\ldots+a_k$ with $a_1=\cdots=a_k=a$. \begin{theorem}\label{Th1.1} Let $G$ be a finite additive abelian group with exponent $n>1$. For any $a_1,\ldots,a_{n-1}\in G$, there is a permutation $\sigma\in S_{n-1}$ such that all the elements $sa_{\sigma(s)}\ (s=1,\ldots,n-1)$ are nonzero if and only if \begin{align}\label{1.2} \left|\left\{1\ls s1)$ be integers satisfying $(\ref{1.1})$. Then the set $$\left\{\sum_{i\in I}m_i:\ I\se\{1,\ldots,n-1\}\r\}$$ contains a complete system of residues modulo $n$. \end{theorem} Obviously Theorem \ref{Th1.2} extends the following result of the second author (cf. the paragraph following \cite[Theorem 2.5]{S03}). \begin{corollary}\label{cor1.1} Let $n>1$ be an integer and let $m_1,m_2,\ldots,m_{n-1}$ be integers all relatively prime to $n$. Then the set $\left\{\sum_{i\in I}m_i:\ I\se\{1,\ldots,n-1\}\r\}$ contains a complete system of residues modulo $n$. \end{corollary} As usual, for any $a\in\Z$ and $n\in\Z^+$, we write $(a,n)$ for the greatest common divisor of $a$ and $n$. Let $n>1$ be an integer. If $m_s\in\Z$ and $(m_s,n)\ls s$ for all $s=1,\ldots,n-1$, then for any $d\in D(n)$ we have $$|\{1\ls s1)$ be integers with $(m_s,n)\ls s$ for all $s=1,\ldots,n-1$. For any $a_1,\ldots,a_{n-1}\in\Z$, there is a function $f:\{1,\ldots,n-1\}\to\{1,\ldots,n-1\}$ such that the sums $$f(1)+a_1,\ \ldots,\ f(n-1)+a_{n-1}$$ are pairwise distinct modulo $n$ and also none of the numbers $$f(1)m_1,\ \ldots,\ f(n-1)m_{n-1}$$ is divisible by $n$. \end{theorem} Motivated by Theorems \ref{Th1.1} and \ref{Th1.2}, we pose the following conjecture. \begin{conjecture}\label{conj1.2} Let $G$ be a finite abelian group with exponent $n>1$. If $a_1,\ldots,a_{n-1}$ are elements of $G$ with $sa_s\not=0$ for all $s=1,\ldots,n-1$, then we have \begin{equation}\bg|\bg\{\sum_{i\in I}a_i:\ I\se\{1,\ldots,n-1\}\bg\}\bg|\gs n. \end{equation} \end{conjecture} By Theorems \ref{Th1.1} and \ref{Th1.2}, this conjecture holds for finite cyclic groups. For any finite abelian group $G$ with exponent $n>1$, it has a cyclic subgroup $H$ of order $n$, and hence for $a_1,\ldots,a_{n-1}\in H$ the set $\{\sum_{i\in I}a_i:\ I\se\{1,\ldots,n-1\}\}$ contains at most $n$ elements of $G$. We will prove Theorem \ref{Th1.1} in the next section and Theorems \ref{Th1.2} and \ref{Th1.3} in Section 3. \section{Proof of Theorem \ref{Th1.1}} \begin{proof}[Proof of Necessity] If there is a permutation $\sigma\in S_{n-1}$ such that $sa_{\sigma(s)}\not=0$ for all $s=1,\ldots,n-1$, then for any $d\in D(n)$ we have $$\left|\left\{1\ls s1$ and $(n/d)x\not=0$. As $o(a_{\sigma(j)})\mid j$, we have $o(a_{\sigma(j)})\ls j\sum_{s=1}^{n-1}o(a_s)$, by our choice of $a_1,\ldots,a_{n-1}$, for some $\tau\in S_{n-1}$ we have $sa_{\tau(s)}^*\ne 0$ for all $s=1,\ldots,n-1$. For any $1\ls si=i_{\sigma}$. Suppose that $j$ is not divisible by $i$. Then $k:=(i, j)i$. For any $s=1,\ldots,n-1$ with $s\not=i,j,k$, we have $sa_{\sigma*(kij)(s)}=sa_{\sigma(s)}\not=0$. Note that $ia_{\sigma*(kij)(i)}=ia_{\sigma(j)}\not=0$. If $0\ne ja_{\sigma(k)}=ja_{\sigma*(kij)(j)}$, then we must have $I(\sigma*(kij))=\{k\}$ and hence $i_{\sigma*(kij)}=kk_i$ for $i=1,\ldots,n$ where $k_1,\ldots,k_n$ are nonnegative integers. If the coefficient of the monomial $x_1^{k_1}\cdots x_n^{k_n}$ in $P(x_1,\ldots,x_n)\in F[x_1,\ldots,x_n]$ is nonzero and $k_1+\cdots+k_n$ is the total degree of $P$, then there are $a_1\in A_1,\ldots,a_n\in A_n$ such that $P(a_1,\ldots,a_n)\not=0$. \end{lemma} \begin{proof}[Proof of Theorem~\ref{Th1.3}] Let $p$ be the smallest prime not dividing $n$. By Euler's theorem, $p^{\varphi(n)}\eq1\pmod n$, where $\varphi$ denotes Euler's totient function. Let us consider the finite field $\mathbb F_q$ with $q=p^{\varphi(n)}$. As $\mathbb F_q^*=\mathbb F_q\sm\{0\}$ is a cyclic group of order $q-1$, and $n$ is a divisor of $q-1$, there is an element $g\in \mathbb F_q^*$ of order $n$. For $i=1,\ldots,n-1$ define $$A_i:=\{g^k:\ 1\ls k\ls n-1\ \mbox{and}\ (g^k)^{m_i}\not=1\}.$$ Then $|A_i|=n-(m_i,n)\gs n-i$ for all $i=1,\ldots,n-1$. For the polynomial $$P(x_1,\ldots,x_{n-1}):=\prod_{1\ls i