The word cyclotomy (German, "Kreistheilung") means "circle-division" and refers to the problem of dividing the circumference of the unit circle into a given number, $n$, of arcs of equal lengths. By the theory of cyclotomy, we shall mean the special attack upon this problem discovered by Gauss in connection with the ruler-and-compass construction of the regular polygon of $n$ sides.

Let $q=ef+1$ be an odd prime power, and let $\theta$ be a fixed primitive element of ${\rm{GF^*(}}\mathit{q}{\rm{)}}$. Define $D_i^{(e, q)}=\theta^i(\theta^e)$, where $(\theta^e)$ denotes the multiplicative subgroup generated by $\theta^e$. The cosets $D_i^{(e, q)}$ are called the index classes or cyclotomic classes of order $e$ with respect to ${\rm{GF(}}\mathit{q}{\rm{)}}$.

For fixed $i$ and $j$, we define $(i, j)_q^{(e)}$ to be the number of solutions of the equation

$ z_i+1=z_j\ \ \ (z_i\in D_i^{(e, q)}, \ z_j\in D_j^{(e, q)}), $

where $1=x^0$ is the multiplicative unit of ${\rm{GF^*(}}\mathit{q}{\rm{)}}$. That is, $(i, j)$ is the number of ordered pairs such that

$ x^{es+i}+1=x^{et+j}\ \ \ (0\leq s, t\leq f-1). $

These constants $(i, j)_q^{(e)}$ are called cyclotomic numbers of order $e$ with respect to ${\rm{GF(}}\mathit{q}{\rm{)}}$, $(i, j)$ in short if without any confusion. For more information about cyclotomic theory, one may be referred to [1] and [2-4].

It is easy to check the elementary relationships between the cyclotomic numbers.

(1) For any integers $m, n$, $(i+me, j+ne)=(i, j)$.

(2) $(i, j)=(e-i, j-i)$.

