%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}