# 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

## 1 Answer

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.

• huh? does not seem to answer the question. it seems to assert in some sense all functions can be constructed... but does not seem to describe how to construct it (one in particular, or the one requested)... – vzn Mar 20 '16 at 0:24
• @vzn If all functions can be constructed, then every particular one can be. – Yuval Filmus Mar 20 '16 at 0:39
• The function description for greater than would be highly appreciated, as I haven't figured out how to build it. – user2991856 Mar 21 '16 at 8:19
• 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