(3) $(i, j) = \left\{ {\begin{array}{*{20}{l}} {(j, i), }&{{\rm{if }}\;\mathit{f}\;{\rm{ is~ even}}, }\\ {(j + e/2, i + e/2), }&{{\rm{if }}\;\mathit{f }\;{\rm{is ~odd}}.} \end{array}} \right.$

(4) $\sum\limits_{j = 0}^{e - 1} {(i, j)} = f - {\theta _i}, {\rm{where}}\;{\theta _i} =$ $\left\{ {\begin{array}{*{20}{l}} {1, }&{{\rm{if }}\;\mathit{f}\;{\rm{is}}\;{\rm{even}}\;{\rm{and}}\;\mathit{i}{\rm{ = 0}}, }\\ {1, }&{{\rm{if }}\;\mathit{f}\;{\rm{is}}\;{\rm{odd}}\;{\rm{and}}\;\mathit{i}{\rm{ = }}\mathit{e}{\rm{/2}}, }\\ {0, }&{{\rm{otherwise}}.} \end{array}} \right.$

(5) $\sum\limits_{i = 0}^{e - 1} {(i, j)} = f - {\eta _j}, {\rm{where}}\;{\eta _j} =$ $\left\{ {\begin{array}{*{20}{l}} {1, }&{{\rm{if}}\;{\rm{ }}\mathit{j}{\rm{ = 0}}, }\\ {0, }&{{\rm{otherwise}}.} \end{array}} \right.$

In 1953, Lehmer [5] established a simple and powerful connection between the theory of cyclotomy and the existence of difference sets. Since then, more and more difference sets were established by means of cyclotomic method. And also, some new properties of cyclotomy were achieved from the existence of difference sets.

Definition 1.1  A partial difference set $D$ is a subset of a group $G$ with the property that every nonidentity element of $D$ can be represented $\lambda$ times as a difference between a pair of elements in $D$ while every nonidentity element of $G\setminus D$ can be represented $\mu$ times as a difference between a pair of elements in $D$. Likewise, partial difference sets have parameters $(v, k, \lambda, \mu)$ associated with them, where $v=|G|$, $k=|D|$, and $\lambda$ and $\mu$ are as described above.

In 1963, Bose [6] introduced the concept of strongly regular graphs.

Definition 1.2  An undirected graph without loops and multiple edges on $v$ vertices is called a $(v, k, \lambda, \mu)$-strongly regular graph if it is regular with valency $k$, and each adjacent pair of vertices has $\lambda$ vertices, which are adjacent to both of them, also each non-adjacent pair of vertices has $\mu$ vertices, which are adjacent to both of them.

Clearly a disconnected strongly regular graph is a disjoint union of complete graphs of equal size. The complement of a strongly regular graph with parameters $(v, k, \lambda, \mu)$ is also a strongly regular graph with parameters $(v, v-k-1, v-2k+\mu-2, $ $v-2k+\lambda)$. In consequence, we have the trivial necessary condition $v-2k+\mu-2\geq0$ for the existence of a strongly regular graph. A simple counting argument shows that we also have the necessary condition $k(k-1)=k\lambda+(v-k-1)\mu$. For more information, one can be refered to [7-9].

As it is known that partial difference sets can be used to construct strongly regular graphs.

Suppose $D$ is a $(v, k, \lambda, \mu)$ partial difference set in $G$. Let the elements of $G$ be vertices of a graph, and join two vertices $v_1$, $v_2$ with an edge if $v_1-v_2\in D$. For all vertices $v$, they will have $k$ edges going into them because each will be connected to $v+d$ for all $d\in D$. If we consider two vertices $v_1$, $v_2$, connected to a vertex $x$, then $x-v_1\in D$ and $x-v_2\in D$. By taking $(x-v_1)-(x-v_2)=v_1-v_2$, this shows that there must be $\lambda$ values for $x$ if $v_1-v_2\in D$ and $\mu$ values for $x$ if $v_1-v_2\in G\setminus D$. Thus if there is a partial difference set, there exist a strongly regular graph with the same parameters. So in this paper, we equate the two concepts if without confusion.

In this paper, we firstly give a construction of a family of partial difference sets which also means the existence of strongly regular graphs with the same parameters. Then we get new properties of cyclotomic numbers.

Denote $q=ef+1$, let $D=\{(a, b):\ a, \ b\in D_i \mbox{ at the same time}, \ i \mbox{ runs from 0 to } e-1\}$, so we have $|G|=q^2$, $|D|=\dfrac{(q-1)^2}{e}$. We will discuss the set $D$ in group $G$ according to the value of $e$.

In this subsection, $q=2f+1$,

$ D=\{(a, b):\ a, \ b\mbox{ are squares or nonsquares at the same time}\}. $

When $e=2$, by the properties, the cyclotomic numbers are given as follows. If $q \equiv 1\pmod 4$, then

$ \begin{array}{ll} \displaystyle(0, 0)_{q}=\frac{q-5}{4}, ~~ \displaystyle(0, 1)_{q}=(1, 0)_{q}=(1, 1)_{q}=\frac{q-1}{4}. \end{array} $

If $q\equiv 3\pmod 4$, then

$ \begin{array}{ll}\displaystyle(0, 0)_{q}=(1, 0)_{q}=(1, 1)_{q}=\frac{q-3}{4}, ~~ \displaystyle(0, 1)_{q}=\frac{q+1}{4}.\end{array} $

We can compute the differences directly from the cyclotomic numbers, no matter $f$ is odd or even.

• $(a, 0)$ appears as a difference, where $a\neq 0$. That is, $(a, 0)=(a_1, b_1)-(a_2, b_1)$.

• $(0, b)$, where $b\neq 0$, is the same as the above case, that is, $(0, b)$ appears $f(f-1)$ times.

• $(a, b)\in D$ appears as a difference, that is $(a, b)=(a_1, b_1)-(a_2, b_2)$, $(a_i, b_i)\in D, \ i=1, 2$.

We can see from the table that $(a, b)\in D$ appears as many times as the sum of the squares of all the cyclotomic numbers.

• $(a, b)\not\in D$ and $a\neq 0, \ b\neq 0$. $(a, b)=(a_1, b_1)-(a_2, b_2)$.

Hence, above all,

$ d_D(a, b)=\left\{\begin{array}{lll}\displaystyle\frac{1}{e}(q-1)^2, \ \ \ &a=0, \ b=0;\ \ \ \\[0.2cm] f^2-f+1, &(a, b)\in D;\\[0.2cm] f(f-1), &\mbox{else}.\end{array}\right. $

Obviously, $D$ is a partial difference set with parameters

$ (q^2, \dfrac{1}{2}(q-1)^2, \dfrac{1}{4}(q^2-4q+7), \dfrac{1}{4}(q^2-4q+3)). $

It corresponds to a $(q^2, \dfrac{1}{2}(q-1)^2, \dfrac{1}{4}(q^2-4q+7), \dfrac{1}{4}(q^2-4q+3))$-strongly regular graph.

Example 1  When $e=2$, $f=1$, $q=3=2\times 1+1$. In ${\rm{GF(}}\mathit{q}{\rm{)}}$, $D_0=\{1\}$, $D_1=\{2\}$, so

$ \begin{eqnarray*}&&G={\rm{GF(}}\mathit{q}{\rm{)}}\times {\rm{GF(}}\mathit{q}{\rm{)}}=\{(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)\}, \\ &&D=\{(a, b):\ a, \ b\in D_i \mbox{ at the same time}, \ i=0, 1\}=\{(1, 1), (2, 2)\}.\end{eqnarray*} $

Obviously, $D$ is a $(9, 2, 1, 0)$ partial difference set. The corresponding strongly regular graph is Figure 1, which is disconnected.

Example 2  When $f=2$, $q=5=2\times 2+1$. In ${\rm{GF(}}\mathit{q}{\rm{)}}$, $D_0=\{1, 4\}$, $D_1=\{2, 3\}$, so

$ D=\{(1, 1), (1, 4), (4, 1), (4, 4), (2, 2), (2, 3), (3, 2), (3, 3)\}. $

It is easy to check that $D$ is a (25, 8, 3, 2) partial difference set. The corresponding strongly regular graph is Figure 2.

When $e=3, 4, 6$, following the same process, we have proved that when $q=ef+1$ is a prime power, there exist $(q^2, \dfrac{1}{e}(q-1)^2, $ $f^2+(e-3)f+1, f(f-1))$ partial difference sets, and also exist strongly regular graphs with the same parameters. Enlightened by the so trim form, we conjecture that the above result may also be true for other "$e$"s.

Theorem 2.1  Let $D=\bigcup\limits_{i=0}^{e-1}(D_i\times D_i)$, where $D_i\times D_i$ stands for $\{(x, y)\ |\ x, y\in D_i\}$. Then $D$ is a partial difference set in $({\rm{GF(}}\mathit{q}{\rm{)}}\oplus{\rm{GF(}}\mathit{q}{\rm{)}}, +)$.

We will prove the theorem by using character theory and a property of Gauss periods.

Let ${\rm{GF(}}\mathit{q}{\rm{)}}$ be the finite field of order $q$, where $q=p^t$, $p$ is a prime. Let $q=ef+1$, where $e>1$, and let $g$ be a primitive element of ${\rm{GF(}}\mathit{q}{\rm{)}}$. We use the following standard notation $\psi_1: {\rm{GF(}}\mathit{q}{\rm{)}}\to \mathbb{C}$ is the additive character of ${\rm{GF(}}\mathit{q}{\rm{)}}$ such that $\psi_1(x)=\xi_p^{\rm{Tr}(\mathit{x})}$, where $\xi_p$ is a complex primitive $p$th root of unity and Tr is the absolute trace from ${\rm{GF(}}\mathit{q}{\rm{)}}$.

$ \begin{eqnarray*}&&D_0=\langle g^e\rangle, \ D_i=g^iD_0, \ \forall i, \ 0\leq i\leq e-1, \\ &&\eta_i=\sum\limits_{x\in D_i}\psi_1(x):=\psi_1(D_i)\end{eqnarray*} $

are the Gauss periods.

The following well-known character theoretic characterizations of abelian partial difference sets will be used in our proof.

Lemma 2.2  Let $G$ be an abelian group of order $v$ and $D$ be a subset of $G$ with $\{d^{-1}:\ d\in D\}=D$. Then $D$ is a $(v, k, \lambda, \mu)$ partial difference set in $G$ if and only if, for any character $\chi$ of $G$,

$ \sum\limits_{d \in D} \chi (d) = \left\{ {\begin{array}{*{20}{l}} {k, }&{{\rm{if}}\;\mathit{\chi }\;{\rm{is}}\;{\rm{princpal}}\;{\rm{on}}\;\mathit{G}{\rm{, }}}\\ {\frac{{\beta \pm \sqrt {{\beta ^2} + 4\gamma } }}{2}, }&{{\rm{if}}\;\mathit{\chi }\;{\rm{is}}\;{\rm{nonprincipal}}\;{\rm{on}}\;\mathit{G}{\rm{, }}} \end{array}} \right. $

where $\beta=\lambda-\mu$; $\gamma=k-\lambda$ if $e\in D$, and $\gamma=k-\mu$ if $e\not\in D$.

Proof of Theorem 2.1.  Let $\psi_a\otimes\psi_b$ be a character of $({\rm{GF(}}\mathit{q}{\rm{)}}\oplus{\rm{GF(}}\mathit{q}{\rm{)}}, +)$. Then

$ \psi_a\otimes\psi_b(D)=\sum\limits_{i=0}^{e-1}\psi_a(D_i)\psi_b(D_i). $

If $a=0$ or $b=0$ (but not both), then one easily sees that $\psi_a\otimes\psi_b(D)=-f$.

If $a\neq0$ and $b\neq 0$, then

$ \psi_a\otimes\psi_b(D)=\sum\limits_{i=0}^{e-1}\psi_{ag^i}(D_0)\psi_{bg^i}(D_0). $

Let $ab^{-1}=g^l$. Then $\psi_a\otimes\psi_b(D)=\sum\limits_{i=0}^{e-1}\eta_i\eta_{i+l}.$ Now note the following property of Gauss periods $\sum\limits_{i=0}^{e-1}\eta_i\eta_{i+l}=q\delta_{l, 0}-f, $ where $\delta_{l, 0}=1$ if $l=0$ and it equals $0$ otherwise. We have

$ \psi_a\otimes\psi_b(D)=q-f\ \mbox{or}\ -f. $

Therefore we have shown that the character sum $\psi_a\otimes\psi_b(D)$ takes two values $q-f, \ -f$ as $\psi_a\otimes\psi_b$ runs through all nontrivial characters of $({\rm{GF(}}\mathit{q}{\rm{)}}\oplus{\rm{GF(}}\mathit{q}{\rm{)}}, +)$. This proves that $D$ is a partial difference set.

It is not difficult to check the parameters are $(q^2, \dfrac{(q-1)^2}{e}$, $f^2+(e-3)f+1, f(f-1))$.

From the point of the strongly regular graphs, suppose $q=ef+1$ is a prime power. Construct a graph $G$ with $q^2$ vertices. Label these vertices with $(a, b)$, here $(a, b)\in {\rm{GF(}}\mathit{q}{\rm{)}}\times {\rm{GF(}}\mathit{q}{\rm{)}}$. Let $D=\{D_i\times D_i:\ i=0, 1, \cdots, e-1\}$. Call $(a, b)\sim(a', b')$ iff $(a-a'\pmod q, b-b'\pmod q)\in D$, we usually omit the "$\pmod q$" if with none confusion. Since for any vertex $(a, b)$, $(a, b)\sim(a, b)+D$, so the degree of $(a, b)$ is $|D|=\dfrac{1}{e}(q-1)^2$. By Theorem 2.1, $G$ is a $(q^2, \dfrac{(q-1)^2}{e}, f^2+(e-3)f+1, f(f-1))$ strongly regular graph.

Since we have proved the existence of the partial difference sets, we can use it to get some properties of cyclotomic numbers in return.

As it is known that for a $(v, k, \lambda, \mu)$ partial difference set $D$, every nonidentity element of $D$ can be represented $\lambda$ times as a difference between a pair of elements in $D$ while every nonidentity element of $G\setminus D$ can be represented $\mu$ times as a difference between a pair of elements in $D$.

On the other hand, for any element $(a, b)$, it can be represented as $(a_1, b_1)-(a_2, b_2)$, here $(a_1, b_1), (a_2, b_2)\in D$.

(1) $(a, b)\in D$.

$ \lambda=\sum\limits_{i=0}^{e-1}\sum\limits_{j=0}^{e-1}(i, j)^2. $

(2) $(a, b)\not\in D$.

$\centerdot$ $a=0$ or $b=0$, but not both.

$ \mu=\frac{q-1}{e}\sum\limits_{i=0}^{e-1}(i, i)=f(f-1); $

$\centerdot$ $a\neq0$ and $b\neq 0$. Suppose $(a, b)\in D_i\times D_j$, $0\leq i, j\leq e-1$, $i\neq j$,

$ \mu=\sum\limits_{m=0}^{e-1}\sum\limits_{n=0}^{e-1}(m-i, n-i)(m-j, n-j). $

So we get the new properties of cyclotomic numbers.

Theorem 3.1  Suppose $q=ef+1$ is a prime power. The cyclotomic numbers satisfy

(1) $\sum\limits_{i=0}^{e-1}\sum\limits_{j=0}^{e-1}(i, j)^2=f^2+(e-3)f+1$;

(2) $\sum\limits_{m=0}^{e-1}\sum\limits_{n=0}^{e-1}(m-i, n-i)(m-j, n-j)=f(f-1)$ for all $0\leq i, j\leq e-1$, $i\neq j$.