Can one construct a linear system of equations whose solution values are extremely close to each other?

70 Views Asked by At

Say we have a uniquely solvable system of linear equations $$ \mathbf{Ax=b} $$ where $\mathbf{A}$ and $\mathbf{b}$ have integer entries with a total of $n$ bits (the entries may be negative, in which case the negative sign can be ignored as far as the bit count is concerned).
It is possible to show (the details involve examining Cramer's rule) that the solution $\mathbf{x}$ to this system will have rational entries such that both numerator and denominator of each entry have at most $n$ bits.
Now I'm asking myself if it is also true that the distance between unequal entries of $\mathbf{x}$ is bounded below by $1/2^n$ which is a lower bound on the smallest number one can write with numerators and denominators of at most $n$ bits each.
A path to a counterexample might be provided by trying to construct a system which has the solution $$ \begin{bmatrix} \frac{1}{2^n-1}\\ \frac{1}{2^n-2} \end{bmatrix}\,. $$ Both denominators only require $n$ bits, so it is conceivable that such a system might exist. But the distance between them is $$ \frac{1}{2^n-2}-\frac{1}{2^n-1}=\frac{1}{(2^n-2)(2^n-1)} $$ which requires roughly $2n$ bits in the denominator. However, constructing such a linear system of equations, having only integer entries with a total of $n$ bits, has proven a little tricky.
Does anybody have an idea how to proceed here, perhaps via computer search? Or is it perhaps impossible to construct such a system?

1

There are 1 best solutions below

0
On BEST ANSWER

To answer my own question: No it isn't possible to construct such a system of equations. Upon review of Cramer's rule each entry of $\mathbf{x}$ can be written to have the same denominator $\det A$, which is bounded above by $2^n$. Hence the difference between two entries of $\mathbf{x}$ is a multiple of $1/\det A$ which is bounded below by $1/2^n$.