Binary sequences and lattices constructed by discrete logarithms

1.   Introduction and main results

Over 20 years ago, Mauduit and Sárközy (partly with coauthors) started to study pseudorandomness of binary sequences

and developed a quantitative and constructive theory of this subject. In particular, in ^[1] Mauduit and Sárközy introduced the measures of pseudorandomness: The well-distribution measure of $E_N$ is defined by

where the maximum is taken over all $a$, $b$, $t\in \mathbb{N}$ with $1\leq a\leq a+(t-1)b\leq N$. The correlation measure of order $k$ of $E_N$ is

where the maximum is taken over all $D = \left(d_1, \cdots, d_k\right)$ and $M$ with $0\leq d_1 < \cdots < d_k\leq N-M$.

The sequence is considered as a "good" pseudorandom sequence if both $W\left(E_N\right)$ and $C_k\left(E_N\right)$ (at least for small $k$) are "small" in terms of $N$. Later many pseudorandom binary sequences were given and studied by using number theoretic methods (see ^[2,3,4,5,6]).

Let $p$ be a prime number and $g$ be a primitive root modulo $p$. For an integer $n$ with $\gcd(n, p) = 1$, let $\hbox{ind}\ n$ be the smallest non-negative integer $t$ with $g^t\equiv n \ (\bmod \ p)$. That is,

We name ind $(n)$ the discrete logarithm of $n$ to the base $g$. Gyarmati ^[7] presented a large family of pseudorandom binary sequences using the discrete logarithms.

Proposition 1.1. Let $f(x)\in \mathbb{F}_p[x]$ be a polynomial of degree $l$, and define $E_{p-1} = (e_1, \cdots, e_{p-1})$ by

Then

Moreover, suppose that at least one of the following assumptions holds:

(i) $f$ is irreducible;

(ii) If $f$ has a factorization $f = \varphi_1^{\alpha_1}\varphi_2^{\alpha_2}\cdots \varphi_u^{\alpha_u}$ where $\alpha_i\in \mathbb{N}$ and $\varphi_i$ is irreducible over $\mathbb{F}_p$, then there exists a number $\beta$ such that exactly one or two $\varphi_i's$ have degree $\beta$;

(iii) $k = 2$;

(iv) $(4k)^l<p$ or $(4l)^k<p$.

Then we have

The first purpose of this paper is to give large families of pseudorandom binary sequences using the discrete logarithms.

Theorem 1.1. Let $f(x)\in \mathbb{F}_p[x]$ be a polynomial of degree $l$, and define $E_{p-1} = (e_1, \cdots, e_{p-1})$ by

where $\overline{n}$ is the inverse of $n$ modulo $p$ such that $n\overline{n}\equiv 1\ (\bmod\ p)$ and $1\leq \overline{n}\leq p-1$. Then

Moreover, if the congruence $xf(x)+1\equiv 0\ (\bmod\ p)$ has no solution, then for any $k\in \mathbb{N}$ we have

Corollary 1.1. Suppose that $p$ is a prime with $p\equiv3\ (\bmod\ 4)$, and $f(x) = xg^2(x)$ with $g(x)\in\mathbb{F}_p[x]$. Define $E_{p-1} = (e_1, \cdots, e_{p-1})$ by

Then

For any $k\in\mathbb{N}$, we have

Let $f, g$ be polynomials over $\mathbb{F}_p$. Define $\frac{f(n)}{g(n)} = f(n)g^{-1}(n)$ for $g(n)\neq 0$. Mérai ^[8] studied the distribution of $\frac{f(n)}{g(n)}$ in the residue classes modulo $p$ and gave nontrivial upper bounds for the well-distribution measure and correlation measure. We also generalize the sequence in Theorem 1.1 by adding a simple rational function.

Theorem 1.2. Suppose that $p$ is a prime number and $s < \log p$ is a positive integer. Let $f(x), g(x)\in\mathbb{F}_p[x]$ and let $0\leq a_1 < a_2 < \cdots < a_s\leq p-1$ be integers with $\gcd(g(x), (x-a_1)\cdots(x-a_s)) = 1$. Define $E_{p} = (e_1, \cdots, e_{p})$ by

Then

Moreover, if the congruence $(x-a_1)\cdots(x-a_s)f(x)+g(x)\equiv 0\ (\bmod\ p)$ has no solution and one of the following two conditions holds:

$\rm{(i)}$ $\min \{s, k\} \leq 2$ and $\max \{s, k\} \leq p-1$,

$\rm{(ii)}$ $(4 k)^{s} \leq p$ or $(4 s)^{k} \leq p$,

