# Greater-Than operator using an Arithmetic Circuit

How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it?

Where $x$ is the input to the circuit and $C$ is a known constant.

• You can’t. Arithmetic circuits only compute polynomials, and the set of positive elements is not the zero set of a polynomial in any ordered ring. Aug 31 '14 at 19:46
• Well, if the ordered ring is an integral domain, then a nonconstant polynomial can only have finitely many zeros, whereas there are infinitely many positive elements. If it’s not a domain, the argument gets a bit more messy, but it still works out. Aug 31 '14 at 20:26
• What do you mean by $x>C$ then? A finite field can’t be ordered. Which ordered structure do you take $x$ and $C$ from, and how do you represent them by elements of the finite field? Aug 31 '14 at 20:45
• Bush: I suggest you try to reformulate the question to actually express what you are thinking of. Sep 1 '14 at 9:34
• You can use interpolation to write any function on a finite field as an arithmetic circuit. Do you have other requirements? Sep 1 '14 at 16:36