Bernd Borchert

Few Gates - Many Zeros

An arithmetical circuit is built by +, - and * gates, integer constants and possibly a variable X. A variable-less arithmetical circuit represents an integer: the value at its top gate. An arithmetical circuit c(X) with variable X respresents a polynomial q(X), i.e. a function mapping integers to integers. A zero of the circuit c(X) is a zero of the polynomial q(X), i.e. an integer a such that q(a)=0. As an example, the arithmetical circuit on the right has 16 different zeros (what can be checked by evaluation): 0, -4, -7, -12, -118, -133, -145, -178, -189, -222, -234, -249, -355, -360, -363, -367. The circuit was found via computer search. It is unknown whether a level-5 circuit of that kind exists, i.e. an arithmetical circuit with 10 gates having 32 different zeros. Even if some 10-gates-32-zeros circuit could be found, at some point a final border of this construction should be expected to exist - because of a result of Lipton 1994: a small arithmetical circuit p(X) with a large number of different zeros would allow a fast randomized integer factorization algorithm.