then for any $k\in \mathbb{N}$ we have

Hubert, Dartyge and Sárközy ^[9] wrote the first paper on pseudorandom binary lattices in 2006, since then, about 25 papers have been published in this field. One can refer to ^{[9,10,11,12,13,14,15,16]} for further related results and constructions. In ^[9], the definition of binary sequences is extended from one dimension to several dimensions by considering functions of type

where $I^{n}_{N}$ denotes the set of the $n$-dimensional vectors whose all coordinates are selected from the set $\{0, 1, \cdots, N-1\}$:

We say that $\eta$ is an $n$-dimensional binary $N$-lattice or briefly binary lattice. Let $k\in\mathbb{N}$ and let $\mathbf{u}_i \ (i = 1, \cdots, n)$ be the $n$-dimensional unit vector whose $i$-coordinate is $1$ and other coordinates are $0$. The measure of pseudorandomness of a binary lattice is defined as follows:

where the maximum is taken over all $n$-dimensional vectors $\mathbf{B} = (b_1, \cdots, b_n)$, $\mathbf{d}_1, \cdots, \mathbf{d}_k$, $\mathbf{T} = (t_1, \cdots, t_n)$ whose coordinates are non-negative integers, $b_1, \cdots, b_n$ are non-zero, $\mathbf{d}_1, \cdots, \mathbf{d}_k$ are distinct, and the points $j_1b_1\mathbf{u}_1+\cdots+j_nb_n\mathbf{u}_n+\mathbf{d}_i$ occurring in the multiple sum belong to $I_N^n$.

A binary lattice $\eta$ is said to have strong pseudorandom properties, or briefly, it is considered as a "good'' pseudorandom lattice if for fixed $n$, $k$ and "large''$N$, the measure $Q_k(\eta)$ is "small'' (much smaller, than the trivial upper bound $N^n$). Gyarmati, Mauduit and Sárközy gave the following constructions in ^[11].

Proposition 1.2. Let $p$ be an odd prime, $f(x, y)\in \mathbb{F}_p[x, y]$ be a polynomial of degree $l$. Suppose that $f(x, y)$ is square-free and it is not of the form $\prod\limits_{j = 1}^{r}f_j\left(\alpha_jx+\beta_jy\right)$, where $\alpha_j, \beta_j\in \mathbb{F}_p$ and $f_j(x)\in \mathbb{F}_p[x]$ for $j = 1, \cdots, r$. Assume that $k\in \mathbb{N}$ and one of the following conditions holds:

$a)$ $f(x, y)$ is irreducible,

$b)$ $k = 2$,

$c)$ $(4l)^{k}\leq p$.

Define $\eta: I_p^2\rightarrow \{-1, +1\}$ by

Then we have

The second purpose of this paper is to construct a large family of pseudorandom binary lattices using the discrete logarithms.

Theorem 1.3. Let $p$ be an odd prime, and let $f(x_1, \cdots, x_n)\in \mathbb{F}_p\left[x_1, \cdots, x_n\right]$ be a polynomial in $n$ variables. Define $\eta: I_{p-1}^n\rightarrow \{-1, +1\}$ by

where $R_p(z)$ denotes the unique $r\in\{0, 1, \cdots, p-1\}$ such that $z\equiv r(\bmod\ p)$. Then we have

2.   Proof of Theorem 1.1, Corollary 1.1 and Theorem 1.2.

We need the following lemmas.

Lemma 2.1. Let $p$ be a prime number, and let $\chi$ be a non-principal character modulo $p$ of order $d$. Suppose that $f(x)\in\mathbb{F}_p[x]$ has $s$ distinct roots in $\overline{\mathbb{F}}_p$, and $f(x)$ is not the constant multiple of the $d$-th power of a polynomial over $\mathbb{F}_p$. Let $y$ be real number with $0 < y\leq p$. Then for any $x\in\mathbb{R}$ we have

Proof. This is Lemma 2 in ^[7].

Lemma 2.2. Let $p$ be a prime number, and let $1\leq d\leq p-1$ with $d\mid p-1$. Then

Proof. This is Lemma 3 in ^[7].

Lemma 2.3. Suppose that $p$ is a prime number and $1\leq\delta_1, \cdots, \delta_k\leq p-2$, $0\leq d_1 < d_2 < \cdots < d_k < p$ are integers. Let $a_1, \cdots, a_s \in \mathbb{F}_p$ be distinct numbers and let

If one of the following two conditions holds:

$\rm{(i)}$ $\min \{s, k\} \leq 2$ and $\max \{s, k\} \leq p-1$,

