Consecutive non-square non-primitive pairs in a Finite Field
Stephen D. Cohen · 2026
Read Consecutive non-square non-primitive pairs in a Finite Field by Stephen D. Cohen (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-21429.txt.
Introduction
Stephen Cohen shows that a finite field holds consecutive elements that are both non-squares and non-primitive whenever a totient density ratio falls below one-third. The same holds when the ratio equals one-third outside five small exceptional fields. This extends a prime-field result that needed a stronger one-quarter bound. More generally, with the ratio at most one-third, the field holds consecutive non-squares that are also powers for the least odd prime divisor, except for six small fields.
Catalog record
| CREATOR | Stephen D. Cohen |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28305 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.21429
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Consecutive non-square non-primitive pairs in a Finite Field Stephen D. Cohen Abstract . Let q q be an odd prime power and write θ q := ϕ ( q − 1 ) q − 1 . \theta_{q}:=\frac{\phi(q-1)}{q-1}. If θ q < 1 3 \theta_{q}<\tfrac{1}{3} , or if θ q = 1 3 \theta_{q}=\tfrac{1}{3} and q ∉ { 7 , 13 , 19 , 25 , 37 } q\notin\{7,13,19,25,37\} , then the finite field 𝔽 q \mathbb{F}_{q} contains a pair of consecutive elements that are both non-square and non-primitive. This extends a result of Jarso and Trudgian for prime fields 𝔽 p \mathbb{F}_{p} , where the same conclusion was obtained under the stronger condition θ p ≤ 1 4 \theta_{p}\leq\tfrac{1}{4} . More generally, let ℓ \ell be the least odd prime divisor of q − 1 q-1 . If θ q ≤ 1 3 \theta_{q}\leq\tfrac{1}{3} , then 𝔽 q \mathbb{F}_{q} contains a pair of consecutive elements that are non-squares and ℓ \ell th powers, with the sole exceptions q ∈ { 7 , 13 , 19 , 25 , 37 , 43 } q\in\{7,13,19,25,37,43\} . 2020 Mathematics Subject Classification Primary 11T30; Secondary 11T24 1. Introduction Let \mathbb{F}_{q} denote the finite field of order q . In a series of papers published in 1985, the author [ 3 , 4 , 5 ] proved that, provided q\neq 2,3,7 , the field \mathbb{F}_{q} contains a consecutive pair of primitive elements. Many related existence results have since been obtained. A natural complementary question is whether there always exists a consecutive pair of non-primitive elements. When q is odd, this question requires some qualification: exactly half of the non-zero elements of \mathbb{F}_{q} are squares, and hence already non-primitive. It is easy to see that, for q>3 , there exist consecutive non-squares. The deeper question is whether there exists a consecutive pair of elements that are both non-square and non-primitive. From now on, assume q is an odd prime power and define \theta_{q}:=\frac{\phi(q-1)}{q-1}. We call an element of \mathbb{F}_{q} NSNP if it is both a non-square and non-primitive. An NSNP pair is a pair of consecutive NSNP elements. If \theta_{q}=1/2 , then every non-square is primitive; this occurs precisely when q is a Fermat prime or q=9 . In these cases, no NSNP elements (and therefore no NSNP pairs) exist. Thus some restriction on \theta_{q} is necessary. For prime fields \mathbb{F}_{p} , the problem has been studied in terms of congruences modulo p . By elementary methods, Gun, Ramakrishnan, Sahu, and Thangadurai [ 8 ] proved that if \theta_{p}<1/6 , then \mathbb{F}_{p} contains an NSNP pair. Using more elaborate sieving methods, Jarso and Trudgian [ 9 ] improved this to the weaker condition \theta_{p}\leq 1/4 . Previously, Gun, Luca, Rath, Sahu, and Thangadurai [ 7 ] had shown via character sum estimates, as a particular case of a more general result, that for sufficiently large primes p , an NSNP pair exists whenever \theta_{p}<1/2-\varepsilon . When \varepsilon=1/6 (so that \theta_{p}<1/3 ), the argument in [ 7 ] appears to require a bound as large as p>10^{430} to guarantee the existence of an NSNP pair. We call an element of \mathbb{F}_{q} NSNP if it is both a non-square and non-primitive. An NSNP pair is a pair of consecutive NSNP elements. If \theta_{q}=1/2 , then every non-square is primitive; this occurs precisely when q is a Fermat prime or q=9 . In these cases, no NSNP elements (and therefore no NSNP pairs) exist. Thus some restriction on \theta_{q} is necessary. Our main result is the following. Theorem 1.1 . Let q be an odd prime power and define \theta_{q}:=\frac{\phi(q-1)}{q-1}. If \theta_{q}<\tfrac{1}{3} , then \mathbb{F}_{q} contains a pair of consecutive elements that are both non-square and non-primitive. If \theta_{q}=\tfrac{1}{3} , then the same conclusion holds except when q\in\{7,13,19,25,37\}. To establish Theorem 1.1 , we study a more general problem. Let \ell be an odd prime dividing q-1 . We say that an element of \mathbb{F}_{q} is an NS \ell element if it is both a non-square and an \ell th power, and define an NS \ell pair analogously. Clearly, every NS \ell pair is an NSNP pair. We prove the following general result, in which \ell is taken to be the least odd prime divisor of q-1 . Theorem 1.2 . Let q be an odd prime power such that \theta_{q}\leq\tfrac{1}{3} , and let \ell be the least odd prime divisor of q-1 . Then, except when \ell=3 and q\in\{7,13,19,25,37,43\}, the field \mathbb{F}_{q} contains an NS \ell pair. Remark 1.1 . The exceptional values of q in Theorem 1.1 correspond precisely to those for which \theta_{q}=\tfrac{1}{3} and no NSNP pair exists. Remark 1.2 . From Theorem 1.1 , \theta_{q}=1/3 represents a critical boundary value. All the exceptional prime powers q have this value of \theta_{q} . To interpret the hypotheses, observe that \theta_{q} is the proportion of primitive elements in \mathbb{F}_{q}^{\times} . Since exactly half of \mathbb{F}_{q}^{\times} consists of non-squares, the proportion of NSNP elements is \frac{1}{2}-\theta_{q}. Thus: • \theta_{q}<1/6 (as in [ 8 ] ) implies NSNP elements are at least twice as numerous as primitive elements; • \theta_{q}\leq 1/4 (as in [ 9 ] ) implies NSNP elements are at least as numerous as primitive elements; • \theta_{q}\leq 1/3 (this paper) implies NSNP elements are at least half as numerous as primitive elements. The existence problem for NSNP pairs is therefore comparable in difficulty to the existence of consecutive primitive pairs. However, primitive elements have a simpler multiplicative structure, and (lower-bound) sieve methods apply more naturally to them. For NSNPs, appropriate upper-bound sieves seem not to be available. It is therefore natural to fix a prime \ell\mid(q-1) and study the existence of consecutive pairs of elements that are both non-squares and \ell th powers. We call such a pair an NS \ell pair . We first treat general \ell , and then specialise to the key small primes \ell=3 and \ell=5 . Remark 1.3 . For later reference, we record which relevant values of \theta_{q} occur for odd prime powers q : • \theta_{q}=1/2 if and only if q is a Fermat prime or q=9 ; • \theta_{q}=1/3 if and only if q-1=2^{a}3^{b} with a,b\geq 1 ; • \theta_{q}\neq 1/4 and \theta_{q}\neq 1/6 , since neither 4 nor 6 is the Euler totient of any integer of the form q-1 with q an odd prime power. 2. A lower bound for the number of NS \ell pairs Let q be an odd prime power, and let \ell be an odd prime dividing q-1 . Since \mathbb{F}_{q}^{\times} is cyclic of order q-1 , there exists a multiplicative character \eta of exact order \ell . Let \lambda denote the quadratic character of \mathbb{F}_{q}^{\times} . Extend both \lambda and \eta to \mathbb{F}_{q} by setting \lambda(0)=0 and \eta(0)=0 . With this convention, all character sums over \mathbb{F}_{q} are well-defined (see [ 2 ] ). We seek a lower bound for N_{\ell}(q)=\#\{\alpha\in\mathbb{F}_{q}:\alpha,\alpha+1\text{ are both non-squares and $\ell$th powers}\}. Define the characteristic function of elements of \mathbb{F}_{q} that are both non-squares and \ell th powers as follows: f_{\ell}(\alpha)=\frac{1}{2\ell}\,(1-\lambda(\alpha))\sum_{i=0}^{\ell-1}\eta^{i}(\alpha). It follows that N_{\ell}(q)=\sum_{\alpha\in\mathbb{F}_{q}\setminus\{0,-1\}}f_{\ell}(\alpha)f_{\ell}(\alpha+1). The exclusion of \{0,-1\} is harmless, since f_{\ell}(0)=0 and f_{\ell}(\alpha+1)=0 when \alpha=-1 . Expanding f_{\ell}(\alpha)f_{\ell}(\alpha+1) gives N_{\ell}(q)=\frac{1}{4\ell^{2}}\sum_{i,j=0}^{\ell-1}S(i,j), where (2.1) S(i,j)=J(\eta^{i},\eta^{j})-\lambda(-1)J(\lambda\eta^{i},\eta^{j})-J(\eta^{i},\lambda\eta^{j})+\lambda(-1)J(\lambda\eta^{i},\lambda\eta^{j}).