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

<p>Where $x$ is the input to the circuit and $C$ is a known constant.</p>

CC BY-SA 3.0
2014-08-31T19:46:36.973Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-08-31T19:48:56.383Z
Can you explain with a bit more details please?
Bush
CC BY-SA 3.0
2014-08-31T20:00:39.817Z
Which part of that is unclear to you?
Emil Jeřábek
CC BY-SA 3.0
2014-08-31T20:12:52.507Z
"the set of positive elements is not the zero set of a polynomial in any ordered ring"
Bush
CC BY-SA 3.0
2014-08-31T20:26:03.263Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-08-31T20:41:33.047Z
I'm talking about a finite field, does it change the answer?
Bush
CC BY-SA 3.0
2014-08-31T20:45:28.537Z
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?
Emil Jeřábek
CC BY-SA 3.0
2014-08-31T20:51:29.357Z
Well, I thought that I can compare between elements in the finite field by just looking at them as elements with the same value which are in the infinite (ordered) field. In particular I thought of the field of integers modulo $N$.
Bush
CC BY-SA 3.0
2014-09-01T09:34:25.197Z
Bush: I suggest you try to reformulate the question to actually express what you are thinking of.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2014-09-01T16:36:36.087Z
You can use interpolation to write any function on a finite field as an arithmetic circuit. Do you have other requirements?
Sasho Nikolov
<ds.algorithms><arithmetic-circuits><circuits>
Greater-Than operator using an Arithmetic Circuit
Bush
# Greater-Than operator using an Arithmetic Circuit

(Asked by: username_0 on 2014-08-31)

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.

**Tags:** ds.algorithms, arithmetic-circuits, circuits
> **Comments:**
> **username_1**: 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.  
> **username_0**: Can you explain with a bit more details please?  
> **username_1**: Which part of that is unclear to you?  
> **username_0**: "the set of positive elements is not the zero set of a polynomial in any ordered ring"  
> **username_1**: 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.  
> **username_0**: I'm talking about a finite field, does it change the answer?  
> **username_1**: 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?  
> **username_0**: Well, I thought that I can compare between elements in the finite field by just looking at them as elements with the same value which are in the infinite (ordered) field. In particular I thought of the field of integers modulo $N$.  
> **username_2**: Bush: I suggest you try to reformulate the question to actually express what you are thinking of.  
> **username_3**: You can use interpolation to write any function on a finite field as an arithmetic circuit. Do you have other requirements?  

---

## 0 answers

