Number of distinct coordinate solutions of linear equations over finite field?

131 Views Asked by At

Let $\mathbf{F}_q$ be a finite field of characteristic $p$. Let $a_1,\dots,a_n$ be $n$ elements of $\mathbf{F}_q$. Given $b\in\mathbf{F}_q$. Consider the following linear equation $$a_1x_1+\cdots+a_nx_n=b \tag{1}$$ How many solutions with distinct coordinates does $(1)$ have? That is, I want to count the cardinality of the set $$\{(x_1,\dots,x_n)\in\mathbf{F}_q^n:a_1x_1+\cdots+a_nx_n=b, x_i\ \text{distinct for}\ 1\leq i\leq n\}.$$ Let $N(a_1,\dots,a_n;b)$ denote the cardinality of this set.

For a special case $a_1=\dots=a_n=1$, I know the explicit formula of $N(a_1,\dots,a_n;b)$ (see this paper Theorem 1.5). In this case, if $p\nmid n$, then $$N(1,\dots,1;b)=\frac{1}{q}q^{\underline{n}}=\frac{1}{q}q(q-1)\cdots(q-n+1).$$ If $p\mid n$, then $$N(1,\dots,1;b)=\frac{1}{q}q^{\underline{n}}+(-1)^{n+n/p}\frac{v(b)}{q}n!\binom{q/p}{n/p},$$ where $v(b)=-1$ if $b\neq 0$, and $v(b)=q-1$ if $b=0$.

Do anyone know some other cases in which we can obtain an explicit formula or at least an asymptotic formula for $N(a_1,\dots,a_n;b)$?

1

There are 1 best solutions below

3
On

Taking advantage of the facts that adding a constant, or multiplying by a non-zero constant, maps a vector without repetitions to another such beast.

The first formula from your source still holds whenever $a_1+a_2+\cdots+a_n=A$ is non-zero. This is because the vector $(x_1,x_2,\ldots,x_n)$ contributes towards $N(a_1,a_2,\ldots,a_n;b)$ if and only if $(x_1+d,x_2+d,\ldots,x_n+d)$ contributes towards $N(a_1,a_2,\ldots,a_n;b+Ad)$. So if $A\neq0$ we can deduce that $N(a_1,a_2,\ldots,a_n;b)$ is independent of $b$.

Consequently whenever $A\neq0$ we have $N(a_1,a_2,\ldots,a_n;b)=(q-1)!/(q-n)!$ for all $b$.

If $A=0$ then it is trickier. We still see that the vector $(x_1,x_2,\ldots,x_n)$ contributes towards $N(a_1,a_2,\ldots,a_n;b)$ if and only if the vector $(x_1/b,x_2/b,\ldots,x_n/b)$ contributes towards $N(a_1,a_2,\ldots,a_n;1)$. But in this case the quantities $N(0)$ and $N(1)$ may be different. Anyway, we still have the equation $$ N(0)+(q-1)N(1)=\frac{q!}{(q-n)!}. $$ Alas, this won't give us enough information.