# Number of solutions of a polynomial over finite fields

Consider in $$\mathbb{F}_q[x_1,\dots,x_n]$$, where $$r$$ is a positive integer dividing $$n$$, the polynomial $$f(x_1,\dots,x_n)=x_1x_2\dots x_r+x_{r+1}x_{r+2}\dots x_{2r}+\dots+x_{n-r+1}x_{n-r+2}x_{n}.$$ What is the cardinality of the set of the solutions to $$f(x_1,\dots,x_n)=0$$?

Bonus question:

and if $$n\neq 0\mod{r}$$, so that the last monomial of $$f$$ has less than $$r$$ variables multiplied?

Edit: $$f(x_1,\dots,x_n)$$ is the product of the first $$r$$ variables plus the product of the second r variables and so on (so it is of degree one in each variable, with total degree $$r$$).

It is clear that imposing a variable in each monomial to be zero then the set of the solutions has at least size around $$q^{(r-1)n/r}r-n/r+1$$, but my question arises from the fact that I don't know what is the actual size of this set (it is not difficult to find some solutions having $$x_i\ne0$$, for all $$i\in\{1,\dots,n\}$$).

• Anyway, I would begin unravelling this by trying to solve for $x_n$ in terms of the others (assuming that my guess of $x_n$ appearing in a single term only is correct). When can you solve for it? What if you cannot? – Jyrki Lahtonen Jun 12 at 10:00
• This can become an interesting question. I'm sure you can improve it, either with pointers from our guide for new askers or possibly getting something going using my comments as hints. Mind you, such comments may easily misfire (I'm prepared for that as I didn't think this through as some clarifications are needed) , but I wanted to share my first thoughts in the hope that you can make some progresss yourself! – Jyrki Lahtonen Jun 12 at 10:03
• Thank you for the comments, I edited explaining better the problem. Unfortunately I don't have a general guess on the behaviour of this number. – Hideus Jun 12 at 13:48
• (cont'd) Consider then the case with $n=kr$. Let $N(k)$ be the number of solutions. If the first $k-1$ products of $r$ variables sum up to zero ($N(k-1)$ ways), then the last product must also be zero ($q^r-(q-1)^r$ ways). If the first $k-1$ don't sum up to zero ($q^{(k-1)r}-N(k-1)$ ways), then the last product must have a fixed non-zero value ($(q-1)^{r-1}$ ways). So we have a recursive formula: $$N(k)=N(k-1)(q^r-(q-1)^{r-1})+(q^{(k-1)r}-N(k-1))(q-1)^{r-1}.$$ I don't know if it is easy to show what this leads to. A different approach may work better. – Jyrki Lahtonen Jun 12 at 18:42
• Yes, you are right! I think that there's a typo in your formula and the actual number is $$N(k)=N(k-1)(q^r-(q-1)^r)+(q^{(k-1)r}-N(k-1))(q-1)^{r-1}$$ – Hideus Jun 13 at 8:35

My previous attempt having failed due to dependence between the terms (see edit history if you want to laugh and point), I think the best approach is to see this as a Markov process over prefixes of the sum, with two states: zero and non-zero.

Let $$n = rs$$.

There are $$q^r$$ possibilities for each term, of which $$(q-1)^r$$ are non-zero, distributed evenly over the $$q-1$$ non-zero field elements. Therefore the number you want is $$\begin{bmatrix}1 & 0 \end{bmatrix} \begin{bmatrix}q^r - (q-1)^r & (q-1)^{r-1} \\ (q-1)^r & q^r - (q-1)^{r-1}\end{bmatrix}^s \begin{bmatrix}1 \\ 0\end{bmatrix}$$ The transition matrix diagonalises (I used a CAS) as $$\begin{bmatrix}\frac{1}{q-1} & -1 \\ 1 & 1\end{bmatrix} \begin{bmatrix}q^r & 0 \\ 0 & q^r - q(q-1)^{r-1}\end{bmatrix} \begin{bmatrix}\frac{q-1}{q} & \frac{q-1}{q} \\ \frac{1-q}{q} & \frac{1}{q} \end{bmatrix}$$ so we get $$\begin{bmatrix}1 & 0 \end{bmatrix} \begin{bmatrix}\frac{1}{q-1} & -1 \\ 1 & 1\end{bmatrix} \begin{bmatrix}q^r & 0 \\ 0 & q^r - q(q-1)^{r-1}\end{bmatrix}^s \begin{bmatrix}\frac{q-1}{q} & \frac{q-1}{q} \\ \frac{1-q}{q} & \frac{1}{q} \end{bmatrix} \begin{bmatrix}1 \\ 0\end{bmatrix} \\ = \begin{bmatrix}\frac{1}{q-1} & -1 \end{bmatrix} \begin{bmatrix}q^n & 0 \\ 0 & [q^r - q(q-1)^{r-1}]^s\end{bmatrix} \begin{bmatrix}\frac{q-1}{q} \\ \frac{1-q}{q} \end{bmatrix} \\ = q^{n-1} + q^{s-1}(q-1)[q^{r-1} - (q-1)^{r-1}]^s$$

For the bonus question, let $$n = rs + t$$ with $$0 < t < r$$. Then we take the same transition matrix, substituting $$t$$ for $$r$$, and apply to the previous result to get $$\begin{bmatrix}1 & 0\end{bmatrix} \begin{bmatrix}q^t - (q-1)^t & (q-1)^{t-1} \\ (q-1)^t & q^t - (q-1)^{t-1}\end{bmatrix} \begin{bmatrix}q^{rs-1} + q^{s-1}(q-1)[q^{r-1} - (q-1)^{r-1}]^s \\ q^{rs} - q^{rs-1} - q^{s-1}(q-1)[q^{r-1} - (q-1)^{r-1}]^s\end{bmatrix} \\ = [q^t - (q-1)^t][q^{rs-1} + q^{s-1}(q-1)[q^{r-1} - (q-1)^{r-1}]^s] + [(q-1)^{t-1}][q^{rs} - q^{rs-1} - q^{s-1}(q-1)[q^{r-1} - (q-1)^{r-1}]^s] \\ = q^{rs} (q-1)^{t-1} + [q^t - q(q-1)^{t-1}][q^{rs-1} + q^{s-1}(q-1)[q^{r-1} - (q-1)^{r-1}]^s] \\ = q^{n-1} + q^s(q-1)[q^{t-1} - (q-1)^{t-1}][q^{r-1} - (q-1)^{r-1}]^s$$

In fact, there's enough structure there to conjecture and prove that for a general composition of $$n$$, $$\lambda_1 + \cdots + \lambda_k = n$$, the number of solutions of $$x_1x_2\cdots x_{\lambda_1}+x_{\lambda_1+1}x_{\lambda_1+2}\cdots x_{\lambda_1 + \lambda_2}+\cdots = 0$$ is given by $$q^{n-1} + q^{k-1}(q-1)\prod_{i=1}^k [q^{\lambda_i-1} - (q-1)^{\lambda_i-1}]$$

By induction on $$k$$.

If $$k=1$$ we have the original problem with $$r=\lambda_1, s=k=1$$.

If it holds for $$k$$ then for $$k+1$$ we have $$\begin{bmatrix}1 & 0\end{bmatrix} \begin{bmatrix}q^{\lambda_{k+1}} - (q-1)^{\lambda_{k+1}} & (q-1)^{\lambda_{k+1}-1} \\ (q-1)^{\lambda_{k+1}} & q^{\lambda_{k+1}} - (q-1)^{\lambda_{k+1}-1}\end{bmatrix} \begin{bmatrix}q^{n - \lambda_{k+1}-1} + q^{k-1}(q-1)\prod_{i=1}^k [q^{\lambda_i-1} - (q-1)^{\lambda_i-1}] \\ q^{n - \lambda_{k+1}} - q^{n - \lambda_{k+1}-1} - q^{k-1}(q-1)\prod_{i=1}^k [q^{\lambda_i-1} - (q-1)^{\lambda_i-1}]\end{bmatrix} \\ = [q^{\lambda_{k+1}} - (q-1)^{\lambda_{k+1}}][q^{n - \lambda_{k+1}-1} + q^{k-1}(q-1)\prod_{i=1}^k [q^{\lambda_i-1} - (q-1)^{\lambda_i-1}]] + [(q-1)^{\lambda_{k+1}-1}][q^{n - \lambda_{k+1}} - q^{n - \lambda_{k+1}-1} - q^{k-1}(q-1)\prod_{i=1}^k [q^{\lambda_i-1} - (q-1)^{\lambda_i-1}]] \\ = q^{n-1} + q^k (q-1) \prod_{i=1}^{k+1} [q^{\lambda_i-1} - (q-1)^{\lambda_i-1}]$$ as desired.

• "If we take the final non-zero term, its value is fixed by the previous ones, which are free and independent" they aren't independent since they can't sum to zero. – mercio Jun 13 at 15:33
• Good point. Back to the drawing board... – Peter Taylor Jun 13 at 16:02
• I've completely rewritten the answer. – Peter Taylor Jun 13 at 19:04