4
$\begingroup$

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? enter image description here 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)

$\endgroup$
7
  • $\begingroup$ Have you tried to figure out $K=2?$ that would be a good start. $\endgroup$ Oct 19 '20 at 7:56
  • $\begingroup$ Yes, but didn't work out $\endgroup$
    – ie86
    Oct 20 '20 at 23:04
  • $\begingroup$ May you clarify your last condition? An example you show does not help, as you consider an effect of adding a positive value to diferent coordinates in different elements of $\mathbb Z_{\geq 0}^k$. Is it true that such effect should hold for any two different sequences? Is it true that such effect should hold even if the terms to be changed are different? A formal definition would help much. $\endgroup$ Oct 30 '20 at 8:04
  • $\begingroup$ @ Ilya Bogdanov, it's hard to define formally. Please see the above plot and it's explanation $\endgroup$
    – ie86
    Nov 1 '20 at 20:24
  • 1
    $\begingroup$ @LSpice You are right, but the order is the "reflected" lexicographic order which is not known as much $\endgroup$
    – ie86
    Nov 3 '20 at 0:11
1
+50
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ @ie86 the term $b(x_{m(x)}) - b(1)$ is equal to $0$ identically for $f(1,0)$, but is equal to $b(2)-b(1) > 0$ for $f(2,0)$. That's the purpose of that term, to ensure that the function is increasing on the highest non-zero coordinate $\endgroup$ Nov 6 '20 at 20:11
  • 1
    $\begingroup$ @ie86 I think I see where the confusion is. $x_{m(x)}$ is the value in coordinate $m(x)$. So for example, let $x = (1,2,4,0)$, then $m(x) = 3$, so $x_{m(x)} = 4$, the value in the max coordinate. $\endgroup$ Nov 6 '20 at 20:16
  • $\begingroup$ Ok, thanks. I didn't get a chance to investigate this function more but since the bounty was expiring, I gave it. If I have a question, I'll comment $\endgroup$
    – ie86
    Nov 6 '20 at 20:18
  • $\begingroup$ The value of your proposed function for the vectors in my plot are: 0, 1, 1.000017 2, 2.000008, 2.000011, 2.000167, 2.000171, 2.000172, 3, 3.000004,... which are very close to their mx values and close to each other. How to achieve an f function with numbers not so close to each other? $\endgroup$
    – ie86
    Nov 9 '20 at 4:07
  • $\begingroup$ @ie86 It will only help so much, since the function 'works' by squeezing intervals into eachother (which necessarily means they get close together eventually), but you can replace all the appearances of the integer $10$ by a smaller value. So in the definition of $\delta_i$, you can try multiply by $\frac{1}{2}$ instead of $\frac{1}{10}$, and same thing in the function definition using $2^{m(x)-K}$. $\endgroup$ Nov 9 '20 at 8:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.