0
$\begingroup$

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.

  • 1
    It's *very* bad style to post this question without linking to [your earlier question](http://math.stackexchange.com/questions/77775/how-to-solve-these-inequalities) 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?2011-11-03
  • 0
    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.2011-11-03
  • 0
    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.2011-11-03
  • 0
    It's okay. Thanks for your advice. I'll review them carefully.2011-11-03
  • 1
    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*.2011-11-03
  • 0
    It is sufficient that for some $j$ the $j$-th coordinate is nonzero in all the vectors $\mathbf{a}_i$, but I see that you have added the condition that the $\mathbf{a}_i$ are sparse while responding to Joriki's answer. How about editing the original question to say that the $\mathbf{a}_i$ are sparse right up front?2011-11-03
  • 0
    @ChrisEagle I checked the definitions of [inequality](http://en.wikipedia.org/wiki/Inequality_(mathematics)) and [inequation](http://en.wikipedia.org/wiki/Inequation). You are right.2011-11-03
  • 0
    @DilipSarwate Thanks for your advice. I've already updated the question.2011-11-03

3 Answers 3

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.

  • 0
    In the special case $K this is efficiently solvable with a randomized algorithm due to the Schwartz-Zippel lemma2012-12-05
1

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). 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.

  • 0
    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$.2011-11-03
  • 0
    If $K>q$ and $\mathbf{a_i}$ are given, is it possible to determine whether a solution exists?2011-11-03
  • 0
    @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.2011-11-03
0

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.