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

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.

© 2013 Bernd Borchert, Pierre McKenzie and Klaus Reinhardt
Licensed under a Creative Commons Attribution License

Article 1

Article 3

Volume 2013

Published articles