# Assumption on weights in threshold circuits

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)

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.
• It seems to me that with this linear program you are risking that the vertex solution does not give the same function as the original one: namely, the two sets of equations have the same right-hand side, and hence you risk that the linear form given by the vertex solution have the same value on inputs both from $X$ and not from $X$. To fix this the right-hand sides should be different. The normal proof I know uses $n+1$ variables (that is, also a variable for $t$) and uses the right-hand sides $-1$ and $1$. Oct 30, 2012 at 14:47
• @Kristoffer You're right, it was a typo. I meant $\geq +1$ and $\leq -1$, as you write. Oct 30, 2012 at 14:56
• @YuvalFilmus Is there a typo in how you are counting the number of equations to solve? It seems like you have $2^n$ simultaneous linear equations to solve. (one for each $x$) And hence all solutions are at most $(2^n)!$ in magnitude because the Cramer's rule matrices are $2^n$ dimensional. Am I missing something? Oct 30, 2017 at 23:13
• Oh! Wait! Are you saying that one can choose any $n$ of the $x$s arbitarily and solving for this subsystem is enough to give you a vertex and hence you are done? Oct 30, 2017 at 23:16
• A vertex is the solution of $n$ linearly independent equations. Oct 31, 2017 at 13:12