Solve inequations over a finite field

Question

The following is a special case of my earlier question which is still not solved.

Suppose both $\mathbf{a_i}$ and $\mathbf{v}$ are $1\times N$ vectors over a finite field $\mathbb{F_q}$, where $i\in \{1,2,\ldots\,K\}$. $\mathbf{a_i}$ are very sparse, i.e. there are only two or three non-zero entries in each $\mathbf{a_i}$. Now, I have $K$ inequations $\mathbf{a_i}\cdot\mathbf{v}\neq 0$.

What is the necessary and sufficient condition that there exists at one such $\mathbf{v}$ that make the $K$ inequations hold simultaneously? Thanks.

Answer 1

There is a solution to this system of inequalities if and only if the product $\prod_i\mathbf a_i\cdot\mathbf v$ is not equivalent to the zero polynomial. This polynomial can have up to $|\mathbb F_q|^N$ different coefficients, so computing it will in general not be more efficient than testing every possible value of $\mathbf v$, but if the $\mathbf a_i$ have few components, or you can transform to a basis in which they have few components, it may be.

Answer 2

Since very little is known about the $\mathbf{a}_i$ except that they are sparse, it is not clear that a necessary and sufficient condition can be specified at all.

If the $\mathbf{a}_i$ are very sparse, say with exactly two nonzero entries each, and if the nonzero entries are equally likely to be chosen independently with probability $(q-1)^{-1}$ from the nonzero elements of $\mathbb{F}_q$, then the probability that $\mathbf{v} = (1, 1, \ldots, 1)$ satisfies the $K$ inequations is $(1 - (q-1)^{-1})^K$ which might be good enough if $q$ is large and $K$ is small.

Answer 3

A counting argument gives the following sufficient condition. I write it up as an answer, because I first stated it incorrectly in a comment (I had confused the roles of $N$ and $K$).

Obviously we must assume that $a_i\neq(0,0,\ldots,0)$ for all $i$. The inequation $a_i\cdot v\neq0$ rules out as potential solutions the points $v$ of the hyperplane determined by the equation $a_i\cdot v=0$. This hyperplane is actually a subspace of dimension $N-1$, so it has $q^{N-1}$ points. The point $v=(0,0,\ldots,0)$ is in all those subspaces, so the union of $K$ such subspaces has at most $1+K\cdot (q^{N-1}-1)$ points. Thus something will be left over, if $1+K\cdot (q^{N-1}-1)<q^N$. This holds whenever $K\le q$, so we get a sufficient condition for the existence of a solution: 1) $a_i\neq(0,0,\ldots,0)$ for all $i$, and 2) $K\le q$. This condition is by no means necessary.