2.1 Norm equation systems

Understanding containment of complete bipartite subgraphs in the projective norm graph boils down to being able to determine the size of the intersection of translates of fibers of the norm function. It is well-known and not difficult to see that the fibers of nonzero elements of $\mathbb {F}_q$ partition the nonzero elements of $\mathbb {F}_{q^{t}}$ into equal parts. Since translation does not change their size, we have that for every $A\in \mathbb {F}_{q^{t}}$ and $a\in \mathbb {F}_q^*$ , the equation $ {\mathrm {N}}_t(X+A)=a$ has exactly $\frac {q^{t}-1}{q-1}$ solutions $X\in \mathbb {F}_{q^{t}}$ .

It is less clear how many common solutions two or more such norm equations have. For a set $U = \big \{ (A_1, a_1), \ldots , (A_{\ell }, a_{\ell }) \big \} \subseteq \mathbb {F}_{q^{t}}\times \mathbb {F}_q^*$ of coefficients we are interested in the number of solutions $ X \in \mathbb {F}_{q^{t}}$ of the system of $\ell $ norm equations

(2.1) $$ \begin{align} {\mathrm{N}}_{t}(A_i + X) = a_i, \quad i\in [\ell]. \end{align} $$

The set of solutions will be denoted by $S_t(U)$ . In [Reference Kohayakawa, Rödl and Sissokho39] it was shown that when the number $\ell $ of equations is equal to the degree t of the field extension, and the $A_i$ are all distinct, then the number of solutions cannot be more than $t!$ . Note that if $A_i=A_j$ for some $i\neq j$ then either there is no solution (if $a_i\neq a_j$ ) or two equations coincide (if $a_i=a_j$ ). We call a set $U = \big \{ (A_1, a_1), \ldots , (A_{\ell }, a_{\ell }) \big \} \subseteq \mathbb {F}_{q^{t}}\times \mathbb {F}_q^*$ of coefficients generic if the first coordinates are all distinct.

In our first theorem we determine the size of the intersection of translates of two fibers. For $t=2$ our result is precise, while for $t\geq 3$ it is mostly asymptotic. We are also able to characterize the degenerate cases, when the intersection of the two fibers is not around the “average” $(1+o(1))q^{t-2}$ . Curiously this can only happen when the degree of the field extension is at most three.

To state our results we introduce some more notation. We denote by $ {\mathrm {Tr}}_t= {\mathrm {Tr}}_{t,q}$ the $\mathbb {F}_q$ -trace function on $\mathbb {F}_{q^{t}}$ , that is, for $X\in \mathbb {F}_{q^t}$ we have $ {\mathrm {Tr}}_{t}(X) :=X+X^q+\cdots +X^{q^{t-1}}$ , and for odd q we let $\eta _{\mathbb {F}_q}$ denote the quadratic character of $\mathbb {F}_q$ . Finally, for an integer q, let $res_3(q) \in \{ -1, 0, 1\}$ denote the residue of q modulo $3$ .

Theorem 1. Let $q=p^k$ be a prime power, $t\geq 2$ be an integer, and $U = \big \{ (A_1, a_1), (A_{2}, a_{2}) \big \} \subseteq \mathbb {F}_{q^{t}}\times \mathbb {F}_q^*$ be a generic set of coefficients. Further put

$$ \begin{align*} c_1{\kern-1pt}={\kern-1pt}c_1\big((A_1,a_1),(A_2,a_2)\big){\kern-1pt}={\kern-1pt}\frac{a_1}{{\mathrm{N}}_t(A_2-A_1)} {\kern-1pt}\in{\kern-1pt} \mathbb{F} _q^* & & \!\!\text{and}\!\! & & c_2=c_2\big((A_1,a_1),(A_2,a_2)\big)= \frac{a_2}{{\mathrm{N}}_t(A_2-A_1)} {\kern-1pt}\in{\kern-1pt} \mathbb{F} _q^*. \end{align*} $$

