Impossibility results for weak threshold networks

It is shown that a weak threshold network (in particular, threshold network) of width w and depth d cannot be constructed from balancers of width p₀, p₁, . . . , p_m-1, if w does not divide Pd, where P is the least common multiple of p₀, p₁, . . . , p_m-1. This holds regardless of the size of the network, as long as it is finite, and it implies a lower bound of log_p w on its depth. More strongly, a lower bound of log_pmax w is shown on the length of every path from an input wire to any output wire that exhibits the threshold property, where p_max is the maximum among p₀, p₁, . . . , P_m-1.