# Taking mod $2$ with LTF gates

Consider the function : $\mathbb{Z}^{\geq 0} \rightarrow \{0,1\}$ given as $n \mapsto n \bmod 2$. Does this have an easy implementation using Linear Threshold Function gates?

I do not mean that the input is the infinite set of positive integers. Think of the input as coming on a single wire carrying a non-negative integer.

This is impossible. For large enough $n$, all your threshold gates will be "saturated", that is, they will have the same output on all large enough $n$, and in particular won't be able to distinguish between $n$ and $n+1$.
• Thanks! So the depth 2 representation of PARITY by depth 2 LTF cannot be compressed in any sense. (In terms of size its anyway optimal as was shown in a recent STOC paper that PARITY is $\Theta(\sqrt{n})$ for depth 2 $LTF$) – gradstudent Oct 19 '17 at 15:24