2 Linearised polynomials and Sidon sets

We start by recalling some elementary facts about linearised polynomials (for a detailed exposition, we refer to [Reference Lidl and Niederreiter6, Ch. 3]).

Let $\mathbb {F}_q$ and $\mathbb {F}_{q^m}$ be the finite fields with q and $q^m$ elements, respectively, where q is a prime or a prime power. Polynomials over $\mathbb {F}_{q^m}$ of the form

$$ \begin{align*} L(x):=\sum_{i=0}^{n}c_ix^{q^i}, \quad n \in \mathbb{N}, \end{align*} $$

are often known as q-polynomials or linearised polynomials. This terminology stems from the following property: if F is an arbitrary extension field of $\mathbb {F}_{q^m}$ , then

$$ \begin{align*} L(\alpha+\beta) & =L(\alpha)+ L(\,\beta)\quad \text{for all}\;\alpha, \beta \in F, \\ L(c\alpha) & =cL(\alpha)\quad \text{for all } c \in \mathbb{F}_{q} \;\text{and all } \alpha \in F. \end{align*} $$

So these special polynomials induce linear transformations of $\mathbb {F}_{q^m}$ and $\mathbb {F}_{q}$ . An important example of a linearised polynomial is the so-called trace polynomial

$$ \begin{align*}\mathrm{Tr}(x)=\sum_{i=0}^{m-1}x^{q^i}\end{align*} $$

defining the trace function of $\mathbb {F}_{q^m}$ over $\mathbb {F}_{q}$ . The following well-known theorem shows the special character of the set of roots of a linearised polynomial.

Theorem 2.1 [Reference Lidl and Niederreiter6, Ch. 3]

Let $L(x)$ be a nonzero linearised polynomial over $\mathbb {F}_{q^m}$ and let the extension field $\mathbb {F}_{q^s}$ of $\mathbb {F}_{q^m}$ contain all the roots of $L(x)$ . Then each root of $L(x)$ has the same multiplicity, which is either $1$ or a power of q, and the roots form a linear subspace of $\mathbb {F}_{q^s}$ , regarded as a vector space over $\mathbb {F}_{q}$ . Reciprocally, let U be a linear subspace of $\mathbb {F}_{q^m}$ , considered as a vector space over $\mathbb {F}_{q}$ . Then for any nonnegative integer k, the polynomial

$$ \begin{align*}L(x)=\prod_{\beta \in U}(x-\beta)^k\end{align*} $$

is a linearised polynomial over $\mathbb {F}_{q^m}.$

A polynomial of the form $A(x)=L(x)+\alpha $ , where $L(x)$ is a linearised polynomial over $\mathbb {F}_{q^m}$ and $\alpha \in \mathbb {F}_{q^m}$ , is called an affine q-polynomial over $\mathbb {F}_{q^m}$ . As in the case of linearised polynomials, there is an analogue of Theorem 2.1.

Theorem 2.2 [Reference Lidl and Niederreiter6, Ch. 3]

Let $A(x)$ be an affine q-polynomial over $\mathbb {F}_{q^m}$ and let the extension field $\mathbb {F}_{q^s}$ of $\mathbb {F}_{q^m}$ contain all the roots of $A(x)$ . Then each root of $A(x)$ has the same multiplicity, which is either $1$ or a power of q, and the roots form an affine subspace of $\mathbb {F}_{q^s}$ , regarded as a vector space over $\mathbb {F}_{q}$ . Reciprocally, let T be an affine subspace of $\mathbb {F}_{q^m}$ , considered as a vector space over $\mathbb {F}_{q}$ . Then for any nonnegative integer k, the polynomial

$$ \begin{align*}A(x)=\prod_{\beta \in T}(x-\beta)^{q^k}\end{align*} $$

is an affine q-polynomial over $\mathbb {F}_{q^m}.$

In this paper, we are interested in the special case $L(x)=x^q+ax$ defined over $\mathbb {F}_{q^2}$ . If L splits completely over $\mathbb {F}_{q^2}$ , then its roots have multiplicity one and form a vector space of dimension one over $\mathbb {F}_{q}$ , that is to say a line, denoted by $\mathcal {L}$ . Let $\mathcal {A}$ be the affine line associated to the affine q-polynomial $A(x)=x^q+ax+b$ , when it splits completely over $\mathbb {F}_{q^2}$ .

