Conflict-Avoiding Codes of Prime Lengths and Cyclotomic Numbers

A binary protocol sequence set for transmitting data packets over a multiple-access collision channel without feedback is called a conflict-avoiding code (CAC) in information theory and has been studied few decades ago by [Mat90, NGM92, GV93, TR02, LT05, Lev07]. A mathematical model for CACs of length $n$ and (Hamming) weight $w$ is as follows. Let $\mathbb{Z}_{n}=\mathbb{Z}/n\mathbb{Z}$ be the additive group of $\mathbb{Z}$ modulo $n$. For a $w$-subset ${\bf x}=\{x_{1},\ldots,x_{w}\}$ of $\mathbb{Z}_{n}$, denote the difference set of ${\bf x}$ by $\Delta({\bf x})=\{x_{i}-x_{j}\mid i\neq j\}$. A CAC of length $n$ and weight $w$ is a collection $\mathcal{C}$ of $w$-subsets of $\mathbb{Z}_{n}$ such that $\Delta({\bf x})\cap\Delta({\bf y})=\varnothing$ for every distinct ${\bf x},{\bf y}$ of $\mathcal{C}$. Each ${\bf x}$ is called a codeword. A CAC is said to be optimal if it has the maximal size among all CACs of the same length and weight. When the weight is $1$ or $2$, there is no difficulty to find the optimal size. For weights more than $2$, however, finding an optimal CAC and determining its size is still an open problem. The first challenge is the weight $3$ and we introduce its development below.

Assume that the weight $w=3$. The construction of an optimal CAC of an arbitrary even length is completely found by many authors [LT05, JMJ⁺07, MFU09, FLM10]. However, the known results for odd lengths are still far from completion. In the case that the length $n$ is odd, the multiplicative order of $2$ in the multiplicative group of units of $\mathbb{Z}_{p}$ for prime divisors $p$ of $n$ becomes a key role in constructing an optimal CAC. For convenience, we denote $\mathbb{Z}_{p}^{\times}$ by the multiplicative group of $\mathbb{Z}_{p}$ and $o_{p}(2)$ by the multiplicative order of $2$ in $\mathbb{Z}_{p}^{\times}$ for an odd prime $p$. A construction of optimal CAC is found in [LT05] for prime length $p$ such that $4\mid o_{p}(2)$. Later, the construction is improved in [Lev07] for composite number length where every prime divisor $p$ of the length satisfies $4\mid o_{p}(2)$.

The remaining situation is that the length has a prime divisor $p$ such that $4\nmid o_{p}(2)$. In [FLS14], the authors prove that the problem of such length can be reduced to the problem of length $n$ such that every prime divisor $p$ of $n$ satisfies $4\nmid o_{p}(2)$. They also prove that an optimal CAC of length $n=p^{k}$ can be constructed from an optimal CAC of length $p$ where $p$ is a non-Wieferich prime (that $2^{p-1}\not\equiv 1\pmod{p^{2}}$). However, the construction for prime length $p$ is not completely found. For other odd lengths one can refer to [Mom07, WF13, LMSJ14, MM17, HLS] for the constructions. It turns out that the prime lengths are fundamental objects needed to be solved. This leads us to study CACs prime lengths and weight $3$.

For an odd prime length $p>3$, a difference set $\Delta({\bf x})$ would have size $4$ or $6$ for a $3$-subset ${\bf x}$ of $\mathbb{Z}_{p}$. Without loss of generality, we can assume the codeword ${\bf x}$ to be $\{0,\alpha,\beta\}$ for some $\alpha,\beta\in\mathbb{Z}_{p}^{\times}$. Then $|\Delta({\bf x})|=4$ if and only if ${\bf x}=\{0,\alpha,2\alpha\}$ for some $\alpha$. In this case, ${\bf x}$ is called an equi-difference codeword. To have an optimal CAC, it is natural to have equi-difference codewords as many as possible. If $M^{e}(p)$ denotes the maximal size among all CACs consisting of equi-difference codewords only, then one has

$$M^{e}(p)=\frac{p-1-2O(p)}{4}$$

where $O(p)=0$ if $4$ divides $\left|\langle-1,2\rangle\right|$ and $O(p)=(p-1)/\left|\langle-1,2\rangle\right|$ otherwise. Moreover, [FLS14, Lemma 3] provides

(1)

$\displaystyle M^{e}(p)\leq M(p)\leq M^{e}(p)+\left\lfloor\frac{O(p)}{3}\right\rfloor$

