Let n binary numbers of length n be given. The Boolean function ”Multiple Product” MP n asks for (some binary representation of) the value of their product. It has been shown in [SR],[SBKH] that this function can be computed in polynomial-size threshold circuits of depth 4. For a lot of other arithmetic functions, circuits of depth 3 are known. They are mostly based on the fact that the value of the considered function modulo some prime numbers p can be computed easily in threshold circuits.
In this paper, we show that the difficulty in constructing smaller depth circuits for MP n stems from the fact that for all numbers m which are divisible by a prime larger than 3, computing MP n modulo m already cannot be computed in depth 2 and polynomial size. This result still holds if we allow m to grow exponentially in n (m < 2cn, for some constant c). This improves upon recent results in [K1].
We also investigate moduli of the form 2i3j. In particular, we show that there are depth-2 polynomial-size threshold circuits for computing MP n modulo m if m ε {2,4,8}, and that no such circuits exist if m is divisible by 9 or 16.