Consider a line $\mathcal {L}\subset \mathbb {F}_{q^2}$ , that is, $\mathcal {L} = \mathrm {Gen}(\theta ):=\lbrace a\theta : a \in \mathbb {F}_q \rbrace $ for some nonzero $\theta \in \mathbb {F}_{q^2}$ . Then for every $\delta \in \mathbb {F}_{q^2}{\setminus} \mathcal {L}$ , the set $\mathcal {A}:=\mathcal {L} + \delta $ is an affine line. Fix once and for all a primitive element $\gamma $ in $\mathbb {F}_{q^2}^{\times }$ .

Before stating and proving our main result, we require the following simple lemma.

Lemma 2.4 [Reference Ganley4, page 323]

If $\alpha _1, \alpha _2, \alpha _3$ and $\alpha _4 \in \mathbb {F}_q$ are distinct, then the relations

(2.1) $$ \begin{align} \alpha_1 \alpha_2 = \alpha_3 \alpha_4, \quad \alpha_1 + \alpha_2 = \alpha_3 + \alpha_4 \end{align} $$

cannot hold simultaneously. In other words, any solution $ (\alpha _1, \alpha _2, \alpha _3, \alpha _4) \in \mathbb {F}_q^4$ of (2.1) satisfies $\alpha _1 \in \lbrace \alpha _3, \alpha _4\rbrace $ .

Theorem 2.5. Let $\gamma $ be a primitive element in $\mathbb {F}_{q^2}^{\times }$ and let $\theta , \delta \in \mathbb {F}_{q^2}^{\times }$ be such that $\delta \notin \mathcal {L} = \mathrm {Gen}(\theta )$ . Then the set

$$ \begin{align*}\mathcal{S} := \mathrm{Log}_{\gamma} (\mathcal{A})=\{ \mathrm{Log}_\gamma (\alpha \theta + \delta) \mid \alpha \in \mathbb{F}_q \},\end{align*} $$

where $\mathcal {A}:=\mathcal {L} + \delta $ , is a Sidon set modulo $q^2 - 1$ .

Proof. Let $a_1, a_2, a_3, a_4 $ be any four different elements in $\mathcal {S}$ such that $a_1 + a_2 = a_3 + a_4$ . Since the sum is taken modulo $q^2-1$ and $\gamma $ is primitive, the powers of $\gamma ^i$ are different for $1\leq i \leq q^2-1$ and $\gamma ^{a_1} \cdot \gamma ^{a_2} = \gamma ^{a_3} \cdot \gamma ^{a_4}$ .

Since the $\gamma ^{a_i}$ terms are different elements of $\mathbb {F}_{q^2}$ and by construction also belong to $\mathcal {A}$ , there exist distinct $\alpha _1, \alpha _2, \alpha _3, \alpha _4 \in \mathbb {F}_q$ such that $(\alpha _1 \theta + \delta )(\alpha _2 \theta + \delta ) = (\alpha _3 \theta + \delta )(\alpha _4 \theta ~+~\delta )$ , that is,

(2.2) $$ \begin{align} \alpha_1 \alpha_2 \theta^2 + (\alpha_1 + \alpha_2)\theta \delta + \delta^2 = \alpha_3 \alpha_4 \theta^2 + (\alpha_3 + \alpha_4)\theta \delta + \delta^2. \end{align} $$

Equation (2.2) is equivalent to

$$ \begin{align*}(\alpha_1 \alpha_2 - \alpha_3 \alpha_4)\theta = (\alpha_3 + \alpha_4 - \alpha_1 - \alpha_2)\delta.\end{align*} $$

By Lemma 2.4, the expressions $\alpha _1 \alpha _2 - \alpha _3 \alpha _4$ and $\alpha _3 + \alpha _4 - \alpha _1 - \alpha _2$ are not zero simultaneously, so we can write

(2.3) $$ \begin{align} \delta = \dfrac{b}{a} \theta, \end{align} $$

