1 Introduction↩︎

Exceptional polynomials, as a generalization of permutation polynomials over finite fields, play a crucial role in coding theory and cryptography. Let \(\mathbb{F}_q\) be the finite field of \(q\) elements with characteristic \(p\), and \(f\) be a polynomial over \(\mathbb{F}_q\). The polynomial \(f\) is called an exceptional polynomial if \(f\) is a permutation function on infinitely many finite extensions of \(\mathbb{F}_q\).

There are many interesting facts about exceptional polynomials. The state of art results concerning classification of exceptional polynomials is included in Michael Zieve’s survey article in Handbook of Finite Fields [1]. A widely used characterization of exceptional polynomials, firstly introduced by Cohen in [2], is as following:

This property indicates that the exceptional polynomials has a geometric origin: the exceptionality of polynomials is determined by the irreducible decomposition of algebraic curve \(f(x)=f(y)\). This inspired us to examine properties of exceptional polynomials through the lens of algebraic curves. Surprisingly, it seems that we can prove a conjecture of Carlitz-Wan (now a theorem) in a relatively easy way, by considering algebraic curves of the form: \[f(x)-y^d-y^{d-1}=a.\]

The Carlitz-Wan conjecture shows important information on the degrees of exceptional polynomials. The conjecture was proposed by Carlitz and generalized by Wan.

There have been several proofs of Carlitz conjecture and its generalization so far. In [3], a very detailed analysis of the monodromy groups of exceptional polynomials led to a proof of Carlitz’s conjecture. Several years later, Lenstra discovered a simple and elementary proof of Carlitz-Wan’s conjecture, which doesn’t rely on primitive group theory or classification of finite simple groups [4]. The arguments made a more detailed use of the ramification groups at infinity of the polynomials \(f(x)-t\) over \(\mathbb{F}_{q}(t)\). Lenstra presented four different versions of his proof in different settings, however his original proof wasn’t published, only given informally in his lectures. Two other proofs, using the same general strategy, appeared in the appendix of the paper [5] by Guralnick and Müller. Quite recently, the paper [6] also gave quick proofs of Carlitz-Wan.

The main purpose of this paper is to give a new proof of Carlitz-Wan conjecture that is both intuitive and easy to understand. Moreover, the strategy is different from any of the proofs mentioned above. The proof we present below only relies on Weil’s Conjecture for curves over finite fields and a result of Bombieri & Katz. The arrangement of remaining parts is as following: we will introduce basic notions of algebraic geometry and Bombieri & Katz’s result in Section 2, and complete the proof in Section 3.

2 Preliminaries↩︎

2.1 Basic notions of algebraic geometry↩︎

Let \(K\) be an algebraically closed field. We denote by \(\mathbb{A}^2(K)\) the affine space \(K^2\), and by \(\mathbb{P}^2(K)\) the projective plane over \(K^{3}\). Both spaces are endowed with their Zariski topologies over \(K\) respectively, where a closed set is the zero locus of a set of polynomials in \(K[x,y]\), or of a set of homogeneous polynomials in \(K[x_0,x_1,x_2]\). The space \(\mathbb{P}^2(K)\) (with coordinate \(x_0,x_1,x_2\)) can be covered with standard open sets \(\{x_i \neq 0\}\) \((i=0,1,2)\), and each of them can be identified with \(\mathbb{A}^2(K)\). For example, \(\{x_0 \neq 0\}\) can be identified with \(\mathbb{A}^2(K)\) via the map \((x_0:x_1:x_2) \mapsto (x_{1}/x_0,x_2/x_0)\).

An affine curve is the zero locus of a single polynomial \(f = 0\) in \(\mathbb{A}^2(K)\), where \(f \in K[x,y]\). This curve is smooth iff. \(f, \frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}\) doesn’t share common zeros in \(\mathbb{A}^2(K)\). Similarly, a projective curve is the zero locus of a homogeneous polynomial \(f=0\) in \(K[x_0,x_1,x_2]\), and it is smooth iff. it is smooth on each of the standard open sets.

