Suppose $x = (x_1,x_2,\dots,x_K) \in \mathbb{Z}^K_{\geq 0}$. For $x,y \in \mathbb{Z}^K_{\geq 0}$, we write $x \succ y$ or $y \prec x$ if $x \neq y$ and

\begin{align*} x_{i(x,y)} > y_{i(x,y)},\quad \text{ where } \quad i(x,y) := \max\{ i: x_i \neq y_i\}. \end{align*}

That is, for any two vectors $x$ and $y$ that are not equal, we let $i(x,y)$ be the last position on which they differ and say that $x \succ y$ if the coordinate of $x$ at $i(x,y)$ is larger than the corresponding coordinate of $y$. We write $x \succeq y$ if either $x = y$ or $x \succ y$, and similarly for $x \preceq y$. This is a total order.

For example, if $x = (7,2,1,0,0)$ and $y = (6,3,1,0,0)$ then $y \succ x$ because they are equal on the last three positions and the next position that they differ is the second coordinate, since 3>2 we conclude that $y \succ x$. This is called "reflected lexicographic order".

Now, let $mx(x) = max\{k: x_k > 0\}$, we are interested in defining a function $f: \mathbb{Z}^K_{\geq 0} \rightarrow [0,K+1)$ that has the following properties:

  • $f(0,0,\ldots,0) = 0$
  • $mx(x) \leq f(x) < mx(x)+1$ (Note that when one of the coordinates of x is 1 and the rest are 0, then $f(x)= mx(x)$, for example let $x = (0,1,0,0,0)$, then $f(x)=mx(x)=2$)
  • $f(.)$ is strictly increasing on $\mathbb{Z}^K_{\geq 0}$ wrt. the total-ordering defined above
  • The effect of adding a positive value to coordinate $k$ should be smaller than adding the same value to coordinate $k+1,....,K$, having all the other values fixed, sth like convexity property but I'm not sure if the exact definition of convexity applies here. For example suppose $K=5$, $f(0,3,0,0,0) - f(0,2,0,0,0) \leq f(0,0,3,0,0) - f(0,0,2,0,0)$

I could define a function that has the first three properties, but not the fourth one: For any $x \in \mathbb{Z}^K_{\geq 0}$, let $g_{k}(x) = \prod_{i=k}^{K} (1+i)^{-x_i}$ for $k=2,\dots,K$ and $g_{K+1}(x) = 1$. \begin{align} f(x) := \sum_{k=2}^{K+1} k g_k(x) \big(1 - k^{-x_{k-1}}\big). \end{align} $f(0,3,0,0,0) - f(0,2,0,0,0) = 2.888889 - 2.666667 = 0.222222$ but $f(0,0,3,0,0) - f(0,0,2,0,0) = 3.9375 - 3.75 = 0.1875$

How to define $f(.)$ so that it follows all the 4 properties?

PS: This is cross-post from Math.SE (I flagged it there to be migrated to mathoverflow but no one has migrated it)

  • $\begingroup$ Have you tried to figure out $K=2?$ that would be a good start. $\endgroup$ – Aaron Meyerowitz yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.