Introduction
Vectorial Boolean functions play an important role in the design of symmetric cryptosystems, serving as the building blocks of block ciphers. To resist differential attacks, a vectorial Boolean function should have low differential uniformity.
Definition 1.1 (Differential uniformity). A function F : F 2 n → F 2 n F \colon\mathbb{F}_2^n \to\mathbb{F}_2^n F : F 2 n → F 2 n has differential uniformity d d d , if
d = max a ∈ F 2 n ∖ { 0 } b ∈ F 2 n ∣ { x : F ( x ) + F ( x + a ) = b } ∣ . d = \max_{\substack{a \in\mathbb{F}_2^n \setminus\{0\}\\ b \in\mathbb{F}_2^n}} \left|\{x \colon F(x) + F(x+a) = b\}\right|. d = a ∈ F 2 n ∖ { 0 } b ∈ F 2 n max ∣ { x : F ( x ) + F ( x + a ) = b } ∣ . A function with differential uniformity 2 is called almost perfect nonlinear (APN).
As the differential uniformity is always even, APN functions F : F 2 n → F 2 n F \colon\mathbb{F}_2^n \to\mathbb{F}_2^n F : F 2 n → F 2 n provide optimal resistance against differential attacks. One of the most important properties of vectorial Boolean functions for use in substitution permutation networks (SPNs) is their linearity, which can be defined via the Walsh transform of the function.
Definition 1.2 (Walsh transform and linearity). Let F : F 2 n → F 2 n F \colon\mathbb{F}_2^n \to\mathbb{F}_2^n F : F 2 n → F 2 n be a function. We define its Walsh transform
W F ( a , b ) = ∑ x ∈ F 2 n ( − 1 ) ⟨ a , F ( x ) ⟩ + ⟨ b , x ⟩ , W_F(a,b) = \sum_{x \in\mathbb{F}_2^n} (-1)^{\langle a,F(x)\rangle+\langle b,x\rangle}, W F ( a , b ) = x ∈ F 2 n ∑ ( − 1 ) ⟨ a , F ( x )⟩ + ⟨ b , x ⟩ , where ⟨ ⋅ , ⋅ ⟩ \langle\cdot,\cdot\rangle ⟨ ⋅ , ⋅ ⟩ is an arbitrary non-degenerate inner product. We call the multiset that collects the values W F ( a , b ) W_F(a,b) W F ( a , b ) for all a ∈ F 2 n ∖ { 0 } a \in\mathbb{F}_2^n \setminus\{0\} a ∈ F 2 n ∖ { 0 } , b ∈ F 2 n b \in\mathbb{F}_2^n b ∈ F 2 n the Walsh spectrum of F F F and the multiset that collects ∣ W F ( a , b ) ∣ |W_F(a,b)| ∣ W F ( a , b ) ∣ for all a ∈ F 2 n ∖ { 0 } a \in\mathbb{F}_2^n \setminus\{0\} a ∈ F 2 n ∖ { 0 } , b ∈ F 2 n b \in\mathbb{F}_2^n b ∈ F 2 n the extended Walsh spectrum of $F. The linearity of F F F is then defined as
L ( F ) = max a ∈ F 2 n ∖ { 0 } b ∈ F 2 n ∣ W F ( a , b ) ∣ . L(F) = \max_{\substack{a \in\mathbb{F}_2^n \setminus\{0\}\\ b \in\mathbb{F}_2^n}} |W_F(a,b)|. L ( F ) = a ∈ F 2 n ∖ { 0 } b ∈ F 2 n max ∣ W F ( a , b ) ∣.
All infinite families of APN functions known so far fall in one of two groups: Either they are quadratic, i.e., of algebraic degree 2. In this case, the theory of quadratic forms immediately implies that the Walsh transform of these functions can only take on 0 or powers of 2. A recent study of the possible Walsh spectra of quadratic APN functions can be found in [1 ] . The second group of APN families consists of APN functions induced by monomials defined over finite fields, i.e., one identifies F 2 n \mathbb{F}_2^n F 2 n with the additive group of the finite field F 2 n \mathbb{F}_{2^n} F 2 n and then considers functions of the form x ↦ x d x \mapsto x^d x ↦ x d . A table of all known infinite families of APN exponents (up to CCZ-equivalence, which does not affect the extended Walsh spectrum) can be found in Table 1 . As we can see in Table 1 , all Walsh spectra of the known APN monomials are known, with the exception of the Dobbertin APN monomials. The main objective of this paper is to fill in this gap. The Dobbertin APN function is a monomial defined on F q 5 \mathbb{F}_{q^5} F q 5 where q = 2 m q=2^m q = 2 m via F q ( x ) = x D q F_q(x)=x^{D_q} F q ( x ) = x D q where D q = q 4 + q 3 + q 2 + q − 1 D_q=q^4+q^3+q^2+q-1 D q = q 4 + q 3 + q 2 + q − 1 .
Table 1. Known APN power families over F 2 n \mathbb{F}_{2^n} F 2 n , n ≥ 3 n\geq3 n ≥ 3 , up to CCZ-equivalence.
Up until this work, the only known result on the Walsh spectrum of the Dobbertin APN function is that all values are divisible by q 2 q^2 q 2 but not all values are divisible by any larger power of 2 2 2 , which was shown in 2000 by Canteaut, Charpin, and Dobbertin [4 ] . Since then, no progress on determining the Walsh spectra of the Dobbertin APN function has been made.
Notation and statement of major results
Fix q = 2 m q=2^m q = 2 m with m ≥ 1 m\geq1 m ≥ 1 , and put K = F q K=\mathbb{F}_q K = F q , L = F q 5 L=\mathbb{F}_{q^5} L = F q 5 , and K r = F q r K_r=\mathbb{F}_{q^r} K r = F q r . For a finite field F F F of characteristic two, write its canonical additive character as
ψ F ( z ) = ( − 1 ) Tr F / F 2 ( z ) . \psi_F(z)=(-1)^{\operatorname{Tr}_{F/\mathbb{F}_2}(z)}. ψ F ( z ) = ( − 1 ) Tr F / F 2 ( z ) .
This paper is concerned with the Walsh transform of the Dobbertin APN function F : L → L F:L\to L F : L → L defined via F ( x ) = x D q F(x)=x^{D_q} F ( x ) = x D q , where D q = q 4 + q 3 + q 2 + q − 1 D_q=q^4+q^3+q^2+q-1 D q = q 4 + q 3 + q 2 + q − 1 . We denote its Walsh transform as
W q ( a , b ) = ∑ x ∈ F q 5 ( − 1 ) Tr F q 5 / F 2 ( a x D q + b x ) . W_q(a,b)=\sum_{x\in\mathbb{F}_{q^5}}(-1)^{\operatorname{Tr}_{\mathbb{F}_{q^5}/\mathbb{F}_2}(ax^{D_q}+bx)}. W q ( a , b ) = x ∈ F q 5 ∑ ( − 1 ) Tr F q 5 / F 2 ( a x D q + b x ) .
Note that a simple substitution shows W q ( a , b ) = W q ( a / ( b D q ) , 1 ) W_q(a,b)=W_q(a/(b^{D_q}),1) W q ( a , b ) = W q ( a / ( b D q ) , 1 ) if b ≠ 0 b\neq0 b = 0 , so it actually suffices to determine W q ( a , 1 ) W_q(a,1) W q ( a , 1 ) and W q ( a , 0 ) W_q(a,0) W q ( a , 0 ) . Moreover, we have gcd ( D q , q 5 − 1 ) = 1 \gcd(D_q,q^5-1)=1 g cd( D q , q 5 − 1 ) = 1 if q = 2 m q=2^m q = 2 m with m m m odd and gcd ( D q , q 5 − 1 ) = 3 \gcd(D_q,q^5-1)=3 g cd( D q , q 5 − 1 ) = 3 if m m m is even (this holds generally for all APN exponents as shown by Dobbertin, see [5 Proposition 165] ), so we get immediately:
Lemma 2.1. Let q = 2 m q=2^m q = 2 m . We have for all a ≠ 0 a\neq0 a = 0 that
W q ( a , 0 ) = { ( − 1 ) m / 2 2 5 m / 2 , m is even , a is a non-cube , ( − 1 ) m / 2 + 1 2 5 m / 2 + 1 , m is even , a is a cube , 0 , m is odd . W_q(a,0)=
\begin{cases}
(-1)^{m/2}2^{5m/2}, & m\text{ is even},\ a\text{ is a non-cube},\\
(-1)^{m/2+1}2^{5m/2+1}, & m\text{ is even},\ a\text{ is a cube},\\
0, & m\text{ is odd}.
\end{cases} W q ( a , 0 ) = ⎩ ⎨ ⎧ ( − 1 ) m /2 2 5 m /2 , ( − 1 ) m /2 + 1 2 5 m /2 + 1 , 0 , m is even , a is a non-cube , m is even , a is a cube , m is odd .
Proof. By the consideration above, we have W q ( a , 0 ) = 0 W_q(a,0)=0 W q ( a , 0 ) = 0 if m m m is odd since x ↦ x q a D x\mapsto x^{q^D_a} x ↦ x q a D permutes L L L . If m m m is even then W q ( a , 0 ) = W F ( a , 0 ) W_q(a,0)=W_F(a,0) W q ( a , 0 ) = W F ( a , 0 ) where F ( x ) = x 3 F(x)=x^3 F ( x ) = x 3 . This cubic sum was determined by Carlitz [6 ] . □
It thus remains to determine W q ( a , 1 ) W_q(a,1) W q ( a , 1 ) for all a ∈ L × a\in L^\times a ∈ L × (note that clearly W q ( 0 , 1 ) = 0 W_q(0,1)=0 W q ( 0 , 1 ) = 0 and W q ( 0 , 0 ) = q 5 W_q(0,0)=q^5 W q ( 0 , 0 ) = q 5 ). We thus, for simplicity, define W q ( a ) : = W q ( a , 1 ) W_q(a):=W_q(a,1) W q ( a ) := W q ( a , 1 ) for the rest of this paper.
We will connect the value of W q ( a , 1 ) W_q(a,1) W q ( a , 1 ) to the number of points of a specific elliptic curve.
For 0 ≤ i < 5 0\le i<5 0 ≤ i < 5 , set a i = a q i a_i=a^{q^i} a i = a q i and read subscripts modulo five. Let e j ( a ) e_j(a) e j ( a ) be the j j j th elementary symmetric polynomial of a 0 , … , a 4 a_0,\ldots,a_4 a 0 , … , a 4 , and put
e 1 ( a ) = Tr L / K ( a ) , e 5 ( a ) = N L / K ( a ) , ω ( a ) = Tr L / K ( a ) 4 + Tr L / K ( a ) 2 e 4 ( a ) + N L / K ( a ) e 3 ( a ) . e_1(a)=\operatorname{Tr}_{L/K}(a),\qquad e_5(a)=\operatorname{N}_{L/K}(a),\qquad\omega(a)=\operatorname{Tr}_{L/K}(a)^4+\operatorname{Tr}_{L/K}(a)^2e_4(a)+\operatorname{N}_{L/K}(a)e_3(a). e 1 ( a ) = Tr L / K ( a ) , e 5 ( a ) = N L / K ( a ) , ω ( a ) = Tr L / K ( a ) 4 + Tr L / K ( a ) 2 e 4 ( a ) + N L / K ( a ) e 3 ( a ) .
These quantities belong to K K K . The single curve used in the proof is the projective cubic defined by
E a : Y 2 + ( Tr L / K ( a ) X + N L / K ( a ) ) Y = X 3 + e 2 ( a ) X 2 + ω ( a ) . (1) \mathcal{E}_a:\quad Y^2+\left(\operatorname{Tr}_{L/K}(a)X+\operatorname{N}_{L/K}(a)\right)Y=X^3+e_2(a)X^2+\omega(a). \tag*{(1)} E a : Y 2 + ( Tr L / K ( a ) X + N L / K ( a ) ) Y = X 3 + e 2 ( a ) X 2 + ω ( a ) . (1)
We will prove that E a \mathcal{E}_a E a defines an elliptic curve when a ∉ { 0 , 1 } a\notin\{0,1\} a ∈ / { 0 , 1 } , see Proposition 6.1 . The main goal is to prove the following theorem:
Theorem 2.2. For a ≠ 1 a\ne1 a = 1 , recall the elliptic curve defined via Eq. (1) . Then for a ∈ L × a\in L^\times a ∈ L × , we have
W q ( a ) = { q 2 ( # E a ( F q ) − q − 1 ) , a ≠ 1 , ( − 1 ) m + 1 q 2 ( q + 1 ) , a = 1. W_q(a)=
\begin{cases}
q^2(\#\mathcal{E}_a(\mathbb{F}_q)-q-1), & a\ne1,\\
(-1)^{m+1}q^2(q+1), & a=1.
\end{cases} W q ( a ) = { q 2 ( # E a ( F q ) − q − 1 ) , ( − 1 ) m + 1 q 2 ( q + 1 ) , a = 1 , a = 1.
The number of rational points of the elliptic curve can be counted using well known techniques to get explicit results. Define the Kloosterman sum over K K K as
Kl K ( k ) = ∑ u ∈ K × ψ K ( u + k / u ) . \operatorname{Kl}_K(k)=\sum_{u\in K^\times}\psi_K(u+k/u). Kl K ( k ) = u ∈ K × ∑ ψ K ( u + k / u ) .
Then we have:
Theorem 2.3. Let q = 2 m q=2^m q = 2 m , K = F q K=\mathbb{F}_q K = F q , and L = F q 5 L=\mathbb{F}_{q^5} L = F q 5 . For a ∈ L ∖ { 0 , 1 } a\in L\setminus\{0,1\} a ∈ L ∖ { 0 , 1 } with Tr L / K ( a ) ≠ 0 \operatorname{Tr}_{L/K}(a)\ne0 Tr L / K ( a ) = 0 , put
d ( a ) = e 2 ( a ) Tr L / K ( a ) 2 + N L / K ( a ) Tr L / K ( a ) 3 , k ( a ) = N L / K ( Tr L / K ( a ) 2 + N L / K ( a ) / a ) Tr L / K ( a ) 12 . d(a)=\frac{e_2(a)}{\operatorname{Tr}_{L/K}(a)^2}+\frac{\operatorname{N}_{L/K}(a)}{\operatorname{Tr}_{L/K}(a)^3},\qquad
k(a)=\frac{\operatorname{N}_{L/K}\left(\operatorname{Tr}_{L/K}(a)^2+\operatorname{N}_{L/K}(a)/a\right)}{\operatorname{Tr}_{L/K}(a)^{12}}. d ( a ) = Tr L / K ( a ) 2 e 2 ( a ) + Tr L / K ( a ) 3 N L / K ( a ) , k ( a ) = Tr L / K ( a ) 12 N L / K ( Tr L / K ( a ) 2 + N L / K ( a ) / a ) . Then k ( a ) ≠ 0 k(a)\ne0 k ( a ) = 0 , and for every a ∈ L a\in L a ∈ L ,
W q ( a ) = { 0 , a = 0 , ( − 1 ) m + 1 q 2 ( q + 1 ) , a = 1 , q 2 ∑ u ∈ K ψ K ( u 3 + e 2 ( a ) u + e 3 ( a ) N L / K ( a ) ) , a ≠ 0 , Tr L / K ( a ) = 0 , q 2 ψ K ( d ( a ) ) Kl K ( k ( a ) ) , a ≠ 1 , Tr L / K ( a ) ≠ 0. W_q(a)=
\begin{cases}
0, & a=0,\\
(-1)^{m+1}q^2(q+1), & a=1,\\
q^2\sum_{u\in K}\psi_K\left(\frac{u^3+e_2(a)u+e_3(a)}{\operatorname{N}_{L/K}(a)}\right), & a\ne0,\ \operatorname{Tr}_{L/K}(a)=0,\\
q^2\psi_K(d(a))\operatorname{Kl}_K(k(a)), & a\ne1,\ \operatorname{Tr}_{L/K}(a)\ne0.
\end{cases} W q ( a ) = ⎩ ⎨ ⎧ 0 , ( − 1 ) m + 1 q 2 ( q + 1 ) , q 2 ∑ u ∈ K ψ K ( N L / K ( a ) u 3 + e 2 ( a ) u + e 3 ( a ) ) , q 2 ψ K ( d ( a )) Kl K ( k ( a )) , a = 0 , a = 1 , a = 0 , Tr L / K ( a ) = 0 , a = 1 , Tr L / K ( a ) = 0. In particular, for a ∈ K ∖ { 0 , 1 } a\in K\setminus\{0,1\} a ∈ K ∖ { 0 , 1 } ,
W q ( a ) = q 2 ψ K ( a ) Kl K ( ( a + 1 ) 5 a ) . W_q(a)=q^2\psi_K(a)\operatorname{Kl}_K\left(\frac{(a+1)^5}{a}\right). W q ( a ) = q 2 ψ K ( a ) Kl K ( a ( a + 1 ) 5 ) .
Note that the cubic sum in the case where Tr L / K ( a ) = 0 \operatorname{Tr}_{L/K}(a)=0 Tr L / K ( a ) = 0 is evaluated explicitly in Proposition 8.3, and the Walsh transform is in this case always 0 , ± q 2 2 ( m + 1 ) / 2 0,\pm q^2 2^{(m+1)/2} 0 , ± q 2 2 ( m + 1 ) /2 if m m m is odd, or 0 , ± q 2 m / 2 , ± q 2 ( m + 2 ) / 2 0,\pm q 2^{m/2},\pm q 2^{(m+2)/2} 0 , ± q 2 m /2 , ± q 2 ( m + 2 ) /2 if m m m is even. In particular, using the well known characterization of the spectrum of Kloosterman sums, we can determine the extended Walsh spectrum of the Dobbertin APN function precisely:
Theorem 2.4. Put
U m = { { 0 , 2 ( m + 1 ) / 2 } , m odd , { 0 , 2 m / 2 , 2 m / 2 + 1 } , m even . U_m =
\begin{cases}
\{0,2^{(m+1)/2}\}, & m\ \text{odd},\\
\{0,2^{m/2},2^{m/2+1}\}, & m\ \text{even}.
\end{cases} U m = { { 0 , 2 ( m + 1 ) /2 } , { 0 , 2 m /2 , 2 m /2 + 1 } , m odd , m even . The values occurring in the extended Walsh spectrum of the Dobbertin APN function defined on L L L are exactly
{ q 2 ( q + 1 ) } ∪ q 2 U m ∪ { q 2 j : j ∈ N odd , ∣ j ∣ ≤ 2 q } . \{q^2(q+1)\}\cup q^2U_m\cup\{q^2j:j\in\mathbb{N}\ \text{odd},\ |j|\le2\sqrt{q}\}. { q 2 ( q + 1 )} ∪ q 2 U m ∪ { q 2 j : j ∈ N odd , ∣ j ∣ ≤ 2 q } . In particular, L ( F ) = q 2 ( q + 1 ) L(F)=q^2(q+1) L ( F ) = q 2 ( q + 1 ) .
A reformulation of the sum and further preparation
The following simple but key lemma transform the character sum attached to the Dobbertin APN function to a cubic sum.
Lemma 3.1. For every a ∈ L a\in L a ∈ L ,
W q ( a ) = ∑ y ∈ L ψ L ( a y q 2 + q + 1 + y q + 1 ) . W_q(a)=\sum_{y\in L}\psi_L(ay^{q^2+q+1}+y^{q+1}). W q ( a ) = y ∈ L ∑ ψ L ( a y q 2 + q + 1 + y q + 1 ) .
Proof. A simple calculation (see [2 Lemma 9] ) shows that ( q + 1 ) D q = ( q + 1 ) ( q 4 + q 3 + q 2 + q − 1 ) ≡ 2 q 2 ( q 2 + q + 1 ) ( m o d q 5 − 1 ) (q+1)D_q=(q+1)(q^4+q^3+q^2+q-1)\equiv2q^2(q^2+q+1)\pmod{q^5-1} ( q + 1 ) D q = ( q + 1 ) ( q 4 + q 3 + q 2 + q − 1 ) ≡ 2 q 2 ( q 2 + q + 1 ) ( mod q 5 − 1 ) , so
W q ( a ) = ∑ y ∈ L ψ L ( a y q 4 + q 3 + q 2 + q − 1 + y ) = ∑ z ∈ L ψ L ( a z 2 q 2 ( q 2 + q + 1 ) + z q + 1 ) = ∑ z ∈ L ψ L ( a z q 2 + q + 1 + z q + 1 ) , \begin{aligned}
W_q(a)=\sum_{y\in L}\psi_L(ay^{q^4+q^3+q^2+q-1}+y) \\
&=\sum_{z\in L}\psi_L(az^{2q^2(q^2+q+1)}+z^{q+1}) \\
&=\sum_{z\in L}\psi_L(az^{q^2+q+1}+z^{q+1}),
\end{aligned} W q ( a ) = y ∈ L ∑ ψ L ( a y q 4 + q 3 + q 2 + q − 1 + y ) = z ∈ L ∑ ψ L ( a z 2 q 2 ( q 2 + q + 1 ) + z q + 1 ) = z ∈ L ∑ ψ L ( a z q 2 + q + 1 + z q + 1 ) ,
using the substitution y = z q + 1 y=z^{q+1} y = z q + 1 and the fact that W q ( a ) = W q ( a 2 i ) W_q(a)=W_q(a^{2^i}) W q ( a ) = W q ( a 2 i ) for any i i i . □
We also need a simple lemma.
Lemma 3.2. Let a ∈ L a\in L a ∈ L , a ∉ { 0 , 1 } a\notin\{0,1\} a ∈ / { 0 , 1 } then Tr L / K ( a ) 2 ≠ N L / K ( a ) / a i \operatorname{Tr}_{L/K}(a)^2\ne\operatorname{N}_{L/K}(a)/a_i Tr L / K ( a ) 2 = N L / K ( a ) / a i for 0 ≤ i < 5 0\le i<5 0 ≤ i < 5 .
Proof. Assume Tr L / K ( a ) 2 = N L / K ( a ) / a i \operatorname{Tr}_{L/K}(a)^2=\operatorname{N}_{L/K}(a)/a_i Tr L / K ( a ) 2 = N L / K ( a ) / a i . Since Tr L / K ( a ) 2 ∈ K \operatorname{Tr}_{L/K}(a)^2\in K Tr L / K ( a ) 2 ∈ K and N L / K ( a ) ∈ K \operatorname{N}_{L/K}(a)\in K N L / K ( a ) ∈ K , this implies a ∈ K a\in K a ∈ K , and a i = a a_i=a a i = a for all i i i . Then, in particular, Tr L / K ( a ) = a \operatorname{Tr}_{L/K}(a)=a Tr L / K ( a ) = a and N L / K ( a ) = a 5 \operatorname{N}_{L/K}(a)=a^5 N L / K ( a ) = a 5 , so N L / K ( a ) / a i = a 4 \operatorname{N}_{L/K}(a)/a_i=a^4 N L / K ( a ) / a i = a 4 and Tr L / K ( a ) 2 = a 2 \operatorname{Tr}_{L/K}(a)^2=a^2 Tr L / K ( a ) 2 = a 2 , implying a 2 = a 4 a^2=a^4 a 2 = a 4 , which only holds if a ∈ { 0 , 1 } a\in\{0,1\} a ∈ { 0 , 1 } , contradicting our assumption. □
A lemma for the Dobbertin sum over degree 2 extension fields
The goal of this section is to relate W q ( a ) W_q(a) W q ( a ) with W q 2 ( a ) W_{q^2}(a) W q 2 ( a ) , for any a ∈ F q 5 × a\in\mathbb{F}_{q^5}^{\times} a ∈ F q 5 × .
Lemma 4.1. For a ∈ F q 5 × a\in\mathbb{F}_{q^5}^{\times} a ∈ F q 5 × ,
W q ( a ) 2 + W q 2 ( a ) = 2 q 5 . W_q(a)^2+W_{q^2}(a)=2q^5. W q ( a ) 2 + W q 2 ( a ) = 2 q 5 .
Proof. Let τ ( x ) = x q 5 \tau(x)=x^{q^5} τ ( x ) = x q 5 ; then τ 2 = id \tau^2=\operatorname{id} τ 2 = id on F q 10 \mathbb{F}_{q^{10}} F q 10 and τ \tau τ fixes exactly F q 5 \mathbb{F}_{q^5} F q 5 . Set f ( x ) = x D q 2 f(x)=x^{D_{q^2}} f ( x ) = x D q 2 on F q 10 \mathbb{F}_{q^{10}} F q 10 . Then f ( x ) = x D q f(x)=x^{D_q} f ( x ) = x D q when x ∈ F q 5 × x\in\mathbb{F}_{q^5}^{\times} x ∈ F q 5 × . Indeed, if x ∈ F q 5 × x\in\mathbb{F}_{q^5}^{\times} x ∈ F q 5 × , the five powers x q 2 i x^{q^{2i}} x q 2 i (0 ≤ i < 5 0\le i<5 0 ≤ i < 5 ) permute x , x q , … , x q 4 x,x^q,\ldots,x^{q^4} x , x q , … , x q 4 .
Now consider (unordered) pairs { x , x ′ } \{x,x'\} { x , x ′ } of distinct elements of F q 10 \mathbb{F}_{q^{10}} F q 10 which are fixed as sets by τ \tau τ , we call this set T T T . If x , x ′ ∈ F q 5 x,x'\in\mathbb{F}_{q^5} x , x ′ ∈ F q 5 , then they are clearly fixed by τ \tau τ element-wise, so we get q 5 ( q 5 − 1 ) / 2 q^5(q^5-1)/2 q 5 ( q 5 − 1 ) /2 pairs of that shape. Let us call the set of these pairs T 1 ⊆ T T_1\subseteq T T 1 ⊆ T . All other pairs necessarily satisfy x ′ = x τ x'=x^\tau x ′ = x τ , so we get ( q 10 − q 5 ) / 2 (q^{10}-q^5)/2 ( q 10 − q 5 ) /2 additional pairs { x , x ′ } \{x,x'\} { x , x ′ } outside F q 5 \mathbb{F}_{q^5} F q 5 , we call the set of these pairs T 2 ⊆ T T_2 \subseteq T T 2 ⊆ T . Thus there are q 5 ( q 5 − 1 ) / 2 + ( q 10 − q 5 ) / 2 = q 10 − q 5 q^5(q^5-1)/2+(q^{10}-q^5)/2=q^{10}-q^5 q 5 ( q 5 − 1 ) /2 + ( q 10 − q 5 ) /2 = q 10 − q 5 such pairs in total. The map
h : { x , x ′ } ⟼ ( x + x ′ , f ( x ) + f ( x ′ ) ) h:\{x,x'\}\longmapsto(x+x',f(x)+f(x')) h : { x , x ′ } ⟼ ( x + x ′ , f ( x ) + f ( x ′ ))
maps T T T into F q 5 × F q 5 \mathbb{F}_{q^5}\times\mathbb{F}_{q^5} F q 5 × F q 5 since τ \tau τ fixes both coordinates. We show that h h h is injective: if h ( { x , x ′ } ) = ( s , t ) h(\{x,x'\})=(s,t) h ({ x , x ′ }) = ( s , t ) , then f ( x + s ) + f ( x ) = t f(x+s)+f(x)=t f ( x + s ) + f ( x ) = t and f ( x ′ + s ) + f ( x ′ ) = t f(x'+s)+f(x')=t f ( x ′ + s ) + f ( x ′ ) = t , and the APN property of the Dobbertin function does not allow additional solutions. Since T T T and F q 5 × × F q 5 \mathbb{F}_{q^5}^{\times}\times\mathbb{F}_{q^5} F q 5 × × F q 5 have the same cardinality, this map is thus a bijection. We have
W q ( a ) 2 = ∑ x , x ′ ∈ F q 5 ψ F q 5 ( a ( f ( x ) + f ( x ′ ) ) + x + x ′ ) = q 5 + 2 ∑ { x , x ′ } ∈ T 1 ψ F q 5 ( a ( f ( x ) + f ( x ′ ) ) + x + x ′ ) , \begin{aligned}
W_q(a)^2=\sum_{x,x'\in\mathbb{F}_{q^5}}\psi_{\mathbb{F}_{q^5}}\left(a(f(x)+f(x'))+x+x'\right) \\
&=q^5+2\sum_{\{x,x'\}\in T_1}\psi_{\mathbb{F}_{q^5}}\left(a(f(x)+f(x'))+x+x'\right),
\end{aligned} W q ( a ) 2 = x , x ′ ∈ F q 5 ∑ ψ F q 5 ( a ( f ( x ) + f ( x ′ )) + x + x ′ ) = q 5 + 2 { x , x ′ } ∈ T 1 ∑ ψ F q 5 ( a ( f ( x ) + f ( x ′ )) + x + x ′ ) ,
where the q 5 q^5 q 5 term comes from the case x = x ′ x=x' x = x ′ . We also get
W q 2 ( a ) = ∑ x ∈ F q 5 ψ F q 10 ( a f ( x ) + x ) + ∑ x ∈ F q 10 ∖ F q 5 ψ F q 10 ( a f ( x ) + x ) = q 5 + ∑ x ∈ F q 10 ∖ F q 5 ψ F q 5 ( a f ( x ) + x + a ( f ( x ) ) τ + x τ ) = q 5 + 2 ∑ { x , x ′ } ∈ T 2 ψ F q 5 ( a ( f ( x ) + f ( x ′ ) ) + x + x ′ ) , \begin{aligned}
W_{q^2}(a)=\sum_{x\in\mathbb{F}_{q^5}}\psi_{\mathbb{F}_{q^{10}}}(af(x)+x)+\sum_{x\in\mathbb{F}_{q^{10}}\setminus\mathbb{F}_{q^5}}\psi_{\mathbb{F}_{q^{10}}}(af(x)+x) \\
&=q^5+\sum_{x\in\mathbb{F}_{q^{10}}\setminus\mathbb{F}_{q^5}}\psi_{\mathbb{F}_{q^5}}\left(af(x)+x+a(f(x))^\tau+x^\tau\right) \\
&=q^5+2\sum_{\{x,x'\}\in T_2}\psi_{\mathbb{F}_{q^5}}\left(a(f(x)+f(x'))+x+x'\right),
\end{aligned} W q 2 ( a ) = x ∈ F q 5 ∑ ψ F q 10 ( a f ( x ) + x ) + x ∈ F q 10 ∖ F q 5 ∑ ψ F q 10 ( a f ( x ) + x ) = q 5 + x ∈ F q 10 ∖ F q 5 ∑ ψ F q 5 ( a f ( x ) + x + a ( f ( x ) ) τ + x τ ) = q 5 + 2 { x , x ′ } ∈ T 2 ∑ ψ F q 5 ( a ( f ( x ) + f ( x ′ )) + x + x ′ ) ,
where we use in the first step that a f ( x ) + x ∈ F q 5 af(x)+x\in\mathbb{F}_{q^5} a f ( x ) + x ∈ F q 5 if x ∈ F q 5 x\in\mathbb{F}_{q^5} x ∈ F q 5 , so ψ F q 10 ( a f ( x ) + x ) = 1 \psi_{\mathbb{F}_{q^{10}}}(af(x)+x)=1 ψ F q 10 ( a f ( x ) + x ) = 1 as well as the transitivity of the trace. Hence
W q ( a ) 2 + W q 2 ( a ) = 2 q 5 + 2 ∑ { x , x ′ } ∈ T ψ F q 5 ( a ( f ( x ) + f ( x ′ ) ) + x + x ′ ) . W_q(a)^2+W_{q^2}(a)=2q^5+2\sum_{\{x,x'\}\in T}\psi_{\mathbb{F}_{q^5}}\left(a(f(x)+f(x'))+x+x'\right). W q ( a ) 2 + W q 2 ( a ) = 2 q 5 + 2 { x , x ′ } ∈ T ∑ ψ F q 5 ( a ( f ( x ) + f ( x ′ )) + x + x ′ ) .
Now we use the bijectivity of the map h h h , so we can replace T T T by F q 5 × × F q 5 \mathbb{F}_{q^5}^{\times}\times\mathbb{F}_{q^5} F q 5 × × F q 5 . We get
W q ( a ) 2 + W q 2 ( a ) = 2 q 5 + 2 ∑ s ∈ F q 5 × t ∈ F q 5 ψ F q 5 ( a t + s ) = 2 q 5 + 2 ∑ s ∈ F q 5 × ψ F q 5 ( s ) ∑ t ∈ F q 5 ψ F q 5 ( a t ) = 2 q 5 , \begin{aligned}
W_q(a)^2+W_{q^2}(a)=2q^5+2\sum_{\substack{s\in\mathbb{F}_{q^5}^{\times}\\t\in\mathbb{F}_{q^5}}}\psi_{\mathbb{F}_{q^5}}(at+s) \\
&=2q^5+2\sum_{s\in\mathbb{F}_{q^5}^{\times}}\psi_{\mathbb{F}_{q^5}}(s)\sum_{t\in\mathbb{F}_{q^5}}\psi_{\mathbb{F}_{q^5}}(at) \\
&=2q^5,
\end{aligned} W q ( a ) 2 + W q 2 ( a ) = 2 q 5 + 2 s ∈ F q 5 × t ∈ F q 5 ∑ ψ F q 5 ( a t + s ) = 2 q 5 + 2 s ∈ F q 5 × ∑ ψ F q 5 ( s ) t ∈ F q 5 ∑ ψ F q 5 ( a t ) = 2 q 5 ,
using orthogonality of characters (recall a ≠ 0 a\ne0 a = 0 ).
Relating the Dobbertin sum to another sum
With Lemma 4.1 in mind, we try to analyze the sequence W q r ( a ) W_{q^r}(a) W q r ( a ) for r ≥ 1 r\ge1 r ≥ 1 . The idea of this approach is to leverage information from extension fields of F q \mathbb{F}_q F q to determine the actual Walsh transform W q ( a ) W_q(a) W q ( a ) (i.e., the case r = 1 r=1 r = 1 in the sequence). This is a natural tool since our aim is to connect the exponential sum to a point counting problem for an elliptic curve, whose rational points over extension fields of F q \mathbb{F}_q F q can be studied uniformly for all possible extension fields through its zeta function.
The goal of this section is thus to connect the Walsh transform of the Dobbertin function W q r ( a ) W_{q^r}(a) W q r ( a ) over arbitrary extension fields F q 5 r \mathbb{F}_{q^{5r}} F q 5 r where a ∈ L = F q 5 a\in L=\mathbb{F}_{q^5} a ∈ L = F q 5 to an exponential sum of a specific polynomial over F q r \mathbb{F}_{q^r} F q r . Fix a ∈ L × a\in L^\times a ∈ L × and choose b ∈ L ∖ K b\in L\setminus K b ∈ L ∖ K arbitrarily. Define linear forms in five variables by
Y j ( X 0 , … , X 4 ) = ∑ i = 0 4 X i b i q j , for 0 ≤ j < 5. Y_j(X_0,\ldots,X_4)=\sum_{i=0}^{4}X_i b^{iq^j},\quad\text{for }0\le j<5. Y j ( X 0 , … , X 4 ) = i = 0 ∑ 4 X i b i q j , for 0 ≤ j < 5.
Since [ L : K ] = 5 [L:K]=5 [ L : K ] = 5 is prime, b b b necessarily has degree five over K K K . Now define
P a ( X 0 , … , X 4 ) = ∑ j = 0 4 a j Y j Y j + 1 Y j + 2 + ∑ j = 0 4 Y j Y j + 1 . (2) P_a(X_0,\ldots,X_4)=\sum_{j=0}^{4}a_jY_jY_{j+1}Y_{j+2}+\sum_{j=0}^{4}Y_jY_{j+1}. \tag*{(2)} P a ( X 0 , … , X 4 ) = j = 0 ∑ 4 a j Y j Y j + 1 Y j + 2 + j = 0 ∑ 4 Y j Y j + 1 . (2)
Recall that a j = a q j a_j=a^{q^j} a j = a q j . The map x ↦ x q x\mapsto x^q x ↦ x q on the coefficients sends a j a_j a j to a j + 1 a_{j+1} a j + 1 and Y j Y_j Y j to Y j + 1 Y_{j+1} Y j + 1 , with indices taken modulo 5. It cyclically permutes both sums, so every coefficient of P a P_a P a is fixed by x ↦ x q x\mapsto x^q x ↦ x q , implying that P a ∈ K [ X ] P_a\in K[X] P a ∈ K [ X ] . We now consider exponential sums using this (fixed) polynomial over arbitrary extension fields of K K K . So, for r ≥ 1 r\ge1 r ≥ 1 , put K r = F q r K_r=\mathbb{F}_{q^r} K r = F q r and set
S r ( a ) = ∑ X ∈ K r 5 ψ K r ( P a ( X ) ) . (3) S_r(a)=\sum_{X\in K_r^5}\psi_{K_r}(P_a(X)). \tag*{(3)} S r ( a ) = X ∈ K r 5 ∑ ψ K r ( P a ( X )) . (3)
Let us now consider S r ( a ) S_r(a) S r ( a ) . It turns out that the behavior depends on if 5 divides r r r or not (or, equivalently, if K r K_r K r contains L L L or not).
Proposition 5.1. Let S r ( a ) S_r(a) S r ( a ) be as in Eq. (3) . Then
S r ( a ) = { ∑ z 0 , … , z 4 ∈ K r ψ K r ( ∑ i = 0 4 a i z i z i + 1 z i + 2 + ∑ i = 0 4 z i z i + 1 ) , 5 ∣ r , W q r ( a ) , 5 ∤ r . S_r(a)=
\begin{cases}
\sum_{z_0,\ldots,z_4\in K_r}\psi_{K_r}\left(\sum_{i=0}^{4}a_i z_i z_{i+1}z_{i+2}+\sum_{i=0}^{4}z_i z_{i+1}\right),&5\mid r,\\
W_{q^r}(a),&5\nmid r.
\end{cases} S r ( a ) = { ∑ z 0 , … , z 4 ∈ K r ψ K r ( ∑ i = 0 4 a i z i z i + 1 z i + 2 + ∑ i = 0 4 z i z i + 1 ) , W q r ( a ) , 5 ∣ r , 5 ∤ r .
Proof. Let us consider first the case that 5 ∣ r 5\mid r 5 ∣ r . Then b ∈ K r b\in K_r b ∈ K r . The coefficient matrix of the forms Y j Y_j Y j is thus exactly the Vandermonde matrix ( b i q j ) j , i (b^{iq^j})_{j,i} ( b i q j ) j , i , which has nonzero determinant. The change of variables ( X 0 , … , X 4 ) ↦ ( Y 0 , … , Y 4 ) (X_0,\ldots,X_4)\mapsto(Y_0,\ldots,Y_4) ( X 0 , … , X 4 ) ↦ ( Y 0 , … , Y 4 ) is thus invertible and we have
S r ( a ) = ∑ X ∈ K r 5 ψ K r ( P a ( X ) ) = ∑ z 0 , … , z 4 ∈ K r ψ K r ( ∑ i = 0 4 a i z i z i + 1 z i + 2 + ∑ i = 0 4 z i z i + 1 ) . S_r(a)=\sum_{X\in K_r^5}\psi_{K_r}(P_a(X))=\sum_{z_0,\ldots,z_4\in K_r}\psi_{K_r}\left(\sum_{i=0}^{4}a_i z_i z_{i+1}z_{i+2}+\sum_{i=0}^{4}z_i z_{i+1}\right). S r ( a ) = X ∈ K r 5 ∑ ψ K r ( P a ( X )) = z 0 , … , z 4 ∈ K r ∑ ψ K r ( i = 0 ∑ 4 a i z i z i + 1 z i + 2 + i = 0 ∑ 4 z i z i + 1 ) .
If 5 ∤ r 5\nmid r 5 ∤ r , then { 1 , b , … , b 4 } \{1,b,\ldots,b^4\} { 1 , b , … , b 4 } is a basis of F q 5 r \mathbb{F}_{q^{5r}} F q 5 r over K r K_r K r , so the map ( X 0 , … , X 4 ) ↦ Y 0 ( X 0 , … , X 4 ) (X_0,\ldots,X_4)\mapsto Y_0(X_0,\ldots,X_4) ( X 0 , … , X 4 ) ↦ Y 0 ( X 0 , … , X 4 ) is a bijection between K r 5 K_r^5 K r 5 and F q 5 r \mathbb{F}_{q^{5r}} F q 5 r . Define y = Y 0 ( X 0 , … , X 4 ) ∈ F q 5 r y=Y_0(X_0,\ldots,X_4)\in\mathbb{F}_{q^{5r}} y = Y 0 ( X 0 , … , X 4 ) ∈ F q 5 r . Choose ℓ ∈ { 1 , 2 , 3 , 4 } \ell\in\{1,2,3,4\} ℓ ∈ { 1 , 2 , 3 , 4 } such that ℓ r ≡ 1 ( m o d 5 ) \ell r\equiv1\pmod5 ℓ r ≡ 1 ( mod 5 ) and set ρ ( y ) = y q ℓ r \rho(y)=y^{q^{\ell r}} ρ ( y ) = y q ℓ r . The first five powers of ρ \rho ρ permute the five Frobenius maps z ↦ z q j r z\mapsto z^{q^{jr}} z ↦ z q j r (0 ≤ j < 5 0\le j<5 0 ≤ j < 5 ), and ρ \rho ρ maps b b b to b q b^q b q and a a a to a q a^q a q . Since ρ \rho ρ fixes every X i ∈ K r X_i\in K_r X i ∈ K r , we necessarily have Y j ( X 0 , … , X 4 ) = ρ j ( y ) Y_j(X_0,\ldots,X_4)=\rho^j(y) Y j ( X 0 , … , X 4 ) = ρ j ( y ) and a j = ρ j ( a ) a_j=\rho^j(a) a j = ρ j ( a ) . Hence
P a ( X 0 , … , X 4 ) = Tr F q 5 r / K r ( a y ρ ( y ) ρ 2 ( y ) + y ρ ( y ) ) . P_a(X_0,\ldots,X_4)=\operatorname{Tr}_{\mathbb{F}_{q^{5r}}/K_r}\left(ay\rho(y)\rho^2(y)+y\rho(y)\right). P a ( X 0 , … , X 4 ) = Tr F q 5 r / K r ( a y ρ ( y ) ρ 2 ( y ) + y ρ ( y ) ) .
Put Q = q r Q=q^r Q = q r and M = F Q 5 M=\mathbb{F}_{Q^5} M = F Q 5 . By [2 Lemma 9] , gcd ( 1 + Q ℓ , Q 5 − 1 ) = 1 \gcd(1+Q^\ell,Q^5-1)=1 g cd( 1 + Q ℓ , Q 5 − 1 ) = 1 , and
D Q ( 1 + Q ℓ ) ≡ 2 Q 2 ℓ ( 1 + Q ℓ + Q 2 ℓ ) ( m o d Q 5 − 1 ) . D_Q(1+Q^\ell)\equiv2Q^{2\ell}(1+Q^\ell+Q^{2\ell})\pmod{Q^5-1}. D Q ( 1 + Q ℓ ) ≡ 2 Q 2 ℓ ( 1 + Q ℓ + Q 2 ℓ ) ( mod Q 5 − 1 ) .
Thus x = y 1 + Q ℓ = y ρ ( y ) x=y^{1+Q^\ell}=y\rho(y) x = y 1 + Q ℓ = y ρ ( y ) permutes M M M . Then
S r ( a ) = ∑ x ∈ M ψ M ( a 2 Q 2 ℓ x D Q + x ) = W Q ( a 2 Q 2 ℓ ) = W Q ( a ) = W q r ( a ) , S_r(a)=\sum_{x\in M}\psi_M\left(a^{2Q^{2\ell}}x^{D_Q}+x\right)=W_Q(a^{2Q^{2\ell}})=W_Q(a)=W_{q^r}(a), S r ( a ) = x ∈ M ∑ ψ M ( a 2 Q 2 ℓ x D Q + x ) = W Q ( a 2 Q 2 ℓ ) = W Q ( a ) = W q r ( a ) ,
where we use that W Q ( c 2 j ) = W Q ( c ) W_Q(c^{2^j})=W_Q(c) W Q ( c 2 j ) = W Q ( c ) .
This means that S r ( a ) S_r(a) S r ( a ) equals the Dobbertin exponential sum over the extension field if 5 ∤ r 5\nmid r 5 ∤ r , and it becomes a much simpler sum in the case 5 ∣ r 5\mid r 5 ∣ r . In particular, S 1 ( a ) S_1(a) S 1 ( a ) is exactly the exponential sum corresponding to the Dobbertin APN function. We will try to determine S 1 ( a ) S_1(a) S 1 ( a ) by considering the sequence of S r ( a ) S_r(a) S r ( a ) , by using the fact that we can calculate S r ( a ) S_r(a) S r ( a ) in an elementary way using Proposition 5.1 if 5 ∣ r 5\mid r 5 ∣ r . Then we will investigate the sequence of S r ( a ) S_r(a) S r ( a ) , and through this determine S 1 ( a ) S_1(a) S 1 ( a ) and thus the Walsh transform of the Dobbertin function.
The calculation if 5 ∣ r 5 \mid r 5 ∣ r
We now calculate S r ( a ) S_r(a) S r ( a ) in the case that 5 ∣ r 5 \mid r 5 ∣ r . Recall that K r = F q r K_r = \mathbb{F}_{q^r} K r = F q r .
Proposition 5.2. Let 5 ∣ r 5 \mid r 5 ∣ r , and put Q = q r Q=q^r Q = q r . For a ∈ L × a \in L^\times a ∈ L × , let S r ( a ) S_r(a) S r ( a ) be defined by Eq. (3) . If a ∉ { 0 , 1 } a \notin\{0,1\} a ∈ / { 0 , 1 } , then
S r ( a ) = Q 2 ( # E a ( K r ) − Q − 1 − 5 ψ K r ( ( a 1 a 4 ) − 1 ) ) . S_r(a)=Q^2\left(\#\mathcal{E}_a(K_r)-Q-1-5\psi_{K_r}\left((a_1a_4)^{-1}\right)\right). S r ( a ) = Q 2 ( # E a ( K r ) − Q − 1 − 5 ψ K r ( ( a 1 a 4 ) − 1 ) ) .
where E a \mathcal{E}_a E a is the projective curve defined by (1) .
If a = 1 a=1 a = 1 , then
S r ( a ) = ( − 1 ) m r Q 2 ( 4 Q − 6 ) . S_r(a)=(-1)^{mr}Q^2(4Q-6). S r ( a ) = ( − 1 ) m r Q 2 ( 4 Q − 6 ) .
The rest of this subsection is dedicated to proving the proposition. By Proposition 5.1 , we need to calculate the sum
S r ( a ) = ∑ z 0 , … , z 4 ∈ K r ψ K r ( ∑ i = 0 4 a i z i z i + 1 z i + 2 + ∑ i = 0 4 z i z i + 1 ) . (4) S_r(a)=\sum_{z_0,\ldots,z_4\in K_r}\psi_{K_r}\left(\sum_{i=0}^{4}a_i z_i z_{i+1}z_{i+2}+\sum_{i=0}^{4}z_i z_{i+1}\right). \tag*{(4)} S r ( a ) = z 0 , … , z 4 ∈ K r ∑ ψ K r ( i = 0 ∑ 4 a i z i z i + 1 z i + 2 + i = 0 ∑ 4 z i z i + 1 ) . (4)
where a ∈ L × a\in L^\times a ∈ L × and subscripts are read modulo five. Recall that a i = a q i a_i=a^{q^i} a i = a q i and retain the notation
Tr L / K ( a ) = ∑ i = 0 4 a i , N L / K ( a ) = ∏ i = 0 4 a i . \operatorname{Tr}_{L/K}(a)=\sum_{i=0}^{4}a_i,\qquad N_{L/K}(a)=\prod_{i=0}^{4}a_i. Tr L / K ( a ) = i = 0 ∑ 4 a i , N L / K ( a ) = i = 0 ∏ 4 a i .
Since ψ K r ( u 2 ) = ψ K r ( u ) \psi_{K_r}(u^2)=\psi_{K_r}(u) ψ K r ( u 2 ) = ψ K r ( u ) , squaring the argument in Eq. (4) leaves its character unchanged. The substitution z i ↦ z i 2 z_i\mapsto z_i^2 z i ↦ z i 2 is a bijection of K r 5 K_r^5 K r 5 . Consequently,
S r ( a ) = ∑ z 0 , … , z 4 ∈ K r ψ K r ( ∑ i = 0 4 a i 2 z i z i + 1 z i + 2 + ∑ i = 0 4 z i z i + 1 ) . S_r(a)=\sum_{z_0,\ldots,z_4\in K_r}\psi_{K_r}\left(\sum_{i=0}^{4}a_i^2z_i z_{i+1}z_{i+2}+\sum_{i=0}^{4}z_i z_{i+1}\right). S r ( a ) = z 0 , … , z 4 ∈ K r ∑ ψ K r ( i = 0 ∑ 4 a i 2 z i z i + 1 z i + 2 + i = 0 ∑ 4 z i z i + 1 ) .
Expanding the argument gives
a 0 2 z 0 z 1 z 2 + a 1 2 z 1 z 2 z 3 + a 2 2 z 2 z 3 z 4 + a 3 2 z 3 z 4 z 0 + a 4 2 z 4 z 0 z 1 + z 0 z 1 + z 1 z 2 + z 2 z 3 + z 3 z 4 + z 4 z 0 . a_0^2z_0z_1z_2+a_1^2z_1z_2z_3+a_2^2z_2z_3z_4+a_3^2z_3z_4z_0+a_4^2z_4z_0z_1
+z_0z_1+z_1z_2+z_2z_3+z_3z_4+z_4z_0. a 0 2 z 0 z 1 z 2 + a 1 2 z 1 z 2 z 3 + a 2 2 z 2 z 3 z 4 + a 3 2 z 3 z 4 z 0 + a 4 2 z 4 z 0 z 1 + z 0 z 1 + z 1 z 2 + z 2 z 3 + z 3 z 4 + z 4 z 0 .
Set
A = 1 + a 2 2 z 2 + a 3 2 z 0 . A=1+a_2^2z_2+a_3^2z_0. A = 1 + a 2 2 z 2 + a 3 2 z 0 .
Grouping the terms involving z 3 , z 4 z_3,z_4 z 3 , z 4 , the argument becomes
A z 3 z 4 + z 2 ( 1 + a 1 2 z 1 ) z 3 + z 0 ( 1 + a 4 2 z 1 ) z 4 + z 1 ( a 0 2 z 0 z 2 + z 0 + z 2 ) . (5) Az_3z_4+z_2(1+a_1^2z_1)z_3+z_0(1+a_4^2z_1)z_4+z_1(a_0^2z_0z_2+z_0+z_2). \tag*{(5)} A z 3 z 4 + z 2 ( 1 + a 1 2 z 1 ) z 3 + z 0 ( 1 + a 4 2 z 1 ) z 4 + z 1 ( a 0 2 z 0 z 2 + z 0 + z 2 ) . (5)
If A ≠ 0 A\ne0 A = 0 , then character orthogonality gives
∑ z 3 , z 4 ∈ K r ψ K r ( A z 3 z 4 + z 2 ( 1 + a 1 2 z 1 ) z 3 + z 0 ( 1 + a 4 2 z 1 ) z 4 ) = ∑ z 4 ∈ K r ψ K r ( z 0 ( 1 + a 4 2 z 1 ) z 4 ) ∑ z 3 ∈ K r ψ K r ( ( A z 4 + z 2 ( 1 + a 1 2 z 1 ) ) z 3 ) = Q ψ K r ( z 0 z 2 ( 1 + a 1 2 z 1 ) ( 1 + a 4 2 z 1 ) A ) . \begin{aligned}
\sum_{z_3,z_4\in K_r}\psi_{K_r}\bigl(Az_3z_4+z_2(1+a_1^2z_1)z_3+z_0(1+a_4^2z_1)z_4\bigr)
&=\sum_{z_4\in K_r}\psi_{K_r}\bigl(z_0(1+a_4^2z_1)z_4\bigr)
\sum_{z_3\in K_r}\psi_{K_r}\bigl((Az_4+z_2(1+a_1^2z_1))z_3\bigr)\\
&=Q\psi_{K_r}\left(\frac{z_0z_2(1+a_1^2z_1)(1+a_4^2z_1)}{A}\right).
\end{aligned} z 3 , z 4 ∈ K r ∑ ψ K r ( A z 3 z 4 + z 2 ( 1 + a 1 2 z 1 ) z 3 + z 0 ( 1 + a 4 2 z 1 ) z 4 ) = z 4 ∈ K r ∑ ψ K r ( z 0 ( 1 + a 4 2 z 1 ) z 4 ) z 3 ∈ K r ∑ ψ K r ( ( A z 4 + z 2 ( 1 + a 1 2 z 1 )) z 3 ) = Q ψ K r ( A z 0 z 2 ( 1 + a 1 2 z 1 ) ( 1 + a 4 2 z 1 ) ) .
Indeed, the inner sum vanishes unless A z 4 + z 2 ( 1 + a 1 2 z 1 ) = 0 Az_4+z_2(1+a_1^2z_1)=0 A z 4 + z 2 ( 1 + a 1 2 z 1 ) = 0 , which forces z 4 = z 2 ( 1 + a 1 2 z 1 ) / A z_4=z_2(1+a_1^2z_1)/A z 4 = z 2 ( 1 + a 1 2 z 1 ) / A .
Including the remaining term in (5) , the contribution for fixed z 0 , z 2 z_0,z_2 z 0 , z 2 with A ≠ 0 A\ne0 A = 0 is
Q ∑ z 1 ∈ K r ψ K r ( z 1 ( a 0 2 z 0 z 2 + z 0 + z 2 ) + z 0 z 2 ( 1 + a 1 2 z 1 ) ( 1 + a 4 2 z 1 ) A ) . (6) Q\sum_{z_1\in K_r}\psi_{K_r}\left(z_1(a_0^2z_0z_2+z_0+z_2)+\frac{z_0z_2(1+a_1^2z_1)(1+a_4^2z_1)}{A}\right). \tag*{(6)} Q z 1 ∈ K r ∑ ψ K r ( z 1 ( a 0 2 z 0 z 2 + z 0 + z 2 ) + A z 0 z 2 ( 1 + a 1 2 z 1 ) ( 1 + a 4 2 z 1 ) ) . (6)
Let s ∈ K r s \in K_r s ∈ K r be the unique element satisfying
s 2 = z 0 z 2 A . s^2 = \frac{z_0z_2}{A}. s 2 = A z 0 z 2 .
Using
( 1 + a 1 2 z 1 ) ( 1 + a 1 2 z 1 ) = 1 + ( a 1 + a 4 ) 2 z 1 + ( a 1 a 4 ) 2 z 1 2 , (1+a_1^2z_1)(1+a_1^2z_1)=1+(a_1+a_4)^2z_1+(a_1a_4)^2z_1^2, ( 1 + a 1 2 z 1 ) ( 1 + a 1 2 z 1 ) = 1 + ( a 1 + a 4 ) 2 z 1 + ( a 1 a 4 ) 2 z 1 2 ,
the argument in Eq. (6) becomes
s 2 + ( a 0 2 z 0 z 2 + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 ) z 1 + ( a 1 a 4 ) 2 s 2 z 1 2 . s^2+(a_0^2z_0z_2+z_0+z_2+(a_1+a_4)^2s^2)z_1+(a_1a_4)^2s^2z_1^2. s 2 + ( a 0 2 z 0 z 2 + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 ) z 1 + ( a 1 a 4 ) 2 s 2 z 1 2 .
Hence the contribution in Eq. (6) equals
Q ψ K r ( s ) ∑ z 1 ∈ K r ψ K r ( ( a 0 2 z 0 z 2 + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s ) z 1 ) . Q\psi_{K_r}(s)\sum_{z_1\in K_r}\psi_{K_r}\left((a_0^2z_0z_2+z_0+z_2+(a_1+a_4)^2s^2+a_1a_4s)z_1\right). Q ψ K r ( s ) z 1 ∈ K r ∑ ψ K r ( ( a 0 2 z 0 z 2 + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s ) z 1 ) .
Orthogonality shows that this equals Q 2 ψ K r ( s ) Q^2\psi_{K_r}(s) Q 2 ψ K r ( s ) if
a 0 2 z 0 z 2 + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s = 0 , a_0^2z_0z_2+z_0+z_2+(a_1+a_4)^2s^2+a_1a_4s=0, a 0 2 z 0 z 2 + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s = 0 ,
and equals zero otherwise.
Thus the contribution from A ≠ 0 A\ne0 A = 0 , divided by Q 2 Q^2 Q 2 , is the number of solutions of
z 0 z 2 = s 2 A = s 2 ( 1 + a 2 2 z 2 + a 3 2 z 0 ) , (7) z_0z_2=s^2A=s^2(1+a_2^2z_2+a_3^2z_0), \tag*{(7)} z 0 z 2 = s 2 A = s 2 ( 1 + a 2 2 z 2 + a 3 2 z 0 ) , (7)
a 0 2 z 0 z 2 + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s = 0 , (8) a_0^2z_0z_2+z_0+z_2+(a_1+a_4)^2s^2+a_1a_4s=0, \tag*{(8)} a 0 2 z 0 z 2 + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s = 0 , (8)
multiplied by ψ K r ( s ) \psi_{K_r}(s) ψ K r ( s ) .
We first count these equations without imposing A ≠ 0 A\ne0 A = 0 . Afterward, we subtract their solutions with A = 0 A=0 A = 0 and restore the contribution from that case in the original sum.
Counting the solutions for fixed s s s . Fix s ∈ K r s\in K_r s ∈ K r and introduce
u = z 0 + a 2 2 s 2 , v = z 2 + a 3 2 s 2 . u=z_0+a_2^2s^2,\qquad v=z_2+a_3^2s^2. u = z 0 + a 2 2 s 2 , v = z 2 + a 3 2 s 2 .
For fixed s s s , these translations are bijections, so counting pairs ( u , v ) (u,v) ( u , v ) is equivalent to counting pairs ( z 0 , z 2 ) (z_0,z_2) ( z 0 , z 2 ) .
We introduce new variables to simplify this system of equations.
p = 1 + a 0 a 3 s , b = 1 + a 0 a 2 s , j = 1 + a 2 a 3 s , M = a 1 a 4 + Tr L / K ( a ) 2 s . p=1+a_0a_3s,\qquad b=1+a_0a_2s,\qquad j=1+a_2a_3s,\qquad M=a_1a_4+\operatorname{Tr}_{L/K}(a)^2s. p = 1 + a 0 a 3 s , b = 1 + a 0 a 2 s , j = 1 + a 2 a 3 s , M = a 1 a 4 + Tr L / K ( a ) 2 s .
Then
u v = z 0 z 2 + a 3 2 s 2 z 0 + a 2 2 s 2 z 2 + a 2 2 a 3 2 s 4 = s 2 ( 1 + a 2 2 z 2 + a 3 2 z 0 ) + a 3 2 s 2 z 0 + a 2 2 s 2 z 2 + a 2 2 a 3 2 s 4 = s 2 j 2 , \begin{aligned}
uv&=z_0z_2+a_3^2s^2z_0+a_2^2s^2z_2+a_2^2a_3^2s^4\\
&=s^2(1+a_2^2z_2+a_3^2z_0)+a_3^2s^2z_0+a_2^2s^2z_2+a_2^2a_3^2s^4\\
&=s^2j^2,
\end{aligned} uv = z 0 z 2 + a 3 2 s 2 z 0 + a 2 2 s 2 z 2 + a 2 2 a 3 2 s 4 = s 2 ( 1 + a 2 2 z 2 + a 3 2 z 0 ) + a 3 2 s 2 z 0 + a 2 2 s 2 z 2 + a 2 2 a 3 2 s 4 = s 2 j 2 ,
using Eq. (7) in the second step.
Substituting Eq. (7) into Eq. (8) to eliminate z 0 z 2 z_0z_2 z 0 z 2 , and then expressing the result through the newly introduced variables gives
a 0 2 s 2 ( 1 + a 2 2 z 2 + a 3 2 z 0 ) + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s = p 2 u + b 2 v + Tr L / K ( a ) 2 s 2 + a 1 a 4 s . a_0^2s^2(1+a_2^2z_2+a_3^2z_0)+z_0+z_2+(a_1+a_4)^2s^2+a_1a_4s=p^2u+b^2v+\operatorname{Tr}_{L/K}(a)^2s^2+a_1a_4s. a 0 2 s 2 ( 1 + a 2 2 z 2 + a 3 2 z 0 ) + z 0 + z 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s = p 2 u + b 2 v + Tr L / K ( a ) 2 s 2 + a 1 a 4 s .
Notice further that p 2 u + b 2 v + Tr L / K ( a ) 2 s 2 + a 1 a 4 s = 0 p^2u+b^2v+\operatorname{Tr}_{L/K}(a)^2s^2+a_1a_4s=0 p 2 u + b 2 v + Tr L / K ( a ) 2 s 2 + a 1 a 4 s = 0 is equivalent to p 2 u + b 2 v = s M p^2u+b^2v=sM p 2 u + b 2 v = s M . Thus counting the solutions to Eq. (7) and Eq. (8) is equivalent to counting the solutions of the system of two equations
u v = s 2 j 2 , p 2 u + b 2 v = s M . (9) uv=s^2j^2,\qquad p^2u+b^2v=sM. \tag*{(9)} uv = s 2 j 2 , p 2 u + b 2 v = s M . (9)
Let N s N_s N s denote their number. We distinguish several cases.
Case s M ≠ 0 sM\ne0 s M = 0 and $pb\ne0. Assume Eq. (9) holds. Then p 2 u p^2u p 2 u and b 2 v b^2v b 2 v have sum s M sM s M and product ( s p b j ) 2 (spbj)^2 ( s p bj ) 2 . Therefore they are the roots of the quadratic equation
w 2 + s M w + ( s p b j ) 2 = 0. w^2+sMw+(spbj)^2=0. w 2 + s M w + ( s p bj ) 2 = 0.
Each root chosen as p 2 u p^{2}u p 2 u determines the other root b 2 v = s M + p 2 u b^{2}v=sM+p^{2}u b 2 v = s M + p 2 u , and hence determines exactly one ordered pair ( u , v ) (u,v) ( u , v ) .
The quadratic equation has 2 roots if Tr K r / F 2 ( p b j / M ) = 0 \operatorname{Tr}_{K_r/\mathbb{F}_2}(pbj/M)=0 Tr K r / F 2 ( p bj / M ) = 0 and 0 roots else (this follows from Hilbert’s Theorem 90, see e.g [5 Section 14.5.] for the solvability of quadratic equations in characteristic 2 more generally), in other words
N s = 1 + ψ K r ( p b j M ) . (10) N_s=1+\psi_{K_r}\left(\frac{pbj}{M}\right). \tag*{(10)} N s = 1 + ψ K r ( M p bj ) . (10)
Case p b = 0 pb=0 p b = 0 , and s M ≠ 0 sM\ne0 s M = 0 . If exactly one of p , b p,b p , b is zero, the second condition of Eq. (9) fixes one of u , v u,v u , v to a unique value (depending on if p = 0 p=0 p = 0 or b = 0 b=0 b = 0 ). The first condition of Eq. (9) then fixes the other one, so N s = 1 N_s=1 N s = 1 in all these cases. If both p , b p,b p , b are zero, the second condition of Eq. (9) is 0 = s M 0=sM 0 = s M , which is impossible, so N s = 0 N_s=0 N s = 0 .
Case s M = 0 sM=0 s M = 0 . For the moment, assume a ≠ 1 a\ne1 a = 1 , the case a = 1 a=1 a = 1 will be handled separately later. If s = 0 s=0 s = 0 , we have by definition of the auxiliary variables p = b = j = 1 p=b=j=1 p = b = j = 1 , and Eq. (9) becomes u v = 0 uv=0 uv = 0 , u + v = 0 u+v=0 u + v = 0 . Thus u = v = 0 u=v=0 u = v = 0 is the unique solution, and N 0 = 1 N_0=1 N 0 = 1 .
If M = 0 M=0 M = 0 , then Tr L / K ( a ) ≠ 0 \operatorname{Tr}_{L/K}(a)\ne0 Tr L / K ( a ) = 0 and s = a 1 a 4 / Tr L / K ( a ) 2 s=a_1a_4/\operatorname{Tr}_{L/K}(a)^2 s = a 1 a 4 / Tr L / K ( a ) 2 . Plugging this into the definitions of p p p and b b b yields
p = Tr L / K ( a ) 2 + N L / K ( a ) / a 2 Tr L / K ( a ) 2 , b = Tr L / K ( a ) 2 + N L / K ( a ) / a 3 Tr L / K ( a ) 2 . p=\frac{\operatorname{Tr}_{L/K}(a)^2+N_{L/K}(a)/a_2}{\operatorname{Tr}_{L/K}(a)^2},\qquad b=\frac{\operatorname{Tr}_{L/K}(a)^2+N_{L/K}(a)/a_3}{\operatorname{Tr}_{L/K}(a)^2}. p = Tr L / K ( a ) 2 Tr L / K ( a ) 2 + N L / K ( a ) / a 2 , b = Tr L / K ( a ) 2 Tr L / K ( a ) 2 + N L / K ( a ) / a 3 .
Note that both p , b p,b p , b are nonzero. Indeed, if Tr L / K ( a ) 2 + N L / K ( a ) / a i = 0 \operatorname{Tr}_{L/K}(a)^2+N_{L/K}(a)/a_i=0 Tr L / K ( a ) 2 + N L / K ( a ) / a i = 0 , then a i = N L / K ( a ) / Tr L / K ( a ) 2 ∈ K a_i=N_{L/K}(a)/\operatorname{Tr}_{L/K}(a)^2\in K a i = N L / K ( a ) / Tr L / K ( a ) 2 ∈ K , forcing a ∈ K a\in K a ∈ K . In that case Tr L / K ( a ) = a \operatorname{Tr}_{L/K}(a)=a Tr L / K ( a ) = a , N L / K ( a ) = a 5 N_{L/K}(a)=a^5 N L / K ( a ) = a 5 , and
Tr L / K ( a ) 2 + N L / K ( a ) a i = a 2 ( a + 1 ) 2 ≠ 0 \operatorname{Tr}_{L/K}(a)^2+\frac{N_{L/K}(a)}{a_i}=a^2(a+1)^2\ne0 Tr L / K ( a ) 2 + a i N L / K ( a ) = a 2 ( a + 1 ) 2 = 0
because a ∉ { 0 , 1 } a\notin\{0,1\} a ∈ / { 0 , 1 } .
The second condition of Eq. (9) now gives v = ( p 2 / b 2 ) u v=(p^2/b^2)u v = ( p 2 / b 2 ) u . Substituting this into the first condition of Eq. (9) gives
( p b u ) 2 = ( s j ) 2 . \left(\frac{p}{b}u\right)^2=(sj)^2. ( b p u ) 2 = ( s j ) 2 .
There is precisely one solution u u u of this equation. Thus N s = 1 N_s=1 N s = 1 when M = 0 M=0 M = 0 as well.
So in total we have N s = 1 + ψ K r ( p b j / M ) N_s=1+\psi_{K_r}(pbj/M) N s = 1 + ψ K r ( p bj / M ) if p b ≠ 0 pb\ne0 p b = 0 and s M ≠ 0 sM\ne0 s M = 0 , N s = 0 N_s=0 N s = 0 if p = b = 0 p=b=0 p = b = 0 and N s = 1 N_s=1 N s = 1 in all other cases. p = 0 p=0 p = 0 happens exactly when s = 1 / ( a 0 a 3 ) s=1/(a_0a_3) s = 1/ ( a 0 a 3 ) , and b = 0 b=0 b = 0 exactly when s = 1 / ( a 0 a 2 ) s=1/(a_0a_2) s = 1/ ( a 0 a 2 ) .
Summing the weighted counts. We now calculate Q 2 ⋅ N s ⋅ ψ K r ( s ) Q^2\cdot N_s\cdot\psi_{K_r}(s) Q 2 ⋅ N s ⋅ ψ K r ( s ) . For now, we include the case A = 0 A=0 A = 0 , which we will later subtract. By the determination of N s N_s N s just now, we get:
∑ s ∈ K r Q 2 ψ K r ( s ) N s = Q 2 ( ∑ s ∈ K r s M ≠ 0 ψ K r ( s ) ( 1 + ψ K r ( p b j / M ) ) − ψ K r ( 1 / ( a 0 a 3 ) ) − ψ K r ( 1 / ( a 0 a 2 ) ) + ∑ s ∈ K r s M = 0 ψ K r ( s ) ) \sum_{s\in K_r}Q^2\psi_{K_r}(s)N_s
=Q^2\left(\sum_{\substack{s\in K_r\\sM\ne0}}\psi_{K_r}(s)\left(1+\psi_{K_r}(pbj/M)\right)-\psi_{K_r}\left(1/(a_0a_3)\right)-\psi_{K_r}\left(1/(a_0a_2)\right)+\sum_{\substack{s\in K_r\\sM=0}}\psi_{K_r}(s)\right) s ∈ K r ∑ Q 2 ψ K r ( s ) N s = Q 2 s ∈ K r s M = 0 ∑ ψ K r ( s ) ( 1 + ψ K r ( p bj / M ) ) − ψ K r ( 1/ ( a 0 a 3 ) ) − ψ K r ( 1/ ( a 0 a 2 ) ) + s ∈ K r s M = 0 ∑ ψ K r ( s )
where we include all cases from the previous calculations. This simplifies by character orthogonality to
∑ s ∈ K r Q 2 ψ K r ( s ) N s = Q 2 ( ∑ s ∈ K r , s M ≠ 0 ψ K r ( s ) ψ K r ( p b j / M ) − ψ K r ( 1 / ( a 0 a 3 ) ) − ψ K r ( 1 / ( a 0 a 2 ) ) ) = Q 2 ( ∑ s ∈ K r , s M ≠ 0 ψ K r ( s + p b j / M ) − 2 ψ K r ( 1 / ( a 0 a 2 ) ) ) = Q 2 ( ∑ s ∈ K r , M ≠ 0 ( ψ K r ( s + p b j / M ) ) − 3 ψ K r ( 1 / ( a 0 a 2 ) ) ) . \begin{aligned}
\sum_{s\in K_r} Q^2\psi_{K_r}(s)N_s
&= Q^2\left(\sum_{\substack{s\in K_r,\\sM\ne0}}\psi_{K_r}(s)\psi_{K_r}(pbj/M)-\psi_{K_r}(1/(a_0a_3))-\psi_{K_r}(1/(a_0a_2))\right)\\
&= Q^2\left(\sum_{\substack{s\in K_r,\\sM\ne0}}\psi_{K_r}(s+pbj/M)-2\psi_{K_r}(1/(a_0a_2))\right)\\
&= Q^2\left(\sum_{\substack{s\in K_r,\\M\ne0}}\left(\psi_{K_r}(s+pbj/M)\right)-3\psi_{K_r}(1/(a_0a_2))\right).
\end{aligned} s ∈ K r ∑ Q 2 ψ K r ( s ) N s = Q 2 s ∈ K r , s M = 0 ∑ ψ K r ( s ) ψ K r ( p bj / M ) − ψ K r ( 1/ ( a 0 a 3 )) − ψ K r ( 1/ ( a 0 a 2 )) = Q 2 s ∈ K r , s M = 0 ∑ ψ K r ( s + p bj / M ) − 2 ψ K r ( 1/ ( a 0 a 2 )) = Q 2 s ∈ K r , M = 0 ∑ ( ψ K r ( s + p bj / M ) ) − 3 ψ K r ( 1/ ( a 0 a 2 )) .
by recognizing that ψ K r ( 1 / ( a 0 a 2 ) ) = ψ K r ( 1 / ( a 0 a 3 ) ) \psi_{K_r}(1/(a_0a_2))=\psi_{K_r}(1/(a_0a_3)) ψ K r ( 1/ ( a 0 a 2 )) = ψ K r ( 1/ ( a 0 a 3 )) since a 0 a 3 = ( a 0 a 2 ) q 3 a_0a_3=(a_0a_2)^{q^3} a 0 a 3 = ( a 0 a 2 ) q 3 , and similarly, for s = 0 s=0 s = 0 we have ψ K r ( s + p b j / M ) = ψ K r ( 1 / ( a 1 a 4 ) ) = ψ K r ( 1 / ( a 0 a 2 ) ) \psi_{K_r}(s+pbj/M)=\psi_{K_r}(1/(a_1a_4))=\psi_{K_r}(1/(a_0a_2)) ψ K r ( s + p bj / M ) = ψ K r ( 1/ ( a 1 a 4 )) = ψ K r ( 1/ ( a 0 a 2 )) .
G ( s ) = s + p b j M = s + ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) a 1 a 4 + Tr L / K ( a ) 2 s . G(s)=s+\frac{pbj}{M}=s+\frac{(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s)}{a_1a_4+\operatorname{Tr}_{L/K}(a)^2s}. G ( s ) = s + M p bj = s + a 1 a 4 + Tr L / K ( a ) 2 s ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) .
Hence
∑ s ∈ K r ψ K r ( s ) N s = ∑ s ∈ K r M ≠ 0 ψ K r ( G ( s ) ) − 3 ψ K r ( ( a 1 a 4 ) − 1 ) . (11) \sum_{s\in K_r}\psi_{K_r}(s)N_s=\sum_{\substack{s\in K_r\\M\ne0}}\psi_{K_r}(G(s))-3\psi_{K_r}((a_1a_4)^{-1}). \tag*{(11)} s ∈ K r ∑ ψ K r ( s ) N s = s ∈ K r M = 0 ∑ ψ K r ( G ( s )) − 3 ψ K r (( a 1 a 4 ) − 1 ) . (11)
However, we counted also the solutions for A = 0 A=0 A = 0 , which we have to subtract now.
The case A = 0 A=0 A = 0 . We must remove the solutions with A = 0 A=0 A = 0 and restore their contribution in the original sum. If A = 0 A=0 A = 0 , Eq. (7) gives z 0 z 2 = 0 z_0z_2=0 z 0 z 2 = 0 . Recalling that A = 1 + a 2 2 z 2 + a 3 2 z 0 A=1+a_2^2z_2+a_3^2z_0 A = 1 + a 2 2 z 2 + a 3 2 z 0 , the only possibilities are ( z 0 , z 2 ) = ( 0 , a 2 − 2 ) (z_0,z_2)=(0,a_2^{-2}) ( z 0 , z 2 ) = ( 0 , a 2 − 2 ) or ( z 0 , z 2 ) = ( a 3 − 2 , 0 ) (z_0,z_2)=(a_3^{-2},0) ( z 0 , z 2 ) = ( a 3 − 2 , 0 ) .
Eq. (8) then leads to
a j − 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s = 0. a_j^{-2}+(a_1+a_4)^2s^2+a_1a_4s=0. a j − 2 + ( a 1 + a 4 ) 2 s 2 + a 1 a 4 s = 0.
for j = 2 j=2 j = 2 in the first case and j = 3 j=3 j = 3 in the second case. Multiplying by a j 2 a_j^2 a j 2 yields a quadratic relation:
1 + a j 2 a 1 a 4 s + a j 2 ( a 1 + a 4 ) 2 s 2 = 0. (12) 1+a_j^2a_1a_4s+a_j^2(a_1+a_4)^2s^2=0. \tag*{(12)} 1 + a j 2 a 1 a 4 s + a j 2 ( a 1 + a 4 ) 2 s 2 = 0. (12)
Under this relation, we have that
( a 1 + a 4 a 1 s + 1 a 1 a j ) 2 + ( a 1 + a 4 a 1 s + 1 a 1 a j ) = s + 1 a 1 a j , \left(\frac{a_1+a_4}{a_1}s+\frac{1}{a_1a_j}\right)^2+\left(\frac{a_1+a_4}{a_1}s+\frac{1}{a_1a_j}\right)=s+\frac{1}{a_1a_j}, ( a 1 a 1 + a 4 s + a 1 a j 1 ) 2 + ( a 1 a 1 + a 4 s + a 1 a j 1 ) = s + a 1 a j 1 ,
since, by Eq. (12) , ( a 1 + a 4 ) 2 s 2 / a 1 2 + 1 / ( a 1 2 a j 2 ) = ( a 4 / a 1 ) s (a_1+a_4)^2s^2/a_1^2+1/(a_1^2a_j^2)=(a_4/a_1)s ( a 1 + a 4 ) 2 s 2 / a 1 2 + 1/ ( a 1 2 a j 2 ) = ( a 4 / a 1 ) s . Since the left hand side has absolute trace 0, we deduce that
ψ K r ( s ) = ψ K r ( ( a 1 a j ) − 1 ) . \psi_{K_r}(s)=\psi_{K_r}((a_1a_j)^{-1}). ψ K r ( s ) = ψ K r (( a 1 a j ) − 1 ) .
If a 1 ≠ a 4 a_1\ne a_4 a 1 = a 4 , the number of solutions of Eq. (12) is (again using the standard formula for quadratic equations in characteristic 2)
1 + ψ K r ( a 1 + a 4 a j a 1 a 4 ) = 1 + ψ K r ( 1 a 1 a j + 1 a 4 a j ) . 1+\psi_{K_r}\left(\frac{a_1+a_4}{a_ja_1a_4}\right)=1+\psi_{K_r}\left(\frac{1}{a_1a_j}+\frac{1}{a_4a_j}\right). 1 + ψ K r ( a j a 1 a 4 a 1 + a 4 ) = 1 + ψ K r ( a 1 a j 1 + a 4 a j 1 ) .
Then
ψ K r ( s ) ( 1 + ψ K r ( 1 a 1 a j + 1 a 4 a j ) ) = ψ K r ( ( a 1 a j ) − 1 ) + ψ K r ( ( a 4 a j ) − 1 ) . \psi_{K_r}(s)\left(1+\psi_{K_r}\left(\frac{1}{a_1a_j}+\frac{1}{a_4a_j}\right)\right)=\psi_{K_r}((a_1a_j)^{-1})+\psi_{K_r}((a_4a_j)^{-1}). ψ K r ( s ) ( 1 + ψ K r ( a 1 a j 1 + a 4 a j 1 ) ) = ψ K r (( a 1 a j ) − 1 ) + ψ K r (( a 4 a j ) − 1 ) .
The total contribution for both j = 2 j=2 j = 2 and j = 3 j=3 j = 3 is thus
ψ K r ( ( a 1 a 2 ) − 1 ) + ψ K r ( ( a 4 a 2 ) − 1 ) + ψ K r ( ( a 1 a 3 ) − 1 ) + ψ K r ( ( a 4 a 3 ) − 1 ) = 2 ( ψ K r ( ( a 1 a 2 ) − 1 ) + ψ K r ( ( a 1 a 4 ) − 1 ) ) . (13) \psi_{K_r}\left((a_1a_2)^{-1}\right)+\psi_{K_r}\left((a_4a_2)^{-1}\right)+\psi_{K_r}\left((a_1a_3)^{-1}\right)+\psi_{K_r}\left((a_4a_3)^{-1}\right)=2\left(\psi_{K_r}\left((a_1a_2)^{-1}\right)+\psi_{K_r}\left((a_1a_4)^{-1}\right)\right). \tag*{(13)} ψ K r ( ( a 1 a 2 ) − 1 ) + ψ K r ( ( a 4 a 2 ) − 1 ) + ψ K r ( ( a 1 a 3 ) − 1 ) + ψ K r ( ( a 4 a 3 ) − 1 ) = 2 ( ψ K r ( ( a 1 a 2 ) − 1 ) + ψ K r ( ( a 1 a 4 ) − 1 ) ) . (13)
If a 1 = a 4 a_1=a_4 a 1 = a 4 , then a i = a a_i=a a i = a for all i i i (since a ∈ K a\in K a ∈ K ) and Eq. (12) is linear and has one solution s s s with ψ K r ( s ) = ψ K r ( a − 2 ) \psi_{K_r}(s)=\psi_{K_r}(a^{-2}) ψ K r ( s ) = ψ K r ( a − 2 ) .
We now compare these excluded weights with the original contribution at A = 0 A=0 A = 0 . In Eq. (5) , the sum over z 3 , z 4 z_3,z_4 z 3 , z 4 at A = 0 A=0 A = 0 equals Q 2 Q^2 Q 2 precisely when z 2 ( 1 + a 1 2 z 1 ) = 0 z_2(1+a_1^2z_1)=0 z 2 ( 1 + a 1 2 z 1 ) = 0 and z 0 ( 1 + a 4 2 z 1 ) = 0 z_0(1+a_4^2z_1)=0 z 0 ( 1 + a 4 2 z 1 ) = 0 .
If a 1 ≠ a 4 a_1\ne a_4 a 1 = a 4 , then z 0 , z 2 z_0,z_2 z 0 , z 2 cannot both be nonzero. There are thus only two possible solutions ( z 0 , z 1 , z 2 ) = ( 0 , a 1 − 2 , a 2 − 2 ) (z_0,z_1,z_2)=(0,a_1^{-2},a_2^{-2}) ( z 0 , z 1 , z 2 ) = ( 0 , a 1 − 2 , a 2 − 2 ) and ( z 0 , z 1 , z 2 ) = ( a 3 − 2 , a 4 − 2 , 0 ) (z_0,z_1,z_2)=(a_3^{-2},a_4^{-2},0) ( z 0 , z 1 , z 2 ) = ( a 3 − 2 , a 4 − 2 , 0 ) , recalling that z 0 = z 2 = 0 z_0=z_2=0 z 0 = z 2 = 0 would lead to A = 1 A=1 A = 1 . In both cases the character ψ K r \psi_{K_r} ψ K r of the term in Eq. (5) is ψ K r ( ( a 1 a 2 ) − 1 ) \psi_{K_r}((a_1a_2)^{-1}) ψ K r (( a 1 a 2 ) − 1 ) (after applying an appropriate Frobenius automorphism inside the character).
Thus the net correction is, taking Eq. (13) into account, − 2 ψ K r ( ( a 1 a 4 ) − 1 ) -2\psi_{K_r}((a_1a_4)^{-1}) − 2 ψ K r (( a 1 a 4 ) − 1 ) for the case a 1 ≠ a 4 a_1\ne a_4 a 1 = a 4 .
If a 1 = a 4 a_1=a_4 a 1 = a 4 , then z 2 ( 1 + a 1 2 z 1 ) = 0 z_2(1+a_1^2z_1)=0 z 2 ( 1 + a 1 2 z 1 ) = 0 and z 0 ( 1 + a 4 2 z 1 ) = 0 z_0(1+a_4^2z_1)=0 z 0 ( 1 + a 4 2 z 1 ) = 0 implies (keeping in mind that now a i = a a_i=a a i = a for all i i i and z 0 = z 2 = 0 z_0=z_2=0 z 0 = z 2 = 0 is impossible) z 1 = a − 2 z_1=a^{-2} z 1 = a − 2 and the condition A = 1 + a 2 ( z 0 + z 2 ) = 0 A=1+a^2(z_0+z_2)=0 A = 1 + a 2 ( z 0 + z 2 ) = 0 forces z 2 = z 0 + a − 2 z_2=z_0+a^{-2} z 2 = z 0 + a − 2 . Plugging these values into Eq. (5) yields a remaining term of z 0 2 + a − 2 z 0 + a − 4 z_0^2+a^{-2}z_0+a^{-4} z 0 2 + a − 2 z 0 + a − 4 . Therefore its contribution is
Q 2 ∑ z 0 ∈ K r ψ K r ( z 0 2 + a − 2 z 0 + a − 4 ) = Q 2 ψ K r ( a − 1 ) ∑ z 0 ∈ K r ψ K r ( ( 1 + a − 2 ) z 0 ) = { 0 , a ≠ 1 , Q 3 ψ K r ( 1 ) , a = 1. Q^2\sum_{z_0\in K_r}\psi_{K_r}\left(z_0^2+a^{-2}z_0+a^{-4}\right)=Q^2\psi_{K_r}(a^{-1})\sum_{z_0\in K_r}\psi_{K_r}\left((1+a^{-2})z_0\right)
=\begin{cases}
0, & a\ne1,\\
Q^3\psi_{K_r}(1), & a=1.
\end{cases} Q 2 z 0 ∈ K r ∑ ψ K r ( z 0 2 + a − 2 z 0 + a − 4 ) = Q 2 ψ K r ( a − 1 ) z 0 ∈ K r ∑ ψ K r ( ( 1 + a − 2 ) z 0 ) = { 0 , Q 3 ψ K r ( 1 ) , a = 1 , a = 1.
Consequently, for every a ∈ L × a\in L^\times a ∈ L × , the entire boundary correction is accounted for by
S r ( a ) = Q 2 ( ∑ s ∈ K r ψ K r ( s ) N s − 2 ψ K r ( ( a 1 a 4 ) − 1 ) + ϵ Q ψ K r ( 1 ) ) , (14) S_r(a)=Q^2\left(\sum_{s\in K_r}\psi_{K_r}(s)N_s-2\psi_{K_r}\left((a_1a_4)^{-1}\right)+\epsilon Q\psi_{K_r}(1)\right), \tag*{(14)} S r ( a ) = Q 2 ( s ∈ K r ∑ ψ K r ( s ) N s − 2 ψ K r ( ( a 1 a 4 ) − 1 ) + ϵ Q ψ K r ( 1 ) ) , (14)
where ϵ = 1 \epsilon=1 ϵ = 1 if a = 1 a=1 a = 1 and 0 0 0 else. For a ∉ { 0 , 1 } a\notin\{0,1\} a ∈ / { 0 , 1 } , combining this with Eq. (11) gives
S r ( a ) = Q 2 ( ∑ s ∈ K r , ( a 1 a 4 + Tr L / K ( a ) 2 s ≠ 0 ) ψ K r ( s + ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) a 1 a 4 + Tr L / K ( a ) 2 s ) − 5 ψ K r ( ( a 1 a 4 ) − 1 ) ) . (15) S_r(a)=Q^2\left(\sum_{\substack{s\in K_r,\\(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s\ne0)}}\psi_{K_r}\left(s+\frac{(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s)}{a_1a_4+\operatorname{Tr}_{L/K}(a)^2s}\right)-5\psi_{K_r}\left((a_1a_4)^{-1}\right)\right). \tag*{(15)} S r ( a ) = Q 2 s ∈ K r , ( a 1 a 4 + Tr L / K ( a ) 2 s = 0 ) ∑ ψ K r ( s + a 1 a 4 + Tr L / K ( a ) 2 s ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) ) − 5 ψ K r ( ( a 1 a 4 ) − 1 ) . (15)
Comparing the remaining sum with the curve. Continue for now to assume a ∉ { 0 , 1 } a\notin\{0,1\} a ∈ / { 0 , 1 } . We interpret the character sum in Eq. (15) as the number of points on a curve.
For each s ∈ K r s\in K_r s ∈ K r with a 1 a 4 + Tr L / K ( a ) 2 s ≠ 0 a_1a_4+\operatorname{Tr}_{L/K}(a)^2s\ne0 a 1 a 4 + Tr L / K ( a ) 2 s = 0 , the equation
w 2 + w = s + ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) a 1 a 4 + Tr L / K ( a ) 2 s (16) w^2+w=s+\frac{(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s)}{a_1a_4+\operatorname{Tr}_{L/K}(a)^2s} \tag*{(16)} w 2 + w = s + a 1 a 4 + Tr L / K ( a ) 2 s ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) (16)
has exactly
1 + ψ K r ( s + ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) a 1 a 4 + Tr L / K ( a ) 2 s ) 1+\psi_{K_r}\left(s+\frac{(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s)}{a_1a_4+\operatorname{Tr}_{L/K}(a)^2s}\right) 1 + ψ K r ( s + a 1 a 4 + Tr L / K ( a ) 2 s ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) )
solutions.
We first rewrite this equation as a cubic. Multiplying Eq. (16) by ( a 1 a 4 + Tr L / K ( a ) 2 s ) 2 (a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)^2 ( a 1 a 4 + Tr L / K ( a ) 2 s ) 2 gives
( ( a 1 a 4 + Tr L / K ( a ) 2 s ) w ) 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) ( ( a 1 a 4 + Tr L / K ( a ) 2 s ) w ) = s ( a 1 a 4 + Tr L / K ( a ) 2 s ) 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) . \left((a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)w\right)^2+(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)\left((a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)w\right)
=s(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)^2+(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s). ( ( a 1 a 4 + Tr L / K ( a ) 2 s ) w ) 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) ( ( a 1 a 4 + Tr L / K ( a ) 2 s ) w ) = s ( a 1 a 4 + Tr L / K ( a ) 2 s ) 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) .
The right side has degree at most four in s s s , with leading term
Tr L / K ( a ) 2 a 0 2 a 2 2 a 3 2 s 4 = ( Tr L / K ( a ) a 0 a 2 a 3 s 2 ) 2 . \operatorname{Tr}_{L/K}(a)^2a_0^2a_2^2a_3^2s^4=\left(\operatorname{Tr}_{L/K}(a)a_0a_2a_3s^2\right)^2. Tr L / K ( a ) 2 a 0 2 a 2 2 a 3 2 s 4 = ( Tr L / K ( a ) a 0 a 2 a 3 s 2 ) 2 .
We remove this square term by setting
v = ( a 1 a 4 + Tr L / K ( a ) 2 s ) w + Tr L / K ( a ) a 0 a 2 a 3 s 2 . v=(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)w+\operatorname{Tr}_{L/K}(a)a_0a_2a_3s^2. v = ( a 1 a 4 + Tr L / K ( a ) 2 s ) w + Tr L / K ( a ) a 0 a 2 a 3 s 2 .
For each fixed s s s with a 1 a 4 + Tr L / K ( a ) 2 s ≠ 0 a_1a_4+\operatorname{Tr}_{L/K}(a)^2s\ne0 a 1 a 4 + Tr L / K ( a ) 2 s = 0 , this is a bijection between w w w and v v v .
Substitution gives
v 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) v = s ( a 1 a 4 + Tr L / K ( a ) 2 s ) 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) + ( Tr L / K ( a ) a 0 a 2 a 3 s 2 ) 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) Tr L / K ( a ) a 0 a 2 a 3 s 2 . \begin{aligned}
v^2+(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)v
={}&s(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)^2\\
&+(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s)\\
&+(\operatorname{Tr}_{L/K}(a)a_0a_2a_3s^2)^2+(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)\operatorname{Tr}_{L/K}(a)a_0a_2a_3s^2.
\end{aligned} v 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) v = s ( a 1 a 4 + Tr L / K ( a ) 2 s ) 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) + ( Tr L / K ( a ) a 0 a 2 a 3 s 2 ) 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) Tr L / K ( a ) a 0 a 2 a 3 s 2 .
Expanding and cancelling the degree-four terms yields the cubic
v 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) v = ( Tr L / K ( a ) 2 + N L / K ( a ) a 1 ) ( Tr L / K ( a ) 2 + N L / K ( a ) a 4 ) s 3 + ( Tr L / K ( a ) 2 ( a 0 a 2 + a 0 a 3 + a 2 a 3 ) + N L / K ( a ) ( a 1 + a 4 ) ) s 2 + ( Tr L / K ( a ) 2 + ( a 1 a 4 ) 2 + a 1 a 4 ( a 0 a 2 + a 0 a 3 + a 2 a 3 ) ) s + a 1 a 4 , (17) \begin{aligned}
v^2+(a_1a_4+\operatorname{Tr}_{L/K}(a)^2s)v
={}&\left(\operatorname{Tr}_{L/K}(a)^2+\frac{N_{L/K}(a)}{a_1}\right)\left(\operatorname{Tr}_{L/K}(a)^2+\frac{N_{L/K}(a)}{a_4}\right)s^3\\
&+\left(\operatorname{Tr}_{L/K}(a)^2(a_0a_2+a_0a_3+a_2a_3)+N_{L/K}(a)(a_1+a_4)\right)s^2\\
&+\left(\operatorname{Tr}_{L/K}(a)^2+(a_1a_4)^2+a_1a_4(a_0a_2+a_0a_3+a_2a_3)\right)s\\
&+a_1a_4, \tag*{(17)}
\end{aligned} v 2 + ( a 1 a 4 + Tr L / K ( a ) 2 s ) v = ( Tr L / K ( a ) 2 + a 1 N L / K ( a ) ) ( Tr L / K ( a ) 2 + a 4 N L / K ( a ) ) s 3 + ( Tr L / K ( a ) 2 ( a 0 a 2 + a 0 a 3 + a 2 a 3 ) + N L / K ( a ) ( a 1 + a 4 ) ) s 2 + ( Tr L / K ( a ) 2 + ( a 1 a 4 ) 2 + a 1 a 4 ( a 0 a 2 + a 0 a 3 + a 2 a 3 ) ) s + a 1 a 4 , (17)
where we use N L / K ( a ) = a 0 a 1 a 2 a 3 a 4 N_{L/K}(a)=a_0a_1a_2a_3a_4 N L / K ( a ) = a 0 a 1 a 2 a 3 a 4 .
For a ≠ 1 a\ne1 a = 1 , the factors Tr L / K ( a ) 2 + N L / K ( a ) / a i \operatorname{Tr}_{L/K}(a)^2+N_{L/K}(a)/a_i Tr L / K ( a ) 2 + N L / K ( a ) / a i are nonzero by Lemma 3.2 . In particular, the coefficient of s 3 s^3 s 3 in Eq. (17) is nonzero.
Now make the affine change of coordinates
X = ( Tr L / K ( a ) 2 + N L / K ( a ) a 1 ) ( Tr L / K ( a ) 2 + N L / K ( a ) a 4 ) s + a 1 a 4 Tr L / K ( a ) 2 + N L / K ( a ) ( a 1 + a 4 ) , Y = ( Tr L / K ( a ) 2 + N L / K ( a ) a 1 ) ( Tr L / K ( a ) 2 + N L / K ( a ) a 4 ) v + ( e 2 ( a ) + Tr L / K ( a ) ( a 1 + a 4 ) ) X + ω ( a ) + Tr L / K ( a ) a 0 a 2 a 3 ( a 1 a 4 ) 2 . \begin{aligned}
X={}&\left(\operatorname{Tr}_{L/K}(a)^2+\frac{N_{L/K}(a)}{a_1}\right)\left(\operatorname{Tr}_{L/K}(a)^2+\frac{N_{L/K}(a)}{a_4}\right)s+a_1a_4\operatorname{Tr}_{L/K}(a)^2+N_{L/K}(a)(a_1+a_4),\\
Y={}&\left(\operatorname{Tr}_{L/K}(a)^2+\frac{N_{L/K}(a)}{a_1}\right)\left(\operatorname{Tr}_{L/K}(a)^2+\frac{N_{L/K}(a)}{a_4}\right)v\\
&+(e_2(a)+\operatorname{Tr}_{L/K}(a)(a_1+a_4))X+\omega(a)+\operatorname{Tr}_{L/K}(a)a_0a_2a_3(a_1a_4)^2.
\end{aligned} X = Y = ( Tr L / K ( a ) 2 + a 1 N L / K ( a ) ) ( Tr L / K ( a ) 2 + a 4 N L / K ( a ) ) s + a 1 a 4 Tr L / K ( a ) 2 + N L / K ( a ) ( a 1 + a 4 ) , ( Tr L / K ( a ) 2 + a 1 N L / K ( a ) ) ( Tr L / K ( a ) 2 + a 4 N L / K ( a ) ) v + ( e 2 ( a ) + Tr L / K ( a ) ( a 1 + a 4 )) X + ω ( a ) + Tr L / K ( a ) a 0 a 2 a 3 ( a 1 a 4 ) 2 .
Substituting this into Eq. (17) , using the definitions of e 2 ( a ) e_2(a) e 2 ( a ) , e 3 ( a ) e_3(a) e 3 ( a ) , e 4 ( a ) e_4(a) e 4 ( a ) and ω ( a ) = Tr L / K ( a ) 4 + Tr L / K ( a ) 2 e 4 ( a ) + N L / K ( a ) e 3 ( a ) \omega(a)=\operatorname{Tr}_{L/K}(a)^4+\operatorname{Tr}_{L/K}(a)^2e_4(a)+N_{L/K}(a)e_3(a) ω ( a ) = Tr L / K ( a ) 4 + Tr L / K ( a ) 2 e 4 ( a ) + N L / K ( a ) e 3 ( a ) , gives
Y 2 + ( Tr L / K ( a ) 2 X + N L / K ( a ) 2 ) Y = X 3 + e 2 ( a ) 2 X 2 + ω ( a ) 2 . Y^2+(\operatorname{Tr}_{L/K}(a)^2X+N_{L/K}(a)^2)Y=X^3+e_2(a)^2X^2+\omega(a)^2. Y 2 + ( Tr L / K ( a ) 2 X + N L / K ( a ) 2 ) Y = X 3 + e 2 ( a ) 2 X 2 + ω ( a ) 2 .
This is the equation obtained by squaring every coefficient of
E a : y 2 + ( Tr L / K ( a ) x + N L / K ( a ) ) y = x 3 + e 2 ( a ) x 2 + ω ( a ) . E_a:\qquad y^2+(\operatorname{Tr}_{L/K}(a)x+N_{L/K}(a))y=x^3+e_2(a)x^2+\omega(a). E a : y 2 + ( Tr L / K ( a ) x + N L / K ( a )) y = x 3 + e 2 ( a ) x 2 + ω ( a ) .
Squaring all coefficients in characteristic 2 of course preserves the number of points of a curve, hence the projective cubic in (17) has exactly # E a ( K r ) \#E_a(K_r) # E a ( K r ) points (note that both have exactly one point at infinity).
If a 1 a 4 + Tr L / K ( a ) 2 s = 0 a_1a_4+\operatorname{Tr}_{L/K}(a)^2s=0 a 1 a 4 + Tr L / K ( a ) 2 s = 0 , Eq. (17) has a unique solution in v v v . The number of affine points on E a ( K r ) E_a(K_r) E a ( K r ) is thus exactly
∑ s ∈ K r , a 1 a 4 + Tr L / K ( a ) 2 s ≠ 0 ( 1 + ψ K r ( s + ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) a 1 a 4 + Tr L / K ( a ) 2 s ) ) + ∑ s ∈ K r , a 1 a 4 + Tr L / K ( a ) 2 s = 0 1 = Q + ∑ s ∈ K r , a 1 a 4 + Tr L / K ( a ) 2 s ≠ 0 ψ K r ( s + ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) a 1 a 4 + Tr L / K ( a ) 2 s ) \begin{aligned}
\sum_{\substack{s\in K_r,\\a_1a_4+\operatorname{Tr}_{L/K}(a)^2s\ne0}}
\left(1+\psi_{K_r}\left(s+\frac{(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s)}{a_1a_4+\operatorname{Tr}_{L/K}(a)^2s}\right)\right)
+
\sum_{\substack{s\in K_r,\\a_1a_4+\operatorname{Tr}_{L/K}(a)^2s=0}}1 \\
&=Q+
\sum_{\substack{s\in K_r,\\a_1a_4+\operatorname{Tr}_{L/K}(a)^2s\ne0}}
\psi_{K_r}\left(s+\frac{(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s)}{a_1a_4+\operatorname{Tr}_{L/K}(a)^2s}\right)
\end{aligned} s ∈ K r , a 1 a 4 + Tr L / K ( a ) 2 s = 0 ∑ ( 1 + ψ K r ( s + a 1 a 4 + Tr L / K ( a ) 2 s ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) ) ) + s ∈ K r , a 1 a 4 + Tr L / K ( a ) 2 s = 0 ∑ 1 = Q + s ∈ K r , a 1 a 4 + Tr L / K ( a ) 2 s = 0 ∑ ψ K r ( s + a 1 a 4 + Tr L / K ( a ) 2 s ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) )
Taking the point at infinity into account, we get
# E a ( K r ) − Q − 1 = ∑ s ∈ K r , a 1 a 4 + Tr L / K ( a ) 2 s ≠ 0 ψ K r ( s + ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) a 1 a 4 + Tr L / K ( a ) 2 s ) . \#\mathcal{E}_a(K_r)-Q-1=\sum_{\substack{s\in K_r,\\a_1a_4+\operatorname{Tr}_{L/K}(a)^2s\ne0}}\psi_{K_r}\left(s+\frac{(1+a_0a_3s)(1+a_0a_2s)(1+a_2a_3s)}{a_1a_4+\operatorname{Tr}_{L/K}(a)^2s}\right). # E a ( K r ) − Q − 1 = s ∈ K r , a 1 a 4 + Tr L / K ( a ) 2 s = 0 ∑ ψ K r ( s + a 1 a 4 + Tr L / K ( a ) 2 s ( 1 + a 0 a 3 s ) ( 1 + a 0 a 2 s ) ( 1 + a 2 a 3 s ) ) .
Combining this identity with Eq. (15) , we obtain
S r ( a ) = Q 2 ( # E a ( K r ) − Q − 1 − 5 ψ K r ( ( a 1 a 4 ) − 1 ) ) . S_r(a)=Q^2\left(\#\mathcal{E}_a(K_r)-Q-1-5\psi_{K_r}\left((a_1a_4)^{-1}\right)\right). S r ( a ) = Q 2 ( # E a ( K r ) − Q − 1 − 5 ψ K r ( ( a 1 a 4 ) − 1 ) ) .
The case a = 1 a=1 a = 1 . Now suppose a = 1 a=1 a = 1 , so all a i = 1 a_i=1 a i = 1 and Tr L / K ( a ) = N L / K ( a ) = 1 \operatorname{Tr}_{L/K}(a)=\operatorname{N}_{L/K}(a)=1 Tr L / K ( a ) = N L / K ( a ) = 1 . The conditions in Eq. (9) become
{ ( z 0 + s 2 ) ( z 2 + s 2 ) = s 2 ( 1 + s ) 2 , ( 1 + s ) 2 ( z 0 + z 2 ) = s ( 1 + s ) . \begin{cases}
(z_0+s^2)(z_2+s^2)=s^2(1+s)^2,\\
(1+s)^2(z_0+z_2)=s(1+s).
\end{cases} { ( z 0 + s 2 ) ( z 2 + s 2 ) = s 2 ( 1 + s ) 2 , ( 1 + s ) 2 ( z 0 + z 2 ) = s ( 1 + s ) .
If s = 0 s=0 s = 0 , there is one solution the equations reduce to z 0 z 2 = 0 z_0z_2=0 z 0 z 2 = 0 , z 0 + z 2 = 0 z_0+z_2=0 z 0 + z 2 = 0 , so there is only one solution z 0 = z 2 = 0 z_0=z_2=0 z 0 = z 2 = 0 . If s = 1 s=1 s = 1 , the equations reduce to ( z 0 + 1 ) ( z 2 + 1 ) = 0 (z_0+1)(z_2+1)=0 ( z 0 + 1 ) ( z 2 + 1 ) = 0 , so z 0 = 1 z_0=1 z 0 = 1 or z 2 = 1 z_2=1 z 2 = 1 with the other one chosen arbitrarily. We have thus in this case 2 Q − 1 2Q-1 2 Q − 1 solutions. If s ∉ { 0 , 1 } s\notin\{0,1\} s ∈ / { 0 , 1 } , we have (using the previous notation) s M ≠ 0 sM\ne0 s M = 0 and p b ≠ 0 p_b\ne0 p b = 0 , so by Eq. (10) the number of solutions is 1 + ψ K r ( ( 1 + s ) 2 ) 1+\psi_{K_r}((1+s)^2) 1 + ψ K r (( 1 + s ) 2 ) .
Thus we have in total
∑ s ∈ K r ψ K r ( s ) N s = 1 + ( 2 Q − 1 ) ψ K r ( 1 ) + ∑ s ∈ K r ∖ { 0 , 1 } ( ψ K r ( s ) + ψ K r ( s ) ψ K r ( ( 1 + s ) 2 ) ) = 1 + ( 2 Q − 1 ) ψ K r ( 1 ) + ∑ s ∈ K r ∖ { 0 , 1 } ψ K r ( s ) + ∑ s ∈ K r ∖ { 0 , 1 } ψ K r ( 1 ) = 1 + ( 2 Q − 1 ) ψ K r ( 1 ) − ( 1 + ψ K r ( 1 ) ) + ( Q − 2 ) ψ K r ( 1 ) = ( 3 Q − 4 ) ψ K r ( 1 ) , \begin{aligned}
\sum_{s\in K_r}\psi_{K_r}(s)N_s=1+(2Q-1)\psi_{K_r}(1)+\sum_{s\in K_r\setminus\{0,1\}}\left(\psi_{K_r}(s)+\psi_{K_r}(s)\psi_{K_r}((1+s)^2)\right) \\
&=1+(2Q-1)\psi_{K_r}(1)+\sum_{s\in K_r\setminus\{0,1\}}\psi_{K_r}(s)+\sum_{s\in K_r\setminus\{0,1\}}\psi_{K_r}(1) \\
&=1+(2Q-1)\psi_{K_r}(1)-(1+\psi_{K_r}(1))+(Q-2)\psi_{K_r}(1) \\
&=(3Q-4)\psi_{K_r}(1),
\end{aligned} s ∈ K r ∑ ψ K r ( s ) N s = 1 + ( 2 Q − 1 ) ψ K r ( 1 ) + s ∈ K r ∖ { 0 , 1 } ∑ ( ψ K r ( s ) + ψ K r ( s ) ψ K r (( 1 + s ) 2 ) ) = 1 + ( 2 Q − 1 ) ψ K r ( 1 ) + s ∈ K r ∖ { 0 , 1 } ∑ ψ K r ( s ) + s ∈ K r ∖ { 0 , 1 } ∑ ψ K r ( 1 ) = 1 + ( 2 Q − 1 ) ψ K r ( 1 ) − ( 1 + ψ K r ( 1 )) + ( Q − 2 ) ψ K r ( 1 ) = ( 3 Q − 4 ) ψ K r ( 1 ) ,
using orthogonality.
The case for A = 0 A=0 A = 0 is dealt with in Eq. (14) , so we obtain
S r ( a ) = Q 2 ( ( 3 Q − 4 ) ψ K r ( 1 ) − 2 ψ K r ( 1 ) + Q ψ K r ( 1 ) ) = Q 2 ( 4 Q − 6 ) ψ K r ( 1 ) = ( − 1 ) m r Q 2 ( 4 Q − 6 ) . S_r(a)=Q^2\left((3Q-4)\psi_{K_r}(1)-2\psi_{K_r}(1)+Q\psi_{K_r}(1)\right)=Q^2(4Q-6)\psi_{K_r}(1)=(-1)^{mr}Q^2(4Q-6). S r ( a ) = Q 2 ( ( 3 Q − 4 ) ψ K r ( 1 ) − 2 ψ K r ( 1 ) + Q ψ K r ( 1 ) ) = Q 2 ( 4 Q − 6 ) ψ K r ( 1 ) = ( − 1 ) m r Q 2 ( 4 Q − 6 ) .
The corresponding elliptic curve
Let a ∈ L × a\in L^\times a ∈ L × be fixed. Write (compare Eq. (1) )
f a ( X , Y ) = Y 2 + ( Tr L / K ( a ) X + N L / K ( a ) ) Y + X 3 + e 2 ( a ) X 2 + ω ( a ) . f_a(X,Y)=Y^2+(\operatorname{Tr}_{L/K}(a)X+\operatorname{N}_{L/K}(a))Y+X^3+e_2(a)X^2+\omega(a). f a ( X , Y ) = Y 2 + ( Tr L / K ( a ) X + N L / K ( a )) Y + X 3 + e 2 ( a ) X 2 + ω ( a ) .
The corresponding homogeneous polynomial is
F a ( X , Y , Z ) = Y 2 Z + ( Tr L / K ( a ) X + N L / K ( a ) Z ) Y Z + X 3 + e 2 ( a ) X 2 Z + ω ( a ) Z 3 . F_a(X,Y,Z)=Y^2Z+(\operatorname{Tr}_{L/K}(a)X+\operatorname{N}_{L/K}(a)Z)YZ+X^3+e_2(a)X^2Z+\omega(a)Z^3. F a ( X , Y , Z ) = Y 2 Z + ( Tr L / K ( a ) X + N L / K ( a ) Z ) Y Z + X 3 + e 2 ( a ) X 2 Z + ω ( a ) Z 3 .
Proposition 6.1. The projective cubic variety V V V defined by the equation F a ( X , Y , Z ) = 0 F_a(X,Y,Z)=0 F a ( X , Y , Z ) = 0 is nonsingular for any a ∈ L ∖ { 0 , 1 } a\in L\setminus\{0,1\} a ∈ L ∖ { 0 , 1 } .
Proof. At Z = 0 Z=0 Z = 0 it has just the point O = [ 0 : 1 : 0 ] O=[0:1:0] O = [ 0 : 1 : 0 ] . We have the partial derivatives
∂ F a ∂ X = Tr L / K ( a ) Y Z + X 2 , ∂ F a ∂ Y = Tr L / K ( a ) X Z + N L / K ( a ) Z 2 , ∂ F a ∂ Z = Y 2 + Tr L / K ( a ) X Y + e 2 ( a ) X 2 + ω ( a ) . \frac{\partial F_a}{\partial X}=\operatorname{Tr}_{L/K}(a)YZ+X^2,\qquad
\frac{\partial F_a}{\partial Y}=\operatorname{Tr}_{L/K}(a)XZ+\operatorname{N}_{L/K}(a)Z^2,\qquad
\frac{\partial F_a}{\partial Z}=Y^2+\operatorname{Tr}_{L/K}(a)XY+e_2(a)X^2+\omega(a). ∂ X ∂ F a = Tr L / K ( a ) Y Z + X 2 , ∂ Y ∂ F a = Tr L / K ( a ) X Z + N L / K ( a ) Z 2 , ∂ Z ∂ F a = Y 2 + Tr L / K ( a ) X Y + e 2 ( a ) X 2 + ω ( a ) .
At O = [ 0 : 1 : 0 ] O=[0:1:0] O = [ 0 : 1 : 0 ] , the partial derivative ∂ F a ∂ Z \frac{\partial F_a}{\partial Z} ∂ Z ∂ F a clearly does not vanish, so O O O is nonsingular. So let us check the affine points (i.e., via scaling, we may choose Z = 1 Z=1 Z = 1 ). If Tr L / K ( a ) = 0 \operatorname{Tr}_{L/K}(a)=0 Tr L / K ( a ) = 0 then ∂ F a ∂ Y \frac{\partial F_a}{\partial Y} ∂ Y ∂ F a does not vanish because N L / K ( a ) ≠ 0 \operatorname{N}_{L/K}(a)\ne0 N L / K ( a ) = 0 . If Tr L / K ( a ) ≠ 0 \operatorname{Tr}_{L/K}(a) \ne0 Tr L / K ( a ) = 0 and ∂ F a ∂ X ( X , Y , 1 ) = ∂ F a ∂ Y ( X , Y , 1 ) = 0 \frac{\partial F_a}{\partial X}(X,Y,1)=\frac{\partial F_a}{\partial Y}(X,Y,1)=0 ∂ X ∂ F a ( X , Y , 1 ) = ∂ Y ∂ F a ( X , Y , 1 ) = 0 then X = N L / K ( a ) Tr L / K ( a ) X=\frac{N_{L/K}(a)}{\operatorname{Tr}_{L/K}(a)} X = Tr L / K ( a ) N L / K ( a ) and Y = N L / K ( a ) 2 Tr L / K ( a ) 3 Y=\frac{N_{L/K}(a)^2}{\operatorname{Tr}_{L/K}(a)^3} Y = Tr L / K ( a ) 3 N L / K ( a ) 2 . For these choices of X , Y X,Y X , Y we have
F_a(X,Y,1)=f_a(X,Y)=\frac{N_{L/K}(a)^4}{\operatorname{Tr}_{L/K}(a)^6}+\frac{N_{L/K}(a)^3}{\operatorname{Tr}_{L/K}(a)^3}+e_2(a)\frac{N_{L/K}(a)^2}{\operatorname{Tr}_{L/K}(a)^2}+\omega(a)=\frac{N_{L/K}(a)^4+N_{L/K}(a)^3\operatorname{Tr}_{L/K}(a)}
It is thus enough to show that the numerator does not vanish. We have
N L / K ( a ) 4 + N L / K ( a ) 3 Tr L / K ( a ) 3 + e 2 ( a ) N L / K ( a ) 2 Tr L / K ( a ) 4 + ω ( a ) Tr L / K ( a ) 6 = N L / K ( a ) 4 + N L / K ( a ) 3 Tr L / K ( a ) = 1 N L / K ( a ) ∏ i = 0 4 ( N L / K ( a ) + Tr L / K ( a ) 2 a i ) \begin{aligned}
N_{L/K}(a)^4+N_{L/K}(a)^3\operatorname{Tr}_{L/K}(a)^3+e_2(a)N_{L/K}(a)^2\operatorname{Tr}_{L/K}(a)^4+\omega(a)\operatorname{Tr}_{L/K}(a)^6=N_{L/K}(a)^4+N_{L/K}(a)^3\operatorname{Tr}_{L/K}(a) \\
&=\frac{1}{N_{L/K}(a)}\prod_{i=0}^{4}\left(N_{L/K}(a)+\operatorname{Tr}_{L/K}(a)^2a_i\right)
\end{aligned} N L / K ( a ) 4 + N L / K ( a ) 3 Tr L / K ( a ) 3 + e 2 ( a ) N L / K ( a ) 2 Tr L / K ( a ) 4 + ω ( a ) Tr L / K ( a ) 6 = N L / K ( a ) 4 + N L / K ( a ) 3 Tr L / K ( a ) = N L / K ( a ) 1 i = 0 ∏ 4 ( N L / K ( a ) + Tr L / K ( a ) 2 a i )
where we use ω ( a ) = Tr L / K ( a ) 4 + Tr L / K ( a ) 2 e 4 ( a ) + N L / K ( a ) e 3 ( a ) \omega(a)=\operatorname{Tr}_{L/K}(a)^4+\operatorname{Tr}_{L/K}(a)^2e_4(a)+N_{L/K}(a)e_3(a) ω ( a ) = Tr L / K ( a ) 4 + Tr L / K ( a ) 2 e 4 ( a ) + N L / K ( a ) e 3 ( a ) , e 1 ( a ) = Tr L / K ( a ) e_1(a)=\operatorname{Tr}_{L/K}(a) e 1 ( a ) = Tr L / K ( a ) , e 5 ( a ) = N L / K ( a ) e_5(a)=N_{L/K}(a) e 5 ( a ) = N L / K ( a ) , and ∏ i a i = N L / K ( a ) \prod_i a_i=N_{L/K}(a) ∏ i a i = N L / K ( a ) . By Lemma 3.2, N L / K ( a ) + Tr L / K ( a ) 2 a i ≠ 0 N_{L/K}(a)+\operatorname{Tr}_{L/K}(a)^2a_i\ne0 N L / K ( a ) + Tr L / K ( a ) 2 a i = 0 if a ∉ { 0 , 1 } a\notin\{0,1\} a ∈ / { 0 , 1 } , so the term cannot vanish, proving that V V V has no singular point in these cases. □
A nonsingular projective cubic variety has genus one, and the point O O O makes it an elliptic curve over K K K , see [23 Proposition III.3.1(c)] , which is exactly the curve given in Eq. (1) :
E a : Y 2 + ( Tr L / K ( a ) X + N L / K ( a ) ) Y = X 3 + e 2 ( a ) X 2 + ω ( a ) , \mathcal{E}_a:\quad Y^2+\left(\operatorname{Tr}_{L/K}(a)X+N_{L/K}(a)\right)Y=X^3+e_2(a)X^2+\omega(a), E a : Y 2 + ( Tr L / K ( a ) X + N L / K ( a ) ) Y = X 3 + e 2 ( a ) X 2 + ω ( a ) ,
as long as a ≠ 1 a\ne1 a = 1 . So let for now a ∈ L ∖ { 0 , 1 } a\in L\setminus\{0,1\} a ∈ L ∖ { 0 , 1 } . For any finite extension K r / K K_r/K K r / K , write
C r ( a ) = # E a ( K r ) − ∣ K r ∣ − 1 (18) C_r(a)=\#\mathcal{E}_a(K_r)-|K_r|-1 \tag*{(18)} C r ( a ) = # E a ( K r ) − ∣ K r ∣ − 1 (18)
where # E a ( K r ) \#\mathcal{E}_a(K_r) # E a ( K r ) denotes the number of K r K_r K r -rational points of E a \mathcal{E}_a E a .
For a = 1 a=1 a = 1 we are not able to use the connection to the elliptic curve as in this case the projective variety is singular. Instead, we simply define directly
C r ( 1 ) = ( − 1 ) r m + 1 ( q r + 1 ) . (19) C_r(1)=(-1)^{rm+1}(q^r+1). \tag*{(19)} C r ( 1 ) = ( − 1 ) r m + 1 ( q r + 1 ) . (19)
Theorem 6.2. For every a ∈ L × a\in L^\times a ∈ L × , there exist α , β ∈ C \alpha,\beta\in\mathbb{C} α , β ∈ C such that, for every r ≥ 1 r\ge1 r ≥ 1 ,
C r ( a ) = − α r − β r , α + β = − C 1 ( a ) ∈ Z , α β = q . C_r(a)=-\alpha^r-\beta^r,\qquad\alpha+\beta=-C_1(a)\in\mathbb{Z},\qquad\alpha\beta=q. C r ( a ) = − α r − β r , α + β = − C 1 ( a ) ∈ Z , α β = q . Consequently,
C r ( a ) 2 + C 2 r ( a ) = ( α r + β r ) 2 − α 2 r − β 2 r = 2 ( α β ) r = 2 q r . C_r(a)^2+C_{2r}(a)=(\alpha^r+\beta^r)^2-\alpha^{2r}-\beta^{2r}=2(\alpha\beta)^r=2q^r. C r ( a ) 2 + C 2 r ( a ) = ( α r + β r ) 2 − α 2 r − β 2 r = 2 ( α β ) r = 2 q r . Proof. For a ≠ 1 a\ne1 a = 1 , this follows from the standard theory of the zeta functions of elliptic curves, see e.g [23 Theorem V.2.3.1(a)] . For a = 1 a=1 a = 1 , we can find α = ( − 1 ) m q \alpha=(-1)^mq α = ( − 1 ) m q and β = ( − 1 ) m \beta=(-1)^m β = ( − 1 ) m directly. □
Investigating the exponential sum over extension fields
In this section, we establish a relation for the sums S r ( a ) S_r(a) S r ( a ) through the application of Dwork’s theorem. Outside of Dwork’s theorem itself (we refer to both Dwork’s original work [11 ] as well as the standard reference [18 ] ), we will explain all necessary (mostly standard) steps for the convenience of potential readers that are not familiar with these techniques. Dwork’s rationality theorem (we will use the version found in [18 Theorem on p. 113] ) states that, for an affine hypersurface V V V over K K K , its zeta function can be expressed as a rational function, namely,
Z V ( T ) = exp ( ∑ r ≥ 1 # V ( K r ) T r r ) = P ( T ) Q ( T ) , Z_V(T)=\exp\left(\sum_{r\ge1}\#V(K_r)\frac{T^r}{r}\right)=\frac{P(T)}{Q(T)}, Z V ( T ) = exp ( r ≥ 1 ∑ # V ( K r ) r T r ) = Q ( T ) P ( T ) ,
where P , Q ∈ Z [ T ] P,Q\in\mathbb{Z}[T] P , Q ∈ Z [ T ] with P ( 0 ) = Q ( 0 ) = 1 P(0)=Q(0)=1 P ( 0 ) = Q ( 0 ) = 1 . Here # V ( K r ) \#V(K_r) # V ( K r ) is the number of K r K_r K r -rational points of V V V . The following proposition is then fairly standard to prove, see e.g. [18 Exercise 6, p. 115] for a similar variant.
Proposition 7.1. There exist finitely many γ 1 , … , γ k ∈ C ∖ { 0 } \gamma_1,\ldots,\gamma_k \in\mathbb{C} \setminus\{0\} γ 1 , … , γ k ∈ C ∖ { 0 } , m 1 , … , m k ∈ Z m_1,\ldots,m_k \in\mathbb{Z} m 1 , … , m k ∈ Z such that
S r ( a ) = ∑ i = 1 k m i γ i r , S_r(a)=\sum_{i=1}^{k}m_i\gamma_i^r, S r ( a ) = i = 1 ∑ k m i γ i r , for every $r \ge 1.
Proof. We define the hypersurface
V a : w 2 + w = P a ( X 0 , … , X 4 ) V_a:\quad w^2+w=P_a(X_0,\ldots,X_4) V a : w 2 + w = P a ( X 0 , … , X 4 )
over K K K , where P a P_a P a is defined in Eq. (2) . For each ( X 0 , … , X 4 ) ∈ K r 5 (X_0,\ldots,X_4) \in K_r^5 ( X 0 , … , X 4 ) ∈ K r 5 , the equation w 2 + w = P a ( X 0 , … , X 4 ) w^2+w=P_a(X_0,\ldots,X_4) w 2 + w = P a ( X 0 , … , X 4 ) has exactly 1 + ψ K r ( P a ( X 0 , … , X 4 ) ) 1+\psi_{K_r}(P_a(X_0,\ldots,X_4)) 1 + ψ K r ( P a ( X 0 , … , X 4 )) solutions, so the total number of K r K_r K r -rational points on V a V_a V a is
# V a ( K r ) = ∑ X 0 , … , X 4 ∈ K r ( 1 + ψ K r ( P a ( X 0 , … , X 4 ) ) ) = q 5 r + S r ( a ) , \begin{aligned}
\#V_a(K_r)=\sum_{X_0,\ldots,X_4\in K_r}\left(1+\psi_{K_r}(P_a(X_0,\ldots,X_4))\right) \\
&=q^{5r}+S_r(a),
\end{aligned} # V a ( K r ) = X 0 , … , X 4 ∈ K r ∑ ( 1 + ψ K r ( P a ( X 0 , … , X 4 )) ) = q 5 r + S r ( a ) ,
by the definition of S r ( a ) S_r(a) S r ( a ) in Eq. (3) .
We now apply Dwork’s theorem to the zeta function of V a V_a V a . Write Z V a ( T ) = P ( T ) / Q ( T ) Z_{V_a}(T)=P(T)/Q(T) Z V a ( T ) = P ( T ) / Q ( T ) . We factor both P P P and Q Q Q in linear factors of the form ( 1 − λ T ) (1-\lambda T) ( 1 − λ T ) with λ ∈ C ∖ { 0 } \lambda\in\mathbb{C}\setminus\{0\} λ ∈ C ∖ { 0 } . Collecting all these factors of both P P P and Q Q Q gives a product
Z V a ( T ) = ∏ λ ( 1 − λ T ) − m λ , Z_{V_a}(T)=\prod_{\lambda}(1-\lambda T)^{-m_\lambda}, Z V a ( T ) = λ ∏ ( 1 − λ T ) − m λ ,
with finitely many nonzero λ \lambda λ . Here m λ ∈ Z m_\lambda\in\mathbb{Z} m λ ∈ Z is the multiplicity of the factor 1 − λ T 1-\lambda T 1 − λ T in Q Q Q minus its multiplicity in P P P . Using the formal power series yields − log ( 1 − λ T ) = ∑ r ≥ 1 λ r T r r -\log(1-\lambda T)=\sum_{r\geq1}\lambda^r\frac{T^r}{r} − log ( 1 − λ T ) = ∑ r ≥ 1 λ r r T r , so
log Z V a ( T ) = − ∑ λ m λ log ( 1 − λ T ) = ∑ r ≥ 1 ( ∑ λ m λ λ r ) T r r . \begin{aligned}
\log Z_{V_a}(T)=-\sum_{\lambda}m_\lambda\log(1-\lambda T) \\
&=\sum_{r\geq1}\left(\sum_{\lambda}m_\lambda\lambda^r\right)\frac{T^r}{r}.
\end{aligned} log Z V a ( T ) = − λ ∑ m λ log ( 1 − λ T ) = r ≥ 1 ∑ ( λ ∑ m λ λ r ) r T r .
On the other hand, by the definition of the zeta function,
log Z V a ( T ) = ∑ r ≥ 1 # V a ( K r ) T r r = ∑ r ≥ 1 ( q 5 r + S r ( a ) ) T r r . \begin{aligned}
\log Z_{V_a}(T)=\sum_{r\geq1}\#V_a(K_r)\frac{T^r}{r} \\
&=\sum_{r\geq1}(q^{5r}+S_r(a))\frac{T^r}{r}.
\end{aligned} log Z V a ( T ) = r ≥ 1 ∑ # V a ( K r ) r T r = r ≥ 1 ∑ ( q 5 r + S r ( a )) r T r .
Comparing coefficients therefore yields
q 5 r + S r ( a ) = ∑ λ m λ λ r . q^{5r}+S_r(a)=\sum_{\lambda}m_\lambda\lambda^r. q 5 r + S r ( a ) = λ ∑ m λ λ r .
Of course q 5 r q^{5r} q 5 r can itself be written as m λ λ r m_\lambda\lambda^r m λ λ r by picking λ = q 5 \lambda=q^5 λ = q 5 , proving the statement. □
We now remove the additional terms in Proposition 5.2 from the extension sums S r ( a ) S_r(a) S r ( a ) . Define
A r ( a ) = { − S r ( a ) , 5 ∤ r , − S r ( a ) − 5 q 2 r ψ K r ( ( a 1 a 4 ) − 1 ) , 5 ∣ r , a ≠ 1 , − S r ( a ) + 5 q 2 r ( q r − 1 ) ( − 1 ) m r , 5 ∣ r , a = 1. (20) A_r(a)=
\begin{cases}
-S_r(a), & 5\nmid r,\\
-S_r(a)-5q^{2r}\psi_{K_r}\left((a_1a_4)^{-1}\right), & 5\mid r,\ a\ne1,\\
-S_r(a)+5q^{2r}(q^r-1)(-1)^{mr}, & 5\mid r,\ a=1.
\end{cases} \tag*{(20)} A r ( a ) = ⎩ ⎨ ⎧ − S r ( a ) , − S r ( a ) − 5 q 2 r ψ K r ( ( a 1 a 4 ) − 1 ) , − S r ( a ) + 5 q 2 r ( q r − 1 ) ( − 1 ) m r , 5 ∤ r , 5 ∣ r , a = 1 , 5 ∣ r , a = 1. (20)
By Proposition 5.2, Eq. (18) and Eq. (19) , these corrections give A r ( a ) = − q 2 r C r ( a ) A_r(a)=-q^{2r}C_r(a) A r ( a ) = − q 2 r C r ( a ) if 5 ∣ r 5\mid r 5 ∣ r . Consequently, Theorem 6.2 gives for all r ≥ 1 r\ge1 r ≥ 1
A 5 r ( a ) = ( q 2 α ) 5 r + ( q 2 β ) 5 r (21) A_{5r}(a)=(q^2\alpha)^{5r}+(q^2\beta)^{5r} \tag*{(21)} A 5 r ( a ) = ( q 2 α ) 5 r + ( q 2 β ) 5 r (21)
We will use this subsequence of the sequence of A r ( a ) A_r(a) A r ( a ) to determine A 1 ( a ) A_1(a) A 1 ( a ) and thus S 1 ( a ) S_1(a) S 1 ( a ) , which is precisely the Dobbertin APN exponential sum. More precisely, our goal is to prove A 1 ( a ) = − q 2 C 1 ( a ) A_1(a)=-q^2C_1(a) A 1 ( a ) = − q 2 C 1 ( a ) , which gives S 1 ( a ) = q 2 C 1 ( a ) S_1(a)=q^2C_1(a) S 1 ( a ) = q 2 C 1 ( a ) . The first step is to show that the correction preserves the finite representation supplied by Dwork’s theorem in Proposition 7.1 .
Proposition 7.2. The sequence ( A r ( a ) ) r ≥ 1 (A_r(a))_{r\ge1} ( A r ( a ) ) r ≥ 1 is integer-valued and there exist finitely many γ 1 , … , γ k ∈ C ∖ { 0 } \gamma_1,\ldots,\gamma_k\in\mathbb{C}\setminus\{0\} γ 1 , … , γ k ∈ C ∖ { 0 } , m 1 , … , m k ∈ Z m_1,\ldots,m_k\in\mathbb{Z} m 1 , … , m k ∈ Z such that
A r ( a ) = ∑ i = 1 k m i γ i r (22) A_r(a)=\sum_{i=1}^{k}m_i\gamma_i^r \tag*{(22)} A r ( a ) = i = 1 ∑ k m i γ i r (22) where additionally
∑ i = 1 k m i = 2. (23) \sum_{i=1}^{k}m_i=2. \tag*{(23)} i = 1 ∑ k m i = 2. (23)
Proof. The integrality of the sequence follows directly by the definition in Eq. (20) . Proposition 7.1 gives a finite power-sum representation for S r ( a ) S_r(a) S r ( a ) , and hence also for − S r ( a ) -S_r(a) − S r ( a ) , say
− S r ( a ) = ∑ i = 1 l t i γ i r (24) -S_r(a)=\sum_{i=1}^{l}t_i\gamma_i^r \tag*{(24)} − S r ( a ) = i = 1 ∑ l t i γ i r (24)
where t i ∈ Z t_i\in\mathbb{Z} t i ∈ Z .
Put
χ = ψ L ( ( a 1 a 4 ) − 1 ) . \chi=\psi_L\left((a_1a_4)^{-1}\right). χ = ψ L ( ( a 1 a 4 ) − 1 ) .
If r = 5 h r=5h r = 5 h , trace transitivity gives
ψ K r ( ( a 1 a 4 ) − 1 ) = χ h = χ r , \psi_{K_r}\left((a_1a_4)^{-1}\right)=\chi^h=\chi^r, ψ K r ( ( a 1 a 4 ) − 1 ) = χ h = χ r ,
because χ ∈ { 1 , − 1 } \chi\in\{1,-1\} χ ∈ { 1 , − 1 } and h , r h,r h , r have the same parity. Thus the definition of A r ( a ) A_r(a) A r ( a ) in Eq. (20) gives
A r ( a ) + S r ( a ) = { − 5 ( q 2 χ ) r , 5 ∣ r , a ≠ 1 , 5 ( ( q 3 ( − 1 ) m ) r − ( q 2 ( − 1 ) m ) r ) , 5 ∣ r , a = 1 , 0 , 5 ∤ r . (25) A_r(a)+S_r(a)=
\begin{cases}
-5(q^2\chi)^r, & 5\mid r,\ a\ne1,\\
5\left((q^3(-1)^m)^r-(q^2(-1)^m)^r\right), & 5\mid r,\ a=1,\\
0, & 5\nmid r.
\end{cases} \tag*{(25)} A r ( a ) + S r ( a ) = ⎩ ⎨ ⎧ − 5 ( q 2 χ ) r , 5 ( ( q 3 ( − 1 ) m ) r − ( q 2 ( − 1 ) m ) r ) , 0 , 5 ∣ r , a = 1 , 5 ∣ r , a = 1 , 5 ∤ r . (25)
Let ζ \zeta ζ be a primitive complex fifth root of unity. Then, for every z ∈ C × z\in\mathbb{C}^{\times} z ∈ C × ,
∑ j = 0 4 ( z ζ j ) r = { 5 z r , 5 ∣ r , 0 , else . \sum_{j=0}^{4}(z\zeta^j)^r=
\begin{cases}
5z^r, & 5\mid r,\\
0, & \text{else}.
\end{cases} j = 0 ∑ 4 ( z ζ j ) r = { 5 z r , 0 , 5 ∣ r , else .
Applying this identity with z = q 2 χ z=q^2\chi z = q 2 χ in the first case of Eq. (25) , and using both z = q 3 ( − 1 ) m z=q^3(-1)^m z = q 3 ( − 1 ) m and z = q 2 ( − 1 ) m z=q^2(-1)^m z = q 2 ( − 1 ) m in the second, shows that both additions in Eq. (25) are finite power sums with integer multiplicities. This together with Eq. (24) proves the first statement of the proposition asserted in Eq. (22) .
It remains to prove Eq. (23) . Combining Eq. (22) with Eq. (21) gives for A 5 r ( a ) A_{5r}(a) A 5 r ( a )
A 5 r ( a ) = ∑ i = 1 k m i ( γ i 5 ) r = ( ( q 2 α ) 5 ) r + ( ( q 2 β ) 5 ) r A_{5r}(a)=\sum_{i=1}^{k}m_i(\gamma_i^5)^r=((q^2\alpha)^5)^r+((q^2\beta)^5)^r A 5 r ( a ) = i = 1 ∑ k m i ( γ i 5 ) r = (( q 2 α ) 5 ) r + (( q 2 β ) 5 ) r
for all r ≥ 1 r\ge1 r ≥ 1 . Group bases with the same fifth power by writing
M δ = ∑ i ∈ { 1 , … , k } γ i 5 = δ m i , M_\delta=\sum_{\substack{i\in\{1,\ldots,k\}\\ \gamma_i^5=\delta}}m_i, M δ = i ∈ { 1 , … , k } γ i 5 = δ ∑ m i ,
so the previous equation becomes
∑ δ ∈ Δ M δ δ r = ( ( q 2 α ) 5 ) r + ( ( q 2 β ) 5 ) r , \sum_{\delta\in\Delta} M_\delta\delta^r = \left((q^2\alpha)^5\right)^r+\left((q^2\beta)^5\right)^r, δ ∈ Δ ∑ M δ δ r = ( ( q 2 α ) 5 ) r + ( ( q 2 β ) 5 ) r ,
for all r ≥ 1 r\ge1 r ≥ 1 where Δ ⊆ C × \Delta\subseteq\mathbb{C}^{\times} Δ ⊆ C × is a finite set.
Recall that distinct nonzero power sequences are linearly independent which follows from the invertibility of the Vandermonde matrix. Comparing coefficients therefore gives M ( q 2 α ) 5 = M ( q 2 β ) 5 = 1 M_{(q^2\alpha)^5}=M_{(q^2\beta)^5}=1 M ( q 2 α ) 5 = M ( q 2 β ) 5 = 1 and M δ = 0 M_\delta=0 M δ = 0 for all other δ \delta δ (in the special case α = β \alpha=\beta α = β we have of course M ( q 2 α ) 5 = 2 M_{(q^2\alpha)^5}=2 M ( q 2 α ) 5 = 2 and all other M δ = 0 M_\delta=0 M δ = 0 ). Summing over the finitely many bases on either side yields
∑ i = 1 k m i = ∑ δ ∈ Δ M δ = 2. \sum_{i=1}^{k}m_i=\sum_{\delta\in\Delta}M_\delta=2. i = 1 ∑ k m i = δ ∈ Δ ∑ M δ = 2.
The subsequence has therefore determined the total multiplicity of the entire sequence. We now use the identity of the Walsh transform of the Dobbertin function we obtained in Lemma 4.1 to relate the values of A r \mathcal{A}_r A r at indices r r r and 2 r 2r 2 r .
Proposition 7.3. For every r ≥ 1 r\ge1 r ≥ 1 ,
A r ( a ) 2 − A 2 r ( a ) = 2 q 5 r . (26) \mathcal{A}_r(a)^2-\mathcal{A}_{2r}(a)=2q^{5r}. \tag*{(26)} A r ( a ) 2 − A 2 r ( a ) = 2 q 5 r . (26)
Proof. If 5 ∤ r 5\nmid r 5 ∤ r , then 5 ∤ 2 r 5\nmid2r 5 ∤ 2 r as well. Hence Eq. (20) , Proposition 5.1 , and Lemma 4.1 give in this case
A r ( a ) 2 − A 2 r ( a ) = S r ( a ) 2 + S 2 r ( a ) = W q r ( a ) 2 + W q 2 r ( a ) = 2 q 5 r . \mathcal{A}_r(a)^2-\mathcal{A}_{2r}(a)=S_r(a)^2+S_{2r}(a)=W_{q^r}(a)^2+W_{q^{2r}}(a)=2q^{5r}. A r ( a ) 2 − A 2 r ( a ) = S r ( a ) 2 + S 2 r ( a ) = W q r ( a ) 2 + W q 2 r ( a ) = 2 q 5 r .
If 5 ∣ r 5\mid r 5 ∣ r , then, by the definitions given in Eq. (20) , Eq. (18) and Eq. (19) , we have A r ( a ) = − q 2 r C r ( a ) \mathcal{A}_r(a)=-q^{2r}C_r(a) A r ( a ) = − q 2 r C r ( a ) and A 2 r ( a ) = − q 4 r C 2 r ( a ) \mathcal{A}_{2r}(a)=-q^{4r}C_{2r}(a) A 2 r ( a ) = − q 4 r C 2 r ( a ) . Theorem 6.2 therefore gives
A r ( a ) 2 − A 2 r ( a ) = q 4 r ( C r ( a ) 2 + C 2 r ( a ) ) = 2 q 5 r . \mathcal{A}_r(a)^2-\mathcal{A}_{2r}(a)=q^{4r}\left(C_r(a)^2+C_{2r}(a)\right)=2q^{5r}. A r ( a ) 2 − A 2 r ( a ) = q 4 r ( C r ( a ) 2 + C 2 r ( a ) ) = 2 q 5 r .
We now know that A r ( a ) \mathcal{A}_r(a) A r ( a ) is a finite power sum with total multiplicity two that satisfies Eq. (26) . The following lemma shows that the doubling identity forces a representation akin to the one given in Theorem 6.2 for the elliptic curve.
Lemma 7.4. Let Q > 0 Q>0 Q > 0 be real. Suppose a real sequence ( b r ) r ≥ 1 (b_r)_{r\ge1} ( b r ) r ≥ 1 has a representation
b r = ∑ i = 1 k m i γ i r , b_r=\sum_{i=1}^{k}m_i\gamma_i^r, b r = i = 1 ∑ k m i γ i r , where m i ∈ Z m_i\in\mathbb{Z} m i ∈ Z , γ i ∈ C × \gamma_i\in\mathbb{C}^{\times} γ i ∈ C × , ∑ i = 1 k m i = 2 \sum_{i=1}^{k}m_i=2 ∑ i = 1 k m i = 2 . If
b r 2 − b 2 r = 2 Q r (27) b_r^2-b_{2r}=2Q^r \tag*{(27)} b r 2 − b 2 r = 2 Q r (27) for all r ≥ 1 r\ge1 r ≥ 1 then there exist u , v ∈ C × u,v\in\mathbb{C}^{\times} u , v ∈ C × such that b r = u r + v r b_r=u^r+v^r b r = u r + v r and u v = Q uv=Q uv = Q .
Proof. Without loss of generality assume that all m i ≠ 0 m_i\ne0 m i = 0 and all γ i \gamma_i γ i are distinct. By linear independence of distinct nonzero power sequences, we can compare coefficient-wise. Since the b r b_r b r are real, conjugate γ i \gamma_i γ i must have equal multiplicities m i m_i m i . Expanding Eq. (27) yields
∑ i , j ∈ { 1 , … , k } m i m j ( γ i γ j ) r − ∑ i = 1 k m i ( γ i 2 ) r − 2 Q r = ∑ γ ′ n γ ′ ( γ ′ ) r = 0 (28) \sum_{i,j\in\{1,\ldots,k\}}m_im_j(\gamma_i\gamma_j)^r-\sum_{i=1}^{k}m_i(\gamma_i^2)^r-2Q^r=\sum_{\gamma'}n_{\gamma'}(\gamma')^r=0 \tag*{(28)} i , j ∈ { 1 , … , k } ∑ m i m j ( γ i γ j ) r − i = 1 ∑ k m i ( γ i 2 ) r − 2 Q r = γ ′ ∑ n γ ′ ( γ ′ ) r = 0 (28)
for all r ≥ 1 r \ge1 r ≥ 1 , where the γ ′ \gamma' γ ′ collect all combinations of γ i 2 \gamma_i^2 γ i 2 , γ i γ j \gamma_i\gamma_j γ i γ j and Q Q Q . Since this equation holds for all r ≥ 1 r \ge1 r ≥ 1 , we have that all n γ ′ = 0 n_{\gamma'}=0 n γ ′ = 0 . Set R = max i ∣ γ i ∣ R=\max_i|\gamma_i| R = max i ∣ γ i ∣ . We consider the coefficient n γ ′ n_{\gamma'} n γ ′ in this equation for γ ′ = R 2 \gamma'=R^2 γ ′ = R 2 . Write the nonreal conjugate pairs of absolute value R R R as
{ z 1 , z ‾ 1 } , … , { z t , z ‾ t } , \{z_1,\overline{z}_1\},\ldots,\{z_t,\overline{z}_t\}, { z 1 , z 1 } , … , { z t , z t } ,
and recall that m z j = m z ‾ j m_{z_j}=m_{\overline{z}_j} m z j = m z j . The contributions to n γ ′ n_{\gamma'} n γ ′ are then m R m_R m R , m − R m_{-R} m − R (both can possibly be 0 of course), m z j m_{z_j} m z j for 1 ≤ j ≤ t 1\le j\le t 1 ≤ j ≤ t and, if R = Q R=\sqrt{Q} R = Q , an additional term of − 2 -2 − 2 . So
0 = n R 2 = m R 2 + m − R 2 + 2 ∑ j = 1 t m z j 2 − m R − m − R = m R ( m R − 1 ) + m − R ( m − R − 1 ) + 2 ∑ j = 1 t m z j 2 . (29) 0=n_{R^2}=m_R^2+m_{-R}^2+2\sum_{j=1}^{t}m_{z_j}^2-m_R-m_{-R}=m_R(m_R-1)+m_{-R}(m_{-R}-1)+2\sum_{j=1}^{t}m_{z_j}^2. \tag*{(29)} 0 = n R 2 = m R 2 + m − R 2 + 2 j = 1 ∑ t m z j 2 − m R − m − R = m R ( m R − 1 ) + m − R ( m − R − 1 ) + 2 j = 1 ∑ t m z j 2 . (29)
with an additional term of − 2 -2 − 2 if R = Q R=\sqrt{Q} R = Q . Suppose first that R < Q R<\sqrt{Q} R < Q . By definition of R R R we have ∣ γ i ∣ ≤ R |\gamma_i|\le R ∣ γ i ∣ ≤ R . Therefore ∣ γ i γ j ∣ ≤ R 2 < Q |\gamma_i\gamma_j|\le R^2<Q ∣ γ i γ j ∣ ≤ R 2 < Q for all choices of i , j i,j i , j . So n Q = − 2 n_Q=-2 n Q = − 2 , since the contributions in Eq. (28) of the terms − 2 Q r -2Q^r − 2 Q r cannot be canceled, contradicting that all n γ ′ = 0 n_{\gamma'}=0 n γ ′ = 0 .
Suppose now that R > Q R>\sqrt{Q} R > Q . Then the right hand side of Eq. (29) has to vanish, so m z j = 0 m_{z_j}=0 m z j = 0 for all j j j and m R , m − R ∈ { 0 , 1 } m_R,m_{-R}\in\{0,1\} m R , m − R ∈ { 0 , 1 } . Consider Eq. (28) again but now look at the coefficient n − R 2 n_{-R^2} n − R 2 . We get
0 = n − R 2 = 2 m R m − R . 0=n_{-R^2}=2m_Rm_{-R}. 0 = n − R 2 = 2 m R m − R .
So m R = m − R = 1 m_R=m_{-R}=1 m R = m − R = 1 is impossible. Clearly, m R = m − R = 0 m_R=m_{-R}=0 m R = m − R = 0 is impossible since R = max i ∣ γ i ∣ R=\max_i|\gamma_i| R = max i ∣ γ i ∣ . So the only possibility left is m R = 1 m_R=1 m R = 1 , m − R = 0 m_{-R}=0 m − R = 0 or m R = 0 m_R=0 m R = 0 , m − R = 1 m_{-R}=1 m − R = 1 . Set z z z as R R R or − R -R − R depending on which of m R m_R m R and m − R m_{-R} m − R are 1. Set
V r = b r − z r − ( Q / z ) r = ∑ i = 1 k m i γ i r − z r − ( Q / z ) r . V_r=b_r-z^r-(Q/z)^r=\sum_{i=1}^{k}m_i\gamma_i^r-z^r-(Q/z)^r. V r = b r − z r − ( Q / z ) r = i = 1 ∑ k m i γ i r − z r − ( Q / z ) r .
We want to show that V r = 0 V_r=0 V r = 0 for all r ≥ 1 r\ge1 r ≥ 1 . All surviving bases γ i \gamma_i γ i in the power representation of V r V_r V r have absolute value less than R R R , since z r z^r z r cancels out the one remaining term with absolute value R R R in b r b_r b r and Q / R < R Q/R<R Q / R < R by our assumption on R R R . We have
V 2 r = b 2 r − z 2 r − ( Q / z ) 2 r = b r 2 − 2 Q r − z 2 r − ( Q / z ) 2 r = ( V r + z r + ( Q / z ) r ) 2 − 2 Q r − z 2 r − ( Q / z ) 2 r = V r 2 + 2 ( z r + ( Q / z ) r ) V r . \begin{aligned}
V_{2r}&=b_{2r}-z^{2r}-(Q/z)^{2r}=b_r^2-2Q^r-z^{2r}-(Q/z)^{2r}\\
&=(V_r+z^r+(Q/z)^r)^2-2Q^r-z^{2r}-(Q/z)^{2r}\\
&=V_r^2+2(z^r+(Q/z)^r)V_r.
\end{aligned} V 2 r = b 2 r − z 2 r − ( Q / z ) 2 r = b r 2 − 2 Q r − z 2 r − ( Q / z ) 2 r = ( V r + z r + ( Q / z ) r ) 2 − 2 Q r − z 2 r − ( Q / z ) 2 r = V r 2 + 2 ( z r + ( Q / z ) r ) V r .
Assume that V r V_r V r is not identically 0. Let D < R D<R D < R be the largest absolute value among all surviving bases in the power representation. The terms in 2 z r V r 2z^rV_r 2 z r V r arising from bases of absolute value D D D in V r V_r V r have absolute value R D RD R D . Bases occurring in V r 2 V_r^2 V r 2 have absolute value at most D 2 D^2 D 2 and in ( Q / z ) r V r (Q/z)^rV_r ( Q / z ) r V r at most D Q / R DQ/R D Q / R . Similarly, all bases occurring in V 2 r V_{2r} V 2 r have absolute value at most D 2 D^2 D 2 . Both are less than R D RD R D , so the terms in 2 z r V r 2z^rV_r 2 z r V r cannot be canceled, giving a contradiction. So V r = 0 V_r=0 V r = 0 for all r ≥ 1 r\ge1 r ≥ 1 , and
b r = z r + ( Q / z ) r b_r=z^r+(Q/z)^r b r = z r + ( Q / z ) r
as claimed for this case.
Lastly, suppose R = Q R=\sqrt{Q} R = Q . We extend the definition of the b r b_r b r in the natural way to the negative numbers, and we show that Eq. (27) holds for all integer indices r r r , not just positive ones. Indeed, consider
b r 2 − b 2 r − 2 Q r = ∑ i , j m i m j ( γ i γ j ) r − ∑ i m i ( γ i 2 ) r − 2 Q r = ∑ γ ′ n γ ′ ( γ ′ ) r , b_r^2-b_{2r}-2Q^r=\sum_{i,j}m_im_j(\gamma_i\gamma_j)^r-\sum_i m_i(\gamma_i^2)^r-2Q^r=\sum_{\gamma'}n_{\gamma'}(\gamma')^r, b r 2 − b 2 r − 2 Q r = i , j ∑ m i m j ( γ i γ j ) r − i ∑ m i ( γ i 2 ) r − 2 Q r = γ ′ ∑ n γ ′ ( γ ′ ) r ,
where the γ ′ \gamma' γ ′ collect all combinations of γ i 2 \gamma_i^2 γ i 2 , γ i γ j \gamma_i\gamma_j γ i γ j and Q Q Q . By Eq. (27) , this sum of powers evaluates to 0 for all r ≥ 1 r\ge1 r ≥ 1 , which then means that all n γ ′ = 0 n_{\gamma'}=0 n γ ′ = 0 , so the sum also evaluates to zero for all negative r r r , so Eq. (27) holds for all integers.
Replacing every γ i \gamma_i γ i by Q / γ i Q/\gamma_i Q / γ i replaces b r b_r b r by
b ~ r = Q r b − r , \widetilde{b}_r = Q^r b_{-r}, b r = Q r b − r ,
Eq. (27) is then also preserved for the sequence b ~ r \widetilde{b}_r b r since
b ~ r 2 − b ~ 2 r = ( Q r b − r ) 2 − Q 2 r b − 2 r = Q 2 r ( b − r 2 − b − 2 r ) = Q 2 r ⋅ 2 Q − r = 2 Q r . \begin{aligned}
\widetilde{b}_r^2-\widetilde{b}_{2r}
&=(Q^r b_{-r})^2-Q^{2r}b_{-2r}=Q^{2r}(b_{-r}^2-b_{-2r})\\
&=Q^{2r}\cdot2Q^{-r}=2Q^r.
\end{aligned} b r 2 − b 2 r = ( Q r b − r ) 2 − Q 2 r b − 2 r = Q 2 r ( b − r 2 − b − 2 r ) = Q 2 r ⋅ 2 Q − r = 2 Q r .
Assume first that there is γ i \gamma_i γ i with absolute value less than Q \sqrt{Q} Q . Then the new sequence b ~ r \widetilde{b}_r b r contains a base with absolute value Q / ∣ γ i ∣ > Q Q/\lvert\gamma_i\rvert>\sqrt{Q} Q / ∣ γ i ∣ > Q . Now our argument from the case R > Q R>\sqrt{Q} R > Q can be applied to the sequence b ~ r \widetilde{b}_r b r , showing that there exist u , v ∈ C × u,v\in\mathbb{C}^{\times} u , v ∈ C × such that b ~ r = u r + v r \widetilde{b}_r=u^r+v^r b r = u r + v r and u v = Q uv=Q uv = Q . But then
b r = Q r b ~ − r = ( Q / u ) r + ( Q / v ) r , b_r=Q^r\widetilde{b}_{-r}=(Q/u)^r+(Q/v)^r, b r = Q r b − r = ( Q / u ) r + ( Q / v ) r ,
and ( Q / u ) ( Q / v ) = Q (Q/u)(Q/v)=Q ( Q / u ) ( Q / v ) = Q , finishing the proof for this subcase.
It thus only remains to consider the case where all γ i \gamma_i γ i in the power representation of b r b_r b r have absolute value exactly Q \sqrt{Q} Q . In this case, Eq. (29) becomes (recalling the additional term of − 2 -2 − 2 )
m R ( m R − 1 ) + m − R ( m − R − 1 ) + 2 ∑ j = 1 t m z j 2 = 2. (30) m_R(m_R-1)+m_{-R}(m_{-R}-1)+2\sum_{j=1}^{t}m_{z_j}^2=2. \tag*{(30)} m R ( m R − 1 ) + m − R ( m − R − 1 ) + 2 j = 1 ∑ t m z j 2 = 2. (30)
Assume first that there is one nonreal, conjugate pair z j , z j ‾ z_j,\overline{z_j} z j , z j in this equation with m z j ≠ 0 m_{z_j}\ne0 m z j = 0 . Observe that m R ( m R − 1 ) m_R(m_R-1) m R ( m R − 1 ) cannot be negative, the same holds for the corresponding term containing m − R m_{-R} m − R . So the only way to satisfy the equation is to have a unique m z j ∈ { − 1 , 1 } m_{z_j}\in\{-1,1\} m z j ∈ { − 1 , 1 } and m R , m − R ∈ { 0 , 1 } m_R,m_{-R}\in\{0,1\} m R , m − R ∈ { 0 , 1 } . Since all γ i \gamma_i γ i have absolute value R R R , this means b r = m R R r + m − R ( − R ) r + m z j ( z j r + z j ‾ r ) b_r=m_RR^r+m_{-R}(-R)^r+m_{z_j}(z_j^r+\overline{z_j}^r) b r = m R R r + m − R ( − R ) r + m z j ( z j r + z j r ) . Since ∑ i = 1 k m i = 2 \sum_{i=1}^{k}m_i=2 ∑ i = 1 k m i = 2 this means m R + m − R + 2 m z j = 2 m_R+m_{-R}+2m_{z_j}=2 m R + m − R + 2 m z j = 2 yielding the only possibility m z j = 1 m_{z_j}=1 m z j = 1 and m R = m − R = 0 m_R=m_{-R}=0 m R = m − R = 0 , so b r = z j r + z j ‾ r b_r=z_j^r+\overline{z_j}^r b r = z j r + z j r with z j z j ‾ = R 2 = Q z_j\overline{z_j}=R^2=Q z j z j = R 2 = Q as claimed.
The last case that remains is that there is no nonreal, conjugate pair in Eq. (30) , i.e., ∑ j = 1 t m z j 2 = 0 \sum_{j=1}^{t}m_{z_j}^2=0 ∑ j = 1 t m z j 2 = 0 . Then b r = m R R r + m − R ( − R ) r b_r=m_RR^r+m_{-R}(-R)^r b r = m R R r + m − R ( − R ) r , and ∑ i = 1 k m i = 2 \sum_{i=1}^{k}m_i=2 ∑ i = 1 k m i = 2 implies immediately m R + m − R = 2 m_R+m_{-R}=2 m R + m − R = 2 . Eq. (30) then simplifies to
2 = m R ( m R − 1 ) + m − R ( m − R − 1 ) = ( m R + m − R ) 2 − ( m R + m − R ) − 2 m R m − R = 2 − 2 m R m − R . \begin{aligned}
2&=m_R(m_R-1)+m_{-R}(m_{-R}-1)\\
&=(m_R+m_{-R})^2-(m_R+m_{-R})-2m_Rm_{-R}\\
&=2-2m_Rm_{-R}.
\end{aligned} 2 = m R ( m R − 1 ) + m − R ( m − R − 1 ) = ( m R + m − R ) 2 − ( m R + m − R ) − 2 m R m − R = 2 − 2 m R m − R .
So m R m − R = 0 m_Rm_{-R}=0 m R m − R = 0 and the only solutions are m R = 2 m_R=2 m R = 2 , m − R = 0 m_{-R}=0 m − R = 0 and m R = 0 m_R=0 m R = 0 , m − R = 2 m_{-R}=2 m − R = 2 , so b r = 2 γ r = γ r + γ r b_r=2\gamma^r=\gamma^r+\gamma^r b r = 2 γ r = γ r + γ r with γ ∈ { − R , R } \gamma\in\{-R,R\} γ ∈ { − R , R } , so γ 2 = R 2 = Q \gamma^2=R^2=Q γ 2 = R 2 = Q , finishing the proof. □
Applying Lemma 7.4 to Propositions 7.2 and 7.3:
Corollary 7.5. We have for all a ∈ L × a\in L^{\times} a ∈ L × , that there exist u , v ∈ C × u,v\in\mathbb{C}^{\times} u , v ∈ C × with u v = q 5 uv=q^5 uv = q 5 such that
A r ( a ) = u r + v r A_r(a)=u^r+v^r A r ( a ) = u r + v r for all r ≥ 1 r\ge1 r ≥ 1 .
In particular, Corollary 7.5 gives A 1 ( a ) = − S 1 ( a ) = − W q ( a ) = u + v A_1(a)=-S_1(a)=-W_q(a)=u+v A 1 ( a ) = − S 1 ( a ) = − W q ( a ) = u + v , so the Walsh transform of the Dobbertin APN function is uniquely determined (for a fixed a a a ) by u u u and v v v . Together with Eq. (21) , we have
A 5 r ( a ) = u 5 r + v 5 r = ( q 2 α ) 5 r + ( q 2 β ) 5 r . A_{5r}(a)=u^{5r}+v^{5r}=(q^2\alpha)^{5r}+(q^2\beta)^{5r}. A 5 r ( a ) = u 5 r + v 5 r = ( q 2 α ) 5 r + ( q 2 β ) 5 r .
Here α , β ∈ C × \alpha,\beta\in\mathbb{C}^{\times} α , β ∈ C × are the coefficients originating from the elliptic curve in Theorem 6.2. Note that ( q 2 α ) ( q 2 β ) = q 5 (q^2\alpha)(q^2\beta)=q^5 ( q 2 α ) ( q 2 β ) = q 5 . We will now show that indeed { u , v } = { q 2 α , q 2 β } \{u,v\}=\{q^2\alpha,q^2\beta\} { u , v } = { q 2 α , q 2 β } . We have to start by connecting A 5 r A_{5r} A 5 r to A r A_r A r . We will do this using a Dickson polynomial. More precisely, we will use the fifth Dickson polynomial, which can be directly defined as
D 5 ( X , A ) = X 5 − 5 A X 3 + 5 A 2 X . D_5(X,A)=X^5-5AX^3+5A^2X. D 5 ( X , A ) = X 5 − 5 A X 3 + 5 A 2 X .
It follows by direct expansion or using the well known properties of the Dickson polynomials that
D 5 ( u + v , u v ) = u 5 + v 5 . D_5(u+v,uv)=u^5+v^5. D 5 ( u + v , uv ) = u 5 + v 5 .
This means that (using Corollary 7.5)
D 5 ( A 1 ( a ) , q 5 ) = A 5 ( a ) = ( q 2 α ) 5 + ( q 2 β ) 5 . (31) D_5(\mathcal{A}_1(a),q^5)=\mathcal{A}_5(a)=(q^2\alpha)^5+(q^2\beta)^5. \tag*{(31)} D 5 ( A 1 ( a ) , q 5 ) = A 5 ( a ) = ( q 2 α ) 5 + ( q 2 β ) 5 . (31)
The following injectivity property shows that we can determine A 1 ( a ) \mathcal{A}_1(a) A 1 ( a ) uniquely from that.
Lemma 7.6. For every A ∈ Q A\in\mathbb{Q} A ∈ Q , the map x ↦ D 5 ( x , A ) x\mapsto D_5(x,A) x ↦ D 5 ( x , A ) is injective on Q \mathbb{Q} Q .
Proof. Suppose x ≠ y x\ne y x = y are rational and D 5 ( x , A ) = D 5 ( y , A ) D_5(x,A)=D_5(y,A) D 5 ( x , A ) = D 5 ( y , A ) . Put
U = x 2 + y 2 − 3 A , V = x y + A . U=x^2+y^2-3A,\qquad V=xy+A. U = x 2 + y 2 − 3 A , V = x y + A . Expansion gives
0 = D 5 ( x , A ) − D 5 ( y , A ) x − y = U 2 + U V − V 2 . 0=\frac{D_5(x,A)-D_5(y,A)}{x-y}=U^2+UV-V^2. 0 = x − y D 5 ( x , A ) − D 5 ( y , A ) = U 2 + U V − V 2 . Consequently,
( 2 U + V ) 2 = 5 V 2 . (2U+V)^2=5V^2. ( 2 U + V ) 2 = 5 V 2 . Since 5 \sqrt{5} 5 is irrational, U = V = 0 U=V=0 U = V = 0 . But then
( x − y ) 2 − 5 ( x + y ) 2 = − 4 ( U + 3 V ) = 0. (x-y)^2-5(x+y)^2=-4(U+3V)=0. ( x − y ) 2 − 5 ( x + y ) 2 = − 4 ( U + 3 V ) = 0. The same irrationality forces x − y = x + y = 0 x-y=x+y=0 x − y = x + y = 0 , contrary to x ≠ y x\ne y x = y . □
This now allows us finally to relate S 1 ( a ) = W q ( a ) S_1(a)=W_q(a) S 1 ( a ) = W q ( a ) to the elliptic curve, and thus to prove Theorem 2.2
Theorem 7.7 (Copy of Theorem 2.2 ). For a ≠ 1 a\ne1 a = 1 , recall the elliptic curve given in Eq. (1)
E a : Y 2 + ( Tr L / K ( a ) X + N L / K ( a ) ) Y = X 3 + e 2 ( a ) X 2 + ω ( a ) . E_a:\quad Y^2+\left(\operatorname{Tr}_{L/K}(a)X+N_{L/K}(a)\right)Y=X^3+e_2(a)X^2+\omega(a). E a : Y 2 + ( Tr L / K ( a ) X + N L / K ( a ) ) Y = X 3 + e 2 ( a ) X 2 + ω ( a ) . Then for a ∈ L × a\in L^\times a ∈ L × , we have
W q ( a ) = { q 2 ( # E a ( F q ) − q − 1 ) , a ≠ 1 , ( − 1 ) m + 1 q 2 ( q + 1 ) , a = 1. W_q(a)=
\begin{cases}
q^2(\#E_a(\mathbb{F}_q)-q-1), & a\ne1,\\
(-1)^{m+1}q^2(q+1), & a=1.
\end{cases} W q ( a ) = { q 2 ( # E a ( F q ) − q − 1 ) , ( − 1 ) m + 1 q 2 ( q + 1 ) , a = 1 , a = 1. Proof. By Eq. (31) , Corollary 7.5, and Eq. (21) ,
D 5 ( A 1 ( a ) , q 5 ) = ( q 2 α ) 5 + ( q 2 β ) 5 = D 5 ( q 2 ( α + β ) , q 5 ) = D 5 ( − q 2 C 1 ( a ) , q 5 ) . D_5(\mathcal{A}_1(a),q^5)=(q^2\alpha)^5+(q^2\beta)^5=D_5\left(q^2(\alpha+\beta),q^5\right)=D_5\left(-q^2C_1(a),q^5\right). D 5 ( A 1 ( a ) , q 5 ) = ( q 2 α ) 5 + ( q 2 β ) 5 = D 5 ( q 2 ( α + β ) , q 5 ) = D 5 ( − q 2 C 1 ( a ) , q 5 ) . Both A 1 ( a ) \mathcal{A}_1(a) A 1 ( a ) and − q 2 C 1 ( a ) -q^2C_1(a) − q 2 C 1 ( a ) are integers. The injectivity of the Dickson polynomial just proven in Lemma 7.6 therefore gives
A 1 ( a ) = − q 2 C 1 ( a ) . \mathcal{A}_1(a)=-q^2C_1(a). A 1 ( a ) = − q 2 C 1 ( a ) . Since A 1 ( a ) = − S 1 ( a ) = − W q ( a ) \mathcal{A}_1(a)=-S_1(a)=-W_q(a) A 1 ( a ) = − S 1 ( a ) = − W q ( a ) by the definition in Eq. (20) , we conclude that S 1 ( a ) = q 2 C 1 ( a ) S_1(a)=q^2C_1(a) S 1 ( a ) = q 2 C 1 ( a ) . For a = 1 a=1 a = 1 this immediately gives W q ( 1 ) = ( − 1 ) m + 1 q 2 ( q + 1 ) W_q(1)=(-1)^{m+1}q^2(q+1) W q ( 1 ) = ( − 1 ) m + 1 q 2 ( q + 1 ) using the special value from Eq. (19) . In all other cases, we get the connection to the elliptic curve via Eq. (18) . □
Counting the points in the elliptic curve
With Theorem 2.2 proven, it remains to determine # E a ( F q ) \#\mathcal{E}_a(\mathbb{F}_q) # E a ( F q ) for the elliptic curve defined by Eq. (1) . This is quite standard.
For a ∉ { 0 , 1 } a \notin\{0,1\} a ∈ / { 0 , 1 } , we now evaluate # E a ( K ) \#\mathcal{E}_a(K) # E a ( K ) . We first determine when the curve is supersingular and when it is ordinary.
Lemma 8.1. Let a ∈ L ∖ { 0 , 1 } a \in L \setminus\{0,1\} a ∈ L ∖ { 0 , 1 } . The elliptic curve E a \mathcal{E}_a E a is ordinary if and only if Tr L / K ( a ) ≠ 0 \operatorname{Tr}_{L/K}(a) \ne0 Tr L / K ( a ) = 0 , and supersingular if and only if Tr L / K ( a ) = 0 \operatorname{Tr}_{L/K}(a) = 0 Tr L / K ( a ) = 0 .
Proof. The homogeneous equation of E a \mathcal{E}_a E a is
Y 2 Z + Tr L / K ( a ) X Y Z + N L / K ( a ) Y Z 2 = X 3 + e 2 ( a ) X 2 Z + ω ( a ) Z 3 . Y^2Z+\operatorname{Tr}_{L/K}(a)XYZ+\operatorname{N}_{L/K}(a)YZ^2=X^3+e_2(a)X^2Z+\omega(a)Z^3. Y 2 Z + Tr L / K ( a ) X Y Z + N L / K ( a ) Y Z 2 = X 3 + e 2 ( a ) X 2 Z + ω ( a ) Z 3 . In characteristic two, a nonsingular plane cubic is supersingular if and only if its X Y Z XYZ X Y Z coefficient is zero [13 p. 332] . Here that coefficient is Tr L / K ( a ) \operatorname{Tr}_{L/K}(a) Tr L / K ( a ) , proving the assertion. □ \square □
For k ∈ K k \in K k ∈ K , define the Kloosterman sum
Kl K ( k ) = ∑ u ∈ K × ψ K ( u + k / u ) . \operatorname{Kl}_K(k)=\sum_{u\in K^\times}\psi_K(u+k/u). Kl K ( k ) = u ∈ K × ∑ ψ K ( u + k / u ) .
We use the following result for the point counting of elliptic curves [19 Proposition 1 and Section 2, p. 881] .
Theorem 8.2. Let K K K be a finite field of characteristic 2. Every ordinary elliptic curve E E E over K K K is K K K -isomorphic to a curve
E d , k : y 2 + x y = x 3 + d x 2 + k , d ∈ K , k ∈ K × . E_{d,k}: \quad y^2+xy=x^3+dx^2+k,\qquad d\in K,\quad k\in K^\times. E d , k : y 2 + x y = x 3 + d x 2 + k , d ∈ K , k ∈ K × . In this case, we have
# E ( K ) = q + 1 + ψ K ( d ) Kl K ( k ) . \#E(K)=q+1+\psi_K(d)\operatorname{Kl}_K(k). # E ( K ) = q + 1 + ψ K ( d ) Kl K ( k ) .
With this, we can prove Theorem 2.3 .
Proof of Theorem 2.3 . For a = 0 a=0 a = 0 , we have W q ( 0 ) = 0 W_q(0)=0 W q ( 0 ) = 0 . For a = 1 a=1 a = 1 , Theorem 2.2 gives
W q ( 1 ) = ( − 1 ) m + 1 q 2 ( q + 1 ) . W_q(1)=(-1)^{m+1}q^2(q+1). W q ( 1 ) = ( − 1 ) m + 1 q 2 ( q + 1 ) .
So assume a ∈ L ∖ { 0 , 1 } a\in L\setminus\{0,1\} a ∈ L ∖ { 0 , 1 } . If Tr L / K ( a ) = 0 \operatorname{Tr}_{L/K}(a)=0 Tr L / K ( a ) = 0 , then ω ( a ) = N L / K ( a ) e 3 ( a ) \omega(a)=\operatorname{N}_{L/K}(a)e_3(a) ω ( a ) = N L / K ( a ) e 3 ( a ) and N L / K ( a ) ≠ 0 \operatorname{N}_{L/K}(a)\ne0 N L / K ( a ) = 0 . Substitute X = u 2 + e 2 ( a ) X=u^2+e_2(a) X = u 2 + e 2 ( a ) , and with z = Y / N L / K ( a ) z=Y/\operatorname{N}_{L/K}(a) z = Y / N L / K ( a ) the curve equation becomes
z 2 + z = ( u 3 + e 2 ( a ) u N L / K ( a ) ) 2 + e 3 ( a ) N L / K ( a ) . z^2+z=\left(\frac{u^3+e_2(a)u}{\operatorname{N}_{L/K}(a)}\right)^2+\frac{e_3(a)}{\operatorname{N}_{L/K}(a)}. z 2 + z = ( N L / K ( a ) u 3 + e 2 ( a ) u ) 2 + N L / K ( a ) e 3 ( a ) .
Since z 2 + z = t z^2+z=t z 2 + z = t has 1 + ψ K ( t ) 1+\psi_K(t) 1 + ψ K ( t ) solutions and ψ K ( t 2 ) = ψ K ( t ) \psi_K(t^2)=\psi_K(t) ψ K ( t 2 ) = ψ K ( t ) , each u ∈ K u\in K u ∈ K contributes
1 + ψ K ( u 3 + e 2 ( a ) u + e 3 ( a ) N L / K ( a ) ) 1+\psi_K\left(\frac{u^3+e_2(a)u+e_3(a)}{\operatorname{N}_{L/K}(a)}\right) 1 + ψ K ( N L / K ( a ) u 3 + e 2 ( a ) u + e 3 ( a ) )
affine points. Summing over u u u and adding O O O proves the stated formula for this case.
Now suppose Tr L / K ( a ) ≠ 0 \operatorname{Tr}_{L/K}(a)\ne0 Tr L / K ( a ) = 0 . Lemma 3.2 gives Tr L / K ( a ) 2 + N L / K ( a ) / a ≠ 0 \operatorname{Tr}_{L/K}(a)^2+\operatorname{N}_{L/K}(a)/a\ne0 Tr L / K ( a ) 2 + N L / K ( a ) / a = 0 , so k ( a ) ≠ 0 k(a)\ne0 k ( a ) = 0 . Expanding the norm gives
N L / K ( Tr L / K ( a ) 2 + N L / K ( a ) / a ) = N L / K ( a ) 4 + N L / K ( a ) 3 Tr L / K ( a ) 3 + e 2 ( a ) N L / K ( a ) 2 Tr L / K ( a ) 4 + ω ( a ) Tr L / K ( a ) \operatorname{N}_{L/K}\left(\operatorname{Tr}_{L/K}(a)^2+\operatorname{N}_{L/K}(a)/a\right)=\operatorname{N}_{L/K}(a)^4+\operatorname{N}_{L/K}(a)^3\operatorname{Tr}_{L/K}(a)^3+e_2(a)\operatorname{N}_{L/K}(a)^2\operatorname{Tr}_{L/K}(a)^4+\omega(a)\operatorname{Tr}_{L/K}(a) N L / K ( Tr L / K ( a ) 2 + N L / K ( a ) / a ) = N L / K ( a ) 4 + N L / K ( a ) 3 Tr L / K ( a ) 3 + e 2 ( a ) N L / K ( a ) 2 Tr L / K ( a ) 4 + ω ( a ) Tr L / K ( a )
The change of coordinates
X = Tr L / K ( a ) 2 x + N L / K ( a ) Tr L / K ( a ) , Y = Tr L / K ( a ) 3 y + N L / K ( a ) 2 Tr L / K ( a ) 3 X=\operatorname{Tr}_{L/K}(a)^2x+\frac{\operatorname{N}_{L/K}(a)}{\operatorname{Tr}_{L/K}(a)},\qquad Y=\operatorname{Tr}_{L/K}(a)^3y+\frac{\operatorname{N}_{L/K}(a)^2}{\operatorname{Tr}_{L/K}(a)^3} X = Tr L / K ( a ) 2 x + Tr L / K ( a ) N L / K ( a ) , Y = Tr L / K ( a ) 3 y + Tr L / K ( a ) 3 N L / K ( a ) 2
therefore transforms the equation of E a \mathcal{E}_a E a into
y 2 + x y = x 3 + d ( a ) x 2 + k ( a ) . y^2+xy=x^3+d(a)x^2+k(a). y 2 + x y = x 3 + d ( a ) x 2 + k ( a ) .
Theorem 8.2 then concludes the proof of this case.
Finally, if a ∈ K ∖ { 0 , 1 } a \in K \setminus\{0,1\} a ∈ K ∖ { 0 , 1 } , then e 2 ( a ) = 0 e_2(a)=0 e 2 ( a ) = 0 , Tr L / K ( a ) = a \operatorname{Tr}_{L/K}(a)=a Tr L / K ( a ) = a , and N L / K ( a ) = a 5 N_{L/K}(a)=a^5 N L / K ( a ) = a 5 . Hence d ( a ) = a 2 d(a)=a^2 d ( a ) = a 2 and k ( a ) = ( ( a + 1 ) 5 a ) 2 k(a)=\left(\frac{(a+1)^5}{a}\right)^2 k ( a ) = ( a ( a + 1 ) 5 ) 2 , yielding the formula for this case.
We now give an explicit evaluation of the cubic sums using Carlitz’s formulas [6 Theorems 1 and 2] .
Proposition 8.3. Let a ∈ L ∖ { 0 , 1 } a \in L \setminus\{0,1\} a ∈ L ∖ { 0 , 1 } with Tr L / K ( a ) = 0 \operatorname{Tr}_{L/K}(a)=0 Tr L / K ( a ) = 0 , and put
A ( a ) = ∑ u ∈ K ψ K ( u 3 + e 2 ( a ) u + e 3 ( a ) N L / K ( a ) ) . A(a)=\sum_{u\in K}\psi_K\left(\frac{u^3+e_2(a)u+e_3(a)}{N_{L/K}(a)}\right). A ( a ) = u ∈ K ∑ ψ K ( N L / K ( a ) u 3 + e 2 ( a ) u + e 3 ( a ) ) . (i) Suppose m m m is odd. Let ρ ∈ K × \rho\in K^\times ρ ∈ K × be the unique element with ρ 3 = N L / K ( a ) \rho^3=N_{L/K}(a) ρ 3 = N L / K ( a ) , and put B = e 2 ( a ) / ρ 2 B=e_2(a)/\rho^2 B = e 2 ( a ) / ρ 2 . If Tr K / F 2 ( B ) = 0 \operatorname{Tr}_{K/\mathbb{F}_2}(B)=0 Tr K / F 2 ( B ) = 0 , then A ( a ) = 0 A(a)=0 A ( a ) = 0 . If Tr K / F 2 ( B ) = 1 \operatorname{Tr}_{K/\mathbb{F}_2}(B)=1 Tr K / F 2 ( B ) = 1 , the equation
z 4 + z = B 2 + 1 z^4+z=B^2+1 z 4 + z = B 2 + 1 has a solution in K K K , and for any such solution,
A ( a ) = ( − 1 ) ( m 2 − 1 ) / 8 2 ( m + 1 ) / 2 ψ K ( e 3 ( a ) N L / K ( a ) + z 3 + z ) . A(a)=(-1)^{(m^2-1)/8}2^{(m+1)/2}\psi_K\left(\frac{e_3(a)}{N_{L/K}(a)}+z^3+z\right). A ( a ) = ( − 1 ) ( m 2 − 1 ) /8 2 ( m + 1 ) /2 ψ K ( N L / K ( a ) e 3 ( a ) + z 3 + z ) . (ii) Suppose m m m is even. If
z 4 + N L / K ( a ) z = e 2 ( a ) 2 z^4+N_{L/K}(a)z=e_2(a)^2 z 4 + N L / K ( a ) z = e 2 ( a ) 2 has no solution in K K K , then A ( a ) = 0 A(a)=0 A ( a ) = 0 . Otherwise, for any solution z ∈ K z\in K z ∈ K ,
A ( a ) = ψ K ( z 3 + e 3 ( a ) N L / K ( a ) ) { ( − 1 ) m / 2 + 1 2 m / 2 + 1 , N L / K ( a ) ∈ ( K × ) 3 , ( − 1 ) m / 2 2 m / 2 , N L / K ( a ) ∉ ( K × ) 3 . A(a)=\psi_K\left(\frac{z^3+e_3(a)}{N_{L/K}(a)}\right)
\begin{cases}
(-1)^{m/2+1}2^{m/2+1}, & N_{L/K}(a)\in(K^\times)^3,\\
(-1)^{m/2}2^{m/2}, & N_{L/K}(a)\notin(K^\times)^3.
\end{cases} A ( a ) = ψ K ( N L / K ( a ) z 3 + e 3 ( a ) ) { ( − 1 ) m /2 + 1 2 m /2 + 1 , ( − 1 ) m /2 2 m /2 , N L / K ( a ) ∈ ( K × ) 3 , N L / K ( a ) ∈ / ( K × ) 3 . In particular,
# E a ( K ) = q + 1 + A ( a ) . \#E_a(K)=q+1+A(a). # E a ( K ) = q + 1 + A ( a ) . Proof. Extracting the constant term gives
A ( a ) = ψ K ( e 3 ( a ) N L / K ( a ) ) ∑ u ∈ K ψ K ( N L / K ( a ) − 1 u 3 + ( e 2 ( a ) / N L / K ( a ) ) u ) . A(a)=\psi_K\left(\frac{e_3(a)}{N_{L/K}(a)}\right)\sum_{u\in K}\psi_K\left(N_{L/K}(a)^{-1}u^3+\left(e_2(a)/N_{L/K}(a)\right)u\right). A ( a ) = ψ K ( N L / K ( a ) e 3 ( a ) ) u ∈ K ∑ ψ K ( N L / K ( a ) − 1 u 3 + ( e 2 ( a ) / N L / K ( a ) ) u ) . Apply [15 Theorems 6.2 and 6.3, pp. 864 and 866] with α = 1 \alpha=1 α = 1 , cubic coefficient κ = N L / K ( a ) − 1 \kappa=N_{L/K}(a)^{-1} κ = N L / K ( a ) − 1 , linear coefficient e 2 ( a ) / N L / K ( a ) e_2(a)/N_{L/K}(a) e 2 ( a ) / N L / K ( a ) , and extension degree m m m . For odd m m m , the substitution u = ρ x u=\rho x u = ρ x gives x 3 + B x x^3+Bx x 3 + B x . Square invariance yields
∑ x ∈ K ψ K ( x 3 + B x ) = ∑ x ∈ K ψ K ( x 3 + B 2 x ) . \sum_{x\in K}\psi_K(x^3+Bx)=\sum_{x\in K}\psi_K(x^3+B^2x). x ∈ K ∑ ψ K ( x 3 + B x ) = x ∈ K ∑ ψ K ( x 3 + B 2 x ) . For B ≠ 0 B\ne0 B = 0 , apply [6 Theorem 2, p. 15] , keeping in mind the identity ( 2 m ) = ( − 1 ) ( m 2 − 1 ) / 8 \binom{2}{m}=(-1)^{(m^2-1)/8} ( m 2 ) = ( − 1 ) ( m 2 − 1 ) /8 for Jacobi symbols. This gives (i). For B = 0 B=0 B = 0 , the sum vanishes because cubing permutes K K K .
For even m m m , apply [6 Theorem 1, pp. 10–11] giving (ii).
Using the well known characterization of the spectrum of Kloosterman sums, we can determine the spectrum of the Dobbertin APN function Theorem 2.4 . We start with a lemma
Lemma 8.4. Put H = { x ∈ L : Tr L / K ( x ) = 0 } H=\{x\in L:\operatorname{Tr}_{L/K}(x)=0\} H = { x ∈ L : Tr L / K ( x ) = 0 } . Define
Φ : H ⟶ K 2 , Φ ( θ ) = ( e 2 ( θ ) , Tr L / K ( θ 5 ) ) . \Phi:H\longrightarrow K^2,\qquad\Phi(\theta)=\left(e_2(\theta),\operatorname{Tr}_{L/K}(\theta^5)\right). Φ : H ⟶ K 2 , Φ ( θ ) = ( e 2 ( θ ) , Tr L / K ( θ 5 ) ) . Then Φ \Phi Φ is surjective.
Proof. Recalling e 1 ( θ ) = Tr L / K ( θ ) e_1(\theta)=\operatorname{Tr}_{L/K}(\theta) e 1 ( θ ) = Tr L / K ( θ ) and e 5 ( θ ) = N L / K ( θ ) e_5(\theta)=N_{L/K}(\theta) e 5 ( θ ) = N L / K ( θ ) , Newton’s identities for elementary symmetric polynomials (or a direct elementary calculation) yield for θ ∈ H \theta\in H θ ∈ H
N L / K ( θ ) = Tr L / K ( θ 5 ) + e 2 ( θ ) Tr L / K ( θ 3 ) . (32) N_{L/K}(\theta)=\operatorname{Tr}_{L/K}(\theta^5)+e_2(\theta)\operatorname{Tr}_{L/K}(\theta^3). \tag*{(32)} N L / K ( θ ) = Tr L / K ( θ 5 ) + e 2 ( θ ) Tr L / K ( θ 3 ) . (32)
Consequently, Φ − 1 ( 0 , 0 ) = { 0 } \Phi^{-1}(0,0)=\{0\} Φ − 1 ( 0 , 0 ) = { 0 } .
Viewed over F 2 \mathbb{F}_2 F 2 , H H H has dimension 4 m 4m 4 m and K 2 K^2 K 2 has dimension 2 m 2m 2 m . Note that Φ \Phi Φ is quadratic, since e 2 e_2 e 2 is quadratic and θ 5 = θ θ 4 \theta^5=\theta\theta^4 θ 5 = θ θ 4 is also quadratic over F 2 \mathbb{F}_2 F 2 .
Write its 2 m 2m 2 m coordinate functions as f 1 , … , f 2 m f_1,\ldots,f_{2m} f 1 , … , f 2 m . For any y ∈ F 2 2 m y\in\mathbb{F}_2^{2m} y ∈ F 2 2 m , the preimage size satisfies
# Φ − 1 ( y ) ≡ ∑ x ∈ F 2 4 m ∏ i = 1 2 m ( 1 + f i ( x ) + y i ) ≡ ∑ x ∈ F 2 4 m ∏ i = 1 2 m ( 1 + f i ( x ) ) ≡ # Φ − 1 ( 0 ) ( m o d 2 ) . \begin{aligned}
\#\Phi^{-1}(y)\equiv\sum_{x\in\mathbb{F}_2^{4m}}\prod_{i=1}^{2m}(1+f_i(x)+y_i) \\
&\equiv\sum_{x\in\mathbb{F}_2^{4m}}\prod_{i=1}^{2m}(1+f_i(x))\equiv\#\Phi^{-1}(0)\pmod2.
\end{aligned} # Φ − 1 ( y ) ≡ x ∈ F 2 4 m ∑ i = 1 ∏ 2 m ( 1 + f i ( x ) + y i ) ≡ x ∈ F 2 4 m ∑ i = 1 ∏ 2 m ( 1 + f i ( x )) ≡ # Φ − 1 ( 0 ) ( mod 2 ) .
The second congruence holds because every term involving some y i y_i y i has degree at most 4 m − 2 4m-2 4 m − 2 since all f i f_i f i are quadratic, and a polynomial of degree less than 4 m 4m 4 m sums to zero over F 2 4 m \mathbb{F}_2^{4m} F 2 4 m . Since the preimage of 0 0 0 has one element, every preimage has odd cardinality, and is in particular not empty. □ \square □
Proof of Theorem 2.4 . First, a = 1 a=1 a = 1 gives ∣ W q ( 1 ) ∣ = q 2 ( q + 1 ) |W_q(1)|=q^2(q+1) ∣ W q ( 1 ) ∣ = q 2 ( q + 1 ) .
Let us first consider the set { q j : j ∈ N odd , ∣ j ∣ ≤ 2 q } \{q^j:j\in\mathbb{N}\text{ odd},\ |j|\leq2\sqrt{q}\} { q j : j ∈ N odd , ∣ j ∣ ≤ 2 q } . Fix k ∈ K × k\in K^\times k ∈ K × . Lemma 8.4 supplies θ ∈ H = { x ∈ L : Tr L / K ( x ) = 0 } \theta\in H=\{x\in L:\operatorname{Tr}_{L/K}(x)=0\} θ ∈ H = { x ∈ L : Tr L / K ( x ) = 0 } such that e 2 ( θ ) = 0 e_2(\theta)=0 e 2 ( θ ) = 0 , Tr L / K ( θ 5 ) = k \operatorname{Tr}_{L/K}(\theta^5)=k Tr L / K ( θ 5 ) = k . By Eq. (32) , we then have N L / K ( θ ) = k N_{L/K}(\theta)=k N L / K ( θ ) = k . Put
a = λ ( θ + 1 ) , where λ 2 = N L / K ( θ + 1 ) − 1 . a=\lambda(\theta+1),\qquad\text{where }\lambda^2=N_{L/K}(\theta+1)^{-1}. a = λ ( θ + 1 ) , where λ 2 = N L / K ( θ + 1 ) − 1 .
Since θ ≠ 0 \theta\neq0 θ = 0 and K ∩ H = { 0 } K\cap H=\{0\} K ∩ H = { 0 } , this is well defined and a ∉ K a\notin K a ∈ / K . Write θ i = θ q i \theta_i=\theta^{q^i} θ i = θ q i for 0 ≤ i < 5 0\leq i<5 0 ≤ i < 5 . We have
Tr L / K ( a ) = λ ( Tr L / K ( θ ) + Tr L / K ( 1 ) ) = λ ( 0 + 1 ) = λ , \operatorname{Tr}_{L/K}(a)=\lambda\bigl(\operatorname{Tr}_{L/K}(\theta)+\operatorname{Tr}_{L/K}(1)\bigr)=\lambda(0+1)=\lambda, Tr L / K ( a ) = λ ( Tr L / K ( θ ) + Tr L / K ( 1 ) ) = λ ( 0 + 1 ) = λ ,
e 2 ( a ) = λ 2 ∑ i < j ( θ i + 1 ) ( θ j + 1 ) = λ 2 ( e 2 ( θ ) + 4 ∑ i = 0 4 θ i + ( 5 2 ) ) = 0 , \begin{aligned}
e_2(a)=\lambda^2\sum_{i<j}(\theta_i+1)(\theta_j+1) \\
&=\lambda^2\left(e_2(\theta)+4\sum_{i=0}^{4}\theta_i+\binom{5}{2}\right)=0,
\end{aligned} e 2 ( a ) = λ 2 i < j ∑ ( θ i + 1 ) ( θ j + 1 ) = λ 2 ( e 2 ( θ ) + 4 i = 0 ∑ 4 θ i + ( 2 5 ) ) = 0 ,
N L / K ( a ) = λ 5 N L / K ( θ + 1 ) = λ 5 λ − 2 = λ 3 . N_{L/K}(a)=\lambda^5N_{L/K}(\theta+1)=\lambda^5\lambda^{-2}=\lambda^3. N L / K ( a ) = λ 5 N L / K ( θ + 1 ) = λ 5 λ − 2 = λ 3 .
Substituting into the definitions in Theorem 2.3 gives d ( a ) = 1 d(a)=1 d ( a ) = 1 and k ( a ) = k k(a)=k k ( a ) = k . Hence
∣ W q ( a ) ∣ = q 2 ∣ Kl K ( k ( a ) ) ∣ . |W_q(a)|=q^2\lvert\operatorname{Kl}_K(k(a))\rvert. ∣ W q ( a ) ∣ = q 2 ∣ Kl K ( k ( a ))∣ .
The range of Kloosterman sums is for m ≥ 2 m\geq2 m ≥ 2 exactly
{ Kl K ( k ) : k ∈ K × } = { j ∈ Z : j ≡ − 1 ( m o d 4 ) , ∣ j ∣ ≤ 2 q } , \{\operatorname{Kl}_K(k):k\in K^\times\}=\{j\in\mathbb{Z}:j\equiv-1\pmod4,\ |j|\leq2\sqrt{q}\}, { Kl K ( k ) : k ∈ K × } = { j ∈ Z : j ≡ − 1 ( mod 4 ) , ∣ j ∣ ≤ 2 q } ,
see [20 Theorem 3.4] , giving the stated values (the m = 1 m=1 m = 1 case can be verified by hand).
Let us now focus on the values in U m U_m U m , and fix η ∈ K × \eta\in K^\times η ∈ K × and B ∈ K B\in K B ∈ K . Lemma 8.4 supplies a nonzero θ ∈ H \theta\in H θ ∈ H with e 2 ( θ ) = B e_2(\theta)=B e 2 ( θ ) = B : Indeed, use the target ( B , 0 ) (B,0) ( B , 0 ) if B ≠ 0 B\neq0 B = 0 , and ( 0 , 1 ) (0,1) ( 0 , 1 ) if B = 0 B=0 B = 0 . Set
a = λ θ , where λ 2 = ( η N L / K ( θ ) ) − 1 . a=\lambda\theta,\qquad\text{where }\lambda^2=(\eta N_{L/K}(\theta))^{-1}. a = λ θ , where λ 2 = ( η N L / K ( θ ) ) − 1 .
Then Tr L / K ( a ) = 0 \operatorname{Tr}_{L/K}(a)=0 Tr L / K ( a ) = 0 . The substitution u = λ x u=\lambda x u = λ x in the cubic-sum formula gives
W q ( a ) = q 2 ψ K ( η e 3 ( θ ) ) ∑ x ∈ K ψ K ( η ( x 3 + B x ) ) . W_q(a)=q^2\psi_K(\eta e_3(\theta))\sum_{x\in K}\psi_K\bigl(\eta(x^3+Bx)\bigr). W q ( a ) = q 2 ψ K ( η e 3 ( θ )) x ∈ K ∑ ψ K ( η ( x 3 + B x ) ) .
Consequently,
∣ W q ( a ) ∣ = q 2 ∣ ∑ x ∈ K ψ K ( η ( x 3 + B x ) ) ∣ . \left|W_q(a)\right| = q^2 \left|\sum_{x\in K}\psi_K\left(\eta(x^3+Bx)\right)\right|. ∣ W q ( a ) ∣ = q 2 x ∈ K ∑ ψ K ( η ( x 3 + B x ) ) .
The result then follows from the Walsh spectra of the Gold APN function, see Table 1 . □
Sidon sets and two-error-correcting codes
A subset S S S of F 2 t \mathbb{F}_2^t F 2 t is Sidon if no four distinct elements sum to zero. A result due to Czerwinski and Pott [7 ] constructs large Sidon sets in F 2 2 m − 1 \mathbb{F}_2^{2m-1} F 2 2 m − 1 as well as binary linear codes with good parameters from APN functions in dimension m m m with high linearity. Theorem 2.2 in particular determines the linearity of the Dobbertin APN function, leading to the following result.
Theorem 9.1. For every m ≥ 1 m \ge1 m ≥ 1 , put
M m = 2 5 m − 1 + 2 3 m − 1 + 2 2 m − 1 . M_m = 2^{5m-1}+2^{3m-1}+2^{2m-1}. M m = 2 5 m − 1 + 2 3 m − 1 + 2 2 m − 1 . There exists a Sidon set of size M m M_m M m in F 2 10 m − 1 \mathbb{F}_2^{10m-1} F 2 10 m − 1 , and there exist binary linear codes with parameters
[ M m − 1 , M m − 10 m , 5 ] 2 . [M_m-1,M_m-10m,5]_2. [ M m − 1 , M m − 10 m , 5 ] 2 .
Proof. By Theorem 2.2 , the largest absolute Walsh coefficient of the Dobbertin APN function is ℓ = q 2 ( q + 1 ) \ell=q^2(q+1) ℓ = q 2 ( q + 1 ) . By [7 Corollary 3.6] , a Sidon set can be constructed from an APN function by intersecting its graph with an affine hyperplane, the size of this Sidon set is
2 5 m + ℓ 2 = M m . \frac{2^{5m}+\ell}{2}=M_m. 2 2 5 m + ℓ = M m .
The intersection affinely spans the hyperplane: otherwise, an additional independent affine equation would imply M m ≤ ℓ M_m\le\ell M m ≤ ℓ , contradicting M m = ( 2 5 m + ℓ ) / 2 > ℓ M_m=(2^{5m}+\ell)/2>\ell M m = ( 2 5 m + ℓ ) /2 > ℓ .
Let S ⊆ F 2 10 m − 1 S\subseteq\mathbb{F}_2^{10m-1} S ⊆ F 2 10 m − 1 be the resulting Sidon set. Since ( M m 3 ) > 2 10 m − 1 \binom{M_m}{3}>2^{10m-1} ( 3 M m ) > 2 10 m − 1 , two distinct three-element subsets of S S S have the same sum. These subsets are disjoint: if they shared exactly one point, the remaining four distinct points would sum to zero, contradicting the Sidon property; if they shared two points, equality of their sums would force the subsets to coincide.
Thus there are six distinct points s 1 , … , s 6 ∈ S s_1,\ldots,s_6\in S s 1 , … , s 6 ∈ S with
s 1 + ⋯ + s 6 = 0. s_1+\cdots+s_6=0. s 1 + ⋯ + s 6 = 0.
Choose s 6 s_6 s 6 as the translation origin and put
S ′ = S + s 6 = { s + s 6 : s ∈ S } . S'=S+s_6=\{s+s_6:s\in S\}. S ′ = S + s 6 = { s + s 6 : s ∈ S } .
Then S ′ S' S ′ is Sidon, contains zero, and linearly spans F 2 10 m − 1 \mathbb{F}_2^{10m-1} F 2 10 m − 1 because S S S affinely spans that space. Moreover, the five distinct nonzero points s 1 + s 6 , … , s 5 + s 6 s_1+s_6,\ldots,s_5+s_6 s 1 + s 6 , … , s 5 + s 6 satisfy
∑ i = 1 5 ( s i + s 6 ) = 0. \sum_{i=1}^{5}(s_i+s_6)=0. i = 1 ∑ 5 ( s i + s 6 ) = 0.
We now follow the construction of Czerwinski and Pott [7 Section 5, before Theorem 5.1] . Form a matrix H H H whose columns are the elements of S ′ ∖ { 0 } S'\setminus\{0\} S ′ ∖ { 0 } and define
C = { c ∈ F 2 M m − 1 : H c T = 0 } . C=\{c\in\mathbb{F}_2^{M_m-1}:Hc^{\mathsf T}=0\}. C = { c ∈ F 2 M m − 1 : H c T = 0 } .
The matrix H H H has rank 10 m − 1 10m-1 10 m − 1 , so C C C has length M m − 1 M_m-1 M m − 1 and dimension
( M m − 1 ) − ( 10 m − 1 ) = M m − 10 m . (M_m-1)-(10m-1)=M_m-10m. ( M m − 1 ) − ( 10 m − 1 ) = M m − 10 m .
Its columns are distinct and nonzero, excluding codewords of weights one and two. A dependence among three columns would, together with zero, contradict the Sidon property of S ′ S' S ′ , and a dependence among four columns would contradict that property directly. Hence C C C has minimum distance at least five.
Finally, the columns corresponding to s 1 + s 6 , … , s 5 + s 6 s_1+s_6,\ldots,s_5+s_6 s 1 + s 6 , … , s 5 + s 6 sum to zero and therefore give a codeword of weight five, so the code has minimum distance exactly 5. □
In F 2 10 m − 1 \mathbb{F}_2^{10m-1} F 2 10 m − 1 , the classical constructions give Sidon sets of size 2 5 m − 1 + 2 ⌊ 5 m / 2 ⌋ 2^{5m-1}+2\lfloor5m/2\rfloor 2 5 m − 1 + 2 ⌊ 5 m /2 ⌋ , see [7 Remark 1.3] . When m m m is odd, the inverse function on F 2 5 m \mathbb{F}_{2^{5m}} F 2 5 m is APN, and its construction gives Sidon sets of size
M m i n v = 2 5 m − 1 + 2 ⌊ 2 5 m / 2 + 1 + 1 4 ⌋ = 2 5 m − 1 + 2 5 m / 2 + O ( 1 ) M_m^{\mathrm{inv}}=2^{5m-1}+2\left\lfloor\frac{2^{5m/2+1}+1}{4}\right\rfloor=2^{5m-1}+2^{5m/2}+O(1) M m inv = 2 5 m − 1 + 2 ⌊ 4 2 5 m /2 + 1 + 1 ⌋ = 2 5 m − 1 + 2 5 m /2 + O ( 1 )
by [7 Theorem 4.3] . The subsequent improvement of the inverse parameters by one point, noted in [7 Section 6] , has the same asymptotic secondary term. These constructions have size 2 5 m − 1 + Θ ( 2 5 m / 2 ) 2^{5m-1}+\Theta(2^{5m/2}) 2 5 m − 1 + Θ ( 2 5 m /2 ) in the dimensions where they apply. In contrast, Theorem 9.1 gives
M m = 2 5 m − 1 + 2 3 m − 1 + 2 2 m − 1 = 2 5 m − 1 + 2 3 m − 1 + o ( 2 3 m ) . M_m=2^{5m-1}+2^{3m-1}+2^{2m-1}=2^{5m-1}+2^{3m-1}+o(2^{3m}). M m = 2 5 m − 1 + 2 3 m − 1 + 2 2 m − 1 = 2 5 m − 1 + 2 3 m − 1 + o ( 2 3 m ) .
To the best of our knowledge, this gives the largest known infinite family of Sidon sets in these ambient dimensions asymptotically, with the best known secondary term.
The corresponding distance-five codes have length N m = M m − 1 N_m=M_m-1 N m = M m − 1 and dimension
k m = M m − 10 m = 2 5 m − 1 + 2 3 m − 1 + 2 2 m − 1 − 10 m . k_m=M_m-10m=2^{5m-1}+2^{3m-1}+2^{2m-1}-10m. k m = M m − 10 m = 2 5 m − 1 + 2 3 m − 1 + 2 2 m − 1 − 10 m .
For the same ambient dimension 10 m − 1 10m-1 10 m − 1 , a spanning Sidon set of size M M M gives a code of dimension M − 10 m M-10m M − 10 m [7 Section 5] . Thus the improvement in Sidon-set size gives the same improvement in code dimension: the secondary term grows from order 2 5 m / 2 2^{5m/2} 2 5 m /2 to 2 3 m − 1 2^{3m-1} 2 3 m − 1 .
To place this in context, let k max ( N , 5 ) k_{\max}(N,5) k m a x ( N , 5 ) be the largest dimension of a binary linear code of length N N N and minimum distance at least five. Shortened double-error-correcting BCH codes and the Hamming bound give, respectively,
N − 2 ⌈ log 2 ( N + 1 ) ⌉ ≤ k max ( N , 5 ) ≤ N − log 2 ( 1 + N + ( N 2 ) ) , N-2\lceil\log_2(N+1)\rceil\leq k_{\max}(N,5)\leq N-\log_2\left(1+N+\binom{N}{2}\right), N − 2 ⌈ log 2 ( N + 1 )⌉ ≤ k m a x ( N , 5 ) ≤ N − log 2 ( 1 + N + ( 2 N ) ) ,
see [21, Ch. 7, Theorem 3, p. 193; Ch. 1, Theorem 6, p. 19]. Consequently,
k max ( N , 5 ) = N − 2 log 2 N + O ( 1 ) . k_{\max}(N,5)=N-2\log_2N+O(1). k m a x ( N , 5 ) = N − 2 log 2 N + O ( 1 ) .
In fact, we can prove that the codes constructed through this construction are at most one dimension away from an optimal code for given ambient dimension and minimum distance 5, which covers exactly the important codes that are 2-error correcting.
Theorem 9.2. Let m ≥ 1 m\geq1 m ≥ 1 , and put
M m = 2 5 m − 1 + 2 3 m − 1 + 2 2 m − 1 , N m = M m − 1 , k m = M m − 10 m . M_m=2^{5m-1}+2^{3m-1}+2^{2m-1},\qquad N_m=M_m-1,\qquad k_m=M_m-10m. M m = 2 5 m − 1 + 2 3 m − 1 + 2 2 m − 1 , N m = M m − 1 , k m = M m − 10 m . The code constructed in Theorem 9.1 has dimension k m k_m k m in F 2 N m \mathbb{F}_2^{N_m} F 2 N m . Every binary linear code C ⊆ F 2 N m C\subseteq\mathbb{F}_2^{N_m} C ⊆ F 2 N m with minimum distance at least five satisfies
dim C ≤ k m + 1. \dim C\leq k_m+1. dim C ≤ k m + 1. Thus our code is within one dimension of optimal among codes in the same ambient space with minimum distance at least five.
Proof. Since N m > 2 5 m − 1 N_m>2^{5m-1} N m > 2 5 m − 1 , we have
1 + N m + ( N m 2 ) = N m 2 + N m + 2 2 > 2 10 m − 3 . 1+N_m+\binom{N_m}{2}=\frac{N_m^2+N_m+2}{2}>2^{10m-3}. 1 + N m + ( 2 N m ) = 2 N m 2 + N m + 2 > 2 10 m − 3 .
The Hamming bound for codes [21 Ch. 1, Theorem 6, p. 19] therefore yields
2 dim C ( 1 + N m + ( N m 2 ) ) ≤ 2 N m , (33) 2^{\dim C}\left(1+N_m+\binom{N_m}{2}\right)\leq2^{N_m}, \tag*{(33)} 2 d i m C ( 1 + N m + ( 2 N m ) ) ≤ 2 N m , (33)
and hence
dim C < N m − 10 m + 3 = k m + 2. \dim C < N_m - 10m + 3 = k_m + 2. dim C < N m − 10 m + 3 = k m + 2.
As dim C \dim C dim C is an integer, dim C ≤ k m + 1 \dim C \le k_m + 1 dim C ≤ k m + 1 . □ \square □
Determining larger Sidon sets or more/better codes with minimum distance 5 remains an open problem, a possible avenue is the construction of APN functions with linearity larger than the one of the Dobbertin APN function.
Declaration of AI use
I obtained the main results of this paper without AI use in the first half of 2026, using the same rough approach shown here but also employing some more complicated tools, using function fields and the theory of zeta functions of elliptic curves. The proof shown here was streamlined and simplified using ChatGPT 6, in particular the use of Dwork’s theorem in its current form was a suggestion made by the AI.
The same AI was also used for editorial help when writing the paper, and to provide literature references.
Acknowledgments
I would like to thank Faruk Göloğlu, who suggested a connection to Kloosterman sums in the very early stages of this project, leading me to the idea to connect the sum to elliptic curves. I also thank Anne Canteaut, Léo Perrin, and Jules Baudrin for some discussions about this project during my visit to INRIA in Paris in the summer of 2026. These discussions in particular led to Lemma 4.1 , which streamlined the proof considerably. I thank INRIA and my hosts for their hospitality during my stay. Department of Mathematics and Statistics, University of South Florida, St. Petersburg, Florida, USA
Email address: lukas.koelsch.math@gmail.com