On the fourth weight of generalized Reed–Muller codes

Abstract

In this paper, we study the fourth weight of generalized Reed–Muller codes. Erickson in his Ph.D. thesis proved that the second weight of $R_q(a(q-1)+b,m)$ depends on the second weight $R_q(b,2)$. Also, Leducq (Discret Math 338:1515–1535, 2015) proved that under the same condition, by the third weight of $R_q(b,2)$ we can determine the third weight of $R_q(a(q-1)+b,m)$. In this paper we will show that the similar result does not hold for the fourth weight of generalized Reed–Muller codes. We will determine the fourth weight of generalized Reed–Muller codes of order $r=a(q-1)+b$ with $3\le b< \frac{q+4}{3}$.

1 Introduction

Let $F_q$ be the finite field with q elements and $m\ge 1$ an integer. We denote by $B_m^q$ the $F_q$-algebra of the functions from $F_q^m$ to $F_q$ and by $F_q[X_1,\cdots , X_m]$ the $F_q$-algebra of polynomials in m variables with coefficients in $F_q$.

Let r be an integer such that $1 \le r < m(q -1)$. The generalized Reed–Muller code of order r is the following subspace of the space $F_{q}^{q^m}$

$$\begin{aligned} R_q(r,m)=\Big \{(f(x))_{x\in F_q^m}|f\in F_q[X_1,\cdots , X_m] \ \text {and}\; deg(f)\le r\Big \} \end{aligned}$$

Throughout this article, we write $r=a(q-1)+b$, $0\le a\le m-1$, $0 \le b < q-1$, $d_r^m=(q-b)q^{m-a-1}$ and by $W_i$ we denote the ith minimum weight of $R_q(r,m)$. The support of $f\in F_q[X_1,\cdots , X_m]$ is the set $\{x\in F_q^m: f (x) \ne 0\}$ and we denote by |f| the cardinal of its support.

There exist many questions concerning generalized Reed–Muller codes. Some of the most important questions are about the first minimum weights and weight distribution of generalized Reed–Muller codes. Not much is known for the mentioned questions for $q\ge 3$ and $r\ge 3$.

The minimum weight has been determined by Kasami et al. [9]. It has been proved that the minimal weight of the generalized Reed–Muller code $R_q(r,m)$ is $(q- b)q^{m-a-1}$ where $r=a(q-1)+b$ and $0\le b< q-1$. The codewords reaching this bound were described by Delsarte et al. [5] (see also [11]).

Erickson [7] proved that if we know the second weight of $R_q(b,2)$ then, we can determine the second weight for all generalized Reed–Muller codes. He conjectured that the second weight of $R_q(b, 2)$ is $(q-b)q+b-1$ and Bruen proved the conjecture using blocking set in [2]. This problem was studied by Geil using Gr$\ddot{o}$bner basis in [8] for $r<q$ and $r> (m-1)(q-1)$ and it was almost completely solved by Rolland [16]. Second weight codewords have been studied in [4, 17] and finally completely described in [12].

Leducq [13] got a full description of the third weight and the third weight codewords of generalized Reed–Muller codes of order $r=a(q-1)+b$ for $3\le b< \frac{q+4}{3}$.

The weight distribution of $R_q(2,m)$ was given by McEliece in [15] for any q and due to some mistakes in the computation, Li [14] provided a precise account for the weight distribution of second order generalized Reed–Muller codes. For $q=2$, for all m and all r, the weight distribution is known in the range $[W_1, 2.5W_1]$ by a result of Kasami et al [10]. We refer the reader to [1, 3, 6] for further results.

In this paper, we want to determine the fourth weight of generalized Reed–Muller codes. The main result of this article is the determination of the fourth weight of $R_q(a(q-1) + b,m)$ the generalized Reed–Muller code of length $q^m$ for prime number q and order $a(q-1) + b$ for $3\le b < \frac{q+4}{3}$.

From a geometric point of view a polynomial f defines a hypersurface in $F_q^m$ and Z(f) the set of points of this hypersurface (the set of zeros of f) is related to the support of the associated codeword by the following formula:

$$\begin{aligned} |f|=q^m-\#Z(f) \end{aligned}$$

2 Preliminaries

2.1 Notation and preliminary remark

Let $f\in B^q_m$, $\lambda \in F_q$. We define $f_{\lambda }\in B^q_ {m-1}$ by

$$\begin{aligned} \forall x = (x_2,..., x_m) \in F^{m-1}_q, f_{\lambda }(x) = f (\lambda , x_2..., x_m). \end{aligned}$$

Let $0\le r \le (m-1)(q-1)$ and $f\in R_q(r, m)$. We denote by S the support of f. Consider H an affine hyperplane in $F^m_q$, by an affine transformation, we can assume $x_1 = 0$ is an equation of H. Then $S \cap H$ is the support of $f_0 \in R_q(r,m-1)$ or the support of $(1 - x_1^{q-1})f \in R_q(r + (q-1),m)$.

2.2 Useful lemmas

Here, we present some lemmas that we need to prove our main results. The Lemmas 1–8 are proved in [7]

Lemma 1

Let $m\ge 1$, $q\ge 2$, $f\in B^q_m$ and $w\in F_q$. If for all $(x_2,\cdots , x_m)$ in $F_q^{m-1}$, $f(w,x_2,\cdots ,x_m)=0$, then for all $(x_1,x_2,\cdots ,x_m)\in F_q^m$,

$$\begin{aligned} f(x_1,\cdots , x_m)=(x_1-w)g(x_1,\cdots ,x_m) \end{aligned}$$

with $deg_{x_1}(g)\le deg_{x_1}(f)-1$ and $deg(g)\le deg(f)-1$.

Lemma 2

Let $m\ge 2$, $q\ge 3$, $0\le r\le m(q-1)$. If $f\in R_q(r,m)$, $f\ne 0$ and there exists $y\in R_q(1,m)$ and $(\lambda _i)_{1\le i\le n}$ n elements in $F_q$ such that the hyperplanes of equation $y=\lambda _i$ do not meet the support of f, then

