1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Most general order-preserving function

  1. Mar 28, 2015 #1
    Is there an easy description for all the real to real functions that are order-preserving? I can only think of linear functions
     
  2. jcsd
  3. Mar 28, 2015 #2

    Mark44

    Staff: Mentor

    What do you mean by "order-preserving?" Is it the idea that if a < b, then f(a) < f(b)? If so any function that is strictly increasing satisfies the latter inequality. If you mean something different, you need to clarify your question.
     
  4. Mar 28, 2015 #3
    What I need is a class of functions that is strictly increasing, very efficient to compute, and when one is selected uniformly and applied to x < y, the pair (f(x), f(y)) is uniformly distributed.
     
  5. Mar 28, 2015 #4

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    For every x,y? Then your class of functions has to be uncountable. What do you mean with "selected uniformly"? There is no clear definition of this on an arbitrary uncountable set.
    Also, uniform distributions over the full real line do not exist.

    f(x)=mx+c with suitable distributions of m and c can give a uniform distribution of (f(x),f(y)) in some finite range, or give nice non-uniform distributions as well.
     
  6. Mar 28, 2015 #5
    OK the domain is integers [1, ..., n], forget about what the range is for now, we can decide that after. I have a pair of numbers (a, b). I want to apply a function at random from this class so that (f(a), f(b)) is uniformly random and f(a) < f(b).

    f has to be efficiently computable. It also has to be "decomposable" into two parts f_1, f_2 such that f(x) = f_2 ( f_1 (x) ). Knowing ONLY ONE of f_1 or f_2, and given f(x), it should be infeasible to compute x.

    I'm thinking Ax + B for A > 0 and random B. Knowing Ax+B, and only one of A or B doesn't tell you anything about x.
     
  7. Mar 28, 2015 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Uniformly random where?

    Every f is "decomposable" that way, simply set f_1(x)=f(x), f_2(x)=x (or vice versa).
    Knowing only one of an arbitrary and unknown "decomposition" makes the task impossible - see my example, one of the functions could be just the identify function.

    I think it would really help if you give more context. What do you actually want to do?
     
  8. Mar 28, 2015 #7
    No. If f_1 = f then knowing f_1 and knowing f(x) gives you x, assuming it's not one-way and is one to one.

    You know that zero-knowledge proof of graph isomorphism? You have two permutations. Composition gives you the permutation. Knowing just one gives you nothing. I'm trying to come up with something similar for two ordered committed numbers.
     
  9. Mar 29, 2015 #8

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    So who is supposed to know what? What is the protocol you want to use, and what is the result?
     
  10. Mar 29, 2015 #9
    You're not supposed to know that. I'm supposed to come up with it. And I have! Thanks for the inputs.
     
  11. Mar 30, 2015 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Most general order-preserving function
Loading...