# Solve inequations over a finite field

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.

-
It's very bad style to post this question without linking to your earlier question of which it's a special case. Are you not aware that this will cause lots of people to duplicate effort that's already been spent on answering the other question? – joriki Nov 3 '11 at 8:40
I am very sorry for that. This new question is not directly obtained from my previous question. So, I even didn't notice this is actually a special case of my previous question. Thanks for warning me. – Leon Nov 3 '11 at 8:52
In that case, I apologize for the italics, I've removed my downvote, and I suggest that you review the basics of matrix products and dot products again before you start applying them to finite fields. – joriki Nov 3 '11 at 8:58
It's okay. Thanks for your advice. I'll review them carefully. – Leon Nov 3 '11 at 9:50
I think it's usual in English to reserve "inequality" for expressions like $a>b$ or $a \geq b$. Expressions like $a \neq b$ are inequations. – Chris Eagle Nov 3 '11 at 11:38

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.

-
In the special case $K<q$ this is efficiently solvable with a randomized algorithm due to the Schwartz-Zippel lemma – Tim Seguine Dec 5 '12 at 18:28

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.

-
In general the bound $K\le q$ is the best possible in the following sense. If $$F_q=\{x_1,x_2,\ldots,x_q\},$$ then the choices $a_i=(1,0,0,\ldots,x_i)$, $1\le i\le q$, and $a_{q+1}=(0,0,\ldots,0,1)$ do not admit any solutions to the system of inequations. Therefore we cannot guarantee that a solution exists, if $K=q+1$. – Jyrki Lahtonen Nov 3 '11 at 15:06
If $K>q$ and $\mathbf{a_i}$ are given, is it possible to determine whether a solution exists? – Leon Nov 3 '11 at 16:13
@Leon: I don't see anything more efficient than joriki's suggestion. BTW, with my example of $q+1$ unsolvable inequations the polynomial he describes is $x_1x_N(x_1^{q-1}-x_N^{q-1})$, which clearly vanishes everywhere. – Jyrki Lahtonen Nov 3 '11 at 20:34

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.

-