1. (a) If $t=2$ then

   $$ \begin{align*} \big|S_2\left(U\right)\big|= \left\{ \begin{array}{ll} 1 - \eta_{\mathbb{F}_q}\left((1+c_1-c_2)^2-4c_1\right) & \text{if } q\text{ odd},\\ 1 & \text{if } p=2\text{ and }c_1+c_2=1,\\ 1 -(-1)^{{\mathrm{Tr}}_{k,2}\left(\frac{c_1}{(1+c_1+c_2)^2}\right)} & \text{if } p=2\text{ and }c_1+c_2\neq 1. \end{array} \right. \end{align*} $$

2. (b) If $t\geq 3$ then

   $$ \begin{align*} \big|S_t\left(U\right)\big|= \left\{ \begin{array}{ll} 2q+1 - res_3(q) & \text{if } t=3, \text{ and } (c_1,c_2) = (1,-1)\\ q^{t-2} + O(q^{t-2.5}) & \text{otherwise,} \end{array} \right. \end{align*} $$

Our second main theorem deals with the intersection of translates of three fibers.

The upper bound of (a) for $t=3$ was proved in [Reference Kohayakawa, Rödl and Sissokho39] using a different argument. Part (b) shows that this upper bound is tight.

2.2 Difference sets

The proof of part (b) of Theorem 2 crucially depends on a characterization of the solutions of (2.1) in the canonical exceptional case from Theorem 1(b). On the one hand, we show that $S_3\Big (\big \{(0,1), (1,-1)\big \}\Big )$ is the union of the roots of two simple polynomials of degree $q+1$ , each of which factors in $\mathbb {F}_{q^{3}}$ . On the other hand, the root set of both polynomials turns out to be a difference set within the multiplicative cyclic group $\mathcal {N} = \{ X \in \mathbb {F}_{q^{3}}: {\mathrm {N}}_3(X)= 1 \}$ of order $q^2+q+1$ .

Given a multiplicative group ${\cal G}$ , a subset $\mathcal {D} \subseteq {\cal G}$ is called a planar difference set if every nonidentity element $A\in {\cal G}$ has a unique representation as a product of an element from $\mathcal {D}$ and an element from $\mathcal {D}^{-1}$ , where $\mathcal {D}^{-1} := \{ d^{-1} : d\in \mathcal {D}\}$ denotes the set of inverses of the elements of $\mathcal {D}$ . We refer to this representation as the mixed representation of A with respect to $\mathcal {D}$ . If the group ${\cal G}$ admits a planar difference set of size m, then, by simple counting, its order has to be of the form $\ell ^2+\ell +1$ with $\ell =m-1$ . Planar difference sets in Abelian groups are only known to exist if the group is cyclic and $\ell $ is a prime power. As it will cause no confusion, in what follows we will omit the word “planar.” For a gentle introduction and a good survey on difference sets the reader may consult, e.g., [Reference Moore and Pollatsek54].

Theorem 3. Let $q\geq 2$ be a prime power. Then we have

$$ \begin{align*} S_3\Big(\big\{(0,1), (1,-1)\big\}\Big) = \mathcal{H}_1\cup\mathcal{H}_2, \end{align*} $$

where

$$ \begin{align*} {\cal H}_1 = \big\{ X \in \overline{\mathbb{F}}_q: X^{q+1}+X+1= 0\big\} & & \text{and} & & {\cal H}_2 =\big\{ X\in \overline{\mathbb{F}}_q : X^{q+1}+X^q+1 =0 \big\}, \end{align*} $$

where $\overline {\mathbb {F}}_q$ denotes the algebraic closure of $\mathbb {F}_q$ . The sets $\mathcal {H}_1,\mathcal {H}_2$ form difference sets in the multiplicative group $\mathcal {N} \subseteq \mathbb {F}_{q^{3}}$ , and $\mathcal {H}_2 = \mathcal {H}_1^{-1}$ . Furthermore for any element $A\in \mathcal {N}\setminus \{ 1 \}$ , its unique mixed representation $A=A_1\cdot A_2$ is given by the following explicit formulas:

(2.2) $$ \begin{align} A_1&=\frac{A^{q+1}-1}{1-A^{q}} \in \mathcal{H}_1 & \text{and}& & A_2&=\frac{A-A^{q+1}}{A^{q+1}-1}\in \mathcal{H}_2. \end{align} $$

The difference sets ${\cal H}_1$ and ${\cal H}_2$ turn out to be of the classic Singer typeFootnote ³ . Their simple description from the theorem, as roots of two sparse polynomials, seems novel, at least we did not find it in the literature In any case, the difference set property and the explicit expression of mixed representations will be crucial in the proof of our main result.

2.3 Common neighborhoods

Our results about norm equation systems transfer in a relatively standard way to common neighborhoods of small vertex sets in the projective norm graphs. For a set $T= \big \{(V_i,v_i) \in \mathbb {F}_{q^{t-1}}\times \mathbb {F}_q^*: \ i\in [\ell ]\big \}$ of $\ell $ vertices of $\text {NG}(q, t)$ , we define the common neighborhood of T as the set

$$ \begin{align*} \Gamma(T)= \big\{ (Y,y)\in V\big(\text{NG}(q,t)\big) : {\mathrm{N}}_{t-1}(Y+V_i) = yv_i,\ i\in [\ell ] \big\} \subseteq \mathbb{F}_{q^{t-1}} \times \mathbb{F}_q^*. \end{align*} $$

Note that in our definition we do allow a vertex to be in its own neighborhood. The size of $\Gamma (T)$ is the common degree of T and is denoted by $\deg (T)$ . With this notation the main result of Alon, Rónyai and Szabó [Reference Alon, Rónyai and Szabó5] can be phrased as $\deg (T) \leq (t-1)!$ for every subset $T\subseteq V\big (\text {NG}(q,t)\big )$ of size t.

A moment of thought reveals that two vertices of the projective norm graph with the same first coordinate do not have a common neighbor in $\text {NG}(q,t)$ . In particular, the common neighborhood of a nongeneric set of vertices is empty. The following proposition formulates how exactly the common neighbors of a generic set of $\ell $ vertices are related to solutions of a system of $\ell -1$ norm equations of type (2.1).

Proposition 1. Let $T = \big \{ (V_i, v_i) : i \in [\ell ]\big \} \subseteq V\big (\text {NG}(q,t)\big )$ be an arbitrary generic set. Then the set $A(T) := \big \{ (A_i(T), a_i(T)) : i\in [ \ell -1]\big \}$ , defined through

$$ \begin{align*} A_i(T) := \frac{1}{V_i-V_\ell} \in \mathbb{F}_{q^{t-1}}^* & & \text{and} & & a_i(T):= \frac{v_i}{v_\ell \cdot{\mathrm{N}}_{t-1}(V_i-V_{\ell})} \in \mathbb{F}_q^*, \end{align*} $$

is also generic, and the function $\Phi $ that maps $(Y, y)$ to $\frac {1}{Y+V_{\ell }}$ , is a bijection from $\Gamma (T)$ to $S_{t-1}\big (A(T) \big ) \setminus \{ 0 \}.$ Footnote ⁴ In particular, we have

$$ \begin{align*} \deg(T)=\Big|S_{t-1}\big(A(T)\big)\Big|-\xi(T), \end{align*} $$

where

$$ \begin{align*} \xi (T) = \left\{ \begin{array}{cl} 1 & \mathrm{if } v_1 = \cdots = v_{\ell} \\ 0 & \mathrm{otherwise}. \end{array} \right. \end{align*} $$

For a pair $T = \big \{(V_1,v_1),(V_2, v_2)\big \}$ of vertices, Proposition 1 implies that the common degree of T is either $\frac {q^{t-1}-1}{q-1}$ (if $v_1\neq v_2$ ) or one less (if $v_1=v_2$ ).

The results of Theorem 1 and Theorem 2(a) translate via Proposition 1 to results on the common degrees of triples and quadruples of vertices of $\text {NG}(q,t)$ , respectively.

In the particular case $t=3=\ell $ the proof of Füredi [Reference Füredi34] strengthening the Kővári-Sós-Turán upper bound, coupled with the fact that $\text {NG}(q,3)$ is $K_{3,3}$ -free, implies that roughly half of the triples in $\text {NG}(q,3)$ must have two common neighbors and roughly half of them have none. Theorem 1(a) and Proposition 1 together characterize triples of each type; we skip the explicit statement.

Next we spell out the direct consequences of Theorem 1(b) and Theorem 2(a), which will also be necessary for our subsequent applications to quasirandomness and generalized Turán numbers.

Part (b) is an extension of the result of [Reference Alon, Rónyai and Szabó5] on the $K_{4,7}$ -freeness of $\text {NG}(q,4)$ , and its proof uses more elementary tools than the one based on [Reference Kollár, Rónyai and Szabó40].

Finally, from Theorem 2(b) and Proposition 1 we infer that the $K_{4,7}$ -free projective norm graph $\text {NG}(q,4)$ contains (many) $K_{4,6}$ for every prime power larger than $4$ .

Complementing Corollary 2 we remark that it is immediate that $\text {NG}(2,4)$ does not contain $K_{4,6}$ , and in $\text {NG}(3,4)$ and $\text {NG}(4,4)$ we verified by computer search that there is no $K_{4,6}$ either.

2.4 Quasirandomness

We call a sequence of graphs $(G_n)$ on a growing number n of vertices with $(1+o(1))p{n\choose 2}$ edges H-quasirandom (of density $p=p(n)$ ) if the number $X_H(G_n)$ of vertex labeled subgraphs of $G_n$ isomorphic to H is $\big (1+o(1)\big ) n^{v(H)}p^{e(H)}$ , the expected number of labeled copies of H in the Erdős-Rényi binomial random graph $G(n,p)$ . It is known [Reference Bollobás19, Reference Erdős29] that for any graph H (with $e(H)>0$ ) $G(n,p)$ is H-quasirandom with high probability (w.h.p.), provided p is large enough, namely $p \gg n^{-1/m(H)}$ , where $m(H) = \max \{ e(H')/v(H') : H' \subseteq H, v(H')> 0\}$ is the maximum density of H. In particular when p is a constant then $G(n,p)$ is quasirandom for every H.

In their seminal papers Chung, Graham, and Wilson [Reference Chung, Graham and Wilson26] and Thomason [Reference Thomason72, Reference Thomason and Whitehead73] proved that in the case of constant edge density p a number of other typical properties of $G(n,p)$ are equivalent to being H-quasirandom for every H. For example, $C_4$ -quasirandomness alone implies H-quasirandomness for every H. Furthermore the property that the eigenvalues $\lambda _1 \geq \cdots \geq \lambda _n$ of the adjacency matrix of $G_n$ satisfy $\lambda _1 = (1+o(1))pn$ and $\lambda (G_n) := \max _{i\neq 1} |\lambda _i| = o(pn)$ is also known to be equivalent.

For sparse graphs, that is, when $p=o(1)$ , the relationship between these properties was investigated in several papers [Reference Chung and Graham25, Reference Conlon, Fox and Zhao27, Reference Kohayakawa, Rödl and Sissokho39]. It turns out that some implications remain valid, while some others, in contrast to the dense case, are far from being true. It is an interesting general problem to quantify, in terms of the edge density $p(n)$ , the extent to which one of these properties implies another.

The projective norm graphs, in particular, serve as examples for some of the implications being false for relatively high edge density p. In [Reference Szabó71] it is shown that the eigenvalues of $\text {NG}(q,t)$ are exactly $\pm 1$ times the absolute values of the different Gaussian sums over the field $\mathbb {F}_{q^{t-1}}$ , and hence, $ \lambda \big (\text {NG}(q,t)\big ) = q^{\frac {t-1}{2}}$ . This is not only of smaller order than the largest eigenvalue, which is $d\approx q^{t-1}$ , but is roughly the square root of it. As it is well-known (and not hard to see, e.g., [Reference Krivelevich, Sudakov, Győri, Katona, Lovász and Fleiner44]) that for every d-regular graph on n vertices $\lambda = \Omega \big (\sqrt {d}\big )$ (provided the density $\frac {d}{n}$ is bounded away from $1$ ), the projective norm graphs are as quasirandom as it gets, at least in terms of their second eigenvalue. In contrast, H-quasirandomness for $H=K_{t,(t-1)!+1}$ fails badly in the norm graphs $\text {NG}(q, t)$ : there are zero copies of this H, while the random graph of the same edge-density w.h.p. contains many, namely $\Theta \big (n^{t}\big )$ . Moreover this occurs for edge density $p= n^{-\frac {1}{t}}$ , an inverse polynomial with an exponent that could be arbitrarily close to $0$ .

Alon and Pudlák [Reference Alon and Pudlák4], for their explicit lower bound on asymmetric Ramsey numbers, needed many copies of small cliques $K_{\ell }$ in the norm graph. They have shown, using the Expander Mixing Lemma, that for every graph H with $v < \frac {t}{2} +1$ vertices the norm graphs of [Reference Kohayakawa, Rödl and Sissokho39] are H-quasirandom. In fact, as noticed by Alon (cf. [Reference Krivelevich, Sudakov, Győri, Katona, Lovász and Fleiner44]), their argument generalizes to show that any d-regular graph G on n vertices with second eigenvalue $\lambda $ (such graphs are also called $(n,d,\lambda )$ -graphs) is H-quasirandom provided $\lambda \ll \frac {d^{\Delta (H)}}{n^{\Delta (H) -1}}$ .

For the projective norm graph this means that if the maximum degree $\Delta (H) < \frac {t+1}{2}$ , then $\text {NG}(q,t)$ is H-quasirandom. For $\Delta =2$ this statement starts to work when t is at least $4$ and for $\Delta =3$ it starts to work when t is at least $6$ . Using Corollary 1 we can go beyond what is possible in terms of subgraph containment from the general eigenvalue bound of the Expander Mixing Lemma, and can deal with the much wider class of degenerate graphs instead of just bounded maximum degree. Recall that a graph G is r-degenerate if every nonempty subgraph of G has a vertex of degree at most r, or equivalently, there is an ordering of the vertices of G such that every vertex has at most r neighbors preceding it.

Theorem 4. Let q be a prime power and let H be a simple graph.

If $t\geq 5$ and H is $3$ -degenerate or $t=3, 4$ and H is $2$ -degenerate, then we have that

(2.3) $$ \begin{align} \left|X_H\big(\text{NG}(q,t)\big) - q^{t\cdot v(H) - e(H)}\right| \leq O\left(q^{t v(H)-e(H)-\frac{1}{2}}\right). \end{align} $$

as q tends to infinity. In particular, $\text {NG}(q,t)$ is H-quasirandom in these cases.

Furthermore if H is $3$ -degenerate and $t = 4$ , then

(2.4) $$ \begin{align} X_H\big(\text{NG}(q,4)\big) = \Theta \left(q^{4v(H) - e(H)}\right). \end{align} $$

2.5 Generalized Turán numbers

For simple graphs T and H (with no isolated vertices) and a positive integer n, the generalized Turán problem asks for the maximum possible number $ {\mathrm {ex}}(n,T,H)$ of unlabeled copies of T in an H-free graph on n vertices. Note that by setting $T=K_2$ we recover the original Turán problem for H. Alon and Shikhelman [Reference Alon and Shikhelman7] investigated the problem in the case when H is a complete bipartite graph $K_{t,s}$ with $t\leq s$ , and T is a complete graph $K_m$ or a complete bipartite graph $K_{a,b}$ . They have shown that $K_{t,s}$ -freeness in an n-vertex graph implies that the number of copies of T is at most $O\left (n^{v(T)-\frac {e(T)}{t}}\right )$ , whenever T is a clique $K_m$ with $m\leq t+1$ or a complete bipartite graph $K_{a,b}$ with $a\leq b <t$ . This, together with the Alon-Pudlák counting of subgraphs in the projective norm graph implied that for every $s>(t-1)!$ , the generalized Turán number

(2.5) $$ \begin{align} ex(n, T,K_{t,s}) = \Theta \left( n^{v(T) - \frac{e(T)}{t}} \right), \end{align} $$

whenever T is a clique $K_m$ with $m\leq \frac {t+2}{2}$ or a complete bipartite graph $K_{a,b}$ with $a\leq b \leq \frac {t}{2}$ . For $T=K_3$ , Kostochka, Mubayi and Verstraëte [Reference Kostochka, Mubayi and Verstraëte41] and Alon and Shikhelman [Reference Alon and Shikhelman7] counted triangles in the projective norm graphs more directly, which extended the validity of (2.5) from $t\geq 4$ to $t\geq 2$ . Ma, Yuan and Zhang [Reference Ma, Yuan and Zhang50] used the random algebraic construction of Bukh to extend the validity of (2.5) to $m\leq t+1$ for cliques $T=K_m$ and to $a<t$ , $b\leq t$ for complete bipartite graphs $T=K_{a,b}$ , provided s is larger than some function $f(t)$ (much larger than $t!$ ).

The lower bound of (2.3) in Theorem 4 is valid for $3$ -degenerate T already when $t\geq 4$ and provides a lower bound on the generalized Turán number $ {\mathrm {ex}}(n,T,K_{t,s})$ . One just have to divide by the size $|Aut(T)|$ of the automorphism group of T as here we count unlabeled copies.

Corollary 3. For every $3$ -degenerate simple graph T and any $t\geq 4$ and $s> (t-1)!$ we have

$$ \begin{align*} {\mathrm{ex}}(n,T,K_{t,s})\geq (1+o(1))\frac{1}{|{\mathrm{Aut}}(T)|}n^{v(T)-\frac{e(T)}{t}}. \end{align*} $$

Combining this result with the upper bound of Alon and Shikhelman [Reference Alon and Shikhelman7], we extend the validity of (2.5) for $T=K_4$ (from $t\geq 6$ to $t\geq 4$ ) and complete bipartite graphs $K_{3,b}$ (from $t\geq 6$ and $b \leq t/2$ to the best possible $t\geq 4$ and $b <t$ ).

Corollary 4. For every $t\geq 4$ and $s>(t-1)!$ we have

$$ \begin{align*} ex(n, T, K_{t,s}) = \Theta\left(n^{v(T)-\frac{e(T)}{t}}\right), \end{align*} $$

whenever T is a clique $K_4$ or a complete bipartite graph $K_{a,b}$ with $a\leq b < s$ and $a\leq 3$ .

3.1 Proof of Theorem 1

To prove Theorem 1 we first transform our system of interest to a simpler form.

To simplify notation, from now on we will write $S_t(c_1,c_2)$ instead of $S_t\big (U'\big )=S_t\Big (\big \{(0,c_1),(1,c_2)\big \}\Big )$ . For $(c_1, c_2)\in (\mathbb {F}_q^*)^2$ and $t\geq 2$ let

$$ \begin{align*} f_{t,c_1,c_2}(X)= {\mathrm{N}}_{t-1}(X+1)\cdot {\mathrm{N}}_{t-1}(X) + c_1 \cdot {\mathrm{N}}_{t-1}(X+1) - c_2 \cdot {\mathrm{N}}_{t-1}(X) \in\mathbb{F}_q[X]. \end{align*} $$

As we will demonstrate shortly, this polynomial is strongly related to our system of norm equations. Let us denote by $ {\mathrm {R}}_t(c_1,c_2)$ the set of roots of $f_{t,c_1,c_2}$ in the algebraic closure $\overline {\mathbb {F}}_q$ of $\mathbb {F}_q$ , and by $ {\mathrm {R}}^*_t(c_1,c_2)\subseteq {\mathrm {R}}_t(c_1,c_2)$ the set of multiple roots among them. In the following lemma we connect $S_t(c_1, c_2)$ to the roots in $ {\mathrm {R}}_t(c_1, c_2)$ . It turns out that every root of $f_{t,c_1,c_2}$ is contained in the union of the fields $\mathbb {F}_{q^{t}}$ and $\mathbb {F}_{q^{t-1}}$ . Furthermore all multiple roots are contained in the intersection $\mathbb {F}_{q^{t}} \cap \mathbb {F}_{q^{t-1}} = \mathbb {F}_q$ and have multiplicity two.

Proof. First we prove part $(i)$ . Let $X\in S_t(c_1,c_2)$ , that is

$$ \begin{align*} c_1 = {\mathrm{N}}_{t}(X) \quad \text{and} \quad c_2 = {\mathrm{N}}_{t}(X+1). \end{align*} $$

Multiplying the equations by $ {\mathrm {N}}_{t-1}(X+1)$ and $ {\mathrm {N}}_{t-1}(X)$ , respectively, and subtracting them from one another we obtain

$$ \begin{align*} c_1 {\mathrm{N}}_{t-1}(X+1) - c_2 {\mathrm{N}}_{t-1}(X) = {\mathrm{N}}_{t}(X){\mathrm{N}}_{t-1}(X+1) - {\mathrm{N}}_{t}(X+1){\mathrm{N}}_{t-1}(X). \end{align*} $$

By substituting $ {\mathrm {N}}_{t}(X)= {\mathrm {N}}_{t-1}(X) X^{q^{t-1}}$ and $ {\mathrm {N}}_{t}(X+1)= {\mathrm {N}}_{t-1}(X+1) (X+1)^{q^{t-1}}$ we get

$$ \begin{align*} c_1 {\mathrm{N}}_{t-1}(X+1) &- c_2 {\mathrm{N}}_{t-1}(X) = {\mathrm{N}}_{t-1}(X){\mathrm{N}}_{t-1}(X+1) X^{q^{t-1}} - {\mathrm{N}}_{t-1}(X+1){\mathrm{N}}_{t-1}(X) (X+1)^{q^{t-1}}\\ &= {\mathrm{N}}_{t-1}(X+1){\mathrm{N}}_{t-1}(X)\left( X^{q^{t-1}} - (X+1)^{q^{t-1}} \right) = {\mathrm{N}}_{t-1}(X+1){\mathrm{N}}_{t-1}(X) (-1). \end{align*} $$

This proves that X is a root of $f_{t,c_1,c_2}$ , that is, $X\in {\mathrm {R}}_t(c_1,c_2)$ .

For part $(ii)$ let us first consider an arbitrary $X\in S_t(c_1,c_2)\cap \mathbb {F}_q$ . By part $(i)$ we know that X is a root of $f_{t,c_1,c_2}$ . To show that it is a multiple root, we check that X is also root of the formal derivative $f^{\prime }_{t,c_1,c_2}$ . As $X\notin \{0,-1\}$ , the formal derivative $f^{\prime }_{t,c_1,c_2}$ at X can be expressed as $\left (q^{t-2}+\dots +q+1\right )$ times

$$ \begin{align*} \left( \frac{{\mathrm{N}}_{t-1}(X+1){\mathrm{N}}_{t-1}(X)}{X} +\frac{{\mathrm{N}}_{t-1}(X+1){\mathrm{N}}_{t-1}(X)}{X+1}+\frac{c_1{\mathrm{N}}_{t-1}(X+1)}{X+1} - \frac{c_2{\mathrm{N}}_{t-1}(X)}{X}\right). \end{align*} $$

Since $X\in S_t(c_1,c_2)$ , we may again replace $c_1$ and $c_2$ by $ {\mathrm {N}}_{t}(X)= {\mathrm {N}}_{t-1}(X) X^{q^{t-1}}$ and $ {\mathrm {N}}_{t}(X+1)= {\mathrm {N}}_{t-1}(X+1) (X+1)^{q^{t-1}}$ , respectively. As $q^{t-2}+\dots +q +1=1$ in $\mathbb {F}_q$ , this results in

$$ \begin{align*} f^{\prime}_{t,c_1,c_2}(X) = {\mathrm{N}}_{t-1}(X) {\mathrm{N}}_{t-1}(X+1) \left( \frac{1}{X} + \frac{1}{X+1} + \frac{X^{q^{t-1}}}{X+1} - \frac{(X+1)^{q^{t-1}}}{X} \right). \end{align*} $$

However, as $X\in \mathbb {F}_q$ , we have $X^q=X$ , so the last factor simplifies to

$$ \begin{align*} \frac{1}{X} + \frac{1}{X+1} + \frac{X}{X+1} - \frac{X+1}{X} = 0, \end{align*} $$

proving that $f^{\prime }_{t,c_1,c_2}(X)=0$ . Consequently $X\in {\mathrm {R}}^*_t(c_1,c_2)$ , hence

(3.1) $$ \begin{align} S_t(c_1,c_2) \cap \mathbb{F}_q \subseteq {\mathrm{R}}_t^*(c_1,c_2). \end{align} $$

Before proving that in (3.1) we have actually equality, we show part $(iii)$ .

We start by bounding the union and intersection of the sets $S_t(c_1,c_2)$ and $ {\mathrm {R}}_t(c_1,c_2)\cap \mathbb {F}_{q^{t-1}}$ . By part $(i)$ we have

$$ \begin{align*} S_t(c_1,c_2) \cup \left({\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\right) \subseteq S_t(c_1,c_2) \cup {\mathrm{R}}_t(c_1,c_2)={\mathrm{R}}_t(c_1,c_2). \end{align*} $$

Since $S_t(c_1, c_2) \subseteq \mathbb {F}_{q^{t}}$ and $\mathbb {F}_{q^{t}}\cap \mathbb {F}_{q^{t-1}}=\mathbb {F}_q$ , by $(i)$ and (3.1) we obtain

$$ \begin{align*} S_t(c_1,c_2) \cap {\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}} = S_t(c_1,c_2) \cap \mathbb{F}_{q^{t-1}}=S_t(c_1,c_2) \cap \mathbb{F}_q\subseteq {\mathrm{R}}^*_t(c_1,c_2). \end{align*} $$

These two observations together imply

$$ \begin{align*} \big|S_t(c_1,c_2)\big|+\big|{\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\big|\leq \big|{\mathrm{R}}_t(c_1,c_2)\big| + \big|{\mathrm{R}}^*_t(c_1,c_2)\big|. \end{align*} $$

Now note that as $\big | {\mathrm {R}}_t(c_1,c_2)\big |$ is the number of different linear factors of $f_{t,c_1,c_2}$ in $\overline {\mathbb {F}}_q$ and $\big | {\mathrm {R}}^*_t(c_1,c_2)\big |$ is the number of different linear factors that appear at least twice, their sum is necessarily bounded from above by the degree of $f_{t,c_1,c_2}$ , that is, by $2\big (q^{t-2}+\dots +q+1\big )$ . This shows

(3.2) $$ \begin{align} \big|S_t(c_1,c_2)\big|+\big|{\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\big| \leq 2\big(q^{t-2}+\dots+1\big). \end{align} $$

To get the desired equality for every pair $(c_1, c_2) \in (\mathbb {F}_q^*)^2$ we will use a Stepanovesque trick of considering their average and using double counting to transfer the difficult task of bounding the number of solutions of a high degree equation into the easy task of bounding the number of solutions of a linear equation. In other words we will show that the desired equality holds for the average; that is,

(3.3) $$ \begin{align} \frac{1}{(q-1)^2}\sum_{c_1\in\mathbb{F}_q^*}\sum_{c_2\in\mathbb{F}_q^*}\Big(\big|S_t(c_1,c_2)\big|+\big|{\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\big|\Big) = 2(q^{t-2}+\dots+1). \end{align} $$

Note that this indeed will be enough, as we have already obtained the same upper bound for the individual terms, so equality for the average is possible only if each individual term matches the upper bound.

To prove (3.3), we split the sum and evaluate each part separately. For the first part we use double-counting to obtain

$$ \begin{align*} \sum_{c_1\in\mathbb{F}_q^*}\sum_{c_2\in\mathbb{F}_q^*}\big|S_t(c_1,c_2)\big|&= \sum_{X\in\mathbb{F}_{q^{t}}}\Big|\big\{(c_1,c_2)\in (\mathbb{F}_q^*)^2 \mid S_t(c_1,c_2) \ni X\big\}\Big| &= \sum_{X\in\mathbb{F}_{q^{t}}\setminus\{0,-1\}} 1 = q^{t}-2. \end{align*} $$

The next to last equality holds since the sets $S_t(c_1, c_2)$ partition $\mathbb {F}_{q^{t}} \setminus \{0, -1\}$ . Indeed, each ${X \in \mathbb {F}_{q^{t}} \setminus \{0, -1\}}$ is contained in exactly one of them, namely $S_t\big ( {\mathrm {N}}_{t}(X), {\mathrm {N}}_{t}(X+1)\big )$ . Similarly,

$$ \begin{align*} \sum_{c_1\in\mathbb{F}_q^*}\sum_{c_2\in\mathbb{F}_q^*}\big|{\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\big|= \sum_{X\in\mathbb{F}_{q^{t-1}}}\sum_{c_1\in\mathbb{F}_q^*}\Big|\big\{c_2\in\mathbb{F}_q^* \mid X \in {\mathrm{R}}_t(c_1,c_2) \big\}\Big|. \end{align*} $$

Now for fixed $X\in \mathbb {F}_{q^{t-1}}$ and $c_1\in \mathbb {F}_q^*$ the expression $f_{t,c_1,c_2}(X)$ becomes a linear polynomial in $c_2$ . It has no root in $\mathbb {F}_q^*$ if $X\in \{0,-1\}$ or $c_1=- {\mathrm {N}}_{t-1}(X)$ , otherwise there is a unique $c_2$ for which $f_{t,c_1,c_2}(X)=0$ , namely $c_2=\frac { {\mathrm {N}}_{t-1}(X+1)\big ( {\mathrm {N}}_{t-1}(X) + c_1\big )}{ {\mathrm {N}}_{t-1}(X)}$ . Hence

$$ \begin{align*} \sum_{c_1\in\mathbb{F}_q^*}\sum_{c_2\in\mathbb{F}_q^*}\big|{\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\big|=\sum_{X\in\mathbb{F}_{q^{t-2}}\setminus \{0,-1\}}\sum_{c_1\in\mathbb{F}_q^*\setminus\{-{\mathrm{N}}_{t-1,q}(X)\}} 1= (q^{t-1}-2)(q-2). \end{align*} $$

Summing up both parts, we get

$$ \begin{align*} \sum_{c_1\in\mathbb{F}_q^*}\sum_{c_2\in\mathbb{F}_q^*}\!\Big(\big|S_t(c_1,c_2)\big|+\big|{\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\big|\Big){\kern-1pt}={\kern-1pt}q^t{\kern-1pt}-{\kern-1pt}2{\kern-1pt}+{\kern-1pt}\left(q^{t-1}-2\right)(q-2)= 2(q-1)^2\left(q^{t-2}+\cdots+1\right), \end{align*} $$

which proves (3.3).

Now we turn back to finish the proof of $(ii)$ . The equality in $(iii)$ implies that in the proof of (3.2) all displayed inequalities and containments must hold with equality, in particular, we have equality in (3.1) as well.

Finally, we prove $(iv)$ . To express $\big |S_t(c_1,c_2)\big |$ we first count the elements of $ {\mathrm {R}}_t(c_1,c_2)\cap \mathbb {F}_{q^{t-1}}$ through classifying them by their norm and then use part $(iii)$ .

$$ \begin{align*} \big|{\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\big| &= \sum_{b\in\mathbb{F}_q}\Big|\big\{X\in {\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}} : {\mathrm{N}}_{t-1}(X)=b\big\}\Big|\\ &= \sum_{b\in\mathbb{F}_q}\Big|\big\{X\in \mathbb{F}_{q^{t-1}} : {\mathrm{N}}_{t-1}(X)=b \text{ and } {\mathrm{N}}_{t-1}(X+1)(b + c_1) = b \cdot c_2\big\}\Big|. \end{align*} $$

Note that $0\notin {\mathrm {R}}_t(c_1,c_2)\cap \mathbb {F}_{q^{t-1}}$ , since $c_1\neq 0$ . Hence, for $b=0$ this set is empty. Moreover, it is also empty for $b=-c_1$ , since neither $c_1$ , nor $c_2$ is $0$ . Consequently,

$$ \begin{align*} \big|{\mathrm{R}}_t(c_1,c_2)\cap\mathbb{F}_{q^{t-1}}\big| &= \sum_{b\in\mathbb{F}_q^*\setminus\{-c_1\}}\left|\left\{X\in \mathbb{F}_{q^{t-1}} \mid {\mathrm{N}}_{t-1}(X)=b \text{ and }{\mathrm{N}}_{t-1}(X+1) = \frac{b \cdot c_2}{b+c_1}\right\}\right|\\ &= \sum_{b\in\mathbb{F}_q^*\setminus\{-c_1\}}\left|S_{t-1}\left(b,\frac{b \cdot c_2}{b+c_1}\right)\right| \end{align*} $$

Now, the assertion of part $(iv)$ follows by part $(iii)$ .

We are now ready to prove Theorem 1. By Lemma 1 it is enough to consider the sets $S_t(c_1,c_2)$ for $(c_1,c_2)\in (\mathbb {F}_q^*)^2$ . We start by examining the case $t=2$ . By part $(iii)$ of Lemma 2 we have

$$ \begin{align*} \big|S_2(c_1,c_2)\big| &=2-\big|{\mathrm{R}}_2(c_1,c_2)\cap\mathbb{F}_q\big|= 2 - \Big|\big\{ X\in\mathbb{F}_q \mid f_{2,c_1,c_2}(X) = 0 \big\}\Big| \\ &= 2 - \Big|\big\{ X\in\mathbb{F}_q \mid (X+1)X + c_1 \cdot (X+1) - c_2 X = 0 \big\}\Big| \\ &= 2 - \Big|\big\{ X\in\mathbb{F}_q \mid X^2 + (1+c_1-c_2)X + c_1 = 0 \big\}\Big| \end{align*} $$

If q is odd, then part $(i)$ of Proposition A.1 from the Appendix gives

$$ \begin{align*} \big|S_2(c_1,c_2)\big| &= 2 - \Big( 1 + \eta_{\mathbb{F}_q}\left((1+c_1-c_2)^2-4c_1\right) \Big) = 1 - \eta_{\mathbb{F}_q}\left((1+c_1-c_2)^2-4c_1\right), \end{align*} $$

while for $q=2^k$ , using part $(ii)$ of Proposition A.2 from the Appendix, we get

$$ \begin{align*} \big|S_2(c_1,c_2)\big| &= \left\{ \begin{array}{ll} 1 & \text{if }c_1+c_2=1\\ 2 - \left(1 +(-1)^{{\mathrm{Tr}}_{k,2}\left(\frac{c_1}{(1+c_1+c_2)^2}\right)} \right) = 1 -(-1)^{{\mathrm{Tr}}_{k,2}\left(\frac{c_1}{(1+c_1+c_2)^2}\right)} & \text{if }c_1+c_2\neq1 \end{array} \right.. \end{align*} $$

This finishes the proof of part (a). In the case $t=3$ , by applying part $(iv)$ of Lemma 2 and the case $t=2$ , we obtain

$$ \begin{align*} \big|S_3(c_1,c_2)\big| &= 2(q+1)-\sum_{b\in\mathbb{F}_q^*\setminus\{-c_1\}} \left|S_{2}\left(b,\frac{bc_2}{b+c_1}\right)\right|. \end{align*} $$

Now first suppose again that q is odd. Then

$$ \begin{align*} \big|S_3(c_1,c_2)\big| &= 2(q+1)-\sum_{b\in\mathbb{F}_q^*\setminus\{-c_1\}}\left(1 - \eta_{\mathbb{F}_q}\left(\left(1+b-\frac{bc_2}{b+c_1}\right)^2-4b\right)\right) \\ &= q+4+\sum_{b\in\mathbb{F}_q^*\setminus\{-c_1\}}\eta_{\mathbb{F}_q}\left(\frac{\big((b+c_1)(1+b)-bc_2\big)^2-4b(b+c_1)^2}{(b+c_1)^2}\right). \end{align*} $$

Put

(3.4) $$ \begin{align} L(b) &=\big((b+c_1)(1+b)-bc_2\big)^2-4b(b+c_1)^2 \nonumber \\ &=b^4+2(c_1-c_2-1)b^3+\big((1+c_1-c_2)^2-6c_1\big)b^2+2c_1(1-c_1-c_2)b+c_1^2, \end{align} $$

and observe that the denominator inside $\eta _{\mathbb {F}_q}$ may be omitted as it is a nonzero square and $\eta _{\mathbb {F}_q}$ is multiplicative. Accordingly,

$$ \begin{align*} \big|S_3(c_1,c_2)\big| &= q+4+\sum_{b\in\mathbb{F}_q^*\setminus\{-c_1\}}\eta_{\mathbb{F}_q}\big(L(b)\big) = q+4-\eta_{\mathbb{F}_q}\big(L(0)\big)-\eta_{\mathbb{F}_q}\big(L(-c_1)\big)+\sum_{b\in\mathbb{F}_q}\eta_{\mathbb{F}_q}\big(L(b)\big) \\ &= q+4-\eta_{\mathbb{F}_q}\left(c_1^2\right)-\eta_{\mathbb{F}_q}\left(c_1^2 c_2^2\right)+\sum_{b\in\mathbb{F}_q}\eta_{\mathbb{F}_q}\big(L(b)\big) = q+2+\sum_{b\in\mathbb{F}_q}\eta_{\mathbb{F}_q}\big(L(b)\big). \end{align*} $$

Our goal is to use the Weil character sum estimate (see Theorem A.1 in the Appendix) for the quadratic character $\eta _{\mathbb {F}_q}$ . As the order of $\eta _{\mathbb {F}_q}$ is $2$ , we can estimate the above sum using the first part of Theorem A.1, unless $L(b)=(b^2+\alpha _1b+\alpha _0)^2$ for some $\alpha _1,\alpha _0\in \mathbb {F}_q$ , in which case the second part of the theorem applies.

By comparing the coefficients of

$$ \begin{align*} (b^2+\alpha_1b+\alpha_0)^2=b^4+2\alpha_1b^3+(\alpha_1^2+2\alpha_0)b^2+2\alpha_1\alpha_0b+\alpha_0^2 \end{align*} $$

with (3.4) it is easy to see that the degenerate case occurs if and only if $(c_1, c_2) = (1,-1)$ . Indeed, the constant terms imply that $c_1 = \alpha _0$ or $c_1=-\alpha _0$ and using the coefficients of b and $b^3$ we have that $2c_1(1-c_1-c_2) = 2\alpha _1\alpha _0 = 2(c_1-c_2-1)\alpha _0$ . Substituting $c_1=-\alpha _0$ leads to $c_2=0$ , a contradiction. Substituting $c_1=\alpha _0$ we obtain $\alpha _0=c_1=1$ and $\alpha _1=-c_2$ and substituting all this into the coefficients of $b^2$ we obtain $c_2=-1$ .

If $(c_1,c_2)=(1,-1)$ , then $L(b)=b^4+2b^3+3b^2+2b+1=(b^2+b+1)^2$ is indeed a square and we can apply the second part of Theorem A.1:

$$ \begin{align*} \big|S_3(1,-1) \big| &= q+2 + \sum_{b\in\mathbb{F}_q}\eta_{\mathbb{F}_q}\Big(1\cdot \left(b^2+b+1\right)^2\Big)= q+2 + \Big(q-\Big|\big\{b\in\mathbb{F}_q \mid b^2+b+1=0\big\}\Big|\Big) \eta_{\mathbb{F}_q}(1) \\ &= q+2 +\Big(q - \left(1+\eta_{\mathbb{F}_q}(-3)\right)\Big) \cdot 1 = 2q + 1 - \eta_{\mathbb{F}_q}(-3)=2q+1-\text{res}_q(3). \end{align*} $$

Otherwise, if $(c_1,c_2)\neq (1,-1)$ , then by the first part of Theorem A.1 we get

$$ \begin{align*} \big| S_3(c_1,c_2) - q\big|= \Big|2 + \sum_{b\in\mathbb{F}_q}\eta_{\mathbb{F}_q}\big(L(b)\big)\Big| \leq 2 + \Big|\sum_{b\in\mathbb{F}_q}\eta_{\mathbb{F}_q}\big(L(b)\big)\Big|\leq 2 + (4-1)\sqrt{q}=O(\sqrt{q}), \end{align*} $$

implying that $S_3(c_1,c_2)=q+O(\sqrt {q})$ . This finishes the case when q is odd.

Now suppose that $q=2^k$ . Then, again by part $(iv)$ of Lemma 2 and the case $t=2$ we have

$$ \begin{align*} S_3(c_1,c_2) &= 2(q+1)-\sum_{ \begin{array}{c} b\in\mathbb{F}_q^*\setminus\{c_1\} \\ b^2+b(1+c_1+c_2)+c_1=0 \end{array} }1\\ &-\sum_{ { \begin{array}{c} b\in\mathbb{F}_q^*\setminus\{c_1\} \\ b^2+b(1+c_1+c_2)+c_1\neq 0 \end{array} } }\left(1 -(-1)^{{\mathrm{Tr}}_{k,2}\left(\frac{b(b+c_1)^2}{\left(b^2+b(1+c_1+c_2)+c_1\right)^2}\right)}\right)\\ &=q+4+\sum_{ { \begin{array}{c} b\in\mathbb{F}_q^*\setminus\{c_1\} \\ b^2+b(1+c_1+c_2)+c_1\neq 0 \end{array} } }(-1)^{{\mathrm{Tr}}_{k,2}\left(\frac{b(b+c_1)^2}{\left(b^2+b(1+c_1+c_2)+c_1\right)^2}\right)}. \end{align*} $$

Put

$$ \begin{align*} f(b)=b(b+c_1)^2\text{ and }g(b)=(b^2+b(1+c_1+c_2)+c_1)^2, \end{align*} $$

and note that both have degree at most $4$ . Accordingly,

$$ \begin{align*} S_3(c_1,c_2) &= q+4+\sum_{ { \begin{array}{c} b\in\mathbb{F}_q^*\setminus\{c_1\} \\ g(b)\neq 0 \end{array} } }(-1)^{{\mathrm{Tr}}_{k,2}\big(\frac{f(b)}{g(b)}\big)}\\ &= q+4-(-1)^{{\mathrm{Tr}}_{k,2}\big(\frac{f(0)}{g(0)}\big)}-(-1)^{{\mathrm{Tr}}_{k,2}\big(\frac{f(c_1)}{g(c_1)}\big)}+\sum_{ { \begin{array}{c} b\in\mathbb{F}_q\\ g(b)\neq 0 \end{array} } }(-1)^{{\mathrm{Tr}}_{k,2}\big(\frac{f(b)}{g(b)}\big)}\\ &= q+2+\sum_{ { \begin{array}{c} b\in\mathbb{F}_q\\ g(b)\neq 0 \end{array} } }(-1)^{{\mathrm{Tr}}_{k,2}\big(\frac{f(b)}{g(b)}\big)}. \end{align*} $$

To bound the sum we want to use Theorem A.2 from the Appendix. It is straightforward to check (see Claim A.1 in the Appendix) that the rational function $\frac {f(b)}{g(b)}$ is degenerate if and only if $(c_1,c_2)=(1,1)$ , in which case we have $ {\mathrm {Tr}}_{k,2}\left (\frac {f(b)}{g(b)}\right )=0$ for every $b\in \mathbb {F}_q, g(b)\neq 0$ .

Accordingly, if $(c_1,c_2)=(1,1)$ , then

$$ \begin{align*} S_3(1,-1) &= q+2 + \sum_{ { \begin{array}{c} b\in\mathbb{F}_q\\ g(b)\neq 0 \end{array} } }(-1)^{0}= 2q+2-\Big|\big\{b\in\mathbb{F}_q \mid b^2+b+1=0\big\}\Big|\\ &=2q+2-\left(1+(-1)^{{\mathrm{Tr}}_{k,2}(1)}\right)=2q+1-(-1)^k=2q+1-\text{res}_3(q). \end{align*} $$

Otherwise, if $(c_1,c_2)\neq (1,1)$ , then by Theorem A.2 we get

$$ \begin{align*} \Big|S_3(c_1,c_2) - q\Big|= \left|2 + \sum_{ { \begin{array}{c} b\in\mathbb{F}_q\\ g(b)\neq 0 \end{array} } }(-1)^{{\mathrm{Tr}}_{k,2}\big(\frac{f(b)}{g(b)}\big)}\right| \leq 2 + \left|\sum_{ { \begin{array}{c} b\in\mathbb{F}_q\\ g(b)\neq 0 \end{array} } }(-1)^{{\mathrm{Tr}}_{k,2}\big(\frac{f(b)}{g(b)}\big)}\right|\leq 2 + a\sqrt{q}, \end{align*} $$

for some positive constant $a\in \mathbb {R}$ (independent of q), implying that $\big |S_3(c_1,c_2)\big |=q+O(\sqrt {q})$ .

For $t=4$ we use part $(iv)$ of Lemma 2 and the case $t=3$ .

$$ \begin{align*} S_4(c_1,c_2) &= 2\left(q^2+q+1\right) - \sum_{b\in\mathbb{F}_q^*\setminus\{-c_1\}}\left|S_{3}\left(b,\frac{bc_2}{b+c_1}\right)\right| \\ &=2\left(q^2+q+1\right) - S_{3}\left(1,\frac{c_2}{1+c_1}\right) - \sum_{b\in\mathbb{F}_q^*\setminus\{-c_1, 1\}}\left|S_{3}\left(b,\frac{bc_2}{b+c_1}\right)\right| \\ &= 2\left(q^2+q+1\right) - O(q) - (q-3) \cdot \big( q + O(\sqrt{q}) \big) = q^2 + O\left(q^{1.5}\right) \end{align*} $$

Note that in the above estimate it was crucial that we could use that for most values of b, the value of $\left |S_3 \left (b,\frac {bc_2}{b+c_1}\right )\right |$ is asymptotically q.

For $t\geq 5$ we can apply induction with base case $t=4$ . The induction step is the same as above, only that now we do not need to distinguish between cases. Indeed, suppose that the statement holds for all $5\leq t'<t$ and consider the general case. By part $(iv)$ of Lemma 2 and the induction hypothesis for $t'=t-1$ we obtain

$$ \begin{align*} S_t(c_1,c_2) &= 2\left(q^{t-2}+\dots+1\right) - \sum_{b\in\mathbb{F}_q^*\setminus\{-c_1\}}\left|S_{t-1}\left(b,\frac{bc_2}{b+c_1}\right)\right|\\ &= 2\left(q^{t-2}+\dots+1\right) - (q-2) \cdot \big( q^{t-3} + O\left(q^{t-3.5}\right)\big)= q^{t-2} + O\left(q^{t-2.5}\right). \end{align*} $$

This finishes the proof of part (b).

3.2 Proof of part (a) of Theorem 2

In this subsection we prove part (a) of Theorem 2 by giving a relatively elementary argument using resultants. Consider the multivariate equation system

(3.5) $$ \begin{align} f_i(Y_1,\dots,Y_{t})=\prod_{j=1}^{t}(Y_j-C_{i,j})-a_i=0,\ i\in[3], \end{align} $$

where $C_{i,j}=-A_i^{q^{j-1}}$ for $i\in [3]$ and $j\in [t]$ . By the identity

$$ \begin{align*} N(A+B)=\prod_{j=1}^t(A+B)^{q^{j-1}}=\prod_{j=1}^t(A^{q^{j-1}}+B^{q^{j-1}}) \end{align*} $$

we have that for every solution $Y\in \mathbb {F}_{q^{t}}$ of our original system the vector $\left (Y, Y^q, \ldots , Y^{q^{t-1}}\right ) \in \left (\mathbb {F}_{q^{t}}\right )^{t}$ is a solution of (3.5). These are all distinct, hence, to prove part (a) of Theorem 2, it will be enough to show that (3.5) has at most $6\left (q^{t-3} + \cdots + q + 1\right )$ solutions.

For polynomials $p(z)=p_nz^n+\cdots +p_1z+p_0$ and $r(z)=r_mz^m+\cdots + r_1z+r_0$ of degree n and m respectively, in the variable z over some field $\mathbb {F}$ , their Sylvester matrix is the $(n+m)\times (n+m)$ matrix $\text {Syl}(p,r)=\{s_{i,j}\}_{i,j\in [n+m]}$ with entries

$$ \begin{align*} s_{i,j}= \left\{ \begin{array}{cl} p_{n+i-j}&\text{if } 1\leq i \leq m \\ r_{i-j} & m+1 \leq i \leq m+n\\ 0 & \mbox{ otherwise} \end{array} \right.. \end{align*} $$

For an example consider Figure 1. An important property of the Sylvester matrix is that the degree of the greatest common divisor of p and r is $n+m-\mbox {rank}(\text {Syl}(p,r))$ , in particular if p and r have a common root, then the determinant of $\text {Syl}(p,r)$ , also called the resultant of p and r, is $0$ . This holds true even if $p_n=0$ or $r_m=0$ , that is, when n and m are only upper bounds on the degree of p and r. (See, e.g., [Reference Kurosh45, Section 54, Chapter 11].) Now if p and r are multivariate polynomials in the variables $Y_1,\dots ,Y_n$ over some field F, then we can write them as univariate polynomials in $Y_n$ , and consider their Sylvester matrix (now with entries from $\mathbb {F}[Y_1,\dots ,Y_{n-1}]$ ). We will call the determinant of this matrix the Sylvester resultant of p and r with respect to $Y_n$ , and denote it by $\mbox {Res}_{Y_n}(p,r)$ . Note that $\mbox {Res}_{Y_n}(p,r)$ is a polynomial in the variables $Y_1,\dots ,Y_{n-1}$ . From the above property of the Sylvester matrix it follows that if $(C_1,\dots ,C_n)$ is a common root of p and r, then $(C_1,\dots ,C_{n-1})$ is a root of $\mbox {Res}_{Y_n}(p,r)$ .

Figure 1

The Sylvester matrix for $n=4$ and $m=3$ .

Let us now return to the polynomials $f_1,f_2,f_3 \in \mathbb {F}_{q^{t}}[Y_1, \ldots , Y_{t}]$ . Our plan is to compute ${g_i=\mbox {res}_{Y_{t}}(f_i,f_3)}$ for $i=1,2$ and then $g=\mbox {Res}_{Y_{t-1}}(g_1,g_2)$ . Then by the above argument, if $(C_1, \ldots , C_{t})\in \left (\mathbb {F}_{q^{t}}\right )^{t}$ is a common root of $f_1, f_2,$ and $f_3$ , then $(C_1, \ldots , C_{t-2})\in \left (\mathbb {F}_{q^{t}}\right )^{t-2}$ is a root of g.

For the computation for $i\in [3]$ we introduce

$$ \begin{align*} h_i=h_i(Y_1,\dots,Y_{t-2})=\prod_{j=1}^{t-2}(Y_j-C_{i,j}), \end{align*} $$

and rewrite $f_i$ as univariate linear polynomial in $Y_{t}$ :

$$ \begin{align*} f_i=\left(h_i\cdot \left(Y_{t-1}-C_{i,t-1}\right)\right)\cdot Y_{t}-\left(h_i\cdot C_{i,t}(Y_{t-1}-C_{i,t-1})+b_i\right). \end{align*} $$

Then for $i=1,2$ we have

$$ \begin{align*} g_i&= \mbox{Res}_{Y_{t}}(f_i,f_3)= \left| \begin{array}{cc} h_i\cdot (Y_{t-1}-C_{i,t-1}) & -\left\{h_i\cdot C_{i,t}(Y_{t-1}-C_{i,t-1})+b_i\right\} \\ h_3\cdot (Y_{t-1}-C_{3,t-1}) & -\left\{h_3\cdot C_{3,t}(Y_{t-1}-C_{3,t-1})+b_3\right\} \end{array} \right| \\&= \left| \begin{array}{cc} h_i\cdot (Y_{t-1}-C_{i,t-1}) & -h_i\cdot C_{i,t}(Y_{t-1}-C_{i,t-1}) \\ h_3\cdot (Y_{t-1}-C_{3,t-1}) & -h_3\cdot C_{3,t}(Y_{t-1}-C_{3,t-1}) \end{array} \right| + \left| \begin{array}{cc} h_i\cdot (Y_{t-1}-C_{i,t-1}) & -b_i \\ h_3\cdot (Y_{t-1}-C_{3,t-1}) & -b_3 \end{array} \right| \\&=h_i\cdot h_3\cdot(Y_{t-1}-C_{i,t-1})(Y_{t-1}-C_{3,t-1}) \left| \begin{array}{cc} 1 & -C_{i,t} \\ 1 & -C_{3,t} \end{array} \right| -h_i\cdot b_3(Y_{t-1}-C_{i,t-1})\\&\quad +h_3\cdot b_i(Y_{t-1}-C_{3,t-1}). \end{align*} $$

That is, $g_i=c_{i,2}Y_{t-1}^2+c_{i,1}Y_{t-1}+c_{i,0}$ is a quadratic polynomial in $Y_{t-1}$ with coefficients

$$ \begin{align*} c_{i,2}&=h_i\cdot h_3\cdot \left| \begin{array}{cc} 1 & -C_{i,t} \\ 1 & -C_{3,t} \end{array} \right| ,\\ c_{i,1}&=-h_i\cdot h_3\cdot (C_{i,t-1}+C_{3,t-1}) \left| \begin{array}{cc} 1 & -C_{i,t} \\ 1 & -C_{3,t} \end{array} \right| -h_i\cdot b_3+h_3\cdot b_i,\\ c_{i,0}&=h_i\cdot h_3\cdot C_{i,t-1}C_{3,t-1} \left| \begin{array}{cc} 1 & -C_{i,t} \\ 1 & -C_{3,t} \end{array} \right| +h_i\cdot b_3 C_{i,t-1}-h_3\cdot b_i C_{3,t-1}. \end{align*} $$

Hence the resultant of $g_1$ and $g_2$ is the four-by-four determinant

$$ \begin{align*} g=\mbox{Res}_{Y_{t-1}}(g_1,g_2)= \left| \begin{array}{cccc} c_{1,2} & c_{1,1} & c_{1,0} & 0 \\ 0 & c_{1,2} & c_{1,1} & c_{1,0} \\ c_{2,2} & c_{2,1} & c_{2,0} & 0 \\ 0 & c_{2,2} & c_{2,1} & c_{2,0} \end{array} \right|. \end{align*} $$

Note that each $c_{i,j}$ is a quadratic polynomial in each of the variables $Y_1,\dots ,Y_{t-2}$ . In particular the degree of g in any of the variables is at most $8$ . It turns out that this bound can be reduced.

Proof. The coefficient in question is clearly the determinant we get by replacing $c_{i,j}$ everywhere in the determinant formula for g with the coefficient of $Y_a^2$ in it. As

$$ \begin{align*} \mbox{coeff}(Y_a^2,c_{i,2})&=\frac{h_i}{Y_a-C_{i,a}}\cdot \frac{h_3}{Y_a-C_{3,a}}\cdot \left| \begin{array}{cc} 1 & -C_{i,t} \\ 1 & -C_{3,t} \end{array} \right| ,\\ \mbox{coeff}(Y_a^2,c_{i,1})&=-\frac{h_i}{Y_a-C_{i,a}}\cdot \frac{h_3}{Y_a-C_{3,a}}\cdot (C_{i,t-1}+C_{3,t-1}) \left| \begin{array}{cc} 1 & -C_{i,t} \\ 1 & -C_{3,t} \end{array} \right| \\ \mbox{coeff}(Y_a^2,c_{i,0})&=\frac{h_i}{Y_a-C_{i,a}}\cdot \frac{h_3}{Y_a-C_{3,a}}\cdot C_{i,t-1}C_{3,t-1} \left| \begin{array}{cc} 1 & -C_{i,t} \\ 1 & -C_{3,t} \end{array} \right| , \end{align*} $$

we have

$$ \begin{align*} \mbox{coeff}(Y_a^8,g)&= \left|\begin{array}{cccc} \mbox{coeff}(Y_a^2,c_{1,2}) & \mbox{coeff}(Y_a^2,c_{1,1}) & \mbox{coeff}(Y_a^2,c_{1,0}) & 0 \\ 0 & \mbox{coeff}(Y_a^2,c_{1,2}) & \mbox{coeff}(Y_a^2,c_{1,1}) & \mbox{coeff}(Y_a^2,c_{1,0}) \\ \mbox{coeff}(Y_a^2,c_{2,2}) & \mbox{coeff}(Y_a^2,c_{2,1}) & \mbox{coeff}(Y_a^2,c_{2,0}) & 0 \\ 0 & \mbox{coeff}(Y_a^2,c_{2,2}) & \mbox{coeff}(Y_a^2,c_{2,1}) & \mbox{coeff}(Y_a^2,c_{2,0}) \end{array} \right|\\&=\left(\frac{h_1}{Y_a-C_{1,a}}\right)^2\left(\frac{h_2}{Y_a-C_{2,a}}\right)^2 \left(\frac{h_3}{Y_a-C_{3,a}}\right)^4 \left|\begin{array}{cc} 1 & -C_{1,t} \\ 1 & -C_{3,t} \end{array} \right| ^2 \left| \begin{array}{cc} 1 & -C_{2,t} \\ 1 & -C_{3,t} \end{array} \right| ^2\cdot D, \end{align*} $$

where

$$ \begin{align*} D= \left| \begin{array}{cccc} 1 & -(C_{1,t-1}+C_{3,t-1}) & C_{1,t-1}C_{3,t-1} & 0 \\ 0 & 1 & -(C_{1,t-1}+C_{3,t-1}) & C_{1,t-1}C_{3,t-1} \\ 1 & -(C_{2,t-1}+C_{3,t-1}) & C_{2,t-1}C_{3,t-1} & 0 \\ 0 & 1 & -(C_{2,t-1}+C_{3,t-1}) & C_{2,t-1}C_{3,t-1} \end{array} \right|. \end{align*} $$

Note that D is just the Sylvester resultant of the two quadratic univariate polynomials $(Y-C_{1,t-1}) (Y-C_{3,t-1})$ and $(Y-C_{2,t-1})(Y-C_{3,t-1})$ . However, these two have $C_{3,t-1}$ as a common zero and hence their Sylvester resultant is $0$ . This implies that the coefficient of $Y_a^8$ in g is $0$ .

To reduce the effective degree of g further, observe that $h_3$ can be factored out from both $c_{2,2}$ and $c_{1,2}$ , which are the nonzero entries of the first column of the determinant defining g. Hence $g = h_3\cdot g^*$ for some polynomial $g^*\in \mathbb {F}_{q^{t}}[Y_1, \ldots , Y_{t-2}]$ . Since $h_3$ is linear in each variable, the degree of $g^*$ in every variable is at most six.

If $(C_1,\dots ,C_{t})$ is a common zero of $f_1, f_2,$ and $f_3$ , then, as the $b_i$ s are nonzero, we have $C_j\neq C_{i,j}$ , for $i\in [3]$ and $j\in [t]$ . In particular $h_3(C_1,\dots ,C_{t-2})\neq 0$ . On the other hand, by the properties of the Sylvester resultant, we must have $g(C_1,\dots ,C_{t-2})=0$ . This implies that $g^*(C_1,\dots ,C_{t-2})=0$ .

Denote by $\tilde {g}$ the univariate polynomial that we obtain by substituting $Y_j=Y^{q^{j-1}}$ in $g^*$ for $j\in [t-2]$ . By the degree bounds on $g^*$ we get that the degree of $\tilde {g}$ is at most $6\left (1+q+q^2+\cdots +q^{t-3}\right )$ , in particular it has at most that many roots. Now if X is a solution to the original system, then $\left (X,X^q,\dots ,X^{q^{t-1}}\right )$ is a common root of the $f_i$ s, hence $\left (X,X^q,\dots ,X^{q^{t-3}}\right )$ is a root of $g^*$ and so X is a root of $\tilde {g}$ . Consequently the number of solutions to the original system is also bounded by $6\left (1+q+q^2+\cdots +q^{t-3}\right )$ .

3.3 Three equations with six solutions

This subsection is devoted to proving part (b) of Theorem 2. Meanwhile, on the way we also give a proof of Theorem 3. As in the remainder of this subsection we will solely consider the case $t=3$ , to simplify notation, from now on we will simply write $ {\mathrm {N}}$ for the norm function $ {\mathrm {N}}_{3}$ .

For two equations we already proved that in some degenerate cases the system of norm equations has twice as many solutions as in the rest of the cases. Heuristically one could think that when considering three equations it should be easier to find a system with $6$ solutions among those that contain such exceptional subsystems. That is the reason that we look at the particular system

(3.6) $$ \begin{align} {\mathrm{N}}(X)&=1, & {\mathrm{N}}(X+1)&=-1, & {\mathrm{N}}(X+A)&=-1, \end{align} $$

where A is a nonidentity element of norm $1$ in $\mathbb {F}_{q^{3}}$ .

In what follows, we will work out the details of the heuristics described above. We start by investigating the exceptional norm equation system

(3.7) $$ \begin{align} {\mathrm{N}}(X)&=1, & {\mathrm{N}}(X+1)&=-1, \end{align} $$

and the algebraic structure of its solution set $S_3(1,-1)$ . In particular, in what follows, we prove Theorem 3. To do so, first we observe that in this case the corresponding polynomial $f_{3,1,-1}$ can be written in a product form.

(3.8) $$ \begin{align} f_{3,1,-1}(X) & =(X+1)^{q+1}X^{q+1}+(X+1)^{q+1}+X^{q+1}=X^{2q+2}+X^{2q+1}+X^{q+2}+3X^{q+1}+X^q+X+1\nonumber\\ &=(X^{q+1}+X+1)\cdot(X^{q+1}+X^q+1). \end{align} $$

We set $h_1(X)=X^{q+1}+X+1$ and $h_2(X)= X^{q+1}+X^q+1$ , so we have $f_{3,1,-1}(X)=h_1(X)\cdot h_2(X)$ . For $i=1,2$ let $\mathcal {H}_i$ denote the set of roots of $h_i$ in $\overline {\mathbb {F}}_q$ and, as before, let $\mathcal {N}$ denote the set of elements in $\mathbb {F}_{q^{3}}$ with norm $1$ . It is easy to see that $\mathcal {N}$ is an order $q^2+q+1$ subgroup of the multiplicative group $\mathbb {F}_{q^{3}}^*$ .

For general $c_1,c_2$ the polynomial $f_{3,c_1,c_2}$ can have roots which are not in $S_3(c_1, c_2)$ . The first part of Theorem 3 states that this does not happen when $(c_1,c_2)=(1,-1)$ . We prove this in the following lemma.

Lemma 4. For every prime power $q\geq 2$ we have

$$ \begin{align*} S_3(1,-1) &= \big\{X\in\overline{\mathbb{F}}_{q^3}\mid h_1(X)\cdot h_2(X)=0\big\}=\mathcal{H}_1\cup\mathcal{H}_2. \end{align*} $$

Proof. By (3.8) and by part $(i)$ of Lemma 2 we have $S_3(1,-1)\subseteq {\mathrm {R}}_3(1,-1)=\big \{X\in \overline {\mathbb {F}}_{q^3}\mid h_1(X)\cdot h_2(X)=0\big \}$ .

Now let $X\in \overline {\mathbb {F}}_{q}$ be such that $h_1(X)\cdot h_2(X)=0$ . Then either

$$ \begin{align*} h_1(X)=0 \text{ and hence } X^q = -\frac{X+1}{X}=v(X) ,\quad \text{ or }\quad h_2(X)=0 \text{ and hence } X^q =-\frac{1}{X+1}=u(X). \end{align*} $$

In the first case

$$ \begin{align*} X^{q^2} = v\big(v(X)\big) = -\frac{-\frac{X+1}{X}+1}{-\frac{X+1}{X}} = u(X) \end{align*} $$

and

$$ \begin{align*} X^{q^3}=v\Big(v\big(v(X)\big)\Big)=v\big(u(X)\big)=-\frac{-\frac{1}{X+1}+1}{-\frac{1}{X+1}}=X, \end{align*} $$

while in the latter case

$$ \begin{align*} X^{q^2} = u\big(u(X)\big) = -\frac{1}{-\frac{1}{X+1}+1} = v(X) \end{align*} $$

and

$$ \begin{align*} X^{q^3}=u\Big(u\big(u(X)\big)\Big)=u\big(v(X)\big)=-\frac{1}{-\frac{X+1}{X}+1}=X. \end{align*} $$

In particular, in both cases we have $X\in \mathbb {F}_{q^{3}}$ and $X^q\cdot X^{q^2}=u(X)v(X)$ . Accordingly,

$$ \begin{align*} {\mathrm{N}}(X) = X\cdot X^q\cdot X^{q^2} = X\cdot v(X)\cdot u(X) = X\cdot \left(-\frac{1}{X+1}\right)\cdot\left(-\frac{X+1}{X} \right) = 1. \end{align*} $$

Similarly, for the norm of $X+1$ we get

$$ \begin{align*} {\mathrm{N}}(X+1)&= (X+1)(X^q+1)(X^{q^2}+1)= (X+1)(u(X)+1)(v(X)+1)\\ &= (X+1)\cdot\left(-\frac{1}{X+1}+1\right) \cdot \left( -\frac{X+1}X+1\right)= -1. \end{align*} $$

This shows that $X\in S_3(1,-1)$ and hence $\big \{X\in \overline {\mathbb {F}}_{q^3}\mid h_1(X)\cdot h_2(X)=0\big \}\subseteq S_3(1,-1)$ .

Note that Lemma 4, in particular, also shows that $\mathcal {H}_1,\mathcal {H}_2\subseteq \mathcal {N}$ . The second part of Theorem 3 will directly follow from the next proposition where we prove several helpful properties of the sets $\mathcal {H}_i$ .

Proof. The statement of $(i)$ follows from the simple fact $h_2\left ( \frac 1X \right ) =\frac {h_1(X)}{X^{q+1}}$ .

For $(ii)$ we first show the uniqueness of the representation of the form (3.9). Suppose that $A\in \mathcal {N}\setminus \{ 1\}$ and $A =A_1 \cdot A_2$ with $A_1\in \mathcal {H}_1$ and $A_2=\frac {A}{A_1}\in \mathcal {H}_2$ . Then

$$ \begin{align*} A_1^{q+1}+A_1 +1=0 & & \text{and} & & \left( \frac{A }{A_1}\right)^{q+1}+\left(\frac{A}{A_1}\right)^q+1=0. \end{align*} $$

By expressing $A_1^{q}$ from the two equations we obtain

$$ \begin{align*} \frac{A_1+1}{A_1}=\frac{A^{q+1}}{A_1} +A^q. \end{align*} $$

Solving for $A_1$ gives that the only possibility is

$$ \begin{align*} A_1 =\frac{A^{q+1}-1}{1-A^q }. \end{align*} $$

This gives uniqueness and the stated formula (3.9) for $A_2=\frac {A}{A_1}$ as well. It remains to verify that $A_i\in \mathcal {H}_i$ . We consider first $A_1$ . Using $ {\mathrm {N}}(A)=A^{q^2+q+1}=1$ we get

$$ \begin{align*} h_1(A_1) &= \frac {A^{q+1}-1}{1-A^{q}}\cdot \left( \frac {A^{q+1}-1}{1-A^{q}}\right)^q+ \frac {A^{q+1}-1}{1-A^{q}}+1= \frac {A^{q+1}-1}{1-A^{q}}\cdot\frac {A^{q^2+q}-1}{1-A^{q^2}}+ \frac {A^{q}\cdot (A -1)}{1-A^{q}}\\ &= \frac {\frac{1}{A^{q^2}}-1}{1-A^{q}} \cdot \frac {\frac{1}{A}-1}{1-A^{q^2}}+ \frac {\frac{1}{A^{q^2+1}}(A -1)}{1-A^{q}}= \frac {1-A}{A^{q^2+1}\cdot (1-A^{q})}+ \frac {A -1}{A^{q^2+1} \cdot (1-A^{q})}=0, \end{align*} $$

and hence $A_1\in \mathcal {H}_1$ . The verification of $A_2\in \mathcal {H}_2$ is a similar calculation that we leave to the reader.

To see the desired equalities of sets in $(iii)$ , note that for an element $Y\in \mathbb {F}_{q^{3}}$ we have $h_1(Y)=h_2(Y)$ if and only if $Y=Y^{q}$ , which happens if and only if $Y\in \mathbb {F}_q$ . Then for $3|q$ we have $X^2+X+1= (X-1)^2$ , while otherwise the nontrivial third-roots of unity are in $\mathbb {F}_q$ if and only if $3|q-1$ .

The statement of $(iv)$ is a direct consequence of the facts that the Frobenius map is an automorphism of the field $\mathbb {F}_{q^{3}}$ that fixes $\mathbb {F}_q$ and $\mathcal {H}_1$ and $\mathcal {H}_2$ are both the set of roots of a polynomial with coefficients in $\mathbb {F}_q$ .

Note that as in an order $q^2+q+1$ multiplicative group any difference set must have size $q+1$ , Theorem 3, in particular, also implies that $\left |\mathcal {H}_1\right |=\left |\mathcal {H}_2\right |=q+1$ , which in turn is equivalent to the polynomials $h_1,h_2$ splitting into linear factors over $\mathbb {F}_{q^{3}}$ .

Next we connect our main interest, the solution set of (3.6), to the solution set of (3.7), and hence to the difference sets $\mathcal {H}_1$ , $\mathcal {H}_2$ .

Proof. By Lemma 4 we know that Y and $\frac {A}{Y}$ are both contained in $\mathcal {H}_1 \cup \mathcal {H}_2$ if and only if they are both solutions of (3.7). We show that this is equivalent to Y being a solution of (3.6).

Suppose first that $Y\in \mathbb {K}$ is a solution of (3.6). Then a fortiori Y is a solution of (3.7) and $Y\ne 0$ . Also,

$$ \begin{align*} {\mathrm{N}}\left( \frac{A}{Y}\right)=\frac{{\mathrm{N}}(A)}{{\mathrm{N}}(Y)}=\frac{1}{1}=1 & & \text{ and } & & {\mathrm{N}}\left( \frac{A}{Y}+1\right)={\mathrm{N}}\left(\frac{A+Y}{Y}\right) = \frac{{\mathrm{N}}(A+Y)}{{\mathrm{N}}(Y)}=\frac{-1}{1}=-1, \end{align*} $$

hence $\frac {A}{Y}$ is also a solution of (3.7).

Conversely, assume that Y and $\frac {A}{Y}$ are both solutions of (3.7). Then, in particular, Y satisfies the first two equations from (3.6), as for the third one we have

$$ \begin{align*} {\mathrm{N}}(Y+A)= {\mathrm{N}}\left( Y\left(1+\frac{A}{Y}\right)\right)= {\mathrm{N}}(Y) {\mathrm{N}}\left(\frac{A}{Y}+1\right)=1\cdot -1=-1, \end{align*} $$

and hence Y is a solution of (3.6).

By the previous proposition, when trying to solve (3.6) we will be looking for product representations $Y \cdot \frac {A}{Y}$ of the element A involving factors from $\mathcal {H}_1 \cup \mathcal {H}_2$ . To prove part (b) of Theorem 2 we will need to find an element $A \in \mathcal {N} \setminus \{ 1\}$ that has three such product representations $A=B_1C_1 =B_2C_2=B_3C_3$ , such that the six elements $B_1,C_1, B_2, C_2, B_3, C_3 \in \mathcal {H}_1 \cup \mathcal {H}_2$ are all distinct. For this we will crucially use that $\mathcal {H}_1$ and $\mathcal {H}_2 = \mathcal {H}_1^{-1}$ are difference sets in $\mathcal {N}$ and inverses of each other.

Recall that if $\mathcal {D}$ is any difference set in some multiplicative group G then every element $A \in G\setminus \{1\}$ has a unique representation, called mixed representation, as a product $B\cdot C=A$ such that one of B and C is from $\mathcal {D}$ and the other is from $\mathcal {D}^{-1}$ . In the next propositions we summarize our knowledge about other product representations. To this end we will call a product $B\cdot C =A$ a $\mathcal {D}$ -representation of the element $A\in G$ if both B and C are from $\mathcal {D}$ .

The explicit descriptions of our specific difference sets allow us to characterize when an $\mathcal {H}_i$ -representation with distinct factors exists.

Proof. As the proof of the two parts is analogous, below we only present the one of $(i)$ .

Suppose first that $A\in \mathcal {N}$ has an $\mathcal {H}_1$ -representation. This means that there is an element $Y\in \mathbb {F}_{q^{3}}$ such that Y and $\frac {A}{Y}$ are both roots of $h_1$ , that is,

$$ \begin{align*} h_1(Y)&=Y^{q+1}+Y+1=0 & \text{and} & & h_1\left(\frac{A}{Y}\right)&=\left(\frac{A}{Y}\right)^q\cdot \frac{A}{Y}+\frac{A}{Y}+1=0. \end{align*} $$

After expressing $Y^q$ from both equations, letting them being equal and clearing denominators we obtain $Y^2+\left (A+1-A^{q+1}\right )\cdot Y+A=0$ . Clearly, the role of Y and $\frac {A}{Y}$ can be switched, which means that both Y and $\frac {A}{Y}$ are roots of the quadratic equation

(3.10) $$ \begin{align} X^2+\left(A+1-A^{q+1}\right)\cdot X+A=0. \end{align} $$

This is possible only if the discriminant

$$ \begin{align*} D=\left(A+1-A^{q+1}\right)^2-4A \end{align*} $$

is a nonzero square in $\mathbb {F}_{q^{3}}$ .

For the other direction suppose that $D=\left (A+1-A^{q+1}\right )^2-4A$ is a nonzero square in $\mathbb {F}_{q^{3}}$ , that is, there is some element $G\in \mathbb {F}_{q^{3}}^*$ such that $D=G^2$ . Then we know that the quadratic equation in (3.10) has two different roots, namely $X_{\pm }=\frac {A^{q+1}-A-1\pm G}{2}$ . Clearly, $X_{+}\cdot X_{-}=A$ , so to finish the proof it is enough to show that $X_{\pm }\in \mathcal {H}_1$ , that is, $h_1(X_{\pm })=0$ .

Using $N(A)=A^{q^2+q+1}=1$ we have

$$ \begin{align*} D^q &=\left(\left(A+1-A^{q+1}\right)^2-4A\right)^q=\left(A^q+1-A^{q^2+q}\right)^2-4 A^q=\\ &=\left(A^q+1-\frac{1}{A}\right)^2-4A^q=\frac{1}{A^2}\left(\left(A^{q+1}+A-1\right)^2-4A^{q+2}\right)= \\ &=\frac{1}{A^2}\left(\left(A+1-A^{q+1}\right)^2-4A\right)=\frac{1}{A^2}D. \end{align*} $$

Then

$$ \begin{align*} \left(\frac{G^q}{G}\right)^2=\frac{(G^2)^q}{G^2}=\frac{D^q}{D}=\frac{\frac{1}{A^2}D}{D}=\frac{1}{A^2} \end{align*} $$

and hence $\frac {G^q}{G}=\pm \frac {1}{A}$ . However

$$ \begin{align*} N\left(\frac{G^q}{G}\right)=\frac{G^q}{G}\cdot \left(\frac{G^q}{G}\right)^q\cdot\left(\frac{G^q}{G}\right)^{q^2}=\frac{G^q}{G}\cdot \frac{G^{q^2}}{G^q}\cdot\frac{G}{G^{q^2}}=1 \end{align*} $$

which, excludes $\frac {G^q}{G}=-\frac {1}{A}$ . Therefore $G^q=\frac {1}{A}G$ . As a consequence we get

$$ \begin{align*} (X_{\pm})^q &=\phi\left(\frac{A^{q+1}-A-1\pm G}{2}\right)=\frac{A^{q^2+q}-A^q-1\pm G^q}{2}=\\ &=\frac{\frac{1}{A}-A^q-1\pm\frac{1}{A}G}{2}=\frac{1}{A}X_{\pm}+\frac{1-A^{q+1}}{A}. \end{align*} $$

Now we are ready to substitute $X_{\pm }$ into $h_1$ .

$$ \begin{align*} h_1(X_{\pm})&=X_{\pm}\cdot (X_{\pm})^q+X_{\pm}+1=X_{\pm}\cdot\left(\frac{1}{A}X_{\pm}+\frac{1-A^{q+1}}{A}\right)+X_{\pm}+1=\\ &=\frac{1}{A}\left(X_{\pm}^2+\left(A+1-A^{q+1}\right)\cdot X_{\pm}+A\right)=0, \end{align*} $$

where at the last equality we just used that $X_{\pm }$ are the roots of (3.10).

To finish the proof just note that when $A\in \mathcal {H}_1$ then $(A+1 - A^{q+1})^2 - 4A$ simplifies to $4(A^2+A+1)$ , which is a nonzero square in $\mathbb {F}_{q^{3}}$ if and only $A^2+A+1$ is such.

For the elements of $\mathcal {H}_i$ the existence of a $\mathcal {H}_{3-i}$ -representation follows directly.

To continue, we will need to split the proof into three different cases based on the remainder of $p \ \pmod 3$ .

3.3.1 Case I: $p\equiv 2 \ \pmod 3$

In this subsection we settle the case when $p\equiv 2 \ \pmod 3$ , in particular the case of even characteristic.

First we show the existence of six solutions when q is congruent to $2$ modulo $3$ (as opposed to p). Recall that to do so we aim to find an element $A\in \mathcal {N} \setminus \{ 1 \}$ , which, next to its unique mixed representation $A=A_1\cdot A_2$ with $A_1\in \mathcal {H}_1$ and $A_2\in \mathcal {H}_2$ (which exists by Proposition 2), also has an $\mathcal {H}_i$ -representation $A = B_i\cdot C_i$ for both $i=1$ and $2$ , such that $B_i\neq C_i$ , and these six elements are all different. Note that the latter follows immediately from the fact that, when $q\equiv 2 \ \pmod 3$ the sets $\mathcal {H}_1$ and $\mathcal {H}_2$ are disjoint by Proposition 2, part $(iii)$ .

In order to find the appropriate element A for which the $\mathcal {H}_i$ -representations exist, for a set $\mathcal {H}\subseteq \mathcal {N}$ we define

$$ \begin{align*} \mathcal{H}^*:=\{B\cdot C\ :\ B,C\in \mathcal{H},\ B\ne C\} \end{align*} $$

to be the set of its pairwise products from distinct factors, and show that $\mathcal {H}_1^* \cap \mathcal {H}_2^*$ is not empty. An element from this intersection is clearly suitable.

First note that by Proposition 4 the pairwise products of the elements of $\mathcal {H}_i$ are all distinct, hence the cardinality of $\mathcal {H}_i^*$ is $\binom {|\mathcal {H}_i|}{2} = \frac {q^2+q}{2}$ . Both $\mathcal {H}_1^*$ and $\mathcal {H}_2^*$ are subsets of the $(q^2+q)$ -element set $\mathcal {N} \setminus \{ 1\}$ . For this note that $\mathcal {H}_i$ is contained in $\mathcal {N}$ , which is closed under multiplication, and that $1 \not \in \mathcal {H}_i^*$ since $\mathcal {H}_i$ is disjoint from its inverse $\mathcal {H}_{3-i}$ by our assumption on q and Proposition 2, part $(iii)$ . Hence the only way $\mathcal {H}_1^*$ and $\mathcal {H}_2^*$ could be disjoint is if their union is $\mathcal {N} \setminus \{ 1 \}$ . In this case however it would also hold that

(3.11) $$ \begin{align} \sigma(\mathcal{N}\setminus \{1\})=\sigma(\mathcal{H}_1^*)+\sigma(\mathcal{H}_2^*), \end{align} $$

where $\sigma (\mathcal {S})$ denotes the sum of the elements of a subset $\mathcal {S}\subseteq \mathbb {F}_{q^3}$ . On the one hand the set $\mathcal {N}$ is the collection of all $q^2+q+1$ roots in $\mathbb {F}_{q^3}$ of the polynomial $X^{q^2+q+1}-1$ and so $\sigma (\mathcal {N})$ is $(-1)$ times the coefficient of $X^{q^2+q}$ in this polynomial, which is $0$ . From this we obtain that $\sigma (\mathcal {N}\setminus \{1\})=-1$ . On the other hand $\mathcal {H}_i$ is the set of all $q+1$ roots in $\mathbb {F}_{q^3}$ of the polynomial $h_i(X)$ , hence $\sigma (\mathcal {H}_i^*)$ is the coefficient of $X^{q-1}$ in $h_i(X)$ , which is 0 for $q>2$ . We arrived to a contradiction, as the left hand side of (3.11) is (-1), while the right hand side is $0$ . This settles the case when $q\equiv 2 \ \pmod 3$ .

For the more general case, next note that $\mathbb {F}_{q^6}$ is a cubic extension of $\mathbb {F}_{q^2}$ and the norm of an element $B\in \mathbb {F}_{q^3}\subseteq \mathbb {F}_{q^6}$ is the same, irrespective in which of the two fields we compute it: $ {\mathrm {N}}_{\mathbb {F}_{q^3}/\mathbb {F}_q} (B) = {\mathrm {N}}_{\mathbb {F}_{q^6}/\mathbb {F}_{q^2}} (B)$ .

This means that if for an element $A\in \mathbb {F}_{q^3}$ with $ {\mathrm {N}}_{\mathbb {F}_{q^3}/\mathbb {F}_q}(A) = 1$ the system (3.6) with the norm function $ {\mathrm {N}}_{\mathbb {F}_{q^3}/F_q}$ has six distinct solutions $X_1, \ldots , X_6 \in \mathbb {F}_{q^3}$ , then the very same six elements are also solutions of the the system (3.6) with the norm function $ {\mathrm {N}}_{\mathbb {F}_{q^6}/F_{q^2}}$ .

Now let $p \equiv 2 \ \pmod 3$ be a prime and let $q=p^k=p^{\ell 2^m}$ be an arbitrary power where $\ell $ is odd. Then from above we get the required six distinct solutions when $m=0$ and $p^\ell> 2$ . By repeated application of the previous observation, the statement also follows for any positive integer m and $p^\ell>2$ . These include all the powers when $p> 2$ .

When $p=2$ then only those powers are included where $\ell \geq 3$ . So we are left with prime powers of the form $2^{2^m}$ . To settle these last cases one first resolves the problem when the prime power is $2^{2^2} =16$ and then uses the above squaring trick to deduce the case of arbitrary $2^{2^m} = 16^{2^{m-2}}$ .

For $q=16$ we have found the appropriate $A \in \mathbb {F}_{16^3}$ of norm $1$ , for which the system (3.6) has six distinct solutions with the aid of a computer. To describe this example, let U be the primitive element of $\mathbb {F}_{16^3}^*$ whose minimal polynomial over $\mathbb {F}_{2}$ is $X^{12} + X^7 + X^6 + X^5 + X^3 + X + 1$ , and consider the system

$$ \begin{align*} {\mathrm{N}}(X)&=1, & {\mathrm{N}}(X+1)& =1, & {\mathrm{N}}(X+U^{405})&=1. \end{align*} $$

By Magma Calculator [Reference Bosma, Cannon and Playoust20] it is easily verified that $A=U^{405}$ is in $\mathcal {N}\setminus \{1\}$ , and that the system has indeed six solutions, namely $U^{1725}, U^{2775}, U^{3435}\in \mathcal {H}_1$ and $U^{1065}, U^{2130}, U^{2370}\in \mathcal {H}_2$ with

$$ \begin{align*} A=U^{1065}\cdot U^{3435}= U^{1725}\cdot U^{2775}=U^{2130}\cdot U^{2370}. \end{align*} $$

3.3.2 Case II: $p=3$

In this subsection we settle the case when $p=3$ . Our strategy is the same as in the previous subsection, but now we do this in two steps. First we find an element that has both $\mathcal {H}_1$ - and $\mathcal {H}_2$ -representation, but in one of them the factors are not distinct.

Lemma 5. For $i=1$ or $2$ there is an element $C\in \mathcal {H}_i \setminus \{ 1 \}$ , such that $C^2$ has an $\mathcal {H}_{3-i}$ -representation $C^2=B\cdot E$ with distinct factors $B\neq E$ .

Proof. We want to find a $C\in \mathcal {H}_i\setminus \{ 1 \}$ for $i=1$ or $2$ , such that $C^2$ has an $\mathcal {H}_{3-i}$ -representation with different elements B and E. This happens exactly if one of the formulas in Proposition 5 is a nonzero square in $\mathbb {F}_{q^3}$ when we substitute $A=C^2$ . In the first case we have

$$ \begin{align*} D_1 = (A+1-A^{q+1})^2 - 4A = (C^2+1-C^{2q+2})^2-4C^2. \end{align*} $$

Using $h_2(C) =C^{q+1}+C^q+1=0$ we can substitute $C^q=-\frac {1}{C+1}$ , resulting in

$$ \begin{align*} D_1&= \left(C^2+1-C^2\cdot \left(\frac{1}{(C+1)^2}\right)\right)^2-4C^2 \\ &= \frac{1}{(C+1)^4} \cdot \left( \left(C^2(C+1)^2+(C+1)^2-C^2\right)^2 - 4(C+1)^4C^2 \right). \end{align*} $$

In the other case we similarly have

$$ \begin{align*} D_2 = (A^{q+1}+A^q-1)^2 - 4A^{2q+1} = (C^{2q+2} + C^{2q} -1)^2-4C^{4q+2}. \end{align*} $$

Using $h_1(C)=C^{q+1}+C+1=0$ we now can substitute $C^q=-\frac {C+1}{C}$ , resulting in

$$ \begin{align*} D_2 &= \left(C^2\left(\frac{C+1}{C}\right)^2 + \left(\frac{C+1}{C}\right)^2 -1\right)^2-4C^2 \left(\frac{C+1}{C}\right)^4 \\ &= \frac{1}{C^4} \cdot \left( \left(C^2(C+1)^2+(C+1)^2-C^2\right)^2 - 4(C+1)^4C^2 \right). \end{align*} $$

Now we see that $D_1$ and $D_2$ is a square exactly if

$$ \begin{align*} D=D(C)=&\left(C^2(C+1)^2+(C+1)^2-C^2\right)^2-4(C+1)^4C^2=\\ =&\left(C^2+3C+1\right)\cdot\left(C^2+C+1\right)\cdot\left(C^2+C-1\right)\cdot\left(C^2-C-1\right) \end{align*} $$

is so, hence we aim to find an element $C\in \mathcal {H}_1\cup \mathcal {H}_2 \setminus \{ 1 \}$ for which D is a square in $\mathbb {F}_{q^3}$ , or equivalently, $N(D)$ is a square in $\mathbb {F}_q$ .

As it turns out the factors of $N(D)$ can be conveniently expressed using the trace $ {\mathrm {Tr}}_{3,q}(C) = C + C^q + C^{q^2} =: \tau $ of C:

$$ \begin{align*} &N(C^2+3C+1) =-\tau^2-3\tau -1,\\ &N(C^2+C+1) =\tau^2 + 3\tau +9,\\ &N(C^2+C-1) =\tau^2+3\tau+1,\\ &N(C^2-C-1) =-\tau^2-3\tau-1, \end{align*} $$

and so

$$ \begin{align*} N(D)= (-\tau^2 -3\tau -1)^2 (\tau^2+3\tau +9) (\tau^2+3\tau +1). \end{align*} $$

In characteristic $3$ this expression is a square if and only if $\tau ^2+1$ is a square. Using Theorem 5.18 from [Reference Lidl and Niederreiter48] we get that

$$ \begin{align*} \sum_{Y\in \mathbb{F}_q}\eta_{\mathbb{F}_q}(Y^2+1)=-\eta_{\mathbb{F}_q}(1)=-1, \end{align*} $$

Therefore, as $Y^2 +1 =0$ has at most two solutions, for at least $\displaystyle \frac {q-3}{2}$ elements $y\in \mathbb {F}_q$ the expression $Y^2+1$ is a square.

This ensures the existence of many good “traces,” which we can use to construct many good C, as we now show that the trace function is a $3$ -to- $1$ function on $\mathcal {H}_1 \cup \mathcal {H}_2 \setminus \{ 1 \}$ . That is, if $ {\mathrm {Tr}}(C_1) = {\mathrm {Tr}}(C_2)$ for $C_1, C_2 \in \mathcal {H}_1 \cup \mathcal {H}_2\setminus \{1\}$ then $C_1$ and $C_2$ are conjugates of each other. For this we note that the minimal polynomial of an element C of $\mathcal {H}_1 \cup \mathcal {H}_2\setminus \{ 1 \}$ can be expressed just by the trace $\tau $ of C:

$$ \begin{align*} m_{\tau}(X)=(X-C)(X-C^q)(X-C^{q^2}) = X^3- \tau X^2- (\tau+3)X-1. \end{align*} $$

Hence if $C_1$ and $C_2$ have the same trace, then they have the same minimal polynomial.

Consequently there are exactly $\frac {|\mathcal {H}_1 \cup \mathcal {H}_2 \setminus \{ 1\}|}{3} = \frac {2q}{3}$ elements in $\mathbb {F}_q^*$ that are traces of some element in $\mathcal {H}_1 \cup \mathcal {H}_2 \setminus \{ 1 \}$ .

In conclusion, if $q>9$ then there are at least $\left (\frac {2q}{3} + \frac {q-3}{2}\right )-q = \frac {q-9}{6}> 0$ elements $t\in \mathbb {F}_q$ which are traces of an element C from $\mathcal {H}_1 \cup \mathcal {H}_2 \setminus \{ 1 \}$ , and for which $t^2+1$ , and hence also $D=D(C)$ , is a square. This completes the proof for $q>9$ .

Otherwise, by our assumption on q, we are left with the case $q = 9$ . Then we can directly find a $\tau \in \mathbb {F} _9$ such that it is the trace of an element $C\in \mathcal {H}_1 \cup \mathcal {H}_2 \setminus \{ 1 \}$ and $\tau ^2+1$ is a nonzero square in $\mathbb {F}_9$ . In fact $\tau =-1$ will do. First note that $\tau ^2+1=1+1=2$ is in $\mathbb {F}_3$ and hence is a square in its quadratic extension $\mathbb {F}_9$ . Now, to finish the argument it is enough to show that $m_{-1}(X)=X^3+X^2+X-1$ is the minimal polynomial of some $C\in \mathcal {H}_1 \cup \mathcal {H}_2 \setminus \{ 1 \}$ over $\mathbb {F}_9$ , because then we automatically have $ {\mathrm {Tr}}(C)=\tau =-1$ . It is immediate that $m_{-1}(X)$ is irreducible over $\mathbb {F}_3$ , hence it cannot have a root in $\mathbb {F}_9$ , and therefore it is irreducible over $\mathbb {F}_9$ . Next consider the polynomial $h_1(X)$ for $q=3$ . Then (when computed over $\mathbb {F}_3$ ) we have

$$ \begin{align*} h_1(X)=X^4+X+1=(X-1)(X^3+X^2+X-1)=(X-1)m_{-1}(X), \end{align*} $$

which in view of Lemma 4 means that the roots of $m_{-1}(X)$ solve the system (3.7) with norm function $ {\mathrm {N}}_{\mathbb {F}_{3^3}/\mathbb {F}_3}$ . But then, as we have seen earlier, the roots of $m_{-1}(X)$ also solve the system (3.7) with norm function $ {\mathrm {N}}_{\mathbb {F}_{9^3}/\mathbb {F}_9}$ , and hence, again by Lemma 4 and the fact $m_{-1}(1)\neq 0$ , we have that any root of $m_{-1}$ is in $\mathcal {H}_1 \cup \mathcal {H}_2\setminus \{1\}$ , as desired.

Let us now fix elements $C\in \mathcal {H}_i \setminus \{ 1 \}$ and $B, E \in \mathcal {H}_{3-i}$ guaranteed by Lemma 5. We show that the element $A:=\frac {C}{E}$ is the kind we are looking for. First observe that by Proposition 2, part $(i)$

$$ \begin{align*} A = C\cdot \frac{1}{E} = B\cdot \frac{1}{C} \end{align*} $$

provide a $\mathcal {H}_i$ - and $\mathcal {H}_{3-i}$ -representation of A, respectively. Note furthermore that as $(\mathcal {H}_i \setminus \{ 1 \}) \cap \mathcal {H}_{3-i} = \emptyset $ , we have $C\neq E$ and hence $A \neq 1$ . Consequently, by Proposition 2, part $(ii)$ there exists a unique mixed representation $A=A_1\cdot A_2 $ with $A_i\in \mathcal {H}_i$ .

Next we show that these six elements from the representations are all distinct. By Proposition 3 these elements then provide six distinct solutions of (3.6).

Lemma 6. The elements $A_i, C, \frac {1}{E} \in \mathcal {H}_i$ and $A_{3-i}, \frac {1}{C}, B \in \mathcal {H}_{3-i}$ are all distinct.

Proof. For the distinctness first we establish that none of the six elements is $1$ . This is certainly true for C and $\frac {1}{C}$ by the choice of C in Lemma 5. Now assume that B or E is $1$ , say $B=1$ (the argument in the case $E=1$ is analogous). On the one hand, as $E \in \mathcal {H}_{3-i}$ , by Proposition 6 E has a unique $\mathcal {H}_i$ -representation: $E = \frac {1}{E^q} \cdot \frac {1}{E^{q^2}}$ . On the other hand $E=1\cdot E= B\cdot E = C\cdot C$ and as $C\in \mathcal {H}_i$ , this results in another $\mathcal {H}_i$ -representation of E. By the uniqueness of an $\mathcal {H}_i$ -representation we must have $E^q = \frac {1}{C} = E^{q^2} = \phi (E^q)$ , and thus $E^q\in \mathbb {F}_q$ and $E^q =\frac {1}{C} \in \mathcal {H}_{3-i}$ . That means $\phi (E)=E^q \in \mathbb {F}_q\cap \mathcal {H}_{3-i} = \mathcal {H}_1 \cap \mathcal {H}_2 = \{ 1 \}$ by Proposition 2, part $(iii)$ , which is only possible if $E=1$ . This contradicts $C\neq 1$ and implies $B, E\neq 1$ . Finally assume that $A_1$ or $A_2$ is equal to $1$ , say $A_1=1$ . Then $A_1\cdot A_2 = A = B\cdot \frac {1}{C}$ are two $\mathcal {H}_2$ -representations of A. By uniqueness either B or C should be $1$ , which is a contradiction by the above.

Since none of the six elements is $1$ and by part $(iii)$ of Proposition 2 $\mathcal {H}_1\cap \mathcal {H}_2=\{1\}$ , we established that

$$ \begin{align*} \displaystyle \left\{A_i,C,\frac{1}{E}\right\}\cap \left\{A_{3-i},B,\frac{1}{C}\right\}=\emptyset. \end{align*} $$

We are left to show that $\left |\{A_i,C,\frac {1}{E}\}\right |=3$ and $\left |\{A_{3-i},B,\frac {1}{C}\right |=3$ . Since they are proved analogously we present just the first one.

If $A_i=C$ , then $A_{3-i}=\frac {1}{E}$ , which is a contradiction as $A_{3-i}\in \mathcal {H}_{3-i}$ and $\frac {1}{E}\in \mathcal {H}_i$ and none of them is $1$ . If $A_i=\frac {1}{E}$ , then $A_{3-i}=C$ , which is a contradiction similarly as $A_{3-i}\in \mathcal {H}_{3-i}$ and $C\in \mathcal {H}_i$ and none of them is $1$ . Finally, suppose that $C=\frac {1}{E}$ . Then we have $B=C^2\cdot \frac {1}{E}=C^3$ , which is a contradiction as $B\in \mathcal {H}_{3-i}\setminus \{1\}$ and $C^3\in \mathcal {H}_i\setminus \{1\}$ because the polynomial $h_i$ is defined over $\mathbb {F}_3$ , hence if $h_i(C)=0$ , then $h_i(C^3)=0$ as well.

3.3.3 Case III: $q\equiv 1\ \pmod 3$ odd

The last case we consider is when $q\equiv 1\ \pmod 3$ . Note that this, in particular, covers the cases when $p\equiv 1\ \pmod 3$ . We remark that the proof below can be adapted whenever $p\geq 5$ , but for simplicity we only present it for the particular case $q\equiv 1\ \pmod 3$ .

As in the previous subsection we aim again to find an A which has three distinct representations, but instead of looking for it in $\mathcal {N}\setminus \{1\}$ we will restrict ourselves to $\mathcal {H}_1\cup \mathcal {H}_2$ . With such a choice of A, Proposition 2 still guarantees a mixed representation $A=A_1\cdot A_2$ with $A_i\in \mathcal {H}_i$ , but now, if say $A\in \mathcal {H}_i$ then Proposition 6 also guarantees an $\mathcal {H}_{3-i}$ representation $A=\frac {1}{A^q}\cdot \frac {1}{A^{q^2}}$ . Therefore, what is left is to find an $\mathcal {H}_i$ -representation $A=B\cdot C$ with different factors $B,C\in \mathcal {H}_i$ . According to Proposition 5 such a representation exists exactly if $A^2+A+1$ is a nonzero square in $\mathbb {F}_{q^{3}}$ . To look for such an element, it will be convenient to embed the set $\mathcal {H}_1\cup \mathcal {H}_2$ into a more structured ambiance.

For this, let us fix a nontrivial third root of unity $\alpha \in \mathbb {F}_q$ (which exists when $3\mid q-1$ ) and consider the linear fractional transformation $\gamma : \mathbb {F}_{q^{3}}\setminus \{\alpha \} \rightarrow \mathbb {F}_{q^{3}}$ , defined by

$$ \begin{align*} \gamma(Z)=\frac{Z - \alpha^{-1}}{Z - \alpha}. \end{align*} $$

Further let us denote by G the multiplicative group of $3(q-1)$ -st roots of unity in $\mathbb {F}_{q^{3}}$ , that is,

$$ \begin{align*} G = \left\{ Y\in \mathbb{F}_{q^{3}}^* \mid Y^{3(q-1)} = 1\right\}. \end{align*} $$

Note that as $q\equiv 1\ \pmod 3$ , G is well defined and has size $3(q-1)$ .

Lemma 7. If $q\equiv 1\ \pmod 3$ then the map $Z \mapsto \gamma (Z)$ is a bijection from the symmetric difference $\mathcal {H}_1 \triangle \mathcal {H}_2=(\mathcal {H}_1\setminus \mathcal {H}_2)\cup (\mathcal {H}_2\setminus \mathcal {H}_1)$ to $G \setminus \mathbb {F}_q^*$ .

Proof. Let $Z\in \mathcal {H}_1\triangle \mathcal {H}_2$ . As $\alpha ,\alpha ^{-1}\in \mathcal {H}_1\cap \mathcal {H}_2$ the value $\gamma (Z)$ is well defined and nonzero. We aim to show that $\gamma (Z)\in G \setminus \mathbb {F}_q^*$ , which happens exactly if $\gamma (Z)^{q-1}\neq 1$ but $\gamma (Z)^{3(q-1)}=1$ . Without loss of generality we may assume that $Z\in \mathcal {H}_1\setminus \mathcal {H}_2$ , the other case can be handled analogously.

$$ \begin{align*} \gamma(Z)^{q} = \frac{(Z-\alpha^{-1})^q}{(Z-\alpha)^q}=\frac{Z^q-\alpha^{-q}}{Z^q-\alpha^q}= \frac{Z^q-\alpha^{-1}}{Z^q-\alpha} \end{align*} $$

As $Z\in \mathcal {H}_1$ , we have $Z^q = - \frac {Z+1}{Z}$ , and hence, using $1+\alpha +\alpha ^{-1}=0$ and $\alpha ^2=\alpha ^{-1}$ we obtain

$$ \begin{align*} \gamma(Z)^{q} = \frac{-\frac{Z+1}{Z}-\alpha^{-1}}{-\frac{Z+1}{Z}-\alpha}= \frac{Z\alpha^{-1}+Z+1}{Z\alpha+Z+1} = \frac{Z\alpha - 1}{Z\alpha^{-1} - 1}= \frac{Z-\alpha^{-1}}{Z-\alpha} \cdot \alpha^{-1} = \gamma(Z) \cdot \alpha^{-1}. \end{align*} $$

Therefore, $\gamma (Z)^{q-1}=\alpha ^{-1}\neq 1$ , but $\gamma (Z)^{3(q-1)}=(\alpha ^{-1})^3=1$ , as desired.

$\gamma $ is clearly injective because it is a nontrivial fractional linear map, and hence to verify that $\gamma $ is indeed a bijection between the two sets it is enough to show that they are of the same size. On the one hand, as $\mathbb {F}_q^*$ is fully contained in G, the set $G\setminus \mathbb {F}_q^*$ has size $3(q-1)-(q-1)=2(q-1)$ . On the other hand, as $|\mathcal {H}_i|=q+1$ and $\mathcal {H}_1\cap \mathcal {H}_2=\{\alpha ,\alpha ^{-1}\}$ , the set $\mathcal {H}_1\triangle \mathcal {H}_2$ has the same size.

Recall that we want to find an element $A\in \mathcal {H}_1\cup \mathcal {H}_2$ for which $A^2+A+1$ is a nonzero square in $\mathbb {F}_{q^{3}}$ . This will be done using the following lemma.

Lemma 8. If $q\equiv 1\ \pmod 3$ , then for every $A\in \mathcal {H}_1\triangle \mathcal {H}_2$ , we have

$$ \begin{align*} \eta_{\mathbb{F}_{q^{3}}}(A^2+A+1) = \eta_{\mathbb{F}_{q^{3}}}(\gamma(A)), \end{align*} $$

that is, $A^2+A+1$ is a square in $\mathbb {F}_{q^{3}}$ if and only if $\gamma (A)$ is such.

Proof. Let $r\in \overline {\mathbb {F}}_q$ and $s \in \overline {\mathbb {F}}_q$ be a square root of $A^2+A+1$ and $\gamma (A)$ , respectively. Then ${\eta _{\mathbb {F}_{q^{3}}}(A^2+A+1)=1}$ if and only if $r^{q^3-1}=1$ (i.e., $r\in \mathbb {F}_{q^{3}}$ ) and $\eta _{\mathbb {F}_{q^{3}}}(\gamma (A))=1$ if and only if $s^{q^3-1}=1$ (i.e., $s\in \mathbb {F}_{q^{3}}$ ).

As $\alpha $ and $\alpha ^{-1}$ are the roots of the polynomial $X^2+X+1$ , we have

$$ \begin{align*} r^2 = A^2+A+1 = (A-\alpha^{-1}) \cdot (A-\alpha)= \gamma(A) \cdot (A-\alpha)^2 = s^2\cdot (A-\alpha)^2. \end{align*} $$

Then, since $q^3-1$ is even and $A-\alpha \in \mathbb {F}_{q^{3}}$ , we have

$$ \begin{align*} r^{q^3-1}= (s \cdot (A-\alpha))^{q^3-1}=s^{q^3-1}\cdot(A-\alpha)^{q^3-1}=s^{q^3-1}, \end{align*} $$

and so they equal $1$ at the same time, as required.

Now, to select the element we are looking for, fix a generator g of the cyclic group G and let $A\in \mathcal {H}_1\triangle \mathcal {H}_2$ for which $\gamma (A)=g^2$ . Note that then the previous lemma ensures that $A^2+A+1$ is a square and in particular we have $A\notin \mathbb {F}_q$ . This way we obtained the three different representations discussed before. The only thing we are left with is to show that the six elements $A_1,A_2,\frac {1}{A^q},\frac {1}{A^{q^2}},B,C$ are all different. We already know that $B\neq C$ and, as $A\notin \mathbb {F}_q$ , we also have $\frac {1}{A^q}\neq \frac {1}{A^{q^2}}$ . Now suppose we have $A_1=A_2$ . This would imply that $A_1=A_2\in \mathcal {H}_1\cap \mathcal {H}_2\subseteq \mathbb {F}_q$ , and hence A belongs to $\mathbb {F}_q$ , a contradiction. Next suppose that the mixed and the $\mathcal {H}_{3-i}$ representations would coincide. This would be only possible if $\frac {1}{A^q}$ or $\frac {1}{A^{q^2}}$ would belong to $\mathcal {H}_1\cap \mathcal {H}_2\subseteq \mathbb {F}_q$ which in turn would imply $A\in \mathbb {F}_q$ , again a contradiction. The same argument also shows that the $\mathcal {H}_1$ and $\mathcal {H}_2$ -representations must be different. At last suppose that the mixed and the $\mathcal {H}_i$ representations coincide, say we have $A_1=B$ and $A_2=C$ . Then one of these elements would belong to $\mathcal {H}_1\cap \mathcal {H}_2$ and hence would be a nontrivial third root of unity, and therefore A would be of the form $\alpha Y$ or $\alpha ^{-1}Y$ for some $Y\in \mathcal {H}_1\cup \mathcal {H}_2$ . The contradiction in this case will follow from the lemma below.

Lemma 9. If $q\equiv 1\ \pmod 3$ and $A\in \mathcal {H}_1\triangle \mathcal {H}_2$ then $\alpha A, \alpha ^{-1}A \notin \mathcal {H}_1\cup \mathcal {H}_2$ .

Proof. Assume to the contrary that $c A\in \mathcal {H}_1\cup \mathcal {H}_2$ for $c=\alpha $ or $\alpha ^{-1}$ . As $A\notin \mathbb {F}_q$ we must then also have $cA \notin \mathbb {F}_q$ , so by Lemma 7 both $\gamma (A)$ and $\gamma (cA)$ belong to $G\setminus \mathbb {F}_q^*$ . By definition

$$ \begin{align*} \gamma(\alpha A) &= \frac{\alpha A-\alpha^{-1}}{\alpha A-\alpha} = \frac{A-\alpha^{-2}}{A-1}=\frac{A-\alpha}{A-1}\quad \text{and}\\ \gamma(\alpha^{-1}A) &= \frac{\alpha^{-1}A-\alpha^{-1}}{\alpha^{-1}A-\alpha} = \frac{A-1}{A-\alpha^2}=\frac{A-1}{A-\alpha^{-1}}, \end{align*} $$

which in particular implies that $\gamma (A)\cdot \gamma (\alpha A)\cdot \gamma (\alpha ^{-1}A)=1$ . Since two of the three factors are in G, so must be the third.

By the definition of G, the three elements $\gamma (A)^3$ , $\gamma (\alpha A)^3$ and $\gamma (\alpha ^{-1}A)^3$ all have to be roots of the polynomial $X^{q-1}-1=0$ and hence belong to $\mathbb {F}_q$ . A straightforward but tedious computation shows that A can be expressed as

$$ \begin{align*} A=\frac{\alpha \gamma(A)^3\gamma(\alpha A)^3+\alpha^2\gamma(\alpha A)^3+1}{1-\alpha^{2}\gamma(A)^3\gamma(\alpha A)^3-\alpha \gamma(\alpha A)^3}. \end{align*} $$

Since all the ingredients were shown to be in $\mathbb {F}_q$ , so has to be A, a contradiction.

3.4 Proof of Corollary 1 and 2

We start by proving the key ingredient, Proposition 1, which connects common degrees of vertex sets to solution sets of norm equations.

Proof of Proposition 1

By definition, the common neighborhood of T is the solution set of the system

(3.12) $$ \begin{align} {\mathrm{N}}_{t-1}(V_i + X) = v_ix, \quad i\in [\ell]. \end{align} $$

By dividing the first $\ell -1$ equations with the last one and applying the straightforward change of variable $Y=\frac {1}{X+V_{\ell }}$ we arrive at the norm equation system

(3.13) $$ \begin{align} {\mathrm{N}}_{t-1}(A_i + Y) = a_i, \quad i\in [\ell-1] \end{align} $$

where for $i\in [\ell -1]$ the parameters $A_i=A_i(T)$ and $a_i=a_i(T)$ are as described in the statement. Note that as $ {\mathrm {N}}_{t-1}(X+V_\ell ) = v_\ell \cdot x \neq 0$ , we have $X+V_\ell \neq 0$ and hence this change of variables is admissible. This transformation also shows that if $(X,x)$ is a solution to (3.12), then $\Phi \big ((X,x)\big )=\frac {1}{X+V_\ell }$ is a solution of (3.13). By definition $\Phi \big ((X,x)\big )\neq 0$ and so we get $\Phi (\Gamma (T))\subseteq S_{t-1}\big (A(T)\big )\setminus \{0\}$ .

As $\Gamma (\Gamma (T)) \supseteq T \neq \emptyset $ , the neighborhood $\Gamma (T)$ is generic, so $\Phi $ is injective on $\Gamma (T)$ .

For the surjectivity of $\Phi $ let $Z\in S_{t-1}\big (A(T)\big )\setminus \{0\}$ and consider the vertex $\displaystyle \left (\frac {1}{Z}-V_\ell ,\frac {1}{v_{\ell }\cdot {\mathrm {N}}_{t-1}(Z)}\right )\in \Phi ^{-1}(Z)$ . Next we show that this vertex belongs to $\Gamma (T)$ . Indeed, for $i\in [\ell -1]$ we have

$$ \begin{align*} {\mathrm{N}}_{t-1}\left(V_i + \left(\frac{1}{Z}-V_\ell\right)\right)= {\mathrm{N}}_{t-1}\left(\frac{1}{A_i}+\frac{1}{Z}\right) = {\mathrm{N}}_{t-1}\left(\frac{Z+A_i}{A_iZ}\right) = \frac{a_i}{{\mathrm{N}}_{t-1}(A_i){\mathrm{N}}_{t-1}(Z)}= \frac{1}{v_\ell\cdot {\mathrm{N}}_{t-1}(Z)} \cdot v_i, \end{align*} $$

and for $i=\ell $ we have

$$ \begin{align*} {\mathrm{N}}_{t-1}\left(V_\ell+\left(\frac{1}{Z}-V_\ell\right)\right)= {\mathrm{N}}_{t-1}\left(\frac{1}{Z}\right) = \frac{1}{v_\ell\cdot {\mathrm{N}}_{t-1}(Z)}\cdot v_\ell. \end{align*} $$

To finish the proof just note that $0\in S_{t-1}\big (A(T)\big )$ if and only if $ {\mathrm {N}}_{t-1}(A_i)=a_i=\frac {v_i}{v_{\ell }}\cdot {\mathrm {N}}_{t-1}(A_i)$ for every $i\in [\ell -1]$ , which in turn is equivalent to $v_1=v_2=\cdots =v_{\ell }$ , that is, to $\xi (T)=1$ .

Now Corollary 1 is a direct consequence of Theorem 1 and Proposition 1. To prove Corollary 2 we need a few more details.

First we connect solutions of general norm equation systems with three equations to four adjacencies in the projective norm-graph. As earlier, in what follows, we will simply write $ {\mathrm {N}}$ for the norm function $ {\mathrm {N}}_{3}$ .

Lemma 10. Let $P=\big \{(A_1,a_1), (A_2,a_2), (A_3,a_3)\big \} \subseteq \mathbb {F}_{q^{3}}^*\times \mathbb {F}_q^*$ and $Y\in S_3(P)\setminus \{0\}$ . Then for any $(V,v)\in \mathbb {F}_{q^{3}}\times \mathbb {F}_q^*$ in the projective norm graph $\text {NG}(q,4)$ the vertex $\left (\frac {1}{Y}-V, \frac {1}{v {\mathrm {N}}(Y)} \right )$ is adjacent to all the vertices

$$ \begin{align*} &\left(\frac{1}{A_1}+V, \frac{a_1 v}{{\mathrm{N}}(A_1)}\right),& &\left(\frac{1}{A_2}+V, \frac{a_2 v}{{\mathrm{N}}(A_2)}\right),& &\left(\frac{1}{A_3}+V, \frac{a_3 v}{{\mathrm{N}}(A_3)}\right),& &(V,v). \end{align*} $$

Proof. We check all the adjacencies from the statement. For the first three vertices, using $ {\mathrm {N}}(Y+A_i)=a_i$ , we have

$$ \begin{align*} {\mathrm{N}}\left(\frac{1}{A_i}+V+\frac{1}{Y}-V\right) = {\mathrm{N}}\left(\frac{Y+A_i}{A_iY} \right)= \frac{{\mathrm{N}}(Y+A_i)}{{\mathrm{N}}(A_iY)}=\frac{a_i}{{\mathrm{N}}(A_i){\mathrm{N}}(Y)}=\frac{a_iv}{{\mathrm{N}}(A_i)}\cdot \frac{1}{v\cdot {\mathrm{N}}(Y)}. \end{align*} $$

For the last vertex we have

$$ \begin{align*} {\mathrm{N}}\left(V+\frac{1}{Y} -V\right) = {\mathrm{N}}\left(\frac{1}{Y} \right)=v\cdot \frac{1}{v\cdot {\mathrm{N}}(Y)}, \end{align*} $$

as requested.

By Theorem 2 there exists an element $A\in \mathcal {N}\setminus \{1\}$ such that for the triple $U=\big \{(0,1),(1,-1), (A,-1)\big \} \subseteq \mathbb {F}_{q^{3}}^*\times \mathbb {F}_q^*$ we have $\big |S_3(U)\big |=6$ . If we choose any element $C\in \mathbb {F}_{q^3}\setminus \big (\{0, -1, -A\}\cup S_3(U)\big )$ and $D\in \mathbb {F}_{q^{3}}^*$ , then the transformed system with parameters

$$ \begin{align*} U_{C,D}=\left\{\left(\frac{C}{D},\frac{1}{{\mathrm{N}}(D)}\right),\left(\frac{C+1}{D},-\frac{1}{{\mathrm{N}}(D)}\right),\left(\frac{C+A}{D},-\frac{1}{{\mathrm{N}}(D)}\right)\right\} \end{align*} $$

will still have $6$ solutions. Moreover, by the choice of C we made sure that all three of the first coordinates and all the $6$ solutions are nonzero. Therefore, we can apply Lemma 10 to obtain that for any $(V,v)\in \mathbb {F}_{q^{3}}\times \mathbb {F}_q^*$ the set

$$ \begin{align*} T_{C,D,V,v}=\left\{\left(\frac{D}{C}+V, \frac{v}{{\mathrm{N}}(C)}\right),\left(\frac{D}{C+1}+V, -\frac{v}{{\mathrm{N}}(C+1)}\right),\left(\frac{D}{C+A}+V, -\frac{v}{{\mathrm{N}}(C+A)}\right),(V,v)\right\} \end{align*} $$

of vertices has $6$ common neighbors in $\text {NG}(q,4)$ , namely

$$ \begin{align*} \Gamma(T_{C,D,V,v})=\left\{\left(\frac{1}{Y}-V, \frac{1}{v {\mathrm{N}}(Y)} \right) : Y\in S_3(U_{C,D})\right\}. \end{align*} $$

Note that for any (ordered) quadruple Q of points of $\text {NG}(q,4)$ there is at most one selection of $C,D,V$ and v such that $Q=T_{C,D,V,v}.$ Furthermore, in order for these $24$ adjacencies to indeed give rise to a $K_{4,6}$ in $\text {NG}(q,4)$ , we need to make sure that none of them represents a loop. If q is even, then $\text {NG}(q,4)$ has no loop edges, so all the participating $4+6$ vertices are by default different, and they form a $K_{4,6}$ . Now assume q is odd and assume $C,D,v$ to be fixed. We call an element $V\in \mathbb {F}_{q^{3}}$ bad if for this element some first coordinate in $T_{C,D,V,v}$ coincides with some other first coordinate in $\Gamma (T_{C,D,V,v})$ . Note that if we forbid bad elements for our choice of V then already the first coordinates forbid a loop to appear. However, for every vertex from $T_{C,D,V,v}$ and any other vertex from $T_{C,D,V,v}$ there exists exactly one element V which makes their first coordinates coincide, and therefore, together there are at most $24$ bad elements.