Assumption on weights in threshold circuits

Question

A threshold gate implementing a linear threshold function on $n$ boolean inputs $x_1, x_2 \ldots, x_n$ is given by the equation: $w_1 x_1 + w_2 x_2 + \ldots, w_n x_n \ge t$ where $w_1, \ldots, w_n, t \in \mathbb{R}$. The $w_i$'s are called the weights of the threshold function and $t$ is called the threshold, and naturally, the gate fires a $1$ on an input $x$ if the weighted sum given by the equation above exceeds $t$.

Now, almost everywhere in the literature on threshold circuits, I encounter this fact (which I am guessing, is folklore since I couldn't find a proof anywhere): The $w_i$'s in the linear equation above can be made integers (on $n \log{n}$ bits), and a threshold circuit made up of these gates will still compute whatever was possible with real weights. I have given this some thought, and I think it must be a simple trick, but I have failed to obtain a proof of this fact. Can somebody help or provide me with a reference? (the only reference I could find was a text by Muroga, which I couldn't procure)

Answer 1

Given $w_1,\ldots,w_n,t$, let $X$ be the set of assignments such that $\sum_i w_i x_i \geq t$, and consider the linear program with variables $z_1,\ldots,z_n$ and the $2^n$ constraints $$ \begin{align*} \sum_i z_i x_i \geq +1 & (x_1,\ldots,x_n) \in X \\ \sum_i z_i x_i \leq -1 & (x_1,\ldots,x_n) \notin X \end{align*} $$ This linear program (with a constant objective function) is feasible (since $z_i = w_i/t$ is a solution), and so has a solution $z_1,\ldots,z_n$ which is a vertex. As such, it is the solution of a system of $n$ equations of the form $$ \sum_i z_i x_i = \pm 1. $$ Cramer's rule gives each $z_i$ as a ratio of two $n \times n$ determinants of matrices of $0,\pm 1$ entries; in fact the denominator is the same. Each numerator $N_i$ and the common denominator $D$ is at most $n!$ in magnitude, so multiplying everything by $D$, we get an integral solution $N_1,\ldots,N_n,D$, where all the quantities are at most $n! \leq n^n = 2^{n\log n}$ in magnitude.