$$\begin{aligned} |f|\ge (q-b)q^{m-a-1}+\left\{ \begin{array}{lr} n(b-n)q^{m-a-2} &{} \textrm{if} n<b, \\ (n-b)(q-1-n)q^{m-a-1} &{} \textrm{if} n\ge b. \end{array}\right. \end{aligned}$$

where $r=a(q-1)+b$, $1\le b\le q-1$.

Lemma 3

If $f\in R_q(r,m)$ with $r\le q-1$ and $|f|<(1+\frac{1}{q})d^m_r$, then f is the product of r linear factors.

Lemma 4

Let $m\ge 2$, $q\ge 3$, $1\le b\le q-1$. Assume $f\in R_q(b,m)$ is such that f depends only on $x_1$ and $g\in R_q(b-k,m)$, $1\le k\le b$. Then either $f+g$ depends only on $x_1$ or $|f+g|\ge (q-b+k)q^{m-1}$.

Lemma 5

Let $m\ge 2$, $q\ge 3$, $1\le a\le m-1$, $1\le b\le q-2$. Assume $f\in R_q(a(q-1)+b,m)$ is such that $\forall x=(x_1,\cdots , x_m)\in F^m_q,$

$$\begin{aligned} f(x)=(1-x_1^{q-1}){\widetilde{f}}(x_2,\cdots ,x_m) \end{aligned}$$

and $g\in R_q(a(q-1)+b-k,m)$, $1\le k\le q-1$, is such that $(1-x_1^{q-1})$ does not divide g. Then either $|f+g|\ge (q-b+k)q^{m-a-1}$ or $k=1$.

Lemma 6

Let $m\ge 2$, $q\ge 3$, $1\le a\le m-2$, $1\le b\le q-2$ and $f\in R_q(a(q-1)+b,m)$. We set an order on the elements of $F_q$ such that $|f_{\lambda _1}|\le \cdots \le |f_{\lambda _q}|$.

If f has no linear factor and there exists $k\ge 1$ such that $(1-x_2^{q-1})$ divides $f_{\lambda _i}$ for $i\le k$ but $(1-x_2^{q-1})$ does not divide $f_{\lambda _{k+1}}$ then,

$$\begin{aligned} |f|\ge (q-b)q^{m-a-1}+k(q-k)q^{m-a-2} \end{aligned}$$

Lemma 7

Let $m\ge 2$, $q\ge 3$, $1\le a\le m$ and $f\in R_q(a(q-1),m)$ such that $|f|=q^{m-a}$ and $g\in R_q(a(q-1)-k,m)$, $1\le k\le q-1$, such that $g\ne 0$. Then, either $|f+g|=kq^{m-a}$ or $|f+g|\ge (k+1)q^{m-a}$.

Lemma 8

Let $m\ge 2$, $q\ge 3$, $1\le a\le m-1$ and $f\in R_q(a(q-1), m)$. If for some $u,v\in F_q$, $|f_u|=|f_v|=q^{m-a-1}$, then there exists T an affine transformation fixing $x_1$ such that

$$\begin{aligned} (f \circ T)_u=(f\circ T)_v \end{aligned}$$

The following results can be found in [13].

Theorem 1

Let $m\ge 2$, $q\ge 9$, $0\le a\le m-2$ and $4\le b< \frac{q+4}{3}$. The third weight of $R_q(a(q-1)+b,m)$ is $W_3=(q-2)(q-b+2)q^{m-a-2}$.

Theorem 2

Let $m\ge 3$, $q\ge 7$ and $0\le a\le m-3$. The third weight of $R_q(a(q-1)+3,m)$ is $W_3=(q-1)^3q^{m-a-3}$.

Theorem 3

For $q\ge 7$, $m\ge 2$, $0\le a\le m-2$, $4 \le b < \frac{q+4}{3}$, up to affine transformation, the third weight codewords of $R_q(a(q- 1) + b,m)$ are of the form:

$$\begin{aligned} f(x)=\prod _{i=1}^a(1-x_i^{q-1}) g(x_{a+1}, x_{a+2}) \ \ \ \ \forall x=(x_1,\cdots , x_m)\in F_q^m \end{aligned}$$

where $g\in R_q(b,2)$ is such that $|g|=(q-2)(q-b+2)$.

Theorem 4

For $q\ge 7$, $m\ge 3$, $0\le a\le m-3$, up to affine transformation, the third weight codewords of $R_q(a(q- 1) + 3,m)$ are of the form:

$$\begin{aligned} f(x)=\prod _{i=1}^a(1-x_i^{q-1}) x_{a+1} x_{a+2}x_{a+3} \ \ \ \ \forall x=(x_1,\cdots , x_m)\in F_q^m. \end{aligned}$$

3 A lower bound on the fourth weight

In this section, we determine a lower bound on the fourth weight of $R_q(a(q-1)+b,m)$ for the cases where $3\le b< \frac{q+4}{3}$. Throughout this paper, by hyperplane we mean affine hyperplane and q is a prime number. The validity of the results of this paper has been checked by a computer program.

Lemma 9

Let $f\in R_q(b,m)$ be the product of b distinct linear factors such that $x_1-\lambda _i$ for $i=1,\cdots , k$ are k of these linear factors. If for some $j_0\notin \{1,\cdots , k\}$, $|f_{\lambda _{j_0}}|=(q-b+k)q^{m-2}$ (the minimum weight of $R_q(b-k,m-1)$) then, for all $j\notin \{1,\cdots , k\}$, there is an integer t where $0\le t\le b-k-1$ such that $|f_{\lambda _j}|=(q-b+k+t)q^{m-2}$.

Proof

We denote by $H_{\lambda _i}$ the affine hyperplane with the equation $x_1=\lambda _i$ for $i=1,\cdots , q$. Assume that S denotes the support of f. By the assumption of the lemma, S does not meet the hyperplanes $H_{\lambda _i}$ for $i=1,\cdots , k$. Denote by $H^{(i)}$ $i=1,\cdots , b-k$ the other affine hyperplanes corresponding to the other linear factors which do not meet S. Since for some $j_0\notin \{1,\cdots , k\}$, $|f_{\lambda _{j_0}}|=(q-b+k)q^{m-2}$ then, $f_{\lambda _{j_0}}$ is a minimum weight codeword of $R_q(b-k,m-1)$. So $H_{\lambda _{j_0}}\cap H^{(i)}=P^{(i)}$ is an affine subspace of codimension 2 where $P^{(i)}\cap P^{(i')}=\emptyset$ for $i\ne i'$. We get that for each two hyperplanes $H^{(s)}$ and $H^{(s')}$, $H^{(s)}\cap H^{(s')}$ is either empty or an affine subspace of codimension 2 which is included in one of the hyperplanes $H_{\lambda _i}$ for $i=1,\cdots , q$. Denote by $P^{ij}$ the affine subspace of codimension 2 $H_{\lambda _i}\cap H^{(j)}$ for $k+1\le i\le q$ and $1\le j\le b-k$ in which for $j\ne j'$, $P^{ij}\cap P^{ij'}=\emptyset$ or $P^{ij}=P^{ij'}$. So we get that $|f_{\lambda _i}|=q^{m-1}-(b-k-t)q^{m-2}$ in which $b-k-t$ is the number of distinct subspaces $P^{ij}$ which is included in $H_{\lambda _i}$. $\square$

Lemma 10

Let $m\ge 3$, $q\ge 9$, $4\le b< \frac{q+4}{3}$ and $f\in R_q(b,m)$. If $|f|>(q-2)(q-b+2)q^{m-2}$, then $|f|\ge (q-1)^2(q-b+2)q^{m-3}$.

Proof

Let $f\in R_q(b,m)$ such that $|f|>(q-2)(q-b+2)q^{m-2}$. Assume $|f|<(q-1)^2(q-b+2)q^{m-3}$. Since

$$\begin{aligned} (q-1)^2(q-b+2)q^{m-3}\le (1+\frac{1}{q})d^m_b=(1+\frac{1}{q})(q-b)q^{m-1} \end{aligned}$$

(1)

for $b< \frac{q+4}{3}$, by Lemma 3f is the product of b linear factors. For $y\in R_q(1,m)$, denote by n the number of distinct $\lambda \in F_q$ such that $y-\lambda$ divides f. Since $n\le b$ by Lemma 2

$$\begin{aligned} (q-b)q^{m-1}+n(b-n)q^{m-2}<(q-1)^2(q-b+2)q^{m-3} \end{aligned}$$

we get that $n\in \{1, 2, b-2, b-1, b\}$.

By applying an affine transformation we can assume that $x_1=\lambda _1$, $\lambda _1\in F_q$ is one of the linear factors.

If $n=b$, then for all $x=(x_1,\cdots , x_m)\in F_q^m$, we have

$$\begin{aligned} f(x)=\alpha \prod _{i=1}^b (x_1-\lambda _i) \end{aligned}$$

with $\lambda _i\in F_q$, $\lambda _i\ne \lambda _j$ for $i\ne j$. In this case f is a minimum weight codeword of $R_q(b,m)$ which is absurd.

If $n=b-1$, then for all $x=(x_1,\cdots , x_m)\in F_q^m$, we have

$$\begin{aligned} f(x)= \prod _{i=1}^{b-1} (x_1-\lambda _i) g(x) \end{aligned}$$

with $\lambda _i\in F_q$, $\lambda _i\ne \lambda _j$ for $i\ne j$ and $g\in R_q(1,m)$. If $deg(g)=0$, then f is a minimum weight codeword of $R_q(b-1,m)$. If $deg(g)=1$, then f is a second minimum weight codeword of $R_q(b,m)$. Both cases give us a contradiction, since $(q-2)(q-b+2)q^{m-2}<|f|<(q-1)^2(q-b+2)q^{m-3}$.

If $n=b-2$, then for all $x=(x_1,\cdots , x_m)\in F_q^m$, we have

$$\begin{aligned} f(x)= \prod _{i=1}^{b-2} (x_1-\lambda _i) g(x) \end{aligned}$$

with $\lambda _i\in F_q$, $\lambda _i\ne \lambda _j$ for $i\ne j$ and $g\in R_q(2,m)$. If $deg(g)=0$, then f is a minimum weight codeword of $R_q(b-2,m)$. If $deg(g)=1$, then f is a second minimum weight codeword of $R_q(b-1,m)$. Both cases give a contradiction. So $deg(g)=2$. For all $i\ge b-1$, $f_{\lambda _i}\in R_q(2,m-1)$ and $|f_{\lambda _i}|=|g_{\lambda _i}|\ge (q-2)q^{m-2}$. Denote by $N:=\#\{i\ge b-1; |f_{\lambda _i}|=(q-2)q^{m-2}\}$. For $\lambda \in F_q$, if $|f_{\lambda }|>(q-2)q^{m-2}$, then $|f_{\lambda }|\ge (q-1)^2q^{m-3}$. Since $|f|<(q-1)^2(q-b+2)q^{m-3}$, we get that $N\ge 1$. So by Lemma 9 we conclude that for all $i\ge b-1$, $|f_{\lambda _i}|=(q-2)q^{m-2}$ or $|f_{\lambda _i}|=(q-1)q^{m-2}$. From

$$\begin{aligned} N(q-2)q^{m-2}+(q-b+2-N)(q-1)q^{m-2}<(q-1)^2(q-b+2)q^{m-3} \end{aligned}$$

we get that $N=q-b+2$ that gives a third minimum weight codeword of $R_q(b,m)$ which is absurd.

If $n=2$, then for all $x=(x_1,\cdots ,x_m)\in F^m_q$, we have

$$\begin{aligned} f(x)= (x_1-\lambda _1) (x_1-\lambda _2) g(x) \end{aligned}$$

with $\lambda _1,\lambda _2\in F_q$, $\lambda _1\ne \lambda _2$ and $g\in R_q(b-2,m)$. Then for all $i\ge 3$, $f_{\lambda _i}\in R_q(b-2,m-1)$ and $|f_{\lambda _i}|=|g_{\lambda _i}|\ge (q-b+2)q^{m-2}$. Denote by $N:=\#\{i\ge 3; |f_{\lambda _i}|=(q-b+2)q^{m-2}\}$. For $\lambda \in F_q$, if $|f_{\lambda }|>(q-b+2)q^{m-2}$, then $|f_{\lambda }|\ge (q-1)(q-b+3)q^{m-3}$. Since

$$\begin{aligned} (q-2)(q-1)(q-b+3)q^{m-3}>(q-1)^2(q-b+2)q^{m-3} \end{aligned}$$

we get that $N\ge 1$. So by Lemma 9 for all $i\ge 3$, $|f_{\lambda _i}|=(q-b+t)q^{m-2}$ where $2\le t\le b-1$. Therefore we have

$$\begin{aligned} |f|\ge & {} N(q-b+2)q^{m-2}+(q-2-N)(q-b+3)q^{m-2}\\= & {} \Big (q(q-2)(q-b+3)-Nq\Big )q^{m-3}. \end{aligned}$$

By considering $|f|<(q-1)^2(q-b+2)q^{m-3}$, we get that $N=q-2$ that gives a third minimum weight codeword of $R_q(b,m)$ which is absurd.

From now, assume $n=1$. Then for all $x=(x_1,\cdots ,x_m)\in F^m_q$, we have

$$\begin{aligned} f(x)= (x_1-\lambda _1) g(x) \end{aligned}$$

with $\lambda _1\in F_q$ and $g\in R_q(b-1,m)$. Then for all $i\ge 2$, $f_{\lambda _i}\in R_q(b-1,m-1)$ and $|f_{\lambda _i}|=|g_{\lambda _i}|\ge (q-b+1)q^{m-2}$. Denote by $N:=\# \{i\ge 2; |f_{\lambda _i}|=(q-b+1)q^{m-2}\}$. For $\lambda \in F_q$, if $|f_{\lambda }|>(q-b+1)q^{m-2}$, then $|f_{\lambda }|\ge (q-1)(q-b+2)q^{m-3}$. Since

$$\begin{aligned} (q-1)(q-1)(q-b+2)q^{m-3}\ge (q-1)^2(q-b+2)q^{m-3} \end{aligned}$$

we get that $N\ge 1$. Assume $H_0$ is the hyperplane with the equation $x_1=\lambda _1$. Let $\mathcal {H}=\{H_1, \cdots , H_{b-1}\}$ be the set of $(b-1)$ other affine hyperplanes which do not meet S. Denote by A the affine subspace of codimension 2 which is included in both of $H_0$ and $H_1$. Let $\mathcal {A}=\{H_i; i\ge 1, H_i\cap H_0=A\}$. Since $n=1$ and $N\ge 1$, for each pair $(H, H')\in \mathcal {A}\times (\mathcal {H}-\mathcal {A})$, $H\cap H'$ is an affine subspace of codimension 2 which is included in one of $H^{(i)}$ (the hyperplane with the equation $x_1=\lambda _i$) for $2\le i\le q$. Then we have

$$\begin{aligned} |f|\ge (q-1)(q-b+1)q^{m-2}+\#\mathcal {A}(b-1-\#\mathcal {A})q^{m-2}. \end{aligned}$$

By considering $|f|<(q-1)^2(q-b+2)q^{m-3}$, we get that $|\mathcal {A}|=b-1$ that gives a second minimum weight codeword of $R_q(b,m)$ which is absurd. $\square$

Lemma 11

Let $m\ge 3$, $q\ge 9$ and $4\le b< \frac{q+4}{3}$. If $f\in R_q((m-3)(q-1)+b,m)$ and $|f|>(q-2)(q-b+2)q$, then $|f|\ge (q-1)^2(q-b+2)$.

Proof

The case where $m=3$ comes from Lemma 10. Assume $m\ge 4$. Let $f\in R_q((m-3)(q-1)+b,m)$ such that $|f|>(q-2)(q-b+2)q$. Assume $|f|< (q-1)^2(q-b+2)$. We denote by S the support of f.

Assume S meets all affine hyperplanes. We set an order on the elements of $F_q$ such that $|f_{\lambda _1}|\le \cdots \le |f_{\lambda _q}|$. Then for all H hyperplane, $\#(S\cap H)\ge (q-b)q$ and since

$$\begin{aligned} q((q-2)(q-b+2)+1)\ge (q-1)^2(q-b+2) \end{aligned}$$

we get that $|f_{\lambda _1}|=(q-b)q$ or $|f_{\lambda _1}|=(q-1)(q-b+1)$ or $|f_{\lambda _1}|=(q-2)(q-b+2)$. By applying an affine transformation, we can assume $(1-x_2^{q-1})$ divides $f_{\lambda _1}$. Let $k\ge 1$ be such that for all $i\le k$, $(1-x_2^{q-1})$ divides $f_{\lambda _i}$ and $(1-x_2^{q-1})$ does not divide $f_{\lambda _{k+1}}$. Then by Lemma 6

$$\begin{aligned} |f|\ge & {} (q-b)q^2+k(q-k)q\\\ge & {} (q-b)q^2+q(q-1) \end{aligned}$$

we get a contradiction, since $(q-b)q^2+q(q-1) \ge (q-1)^2(q-b+2)$.

So there exists a hyperplane $H_0$ which does not meet S. By applying an affine transformation, we can assume $x_1=\alpha$, $\alpha \in F_q$ is an equation of $H_0$. Denote by n the number of hyperplanes parallel to $H_0$ which do not meet S.

If $n=q-1$, then for all $x=(x_1,\cdots , x_m)\in F^m_q$ we can write

$$\begin{aligned} f(x)= (1-x_1^{q-1}) g(x_2,\cdots , x_m) \end{aligned}$$

where $g\in R_q((m-4)(q-1)+b, m-1)$ and $|f|=|g|$. So g has the same conditions as f with one variable less. Iterating this process we end either in the case where $a=0$ (which is absurd by Lemma 10) or in the case where $n<q-1$.

From now, we assume $n<q-1$. By Lemma 2 since $|f|<(q-1)^2(q-b+2)$, $n\in \{1, 2, b-2, b-1, b\}$. We can write for all $x=(x_1, \cdots , x_m)\in F^m_q$,

$$\begin{aligned} f(x)= \prod _{1\le i\le n} (x_1-\lambda _i) g(x) \end{aligned}$$

where $g\in R_q((m-3)(q-1)+b-n, m)$. Then for all $i\ge n+1$, $f_{\lambda _i}\in R_q((m-3)(q-1)+b-n, m-1)$ and $|f_{\lambda _i}|=|g_{\lambda _i}|\ge q(q-b+n)$.

Assume $n=b$. For $\lambda \in F_q$ if $|g_{\lambda }|>q^2$ then $|g_{\lambda }|\ge 2(q-1)q$. Denote by $N:=\# \{i\ge b+1; |g_{\lambda _i}|=q^2\}$. Since

$$\begin{aligned} (q-b)2(q-1)q \ge (q-1)^2(q-b+2) \end{aligned}$$

for $b<\frac{q+4}{3}$, we get $N\ge 1$. Furthermore, since

$$\begin{aligned} (q-b)q^2 < (q-2)(q-b+2)q \end{aligned}$$

$N\le q-b-1$.

Assume $|f_{\lambda _{b+N+1}}|\ge (N+1)q^2$. Then

$$\begin{aligned} Nq^2+(q-b-N)(N+1)q^2\le |f|<(q-1)^2(q-b+2). \end{aligned}$$

Therefore

$$\begin{aligned} Nq^2(q-b-N)\le 2bq-3q-b+2<(2b-3)q \end{aligned}$$

which gives $N(q-b-N)<1$ for $b<\frac{q+4}{3}$ and this is absurd since $1\le N\le q-b-1$. If $|f_{\lambda _{b+N+1}}|=Nq^2$ then

$$\begin{aligned} Nq^2+(q-b-N)Nq^2\le |f|<(q-1)^2(q-b+2). \end{aligned}$$

So

$$\begin{aligned} Nq^2(q-b)-N(N-1)q^2-q^2(q-b)< 2bq-3q-b+2<(2b-3)q \end{aligned}$$

which gives

$$\begin{aligned} (N-1)(q-b-N)q^2<(2b-3)q. \end{aligned}$$

So the only possibility such that $|f_{\lambda _{b+N+1}}|=Nq^2$ is $N=1$ or $N=q-b$ which are absurd by definition of N and inequality $N\le q-b-1$, respectively.

By Lemma 8 for all $b+1\le i\le N+b$, $g_{\lambda _{b+1}}=g_{\lambda _i}$. So we can write for all $x=(x_1,\cdots ,x_m)\in F^m_q$

$$\begin{aligned} f(x)= & {} \prod _{1\le i\le b}(x_1-\lambda _i)\Bigg (g_{\lambda _{b+1}}(x_2,\cdots , x_m)+\prod _{b+1\le i\le N+b}(x_1-\lambda _i) h(x)\Bigg )\\= & {} \prod _{1\le i\le b}(x_1-\lambda _i)\Bigg (\alpha f_{\lambda _{b+1}}(x_2,\cdots ,x_m)+\prod _{b+1\le i\le N+b}(x_1-\lambda _i)h(x)\Bigg ) \end{aligned}$$

where $h\in R_q((m-3)(q-1)-N, m)$ and $\alpha \in F_q^*$.

Then for all $(x_2,\cdots ,x_m)\in F_q^{m-1}$,

$$\begin{aligned} f_{\lambda _{b+N+1}}(x_2,\cdots , x_m)=\beta f_{\lambda _{b+1}}(x_2,\cdots , x_m)+\gamma h_{\lambda _{b+N+1}}(x_2,\cdots ,x_m) \end{aligned}$$

which is absurd by Lemma 7.

Now, assume $n\in \{1, 2, b-2, b-1\}$.

Applying argument as in the beginning of the proof of this lemma, we can assume that $(1-x_2^{q-1})$ does not divide f.

Since $n\ge 1$, $f_{\lambda _1}=0$. So $(1-x_2^{q-1})$ divides $f_{\lambda _1}$. Then since $(1-x_2^{q-1})$ does not divide f, there exists $k\in \{1,2,\cdots , q-1\}$ such that for all $i\le k$, $(1-x_2^{q-1})$ divides $f_{\lambda _i}$ and $(1-x_2^{q-1})$ does not divide $f_{\lambda _{k+1}}$. For $\lambda \in F_q$, if $|f_{\lambda }|>q(q-b+n)$, then

$$\begin{aligned} |f_{\lambda }|\ge W_2= \left\{ \begin{array}{lr} q^2 &{} \textrm{if} \ \ n=b-1, \\ (q-1)(q-b+2) &{} \textrm{if} \ \ n=1,\\ (q-1)(q-b+3) &{} \textrm{if} \ \ n=2,\\ (q-1)^2 &{} \textrm{if} \ \ n=b-2. \end{array}\right. \end{aligned}$$

Denote by $N:=\# \{i\ge n+1; |f_{\lambda _i}|=q(q-b+n)\}$. In all cases, $(q-n)W_2\ge (q-1)^2(q-b+2)$. So $N\ge 1$. Furthermore, for all $n\in \{1, 2, b-2, b-1\}$, $(q-n)q(q-b+n)\le (q-2)(q-b+2)q$. So $N\le q-n-1$.

Then $|f_{\lambda _{n+1}}|=q(q-b+n)$ and $f_{\lambda _{n+1}}$ is a minimal weight codeword of $R_q((m-3)(q-1)+b-n,m-1)$. So by applying an affine transformation we can assume $(1-x_2^{q-1})$ divides $f_{\lambda _{n+1}}$. Then $k\ge n+1\ge 2$.

If $N\ge 2$ and $n+1\le k\le n+N-1$, then $|f_{\lambda _{k+1}}|=q(q-b+n)<q(q-b+k)$. If $N=1$ and $n+1\le k\le q-1$ or $N\ge 2$ and $n+N\le k\le q-1$, assume $|f_{\lambda _{k+1}}|\ge q(q-b+k)$. Then

$$\begin{aligned} |f|\ge & {} Nq(q-b+n)+(k-n-N)W_2+(q-k)q(q-b+k)\\\ge & {} (q-1)^2(q-b+2) \end{aligned}$$

which is absurd.

Since for all $n+1\le i\le k$, $(1-x_2^{q-1})$ divides $f_{\lambda _i}$, it divides $g_{\lambda _i}$ too. Then for all $x=(x_1,\cdots , x_m)\in F_q^m$ we can write

$$\begin{aligned} f(x)= & {} \prod _{1\le i\le n}(x_1-\lambda _i)\Bigg (\prod _{n+1\le i\le k} (x_1-\lambda _i)h(x_1,\cdots , x_m)+(1-x_2^{q-1})l(x_1,x_3,\cdots , x_m)\Bigg ) \end{aligned}$$

with $deg(h)\le (m-3)(q-1)+b-k$. Then for all $x=(x_1,\cdots ,x_m)\in F^m_q$

$$\begin{aligned} f_{\lambda _{k+1}}(x_2,\cdots , x_m)= & {} \alpha h_{\lambda _{k+1}}(x_2,\cdots , x_m)+\beta (1-x_2^{q-1})l_{\lambda _{k+1}}(x_3,\cdots , x_m)) \end{aligned}$$

Therefore, we get a contradiction by Lemma 5, since $k\ge 2$ and $|f_{\lambda _{k+1}}|<q(q-b+k)$. $\square$

Lemma 12

Let $q\ge 4$, $m\ge 3$. If $f\in R_q(3,m)$ and $|f|>(q-1)^3q^{m-3}$ then, $|f|\ge ((q-1)^3+1)q^{m-3}$.

Proof

We prove this lemma by induction on m. The case where $m=3$ is an immediate result. Suppose that for some $m\ge 4$, if $f \in R_q(3,m-1)$ is such that $|f|>(q-1)^3q^{m-4}$ then $|f|\ge ((q-1)^3+1)q^{m-4}$.

Let $f\in R_q(3,m)$ such that $|f|>(q-1)^3q^{m-3}$. Assume $|f|<((q-1)^3+1)q^{m-3}$. Denote by S the support of f.

Assume S meets all affine hyperplanes. Then for all H hyperplanes $\# (S\cap H)\ge (q-3)q^{m-2}$. Suppose that there exists $H_1$ such that $\#(S\cap H_1)=(q-3)q^{m-2}$. By applying an affine transformation, we can assume $x_1 = \alpha$ is an equation of $H_1$. Set an order on the elements of $F_q$ such that $|f_{\lambda _1}|\le \cdots \le |f_{\lambda _q}|$. Then $f_{\lambda _1}$ is a minimum weight codeword of $R_q(3, m-1)$. By applying an affine transformation, we can assume $f_{\lambda _1}$ depends only on $x_2$. Let $k\ge 1$ be such that $f_{\lambda _i}$ depends only on $x_2$ for all $i\le k$ but $f_{\lambda _{k+1}}$ does not depend only on $x_2$. If $k>3$, we can write for all $x=(x_1,\cdots , x_m)\in F_q^m$

$$\begin{aligned} f(x)=\sum _{i=0}^3 f_{\lambda _{i+1}}^{(i)}(x_2,\cdots , x_m)\prod _{1\le j\le i}(x_1-\lambda _j) \end{aligned}$$

Since for $i\le 4$, $f_{\lambda _i}$ depends only on $x_2$, then f depends only on $x_1,x_2$, Then $|f|\equiv 0$ (mod $q^{m-2}$). Since $|f|>(q-1)^3q^{m-3}$, then $|f|\ge ((q-1)^3+1)q^{m-3}$ which is absurd. So $k\le 3$. Since $f_{\lambda _1}$, $\cdots$, $f_{\lambda _k}$ depend only on $x_2$, we can write for all $x_1,x_2\in F_q$ and ${\widehat{x}}\in F_q^{m-2}$

$$\begin{aligned} f(x_1,x_2, {\widehat{x}})=g(x_1,x_2)+ \prod _{i=1}^k (x_1-\lambda _i) h(x_1,x_2,{\widehat{x}}) \end{aligned}$$

where $deg(h)\le 3-k$. Then

$$\begin{aligned} f_{\lambda _{k+1}}(x_2, {\widehat{x}})=g_{\lambda _{k+1}}(x_2)+ \alpha h_{\lambda _{k+1}}(x_2,{\widehat{x}}) \end{aligned}$$

where $\alpha \in F_q^*$. So by Lemma 4 since $f_{\lambda _{k+1}}$ does not depend only on $x_2$, $|f_{\lambda _{k+1}}|\ge (q-3+k)q^{m-2}$. So

$$\begin{aligned} |f|\ge k(q-3)q^{m-2}+(q-k)(q-3+k)q^{m-2}=(q-3)q^{m-1}+k(q-k)q^{m-2}. \end{aligned}$$

By considering $|f|<((q-1)^3+1)q^{m-3}$, we get a contradiction.

So for all H hyperplanes, $\# (S\cap H)\ge (q-1)(q-2)q^{m-3}$. By induction hypothesis and considering q parallel hyperplanes there exists an affine hyperplane $H_0$ such that $\#(S\cap H_0)=(q-1)(q-2)q^{m-3}$ or $\#(S\cap H_0)=(q-1)^3q^{m-4}$. In both cases, we get that there exists A an affine subspace of codimension 2 included in $H_0$ which does not meet S. Considering all hyperplanes through A, since for all H hyperplanes, $\#(S\cap H)\ge (q-1)(q-2)q^{m-3}$, we get

$$\begin{aligned} (q+1)(q-1)(q-2)q^{m-3}<((q-1)^3+1)q^{m-3} \end{aligned}$$

and this is absurd. So there exists an affine hyperplane $H_1$ which does not meet S. Denote by n the number of hyperplanes parallel to $H_1$ which do not meet S.

By applying an affine transformation, we can assume $x_1=\lambda _1$ is an equation of $H_1$. We have $n\le 3$.

If $n=3$, then for all $x=(x_1,\cdots ,x_m)\in F_q^m$ we can write

$$\begin{aligned} f(x)= (x_1-\lambda _1) (x_1-\lambda _2)(x_1-\lambda _3) g(x) \end{aligned}$$

where $\lambda _i\in F_q$, $\lambda _i\ne \lambda _j$ for all $i\ne j$, $deg(g)=0$. So $|f|=(q-3)q^{m-1}$ that gives a minimum weight codeword of $R_q(3,m)$ which is absurd.

If $n=2$, then for all $x=(x_1,\cdots ,x_m)\in F_q^m$ we can write

$$\begin{aligned} f(x)= (x_1-\lambda _1) (x_1-\lambda _2) g(x) \end{aligned}$$

where $\lambda _i\in F_q$, $\lambda _1\ne \lambda _2$, $deg(g)\le 1$. If $deg(g)=0$, $|f|=(q-2)q^{m-1}$. If $deg(g)=1$, $|f|=(q-2)(q-1)q^{m-2}$. We get a contradiction in both cases.

From now, assume $n=1$. Then for all $x=(x_1,\cdots ,x_m)\in F_q^m$ we have

$$\begin{aligned} f(x)= (x_1-\lambda _1) g(x) \end{aligned}$$

where $deg(g)\le 2$. Then for $i\ge 2$, $deg(f_{\lambda _i})\le 2$ and so either $|f_{\lambda _i}|=(q-2)q^{m-2}$ or $|f_{\lambda _i}|=(q-1)^2q^{m-3}$ or $|f_{\lambda _i}|\ge (q^2-q-1)q^{m-3}$ (see [13]). Since

$$\begin{aligned} (q-1)(q^2-q-1)q^{m-3}\ge ((q-1)^3+1)q^{m-3}, \end{aligned}$$

is a contradiction, there exists $i\ge 2$ such that $|f_{\lambda _i}|=(q-2)q^{m-2}$ or $|f_{\lambda _i}|=(q-1)^2q^{m-3}$. Denote by $H'$ a hyperplane such that $\#(S\cap H')=(q-2)q^{m-2}$ ($\#(S\cap H')=(q-1)^2q^{m-3}$). Then there exist $P_1$ and $P_2$ two parallel affine subspaces of codimension 2 (two affine subspaces of codimension 2 intersect in an affine subspace of codimension 3) included in $H'$ not in S. Consider P an affine subspace of codimension 2 included in $H'$ which intersect $P_1$ and $P_2$ (in two different subspace of codimension 3). Then $\#(S\cap P)=(q-2)q^{m-3}$. Then for all H hyperplane through P, $\#(S\cap H)\ge (q-1)(q-2)q^{m-3}$. We can apply the same argument to all affine subspaces of codimension 2 included in $H'$ parallel to P. Now, consider a hyperplane through P and the $q-1$ parallel hyperplanes to this hyperplane. Since $|f|<((q-1)^3+1)q^{m-3}$, by induction hypothesis one of these hyperplanes say $H''$ meets S either in $(q-2)(q-1)q^{m-3}$ or $(q-1)^3q^{m-4}$ points.

Denote by $(A_i)_{1\le i\le 3}$ the 3 affine subspaces of codimension 2 included in $H''$ which do not meet S. Suppose that S meets all hyperplanes through $A_i$ and consider H one of them. If all hyperplanes parallel to H meet S then as in the beginning of the proof of this lemma, we get that $\#(S\cap H)\ge (q-1)(q-2)q^{m-3}$. If there exists a hyperplane parallel to H which does not meet S then $\#(S\cap H)\ge (q-2)q^{m-2}$. In all cases we get a contradiction since $(q+1)(q-1)(q-2)q^{m-3}\ge ((q-1)^3+1)q^{m-3}$.

Then there exist three hyperplanes $H_1$ (with the equation $x_1=\lambda _1$), $H_2$ and $H_3$ which do not meet S. Since $n=1$, the intersection of $H_2$ and $H_3$ is an affine subspace of codimension 2 say $A_{2,3}$. There are three following cases:

If $A_{2,3}$ is contained in the hyperplane $H_1$, then for all $i\ge 2$ $|f_{\lambda _i}|=(q-2)q^{m-2}$. So $|f|=(q-1)(q-2)q^{m-2}$ which is absurd.

If $A_{2,3}$ is contained in one of the hyperplanes $x_1=\lambda _j$ for $j\ge 2$, then $|f_{\lambda _j}|=(q-1)q^{m-2}$ and $|f_{\lambda _i}|=(q-2)q^{m-2}$ for $i\ge 2$ and $i\ne j$. So

$$\begin{aligned} |f|= & {} (q-2)(q-2)q^{m-2}+(q-1)q^{m-2}\\= & {} (q^2-3q+3)q^{m-2}\\= & {} ((q-1)^3+1)q^{m-3}, \end{aligned}$$

we get a contradiction, since $|f|<((q-1)^3+1)q^{m-3}$.

If $A_{2,3}$ meets the hyperplane $x_1=\lambda _i$ in an affine subspace $P_i$ of codimension 3 for all i, then $|f_{\lambda _i}|=(q-1)^2q^{m-3}$. So $|f|=(q-1)(q-1)^2q^{m-3}=(q-1)^3q^{m-3}$ which is absurd. $\square$

In what follows, let

$$\begin{aligned} {\tilde{c}}_b= \left\{ \begin{array}{lr} (q-2)(q-b+2)q &{} \textrm{if} \ \ 4\le b< \frac{q+4}{3}, \ \ q\ge 9 \\ (q-1)^3 &{} \textrm{if} \ \ b=3, \ \ q\ge 7 \end{array}\right. \end{aligned}$$

and

$$\begin{aligned} {\tilde{d}}_b= \left\{ \begin{array}{lr} (q-1)^2(q-b+2) &{} \textrm{if} \ \ 4\le b< \frac{q+4}{3}, \ \ q\ge 9 \\ (q-1)^3+1 &{} \textrm{if} \ \ b=3, \ \ q\ge 7 \end{array}\right. \end{aligned}$$

Proposition 1

Let $m\ge 3$, $q\ge 9$, $0\le a\le m-3$, $3\le b <\frac{q+4}{3}$ and $f\in R_q(a(q-1)+b,m)$. If $|f|>{\tilde{c}}_b q^{m-a-3}$ then $|f|\ge {\tilde{d}}_b q^{m-a-3}$.

Proof

The cases where $a=0$ or $m=3$ have been considered in Lemmas 10 and 12. Assume $m\ge 4$ and $a\ge 1$. We prove the result by induction on $m-a$. The case where $a=m-3$ is an immediate result for $b=3$ and follows from Lemma 11 for $b\ge 4$. If $m=4$, the only possibilities are $a=0$ and $a=1$ that have been considered before. So, from now suppose that $m\ge 5$. Let $1\le a\le m-4$. Assume if $f\in R_q((a+1)(q-1)+b,m)$ is such that $|f|>{\tilde{c}}_b q^{m-a-4}$ then, $|f|\ge {\tilde{d}}_b q^{m-a-4}$.

Let $f\in R_q(a(q-1)+b,m)$ such that $|f|>{\tilde{c}}_bq^{m-a-3}$. Assume $|f|<{\tilde{d}}_b q^{m-a-3}$. Denote by S the support of f.

Suppose that S meets all affine hyperplanes. We set an order on the elements of $F_q$ such that $|f_{\lambda _1}|\le \cdots \le |f_{\lambda _q}|$. Since $|f|<{\tilde{d}}_b q^{m-a-3}$, by induction hypothesis, $f_{\lambda _1}$ is either a minimal weight codeword or second weight codeword or third weight codeword of $R_q(a(q-1)+b, m-1)$. In all cases, by applying an affine transformation we can assume $(1-x_2^{q-1})$ divides $f_{\lambda _1}$. Let $k\ge 1$ be such that for all $i \le k$, $(1 - x_2^{q-1})$ divides $f_{\lambda _i}$ but $(1-x_2^{q-1})$ does not divide $f_{\lambda _{k+1}}$. Then, by Lemma 6,

$$\begin{aligned} |f|\ge (q-b)q^{m-a-1}+k(q-k)q^{m-a-2}\ge (q-b)q^{m-a-1}+(q-1)q^{m-a-2} \end{aligned}$$

which is absurd, since $(q-b)q^{m-a-1}+(q-1)q^{m-a-2}\ge {\tilde{d}}_b q^{m-a-3}$.

So there exists a hyperplane $H_0$ which does not meet S. By applying an affine transformation we can assume $x_1 = \alpha$, $\alpha \in F_q$, is an equation of $H_0$. We denote by n the number of hyperplanes parallel to $H_0$ which do not meet S.

If $n=q-1$, then we can write for all $x=(x_1,\cdots , x_m)\in F_q^m$

$$\begin{aligned} f(x)=(1-x_1^{q-1})g(x_2,\cdots , x_m) \end{aligned}$$

where $g\in R_q((a-1)(q-1)+b,m-1)$ and $|f|=|g|$. Then g has the same conditions as f. Iterating this process, we end either in the case where $a = 0$ (which gives a contradiction by Lemma 10 and 12) or in the case where $n<q-1$. So from now we assume $n<q-1$. Since $|f|<{\tilde{d}}_b q^{m-a-3}$, by Lemma 2 the only possibilities are $n\in \{1, 2, b-2, b-1, b\}$. We can write for all $x=(x_1,\cdots , x_m)\in F_q^m$

$$\begin{aligned} f(x)=\prod _{i=1}^n (x_1-\lambda _i)g(x) \end{aligned}$$

where $g\in R_q(a(q-1)+b-n,m)$. Then for all $i\ge n+1$, $f_{\lambda _i}\in R_q(a(q-1)+b-n,m-1)$ and $|f_{\lambda _i}|=|g_{\lambda _i}|\ge (q-b+n)q^{m-a-2}$.

Assume $n=b$. For $\lambda \in F_q$, if $|g_{\lambda }|>q^{m-a-1}$, then $|g_{\lambda }|\ge 2(q-1)q^{m-a-2}$. We denote By $N=\#\{i\ge b+1: |g_{\lambda _i}|=q^{m-a-1}\}$. Since for $i\ge b+1$ $|f_{\lambda _i}|=|g_{\lambda _i}|$ and $(q-b)2(q-1)q^{m-a-2}>{\tilde{d}}_b q^{m-a-3}$, $N\ge 1$. On the other hand since $(q-b)q^{m-a-1}<{\tilde{c}}_b q^{m-a-3}<|f|$, $N\le q-b-1$.

Assume $|f_{\lambda _{b+N+1}}|\ge (N+1)q^{m-a-1}$. Then

$$\begin{aligned} Nq^{m-a-1}+(q-b-N)(N+1)q^{m-a-1}\le |f|<{\tilde{d}}_b q^{m-a-3} \end{aligned}$$

which gives

$$\begin{aligned} (q-b)Nq^2-N^2q^2<{\tilde{d}}_b -(q-b)q^2 \end{aligned}$$

therefore

$$\begin{aligned} N(q-b-N)q^2<(2b-3)q. \end{aligned}$$

which is absurd since $N(q-b-N)\ge 1$ and $b< \frac{q+4}{3}$.

If $|f_{\lambda _{b+N+1}}|=Nq^{m-a-1}$, then

$$\begin{aligned} Nq^{m-a-1}+(q-b-N)Nq^{m-a-1}\le |f|<{\tilde{d}}_b q^{m-a-3} \end{aligned}$$

which gives

$$\begin{aligned} Nq^2(q-b-N+1)<{\tilde{d}}_b<q^2(q-b+1). \end{aligned}$$

So we have

$$\begin{aligned} (N-1)(q-b+1)<N^2 \end{aligned}$$

which is absurd for $2\le N\le q-b-1$. So the only possibility such that $|f_{\lambda _{b+N+1}}|=Nq^{m-a-1}$ is the case where $N=1$ that is a contradiction by definition of N.

By Lemma 8, for all $b+1\le i\le N+b$, $g_{\lambda _{b+1}}=g_{\lambda _i}$. So we can write for all $x=(x_1,\cdots , x_m)\in F_q^m$

$$\begin{aligned} f(x)= & {} \prod _{1\le i\le b}(x_1-\lambda _i)\Bigg (g_{\lambda _{b+1}}(x_2,\cdots , x_m)+\prod _{b+1\le i\le N+b}(x_1-\lambda _i)h(x)\Bigg )\\= & {} \prod _{1\le i\le b}(x_1-\lambda _i)\Bigg (\alpha f_{\lambda _{b+1}}(x_2,\cdots , x_m)+\prod _{b+1\le i\le N+b}(x_1-\lambda _i)h(x)\Bigg ) \end{aligned}$$

where $h\in R_q(a(q-1)-N, m)$ and $\alpha \in F_q^*$.

Then, for all $(x_2,\cdots , x_m)\in F_q^{m-1}$,

$$\begin{aligned} f_{\lambda _{b+N+1}}(x_2,\cdots , x_m)=\beta f_{\lambda _{b+1}}(x_2,\cdots , x_m)+\gamma h_{\lambda _{b+N+1}}(x_2,\cdots , x_m). \end{aligned}$$

This is a contradiction by Lemma 7.

From now, assume $n\in \{1, 2, b-2, b-1\}$.

Applying argument as in the begining of the proof of this proposition, we can assume that $(1-x_2^{q-1})$ does not divide f.

Since $n\ge 1$, $f_{\lambda _1}=0$. So, $(1-x_2^{q-1})$ divides $f_{\lambda _1}$. Since $(1-x_2^{q-1})$ does not divide f, there exists $k\in \{1, \cdots , q-1\}$ such that for all $i\le k$, $(1-x_2^{q-1})$ divides $f_{\lambda _i}$ and $(1-x_2^{q-1})$ does not divide $f_{\lambda _{k+1}}$. For $i\ge n+1$, if $|f_{\lambda _i}|> (q-b+n)q^{m-a-2}$ then

$$\begin{aligned} |f_{\lambda _i}|\ge W_2= \left\{ \begin{array}{lr} q^{m-a-1} &{} \textrm{if} \ \ n=b-1, \\ (q-1)(q-b+2)q^{m-a-3} &{} \textrm{if} \ \ n=1,\\ (q-1)(q-b+3)q^{m-a-3} &{} \textrm{if} \ \ n=2 \ and \ b\ne 3,\\ (q-1)^2q^{m-a-3} &{} \textrm{if} \ \ n=b-2. \end{array}\right. \end{aligned}$$

We denote by $N=\#\{i\ge n+1: |f_{\lambda _i}|=(q-b+n)q^{m-a-2}\}$. Since for $n\in \{1, 2, b-2, b-1\}$ if $(n,b)\ne (1,3)$ $(q-n)W_2\ge {\tilde{d}}_b q^{m-a-3}$, $N\ge 1$. Furthermore, in all cases, $(q-n)(q-b+n)q^{m-a-2}\le {\tilde{c}}_b q^{m-a-3}<|f|$. So $N\le q-n-1$.

Assume $(n,b)=(1,3)$. We denote by $N=\#\{i\ge 2: |f_{\lambda _i}|=(q-2)q^{m-a-2} \ or \ |f_{\lambda _i}|=(q-1)^2q^{m-a-3}\}$. For $i\ge 2$, if $|f_{\lambda _i}|>(q-1)^2q^{m-a-3}$ then $|f_{\lambda _i}|\ge W_3= (q^2-q-1)q^{m-a-3}$. Since $(q-1)(q^2-q-1)q^{m-a-3}> ((q-1)^3+1)q^{m-a-3}$, $N\ge 1$. Also, since $(q-1)(q-1)^2q^{m-a-3}<|f|$, $N\le q-2$.

The above arguments show that for $3\le b<\frac{q+4}{3}$ and $n\in \{1, 2, b-2, b-1\}$ except possibly $(n,b)=(1,3)$ $f_{\lambda _{n+1}}$ is a minimum weight codeword of $R_q(a(q-1)+b-n, m-1)$ and if $(n,b)=(1,3)$ $f_{\lambda _{n+1}}$ is either a minimum or second minimum weight codeword of $R_q(a(q-1)+2,m-1)$. So by applying an affine transformation we can assume $(1-x_2^{q-1})$ divides $f_{\lambda _{n+1}}$. Thus $k\ge n+1\ge 2$.

If $N\ge 2$ and $n+1\le k\le n+N-1$, then $k+1\in N$ and so $|f_{\lambda _{k+1}}|<(q-b+k)q^{m-a-2}$. If $N=1$ and $n+1\le k\le q-1$ or $N\ge 2$ and $n+N\le k\le q-1$, assume that $|f_{\lambda _{k+1}}|\ge (q-b+k)q^{m-a-2}$. We get

$$\begin{aligned} |f|\ge N(q-b+n)q^{m-a-2}+(k-n-N)W_2+(q-k)(q-b+k)q^{m-a-2} \end{aligned}$$

which is absurd since $|f|<{\tilde{d}}_b q^{m-a-3}$ and $1\le N\le q-n-1$.

Since $(1-x_2^{q-1})$ divides $f_{\lambda _i}$ for all $i\le k$, it divides $g_{\lambda _i}$ too. Therefore, we can write for all $x=(x_1, x_2, \cdots , x_m)\in F_q^m$

$$\begin{aligned} f(x)= & {} \prod _{1\le i\le n}(x_1-\lambda _i)\Bigg (\prod _{n+1\le i\le k}(x_1-\lambda _i)h(x_1,x_2,\cdots , x_m)\\{} & {} +(1-x_2^{q-1})l(x_1,x_3,\cdots , x_m)\Bigg ) \end{aligned}$$

with $deg(h)\le a(q-1)+b-k$ and $l\in R_q((a-1)(q-1)+b-n, m-1)$. Then for all $(x_2,\cdots , x_m)\in F_q^{m-1}$,

$$\begin{aligned} f_{\lambda _{k+1}}(x_2,\cdots , x_m)=\alpha h_{\lambda _{k+1}}(x_2,\cdots , x_m)+\beta (1-x_2^{q-1})l_{\lambda _{k+1}}(x_3,\cdots , x_m). \end{aligned}$$

We get a contradiction by Lemma 5, since $k\ge 2$ and $|f_{\lambda _{k+1}}|<(q-b+k)q^{m-a-2}$ $\square$

4 An upper bound on the fourth weight

Theorem 5

Let $q\ge 3$, $m\ge 2$, $0\le a\le m-1$, $1\le b\le q-1$, then if $W_4$ is the fourth weight of $R_q(a(q-1)+b,m)$, we have

• (1) If $b=1$ then,

  • for $q=3$, $m\ge 3$ and $1\le a\le m-2$, $W_4\le 4.3^{m-a-1}$,

  • for $q=4$, $m\ge 3$ and $1\le a\le m-2$, $W_4\le 6.4^{m-a-1}$,

  • for $q=3$ and $a=m-1$ or $q=4$ and $a=m-1$, $W_4\le 2q$,

  • for $q\ge 5$ and $1\le a\le m-1$, $W_4\le 2(q-1)q^{m-a-1}$,

• (2) If $2\le b\le q-1$

  • for $q\ge 5$, $m\ge 3$, $0\le a\le m-3$, and $4\le b\le \lfloor \frac{q}{2}+2\rfloor$, $W_4\le (q-1)^2(q-b+2)q^{m-a-3}$,

  • for $q\ge 7$, $0\le a\le m-2$, and $\lfloor \frac{q}{2}+2\rfloor \le b\le q-1$, $W_4\le (q-2)(q-b+2)q^{m-a-2}$,

  • for $q\ge 4$, $m\ge 3$, $0\le a\le m-3$ and $b=3$, $W_4\le ((q-1)^3+1)q^{m-a-3}$,

  • for $q\ge 4$, $0\le a\le m-2$ and $b=2$, $W_4\le q^{m-a}$.

  • for $q=3$, $1\le a\le m-1$ and $b=2$, $W_4\le 2.3^{m-a-1}$.

Proof

• (1)

  • For $q=3$, $m\ge 3$ and $1\le a\le m-2$, define for $x=(x_1,\cdots ,x_m)\in F_q^m$,

    $$\begin{aligned} f(x)=\prod _{i=1}^{a-1} (1-x_i^{2}) (x_{a}-u)(x_{a+1}-v) \end{aligned}$$

    with $u, v\in F_q$. Then, $f \in R_3(2a,m)$ and $|f|=4.3^{m-a-1}\ge 3^{m-a}$.

  • For $q=4$, $m\ge 3$ and $1\le a\le m-2$, define for $x=(x_1,\cdots ,x_m)\in F_q^m$,

    $$\begin{aligned} f(x)=\prod _{i=1}^{a-1} (1-x_i^{3}) (x_{a}-u)(x_{a}-v)(x_{a+1}-w) \end{aligned}$$

    with $u, v, w\in F_q$ and $u \ne v$. Then, $f \in R_4(3a,m)$ and $|f|=6.4^{m-a-1}\ge 18.4^{m-a-2}$.

  • For $q=3$ and $a=m-1$ define for $x=(x_1,\cdots , x_m)\in F_3^m$

    $$\begin{aligned} f(x)=\prod _{i=1}^{m-2} (1-x_i^{2}) (x_{m-1}-u) \end{aligned}$$

    with $u\in F_q$. Then, $f\in R_q(2m-3, m)\subset R_q(2(m-1)+1,m)$ and $|f|=6>4\ge W_3$.

  • For $q=4$ and $a=m-1$ define for $x=(x_1,\cdots , x_m)\in F_4^m$

    $$\begin{aligned} f(x)= & {} \prod _{i=1}^{m-3} (1-x_i^{3}) (x_{m-2}-u_1)(x_{m-2}-u_2)(x_{m-1}-u_3)\\{} & {} (x_{m-1}-u_4)(x_m-u_5)(x_m-u_6) \end{aligned}$$

    with $u_i\in F_q$ and $u_{2i-1}\ne u_{2i}$ for $i=1,2,3$. Then, $f\in R_q(3\,m-3, m)\subset R_q(3(m-1)+1,m)$ and $|f|=8>6\ge W_3$.

  • For $q\ge 5$ and $1\le a\le m-1$ define for $x=(x_1,\cdots , x_m)\in F_q^m$

    $$\begin{aligned} f(x)=\prod _{i=1}^{a-1} (1-x_i^{q-1}) \prod _{j=1}^{q-2}(x_a-b_j)(x_{a+1}-u) \end{aligned}$$

    with $u,b_j\in F_q$ and $b_i\ne b_j$ for $i\ne j$. Then $f\in R_q(a(q-1),m)\subset R_q(a(q-1)+1,m)$ and $|f|=2(q-1)q^{m-a-1}>2(q-2)q^{m-a-1}\ge W_3$.

• (2) For $q\ge 5$, $0\le a\le m-3$ and $4\le b\le \lfloor \frac{q}{2}+2\rfloor$, define for $x=(x_1,\cdots ,x_m)\in F_q^m$,

  $$\begin{aligned} f(x)=\prod _{i=1}^a (1-x_i^{q-1}) \prod _{j=1}^{b-2}(x_{a+1}-b_j)(x_{a+2}-c)(x_{a+3}-d) \end{aligned}$$

  with $b_j\in F_q$, $b_j\ne b_k$ for $j\ne k$ and $c,d\in F_q$. Then, $f\in R_q(a(q-1)+b,m)$ and $|f|=(q-1)^2(q-b+2)q^{m-a-3}>(q-2)(q-b+2)q^{m-a-2}$.

  • For $q\ge 7$, $0\le a\le m-2$, $\lceil \frac{q}{2}+2\rceil \le b\le q-1$, define for $x=(x_1,\cdots ,x_m)\in F_q^m$,

    $$\begin{aligned} f(x)=\prod _{i=1}^a (1-x_i^{q-1}) \prod _{j=1}^{b-2}(x_{a+1}-b_j)(x_{a+2}-c)(x_{a+2}-d) \end{aligned}$$

    with $b_j\in F_q$, $b_j\ne b_k$ for $j\ne k$, $c,d\in F_q$ and $c\ne d$. Then, $f\in R_q(a(q-1)+b,m)$ and $|f|=(q-2)(q-b+2)q^{m-a-2}>W_3$.

  • For $q\ge 4$, $m\ge 3$, $0\le a\le m-3$ and $b=3$,

    $$\begin{aligned} f(x)=\prod _{i=1}^a (1-x_i^{q-1}) (x_{a+1}-c)(x_{a+2}-d)(\alpha x_{a+1}+\beta x_{a+2}-e) \end{aligned}$$

    with $c, d, e\in F_q$, $\alpha , \beta \in F_q^*$ and $e\ne \alpha c+\beta d$. Then, $f\in R_q(a(q-1)+3,m)$ and $|f|=((q-1)^3+1)q^{m-a-3}>(q-1)^3q^{m-a-3}$.

  • For $q\ge 4$, $0\le a\le m-2$ and $b=2$, define for $x=(x_1,\cdots , x_m)\in F_q^m$,

    $$\begin{aligned} f(x)=\prod _{i=1}^a (1-x_i^{q-1}) \end{aligned}$$

    then, $f\in R_q(a(q-1),m)\subset R_q(a(q-1)+2,m)$ and $|f|=q^{m-a}>(q-1)q^{m-a-1}\ge W_3$.

  • For $q=3$, $1\le a\le m-1$ and $b=2$, define for $x=(x_1,\cdots , x_m)\in F_q^m$,

    $$\begin{aligned} f(x)=\prod _{i=1}^a (1-x_i^{2})(x_{a+1}-u) \end{aligned}$$

    with $u\in F_q$. Then, $f\in R_3(2a+1,m)\subset R_3(2a+2,m)$ and $|f|=2.3^{m-a-1}>16.3^{m-a-3}\ge W_3$.

$\square$

5 Fourth weight in the case where $m\ge 3$

By combining the results in Sections 3 and 4, we have the following results.

Theorem 6

Let $m\ge 3$, $q\ge 9$, $0\le a\le m-3$ and $4\le b< \frac{q+4}{3}$. The fourth weight of $R_q(a(q-1)+b, m)$ is $W_4=(q-1)^2(q-b+2)q^{m-a-3}$.

Theorem 7

Let $m\ge 3$, $q\ge 7$ and $0\le a\le m-3$. The fourth weight of $R_q(a(q-1)+3, m)$ is $W_4=((q-1)^3+1)q^{m-a-3}$.

Proof

By Proposition 1 we have

$$\begin{aligned} W_4\ge \left\{ \begin{array}{lr} (q-1)^2(q-b+2)q^{m-a-3} &{} \textrm{if} \ \ 4\le b< \frac{q+4}{3}, \\ ((q-1)^3+1)q^{m-a-3} &{} \textrm{if} \ \ b=3. \end{array}\right. \end{aligned}$$

By Theorem 5 Part (2), there exists $g\in R_q(b,3)$ such that $|g|={\tilde{d}}_b$. For $x=(x_1,\cdots , x_m)\in F_q^m$, we define

$$\begin{aligned} f(x)=\prod _{i=1}^a (1-x_i^{q-1}) g(x_{a+1}, x_{a+2}, x_{a+3}). \end{aligned}$$

Then $f\in R_q(a(q-1)+b, m)$ and $|f|=|g|q^{m-a-3}$ which proves both of theorems. $\square$

6 Fourth weight in the case where $m=2$

In this section, we determine the fourth weight and the fourth weight codewords of $R_q(b,2)$.

Proposition 2

For $q\ge 11$, the fourth weight of $R_q(4,2)$ is $W_4=(q-2)^2+1$.

Furthermore, if $f\in R_q(4, 2)$ is such that $|f|=(q-2)^2+1$ then up to affine transformation for all $(x,y)\in F_q^2$ either

$$\begin{aligned} f(x,y)=\prod _{j=1}^2 (a_1x+b_1y+c_j)(a_2x+b_2y)(a_3x+b_3y) \end{aligned}$$

with $(a_i,b_i)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c_j\in F_q^*$ for $j=1,2$

or

$$\begin{aligned} f(x,y)=\prod _{j=1}^3 (a_jx+b_jy)(a_4x+b_4y+c) \end{aligned}$$

with $(a_i,b_i)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c\in F_q^*$.

Proof

The third weight in this case is $(q-2)^2$. So if there exists $f\in R_q(4,2)$ such that $|f|=(q-2)^2+1$, $W_4=(q-2)^2+1$ and f is a fourth weight codeword of $R_q(4,2)$. Since $(q-2)^2+1<(q-3)q$ and $(q-3)q$ is the minimum weight of $R_q(3,2)$, $deg(f)=4$. We prove first that f is the product of 4 affine factors. Let p be a point of $F_q^2$ which is not in S and l be a line in $F_q^2$ such that $p\in l$. Then either l does not meet S or l meets S in at least $q-4$ points. If any line through p meets S then,

$$\begin{aligned} (q+1)(q-4)\le |f|=(q-2)^2+1 \end{aligned}$$

which is absurd for $q\ge 11$. So there exists a line through p which does not meet S. By applying the same argument to all points not in S, we get that f is the product of affine factors.

Denote by Z the set of zeros of f. We have just proved that Z is the union of 4 lines in $F_q^2$. If the 4 lines are parallel then, f is the minimum weight codeword of $R_q(4,2)$ which is absurd. If 3 of these lines are parallel or the 4 lines intersect in one common point, f is a second weight codeword of $R_q(4,2)$ which is absurd. Assume 2 of these lines are parallel. If the 2 other lines are parallel or intersect in a point which is included in one of the parallel lines then, f is a third weight codeword of $R_q(4,2)$ which is absurd. If the 2 other lines intersect in a point which is not included in any of the parallel lines then we are in the first case of the proposition. Finally, assume all of 4 lines intersect pairwise. They can not intersect in one point. If 3 of 4 lines intersect in a point then, we are in the second case of the proposition. Otherwise $|Z|=4q-6<4q-5$ which is absurd. $\square$

Proposition 3

For $q\ge 13$, the fourth weight of $R_q(5,2)$ is $W_4=(q-2)(q-3)+1$.

Furthermore, if $f\in R_q(5,2)$ is such that $|f|=(q-2)(q-3)+1$ then up to affine transformation for all $(x,y)\in F_q^2$ either

$$\begin{aligned} f(x,y)=\prod _{j=1}^3 (a_1x+b_1y+c_j)(a_2x+b_2y)(a_3x+b_3y) \end{aligned}$$

with $(a_i,b_i)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c_j\in F_q^*$ for $j=1,2,3$

or

$$\begin{aligned} f(x,y)= & {} \prod _{i=1}^2(a_1x+b_1y+c_i)\prod _{j=1}^2(a_2x+b_2y+d_j)(\alpha (a_1x+b_1y+c_i)\\{} & {} +\beta (a_2x+b_2y+d_j)), \ \ \ i,j\in \{1,2\} \end{aligned}$$

with $(a_i,b_i)\in F^2_q{\setminus } \{(0,0)\}$, $a_1b_2-a_2b_1\ne 0$, $c_i,d_i\in F_q$ are such that $c_1\ne c_2$ and $d_1\ne d_2$ and $\alpha , \beta \in F_q^*$

or

$$\begin{aligned} f(x,y)= & {} \prod _{i=1}^3(a_ix+b_iy)(a_1x+b_1y+c)(\alpha (a_jx+b_jy)+\beta (a_1x+b_1y+c)),\\{} & {} j=2,3 \end{aligned}$$

with $(a_i,b_i)\in F_q^2{\setminus } \{(0,0)\}$, $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c,\alpha , \beta \in F^*_q$

or

$$\begin{aligned} f(x,y)=\prod _{j=1}^4 (a_jx+b_jy)(a_5x+b_5y+c) \end{aligned}$$

with $(a_j,b_j)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c\in F_q^*$.

Proof

The third weight in this case is $(q-2)(q-3)$. So if there exists $f\in R_q(5,2)$ such that $|f|=(q-2)(q-3)+1$, $W_4=(q-2)(q-3)+1$ and f is a fourth weight codeword of $R_q(5,2)$. Let $f\in R_q(5,2)$ such that $|f|=(q-2)(q-3)+1$. Since $(q-2)(q-3)+1<(q-4)q$ and $(q-4)q$ is the minimum weight of $R_q(4,2)$, $deg(f)=5$. We prove first that f is the product of 5 affine factors. Let p be a point of $F_q^2$ which is not in S and l be a line in $F_q^2$ such that $p\in l$. Then either l does not meet S or l meets S in at least $q-5$ points. If any line through p meets S then

$$\begin{aligned} (q+1)(q-5)\le |f|=(q-3)(q-2)+1 \end{aligned}$$

which is absurd for $q\ge 13$. So there exists a line through p which does not meet S. By applying the same argument to all points not in S, we get that f is the product of affine factors.

Denote by Z the set of zeros of f. We have just proved that Z is the union of 5 lines in $F_q^2$. If the 5 lines are parallel then f is a minimum weight codeword of $R_q(5, 2)$ which is absurd. If 4 of these lines are parallel or the 5 lines intersect in one common point, then f is a second minimum weight codeword of $R_q(5,2)$ which is absurd. Assume that 3 of these lines are parallel. Consider all possibilities:

• 1. If the 2 other lines are parallel or intersect in one point which is included in one of the parallel lines then, f is a third minimum weight codeword of $R_q(5,2)$ which is absurd.

• 2. If the 2 other lines intersect in one point which is not included in any of the parallel lines then we are in the first case of the proposition.

Assume 2 of these lines are parallel. Consider all of cases.

• 1. If an other pair of lines are parellel and the fifth line meets the four other lines in two points then, f is a third minimum weight codeword of $R_q(5,2)$ which is absurd. If the fifth line meets the four other lines in three points then, we are in the second case of the proposition. Otherwise $\#Z=5q-8<5q-7$ which is absurd.

• 2. If the 3 other lines intersect in one common point which is included in one of the parallel lines then, f is a third minimum weight codeword of $R_q(5,2)$ which is absurd. If 2 of the three other lines intersect in a point which is included in one of 2 parallel lines and the fifth line meets the four other lines in 3 points then, we are in the third case of the proposition. Otherwise $\#Z\le 5q-8<5q-7$ which is absurd.

Assume all lines intersect pairwise. They can not intersect in one point. If 4 of 5 lines intersect in one common point and the fifth line meets the other lines in different points of that point then, we are in the last case of the proposition. Otherwise $\#Z\le 5q-8<5q-7$ which is absurd. $\square$

Proposition 4

For $q\ge 16$, the fourth weight of $R_q(6,2)$ is $W_4=(q-2)(q-4)+1$.

Furthermore, if $f\in R_q(6,2)$ is such that $|f|=(q-2)(q-4)+1$ then up to affine transformation for all $(x,y)\in F_q^2$ either

$$\begin{aligned} f(x,y)=\prod _{j=1}^4 (a_1x+b_1y+c_j)(a_2x+b_2y)(a_3x+b_3y) \end{aligned}$$

with $(a_i,b_i)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c_j\in F_q^*$ for $j=1,2,3,4$

or

$$\begin{aligned} f(x,y)=\prod _{i=1}^3(a_1x+b_1y+c_i) \prod _{j=1}^3(a_2x+b_2y+d_j) \end{aligned}$$

with $(a_i,b_i)\in F^2_q\setminus \{(0,0)\}$ are such that $a_1b_2-a_2b_1\ne 0$, $c_i,d_i\in F_q$ and $c_i\ne c_j$, $d_i\ne d_j$ for $i\ne j$

or

$$\begin{aligned} f(x,y)=\prod _{i=1}^3(x-a_i)\prod _{j=1}^2(y-b_j)\Big ((a_i-a_k)y+(b_1-b_2)x+a_kb_2-a_ib_1\Big ) \ \ \ \ \ \ \ i\ne k \end{aligned}$$

with $a_i,b_j\in F_q$, $b_1\ne b_2$ and $a_i\ne a_j$ for $i\ne j$

or

$$\begin{aligned} f(x,y)=(a_1x+b_1y)\prod _{i=1}^2(a_1x+b_1y+c_i) \prod _{j=2}^4(a_jx+b_jy) \end{aligned}$$

with $(a_i,b_i)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$, $c_1,c_2\in F_q^*$ and $c_1\ne c_2$

or

$$\begin{aligned} f(x,y)= & {} \prod _{i=1}^3(x-a_i)(y-b_1)(\alpha x+\beta y-\alpha a_1-\beta b_1) \Big (\alpha (a_1-a_2)(x-a_3)\\{} & {} +\beta (a_3-a_2)(y-b_1)\Big ) \end{aligned}$$

with $b_1, a_i\in F_q$, $a_i\ne a_j$ for $i\ne j$ and $\alpha , \beta \in F_q^*$

or

$$\begin{aligned} f(x,y)= & {} \prod _{i=1}^2(x-a_i)\prod _{j=1}^2(y-b_j)\Big ((b_2-b_1)x+(a_2-a_1)y+a_1b_1-a_2b_2\Big )\\{} & {} \Big ((b_2-b_1)x+(a_2-a_1)y+a_1b_2+a_2b_1-2a_2b_2\Big ) \end{aligned}$$

with $a_i,b_i\in F_q$ are such that $a_1\ne a_2$ and $b_1\ne b_2$ and $a_1b_1+a_2b_2\ne a_1b_2+a_2b_1$

or

$$\begin{aligned} f(x,y)= & {} \prod _{i=1}^2(x-a_i)\prod _{j=1}^2(y-b_j)\Big ((b_2-b_1)x+(a_2-a_1)y+a_1b_1-a_2b_2\Big )\\{} & {} \Big ((b_1-b_2)x+(a_2-a_1)y+b_2a_1-b_1a_2\Big ) \end{aligned}$$

with $a_i,b_i\in F_q$ are such that $a_1\ne a_2$ and $b_1\ne b_2$

or

$$\begin{aligned} f(x,y)=\prod _{j=1}^5 (a_jx+b_jy)(a_6x+b_6y+c) \end{aligned}$$

with $(a_j,b_j)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c\in F_q^*$.

Proof

The third weight in this case is $(q-2)(q-4)$. So if there exists $f\in R_q(6,2)$ such that $|f|=(q-2)(q-4)+1$, $W_4=(q-2)(q-4)+1$ and f is a fourth weight codeword of $R_q(6,2)$. Let $f\in R_q(6,2)$ such that $|f|=(q-2)(q-4)+1$. Since $(q-2)(q-4)+1<q(q-5)$ and $q(q-5)$ is the minimum weight of $R_q(5,2)$, $deg(f)=6$. We prove first that f is the product of 6 affine factors. Let p be a point of $F_q^2$ which is not in S and l be a line in $F_q^2$ such that $p\in l$. Then either l does not meet S or l meets S in at least $q-6$ points. If any line through p meets S then

$$\begin{aligned} (q+1)(q-6)\le |f|=(q-2)(q-4)+1 \end{aligned}$$

which is absurd for $q\ge 16$. So there exists a line through p which does not meet S. By applying the same argument to all points not in S, we get that f is the product of affine factors.

Denote by Z the set of zeros of f. We have just proved that Z is the union of 6 lines in $F_q^2$. If the 6 lines are parallel then, f is the minimum weight codeword of $R_q(6,2)$ which is absurd. If 5 of these lines are parallel or the 6 lines intersect in one common point then, f is a second weight codeword of $R_q(6,2)$ which is absurd. If 4 of these lines are parallel, the following cases will happen:

• 1. If the two other lines are parallel or intersect in one point which is included in one of the parallel lines then, f is a third weight codeword of $R_q(6,2)$ which is absurd.

• 2. If the two other lines intersect in one point which is not included in any of the parallel lines then, we are in the first case of the proposition (see Fig. 1a).

If 3 of these lines are parallel, the following cases will happen:

• 1. If the three other lines are parallel then, we are in the second case of the proposition (see Fig. 1b).

• 2. Assume that two of three other lines are parallel. If the last line meets the five other lines in 3 points then, we are in the third case of the proposition (see Fig. 1c). Otherwise $\#Z\le 6q-10<6q-9$ which is absurd.

• 3. If the three other lines intersect in one common point which is included in one of the parallel lines then, we are in the fourth case of the proposition (see Fig. 1d).

• 4. If the three other lines intersect pairwise in three different points which are included in the parallel lines then, we are in the fifth case of the proposition (see Fig. 1e). Otherwise $\#Z\le 6q-10<6q-9$ which is absurd.

If 2 of these lines are parallel, the following cases will happen:

• 1. Assume the 6 lines can be partitioned to three pair of parallel lines. If the lines of each pair meet the four other lines in 5 points, we are in the 6th case of the proposition (see Fig. 1f). Otherwise $\#Z\le 6q-11<6q-9$ which is absurd.

• 2. Assume the 6 lines can be partitioned so that there are two pair of parallel lines. So if the two other lines meet the four other lines in 4 points, we are in the 7th case of the proposition (see Fig. 1g). Otherwise $\#Z\le 6q-10$ which is absurd.

• 3. Assume there is one pair of parallel lines. If the four other lines intersect in one point included in one of the parallel lines then f is a third weight codeword of $R_q(6,2)$ which is absurd. Otherwise $\#Z\le 6q-10$ that is a contradiction.

Fig. 1

Possible sets of zeros of fourth weight codewords in $R_q(6,2)$ for $q\ge 16$

If the 6 lines intersect pairwise, they can not intersect in one point. Then if 5 lines intersect in one point and the 6th line meets the other lines in different points of that point then we are in the last case of the proposition (see Fig. 1h). Otherwise $\#Z\le 6q-11$ which is absurd. $\square$

Theorem 8

For $q\ge 19$ and $7\le b< \frac{q}{3}+1$, the fourth weight of $R_q(b,2)$ is $W_4=(q-2)(q-b+2)+1$.

Furthermore, if $f\in R_q(b,2)$ is such that $|f|=(q-2)(q-b+2)+1$ then up to affine transformation for all $(x,y)\in F_q^2$ either

$$\begin{aligned} f(x,y)=\prod _{j=1}^{b-2} (a_1x+b_1y+c_j)(a_2x+b_2y)(a_3x+b_3y) \end{aligned}$$

with $(a_i,b_i)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c_j\in F_q^*$ for $j=1,\cdots , b-2$ or

$$\begin{aligned} f(x,y)=\prod _{j=1}^{b-1} (a_jx+b_jy)(a_bx+b_by+c) \end{aligned}$$

with $(a_i,b_i)\in F^2_q\setminus \{(0,0)\}$ are such that $a_ib_j-a_jb_i\ne 0$ for $i\ne j$ and $c\in F_q^*$.

Proof

The third weight in this case is $(q-2)(q-b+2)$. So if there exists $f\in R_q(b,2)$ such that $|f|=(q-2)(q-b+2)+1$, $W_4=(q-2)(q-b+2)+1$ and f is a fourth weight codeword of $R_q(b,2)$. Let $f\in R_q(b,2)$ such that $|f|=(q-2)(q-b+2)+1$. Denote by S its support.

Since $(q-2)(q-b+2)+1<q(q-b+1)$ and $q(q-b+1)$ is the minimum weight of $R_q(b-1,2)$, $deg(f)=b$. We prove first that f is the product of b affine factors. Let p be a point of $F_q^2$ which is not in S and l be a line in $F_q^2$ such that $p\in l$. Then either l does not meet S or l meets S in at least $q-b$ points. If any line through p meets S then

$$\begin{aligned} (q+1)(q-b)\le |f|=(q-2)(q-b+2)+1 \end{aligned}$$

which is absurd for $b< \frac{q}{3}+1$. So there exists a line through p which does not meet S. By applying the same argument to all points not in S, we get that f is the product of affine factors.

Denote by Z the set of zeros of f. We have just proved that Z is the union of b lines in $F_q^2$. For each line l which does not meet S, we denote by $n_l=\#(\{l'| \ l\cap l'=\emptyset , l'\cap S= \emptyset \}\cup \{l\})$ the number of lines parallel to l and not in S plus 1. By Lemma 2 since $n_l\le b$,

$$\begin{aligned} (q-b)q+n_l(b-n_l)\le (q-2)(q-b+2)+1 \end{aligned}$$

we get that $n_l\in \{1, 2, b-2, b-1, b\}$.

We say that those lines are in configuration $A_b$ if the b lines are parallel, in configuration $B_b$ if exactly $b-1$ lines are parallel, in configuration $C_b$ if the b lines meet in a point, in configuration $D_b$ if $b-2$ lines are parallel and the 2 other lines are also parallel, in configuration $E_b$ if $b-2$ lines are parallel and the 2 other lines intersect in one point included in one of the parallel lines, in configuration $F_b$ if $b-1$ lines intersect in one point and the bth line is parallel to one of the previous, in configuration $G_b$ if $b-2$ lines are parallel and the 2 other lines intersect in one point which is not included in any of the parallel lines, in configuration $H_b$ if $b-1$ lines intersect in one point and the bth line meets the other lines in different points of that point (see Fig. 2) and in configuration $I_b$ if we are in none of the previous configurations.

We prove by induction on b that Z the set of zeros of f is of type $G_b$ or $H_b$. Since the number of points in such set is $bq-2b+3$, we get the result.

Assume $b=7$. We have just proved that Z is the union of 7 lines in $F_q^2$. According to what we said $n_l\in \{1, 2, 5, 6, 7\}$. If the 7 lines are parallel (configuration $A_7$) then f is the minimum weight codeword of $R_q(7,2)$ which is absurd. If 6 of these lines are parallel (configuration $B_7$) or the 7 lines intersect in a point (configuration $C_7$) then, f is a second weight codeword of $R_q(7, 2)$ which is absurd. If 5 of these lines are parallel, then if the 2 other lines are parallel (configuration $D_7$) or intersect in one point included in one of the parallel lines (cofiguration $E_7$) then, f is the third weight codeword of $R_q(7,2)$ which is absurd. So the only possibility in this case is configuration $G_7$. If 2 of these lines are parallel then, if the 5 other lines intersect in one point included in one of parallel lines (configuration $F_7$) then, f is the third weight codeword of $R_q(7,2)$ which is absurd. Otherwise $\#Z\le 7q-12<7q-11$ that gives a contradiction. If all lines intersect pairwise then they cannot intersect in one point. Then if $b-1$ lines intersect in one point and the bth line meets the other lines in different point of that point then, we are in configuration $H_7$. Otherwise $\#Z\le 7q-14<7q-11$ which is absurd. This proves the result for $b = 7$.Let $7\le b < \frac{q}{3}+1$. Assume if $f\in R_q(b, 2)$ and $|f | =(q-2)(q-b+2)+1$ then its set of zeros is of type $G_b$ or $H_b$.

Fig. 2

Possible sets of zeros of fourth weight codewords in $R_q(7,2)$ for $q\ge 19$

Let $f\in R_q(b+1,2)$ such that $|f|=(q-2)(q-b+1)+1$. Denote by Z the set of zeros of f. Then as in the beginning of the proof, we get that Z is the union of $b+1$ lines in $F_q^2$ and as we said before for any line l in Z $n_l\in \{b+1, b, b-1, 2, 1\}$. Let us consider now a type $I_{b+1}$ configuration of $b+1$ lines. By considering the structure of the introduced configuration, we get that $n_l=1$ or 2. So if we extract from this configuration a subset with b lines we obtain one of the following situations:

• 1. Z is the union of a type $F_b$ configuration and a line l. Since Z is a configuration $I_{b+1}$, l cannot intersect the configuration $F_b$ in the point where $b-1$ lines of the configuration intersect. So, l intersects the configuration $F_b$ in at least $b-2$ points. We get that $\#Z\le bq-2b+4+q-b+2=(b+1)q-3b+6<(b+1)q-2b+1$.

• 2. Z is the union of a type $H_b$ configuration and a line l. Since Z is a configuration $I_{b+1}$, l cannot intersect the configuration $H_b$ in the point where $b-1$ lines of the configuration intersect. So, l intersect the configuration $H_b$ in at least $b-2$ points. We get that $\#Z\le bq-2b+4+q-b+2=(b+1)q-3b+6<(b+1)q-2b+1$.

• 3. Z is the union of a type $I_b$ configuration and a line l. Since for any line l $n_l=1$ or 2 so, l meets the configuration $I_b$ in at least 2 points. Then, by induction hypothesis, $\#Z < bq -2b + 3 + q -2 = bq + q -2b + 1$.

$\square$