where $b = \alpha _1 \alpha _2 - \alpha _3 \alpha _4$ and $a = \alpha _3 + \alpha _4 - \alpha _1 - \alpha _2$ . Since ${b}/{a} \in \mathbb {F}_q$ , (2.3) implies $\delta \in \mathrm {Gen}(\theta )$ , which contradicts our hypothesis and proves our claim.

Remark 2.6. Let us consider the linearised polynomial $ f (x) = x ^ q-x $ , which decomposes completely in $\mathbb {F}_{q^2}$ . Its roots are all the elements of $\mathbb {F}_{q}$ , so the affine polynomial $g(x) = f (x-a)$ is also reducible and

$$ \begin{align*} f (x-a)=x^q-a^q-(x-a) =x^q-x-(a^q+a). \end{align*} $$

Setting $\beta =a^q+a$ , a straightforward calculation shows that $\beta $ has trace 0 and we get Bose’s construction as a particular case.

3 Linearised polynomials and Sidon arrays

In this section, we define new objects which we have called Sidon arrays. We first make some further remarks on the linearised polynomials that appear in the construction of Sidon sets in the previous section. We need the following lemma giving conditions for the polynomial $x^q+ax$ to factorise completely over $\mathbb {F}_{q^2}$ .

Using Lemma 3.1 and since $f(x)=b^{-q}\mathrm {Tr}(bx)=\prod _{i=1}^{q}(x-b^{-1}\lambda _i)$ , the roots of f can be written as $\beta \lambda _j$ for $\beta $ a $(q + 1)$ th root of unity and $\lambda _j$ ranging over all trace zero elements in $\mathbb {F}_{q^2}$ .

Remark 3.2. The roots of a q-polynomial of the form $x^q + ax $ form a vector subspace of dimension one over $ \mathbb {F} _q $ and therefore an additive normal subgroup $ \mathcal {G} _a $ of $ \mathbb {F} _ {q ^ 2} $ with $ q $ elements. Thus, $ \mathbb {F}_{q^2} $ is the union of $ q $ different classes, that is,

$$ \begin{align*} \mathbb {F}_ {q^2} = \bigcup_{i = 1}^q (c_i + \mathcal{G}_a) \end{align*} $$

with the convention that $ c_1 = 0 $ corresponds to the class of $ \mathcal {G} _a $ .

By Theorem 2.2, the q elements of a class $c_i + \mathcal {G}_a$ are the roots of an affine polynomial of the form $f(x)=x^q+ax+b$ . Since $c_i$ belongs to at least one line, there is a linearised polynomial $L(x)$ that has $c_i$ as one of its roots. By the description given above for the roots of $L(x)$ , we can also characterise the roots of the affine polynomial $f(x)$ as $ \theta \lambda +\beta \mathcal {G}_0$ , where $\mathcal {G}_0$ is the additive subgroup in $\mathbb {F}_{q^2}$ of trace zero elements, $\beta $ and $\theta $ are $(q+1)$ th roots of unity and $\lambda \in \mathcal {G}_0$ is such that $\theta \lambda \notin \beta \mathcal {G}_0$ .

By Remark 3.2, the elements of $ \mathbb {F} _ {q ^ 2} $ can be organised in a $ q \times q $ matrix $ \mathcal {S}$ such that the ith row is the class $ (c_i + \mathcal {G} _a) $ . Recall that the elements of $\mathcal {G} _a$ are of the form $\beta \lambda _j$ , where $\beta $ is a $(q + 1)$ th root of unity and $\lambda _j$ ranges over all trace zero elements in $\mathbb {F}_{q^2}$ . So the entries of $\mathcal {S}$ are $s_{i,j}=c_i+\beta \lambda _j$ .

From the comments and Remark 3.2, Sidon arrays of order $ q $ exist and they can be constructed as indicated above.

Example 3.4. Let us consider $q=p=5$ . The polynomial $ p(x) = x^2 + 4x + 2 $ is primitive over $ \mathbb {F}_5 $ with root $\gamma $ . Take $a=\gamma ^{16}$ . Then $\mathcal {G}_a=\lbrace 0, \gamma ^{19}\gamma ,\gamma ^7, \gamma ^{13} \rbrace $ is the set of roots of $f(x)=x^5 + \gamma ^{16}x$ . The elements of $\mathbb {F}_{q^2}$ can be organised as in Table 1.