where $M(p)$ denotes the maximal size among all CACs. Thus, if $O(p)<3$, then a CAC consisting of equi-difference codewords only must be optimal. It remains to consider $O(p)\geq 3$. The authors of [FLS14] propose an algorithm for constructing nonequi-difference codewords. They conjecture that the algorithm always works for prime length $p$ for constructing $\left\lfloor\frac{O(p)}{3}\right\rfloor$ nonequi-difference codewords. Then $\frac{p-1-2O(p)}{4}$ equi-difference codewords could be further obtained and this CAC would be optimal by the upper bound in (1). For our purpose, we rephrase the statement of their conjecture in terms of cosets of the subgroup $\langle-1,2\rangle$, generated by $-1$ and $2$, in the multiplicative group $\mathbb{Z}_{p}^{\times}=\mathbb{Z}_{p}\setminus\{0\}$.

We remark that each $(a_{i},b_{i},c_{i})$ corresponds to the nonequi-difference codeword ${\bf x}_{i}=\{0,a_{i},c_{i}\}$ where $\Delta({\bf x}_{i})=\{\pm a_{i},\pm b_{i},\pm c_{i}\}$. Those triples $(a_{i},b_{i},c_{i})$ above correspond to a hypergraph matching in an auxiliary hypergraph in their terminology. We give an example to illustrate how Conjecture A and their algorithm work for constructing an optimal CAC.

Consider CACs of length $p=73$ and weight $3$ where $O(p)=4$. First, there are four cosets of $\langle-1,2\rangle$ in $\mathbb{Z}_{73}^{\times}$:

$$\langle-1,2\rangle,\quad 3\langle-1,2\rangle,\quad 5\langle-1,2\rangle,\quad 11\langle-1,2\rangle.$$

We pick elements $a,b,c$ in three different cosets respectively such that $a+b=c$. For example, we choose $a=2$, $b=3$ and $c=5$ from the first three cosets. Let ${\bf x}=\{0,2,5\}$. Then ${\bf x}$ is a nonequi-difference codeword and $\Delta({\bf x})=\{\pm 2,\pm 3,\pm 5\}$. The elements in $\langle-1,2\rangle\setminus\Delta({\bf x})$ lead to four equi-difference codewords

$${\bf x}_{1}=\{0,2^{2},2^{3}\},\quad{\bf x}_{2}=\{0,2^{4},2^{5}\},\quad{\bf x}_{3}=\{0,2^{6},2^{7}\},\quad{\bf x}_{4}=\{0,2^{8},2^{9}\}.$$

It is similar to $3\langle-1,2\rangle\setminus\Delta({\bf x})$, $5\langle-1,2\rangle\setminus\Delta({\bf x})$ and $11\langle-1,2\rangle\setminus\Delta({\bf x})$ that

$${\bf x}_{i+4}=\{0,3\cdot 2^{2i},3\cdot 2^{2i+1}\},\quad{\bf x}_{i+8}=\{0,5\cdot 2^{2i},5\cdot 2^{2i+1}\},\quad{\bf x}_{i+12}=\{0,11\cdot 2^{2i},11\cdot 2^{2i+1}\},$$

respectively, for $i=1,2,3,4$. The difference sets of all codewords ${\bf x},{\bf x}_{1},\ldots,{\bf x}_{16}$ are pairwisely disjoint. By the upper bound of $M(p)$ in (1), the collection $\mathcal{C}=\{{\bf x},{\bf x}_{1},\ldots,{\bf x}_{16}\}$ forms an optimal CAC which consists of $1$ nonequi-difference codeword and $16$ equi-difference codewords. If we choose $a=6$, $b=5$ and $c=11$ such that $a+b=c$, then ${\bf x}=\{0,6,11\}$ and $\Delta({\bf x})=\{\pm 6,\pm 5,\pm 11\}$. The same procedure will lead to another $16$ equi-difference codewords. Different choices of $a,b,c$ will give different optimal CACs.

The authors of [MZS14] independently give a similar thought to the existence of the triples $(A_{i},B_{i},C_{i})$ in Conjecture A in terms of the group structure of the quotient group $\mathbb{Z}_{p}^{\times}/\langle-1,2\rangle$. They notice that $\mathbb{Z}_{p}^{\times}/\langle-1,2\rangle$ is a cyclic group because $\mathbb{Z}_{p}^{\times}$ is cyclic.

Note that $\left[\mathbb{Z}_{p}^{\times}:\langle-1,2\rangle\right]\geq 3$ implies either $O(p)=0$ or $O(p)\geq 3$. Moreover, if Conjecture B holds for a prime $p$, then one can set $A_{1}=t^{0}\langle-1,2\rangle$, $B_{1}=t^{1}\langle-1,2\rangle$, $C_{1}=t^{2}\langle-1,2\rangle$, $A_{2}=t^{3}\langle-1,2\rangle$, $B_{2}=t^{4}\langle-1,2\rangle$, $C_{2}=t^{5}\langle-1,2\rangle$ and so on to obtain $t^{3i}+t^{3i}b=t^{3i}c$ for each $i$ where $(t^{3i},t^{3i}b,t^{3i}c)\in A_{i}\times B_{i}\times C_{i}$. Hence, Conjecture B implies Conjecture A. For the previous example that $p=73$, $t$ can be chosen as $5$. Then $b=5$, $c=6\in 5^{2}\langle-1,2\rangle$ and $1+5=6$ in $\mathbb{Z}_{p}$. Moreover, $p$ is not assumed to be non-Wieferich. In [MZS14], the authors have checked in computer that Conjecture B holds for prime $p\leq 2^{30}$.

