Chicago Journal of Theoretical Computer Science

Volume 2013

Article 2

Published by the Department of Computer Science, The University of Chicago.

Few Product Gates but Many Zeroes

Bernd Borchert
WSI, Universität Tübingen
Sand 13
72076 Tübingen, Germany
borchert AT

Pierre McKenzie
DIRO, Univ de Montréal
C. P. Centre-Ville
Montréal (Qc) H3C 3JT
mckenzie AT


Klaus Reinhardt
WSI, Universität Tübingen
Sand 13
72076 Tübingen, Germany
reinhard AT

March 10, 2013


A d-gem is a $\{+,-,\times\}$-circuit having very few $\times$-gates and computing from $\{x\}\cup Z$ a univariate polynomial of degree $d$ having $d$ distinct integer roots. We introduce $d$-gems because they offer the remote possibility of being helpful for factoring integers, and because their existence for infinitely many $d$ would disprove a form of the Blum-Cucker-Shub-Smale conjecture (strengthened to allow arbitrary constants). A natural step towards a better understanding of the BCSS conjecture thus would be to construct $d$-gems or to rule out their existence. Ruling out $d$-gems for large $d$ is currently totally out of reach. Here the best we can do towards that goal is to prove that skew $2^n$-gems if they exist require $n$ $\{+,-\}$-gates and that skew $2^n$-gems or any $n\geq5$ would provide new solutions to the Prouhet-Tarry-Escott problem in number theory (skew meaning the further restriction that each $\{+,-\}$-gate merely adds an integer to a polynomial). In the opposite direction, here we do manage to construct skew $d$-gems for several values of $d$ up to $55$.

Submitted June 6, 2010, revised January 20, 2012, and in final form March 9, 2013, published March 10, 2013.

DOI: 10.4086/cjtcs.2013.002

[] Article 1 [] Article 3
[back] Volume 2013 [back] Published articles
[CJCTS home]