$\rm{(ii)}$ $(4 k)^{s} \leq p$ or $(4 s)^{k} \leq p$,

then the polynomial

has a $(p-1-\delta_u)$-th root in $\mathbb{F}_p$.

Proof. From

we have if there exists a $c$ such that

has exactly one solution which is $(d_u, a_v)$ for some $1\leq u\leq k, 1\leq v\leq s$, then $a_v-d_u$ is a $(p-1-\delta_u)$-th root of the function $H(x)$.

Consider the sets $\mathcal{A} = \left\{a_{1}, a_{2}, \ldots, a_{s}\right\}, \mathcal{D} =$ $\left\{d_{1}, d_{2}, \ldots, d_{k}\right\}$. It was proved in ^[17]HY__HY, Theorem 2] that under any of the following conditions:

$\rm{(i)}$ $\min \{s, k\} \leq 2$ and $\max \{s, k\} \leq p-1$,

$\rm{(ii)}$ $(4 k)^{s} \leq p$ or $(4 s)^{k} \leq p$,

there is a $c \in \mathbb{Z}_{p}$ such that

has exactly one solution. Thus the statement of the lemma follows easily from this.

Now we prove Theorem 1.1. For $1\leq n\leq p-1$ with $\left(f(n)+\overline{n}, p\right) = 1$ we have

Therefore

For $a, b, t$ with $1\leq a\leq a+(t-1)b\leq p-1,$ by (2.1) we get

where the error term equals to the number of $n$ such that $\left(f(n)+\overline{n}, p\right) > 1$. Write $\delta = \hbox{ord}\ \chi$. From Lemma 2.1 we have

since the polynomial $(a+jb)^{\delta}f(a+jb)+(a+jb)^{\delta-1}$ has a zero $j = -a\overline{b}$ of order $\delta-1$. Hence from Lemma 2.2 we get

Therefore

Now we consider the correlation measure of $E_{p-1}$. We suppose that the congruence $xf(x)+1\equiv0\ (\bmod \ p)$ has no solution. For $0\leq d_1 < \cdots < d_k\leq p-1-M$, from (2.1) we have

Let $\chi^*$ be a generator of the group modulo $p$ characters, and let

Then

Since $xf(x)+1\equiv0\ (\bmod \ p)$ has no solution, $-d_{u}$ is the $(p-1-\delta_u)$-th zero of the polynomial

for $u = 1, 2, \cdots, k$. Thus this function is not the constant multiple of the $(p-1)$-th power of a polynomial over $\mathbb{F}_p$, from Lemma 2.1 we get

Combining (2.3), (2.5) and Lemma 2.2 we have

Therefore

This proves Theorem 1.1.

Now we prove Corollary 1.1. From $f(x) = x g^2(x)$ we get $x f(x) = \left(xg(x)\right)^2.$ Since $-1$ is a quadratic non-residue modulo $p$ for $p\equiv 3\ (\bmod \ 4)$, the congruence $xf(x)+1\equiv 0\ (\bmod \ p)$ has no solution. So, from Theorem 1.1, we conclude that

This completes the proof of Corollary 1.1.

Now we prove Theorem 1.2. For $1\leq n\leq p-1$ with $\left(f(n)+\frac{g(n)}{(n-a_1)\cdots (n-a_s)}, p\right) = 1$, we have

Therefore

and then

where the error term equals to the number of $n$ such that $\left(f(n)+\frac{g(n)}{(n-a_1)\cdots (n-a_s)}, p\right) > 1$. Since $\gcd(g(n), (n-a_1)\cdots(n-a_s)) = 1$ and $\delta = \hbox{ord}\ \chi$, we obtain the following estimate similar to (2.2).

Hence from Lemma 2.2 we get

Therefore

According to (2.3) and (2.4) we get a similar equality for the correlation measure of $E_{p}$ that

We assume that $(x-a_1)\cdots(x-a_s)f(x)+g(x)\equiv 0\ (\bmod \ p)$ has no solution, thus from this and Lemma 2.3 we obtain that the function

has a $(p-1-\delta_u)$-th root in $\mathbb{F}_p$. Then this function is not the constant multiple of the $(p-1)$-th power of a polynomial over $\mathbb{F}_p$, so from Lemmas 2.1 and 2.2 we have

Therefore,

This proves Theorem 1.2.

3.   Estimate of mixed exponential sums and proof of Theorem 1.3

We need the following estimates for mixed exponential sums to prove Theorem 1.2.