The motivation of this article is to study Conjecture B. Throughout this article, we denote

$$\ell=\left[\mathbb{Z}_{p}^{\times}:\langle-1,2\rangle\right]=\left|\mathbb{Z}_{p}^{\times}/\langle-1,2\rangle\right|$$

for a given prime $p$. The existence of $b$ and $c$ in Conjecture B is strongly related to the so-called cyclotomic numbers $A(i,j)$ of order $\ell$ with respect to a primitive root where $i,j$ are integers. In particular, both $b$ and $c$ exist if and only if $A(i,2i)\neq 0$ for certain $i$. More precisely, Conjecture B is equivalent to the following statement. See Section 2 for detail.

The cyclotomic numbers was considered by C.F. Gauss [Gau01] and later L.E. Dickson [Dic35b, Dic35a, Dic35c] studied these numbers in the context of Waring’s problem. One of the central problems is to determine these numbers in terms of solutions of a certain Diophantine systems. See also the surveys [Raj80, Kat02, AT20]. However, it is still not obvious whether $A(i,2i)\neq 0$ because it is difficult either to find a suitable Diophantine system or to write down the formulas of cyclotomic numbers when $\ell$ is getting larger. Recently, cyclotomic numbers are developed into a secured public-key cryptography model [ATP21].

In this article, we study the conjecture above and we will prove the following result.

This not only answers Conjecture B but Conjecture A for a class of primes $p$. Moreover, the size $M(p)$ of optimal CAC can be determined as follows, while $O(p)=\ell$ if $4\nmid o_{p}(2)$.

This article is organized as follows. In Section 2, we introduce cyclotomic numbers and see how these numbers connect to Conjecture B. The cyclotomic numbers will lead to an interesting matrix in Section 3. This matrix can be used to answer Conjecture B, as well as Conjecture A, for primes with small $\ell$. In Section 4, we will see that the number of squares in a certain subset of $\mathbb{Z}_{p}$ can be represented to a particular sum of cyclotomic numbers. By counting squares and using an upper bound of cyclotomic numbers given in [BHKM13], we will be able to prove Theorem A. Finally, we remark how an obstacle is encountered for primes with composite number $\ell$.

In this article, $p$ is an odd prime and $\mathbb{Z}_{p}$ is the finite field of $p$ elements. Throughout this article, we denote

$$L=\langle-1,2\rangle$$

the subgroup of $\mathbb{Z}_{p}^{\times}=\mathbb{Z}_{p}\setminus\{0\}$ generated by $-1$ and $2$, and then $\ell=\left[\mathbb{Z}_{p}^{\times}:L\right]$ is the index of $L$ in $\mathbb{Z}_{p}^{\times}$. We always assume

$$\ell\geq 3.$$

A generator of $\mathbb{Z}_{p}^{\times}$ is also called a primitive root of $\mathbb{Z}_{p}$. Fix a primitive root $g$. Define the number

$$A(i,j)=\left|\left\{(m,n)\mid 0\leq m,n\leq\frac{p-1}{\ell}-1\text{ and }1+g^{i+m\ell}=g^{j+n\ell}\right\}\right|$$

for $i,j\in\mathbb{Z}$. These numbers $A(i,j)$ are called cyclotomic numbers of order $\ell$ with respect to $g$. We can rewrite $A(i,j)$ as follows. Note that $|L|=\frac{p-1}{\ell}$ and $L$ consists of all $\ell$-th power of elements of $\mathbb{Z}_{p}^{\times}$. Thus, both $g^{m\ell},g^{n\ell}\in L$ for $0\leq m,n\leq|L|-1$. It follows that

$$A(i,j)=\left|(1+g^{i}L)\cap g^{j}L\right|$$

for $i,j\in\mathbb{Z}$. If $i^{\prime}$ and $j^{\prime}$ are integers such that $i^{\prime}\equiv i\pmod{\ell}$ and $j^{\prime}\equiv j\pmod{\ell}$, then $g^{i^{\prime}}L=g^{i}L$ and $g^{j^{\prime}}L=g^{j}L$. We have $A(i^{\prime},j^{\prime})=A(i,j)$. Hence, it is convenient to consider $i,j$ modulo $\ell$.

