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|$?

  • 1
    $\begingroup$ 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$. $\endgroup$ – Emil Jeřábek Mar 2 '14 at 10:48
  • $\begingroup$ @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? $\endgroup$ – joro Mar 2 '14 at 10:58
  • $\begingroup$ It has $|S|^k$ solutions, as you are free to choose any $x_{n-k+1},\dots,x_n\in S$. $\endgroup$ – Emil Jeřábek Mar 2 '14 at 13:16

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.