%Here is the paper. This is unchanged from the version you %sent me Feb 10 1993, except for 3 typos fixed, and: %You'd said the referees wanted to get motivated. %In the .ps file I sent you this morning is (among other things) my %original motive for %looking at this subject. But as you can see, it is not so %clear how to summarize that succinctly! So I have contented myself %with the following: 1. I have cited the ``applications of Sk sets'' %papers earlier to thrust that in front of the ref's noses, 2. I have %put a sentence or two to motivate the open problems at the end. % Frankly, I think this is a very well done, though small, paper, %and I cant see what grounds there are to complain about it, %sort of embarrassing, but there you have it. Feel free to complete %the modifications if any, abuse me further, and/or send it off. % - cheers... Warren. \documentstyle[11pt]{article} \input amssym.def \input amssym.tex \setlength{\textwidth}{6.2in} \setlength{\textheight}{9in} \setlength{\oddsidemargin}{.2in} \setlength{\topmargin}{-0.25in} \setlength{\headheight}{0in} \newcommand{\eqn}[1]{(\ref{#1})} \newcommand{\vsp}{\vspace{.1in}} \newcommand{\hsp}{\hspace*{\parindent}} \newcommand{\beql}[1]{\begin{equation}\label{#1}} \newcommand{\eeq}{\end{equation}} \renewcommand{\theequation}{\arabic{section}.\arabic{equation}} \catcode`\@=11 \renewcommand{\section}{ \setcounter{equation}{0} \@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus -.2ex}{2.3ex plus .2ex}{\large\bf} } \catcode`@=12 \makeatletter \def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth \def\@svsec{}\else \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi \@tempskipa #5\relax \ifdim \@tempskipa>\z@ \begingroup #6\relax \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}% \endgroup \csname #1mark\endcsname{#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}\else \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname {#7}\addcontentsline {toc}{#1}{\ifnum #2>\c@secnumdepth \else \protect\numberline{\csname the#1\endcsname}\fi #7}}\fi \@xsect{#5}} \def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]} \makeatother \newtheorem{defn}{Definition} \newtheorem{theo}{Theorem} \newcommand{\ro}{\mbox} \thispagestyle{empty} \begin{document} \begin{center} {\Large {\bf Nonabelian sets with distinct $k$-sums}} \\ \vspace{\baselineskip} {\em Andrew M. Odlyzko} \\ \vspace{0.5\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ (Email: {\tt amo@research.att.com}) \\ \vspace{\baselineskip} {\em Warren D. Smith} \\ \vspace{0.5\baselineskip} NEC \\ 4 Independence Way \\ Princeton, New Jersey 08540 \\ (Email: {\tt wds@research.nj.nec.com}) \\ \vspace{1.5\baselineskip} {\bf ABSTRACT} \vspace{.5\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} \hspace*{.25in} A modified Bose-Chowla construction of sets with distinct sums of $k$-element subsets is presented. In infinitely many cases it yields sets with a certain multiplicative symmetry. These sets are then used to construct large sets $S$ in certain nonabelian groups with the property that all $k$-letter words with letters from $S$ are distinct. \vspace{.5in} \begin{list} {}{\setlength{\leftmargin}{.8in}\setlength{\labelwidth}{0.8in} \setlength{\labelsep}{.1in}\hfill} \item[{Keywords:}] $S_k$-sets, sets with distinct sums, additive basis, groups, combinatorics. \end{list} \clearpage \large\normalsize \newcommand{\af}{\alpha} \renewcommand{\baselinestretch}{1} \thispagestyle{empty} \setcounter{page}{1} \begin{center} {\Large {\bf Nonabelian sets with distinct $k$-sums}} \\ \vspace{\baselineskip} {\em A. M. Odlyzko} \\ \vspace{0.5\baselineskip} AT\&T Bell Laboratories \\ Murray Hill, New Jersey 07974 \\ \vspace{\baselineskip} {\em W.~D. Smith} \\ \vspace{0.5\baselineskip} NEC \\ 4 Independence Way \\ Princeton, New Jersey 08540 \\ \vspace{1.5\baselineskip} \end{center} \setlength{\baselineskip}{1.5\baselineskip} \section{Introduction} \hsp {\em Sets with distinct $k$-sums} are (hopefully large) sets $S$ such that all sums of $k$ elements selected from $S$ are distinct. (For short, we will call such sets {\em $S_k$-sets.}) In the past, interest has generally been focused on such sets inside of $Z_m$ (that is, the {\em sum} is evaluated modulo $m$). Most of the applications still work if $S$ and the $+$ operation live inside any abelian group. In some cases, larger sets $S$ may be found inside such groups than exist in the cyclic group of the same order. $S_k$-sets have many uses in combinatorics \cite{Chun89,Klov81,Grah80,BSSS90}. We first show that for each $k \ge 2$, an infinite number of values $m$ exist so that a set $S$ with distinct $k$-sums exists inside $Z_m$, where $|S|^k > m$, and such that these sets $S$ enjoy a {\em multiplicative symmetry} modulo $m$. (These sets are a slight variant of a well-known construction. What is new is that our modification gives sets with multiplicative symmetries.) Second, we extend the $S_k$-set notion to nonabelian groups $G$. We prove that for each value of $k = 2 , 3, \dots$, an infinite number of groups $G$ exist, such that there is a set $S$ inside $G$ with $|G|^{1/k} = O( |S| k )$ and such that all $k$-letter words whose letters are in $S$ are distinct in $G$. These sets arose in connection with the second author's ongoing work on maximal number of edges in graphs of small girth. \begin{defn}\label{de1} {\rm {\em Perfect difference sets} are sets $S$, $S \subset Z_m$, where $Z_m$ is the additive abelian group of integers modulo $m$, such that every nonzero integer modulo $m$ has a unique representation as a difference $a-b$ mod $m$, $a \in S$, $b \in S$. } \end{defn} In 1938, James Singer (\cite{Sing38}, \cite{Hall86}, \cite{Sing65}) constructed perfect difference sets for $|S| = q$, $q$ any prime power. So far, Singer's construction is the only construction (up to obvious isomorphisms) that has ever been found for perfect difference sets. It is not known whether perfect difference sets exist that are not of Singer's type. Marshall Hall found that Singer's sets, as well as all known generalized difference sets (that is, in which each nonzero element of $Z_m$ is represented in $\lambda$ [a constant] number of ways as a difference of two elements in $S$) always possess isomorphs exhibiting {\em multiplicative symmetries}. That is, multiplying $S$ by some integer $t$ (modulo $m$) leaves it invariant. Indeed, Hall observes \cite{Hall86} that for every known generalized difference set, any prime $t$ such that $\ro{gcd}(m,t)=1$ and $t | (|S|-\lambda )$ gives rise to a multiplicative symmetry. For example, with $q = 2$, $m = 7$, the set $S = \{ 1, 2, 4 \}$ is a perfect difference set featuring the multiplicative symmetry $S = 2S$. With $q = 3$, $m = 13$, the set $S = \{ 0 , 1 , 3 , 9 \}$ is a perfect difference set featuring the multiplicative symmetry $S = 3S$. This phenomenon was partially explained by Hall and Ryser's {\em multiplier theorem} \cite[Theorem~11.4.1, p.~160 and Theorem~11.15.2, p.~166]{Hall86}. Perfect difference sets may be generalized in the following two ways. First, we may consider replacing $Z_m$ by an arbitrary abelian group. (As motivation, we mention that, as was observed in \cite{BSSS90}, there is an $S_2$-set of size 7 inside $G= Z_2^3 \times Z_3$, $|G|=24$. The least $m$ so that an $S_2$=set of size 7 exists inside $Z_m$ is 48 \cite{Grah80A}.) Secondly, we note that the sums of two elements in $S$ are distinct if and only if the differences of elements in $S$ are distinct, since $a + b = c + d$ if and only if $a-d = c-b$, which suggests the generalization of letting there be more than two elements in the sum: \begin{defn}\label{de2} {\rm {\em $S_k$-sets} are sets $S \subset G$, where $G$ is any abelian finite group, such that the sum of any $k$ elements selected (with replacement) from $S$ is not equal to the sum of any other $k$ elements of $S$. } \end{defn} Thus $S_2$-sets in $G = Z_m$, if $m = |S|^2 - |S|+1$, are precisely the perfect difference sets. Applications of $S_k$-sets may be found in \cite{Chun89,Klov81,Grah80,BSSS90}. How large can an $S_k$-set be, compared to the size of the containing group $G$? Obviously \beql{eq101} |G| \ge \frac{|S| (|S|+1) \dots (|S|+k-1)}{k!} , \eeq since the right-hand side is the number of ways to choose (a multiset of) $k$ elements from $S$, with replacement. Thus when $|G|$ is large and $k$ is fixed, we have \beql{eq102} |S| \precsim ( k! |G| )^{1/k} ~. \eeq An upper bound with better asymptotic behavior is \beql{eq103} |G| \ge \frac{\prod\limits_{i=0}^{\lfloor k/2 \rfloor} (|S|-\lceil k/2 \rceil+i) \cdot \prod\limits_{j=0}^{\lceil k/2 \rceil} (|S|+j)} {\lfloor k/2 \rfloor ! \cdot \lceil k/2 \rceil !} ~. \eeq This arises as follows. Choose $\lfloor k/2 \rfloor$ elements with replacement from $S$, and let their sum be $A$. From the remaining $ \ge |S| - \lfloor k/2 \rfloor$ elements, choose $\lceil k/2 \rceil$ elements, and let their sum be $B$. Then the differences $A-B$ are distinct, and their number is bounded below by the quantity on the right hand side of \eqn{eq103}. When $|G|$ is large and $k$ is fixed, this leads to \beql{eq104} |S| \precsim ( \lfloor k/2 \rfloor ! \cdot \lceil k/2 \rceil ! \cdot |G| )^{1/k} ~. \eeq When $k = 2$, Singer's construction, known results on prime gaps, and this upper bound are sufficient to determine the asymptotics of the minimal order $\nu ( n )$ of an abelian group $G$ containing an $S_2$-set of cardinality $n$: \beql{eq105} \nu (n) \sim n^2 ~. %To be stronger, n^2 - n^{36/23} < \nu(n) < n^2 + O(n). \eeq This observation settles an open problem mentioned in \cite[p.~1343]{BSSS90}. R.C. Bose and S. Chowla \cite{Bose62} constructed $S_k$-sets of cardinality $q+1$, where $k = 2 , 3 , 4 , \dots$ and $q$ is any prime power, inside $Z_m$, where $m = \frac{q^{k+1} - 1}{q-1}$. These specialize to Singer's sets when $k=2$. They also constructed $S_k$-sets of cardinality $q$, where $k = 2 , 3 , 4 , \dots$ and $q$ is any prime power, inside $Z_m$, where $m = q^k - 1$. Observe that in the limit when $k \ge 3$ is fixed and $|G|$ is large, Bose and Chowla's $S_k$-sets are only a constant factor ($\approx \frac{k}{2e}$, if $k$ is large, where $e \approx 2.71828$ is Euler's constant) smaller than the asymptotic upper bound \eqn{eq104}. When $k \ge 3$, however, Bose and Chowla's sets are not necessarily {\it exactly} optimal. \begin{itemize} \item Example: Bose and Chowla supply a 6-element $S_3$-set inside $Z_{156}$, but there is a 8-element $S_3$-set in $Z_{156}$: $S = \{ 1 , 5 , 25 , 125 \} \cup \{ 2 , 10 , 50 , 94 \}$. \item Example: Bose and Chowla supply a 5-element $S_3$-set inside $Z_{124}$, but there is a 6-element $S_3$-set in $Z_{124}$: $S = \{ 1 , 5 , 25 \} \cup \{ 2 , 10 , 50 \}$. \end{itemize} Also note that both these examples have a multiplicative symmetry $S = 5S$. In the present paper, we will observe that in an infinite number of cases some isomorph of Bose and Chowla's second type of set possesses a multiplicative symmetry. \begin{theo}\label{th1} For every integer $k \ge 2$ and every prime $p$ so that $k | (p-1)$, there exists an $S_k$-set $S$ of cardinality $p$ inside $Z_m$, where $m = p^k - 1$, such that $S = p S$. \end{theo} Next, we will extend the $S_k$-set notion to nonabelian groups $G$. \begin{defn}\label{de3} {\rm A {\em nonabelian $S_k$-set} is a set $S \subset G$, where $G$ is a (nonabelian) finite group, such that all $k$-letter words, whose letters are selected (with replacement) from $S$, are distinct in $G$. } \end{defn} Notice that any $S_k$-set, including a nonabelian one, is also an $S_j$-set for every $j = 1 , 2 , \dots k$. (Proof: consider appending a $(k-j)$-letter constant suffix to the end of the $j$-letter words.) We prove the following result. \begin{theo} \label{th2} For each value of $k = 2 , 3, \dots$, and any prime $p$ with $k | (p-1)$, a nonabelian group $G$ of order $|G|= (p^k - 1) k$ exists which contains a nonabelian $S_k$-set $S$ of cardinality $(p-1)/k$. \end{theo} %If k prime, then equiv classes must be of size k or 1. %And 1 can happen only if (from AMO pf) 2 linear eqns satisfied by 2 %variables b and c... which means only 1 solution... hence there is only 1 %equiv class of size 1. Analogously to \eqn{eq101}, one easily sees that any nonabelian $S_k$-set $S$ inside a group $G$ must obey \beql{eq106} |S| \le |G|^{1/k} , \eeq so the construction of Theorem~\ref{th2} comes within a constant factor (in the asymptotic regime where $k$ is fixed and $|G|$ is large) of this upper bound. When $k$ is large, this constant factor is approximately $k$. We can do better if $k=2$ and if we do not require that words $a^2$ be distinct (or equivalently, if we remove the words {\em with replacement} from Definition \ref{de3}): \begin{theo} \label{th3} Let $q$ be a prime power. Then there exists a set $S$ of cardinality $q+2$ inside the dihedral group $D_{2m}$ of order $2m$, where $m = ( q^3-1 ) / ( q-1 )$, such that the products $xy$ with $x,y \in S$, $x \neq y$, are distinct. (In particular, $xy \neq yx$ for $x \neq y$.) \end{theo} \noindent{\bf Proof.} Let $D_{2m}$ be generated by $r$ and $f$ where $r^m = f^2 = ( r f )^2 = 1$. Let $S$ consist of the $q+1$ elements of $D_{2m}$ of form $r^z f$ where $z$ is in Singer's perfect difference set inside $Z_m$, and 1. \hfill $\blacksquare$ \vsp \noindent{\bf Remark:} One may also construct a set $S$ of cardinality $1 + \prod_i (q_i+1)$ inside a group of order $2 \prod_i ( q_i^3-1 ) / ( q_i-1 )$ where the $q_i$ are prime powers, such that all the words $xy$, $x \neq y$, are distinct. \section{$S_k$-sets with multiplicative symmetries} \hsp In this section we prove Theorem~\ref{th1}. We modify the Bose-Chowla construction \cite{Bose62,Halb66}. Let $g$ be a primitive element of $GF(p^k)$ (i.e., an element of multiplicative order $p^k -1$). The discrete logarithm of $y \in GF(p^k)$, $y \neq 0$, is an integer $\ell$, taken as an element of $Z_m$, $m= p^k -1$, such that $y=g^\ell$. We write $\ell = \log_g y$. We will often use the bijection between $Z_m$ and $GF(p^k) \setminus \{0\}$ given by the discrete logarithm. As in the Bose-Chowla construction, choose $x \in GF(p^k)$ so that $x$ is of degree $k$ over $GF(p)$, and is thus not in any proper subfield of $GF(p^k)$. For a fixed $b \in Z_m$, we let \beql{eq201} S = \{ \log_g (x+j) + b:~ 0 \le j \le p-1 \} ~. \eeq The standard Bose-Chowla construction has $b=0$. The present sets remain $S_k$-sets since the addition of a constant to all elements does not affect the $S_k$-set property. We now show that if we choose $x$ and $b$ properly, then $S$ will have the multiplicative symmetry $pS=S$. This symmetry property will hold if for every $j \in GF(p)$, there is an $h \in GF(p)$ such that \beql{eq202} p( \log_g (x+j) + b) = \log_g (x+h) +b \eeq holds in $Z_m$. Exponentiating, we find this is equivalent to the equation \beql{eq203} g^{bp} (x+j)^p = g^b (x+h) \eeq in $GF(p^k)$, which (by the ``freshman's dream'' identity $(A+B)^p \equiv A^p + B^p$ mod $p$) in turn is equivalent to \beql{eq204} x^p = g^{-b(p-1)} x + g^{-b(p-1)} h-j ~. \eeq If there are fixed $g$, $x$ and $b$ such that as $j$ varies over $GF(p)$, the $h$ defined by Eq.~\eqn{eq204} remains in $GF(p)$, then we must have \beql{eq205} \af = g^{-b(p-1)} \in GF(p) ~. \eeq Moreover, we then must have \beql{eq206} x^p = \af x + \af h-j ~. \eeq If Eq.~\eqn{eq206} holds for even a single pair $(h,j)$ with $\af \in GF(p)$, then for every $j \in GF(p)$, there will be an $h \in GF(p)$ such that Eq.~\eqn{eq206} holds, and the set $S$ will satisfy $pS=S$. Suppose that $k | (p-1)$. We will show that a suitable choice of $x$ and $\alpha$ exists so that Eq.~\eqn{eq206} holds with $h = (j+1) / \af$ for all $j$. We choose \beql{eq207} \af = g^{(p^k -1)/k} ~. \eeq We first show that $\af$ satisfies Eq.~\eqn{eq205}. To prove this, it suffices to show that $p-1$ divides $(p^k-1)/k$. This is equivalent to showing that $k$ divides $$ \frac{p^k-1}{p-1} = p^{k-1} + p^{k-2} + \dots + 1 ~. $$ However, modulo $p-1$ the sum on the right hand side above is $k$, and since $k$ divides $p-1$, we are done. We now come to the heart of the proof. Consider the equation \beql{eq208} z^p - \af z - 1 = 0~. \eeq When we factor this over $GF(p)$, we {\it claim} that it has one linear factor and $(p-1)/k$ irreducible factors, each of which is of degree $k$. If $z$ is in $GF(p)$, then $z^p = z$ by Fermat's little theorem, so \eqn{eq208} shows that $z = -1/(\af-1)$. Further, \eqn{eq208} has no multiple roots by the derivative test, so we have established the claimed result about linear factors. Suppose now that $z$ is a root of \eqn{eq208} but $z$ is not in $GF(p)$. The conjugates of $z$ are $z^p$, $z^{p^2}$, $z^{p^3}$,.... We find that \beql{eq209} z^{p^2} = ( \af z + 1 )^p = \af z^p + 1 = \af^2 z + \af + 1~. \eeq An easy induction establishes the more general relation \beql{eq210} z^{p^r} = \af^r z+ \frac{\af^r - 1}{\af - 1} ~. \eeq Since $\af$ is a primitive $k$th root of unity, we find that $z^{p^\mu} = z$ for $\mu = k$, but for no smaller positive $\mu$. Hence $z$ is of degree $k$ over $GF(p)$, and our {\em claim} is now proved. We have shown that for $k|(p-1)$, if we select $\af$ according to \eqn{eq207}, then there will be an $x$ satisfying \eqn{eq208} such that the set $S$ will have the multiplicative symmetry $pS=S$. \hfill $\blacksquare$ We now mention some further consequences of the above proof. 1. The mapping $x \to px$ of our set $S$ to itself consists of one fixed point and $(p-1)/k$ orbits of length $k$. To see this, note that for $x$ and $\af$, $\af \ne 0$, fixed, $$ \af h - j = x^p - \af x = 1 $$ has exactly one solution $(h,j)$ with $h = j$, namely $h = j = 1/(\af-1)$, corresponding to the fixed point. There cannot be orbits of length $r$, $2 \le r < k$, since that would imply $$h = \af^r h - \frac{\af^r - 1}{\af - 1}$$ so that (we are allowed to divide out the factor of $\af^r-1$, since it is nonzero, since $\af$ is a primitive $k$th root of unity) $h = 1/(\af - 1)$, but that was the fixed point. \hfill $\blacksquare$ 2. Our construction requires that $k | (p-1)$. Conversely, one can show that if Eq.~\eqn{eq206} is satisfied for any $h$ and $j$, and some $\af \in GF(p)$, with $x$ of degree $k$ over $GF(p)$, then $k|(p-1)$. 3. The value of the {\em offset} $b$ may be deduced, from Eqs.~\eqn{eq205}, \eqn{eq207}, and the fact that $\alpha$ is a primitive $k$th root of unity, to be \beql{eq211} b = \frac{(p^k-1)(k-1)}{(p-1)k} . \eeq 4. The symmetric $S_k$-sets in $Z_m$ which arise in this construction will remain symmetric $S_k$-sets if any multiple of $m/k$ is added to each element, or equivalently to $b$. In practice, to construct the set $S$, we would select $\af$ to be any element of $GF(p) \setminus \{0\}$ of multiplicative order $k$, and let $f(X)$ be one of the irreducible factors of degree $k$ of $X^p - \af X -1$ over $GF(p)$. The field $GF(p^k)$ would then be represented as $GF(p) [X] /(f(X))$, with $x$ the image of $X$, and $g$ would be a $((p^k -1)/k)$-th root of $\af$ generating $GF(p^k)$. We now give an example to illustrate the construction procedure. Let $p=11$ and $k=5$. Note $5 | (11-1)$. The prime factorization of $m = 11^5-1 = 161050$ is $2 \cdot 5^2 \cdot 3221$. We select $\alpha=9$ since $9^5 \equiv 1$ mod $11$. The factorization of $x^{11} - 9x - 1$ over $GF(11)$ is \beql{eq212} (7+x) (2+4x+9x^2 + 6x^3 +2x^4 + x^5) (7+4x+9x^2 + 6x^3 +2x^4 + x^5) . \eeq We will therefore use $f(x) = 2+4x+9x^2 + 6x^3 +2x^4 + x^5$. A suitable $g$, which is a $32210$th root of $9$ (modulo $F$ and modulo $11$), is $g = 2 + x^2$. The fact that this $g$ is a generator (as opposed to just being any old $32210$th root of 9) may be verified by observing that none of $g^{5 \cdot 5 \cdot 2} = 2 x + 6 x^2 + 4 x^3 + 10 x^4$, $g^{3221 \cdot 5 \cdot 2} = 9$, and $g^{3221 \cdot 5 \cdot 5} = 4$ are 1. We find Eq.~\eqn{eq211} that $b = 12884$. Then $\log_g(x+7)=3221$, $\log_g(x+0)=30542$, $\log_g(x+6)=70549$, and so on, as are easily verified, so that, upon adding $b$ to these values, we arrive finally at the sought-after $S_5$-set modulo $161050$: \beql{eq213} \{ 16105 \} \cup \{ 43426 ,\, 83433 \} \times \{ 1 ,\, 11 ,\, 11^2 ,\, 11^3 ,\, 11^4 \} . \eeq Note that the complicated steps here were the selection of $g$ and the discrete logarithm calculations. (Both of these computations are of course easy to verify by binary powering, but it is not immediately clear how to do them.) Selecting $g$ is actually quite efficiently accomplished by random trial. The probability that a random nonzero element of $GF(p^k)$ is a generator is $\phi ( m ) / m$, where $\phi$ is Euler's totient function and $m = p^k -1$, and the probability that a random generator $g$ will obey $g^{m/k} = \alpha$ is $1/k$. The combined probability $\phi(m) / (mk)$ (which in the present case is $1288/16105 \approx 0.08$) is of order at least $1/(k^2 \log p)$. The discrete logarithms are certainly the computational bottleneck. In small cases such as this one, exhaustive search suffices. For larger values of $m = p^k-1$, one can use the polynomial factorization algorithms in \cite{Gedd92} and discrete logarithm algorithms in \cite{McCu90,Odly85}. \section{Large nonabelian $S_k$-sets} \hsp In this section we prove Theorem~\ref{th2}. The group is the following group of permutations of $m = p^k - 1$ letters: \beql{eq301} \begin{array}{c} x \to x + a \bmod m , ~ a = 0..m-1 , ~ \mbox{{\em rotations}} \\ x \to xp + a \bmod m , ~ \mbox{{\em scramblings}} \end{array} \eeq and the permutations they generate, namely \beql{eq302} x \to xp^e + a \bmod m , ~ (e=0..k-1 , a = 0..m-1) ~. \eeq We observe that \begin{itemize} \item The group has order $k m$. \item The $k$th power of a scrambling is a rotation (since $p^k \equiv 1$ mod $m$). \end{itemize} Note that the composition of $k$ scramblings with $a$-values $a_1$, $a_2$, $a_3$,... $a_k$ is the following permutation: \beql{eq303} x \rightarrow x p^k + ( a_1 p^{k-1} + a_2 p^{k-2} + \dots + a_k ) \eeq which is actually a rotation since $p^k=1$ mod~$m$. (It is not the identity, however, unless $a_1 = a_2 = \dots = a_k \in \{ 0 , p-1 \}$.) Let $T$ be an ordinary abelian $S_k$-set of cardinality $p$, inside $Z_m$ constructed in Theorem~\ref{th1}, and having the multiplicative symmetry $Tp = T$. Then divide $T$ into $(|T|-1)/k$ equivalence classes of size $k$ (also called {\em orbits}) under this symmetry plus a singleton. Then let $S$ be the scramblings with $a$'s consisting of one representative from each cardinality-$k$ equivalence class. The reason this set $S$ works is that $a_i p^{k-i}$ is also an element of $T$ due to the multiplicative symmetry, so that the rotation length in \eqn{eq303} is a sum of $k$ elements of $T$, so these are distinct -- except for the possibility of two such sums being the same sum in a different order, which cannot happen since we have picked one representative from each equivalence class. \hfill $\blacksquare$ \section{Open problems} \begin{enumerate} \item Understand the multiplicative symmetries of $S_k$-sets in $Z_m$. \item Here are two alternative ways to define {\em nonabelian $S_k$-sets} $S$ inside a nonabelian group $G$. \begin{itemize} \item Consider the $2k$-letter words whose letters are alternately in $S$ and in $S^{-1}$, and where we only allow words such that no letter is adjacent to its inverse. We require that none of these words are the identity. \item Consider the $\ell$-letter words $w$ whose letters lie in $S$ or $S^{-1}$. Again, no letter of $w$ is allowed to be adjacent to its inverse. We require that none of these words are the identity. \end{itemize} Can large nonabelian $S_k$-sets of these two types be constructed? If these problems are solved, then one will have also made progress on an open problem in graph theory, the problem of finding the graphs of fixed girth $g > 2k$ and having the most edges. Specifically, Cayley graphs and bipartite doubles of Cayley graphs constructed using generators from $S$ will have large girths. \end{enumerate} \clearpage \begin{thebibliography}{BSSS901} \bibitem{Bond76} J.~A. Bondy and U.~S.~R. Murty, {\em Graph theory with applications}, North-Holland, 1976. \bibitem{Bose62} R.~C. Bose and S. Chowla, Theorems in the additive theory of numbers, {\em Math. Helvet.}, 37 (1962--3) 141--147. \bibitem{BSSS90} A.~E. Brouwer, J.~B. Shearer, N.~J.~A. Sloane, and W.~D. Smith, A new table of constant weight codes, {\em IEEE Trans. Information Th.}, 36(6) (1990) 1334--1380. \bibitem{Bruk55} R.~H. Bruck, Difference sets in a finite group, {\em Trans. Amer. Math. Soc.}, 78 (1955) 464-481. \bibitem{Chun89} F.~R.~K. Chung, Diameters and eigenvalues, {\em J. AMS}, 2(2) (1989) 187--196. \bibitem{Gedd92} K.~O. Geddes, S.R. Czapor, and G. Labahn, {\em Algorithms for computer algebra}, Kluwer, 1992. \bibitem{Grah80} R.~L. Graham and N.~J.~A. Sloane, Lower bounds for constant weight codes, {\em IEEE Trans. Info. Theory}, 26 (1980) 37--43. \bibitem{Grah80A} R.~L. Graham and N.~J.~A. Sloane, On additive bases and harmonious graphs, {\em SIAM J. Algebraic \& Discr. Methods}, 1 (1980) 382--404. \bibitem{Halb66} H.~Halberstam and K.~F. Roth, {\em Sequences}, Oxford University Press, 1966. \bibitem{Hall86} Marshall Hall, Jr., {\em Combinatorial Theory}, Wiley, 1986. \bibitem{Klov81} Torliev Kl{\o}ve, A lower bound for $A(n,4,w)$, {\em IEEE Trans. Info. Theory}, 27(2) (1981) 257--258. \bibitem{Lidl83} Rudolf Lidl and Harald Niederreiter, {\em Finite Fields}, Addison-Wesley, 1983. \bibitem{McCu90} K.~S. McCurley, {\em The discrete logarithm problem}, pp. 49-74 in {\em Cryptology and computational number theory}, ed. C. Pomerance, AMS Proc. Sympos. Pure Math. \#42, 1990. \bibitem{Odly85} A.~M. Odlyzko, {\em Discrete logarithms in finite fields and their cryptographic significance}, pp. 224-314 in {\em Advances in Cryptology, Proceedings of EUROCRYPT 84}, ed. T. Beth, N. Cot, and I. Ingemarsson, Springer-Verlag Lecture Notes in Computer Science \#209, 1985. \bibitem{Sing38} James Singer, A theorem in finite projective geometry and some applications to number theory, {\em Trans. Amer. Math. Soc.}, 43 (1938) 377--385. \bibitem{Sing65} James Singer, Perfect difference sets, {\em Trans. New York Acad. Sci.}, (2) 28 (1965/6) 883--888. \end{thebibliography} \end{document}