0
$\begingroup$

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.

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

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

$$f(x,y) = \frac{1}{2}(x+y+\mid x-y \mid)$$

$\endgroup$
1
$\begingroup$

$\max\{a,b\}=\frac{a+b+|a-b|}{2}$, $\min\{a,b\}=\frac{a+b-|a-b|}{2}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .