On the distribution of primitive roots and Lehmer numbers

1.   Introduction

Let $q$ be a power of odd prime. Several researchers have looked into a variety of properties about the primitive roots modulo $q$. Let $g_1, g_2$ represent two primitive roots modulo $q$, $a$, $b$ and $c$ represent arbitrary non-zero elements in $\mathbb{F}_q$. Is there some $q_0$ such that for all $q > q_0$, there is always one representation

For $b = 1$ and $c = -1$, Vegh ^[1] considered a specific form of Eq (1.1), which is known as Vegh's Conjecture, (see [2,§ F9] for further details). Cohen ^[3] demonstrated Vegh's Conjecture for all $q > 7$.

For $b = 1$ and $c = 1$, Golomb ^[4] proposed another specific form of Eq (1.1). This was proved by Sun ^[5] for $q > 2^{60}\approx 1.15\times 10^{18}$.

Moreover, Cohen et al. ^[6] studied linear sums of primitive roots and their inverses in finite fields $\mathbb{F}_q$ and showed that if $q > 13$, then for arbitrary non-zero $a, b \in \mathbb{F}_q$, there is a pair of primitive elements ($g_1$, $g_2$) of $\mathbb{F}_q$ such that both $ag_1+bg_2$ and $ag^{-1}_1+bg^{-1}_2$ are primitive.

Let $p$ be an odd prime. Carlitz ^[7] relied on some results of Davenport and obtained for any $k-1$ fixed integers $c_1, c_2, \ldots, c_{k-1}$ with $c_i \geq 1 (i = 1, 2, \ldots, k-1)$. Let $g, g_1, \ldots, g_{k-1}$ be primitive roots modulo $p$ and $N_k$ denote the number of $g\bmod p$ such that $g_1-g = c_1, \ldots, g_{k-1}-g = c_{k-1}$. Then

More results of the primitive roots distribution can be found in ^[8,9,10,11].

Lehmer [2,§ F12] proposed the definition of $Lehmer~~ number$, according to which $a$ is a $Lehmer ~~number$ if and only if $a$ and $\bar{a}$ have opposite parity, i.e., $(2, a+\bar{a}) = 1$, where $\bar{a}$ is the multiplicative inverse of $a$ modulo $p$. It is simple to demonstrate that there are no Lehmer numbers modulo $p$ when $p = 3$ or $7$. Zhang ^[12] established that if $M_p$ denotes the number of Lehmer numbers modulo $p$, then

A Lehmer number that is also a primitive root modulo $p$ will be called a $Lehmer~~ primitive~~ root$ or an $LPR$. The inverse of an $LPR$ is also an $LPR$. We assume that $p > 3$ because there is no Lehmer number modulo $3$. Wang and Wang ^[13] investigated the distribution of $LPRs$ involving Golomb's conjecture. Let $G_p$ denote the number of Golomb pairs $(a, b)$ (i.e., $a+b\equiv 1(\bmod\; p)$) are $LPRs$. They showed

Let $N_p$ denote the number of $LPRs$ modulo $p$. For odd integers $m\geq 3$, define the positive number $T_m$ by

Cohen and Trudgian ^[14] improved the result of Wang and Wang ^[13] and showed

and

where $\frac{2}{\pi}\left(1+\frac{0.548}{\ln p}\right) < T_p < \frac{2}{\pi}\left(1+\frac{1.549}{\ln p}\right)$.

Specifically, they obtained that for an odd prime $p(\neq 3, 7)$, there exists an $LPR$ modulo $p$.

Inspired by the results of Cohen and Trudgian ^[14] and Wang and Wang ^[13], we mainly studied the distribution of $LPRs$ modulo $p$ related to the Golomb's conjecture in two aspects. On the one hand, we extend Eq (1.1) to the case involving $k > 1$ variables. Let $\mathcal{R}$ be set of $LPRs$ modulo $p$ that is a subset of ${\mathbb{F}}_p$. $a_1, a_2, \ldots, a_k, c$ are non-zero elements in ${\mathbb{F}}_p$ and $N(\mathcal{R}, p)$ denotes the number of solutions of the equation

We consider the distribution properties of $N(\mathcal{R}, p)$, and obtain the following:

Theorem 1. Let $p > 3$ be an odd prime. Then we have

where the symbol $\mathrm{O}$ is dependent on $k$.

When $k = 2$, we can obtain the number of the Golomb pairs that are $LPRs$.

On the other hand, we consider the distribution of $k$ consecutive $LPRs$ and generalize it to a more general form.

Let $f(x)\in \mathbb{F}_p[x]$. Define

Then we have:

Theorem 2. Let $f(x)\in \mathbb{F}_p[x]$ with degree $l\geq 1$. $c_1, c_2, \ldots, c_k$ are distinct elements in $\mathbb{F}_p$. Suppose that one of the following conditions holds:

$\rm (i)$ $f(x)$ is irreducible,

$\rm (ii)$ $f(x)$ has no multiple zero in $\bar{\mathbb{F}}_p$ and $k = 2$,

$\rm (iii)$ $f(x)$ has no multiple zero in $\bar{\mathbb{F}}_p$ and $(4k)^{l} < p$.

Then we have

where the symbol $\mathrm{O}$ is dependent on $k$ and $l$.

Take $f(x) = x$, $c_k = 0$ in Theorem 2. Then we can get the number of $k$ consecutive primitive roots $x, x+c_1, \ldots, x+c_{k-1}$ are Lehmer numbers, which is:

Corollary 1. Let $p$ be an odd prime. Then for any $1\leq\ x\leq(p-1)$ that is an LPR modulo $p$, we have

where the symbol $\mathrm{O}$ is dependent on $k$.

When $k = 1, 2$, we can easily deduce the Theorem 1 and Theorem 6 in Cohen and Trudgian ^[14], respectively.

Notation: Throughout this paper, $\mathbb{F}_q$ denotes a finite field of characteristic $p$, $\bar{\mathbb{F}}_q$ denotes the algebraic closure of $\mathbb{F}_q$, $\phi(n)$ is reserved for the Euler function, $\mu(n)$ is the M$\ddot{o}$bius function. We use $\omega(n)$ to denote the number of all distinct prime divisors of $n$. Write $\sum_{\chi_d}$ to denote a sum over all $\phi(d)$ multiplicative characters $\chi_d$ of order $d$ over ${\mathbb{F}}_p$, and denote by $\mathop{\sum_{n = 1}^{p}}^{'}$ the summation of $1\leq n\leq p$ with $(n, p) = 1$. $\tau(\chi)$ is the classical Gauss sums associated with character $\chi$ mudulo $p$. $f\ll g$ means $|f|\leq cg$ with some positive constant $c$, $f = \mathrm{O}(g)$ means $f\ll g$.

2.   Some lemmas

To complete the proof of the theorems, we need following several lemmas. The proofs of these lemmas require some basic knowledge of analytic number theory, which can be found in ^[15].

Lemma 1. Let $p$ be an odd prime. Then for any integer $a$ coprime to $p$ (i.e., $(a, p) = 1$), we have the identity

Proof. See Proposition 2.2 of Narkiewicz ^[16]. □

Lemma 2. Let $p$ be an odd prime, $\chi$ be a nonprincipal multiplicative character modulo $p$ of order $d$. Suppose $g(x)\in \mathbb{F}_p[x]$ has precisely $m$ distinct ones among its zeros, and suppose that $g(x)$ is not the constant multiple of a $d$-th power over $\mathbb{F}_q$. Then

Proof. See Theorem 2C in Chapter 2 of Schmidt ^[17]. □

Lemma 3. Let $\mathbb{F}_q$ be a finite field of characteristic $p$, $\psi$ be a nontrivial additive character and $\chi$ be a nonprincipal multiplicative character on $\mathbb{F}_q$ of order $d$. For two rational functions $f(x), g(x)\in\mathbb{F}_q[x]$, define $K(\psi, f;\chi, g) = \sum_{x\in\mathbb{F}_q\backslash S}\chi(g(x))\psi(f(x))$, where $S$ denotes the set of poles of $f(x)$ and $g(x)$. Suppose the following conditions hold:

$\rm (i)$ $g(x)$ is not the constant multiple of a $d$-th power over $\mathbb{F}_q$.

$\rm (ii)$ $f(x)$ is not of the form $(h(x))^p-h(x)$ with a rational function $h(x)$ over $\mathbb{F}_q$.

Then we have

where $m$ is the number of distinct roots and (noninfinite) poles of $g(x)$ in $\mathbb{F}_q$.

Proof. See Theorem 2G in Chapter 2 of Schmidt ^[17]. □

Lemma 4. Let $p$ be an odd prime. Let $c_1, \cdots, c_k$ be distinct elements in $\mathbb{F}_p$. Assume that $f(x)\in\mathbb{F}_{p}[x]$ with $\deg(f) = l$. Define the polynomial

Suppose one of the following conditions holds:

$\rm (i)$ $f(x)$ is irreducible,

$\rm (ii)$ $f(x)$ has no multiple zero in $\bar{\mathbb{F}}_p$ and $k = 2$,

$\rm (iii)$ $f(x)$ has no multiple zero in $\bar{\mathbb{F}}_p$ and $(4k)^{l} < p$.

Then $h(x)$ has at least one simple root in $\bar{\mathbb{F}}_p$.

Proof. Suppose that $f(x)$ is irreducible. Then $f(x+c_1), \cdots, f(x+c_k)$ are distinct irreducible polynomials, and $h(x)$ has at least $k$ simple roots in $\bar{\mathbb{F}}_p$. The cases of $\rm (ii)$ and $\rm (iii)$ can be proved by Theorem 2 and Lemma 2 of ^[18], for $k = 2$ or $(4k)^{l} < p$, $(l, k, p)$ is "admissible triple, " then $f(x+c_1)\cdots f(x+c_k)$ has at least one simple root. □

Lemma 5. Let $p$ be an odd prime, $m_1, \ldots, m_k, n_1, \ldots, n_k$ be integers with $(m_1\cdots m_kn_1\cdots n_k, p) = 1$, and polynomials $g(x), f_1(x), \ldots, f_k(x)\in\mathbb{F}_p[x]$. Let $\chi$ be a Dirichlet character modulo $p$ of order $d$. Define

Suppose the following conditions hold:

$\rm (i)$ $g(x)$ can not be the constant multiple of a $d$-th power over $\mathbb{F}_p$.

$\rm (ii)$ $F(x) = f_1(x)\cdots f_k(x)$ has at least one simple root in $\bar{\mathbb{F}}_p$.

Then we have

where $e(x) = e^{2\pi ix}$ and $l$ is the number of distinct roots of $g(x)$ in $\bar{\mathbb{F}}_p$.

Proof. It is clear that

Condition $\rm (i)$ is the same as Lemma 3. So our goal is to prove the rational function $G(x)/F(x)$ satisfies condition $\rm (ii)$ in Lemma 3 if $F(x)$ has a simple root in $\bar{\mathbb{F}}_p$. Assume that there are polynomials $K(x), L(x)\in\mathbb{F}_p[x]$ with $(K(x), L(x)) = 1$ such that

Then we have

Since $F(x) = f_1(x)\cdots f_k(x)$ has at least one simple root in $\bar{\mathbb{F}}_p$, then there exists an irreducible polynomial $w(x)\in\mathbb{F}_p[x]$ such that $w(x)\mid F(x)$ and $w(x)^2\nmid F(x)$. Assume that $w(x)\mid f_1(x)$, then we have

Hence, from Eq (2.1)

which contradicts to $(K(x), L(x)) = 1$. Therefore, from Lemma 3 we get

where $l$ is the number of distinct roots of $g(x)$ in $\bar{\mathbb{F}}_p$. □

Lemma 6. Let $\chi$ be a primitive character modulo $p$, $\chi_{d_i}$ be character modulo $p$ of order $d_i$. There exist some $1\leq s_i\leq d_i$ with $(s_i, d_i) = 1$, $i = 1, 2, \ldots, k$. Then we have

Proof. From the definition of the Dirichlet character modulo $p$, we can get

where $\text{ind}(a)$ denotes an index of $a$ with base $g$ of modulo $p$, and $g$ is a positive primitive root of modulo $p$. □

3.   Proofs of the theorems

Firstly, we prove the Theorem 1. Let $p$ be an odd prime, $k$ be any fixed positive integer. Then for any $k$ different integers $a_1, \ a_2, \ldots, a_k \in {\mathbb{F}}_p$, from Lemma 1 and the definition of Lehmer number we have

where $l_i = (-1)^{g_i+\overline{g_i}}, i = 1, 2, \cdots, k$.

From Eq (3.2), let

Using the properties of Gauss sums we can get

where we have used the fact that $\sum_{d|n}|\mu(d)| = 2^{\omega(n)}$.

Hence, Eq (3.2) and the above formulae yield that

Then we compute $A_2$ in Eq (3.1). For simplicity, let

noting that

Hence,

Noting that, if $m = 0$, then $\sum_{u = 1}^{p-1}(-1)^ue\left(\frac{-mu}{p}\right) = \sum_{u = 1}^{p-1}(-1)^u = 0$, since $p$ is odd. Hence,

From the above discussion and Eq (3.1), we can obtain

Summing the above formula for $t$ from 1 to $k$, then the last term of Eq (3.6) is

here we have utilized $T^2_p < \frac{4}{\pi^2}\left(1+\frac{1.549}{\ln p}\right)^2 < 2.4$ and the results in Wang and Wang (see Lemma 2.2 of ^[13]) that

Similarly, note that $\sum_{d|n}|\mu(d)| = 2^{\omega(n)}$ and we can get the estimate of the other terms of Eq (3.6). Then we have

Inserting Eqs (3.3) and (3.7) into (3.1), we can deduce that

This proves the Theorem 1.

Now we prove the Theorem 2. Let $\mathcal{A}$ denote the set of integers $1\leq x\leq p$ such that

By the definition of primitive roots and Lehmer number, it follows that

where $g_i = (-1)^{f(x+c_i)+\overline{f(x+c_i)}}, i = 1, 2, \ldots, k$.

Obviously,

From Lemma 6 we have

Due to $d_1d_2\cdots d_k > 1$, and

from Lemma 4 we can get that the polynomial

has a root in $\bar{\mathbb{F}}_p$ with multiples less than $p-1$, thus it can not be multiple of a $(p-1)$-th power of polynomial over $\mathbb{F}_p$. Take $g(x) = (f(x+c_1))^{\frac{s_1(p-1)}{d_1}}\cdots(f(x+c_k))^{\frac{s_k(p-1)}{d_k}}$, in Lemma 2 we have

Hence, we have

Using the methods in the proof of Theorem 1 we have

From the above discussion and Lemma 5, we can obtain

Combing Eqs (3.8), (3.9) and (3.10) we have

Then we have

This complete the proof of Theorem 2.

4.   Conclusions

From two perspectives, this paper consider the distribution of $LPRs$ that are related to the generalized Golomb's conjecture. Theorem 1 extends the binary linear equation $ag_1+bg_2 = c$ to the multivariate linear equation $a_1g_1+a_2g_2+\cdots+a_kg_k = c$, and uses the properties of Gauss sums to derive an asymptotic formula for the number of its solutions $g_1, g_2, \ldots, g_k$ that are $LPRs$. Theorem 2 considers $k$ consecutive $LPRs$ and employs the upper bound estimation of the generalized Kloosterman sums to provide a more general result that for $f(x)\in {\mathbb{F}}_p[x]$, $k$ polynomials $f(x+c_1), f(x+c_2), \ldots, f(x+c_k)$ are Lehmer primitive roots modulo $p$.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The author gratefully appreciates the referees and academic editor for their helpful and detailed comments.

This work is supported by the N. S. F. (12126357) of P. R. China and the Natural Science Basic Research Plan in Shaanxi Province of China (2023-JC-QN-0050).

Conflict of interest

The author declare there are no conflicts of interest.