Most general order-preserving function

  • Context: Graduate 
  • Thread starter Thread starter Dragonfall
  • Start date Start date
  • Tags Tags
    Function General
Click For Summary

Discussion Overview

The discussion centers on the characterization of order-preserving functions from the real numbers to the real numbers, with a focus on identifying a class of functions that are strictly increasing, efficiently computable, and yield uniformly distributed outputs when applied to pairs of inputs. Participants explore various definitions and implications of order-preserving functions, as well as the computational properties of proposed function classes.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • Some participants propose that order-preserving functions are those that satisfy the condition f(a) < f(b) whenever a < b, suggesting that strictly increasing functions meet this criterion.
  • One participant seeks a class of strictly increasing functions that, when selected uniformly, produce uniformly distributed pairs (f(x), f(y)) for x < y.
  • Another participant questions the feasibility of defining a uniform selection from an uncountable set and notes that uniform distributions over the full real line do not exist.
  • A suggestion is made that linear functions of the form f(x) = mx + c could yield uniform distributions under certain conditions, particularly when m and c are chosen appropriately.
  • One participant refines the problem to a finite domain of integers and emphasizes the need for the function to be efficiently computable and decomposable into two parts.
  • Concerns are raised about the definition of "decomposable" functions, with a participant arguing that knowing one part of a decomposition does not necessarily prevent the recovery of the input.
  • Another participant introduces the concept of zero-knowledge proofs in relation to the problem, suggesting a parallel with ordered committed numbers.
  • A later reply hints at the development of a new protocol related to Yao's Millionaires' Problem, although details remain vague.

Areas of Agreement / Disagreement

Participants express differing views on the definitions and properties of order-preserving functions, particularly regarding uniform distributions and the implications of function decomposition. The discussion remains unresolved with multiple competing perspectives on the feasibility of the proposed approaches.

Contextual Notes

Limitations include the lack of clarity around the definition of "uniformly selected" functions from uncountable sets, as well as the implications of function decomposition on the ability to recover inputs. The discussion also highlights the complexity of achieving uniform distributions in various contexts.

Dragonfall
Messages
1,023
Reaction score
5
Is there an easy description for all the real to real functions that are order-preserving? I can only think of linear functions
 
Mathematics news on Phys.org
Dragonfall said:
Is there an easy description for all the real to real functions that are order-preserving? I can only think of linear functions
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.
 
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.
 
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.
 
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.
 
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?
 
mfb said:
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?

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.
 
Dragonfall said:
I'm trying to come up with something similar for two ordered committed numbers.
So who is supposed to know what? What is the protocol you want to use, and what is the result?
 
You're not supposed to know that. I'm supposed to come up with it. And I have! Thanks for the inputs.
 

Similar threads

High School The Relationship Between Function and Ordering Relation
  • · Replies 8 ·
Replies
8
Views
2K
Undergrad Gradient descent algorithm and optimizers
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Why is it important to convert angle units when using trigonometric functions?
  • · Replies 8 ·
Replies
8
Views
2K
Graduate Ramanujan Summation, Variations of
  • · Replies 7 ·
Replies
7
Views
2K
Undergrad Can the same argument be used for both radians and degrees in the sine function?
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Is parallel transport exactly norm-preserving or only approximately?
  • · Replies 21 ·
Replies
21
Views
1K
Graduate Jacobi Elliptic Functions and Integrals
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Comparing ##a^b## and ##b^a##
  • · Replies 19 ·
Replies
19
Views
2K
High School Can 2(sinx) be called a 'trigonometric function'?
  • · Replies 28 ·
Replies
28
Views
3K
Undergrad Elementary Functions - What Is The Exact Definition?
  • · Replies 8 ·
Replies
8
Views
3K