Distinct coordinate solutions of linear equations over finite fields

Abstract

Let ${\mathbb{F}}_q$ be the finite field of $q$ elements and $a_1,a_2,\dots ,a_k,b\in {\mathbb{F}}_q$. We investigate $N_{{\mathbb{F}}_q}(a_1,a_2,\dots ,a_k;b)$, the number of ordered solutions $(x_1,x_2,\dots ,x_k)\in {\mathbb{F}}_q^k$ of the linear equation $$a_1{x}_1+a_2{x}_2+\cdots +a_k{x}_k=b$$ with all $x_i$ distinct. We obtain an explicit formula for $N_{{\mathbb{F}}_q}(a_1,a_2,\dots ,a_k;b)$ involving combinatorial numbers depending on $a_i$'s. In particular, we obtain closed formulas for two special cases. One is that $a_i,1\le i\le k$ take at most three distinct values and the other is that ${\sum }_{i=1}^k{a}_i=0$ and ${\sum }_{i\in I}{a}_i\ne 0$ for any $I⊊[k]$. The same technique works when ${\mathbb{F}}_q$ is replaced by ${\mathbb{Z}}_n$, the ring of integers modulo $n$. In particular, we give a new proof for the main result given by Bibak, Kapron and Srinivasan, which generalizes a theorem of Schönemann via a graph theoretic method.

12 pages, no figures. This is the revised version, incorporating referee comments