# Linear system with many solutions from a finite set

Basically I am looking for a linear system with many solutions from a finite set.

Choose a finite set of rationals $S$ and fix positive integer $k$.

Let $A$ be a linear system with $n$ variables $x_i$ and $n-k$ linearly independent equations.

Is the number of solutions of $A$ with $x_i \in S$ bounded by an absolute constant?

This might be related to integer programming or some variant of SAT.

If the number of solutions is bounded what is lower bound in terms if $k$ and $|S|$?

• I’m confused. Do you want lower or upper bounds? The lower bound is $0$, the system does not have to have any solutions in $S^n$. The upper bound is $|S|^k$, which is easily proven by induction on $k$, and it is attained by the system $x_1=\dots=x_{n-k}=a$ where $a$ is a fixed element of $S$. – Emil Jeřábek Mar 2 '14 at 10:48
• @EmilJeřábek I am looking for constructions with many solutions. The system $x_1=\dots=x_{n-k}=a$ appears to have only one solution $(a \ldots a)$, not $|S|^k$ or am I missing something? – joro Mar 2 '14 at 10:58
• It has $|S|^k$ solutions, as you are free to choose any $x_{n-k+1},\dots,x_n\in S$. – Emil Jeřábek Mar 2 '14 at 13:16