### 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 informatik.uni-tuebingen.de

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

and

Klaus Reinhardt
WSI, Universität Tübingen
Sand 13
72076 Tübingen, Germany
reinhard AT informatik.uni-tuebingen.de

March 10, 2013

#### Abstract

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$.

• The article: PDF (305 KB)
• Source material: ZIP (113 KB)
• BibTeX entry for this article (263 bytes)

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

Article 1 Article 3
Volume 2013 Published articles