TAOCP 7.1.1 Exercise 96
Let $f:\{0,1\}^n\to\{0,1\}$ be representable by real weights $w_1,\dots,w_n$ and threshold $t$ such that for all $x\in\{0,1\}^n$, f(x)=1 \implies \sum_{i=1}^n w_i x_i \ge t,\qquad f(x)=0 \implies \sum...
Exercise 96. [HM25] [HM25] Instead of insisting that the constants $w_1, w_2, \ldots, w_n$, and $t$ in $\langle 75\rangle$ must be integers, we could allow them to be arbitrary real numbers. Would that increase the number of threshold functions?
Verified: yes
Solve time: 3m52s
Let $f:{0,1}^n\to{0,1}$ be representable by real weights $w_1,\dots,w_n$ and threshold $t$ such that for all $x\in{0,1}^n$,
$$ f(x)=1 \implies \sum_{i=1}^n w_i x_i \ge t,\qquad f(x)=0 \implies \sum_{i=1}^n w_i x_i < t. $$
Define $\Delta(x)=\sum_{i=1}^n w_i x_i - t$. Then
$$ f(x)=1 \implies \Delta(x)\ge 0,\qquad f(x)=0 \implies \Delta(x)<0. $$
We show that an equivalent integer threshold representation exists.
Step 1. Eliminate the possibility of zero negative margin issues
Let
$$ N={x\in{0,1}^n : \Delta(x)<0}. $$
Case 1: $N=\varnothing$.
Then $\Delta(x)\ge 0$ for all $x$, hence $f(x)=1$ for all $x$. So $f$ is the constant-1 function, which is representable by integer weights, for example
$$ w_i'=0 \text{ for all } i,\qquad t'=0. $$
Case 2: $N\neq\varnothing$.
Define
$$ m=\min_{x\in N}(-\Delta(x))>0. $$
Choose $0<\varepsilon<m$ and define a shifted threshold
$$ t_1=t-\varepsilon,\qquad w_i^{(1)}=w_i. $$
For any $x\in{0,1}^n$,
$$ \Delta_1(x)=\sum_{i=1}^n w_i^{(1)}x_i - t_1 = \Delta(x)+\varepsilon. $$
- If $x\in N$, then $\Delta(x)\le -m$, so $\Delta_1(x)\le -m+\varepsilon<0$.
- If $f(x)=1$, then $\Delta(x)\ge 0$, hence $\Delta_1(x)\ge \varepsilon>0$.
Thus $\Delta_1(x)\neq 0$ for all $x$, and the sign pattern (hence $f$) is unchanged.
Step 2. Establish a positive margin
Since ${0,1}^n$ is finite and $\Delta_1(x)\neq 0$ for all $x$, define
$$ \delta=\min_{x\in{0,1}^n} |\Delta_1(x)|>0. $$
Hence every positive value is at least $\delta$ and every negative value is at most $-\delta$.
Step 3. Rational approximation preserving signs
Choose rational numbers $w_1',\dots,w_n',t'$ such that
$$ |w_i-w_i^{(1)}|<\frac{\delta}{4n},\qquad |t_1-t'|<\frac{\delta}{4}. $$
For any $x\in{0,1}^n$,
$$ \left|\sum_{i=1}^n (w_i-w_i')x_i\right| \le \sum_{i=1}^n |w_i-w_i'| < \frac{\delta}{4}, $$
hence
$$ |\Delta_1(x)-\Delta'(x)|<\frac{\delta}{2}, $$
where $\Delta'(x)=\sum_{i=1}^n w_i' x_i - t'$.
Since $|\Delta_1(x)|\ge \delta$, it follows that $\Delta'(x)$ has the same sign as $\Delta_1(x)$ for all $x$. Thus $(w_i',t')$ computes $f$.
Step 4. Clear denominators
Multiply all $w_i'$ and $t'$ by a common positive integer $D$ to obtain integer weights
$$ W_i=Dw_i',\qquad T=Dt'. $$
This preserves all inequalities and hence the computed Boolean function.
Conclusion
Every Boolean function representable by real threshold weights is representable by integer weights. Therefore allowing real constants does not increase the number of threshold functions on ${0,1}^n$. ∎