# How to design the max function for integers using only additions and multiplications?

I want to design a function which outputs the maximum value between two integers, something like this $f(x,y) = \begin{cases} 1, & \text{if } x > y, \\ 0, & \text{otherwise}. \end{cases}$ , using only additions, substractions and multiplications.

I would like to have a single equation $f(x,y) = x *y *x ..$ where $*$ maybe any operation from the ones mentioned above, if necessary division can be used too but preferably not.

I can restrict the operation to a finite algebraic field $Z_t$.

For equality comparison, I can define the function $EQU(x,y) = \begin{cases} 1, & \text{if } x == y, \\ 0, & \text{otherwise}. \end{cases}$

If $t$ is prime, the equality comparison can be computed like this $EQU(x,y)=1-(x-y)^\phi$, where the Euler totient $\phi(t)=t-1$, because $t$ is prime. Now, I am asking if something similar could be done for greater than comparison.

I need these comparison functions for a homomorphic encryption application where functions are computed as arithmetic circuits.

• Given that you have accepted an answer that doesn't meet your stated requirements, it is rather unclear what you were actually asking for. Mar 16, 2016 at 0:51
• EQU does not seem to work as advertised... Mar 19, 2016 at 12:17
• Yes, it doesn't. I replaced t from the exponent with phi(t)=t-1 and if t is prime the equation holds. Mar 20, 2016 at 10:56

A function defined using only addition, subtraction and multiplication is a polynomial function. The function $\max(x, y)$ is not a polynomial function. To see this, note that if $\max(x, y)$ were a polynomial, then the function $g$ defined by $g(x)= \max(x, 0)$ would be a non-zero polynomial function with infinitely many roots.
$$f(x,y) = \frac{1}{2}(x+y+\mid x-y \mid)$$
$\max\{a,b\}=\frac{a+b+|a-b|}{2}$, $\min\{a,b\}=\frac{a+b-|a-b|}{2}$