Table 1 A Sidon array modulo 25 before taking logarithms.

Taking logarithms, with the convention $ \mathrm {Log}_ \gamma (0) = 24 $ , gives Table 2.

Table 2 A Sidon array modulo 25.

It can be verified that the table meets the conditions for a Sidon array. In fact, the second row corresponds to the set obtained in Example 2.7, as logarithms of the roots of the polynomial $A(x)=x^5 + \gamma ^{16}x + \gamma ^{14}$ .

Sidon arrays are a refinement of the partitions in the case $ h = 2 $ introduced by Gilberto et al. [Reference Gilberto, Alberto and Velasquez5]. They proved the following theorem.

In our case, taking $h = 2$ , we have a partition of $\mathbb {Z}_{q^2}$ modulo $q ^ 2-1$ as $B_2$ sets, that is, Sidon sets.

A Golomb ruler $G_k$ of order k is an ordered set of k integers $(a_1, a_2, \ldots , a_k)$ such that $0 \leq a_1 < a_2 < \cdots < a_k$ and all the differences $\lbrace a_i - a_j \mid 1 \leq j < i \leq k\rbrace $ are distinct. A $(v, k)$ -modular Golomb ruler is an ordered set of k integers $(a_1, a_2, \ldots , a_k)$ such that $0 \leq a_1 < a_2 < \cdots < a_k$ and all the differences $\lbrace a_i - a_j \mid 1 \leq j < i \leq k,\; i \neq j \rbrace $ are distinct and nonzero modulo v.

Sidon sets are widely used in the construction of Golomb rulers and modular Golomb rulers (see [Reference Caicedo, Martos and Trujillo2, Reference Davydov, Faina, Giulietti, Marcugini and Pambianco3, Reference Martos Ojeda, Delgado Ordoñez and Trujillo Solarte8]). In this context, disjoint Golomb rulers (see [Reference Xiu, Fan and Liang11]) are similar to Sidon arrays. This is another reason for our interest in Sidon arrays, since they could have similar properties and applications as disjoint Golomb Rulers.

4 Linear recurrences and fast construction of Sidon sets

We begin this section with the definition and properties of recurrence relations, which we need for our applications. For more details, see [Reference Lidl and Niederreiter6, Ch. 6].

Definition 4.1. Let $k \in \mathbb {N}$ . A sequence $s_0,s_1,\ldots $ of elements of $\mathbb {F}_q$ is called a linear recurring sequence of order k in $\mathbb {F}_q$ if there are elements $a,a_0,a_1,\ldots , a_{k-1} \in \mathbb {F}_q$ such that

(4.1) $$ \begin{align} s_{n+k} = a_{k-1}s_{n+k-1}+a_{k-2}s_{n+k-2}+\cdots +a_{0}s_n+a. \end{align} $$

The terms $s_0 , s_1,\ldots , s_{k-1}$ determining the sequence are called initial values. Equation (4.1) is called a linear recurrence relation of order k. If $a=0$ it is called homogeneous, otherwise it is called nonhomogeneous. The vector $(s_n, s_{n+1},\ldots , s_{n+k-1})$ is called an nth state vector; in particular, $(s_0, s_{1},\ldots , s_{k-1})$ is called an initial state vector. Linear recurring sequences in $\mathbb {F}_q$ are eventually periodic. More precisely, we have the following result.

Suppose that the affine polynomial $ f (x) = x^q + ax + b $ factorises as a product of linear polynomials over $\mathbb {F}_{q^2}$ , so its roots lie on an affine line and therefore their discrete logarithms form a Sidon set modulo $q^2-1$ . As remarked above, $f(x)=\beta ^{-q} \mathrm {Tr}(\,\beta x+ \alpha )$ for some nonzero $\beta , \alpha \in \mathbb {F}_{q^2}$ . So if $\theta $ is a root of $f(x)$ , then it is also a root of $\mathrm {Tr}(\,\beta x+ \alpha )$ . We will use this fact to give a fast construction of Sidon sets without the need to take discrete logarithms.

