🔢 mathematics

Consecutive non-square nom-primitive pairs in as finite field

This paper establishes that finite fields $\mathbb{F}_q$ with odd prime power $q$ contain consecutive elements that are both non-square and non-primitive (or non-square and $\ell$ -th powers) under the condition $\theta_q \le \frac{1}{3}$ , thereby extending previous results for prime fields to a broader class of finite fields with only a few specific exceptions.

Original authors: Stephen D. Cohen

Published 2026-04-24

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Stephen D. Cohen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a giant, finite party called The Finite Field ( $F_q$ ).

In this party, there are $q$ guests. Every guest has a special ID card that tells us two things about them:

Are they a "Square"? (Think of this as wearing a specific type of hat. Exactly half the guests wear this hat; the other half don't.)
Are they "Primitive"? (This is the VIP status. A primitive guest is the "King" of the party; they can generate the entire guest list just by taking steps around the room. Most guests are not Kings.)

The Big Question

The mathematician Stephen Cohen is asking a very specific question about this party:

"Can we always find two guests standing right next to each other (consecutive numbers like 5 and 6) who are BOTH wearing the 'No Hat' (Non-Square) AND are NOT the King (Non-Primitive)?"

He calls these special pairs "NSNP Pairs" (Non-Square, Non-Primitive Pairs).

The Problem with the "VIP Ratio"

The difficulty of finding these pairs depends on how many "Kings" (Primitive elements) are at the party.

If there are too many Kings, almost everyone is a King. If you aren't a King, you must be wearing the Hat (a Square). In this case, you can't find a "No Hat, Not King" person.
If there are fewer Kings, it becomes easier to find people who are neither Kings nor wearing Hats.

The author uses a special number, $\theta_q$ (Theta), to measure the "King Density."

High $\theta_q$ : Too many Kings. No NSNP pairs exist.
Low $\theta_q$ : Fewer Kings. NSNP pairs likely exist.

The Discovery

Previous mathematicians had found that if the King Density ( $\theta$ ) was very low (less than 1/4), you could definitely find these pairs.

Stephen Cohen's breakthrough is proving that you can find these pairs even if the King Density is higher—up to 1/3.

Think of it like this:

Old Rule: "If Kings make up less than 25% of the crowd, we can find two 'No Hat, Not King' neighbors."
New Rule: "We can find them even if Kings make up as much as 33% of the crowd!"

The "Exception List" (The Party Crashes)

However, math is rarely perfect. Cohen found that while the rule works for almost every party size, there are a few specific party sizes (numbers like 7, 13, 19, 25, 37) where the rule breaks.

In these specific small parties, even though the King Density is low enough, the guests are arranged in a way that no two "No Hat, Not King" neighbors exist.
It's like a puzzle where the pieces fit together perfectly to block the solution, but only for these specific small numbers.

How Did He Solve It?

Cohen didn't just guess; he used a mix of heavy math tools and detective work:

The "Sieve" Method (The Net):
He used a mathematical "net" (called character sums and Jacobi sums) to cast over the party. This net is designed to catch the specific type of guest he's looking for. He proved that if the party is big enough, the net must catch at least one pair.
The "Small Party" Detective Work:
For the smaller parties where the "net" isn't strong enough to guarantee a catch, he went in and checked them one by one (using computers).
- He checked the "small" parties (like $q=7, 13, 19...$ ).
- He found that for most of them, the pairs do exist.
- He confirmed that for the "Exception List" (7, 13, 19, 25, 37), the pairs do not exist.
The "Special Case" of 43:
There was one tricky number, 43. The general rule for "Non-Square, Non-Cube" pairs failed here, but Cohen dug deeper and found a specific pair (7 and 8) that works for the main rule. So, 43 was removed from the "Exception List" for the main theorem.

Why Does This Matter?

You might ask, "Who cares about two neighbors at a math party?"

This is about predictability in randomness.

Primitive elements are the "generators" of the universe of numbers. They are the most useful, powerful numbers.
Non-primitive elements are the "ordinary" numbers.
Finding two ordinary numbers standing next to each other is a fundamental test of how numbers are distributed.

If we can prove these pairs exist under these conditions, it helps mathematicians understand the hidden structure of numbers, which is crucial for things like cryptography (locking and unlocking digital secrets) and coding theory (sending messages without errors).

Summary in a Nutshell

Stephen Cohen proved that in almost any finite world of numbers, as long as there aren't too many "special" numbers (Kings), you are guaranteed to find two "ordinary" numbers standing side-by-side. He pushed the limit of "how many Kings is too many" from 25% up to 33%, and he made a detailed map of the few tiny worlds where this rule doesn't apply.

1. Problem Statement

The paper investigates the existence of consecutive pairs of elements in a finite field $\mathbb{F}_q$ (where $q$ is an odd prime power) that satisfy two specific properties simultaneously:

Non-Square (NS): The element is not a quadratic residue in $\mathbb{F}_q$ .
Non-Primitive (NP): The element is not a generator of the multiplicative group $\mathbb{F}_q^*$ .

Such an element is termed NSNP. The goal is to determine conditions under which $\mathbb{F}_q$ contains a pair $(\alpha, \alpha+1)$ where both $\alpha$ and $\alpha+1$ are NSNP.

Context:

If $\theta_q = \frac{\phi(q-1)}{q-1} = 1/2$ (occurring when $q$ is a Fermat prime or $q=9$ ), every non-square is primitive. Thus, no NSNP elements exist.
Previous results established existence for prime fields $\mathbb{F}_p$ under the condition $\theta_p \le 1/4$ (Jarso and Trudgian) or $\theta_p < 1/6$ (Gun et al.).
The paper aims to extend these results to general finite fields $\mathbb{F}_q$ and improve the bound on $\theta_q$ .

2. Methodology

The author employs a combination of analytic number theory techniques and computational verification.

A. Character Sums and Jacobi Sums

To count the number of NS $\ell$ pairs (elements that are non-squares and $\ell$ -th powers), the author defines a characteristic function $f_\ell(\alpha)$ using the quadratic character $\lambda$ and a multiplicative character $\eta$ of order $\ell$ .
The count $N_\ell(q)$ is expressed as a sum over $\mathbb{F}_q$ :
$N_\ell(q) = \sum_{\alpha \in \mathbb{F}_q \setminus \{0, -1\}} f_\ell(\alpha)f_\ell(\alpha+1)$
Expanding this product leads to a linear combination of Jacobi sums $J(\chi_1, \chi_2)$ .

Bounding Strategy: The author utilizes the standard bound $|J(\chi_1, \chi_2)| = \sqrt{q}$ for non-trivial characters. By separating the trivial cases (where the sum equals $-1$ or $q$ ) from the non-trivial cases, a lower bound for $N_\ell(q)$ is derived:
$N_\ell(q) \ge \frac{q - 4(\ell-1)^2\sqrt{q} - C}{4\ell^2}$
where $C$ is a small constant depending on $\ell$ and $\lambda(-1)$ .
Corollary: If $q > 16\ell^4$ , then $N_\ell(q) > 0$ , guaranteeing the existence of such pairs.

B. Cyclotomic Numbers

For small values of $\ell$ (specifically $\ell=3$ and $\ell=5$ ), the analytic lower bounds are insufficient to cover all small $q$ . The author switches to Cyclotomic Numbers of order $2\ell$ .

The number of NS $\ell$ pairs corresponds exactly to the cyclotomic number $(\ell, \ell)_{2\ell}$ .
The author utilizes explicit formulas for these numbers (based on Gauss, Jacobi, and Whiteman) which depend on the representation of $q$ (e.g., $q = A^2 + 3B^2$ for $\ell=3$ ) and the index of the element 2.
This allows for the exact calculation of $N_3(q)$ and $N_5(q)$ for specific small prime powers.

C. Computational Verification

For the "exceptional" small values of $q$ where theoretical bounds fail or are inconclusive, the author performs direct computations using Pari/GP.

For $\ell=3$ , all $q < 269$ satisfying the conditions were checked.
For $\ell=5$ , specific candidates ( $q \in \{911, 1331, 2381, 3221, 3851\}$ ) were verified computationally.

3. Key Contributions and Results

Main Theorem (Theorem 1.1)

The paper establishes that for an odd prime power $q$ :

If $\theta_q < 1/3$ , $\mathbb{F}_q$ always contains a consecutive NSNP pair.
If $\theta_q = 1/3$ , $\mathbb{F}_q$ contains such a pair except when $q \in \{7, 13, 19, 25, 37\}$ .

This improves upon previous results by relaxing the condition from $\theta_q \le 1/4$ to $\theta_q \le 1/3$ .

Generalized Result (Theorem 1.2)

The author proves a more general result regarding NS $\ell$ pairs (non-squares and $\ell$ -th powers), where $\ell$ is the least odd prime divisor of $q-1$ .

If $\theta_q \le 1/3$ , an NS $\ell$ pair exists, with exceptions only when $\ell=3$ and $q \in \{7, 13, 19, 25, 37, 43\}$ .
Significance of $q=43$ : While $q=43$ is an exception for NS3 pairs (no consecutive non-squares that are also cubes), it is not an exception for NSNP pairs. The author proves that $(7, 8)$ is an NSNP pair in $\mathbb{F}_{43}$ because 7 is a non-square 7th power and 8 is a non-square cube.

Detailed Analysis of Cases

Case $\ell \ge 7$ : The analytic bound $q > 16\ell^4$ is easily satisfied for $\theta_q \le 1/3$ . The paper proves that if the least prime divisor is $\ge 7$ , the existence is guaranteed without exceptions.
Case $\ell = 3$ : The paper provides a complete classification. It lists 29 small prime powers where $3 | (q-1)$ and $\theta_q \le 1/3$ . It proves existence for all except $\{7, 13, 19, 25, 37, 43\}$ (for NS3) and $\{7, 13, 19, 25, 37\}$ (for NSNP).
Case $\ell = 5$ : The paper verifies existence for the remaining small candidates ( $q \in \{911, 1331, 2381, 3221, 3851\}$ ), confirming $N_5(q) > 0$ for all.

4. Significance and Implications

Optimization of Bounds: The result $\theta_q \le 1/3$ is shown to be a "critical boundary." The paper demonstrates that the density of primitive elements can be as high as $1/3$ while still guaranteeing the existence of consecutive non-primitive non-squares.
Methodological Shift: The paper highlights the difficulty of applying upper-bound sieves to non-primitive elements compared to primitive elements. It successfully bridges the gap between analytic bounds (Jacobi sums) and exact arithmetic (Cyclotomic numbers).
Completeness: By combining theoretical bounds with exhaustive computation for small fields, the paper provides a definitive answer for the existence of these pairs in all odd prime fields, identifying the exact set of exceptions.

5. Future Questions

The author concludes by posing three open questions:

Even Characteristic: Does a similar condition on $\theta_q$ guarantee consecutive non-primitive pairs in fields of characteristic 2 ( $\mathbb{F}_{2^k}$ )?
Tighter Bounds for Large $\ell$ : Is the condition $\theta_q \le 1/3$ necessary for $\ell \ge 7$ , or can it be relaxed (e.g., to $\theta_q < \frac{\ell-1}{2\ell}$ )?
Triple Consecutive Pairs: Can a condition on $\theta_q$ guarantee the existence of three consecutive NSNP elements? (Previous work suggests this is possible for large $q$ ).