As $g$ is a primitive root and $\ell=\left[\mathbb{Z}_{p}^{\times}:L\right]$, the quotient group $\mathbb{Z}_{p}^{\times}/L$ consists of elements $g^{0}L=L,g^{1}L,\ldots,g^{\ell-1}L$. In particular, the set

$$\left\{g^{i}L\mid 1\leq i\leq\ell\text{ and }(i,\ell)=1\right\}$$

is a complete set of generators of $\mathbb{Z}_{p}^{\times}/L$ where $(\cdot,\cdot)$ denotes the greatest common divisor of two given integers. Let $t\in\mathbb{Z}_{p}^{\times}$. Then $tL$ generates $\mathbb{Z}_{p}^{\times}/L$ if and only if $tL=g^{i}L$ for some $1\leq i\leq\ell$ with $(i,\ell)=1$. Moreover,

$$\left|(1+tL)\cap t^{2}L\right|=\left|(1+g^{i}L)\cap g^{2i}L\right|=A(i,2i).$$

Thus, Conjecture B holds for $p$ if and only if $A(i,2i)\neq 0$ for some $1\leq i\leq\ell$ with $(i,\ell)=1$. Because each $A(i,2i)$ is nonnegative, it is enough to consider the following sum

$$s(\ell)=\sum_{\begin{subarray}{c}1\leq i\leq\ell,\\ (i,\ell)=1\end{subarray}}A(i,2i).$$

The argument above actually shows the following lemma.

The sum $s(\ell)$ is defined with respect to a given primitive root $g$. In fact, we can freely compute $s(\ell)$ when picking an arbitrary primitive root. This helps a lot in practice. We leave a proof below for the readers because we do not find any reference for this fact.

As we have mentioned, one of main problems on the theory of cyclotomic numbers is to find explicit formulas for all $A(i,j)$ in terms of solutions of certain Diophantine systems. For example, consider $p\equiv 1\pmod{3}$ such that $\ell=3$. It is well-known that the Diophantine system

$$\left\{\begin{array}[]{c}4p=X^{2}+27Y^{2},\\ X\equiv 1\pmod{3}\end{array}\right.$$

has a solution $(a,b)$ with unique $a$, where $-p<a<p$. [Gau01, Section 358] gives that

$$A(0,0)=\frac{1}{9}(p-8+a),$$

$$A(0,1)=A(1,0)=A(2,2)=\frac{1}{18}(2p-4-a+9b),$$

$$A(0,2)=A(1,1)=A(2,0)=\frac{1}{18}(2p-4-a-9b),$$

$$A(1,2)=A(2,1)=\frac{1}{9}(p+1+a)$$

where the sign of $b$ depends of the choices of primitive roots. In this case, $A(1,2)=A(2,1)>0$ and thus

$$s(3)=A(1,2)+A(2,4)=A(1,2)+A(2,1)>0,$$

while $A(2,4)=A(2,1)$ because $4\equiv 1\pmod{\ell}$. However, the formulas for large $\ell$ will be extremely complicated and hard to find. For instance, the formulas for $\ell=11$ are presented in [LW75]. But it is not obvious whether $s(11)\neq 0$ or not for $p\equiv 1\pmod{11}$. See also Example 4.5.

We deduce the following useful properties.

The modulo relation and properties of cyclotomic numbers lead us to an interesting matrix. This will provide a new insight to the conflict-avoiding code problem. In this section, we will be able to easily answer Conjecture B for small $\ell$.

For a given primitive root of $\mathbb{Z}_{p}$, the cyclotomic matrix is an $\ell$-by-$\ell$ matrix defined as follows

$$(A(i,j))_{\ell\times\ell}\quad\text{for }i,j=0,1,\ldots,\ell-1.$$

It is convenient to give a variation of the cyclotomic matrix. We define the extended cyclotomic matrix $B=(b_{i,j})_{\ell\times\ell}$ as follows

$$b_{i,j}=\left\{\begin{array}[]{ll}A(0,0)+1&\text{if $i=j=0$;}\\ A(i,j)&\text{otherwise}.\end{array}\right.$$

For $i,j$ modulo $\ell$, Lemma 2.3 gives the relation for entries:

(2)

$\displaystyle b_{i,j}=b_{-i,j-i}=b_{j-i,-i}=b_{i-j,-j}=b_{-j,i-j}=b_{j,i}.$

For convenience, the row $(b_{i,0},b_{i,1},\ldots,b_{i,\ell-1})$ of $B$ is said to be indexed by $i$ for $i=0,\ldots,\ell-1$. This matrix $B$ has following nice properties.

Recall the sum $s(\ell)$ and we have

$$s(\ell)=\sum_{\begin{subarray}{c}1\leq i\leq\ell,\\ (i,\ell)=1\end{subarray}}b_{i,2i}.$$

The relations (2) and Lemma 3.1 lead us to answer that $s(\ell)>0$ for small $\ell$.