Fix a primitive element $\gamma $ of $\mathbb {F}_{q^2}$ and define the sequence $s_i:=\mathrm{Tr}(\,\beta \gamma ^i+\alpha ) \in \mathbb {F}_q$ . By the properties of the trace polynomial, it is easy to prove that the sequence $s_i$ is periodic with period $q^2-1$ and therefore a linear recurring sequence of order k in $\mathbb {F}_q$ for some k. The next theorem follows from the above discussion and the construction in Section 2.

Although the definition of the set does not involve discrete logarithms, there is still the problem of evaluating the trace polynomial and calculating all the powers of the primitive element $\gamma $ . Using the fact that the sequence is recurrent, we can reduce our problem to calculate only the initial values of the recurrence, with the rest reduced to arithmetic on $\mathbb {F}_q$ .

Since $ \gamma $ is a primitive element, there exist $ n_0 $ and $ m_0 $ such that $ \beta = \gamma ^ {n_0} $ and $ \alpha = \gamma ^ {m_0} $ . In $\mathbb {F}_q$ ,

$$ \begin{align*} s_i=\mathrm{Tr}(\,\beta \gamma^i+\alpha) =\mathrm{Tr}(\,\beta \gamma^i)+ \mathrm{Tr}(\alpha) =\mathrm{Tr}(\gamma^{n_0} \gamma^i)+ \mathrm{Tr}(\gamma^{m_0}) = t_{i+n_0}+t_{m_0}, \end{align*} $$

where $t_i:=\mathrm {Tr}(\gamma ^i)$ is the sequence given by the trace. Also, $ t_i $ is periodic with period $ q^2-1 $ .

Let $ p(x) = x^2-a_1x-a_0 \in \mathbb {F}_q[x] $ be the minimal polynomial of $ \gamma $ . Then we have $ \gamma ^2 = a_1 \gamma + a_0 $ and multiplying by $ \gamma ^i $ gives $ \gamma ^{i + 2} = a_1 \gamma ^{i + 1} + a_0 \gamma ^i $ . Taking the trace on both sides,

(4.2) $$ \begin{align} t_{i+2} = \mathrm{Tr}(\gamma^{i+2})=\mathrm{Tr}(a_1\gamma^{i+1} +a_0\gamma ^i) =a_1\mathrm{Tr}(\gamma^{i+1}) +a_0\mathrm{Tr}(\gamma ^i) =a_1t_{i+1}+a_0t_i. \end{align} $$

That is, the recurrence has order $ 2 $ and the coefficients of the recurrence are the coefficients of the minimal polynomial $ p(x) $ . So we only need to find the initial values $ t_0 $ and $ t_1 $ :

$$ \begin{align*} t_0=\mathrm{Tr}(\gamma^0) =1^q+1 =2 , \quad t_1=\mathrm{Tr}(\gamma) = \gamma^q + \gamma =-a_1, \end{align*} $$

the last equation because $ \gamma $ and $ \gamma ^q $ are conjugates. Thus the sequence $ s_i $ is completely determined. However, this is not yet an effective method because if $ n_0 $ and $ m_0 $ are large, we need to calculate many terms of the recurrence $t_i$ . Instead, we use the particular case $ \beta = 1 $ , that is, we consider the sequence $ s_i = \mathrm {Tr} (x + \alpha ) = t_i + t_{m_0} $ . Set $ b = t_ {m_0} $ so that $ t_i = s_i-b $ . Substituting this in (4.2) gives

$$ \begin{align*} s_{n+2}&= a_1(s_{n+1}-b)+a_0(s_n-b)+b \\[2pt] &= a_1s_{n+1}+a_0s_n+b(1-a_1-a_0) \\[2pt] &= a_1s_{n+1}+a_0s_n+bp(1). \end{align*} $$

From this discussion, we derive the following result.

The result of the previous theorem can be described algorithmically as shown in Algorithm 1.

Algorithm 1: SidonSets

Algorithm 1 requires calculation of $O(q^2)$ terms to form the period and the calculations being done in $\mathbb {F}_q$ . In [Reference Lindström7, Theorem 2.1], the author shows that Bose-type Sidon sets can be constructed without taking logarithms, only calculating certain powers and doing arithmetic modulo $q^2-1$ , that is, with the same complexity. When $q=p$ with p prime, [Reference Lindström7] also gives a fast criterion to construct primitive polynomials.