Lemma 3.1. Let $p$ be a prime number. Let $\psi$ be a nontrivial additive character and $\chi$ a multiplicative character of $\mathbb{F}_{p}$ of order $d$. Furthermore, let $F = \frac{f}{g}, Q = \frac{q}{r}$ be non-zero rational functions over $\mathbb{F}_{p}$ and let $s$ be the number of distinct zeros of $g$ in $\overline{\mathbb{F}}_{p}$. Assume that $\mathcal{S}$ is the set of poles of $F$ and $Q$. If one of the following conditions holds:

${\rm(i)}$ $g(x)\nmid f(x)$,

${\rm(ii)}$ $Q(x)$ is not of the form $b B(x)^{d}$ for any $b \in \mathbb{F}_{p}$ and $B(x) \in \mathbb{F}_{p}(x)$.

If $1 \leq N < p$, then we have

Proof. See Theorem 5 in ^[18].

Lemma 3.2. Assume that $p > 2$ is a prime, $\delta_1, \cdots, \delta_k$ are integers, and $\chi^*$ is a generator of the group of characters modulo $p$. Let $u_{1}, \cdots, u_{k}$ be integers with $\left(u_{1} \cdots u_{k}, p\right) = 1$, and let

be distinct vectors whose coordinates are integers. Suppose that $f(x)\in\mathbb{F}_p[x]$. Let $1\leq N < p$. For any integers $1\leq t_1, \cdots, t_n < N$ and $1\leq b_1, \cdots, b_n < p$, define

Then we have

Proof. This lemma can be proved by using the methods in ^[15] with slight modifications. For a completeness we give detailed proof. Without loss of generality, we may assume that $d_{11}, \cdots, d_{k 1}$ are not the same, since $\mathbf{d}_{1}, \cdots, \mathbf{d}_{k}$ are distinct. If there are $l$ distinct elements in $\{d_{11}, \cdots, d_{k 1}\}$, we find that

where $d_{i_{1} 1}, \cdots, d_{i_{l}1}$ are distinct. Then

Let

and define

where

It is not hard to see that

where the error term equals to the number of vectors $(x_2, \cdots, x_n)$ such that

Then we have

Define

and

We get

Since $-d_{i_{1} 1}, \ldots, -d_{i_{l} 1}$ are not zeros of $g(x)$, we have $z(x)\nmid g(x)$. There exist at most $k\deg(f)$ different roots for the function $f(j_1b_1+d_{11})^{\delta_1}\cdots f(j_1b_1+d_{k1})^{\delta_k}$. Thus we can use Lemma 3.1 to get

Therefore,

This completes the proof of Lemma 3.2.

Now we prove Theorem 1.3. For $x_1, \cdots, x_n$ with $\left(f(x_1)\cdots f(x_n), p\right) = 1$ we have

Therefore

Let $b_1, \cdots, b_n$ be positive integers, and write $\mathbf{d}_i = \left(d_{i1}, \cdots, d_{in}\right)$ for $i\in\{1, \cdots, k\}$. By (3.2) we get

Let $\chi^*$ be a generator of the group of characters modulo $p$, and let $\chi_u = \left(\chi^*\right)^{\delta_u}$, where $1\leq \delta_u\leq p-1$ for $u\in\{1, 2, \cdots, k\}$. From Lemma 3.2 we have

Then combining (3.3) and (3.4) we get

where $\left < \theta\right > = \min\left(\theta-\lfloor\theta\rfloor, \ 1-\left(\theta-\lfloor\theta\rfloor\right)\right)$ denotes the distance from $\theta$ to nearest integer. Noting that

Combining (3.5) and (3.6) we obtain

Therefore,

This completes the proof of Theorem 1.3.

4.   Conclusions

In this paper, a method is given for the application of primitive characters modulo $p$ and the estimates of both character sums and mixed exponential sums to the estimates of pseudorandom measures. The binary sequences in Theorem 1.1, Corollary 1.1 and Theorem 1.2 are demonstrated to be pseudorandom, since the upper bounds of both the well-distribution measure and the correlation measure of those sequences are $o(p)$ as $p\rightarrow \infty$. With the growth of the number of dimensions, the error term of the pseudorandom measure in (3.3) is up to $k\deg(f)p^{n-1}$, thus the result in Theorem 1.3 is the best one by now which is based on Lemma 3.2.

Acknowledgments

The authors express their gratitude to the referee for his/her helpful and detailed comments. This work is supported by National Natural Science Foundation of China under Grant No. 12071368, and the Science and Technology Program of Shaanxi Province of China under Grant No. 2019JM-573 and 2020JM-026.

Conflict of interest

The authors declare that there are no conflicts of interest regarding the publication of this paper.