# It is possible to implement a *greater than* function using only addition, substractions and multiplications?

All values are from a finite field $Z_t$. I want to write a function greater than like this

$GT(x,y) = \begin{cases} 1, & \text{if } x > y, \\ 0, & \text{otherwise}. \end{cases}$

using only additions, multiplications, subtractions and preferably not divisions.

The equality function

$EQU(x,y) = \begin{cases} 1, & \text{if } x == y, \\ 0, & \text{otherwise}. \end{cases}$

can be computed like this

$EQU(x,y) = 1 - (x-y)^p$, where p is the Euler totient function $p=phi(t)=t-1$ because $t$ is prime.

Can a greater than function be written in a similar way ?

The greater than function would be used for a homomorphic encryption application to find the maximum integer value from a vector of encrypted integers.

• Your last equation doesn't work. ​ (Just try x and y that differ by more than 1.) ​ ​ ​ ​ – user12859 Mar 19 '16 at 11:10
• There is no reasonable greater on finite fields. – k.stm Mar 19 '16 at 11:25
• @RickyDemer It does work, if one replaces $t$ by $t-1$: In a finite field $ℤ_t$, for all $α ∈ ℤ_t$ with $α ≠ 0$, $α^{t-1} = 1$. – k.stm Mar 19 '16 at 11:27
• I want to use the greater than function for a homomorphic comparison between messages from some space Z_t, where t is greater than 2. In section 3 of this paper acad.ro/sectii2002/proceedings/doc2015-3s/08-Togan.pdf is given the polynomial for greater than function for binary values. I want the same functionality but for integer values, if it is possible to be computed. – user2991856 Mar 19 '16 at 13:44
• What does this have to do with CS? Why isn't this on MathOverflow or Mathematics? – cat Mar 19 '16 at 16:27

Every function on a finite field $GF(q)$ can be represented unique as a polynomial of individual degree at most $q-1$.
Indeed, as you mention, $1-x^{q-1} = [\![x=0]\!]$ is a polynomial that equals $1$ if and only if $x=0$. Therefore we can represent any function $f\colon GF(q)^n \to GF(q)$ in the variables $x_1,\ldots,x_n$ in the following form: $$\sum_{t_1,\ldots,t_n \in GF(q)} f(t_1,\ldots,t_n) \prod_{i=1}^n \left(1-(x_i-t_i)^{q-1}\right).$$ Since the dimension of the space of $n$-variate functions is $q^n$ and the number of monomials of individual degree at most $q-1$ is also $q^n$, we conclude that this representation is unique.
• I give a formula that works for every function $f$. You just have to substitute your function $f$. The result won't necessarily be pretty, but it will be a polynomial which computes your function. – Yuval Filmus Mar 21 '16 at 8:29
• Perhaps, though, there isn't a function that computes a reasonable $>$ on $GF(q)$. We won't know that until we settle on a definition. – Rick Decker Mar 24 '16 at 14:23