1 Introduction
1.1 Background and motivation
The concept of the intersection distribution was initially proposed in [12] for the purpose of studying Kakeya sets in affine planes [20] and projective planes [1]. Indeed, the intersection distribution has been deeply rooted in the study of finite geometry, as many classical configurations in projective planes can be characterized simply by using their intersection distributions [9] (see also [12, Remark 1.4(1)]). Intersection distribution can be defined from two intertwined perspectives: polynomials over finite fields and point sets in the classical projective planes [12, Sect. 1]. Below, we shall describe these two perspectives and their connection. Throughout this paper, we use \(\mathbb {F}_q\) to denote the finite field of order q and f a univariate polynomial over \(\mathbb {F}_q\). For simplicity, we call roots of f in \(\mathbb {F}_q\) as \(\mathbb {F}_q\)-roots of f.
Definition 1.1
(Intersection distribution of polynomials over finite fields) Let \(f \in \mathbb {F}_q[x]\). For \(0 \le i \le q\), defineThe sequence \(v(f):=v(f,q)=(v_i(f,q))_{i=0}^{q}\) is called the intersection distribution of f over \(\mathbb {F}_q\).
$$\begin{aligned} v_i(f):=v_i(f,q)&=\left| \{(b,c) \in \mathbb {F}_q^2 \mid f(x)-bx-c=0\, \hbox {has } i\, \hbox {distinct solutions in }\mathbb {F}_q\}\right| \\&=\left| \{(b,c) \in \mathbb {F}_q^2 \mid f(x)-bx-c\, \hbox {has}\, i\, \mathbb {F}_q\text {-}roots \}\right| . \end{aligned}$$
Remark 1.2
(1)
The intersection distribution v(f, q) depends on the polynomial f and the base field \(\mathbb {F}_q\). Whenever the base field \(\mathbb {F}_q\) is clear, we use v(f) and \(v_i(f)\) to denote the intersection distribution.
(2)
Let \(f(x)=\sum _{i=0}^n a_i x^i \in \mathbb {F}_q\) be a polynomial of degree n. Denote \(g(x)=\left( f(x)-a_1x-a_0\right) /a_n\). It is easy to see that \(v(f)=v(g)\). Therefore, when computing v(f), we may assume that \(a_n=1\) and \(a_1=a_0=0\).
(3)
Given \(f \in \mathbb {F}_q[x]\) with degree n, we have \(v_i(f)=0\) for \(i>n\). So in describing the intersection distribution of f, it is convenient to exclude the zero values when their subscripts exceed the degree of the polynomial.
By Definition 1.1, \(v_i(f)\) counts the number of non-vertical lines in the affine plane \(\textrm{AG}(2,q)\) that intersect the graph \(\{(x,f(x)) \mid x \in \mathbb {F}_q\}\) of f at exactly i points. Note that each vertical line of \(\textrm{AG}(2,q)\) intersects the graph of f at exactly one point. With this respect the intersection distribution of f provides complete information about how all the lines of \(\textrm{AG}(2,q)\) intersect the graph of f over \(\mathbb {F}_q\).
Advertisement
Definition 1.3
(Intersection distribution of point sets in classical projective planes) Let D be a point set of cardinality \(|D|>1\) in \(\textrm{PG}(2,q)\). For each \(0 \le i \le q+1\), define \(u_i(D)\) to be the number of lines in \(\textrm{PG}(2,q)\) that intersect D at exactly i points. The sequence \(u(D)=(u_i(D))_{i=0}^{q+1}\) is called the intersection distribution of D.
The polynomial perspective and the point set perspective of the intersection distribution are closely related. Recall that each polynomial f over \(\mathbb {F}_q\) leads to a point set of cardinality \(q+1\) in the classical projective plane \(\textrm{PG}(2,q)\):The intersection distribution of f determines that of \(S_f\) and vice versa:
$$\begin{aligned} S_f=\left\{ \langle (x,f(x),1) \rangle \mid x \in \mathbb {F}_q\right\} \cup \left\{ \langle (0,1,0) \rangle \right\} . \end{aligned}$$
Result 1.4
[12, Proposition 3.2] Let f be a polynomial over \(\mathbb {F}_q\) and \(S_f\) the associated point set in \(\textrm{PG}(2,q)\). Then we haveand
$$\begin{aligned} v_0(f)=u_0(S_f), v_1(f)=u_1(S_f)-1, v_2(f)=u_2(S_f)-q, \end{aligned}$$
$$\begin{aligned}v_i(f)=u_i(S_f), \hbox { for each } 3 \le i \le q, \hbox { and } u_{q+1}(S_f)=0.\end{aligned}$$
Consequently, articulating the interaction between \(S_f\) and lines in \(\textrm{PG}(2,q)\) boils down to computing the intersection distribution of f. From this perspective, it is a natural problem to determine the intersection distribution of a polynomial over finite fields. As we shall see below, polynomials having very few nonzero values within their intersection distributions usually give rise to elegant geometric and combinatorial objects.
1.2 Intersection distribution of polynomials of degree two and three
There have been some known results regarding the intersection distribution of polynomials. When confined to monomials, the intersection distribution has been settled for a few families of monomials, see [11‐13]. In particular, the intersection distribution of all polynomials of degree two and degree three have been determined [11], for which a brief account follows.
In light of Remark 1.2(2), the following result gives the intersection distribution of all polynomials of degree two.
Advertisement
Result 1.5
For \(f(x)=x^2 \in \mathbb {F}_q[x]\), we have
$$\begin{aligned} v_0(f)=\frac{q(q-1)}{2}, \quad v_1(f)=q, \quad v_2(f)=\frac{q(q-1)}{2}. \end{aligned}$$
(1.1)
Recall that a polynomial \(f \in \mathbb {F}_{2^n}[x]\) is an oval polynomial, or o-polynomial in short, if f is a permutation polynomial and \(f(x)+cx\) is 2-to-1 for each \(c \in \mathbb {F}_{2^n}^*\) [4, 19]. We shall remark that polynomials over \(\mathbb {F}_{2^n}\) with the same intersection distribution as that of \(x^2\) given by Eq. (1.1) are precisely the o-polynomials. o-polynomials play a pivotal role in finite geometry as their classification directly corresponds to the classification of ovals in classical projective planes [4, 19]. Notably, Kai-Uwe Schmidt made significant contribution to this long-standing problem [2].
Remark 1.6
[12, Result 1.7] \(v_0(f)\) is called the non-hitting index of f, indicating the number of lines in the affine plane \(\textrm{AG}(2,q)\) not intersecting the graph of f. We have \(q-1 \le v_0(f) \le \frac{q(q-1)}{2}\). Moreover,Therefore, the non-hitting index \(v_0(f)\) measures the distance from f to linear functions, and to the o-polynomials (when q is even) or to \(x^2\) (when q is odd).
-
\(v_0(f)=q-1\) if and only if f is a linear function;
-
for q even, \(v_0(f)=\frac{q(q-1)}{2}\) if and only if f is an o-polynomial;
Inspired by the intersection distribution viewpoints towards o-polynomials, the authors of [11] determined the intersection distribution of degree three polynomials.
Result 1.7
Let \(f(x)=x^3+ax^2 \in \mathbb {F}_q[x]\), where \(q=p^n\) for some prime p.
1.
If \(p \ne 3\), then we have
$$\begin{aligned} v_0(f)=\frac{q^2-1}{3}, \quad v_1(f)=\frac{q^2-q+2}{2}, \quad v_2(f)=q-1, \quad v_3(f)=\frac{q^2-3q+2}{6}. \end{aligned}$$
(1.2)
2.
If \(p=3\) and \(a=0\), then we have
$$\begin{aligned} v_0(f)=\frac{q(q-1)}{3}, \quad v_1(f)=\frac{q(q+1)}{2}, \quad v_2(f)=0, \quad v_3(f)=\frac{q(q-1)}{6}. \end{aligned}$$
(1.3)
3.
If \(p=3\) and \(a \ne 0\), then we have
$$\begin{aligned} v_0(f)=\frac{q^2}{3}, \quad v_1(f)=\frac{q(q-1)}{2}, \quad v_2(f)=q, \quad v_3(f)=\frac{q(q-3)}{6}. \end{aligned}$$
In view of Remark 1.2(2), Result 1.7 determines the intersection distribution of all degree three polynomials. In parallel to the classification of o-polynomials, the project of classifying all monomials having the same intersection distribution as \(x^3\), which shows in Eq. (1.2) for \(p \ne 3\) and in Eq. (1.3) for \(p=3\), was initiated in [11]. It was asserted in [11] that all such monomials are either the obvious ones or belong to two conjectured families. These two conjectured families were recently confirmed in [13]. It is interesting to note that monomials in these two families produce Steiner triple systems which may be nonisomorphic to the canonical affine triple systems (see [11, Sect. 4]).
1.3 Statement of main results
In summary, the study of the intersection distribution of degree two and degree three polynomials led to interesting geometric and combinatorial objects. In this paper, we proceed to determine the intersection distribution of degree four polynomials. As an application, we present a construction of Steiner systems using polynomials with prescribed intersection distribution. We first set up some notation that will be used throughout the paperWe are now ready to describe the main result.
-
\(q=p^n\) for some prime p and some positive integer n.
-
For \(f, g \in \mathbb {F}_q[x]\), we write \(f \sim g\) if there exists \(a, c \in \mathbb {F}_q^*\) and \(b, d, e \in \mathbb {F}_q\), such that \(g(x)=cf(ax+b)+dx+e\). Obviously if \(f \sim g\), then \(v(f)=v(g)\), namely, f and g have the same intersection distribution.
-
For \(f \in \mathbb {F}_q[x]\), we say that f has i \(\mathbb {F}_q\)-roots if f has exactly i distinct \(\mathbb {F}_q\)-roots, regardless of their multiplicities.
-
For q odd, we use \(\square \) to denote the set of nonzero squares of \(\mathbb {F}_q\) and
to denote the set of nonsquares of \(\mathbb {F}_q\). -
We use \(\alpha \) to denote a primitive elment of \(\mathbb {F}_q\).
-
For even n, we use \(\eta \) to denote a primitive third root of unity in \(\mathbb {F}_{2^n}\). A polynomial \(f \in \mathbb {F}_{2^n}[x]\) is called \(\mathbb {F}_4\)-linearized if \(f(y+z)=f(y)+f(z)\) for all \(y, z \in \mathbb {F}_{2^n}\) and \(f(ay)=af(y)\) for all \(y \in \mathbb {F}_{2^n}\) and \(a \in \mathbb {F}_4\).
-
We use \(\textrm{tr}\) to denote the standard trace function from \(\mathbb {F}_q\) to \(\mathbb {F}_p\).
-
Let P be a proposition, define the delta function$$\begin{aligned} \delta (P)= {\left\{ \begin{array}{ll} 1 & \hbox {if }P\, \hbox {is true,}\\ 0 & \hbox {if }P\, \hbox {is false.} \end{array}\right. } \end{aligned}$$
Theorem 1.8
Let \(\mathbb {F}_q=\mathbb {F}_{p^n}\) and \(f \in \mathbb {F}_q[x]\) be a degree four polynomial. Then one of the following holds.
(I)
If \(f \sim x^4 \in \mathbb {F}_q[x]\), then
(II)
If \(f \sim x^4+x^2 \in \mathbb {F}_q[x]\), then
(III)
If \(p=2\) and \(f \sim x^4+x^3 \in \mathbb {F}_q[x]\), then
$$\begin{aligned} & \left( v_0(f),v_1(f),v_2(f),v_3(f),v_4(f)\right) \\ & \quad = \left( \frac{3q^2-2q}{8}, \frac{2q^2+3q-2}{6}, \frac{q^2-2q+4}{4}, \frac{q-2}{2}, \frac{q^2-6q+8}{24}\right) \end{aligned}$$
(IV)
If \(p \ge 3\) and \(f \sim x^4+\alpha x^2 \in \mathbb {F}_q[x]\), then
Previously, the intersection distribution of degree three polynomials was determined by calculating a finer measure known as the multiplicity distribution (see [11, Def. 1.3] and Def. 5.1 for the precise definition). However, the computation of the multiplicity distribution for degree four polynomials is cumbersome. Instead, we adopted a different and more direct approach in this paper. By analyzing the pattern of roots of degree four polynomials, we are able to determine their intersection distribution without computing the multiplicity distribution. We believe this new method will shed new lights on the computation of intersection distributions for higher degree polynomials.
The rest of the paper is organized as follows. In Sect. 2, we describe some preliminary results about the intersection distribution. In particular, we reduce the determination of the intersection distribution of degree four polynomials to four specific classes of polynomials. In Sect. 3, we prove Theorem 1.8 by computing the intersection distribution of these four classes of polynomials. In Sect. 4, we observe that for n even and \(f \in \mathbb {F}_{2^n}[x]\), if f has the same intersection distribution as \(x^4 \in \mathbb {F}_{2^n}[x]\), then a Steiner system \(S(2,4,2^n)\) follows from f. This motivates us to consider the natural question of determining monomials having the same intersection distribution as \(x^4\). Finally, some concluding remarks and open problems are presented in Sect. 5.
2 Preliminaries
In this section, we describe some preliminary results concerning the intersection distribution. Regarding degree four polynomials, by using “\(\sim \)”, the equivalence relation described in Sect. 1, the determination of intersection distribution boils down to the following four classes of polynomials.
Lemma 2.1
Let \(q=p^n\) and \(f(x) \in \mathbb {F}_q[x]\) be a polynomial of degree four. Then one of the following holds.
(I)
\(f \sim x^4\)
(II)
\(f \sim x^4+x^2\)
(III)
\(p=2\) and \(f \sim x^4+x^3\)
(IV)
p odd and \(f \sim x^4+\alpha x^2\)
Proof
If \(a_3=a_2=0\), then \(f(x)=x^4\), which is Case (I).
If \(a_3=0\) and \(a_2 \ne 0\), then \(f(x)=x^4+a_2x^2\). If \(p=2\), substituting x by \(a_2^{q/2}x\), we have \(f \sim x^4+x^2\), which is Case (II). If p is odd, we have either \(a_2=\alpha ^{2k}\) or \(a_2=\alpha ^{2k+1}\) for some k. By substituting x by \(\alpha ^k x\), we have either \(f \sim x^4+x^2\), which is Case (II) or \(f \sim x^4+\alpha x^2\) which is Case (IV).
If \(a_3a_2 \ne 0\), then \(f(x)=x^4+a_3x^3+a_2x^2\). If \(p=2\), substituting x by \(x+\frac{a_2}{a_3}\), we have \(f \sim x^4+a_3x^3+\frac{a_2^2}{a_3}x+f(\frac{a_2}{a_3}) \sim x^4+x^3\), which is Case (III). If p is odd, substituting x by \(x-\frac{a_3}{4}\), we have \(f \sim x^4+\left( a_2-\frac{3a_3^2}{8}\right) x^2+\left( \frac{a_3^2-4a_2a_3}{8}\right) x+f\left( -\frac{a_3}{4}\right) \). Depending on the conditions that \(a_2-\frac{3a_3^2}{8}=0\), \(a_2-\frac{3a_3^2}{8} \in \square \), or
, we have \(f \sim x^4\) (Case (I)), \(f \sim x^4+x^2\) (Case (II)), or \(f \sim x^4+\alpha x^2\) (Case (IV)) respectively. This proves Lemma 2.1. \(\square \)
, we have \(f \sim x^4\) (Case (I)), \(f \sim x^4+x^2\) (Case (II)), or \(f \sim x^4+\alpha x^2\) (Case (IV)) respectively. This proves Lemma 2.1. \(\square \)The following three identities, which have been essentially stated in [12, Proposition 2.1] (see also [9, Lemma 12.1]), are useful in the computation of intersection distribution.
Proposition 2.2
[12, Proposition 2.1] Let f be a polynomial over \(\mathbb {F}_q\). The following equations hold.
$$\begin{aligned} \sum _{i=0}^{q} v_i(f)&=q^2, \\ \sum _{i=1}^{q} iv_i(f)&=q^2, \\ \sum _{i=2}^{q} i(i-1)v_i(f)&=q(q-1). \end{aligned}$$
Given a degree four polynomial f, according to Remark 1.2(3), the only possibly nonzero values within v(f) are \(v_i(f)\), \(0 \le i \le 4\). In connection with Proposition 2.2, it suffices to determine \(v_2(f)\) and \(v_3(f)\). We shall compute \(v_2(f)\) and \(v_3(f)\) directly by analyzing the patterns of \(\mathbb {F}_q\)-roots of f. For two positive integers \(n_1, n_2\), we defineHere we say a polynomial f(x) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [n_1], r_2 [n_2] \}\) if \(r_1\) and \(r_2\) are two distinct \(\mathbb {F}_q\)-roots of f with multiplicity \(n_1\) and \(n_2\) respectively, and f has no other \(\mathbb {F}_q\)-roots. Likewise, we can define \(v_{[n_1,n_2,n_3]}(f)\) for \(n_1, n_2, n_3 \ge 1\). It is easy to prove the following.
$$\begin{aligned} v_{[n_1,n_2]}(f)=\left| \{(b,c) \in \mathbb {F}_q^2 \mid f(x)-bx-c\, \hbox {has } \mathbb {F}_q\text {-}\hbox {roots of pattern} \{ r_1 [n_1], r_2 [n_2] \} \}\right| . \end{aligned}$$
Lemma 2.3
Let \(f \in \mathbb {F}_q[x]\) be a polynomial of degree four. Let \(b, c \in \mathbb {F}_q\).
(1)
\(f(x)-bx-c\) has three \(\mathbb {F}_q\)-roots if and only if \(f(x)-bx-c\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [2], r_2 [1], r_3 [1] \}\). Thus, \(v_3(f)=v_{[2,1,1]}(f)\).
(2)
\(f(x)-bx-c\) has two \(\mathbb {F}_q\)-roots if and only if one of the following holds: We have \(v_2(f)=v_{[2,2]}(f)+v_{[3,1]}(f)+v_{[1,1]}(f)\).
(2a)
\(f(x)-bx-c\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [2], r_2 [2] \}\).
(2b)
\(f(x)-bx-c\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [3], r_2 [1] \}\).
(2c)
\(f(x)-bx-c\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [1], r_2 [1] \}\).
We remark that for degree four polynomials, their pattern of \(\mathbb {F}_q\)-roots is closely related to the work [14], which describes the factorization of degree four polynomial over \(\mathbb {F}_{2^n}\) in terms of the roots of a related degree three polynomial. To conclude this section, we present several auxiliary results. The first lemma is considered folklore and will be frequently referenced without explicit mention.
Lemma 2.4
Let \(q=p^n\) and \(f(x)=x^2+a_1x+a_0 \in \mathbb {F}_q[x]\).
(1)
\(p=2\): f has two \(\mathbb {F}_q\)-roots if and only if \(\textrm{tr}\left( \frac{a_0}{a_1^2}\right) =0\); f is irreducible over \(\mathbb {F}_q\) if and only if \(\textrm{tr}\left( \frac{a_0}{a_1^2}\right) =1\).
(2)
p odd: f has two \(\mathbb {F}_q\)-roots if and only if \(a_1^2-4a_0 \in \square \); f is irreducible over \(\mathbb {F}_q\) if and only if
.
.For odd q, set \(C_0^{(2,q)}=\square \) and
. Recall that the cyclotomic numbers of order 2 are defined asThe cyclotomic numbers of order 2 are well known, see for instance [18].
. Recall that the cyclotomic numbers of order 2 are defined as$$\begin{aligned} (i,j)_q=\left| (1+C_i^{(2,q)}) \cap C_j^{(2,q)}\right| , \quad 0 \le i,j \le 1. \end{aligned}$$
Lemma 2.5
Let q be an odd prime power.
(1)
If \(-1 \in \square \), we have
$$\begin{aligned} (0,0)_q=\frac{q-5}{4}, \quad (0,1)_q=(1,0)_q=(1,1)_q=\frac{q-1}{4}. \end{aligned}$$
(2)
If
, we have
, we have $$\begin{aligned} (0,1)_q=\frac{q+1}{4}, \quad (0,0)_q=(1,0)_q=(1,1)_q=\frac{q-3}{4}. \end{aligned}$$
The next lemma is a little technical and will be used later. Its proof is presented in the Appendix.
Lemma 2.6
Let \(p>3\) and \(q=p^n\).
(1)
(2)
(3)
3 The intersection distribution of degree four polynomials
In this section, we shall prove Theorem 1.8 by computing \(v_2(f)\) and \(v_3(f)\) directly for the four classes of polynomials in Lemma 2.1. We first deal with \(v_3(f)\) in the following lemma.
Lemma 3.1
Suppose \(f \in \mathbb {F}_q[x]\) is a degree four polynomial with \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [2], r_2 [1], r_3 [1] \}\).
(I)
If \(f(x)=x^4\), then
(II)
If \(f(x)=x^4+x^2\), then
(III)
If \(p=2\) and \(f(x)=x^4+x^3\), then \(v_3(f)=\frac{q-2}{2}\).
(IV)
If \(p \ge 3\) and \(f(x)=x^4+\alpha x^2\), then
Proof
We shall only prove part (II) for \(f(x)=x^4+x^2\), as the proofs of all the other cases are very similar. By Lemma 2.3(1), we have \(v_3(f)=v_{[2,1,1]}(f)\), whereSuppose \((a_1,a_0) \in v_{[2,1,1]}(f)\) and \(x^4+x^2+a_1x+a_0\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [2], r_2 [1], r_3 [1] \}\). Then \(x^4+x^2+a_1x+a_0=(x-r_1)^2(x-r_2)(x-r_3)\), by comparing the coefficients on both sides, we havewhere \(r_1, r_2, r_3\) are distinct elements in \(\mathbb {F}_q\). Since counting the number of elements \((a_1,a_0) \in v_{[2,1,1]}(f)\) is equivalent to counting the number of such \((r_1,r_2,r_3)\)’s, we haveIf \(p=2\), \(r_2+r_3=-2r_1\) implies \(r_2=r_3\), contradicting that \(r_1\), \(r_2\), \(r_3\) are distinct. Thus, \(v_{[2,1,1]}(f)=0\).
$$\begin{aligned} v_{[2,1,1]}(f)= & \left| \{ (a_1,a_0) \in \mathbb {F}_q^2 \mid x^4+x^2+a_1x+a_0 \right. \\ & \left. \hbox { has } \mathbb {F}_q\text {-}\hbox {roots of pattern} \{ r_1 [2], r_2 [1], r_3 [1] \} \}\right| . \end{aligned}$$
$$\begin{aligned} r_2+r_3=-2r_1, r_2r_3-3r_1^2=1, -2r_1^3+2r_1r_2r_3=-a_1, r_1^2r_2r_3=a_0 \end{aligned}$$
$$\begin{aligned} v_{[2,1,1]}(f)&=\frac{1}{2}\left| \{ (r_1,r_2,r_3) \in \mathbb {F}_q^3 \mid r_2+r_3=-2r_1, r_2r_3-3r_1^2=1, r_1, r_2, r_3\, \hbox {distinct} \}\right| . \end{aligned}$$
If \(p=3\), we haveIf \(p>3\), thenIt is easy to see from the above thatBy using the cyclotomic numbers \((i,j)_q\) and Lemma 2.5, we conclude that
This completes the proof for part (II) of Lemma 3.1. \(\square \)
$$\begin{aligned} v_{[2,1,1]}(f)&=\frac{1}{2}\left| \{ (r_1,r_2,r_3) \in \mathbb {F}_q^3 \mid r_2+r_3=r_1, r_2r_3=1, r_1, r_2, r_3\, \hbox {distinct} \}\right| \\&=\frac{1}{2}\left| \{ (r_1,r_2) \in \mathbb {F}_q^2 \mid r_2+r_2^{-1}=r_1, r_2 \not \in \{ 0,1,-1\} \}\right| \\&=\frac{1}{2}\left| \{ r_2 \in \mathbb {F}_q\mid r_2 \not \in \{ 0,1,-1\} \}\right| =\frac{q-3}{2}. \end{aligned}$$
$$\begin{aligned} v_{[2,1,1]}(f)&=\frac{1}{2}\left| \{ (r_1,r_2,r_3) \in \mathbb {F}_q^3 \mid r_2+r_3=-2r_1, r_2r_3=3r_1^2+1, r_1, r_2, r_3\, \hbox {distinct} \}\right| \\&=\frac{1}{2}\left| \{ (r_1,r_2,r_3) \in \mathbb {F}_q^3 \mid r_2, r_3\, \hbox {are two distinct roots of }\right. \\&\quad \qquad \quad x^2\left. +2r_1x+3r_1^2+1 \,\textrm{in}\, \mathbb {F}_q\setminus \{r_1\} \}\right| . \end{aligned}$$
$$\begin{aligned} v_{[2,1,1]}(f)&=\frac{1}{2}\left| \{ (r_1,r_2,r_3) \in \mathbb {F}_q^3 \mid r_2, r_3\, \hbox {are two distinct roots of} \right. \\&\quad \qquad \quad x^2\left. +2r_1x+3r_1^2+1, 6r_1^2 \ne -1 \}\right| \\&=\frac{1}{2} \cdot 2 \left| \{ r_1 \in \mathbb {F}_q\mid -2r_1^2-1 \in \square , 6r_1^2 \ne -1 \}\right| \\&=2 \cdot \left| \{ u \in \square \mid -2u-1 \in \square , 6u \ne -1 \}\right| + \delta (-1 \in \square ) \\&=2 \cdot \left( |\{ u \in \square \mid -2u-1 \in \square \}|-\delta (-6 \in \square )\right) + \delta (-1 \in \square ). \end{aligned}$$
Next we consider \(v_2(f)\). By Lemma 2.3(2), it suffices to calculate \(v_{[2,2]}(f)\), \(v_{[3,1]}(f)\), and \(v_{[1,1]}(f)\). Below we shall compute each of them for the four classes of polynomials in Lemma 2.1. We first consider \(v_{[2,2]}(f)\).
Lemma 3.2
Let \(f \in \mathbb {F}_q[x]\) be a degree four polynomial with \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [2], r_2 [2] \}\).
(I)
If \(f(x)=x^4\), then \(v_{[2,2]}(f)=0\).
(II)
If \(f(x)=x^4+x^2\), then
(III)
If \(p=2\) and \(f(x)=x^4+x^3\), then \(v_{[2,2]}(f)=0\).
(IV)
If \(p \ge 3\) and \(f(x)=x^4+\alpha x^2\), then
Proof
We shall only prove part (IV) with \(p \ge 3\) and \(f(x)=x^4+\alpha x^2\), as the remaining cases are either similar or simpler. Note thatSuppose \((a_1,a_0) \in v_{[2,2]}(f)\) and \(x^4+\alpha x^2+a_1x+a_0\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [2], r_2 [2] \}\). Since \(x^4+\alpha x^2+a_1x+a_0=(x-r_1)^2(x-r_2)^2\), comparing the coefficients on both sides, we haveSo we haveIf \(p=3\), \(-2r_1^2=r_1^2=\alpha \), which is impossible. Thus, \(v_{[2,2]}(f)=0\).
$$\begin{aligned} v_{[2,2]}(f)=\left| \{ (a_1,a_0) \in \mathbb {F}_q^2 \mid x^4+\alpha x^2+a_1x+a_0\, \hbox {has}\, \mathbb {F}_q\text {-}\hbox {roots of pattern}\, \{ r_1 [2], r_2 [2] \} \}\right| . \end{aligned}$$
$$\begin{aligned} -2(r_1+r_2)=0, r_1^2+r_2^2+4r_1r_2=\alpha , -2(r_1^2r_2+r_1r_2^2)=a_1, r_1^2r_2^2=a_0, r_1 \ne r_2. \end{aligned}$$
$$\begin{aligned} v_{[2,2]}(f)&=\frac{1}{2}\left| \{ (r_1,r_2) \in \mathbb {F}_q^2 \mid r_2=-r_1, -2r_1^2=\alpha , r_1\ne 0 \}\right| \\&=\frac{1}{2}\left| \{ r_1 \in \mathbb {F}_q\mid -2r_1^2=\alpha , r_1\ne 0 \}\right| . \end{aligned}$$
If \(p>3\),
Then the proof for part (IV) is complete. \(\square \)
Next we compute \(v_{[3,1]}(f)\) for the four classes of polynomials in Lemma 2.1.
Lemma 3.3
Let \(f \in \mathbb {F}_q[x]\) be a degree four polynomial with \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [3], r_2 [1] \}\).
(I)
If \(f(x)=x^4\), then
$$\begin{aligned} v_{[3,1]}(f)= {\left\{ \begin{array}{ll} 0 & \hbox {if }p=2 \\ q-1 & \hbox {if }p=3 \\ 0 & \hbox {if }p>3 \end{array}\right. } \end{aligned}$$
(II)
If \(f(x)=x^4+x^2\), then
(III)
If \(p=2\) and \(f(x)=x^4+x^3\), then \(v_{[3,1]}(f)=1\).
(IV)
If \(p \ge 3\) and \(f(x)=x^4+\alpha x^2\), then
Proof
We shall only prove part (I) with \(f(x)=x^4\), as the remaining cases are either similar or simpler. Note thatSuppose \((a_1,a_0) \in v_{[3,1]}(f)\) and \(x^4+a_1x+a_0\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [3], r_2 [1] \}\). Since \(x^4+a_1x+a_0=(x-r_1)^3(x-r_2)\), comparing the coefficients on both sides, we haveHence,If \(p=2\), \(r_2=-3r_1\) implies \(r_1=r_2\), contradicting \(r_1 \ne r_2\). Thus, \(v_{[3,1]}(f)=0\).
$$\begin{aligned} v_{[3,1]}(f)=\left| \{ (a_1,a_0) \in \mathbb {F}_q^2 \mid x^4+a_1x+a_0\, \hbox {has}\, \mathbb {F}_q\text {-}\hbox {roots of pattern}\, \{ r_1 [3], r_2 [1] \} \}\right| . \end{aligned}$$
$$\begin{aligned} 3r_1+r_2=0, 3(r_1^2+r_1r_2)=0, -(r_1^3+3r_1^2r_2)=a_1, r_1^3r_2=a_0, r_1 \ne r_2. \end{aligned}$$
$$\begin{aligned} v_{[3,1]}(f)&=\left| \{ (r_1,r_2) \in \mathbb {F}_q^2 \mid r_2=-3r_1, -6r_1^2=0, r_1 \ne r_2 \}\right| . \end{aligned}$$
If \(p=3\), \(v_{[3,1]}(f)=|\{ (r_1,r_2) \in \mathbb {F}_q^2 \mid r_2=0, r_1 \ne 0 \}|=q-1\).
If \(p>3\), then \(r_1=r_2=0\). Thus, \(v_{[3,1]}(f)=0\).
Then the proof for part (I) is complete. \(\square \)
Below we calculate \(v_{[1,1]}(f)\) for the four classes of polynomials in Lemma 2.1.
Lemma 3.4
Let \(f \in \mathbb {F}_q[x]\) be a degree four polynomial with \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [1], r_2 [1] \}\).
(I)
If \(f(x)=x^4\), then
(II)
If \(f(x)=x^4+x^2\), then
(III)
If \(p=2\) and \(f(x)=x^4+x^3\), then \(v_{[1,1]}(f)=\frac{q^2-2q}{4}\).
(IV)
If \(p \ge 3\) and \(f(x)=x^4+\alpha x^2\), then
Proof
We shall only prove part (II) and part (III), as the remaining cases are either similar or simpler.
For part (II), \(f(x)=x^4+x^2\). Note thatSuppose \((a_1,a_0) \in v_{[1,1]}(f)\) and \(x^4+x^2+a_1x+a_0\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [1], r_2 [1] \}\). Since \(x^4+x^2+a_1x+a_0=(x-r_1)(x-r_2)(x^2+sx+t)\), comparing the coefficients on both sides, we haveTherefore,If \(p=2\), \(x^2+(r_1+r_2)x+r_1^2+r_2^2+r_1r_2+1\) with \(r_1 \ne r_2\) is irreducible over \(\mathbb {F}_q\) if and only if \(\textrm{tr}\big (\frac{r_1^2+r_2^2+r_1r_2+1}{(r_1+r_2)^2}\big )=\textrm{tr}(1)+\textrm{tr}\big (\frac{r_1r_2}{r_1^2+r_2^2}\big )+\textrm{tr}\big (\frac{1}{(r_1+r_2)^2}\big )=\textrm{tr}(1)+\textrm{tr}\big (\frac{1}{r_1+r_2}\big ) \ne 0\). Recall thatWe haveIf \(p=3\), \(x^2+(r_1+r_2)x+r_1^2+r_2^2+r_1r_2+1\) with \(r_1 \ne r_2\) is irreducible over \(\mathbb {F}_q\) if and only if
. Hence,
Note that
Recall that for \(p=3\), \(-1 \in \square \) if and only if n is even, and
if and only if n is odd. We can deriveIf \(p>3\), \(x^2+(r_1+r_2)x+r_1^2+r_2^2+r_1r_2+1\) with \(r_1 \ne r_2\) is irreducible over \(\mathbb {F}_q\) if and only if
.
Therefore,
where the last equation follows from Lemma 2.6(2). The proof for part (II) is now complete.
$$\begin{aligned} v_{[1,1]}(f)=\left| \{ (a_1,a_0) \in \mathbb {F}_q^2 \mid x^4+x^2+a_1x+a_0\, \hbox {has}\, \mathbb {F}_q\text {-}\hbox {roots of pattern}\, \{ r_1 [1], r_2 [1] \} \}\right| . \end{aligned}$$
$$\begin{aligned} & r_1+r_2=s, r_1^2+r_2^2+r_1r_2+1=t,\\ & \quad -(r_1^3+r_1^2r_2+r_1r_2^2+r_2^3+r_1+r_2)=a_1,\\ & \quad r_1^3r_2+r_1r_2^3+r_1^2r_2^2+r_1r_2=a_0. \end{aligned}$$
$$\begin{aligned} v_{[1,1]}(f)= & \frac{1}{2}\bigl |\{ (r_1,r_2,s,t) \in \mathbb {F}_q^4 \mid r_1+r_2=s, r_1^2+r_2^2+r_1r_2+1=t,\\ & \qquad x^2+sx+t\,\, \hbox {irreducible over}\,\, \mathbb {F}_q, r_1 \ne r_2\}\ \bigr |\\= & \frac{1}{2}\left| \{ (r_1,r_2) \in \mathbb {F}_q^2 \mid x^2+(r_1+r_2)x+r_1^2+r_2^2+r_1r_2+1 \right. \\ & \qquad \left. \hbox {irreducible over }\mathbb {F}_q, r_1 \ne r_2 \}\right| . \end{aligned}$$
$$\begin{aligned} \left| \{ u \in \mathbb {F}_q^* \mid \textrm{tr}(\frac{1}{u}) \ne \textrm{tr}(1) \}\right| = {\left\{ \begin{array}{ll} \frac{q}{2} & \hbox {if }n\, \hbox {even} \\ \frac{q-2}{2} & \hbox {if }n\, \hbox {odd} \end{array}\right. } \end{aligned}$$
$$\begin{aligned} v_{[1,1]}(f)&=\frac{1}{2}\left| \{ (r_1,r_2) \in \mathbb {F}_q^2 \mid \textrm{tr}\big (\frac{1}{r_1+r_2}\big ) \ne \textrm{tr}(1), r_1 \ne r_2 \}\right| \\&\quad = {\left\{ \begin{array}{ll} \frac{1}{2}\cdot \frac{q}{2}\cdot q=\frac{q^2}{4} & \hbox {if }p=2, n\, \hbox {even} \\ \frac{1}{2}\cdot \frac{q-2}{2}\cdot q=\frac{q^2-2q}{4} & \hbox {if }p=2, n\, \hbox {odd}. \end{array}\right. } \end{aligned}$$
. Hence,
if and only if n is odd. We can derive$$\begin{aligned} v_{[1,1]}(f)= {\left\{ \begin{array}{ll} \frac{1}{2}(\frac{q^2-2q+1}{2}-\frac{q-1}{2})=\frac{q^2-3q+2}{4} & \hbox {if }p=3, n\, \hbox {even} \\ \frac{1}{2}(\frac{q^2+1}{2}-\frac{q-1}{2})=\frac{q^2-q+2}{4} & \hbox {if }p=3, n\, \hbox {odd}. \end{array}\right. } \end{aligned}$$
.
Therefore,
For part (III), \(p=2\) and \(f(x)=x^4+x^3\). Note thatSuppose \((a_1,a_0) \in v_{[1,1]}(f)\) and \(x^4+x^3+a_1x+a_0\) has \(\mathbb {F}_q\)-roots of pattern \(\{ r_1 [1], r_2 [1] \}\). Since \(x^4+x^3+a_1x+a_0=(x-r_1)(x-r_2)(x^2+sx+t)\), comparing the coefficients on both sides, we haveTherefore,Since \(p=2\), \(x^2+(r_1+r_2+1)x+r_1^2+r_2^2+r_1r_2+r_1+r_2\) with \(r_1 \ne r_2\) is irreducible over \(\mathbb {F}_q\) if and only if \(r_1+r_2 \not \in \{ 0,1\}\) and \(\textrm{tr}\big (\frac{r_1^2+r_2^2+r_1r_2+r_1+r_2}{(r_1+r_2+1)^2}\big )=\textrm{tr}\big (\frac{r_1^2+r_2^2+r_1r_2}{(r_1+r_2+1)^2}\big )+\textrm{tr}\big (\frac{r_1+r_2}{(r_1+r_2+1)^2}\big )=\textrm{tr}\big (\frac{r_1^2+r_2^2+r_1r_2}{r_1^2+r_2^2+1}\big )=1\). Since \(r_1+r_2 \not \in \{0,1\}\), we set \(r_2=r_1+a\) with \(a \not \in \{ 0,1 \}\). Substituting \(r_2\) with \(r_1+a\), we haveThus, \(\textrm{tr}\big (\frac{r_1^2+r_2^2+r_1r_2}{r_1^2+r_2^2+1}\big )=\textrm{tr}\big (\frac{a^2+r_1}{a^2+1}\big )\). Consequently,Then the proof for part (III) is complete. \(\square \)
$$\begin{aligned} v_{[1,1]}(f)=\left| \{ (a_1,a_0) \in \mathbb {F}_q^2 \mid x^4+x^3+a_1x+a_0\, \hbox {has}\, \mathbb {F}_q\text {-}\hbox {roots of pattern}\, \{ r_1 [1], r_2 [1] \} \}\right| . \end{aligned}$$
$$\begin{aligned}&r_1+r_2+1=s, r_1^2+r_2^2+r_1r_2+r_1+r_2=t, \\&r_1^3+r_1^2r_2+r_1r_2^2+r_2^3+r_1^2+r_2^2+r_1r_2=a_1, r_1^3r_2+r_1r_2^3+r_1^2r_2^2+r_1^2r_2+r_1r_2^2=a_0. \end{aligned}$$
$$\begin{aligned} & v_{[1,1]}(f)\\= & \frac{1}{2}\bigl |\{ (r_1,r_2,s,t) \in \mathbb {F}_q^4 \mid r_1+r_2+1=s, r_1^2+r_2^2+r_1r_2+r_1+r_2=t,\\ & \quad \qquad x^2+sx+t \hbox { irreducible over}\, \mathbb {F}_q, r_1 \ne r_2 \}\bigr |\\= & \frac{1}{2}\bigl |\{ (r_1,r_2) \in \mathbb {F}_q^2 \mid \\ & \qquad \quad x^2+(r_1+r_2+1)x+r_1^2+r_2^2+r_1r_2+r_1+r_2\,\, \hbox {irreducible over }\mathbb {F}_q, r_1 \ne r_2 \}\bigr |. \end{aligned}$$
$$\begin{aligned} \frac{r_1^2+r_2^2+r_1r_2}{r_1^2+r_2^2+1}= & \frac{r_1^2+(r_1+a)^2+r_1(r_1+a)}{r_1^2+(r_1+a)^2+1}\\= & \frac{a^2+r_1^2+ar_1}{a^2+1}=\big (\frac{r_1}{a+1}\big )^2+\frac{r_1}{a+1}+\frac{a^2+r_1}{a^2+1}. \end{aligned}$$
$$\begin{aligned} v_{[2,2]}(f)=\frac{1}{2}\left| \{ (r_1,a) \in \mathbb {F}_q^2 \mid a \not \in \{ 0,1 \}, \textrm{tr}\big (\frac{a^2+r_1}{a^2+1}\big )=1\}\right| =\frac{1}{2}\cdot (q-2)\cdot \frac{q}{2}=\frac{q^2-2q}{4}. \end{aligned}$$
We are now ready to prove Theorem 1.8.
Proof
(Proof of Theorem 1.8) Let \(f \in \mathbb {F}_q[x]\) be a degree four polynomial. By Lemma 2.1, we can assume without loss of generality that f belongs to one of the four classes of polynomials in Theorem 1.8. Combining Lemma 3.2, Lemma 3.3, Lemma 3.4, and Lemma 2.3(2), we obtain \(v_2(f)\). Moreover, \(v_3(f)\) follows from Lemma 3.1. Employing the equations in Proposition 2.2, \(v_2(f)\), and \(v_3(f)\), we derive the intersection distribution of f. \(\square \)
4 Steiner systems \(S(2,4,2^n)\) and \(x^4\)-like polynomials
As we observed in Sect. 1, polynomials with simple intersection distributions often lead to elegant geometrical and combinatorial structures. In this section, we observe that certain polynomials having the same intersection distribution as \(x^4\) generate Steiner systems. For simplicity, we use \(x^4\)-like polynomials to refer to polynomials having the same intersection distribution as \(x^4\).
Recall that a Steiner system S(2, 4, v) is a set system \((\mathcal {V},\mathcal {B})\), where \(\mathcal {V}\) is a point set of v elements, and \(\mathcal {B}\) is a block set consisting of distinct 4-subsets, such that every two points are contained in exactly one block. Below, we note some well known facts about Steiner systems S(2, 4, v), which can be found in the excellent survey [16] (see also [8]).
Remark 4.1
(1)
A Steiner system S(2, 4, v) exists if and only if \(v \equiv 1, 4 \pmod {12}\). Therefore, an \(S(2,4,2^n)\) exists if and only if \(n \ge 2\) is even.
(2)
Let n be even. Let \(\textrm{AG}(\frac{n}{2},4)\) be the \(\frac{n}{2}\)-dimensional affine space over \(\mathbb {F}_4\). Let \(\mathcal {V}\) be the set of all points in \(\textrm{AG}(\frac{n}{2},4)\). Let \(\mathcal {B}\) be the set of all lines, namely, all one-dimensional affine space, in \(\textrm{AG}(\frac{n}{2},4)\). Recall that \(\eta \) is a primitive third root of unity in \(\mathbb {F}_{2^n}\). We have The set system \((\mathcal {V},\mathcal {B})\) is a Steiner system \(S(2,4,2^n)\). This point-line incidence in the affine space \(\textrm{AG}(\frac{n}{2},4)\) gives the canonical example of \(S(2,4,2^n)\), which we call the affine Steiner system \(S(2,4,2^n)\).
$$\begin{aligned} \mathcal {B}=\{ \{ y, y+z, y+\eta z, y+\eta ^2 z\} \mid y \in \mathbb {F}_{2^n}, z \in \mathbb {F}_{2^n}^* \}. \end{aligned}$$
(4.1)
(3)
Given two S(2, 4, v) Steiner systems \((\mathcal {V}_1,\mathcal {B}_1)\) and \((\mathcal {V}_2,\mathcal {B}_2)\), they are called isomorphic if there exists a bijection between point sets \(\mathcal {V}_1\) and \(\mathcal {V}_2\), which also induces a bijection between the blocks \(\mathcal {B}_1\) and \(\mathcal {B}_2\). The construction and classification of nonisomorphic S(2, 4, v) Steiner systems have been a long-standing problem.
For all \(v \equiv 1, 4 \pmod {12}\), the existence of S(2, 4, v) was established by Hanani [7] using inductive constructions. On the other hand, the lack of a simple direct proof of the existence of S(2, 4, v) was observed in [16, p. 3]. Finding a direct proof of the existence of S(2, 4, v) “appears very desirable” [16, p. 3] and was left as an open problem in [16, p. 23].
On this note, we describe a simple direct construction of \(S(2,4,2^n)\) using \(x^4\)-like polynomials over \(\mathbb {F}_{2^n}\) with n even.
Theorem 4.2
Let n be even. Let \(f \in \mathbb {F}_{2^n}[x]\) be a \(x^4\)-like polynomial. Let \(\mathcal {V}=\mathbb {F}_{2^n}\) andThen \((\mathcal {V},\mathcal {B}_f)\) is a \(S(2,4,2^n)\). Moreover, if \(f(0)=0\), then \((\mathcal {V},\mathcal {B}_f)\) is the affine Steiner system \(S(2,4,2^n)\) if and only if f is an \(\mathbb {F}_4\)-linearized polynomial.
$$\begin{aligned} \mathcal {B}_f= & \{ \{x_1, x_2, x_3, x_4\} \mid x_1, x_2, x_3, x_4 \in \mathbb {F}_{2^n}\, \hbox {distinct}, \\ & \quad \frac{f(x_2)-f(x_1)}{x_2-x_1}=\frac{f(x_3)-f(x_1)}{x_3-x_1}=\frac{f(x_4)-f(x_1)}{x_4-x_1}\}. \end{aligned}$$
Proof
Note that \(\mathcal {B}_f\) consists of all the intersecting points between the graph \(\{ (x,f(x)) \mid x \in \mathbb {F}_{2^n} \}\) of f and the lines in \(\textrm{AG}(2,\mathbb {F}_{2^n})\), whenever a line in \(\textrm{AG}(2,\mathbb {F}_{2^n})\) meets the graph at exactly four points. Set \(q=2^n\). Since \(f \in \mathbb {F}_{2^n}[x]\) is a \(x^4\)-like polynomial with n even, then by Theorem 1.8(I),Suppose \(x_1, x_2 \in \mathbb {F}_{2^n}\) are two distinct elements. Since \(v_2(f)=v_3(f)=0\) and \(v_i(f)=0\) for \(i>4\), the two distinct points \((x_1,f(x_1))\) and \((x_2,f(x_2))\) uniquely determines a line in \(\textrm{AG}(2,\mathbb {F}_{2^n})\) intersecting \(\{ (x,f(x)) \mid x \in \mathbb {F}_{2^n} \}\) at exactly four points. Thus, \(x_1\) and \(x_2\) are contained in a unique 4-subset in \(\mathcal {B}_f\). Consequently, \((\mathcal {V},\mathcal {B}_f)\) is a \(S(2,4,2^n)\).
$$\begin{aligned} v(f)=\left( v_0(f),v_1(f),v_2(f),v_3(f),v_4(f)\right) =\left( \frac{q^2-q}{4}, \frac{2q^2+q}{3}, 0, 0, \frac{q^2-q}{12}\right) . \end{aligned}$$
For the second part of the theorem, by the definition of \(\mathcal {B}_f\), assuming \(f(0)=0\) does not lose any generality. If f is \(\mathbb {F}_4\)-linearized, for \(\{ x_1, x_2, x_3, x_4\} \in \mathcal {B}_f\), \(x_3=\eta ^2x_1+\eta x_2\) and \(x_4=\eta x_1+\eta ^2 x_2\) satisfying \(\frac{f(x_2)-f(x_1)}{x_2-x_1}=\frac{f(x_3)-f(x_1)}{x_3-x_1}=\frac{f(x_4)-f(x_1)}{x_4-x_1}\). Since \((\mathcal {V},\mathcal {B}_f)\) is a \(S(2,4,2^n)\), \(x_3\) and \(x_4\) are uniquely determined by \(x_1\) and \(x_2\). Thus, \(\{ x_1, x_2, x_3, x_4\}=\{ x_1, x_1+(x_1+x_2), x_1+\eta (x_1+x_2), x_1+\eta ^2(x_1+x_2) \}\). Consequently, \(\mathcal {B}_f=\{ \{ y, y+z, y+\eta z, y+\eta ^2 z\} \mid y \in \mathbb {F}_{2^n}, z \in \mathbb {F}_{2^n}^* \}\), which coincides with the block set of the affine Steiner system in Eq.( 4.1). Conversely, if \((\mathcal {V},\mathcal {B}_f)\) is the affine Steiner system \(S(2,4,2^n)\), then each block \(\{ x_1, x_2, x_3, x_4 \} \in \mathcal {B}_f\) must be of the formEmploying \(\frac{f(x_2)-f(x_1)}{x_2-x_1}=\frac{f(x_3)-f(x_1)}{x_3-x_1}\), we have \(\eta ^2 f(x_1)+\eta f(x_2)=f(\eta ^2 x_1+\eta x_2)\) for every two distinct \(x_1, x_2 \in \mathbb {F}_{2^n}\). This implies that f is \(\mathbb {F}_4\)-linearized. \(\square \)
$$\begin{aligned} x_3=x_1+\eta (x_1+x_2)=\eta ^2 x_1+\eta x_2, \quad x_4=x_1+\eta ^2(x_1+x_2)=\eta x_1+\eta ^2 x_2. \end{aligned}$$
Theorem 4.2 motivates us to consider the natural problem of finding \(x^4\)-like polynomials. Below, we focus on \(x^4\)-like monomials. We first list some obvious \(x^4\)-like polynomials and part of them follow from [12, Table 3.1].
Proposition 4.3
The followings are \(x^4\)-like monomials over \(\mathbb {F}_{p^n}\).
(1)
For \(p=2\) and n even, \(x^{2^i}\) with \(\gcd (i,n)=2\).
(2)
For \(p=2\) and n odd, each oval monomial.
(3)
For \(p=3\), \(x^{3^i+1}\) with \(\gcd (i,n)=1\).
(4)
For \(p>3\), \(x^4\).
Remark 4.4
We note that for \(p=2\) and n odd, every oval polynomial over \(\mathbb {F}_{p^n}\) is \(x^4\)-like. Therefore, beyond \(x^4\)-like monomials, it would be interesting to study \(x^4\)-like polynomials.
Next, we record some numerical experiments.
Example 4.5
The following is a list of \(x^4\)-like monomials over \(\mathbb {F}_{p^n}\).
(1)
For \(p=2\) and \(2 \le n \le 19\), all \(x^4\)-like monomials over \(\mathbb {F}_{2^n}\) belong to Proposition 4.3(1)(2).
(2)
For \(p=3\), \(2 \le n \le 12\) and n even, all \(x^4\)-like monomials over \(\mathbb {F}_{3^n}\) belong to Proposition 4.3(3).
(3)
For \(p=3\), \(3 \le n \le 11\) and n odd, all \(x^4\)-like monomials over \(\mathbb {F}_{3^n}\) are:
(3b)
\(x^{2\cdot 3}\), \(x^{2\cdot 3^{\frac{n-1}{2}}}\), \(x^{2\cdot 3^{\frac{n+1}{2}}+4}\).
(3c)
\(x^d\) over \(\mathbb {F}_{3^n}\) with \((n,d)=\{ (5,98), (7,1750), (9,7874), (11,141718) \}\).
(4)
For \(p>3\), \(n=1\), and \(p < 10^4\), all \(x^4\)-like monomials over \(\mathbb {F}_p\) are:
(4a)
\(x^4\).
(4b)
\(x^{\frac{2(p+1)}{3}}\) with \(p \equiv 5 \pmod {6}\).
(4c)
\(x^d\) over \(\mathbb {F}_{p}\) with \((p,d) \in \{ (29,16) \}\).
(5)
For \(p>3\), \(n>1\) odd and \(p^n < 10^4\), all \(x^4\)-like monomials over \(\mathbb {F}_{p^n}\) are:
(5a)
\(x^4\).
(5b)
\(x^d\) over \(\mathbb {F}_{p^n}\) with
$$\begin{aligned} (p,n,d) \in \{&(5,3,24), (5,3,28), (5,3,84), (5,5,124), (5,5,128), (5,5,2084), \\&(7,3,52), (7,5,346), (11,3,888), (17,3,3276), (23,3,8112)\}. \end{aligned}$$
(6)
For \(p>3\), n even and \(p^n < 2 \cdot 10^4\), all \(x^4\)-like monomials over \(\mathbb {F}_{p^n}\) are \(x^4\).
In view of Proposition 4.5(1), it appears that all \(x^4\)-monomials over \(\mathbb {F}_{2^n}\) with n even are \(\mathbb {F}_4\)-linearized. According to Theorem 4.2, the Steiner systems \(S(2,4,2^n)\) derived from these monomials all coincide with the affine Steiner system. Hence, in order to employ Theorem 4.2 and generate new Steiner systems \(S(2,4,2^n)\), one shall look for \(x^4\)-like polynomials which are not monomials. As a preliminary step, we conducted a numerical search of \(x^4\)-like binomials and obtained a number of examples.
Remark 4.6
Consider binomials of the form \(x^{d_1}-ax^{d_2}\) over \(\mathbb {F}_{p^n}\) with \(d_1 \ge 4\) and \(2 \le d_2 < d_1\).
(1)
For \(p=2\) and \(2 \le n \le 10\), all \(x^4\)-like binomials \(x^{d_1}-ax^{d_2}\) satisfy and a is some element in \(\mathbb {F}_{2^n}^*\). Interestingly, all these binomials are \(\mathbb {F}_4\)-linearized and hence generate affine Steiner system \(S(2,4,2^n)\) in view of Theorem 4.2.
$$\begin{aligned} (n,d_1,d_2) \in \{ (6,16,4), (8,16,4), (8,64,4), (8,64,16), (10,64,16), (10,256,4) \} \end{aligned}$$
(2)
For \(p=3\) and \(2 \le n \le 7\), all \(x^4\)-like binomials \(x^{d_1}-ax^{d_2}\) satisfy and a is some element in \(\mathbb {F}_{3^n}^*\).
$$\begin{aligned} (n,d_1,d_2) \in \{&(2,4,3), (2,6,2), (3,4,3), (3,6,3), (3,10,9), (3,15,2), (3,22,11), (4,4,3), \\&(4,28,27), (5,4,3), (5,6,3), (5,10,9), (5,18,9), (5,28,27), (5,58,29), \\&(5,82,81), (5,98,49), (6,4,3), (6,244,243), (7,4,3), (7,6,3), (7,10,9), \\&(7,28,27), (7,54,27), (7,82,81), (7,166,83), (7,244,243), (7,730,729), \\&(7,1750,875) \} \end{aligned}$$
(3)
For \(p \in \{5,7,11\}\) and \(2 \le n \le 3\), all \(x^4\)-like binomials \(x^{d_1}-ax^{d_2}\) satisfy and a is some element in \(\mathbb {F}_{p^n}^*\).
$$\begin{aligned} (p,n,d_1,d_2) \in \{ (5,2,10,4), (5,2,12,8), (5,2,12,10), (5,2,16,4), (5,2,22,10) \} \end{aligned}$$
5 Concluding remarks
In this paper, we determined the intersection distribution of degree four polynomials by analyzing the patterns of their \(\mathbb {F}_q\)-roots. We proposed a simple direct construction of Steiner systems \(S(2,4,2^n)\) using polynomials having the same intersection distribution as \(x^4\). This connection inspires us to look for \(x^4\)-like polynomials. Below, we mention a few open problems:
Open Problem 1. For n even, find \(x^4\)-like polynomials over \(\mathbb {F}_{2^n}\) that are not \(\mathbb {F}_4\)-linearized. By Theorem 4.2, such polynomials will generate Steiner system \(S(2,4,2^n)\) distinctive from the affine Steiner system. It would be highly interesting to employ Theorem 4.2 and construct \(S(2,4,2^n)\) Steiner systems that are nonisomorphic to the affine Steiner systems.
Open Problem 2. The data in Example 4.5 and Remark 4.6 indicates the presence some infinite families of \(x^4\)-like monomials and binomials. An interesting problem is to provide theoretical explanation for these polynomials being \(x^4\)-like.
In the view that there have been many elegant combinatorial structures derived from polynomials with highly structured intersection distribution [5, 11, 12, 15], we believe that further study of intersection distribution is of great interest. Therefore, we invite the readers to consider the following problem.
Open Problem 3. Determine the intersection distribution of polynomials over finite fields with degree greater than four.
Since the analysis of patterns of \(\mathbb {F}_q\)-roots becomes more difficult when the degree of polynomial increases, we expect that the resolution of the above question requires deeper mathematical techniques.
Finally, we mention the concept of multiplicity distribution which is intrinsically connected to intersection distribution.
Definition 5.1
(Multiplicity distribution) Let \(f \in \mathbb {F}_q[x]\). For \(b \in \mathbb {F}_q\) and \(0 \le i \le q\), defineThe sequence \((M_i(f,b))_{i=0}^q\) is the multiplicity distribution of f at the direction b over \(\mathbb {F}_q\). The multiset \(M(f)=\{(M_i(f,b))_{i=0}^q \mid b \in \mathbb {F}_q\}\) is the multiplicity distribution of f over \(\mathbb {F}_q\).
$$\begin{aligned} M_i(f,b)&=|\{ c \in \mathbb {F}_q\mid f(x)-bx-c=0 \hbox { has exactly }i \hbox { solutions in}\,\, \mathbb {F}_q\}|\\&=|\{ c \in \mathbb {F}_q\mid f(x)-bx-c \hbox { has }i\, \mathbb {F}_q\text {-}\hbox {roots} \}|. \end{aligned}$$
The multiplicity distribution was formally proposed in [12, Sect. 1] with a natural geometric motivation. Given \(f \in \mathbb {F}_q[x]\) and \(b \in \mathbb {F}_q\), for \(0 \le i \le q\), \(M_i(f,b)\) counts the number among the q lines \(\{ y=bx+c \mid c \in \mathbb {F}_q\}\) with slope b in the affine plane \(\textrm{AG}(2,q)\), which intersect the graph of f in exactly i points. Therefore, the multiplicity distribution of a polynomial determines and contains finer information than its intersection distribution. Precisely, for \(f \in \mathbb {F}_q[x]\) and \(0 \le i \le q\), we haveIndeed, the study of multiplicity distributions was motivated by this connection at the outset [12, Sect. 4]. Interestingly, multiplicity distribution has found widespread applications in Kakeya set [11, Sect. 5], [12, Sect. 4], combinatorial t-designs [6, 11, Sect. 4], locally recoverable codes [3], and optical orthogonal codes [10, Remark 17]. We conclude with the following open problem.
$$\begin{aligned} v_i(f)=\sum _{b \in \mathbb {F}_q}M_i(f,b). \end{aligned}$$
Open Problem 4 Determine the multiplicity distribution of degree four polynomials over finite fields.
Declarations
Conflict of interest
The authors declare no conflict of interest.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
