Cyclotomic Numbers of Order $q-1$ over $\mathbb{F}_{q^r}$

1. Problem Statement

The paper investigates cyclotomic numbers $(a, b)_e$ over finite fields, specifically in the context where the order of the cyclotomy is $e = q-1$ and the underlying field is an extension $\mathbb{F}_{q^r}$ (where $q=p^n$ and $r \ge 2$).

• Definitions: Let $k = \frac{q^r-1}{q-1}$. The cyclotomic numbers $(a, b)_{q-1}$ count the number of elements $x \in C_a$ such that $x+1 \in C_b$, where $C_a$ are cyclotomic cosets of order $q-1$ in $\mathbb{F}_{q^r}$.
• Context: While asymptotic behavior for fixed $e$ as $|F| \to \infty$ is known ($(a,b)_e \sim |F|/e^2$), and upper bounds exist for large characteristic, this paper focuses on the specific family where $e = q-1$ is fixed relative to the field size $q^r$.
• Core Question: The authors aim to determine if the inequality $(a, b)_{q-1} \le \lceil k/2 \rceil$ holds for all $0 \le a, b \le q-2$. This bound is significant because it relates to the rank of specific matrices associated with cyclotomy and the distribution of solutions to norm equations.

2. Methodology

The authors employ a multi-faceted approach combining algebraic number theory, character sums, and graph theory:

1. Character Sum Formulation:

   • They express $(a, b)_{q-1}$ using multiplicative characters and Jacobi sums over $\mathbb{F}_{q^r}$.
   • By utilizing the relative norm map $N = N_{\mathbb{F}_{q^r}/\mathbb{F}_q}$, they relate Jacobi sums over the extension field to powers of Jacobi sums over the base field $\mathbb{F}_q$.
   • They decompose the sum into cases based on whether the characters involved are trivial or non-trivial, isolating a main term and an error term.

2. Estimation and Bounds:

   • Main Term Analysis: The main term is derived from trivial character cases, yielding explicit formulas involving $q^r$ and $(q-2)^r$.
   • Error Term Estimation: The error term involves non-trivial characters. Using the Hasse-Davenport relation and properties of Gauss sums, they bound the magnitude of this term by $O(q^{r/2})$.
   • Case Analysis: They rigorously analyze the inequality $(a, b)_{q-1} \le \lceil k/2 \rceil$ by comparing the main term plus the error bound against $\lceil k/2 \rceil$ for various parities of $q$ and $r$.

3. Cayley Digraph Interpretation:

   • The authors provide a structural interpretation of $(a, b)_{q-1}$ using a directed Cayley graph $\Gamma_q$.
   • They define a graph with vertices $G_q = \mathbb{F}_q^\times \times \mathbb{F}_q^\times$ and edges determined by the set $\Omega_q = \{(x, 1-x) \mid x \in \mathbb{F}_q \setminus \{0, 1\}\}$.
   • The cyclotomic number is shown to be related to the number of walks of length $r$ in this graph, specifically connecting the identity element to a target vertex determined by $a$ and $b$. This yields an exact formula involving the adjacency matrix $A_q$.

4. Special Cases ($r$ is prime):

   • For odd prime $r = \ell$, they decompose the solution set based on the degree of the minimal polynomial of the solutions over $\mathbb{F}_q$.
   • They distinguish between solutions in $\mathbb{F}_q$ (degree 1) and solutions in $\mathbb{F}_{q^\ell} \setminus \mathbb{F}_q$ (degree $\ell$), utilizing properties of irreducible polynomials and resultants.

3. Key Contributions and Results

A. The Main Theorem (Inequality Validity)

The paper proves that for $q = p^n, r \ge 2, k = \frac{q^r-1}{q-1}$, and $e = q-1$:

• General Case: If $q \neq 2$, then $(a, b)_{q-1} \le \lceil k/2 \rceil$ holds for all $0 \le a, b \le q-2$.
• Exception: If $q = 2$ and $r \ge 3$, the inequality fails. Specifically, $(0, 0)_1 = 2^r - 2$, while $\lceil k/2 \rceil = 2^{r-1}$. Since $2^r - 2 > 2^{r-1}$ for $r \ge 3$, the bound is violated.
• Equality Case: If $q=2$ and $r=2$, equality holds ($2^2-2 = 2 = \lceil 3/2 \rceil$).

B. Exact Formulas

The authors derive an exact formula for $(a, b)_{q-1}$:
$$(a, b)_{q-1} = \frac{q^r - (-1)^{r-1}(q-2)^r - 2}{(q-1)^2} + (-1)^{r-1} W_{(-1)^r \omega^{ak}, \omega^{bk}}(q, r)$$
where $W_{u,v}(q, r)$ is the number of walks of length $r$ in the Cayley graph $\Gamma_q$ from $(1,1)$ to $(u,v)$.

C. Sharper Bounds for Prime $r$

When $r = \ell$ is an odd prime, the authors provide significantly tighter bounds than the general $\lceil k/2 \rceil$:

• If $p = \ell$: $0 \le (a, b)_{q-1} \le \ell q^{\ell-2} + 1$.
• If $p \neq \ell$: $0 \le (a, b)_{q-1} \le \ell q^{\ell-2} + \ell - 1$.
• Specifically for $r=2$: $(a, b)_{q-1} \in \{0, 1, 2\}$.
• Specifically for $r=3$: $6 \le (a, b)_{q-1} \le 2q + 4$.

D. Matrix Interpretation

The paper connects the cyclotomic numbers to the rank of the matrix $C(a,b)$ defined in the introduction. The failure of the inequality in the $q=2, r \ge 3$ case corresponds to the matrix $C(0,0)$ being the all-one matrix, which has rank 1, leading to a large cyclotomic number.

4. Significance

• Resolution of a Specific Conjecture: The paper settles the question of whether the bound $(a, b)_e \le \lceil k/2 \rceil$ holds for the specific family $e=q-1$. It identifies the only exceptions ($q=2, r \ge 3$), providing a complete classification.
• Structural Insight: By linking cyclotomic numbers to walks on Cayley graphs, the paper offers a new combinatorial perspective that complements traditional analytic number theory methods.
• Refined Estimates: The derived bounds for prime $r$ are much sharper than the general $\lceil k/2 \rceil$ bound, showing that for large $q$, the cyclotomic numbers are actually quite small (polynomial in $q$ rather than exponential in $r$).
• Future Directions: The authors pose open questions regarding the failure of similar inequalities in more general settings and the structural properties of the matrices $C(a,b)$ in those failure cases.

In summary, this work provides a comprehensive analysis of cyclotomic numbers of order $q-1$ over $\mathbb{F}_{q^r}$, combining character sum estimates with graph-theoretic interpretations to establish precise bounds and identify the unique conditions under which standard upper bounds fail.