How to define a function that has these specific properties?

Question

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$
• 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$, also $f(0,1)= f(0,1,0,...,0) =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 four properties, but not the fifth 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 5 properties? The x-axis on this plot is an array, with each column representing a vector $x$ (I just chose some vectors), ordered in increasing reflected lexicographic order. The blue curve is the $f$ function I defined and the red curve is $mx$ function. I'm not sure if mathematically this makes sense but I was wondering if we can have convex function (or even linear functions) between each $k$ and $k+1$?

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

Answer 1

The function $f$ we construct below certainly isn't linear between $k$ and $k+1$, but it does satisfy the five requirements.

As a brief notation change, we let $m(x)$ be what you have called $mx(x)$, $\mathbb{N} = \mathbb{Z}_{\geq 0}$, and let $e_i$ be the tuple that is $1$ in the $i$ coordinate and $0$ everywhere else. We make the convention that $m(0,\dots,0) = 0$.

---

Let $b: \mathbb{N}\rightarrow [0,1)$ be any strictly increasing function such that $b(0) = 0$. For example, $b(x) = \frac{x}{x+1}$. The basic idea will be to create a function $f(x) = m(x) + g(x)$, where $g$ is a sum of terms $c_ib(x_i)$, such that $c_{i-1} < c_i(b(x_i + 1) - b(x_i))$. One unfortunate feature of this construction is that the $c_i$ values depend on the tuple $x$ itself.

Now let's fix a $K$, choose any function $b$ as described above, and consider $x = (x_1, \dots, x_k)$ in $(\mathbb{N}^k, \prec)$. For all $i<m(x)$, define the $i^{th}$ interval width $\delta_i = \frac{1}{10}\left(b(x_{i+1} + 1) - b(x_{i+1}) \right)$.

Now set $f(x) = 0$ if $x=(0,\dots,0)$, and if $x\neq 0$ then $$f(x) = m(x) + 10^{m(x) - K}\cdot \left[ b\left(x_{m(x)}\right) -b(1) + \sum_{i=1}^{m(x)-1} \left( \prod_{j=i}^{m(x)-1} \delta_j \right)\cdot b(x_i) \right]$$

---

Note that $b\left(x_{m(x)}\right) -b(1) \geq 0$, and is equal to $0$ exactly when $x_{m(x)} = 1$. Further, the final summation is also non-negative, and is equal to $0$ only when $x_i = 0$ for all $i < m(x)$. It's not hard to see that the summation as a whole is less than $b\left(x_{m(x)} + 1\right) - b\left(x_{m(x)}\right)$. The first three conditions follow immediately from these observations.

To see that the last two conditions hold, it helps to notice that $$ \left( \prod_{j=l}^{m(x)-1} \delta_j \right)\cdot b(x_l) > \sum_{i=1}^{l-1}\left( \prod_{j=i}^{m(x)-1} \delta_j \right)\cdot b(x_i)$$

The factor of $10^{m(x)-K}$ in the definition of $f$ is just to make sure that the effect of adding things to coordinates greater than $m(x)$ has a smaller effect the smaller the coordinate.