2.2 Lower bound for \(\#X(\mathbb{F}_{q})-q-1\)↩︎

Let \(X\) be a projective smooth curve over \(\mathbb{F}_{q}\) defined by a single homogeneous polynomial \(f \in \mathbb{F}_{q}[x,y,z]\). Denote by \(X(\mathbb{F}_{q})\) the set of \(\mathbb{F}_{q}\)-rational points on \(X\), namely, the set of solutions to \(f = 0\) with coordinates in \(\mathbb{F}_{q}\). The celebrated Weil Conjecture for curves states the following:

One wants to measure how far the quantity \(\#X(\mathbb{F}_{q})\) may differ from the main term \(q+1\). Since \(\alpha_i\) are \(q\)-Weil numbers, we have: \[\lvert \#X(\mathbb{F}_{q})-q-1 \rvert \leq 2gq^{1/2}\] This is the famous Hasse-Weil bound. Intuitively, this bound shows that the quantity \(\#X(\mathbb{F}_{q})\) should be reasonably close to \(q+1\). Additionally, for a fixed \(X\), \(\#X(\mathbb{F}_{q^t})\) shouldn’t stay too close to \(q^t+1\) either (as \(t \to \infty\)), unless \(\#X(\mathbb{F}_{q^t})=q^t+1\):

3 Proof of Conjecture↩︎

Assume that an exceptional polynomial \(f \in \mathbb{F}_{q}[x]\) of degree \(d\) exists, such that \((d,q-1) \neq 1\). Without loss of generality we require there doesn’t exist \(g\) s.t. \(f(x)=g(x)^p\), and \(f(0)=0\). Define a bivariate homogeneous polynomial of degree \(d\) in \(\mathbb{F}_{q}[x,z]\) by \(F(x,z) = z^d f(x/z)\). After possibly replacing \(\mathbb{F}_{q}\) with a finite extension of \(\mathbb{F}_{q}\), we may assume there exists two elements \(0 \neq a,b \in \mathbb{F}_{q}\) such that the projective curve defined in \(\mathbb{P}^2(\overline{\mathbb{F}_{q}})\) (with coordinates \(x,y,z\)) \[X: F(x,z)-y^d-b \cdot y^{d-1}z = az^d.\] is smooth. Indeed, set theoretically, \(X\) can be split into two parts, the finite part \(X_0:= X \cap \{z \neq 0\}\) and the points at infinity \(X_1:=X \cap \{z =0\}\). The finite part is exactly the affine curve \(f(x)-y^d-by^{d-1}=a\), and the points at infinity are \(\{x^d-y^d=0\} \subseteq \mathbb{P}^1(\overline{\mathbb{F}_{q}}) \cong \{z = 0\}\), the projective line over \(\overline{\mathbb{F}_{q}}\).

The curve can be chosen to be smooth on \(\{z=0\}\): If we consider the open set \(\{x=1\}\), then the affine equation is \(F(1,z)-y^d -by^{d-1}z=0\). The partial derivative with respect to \(z\) is \(F_z(1,z) - (ad)z^{d-1} - y^{d-1}\cdot b\). Notice that \(y\) is nonzero on \(\{z=0\}\), hence we can at least change \(b\) to make partial derivative non-vanishing.

On the other hand, on the finite part, we need to choose \(a,b\) such that the partial derivative with respect to \(x,y\), i.e. \((f'(x),-dy^{d-1}-b(d-1)y^{d-2})\) is nonzero. Since either \(d\) or \(d-1\) non-vanishes, the \(y\)-derivative doesn’t vanish except on at most two points \(0\) and \(x_0=\frac{-b(d-1)}{d}\) (if \(p \nmid d\)). We just need to shift \(a\) such that \(f'(x)\neq0\) whenever \(f(x)=a\) or \(f(x)=a+x_0^{d-1}(x_0+b)\).

Note that the property \((d,q-1) \neq 1\) still holds after replacing \(\mathbb{F}_{q}\) by its finite extension.

Since \(f\) is an exceptional polynomial, there exists a tower of finite extensions \(\mathbb{F}_{q} \subseteq k_1 \subseteq k_2 \subseteq \ldots\) such that \(f\) is a permutation polynomial over each \(k_i\). On the finite part \(X_0\) of \(X\), clearly \(\#X_0(k_i) = \#k_i\) since \(f\) permutes \(k_i\).

On the other hand, since \((d,q-1) \neq 1\), we have \(\#\mu_d \cap \mathbb{F}_{q} > 1\), where \(\mu_d\) is the group of \(d\)-th roots of unity in \(\overline{\mathbb{F}_{q}}\). Hence, by the definition of \(X_1\), more than 1 points at infinity are defined over \(\mathbb{F}_{q}\). The same argument also applies to every \(k_i\), since \((d, \#k_i -1) \neq 1\). To sum up, we have \(1 < \#X_1(k_i) \leq d\) for every \(i\).

Write \(\#k_i = \mathbb{F}_{q^{n_i}}\). Since \[\#X(k_i) = \#X_0(k_i)+ \#X_1(k_i) = \#k_i+1+A(n_i).\] We have \(A(n_i) = \#X_1(k_i)-1\) nonzero and bounded by \(d\). As \(n_i \to \infty\), it contradicts Bombieri & Katz’s results. QED

Funding sources↩︎

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Acknowledgement↩︎

The authors thank Michael Zieve for helping us fix the error and offering valuable suggestions in the preparation of our article. The authors also thank Zeyu Lu and Jiaming Zhang for valuable discussions.

References↩︎