3
$\begingroup$

Suppose, that I have 4 points $x,y,z,w$ (positions on the x-axis), such that $x\le y\le z\le w$.

I find pairwise distances between them: $y-x,z-x,w-x,z-y,w-y,w-z$. Distances should be less or equal to some constant $k$.

Is there a function that contains all pairwise distances and attains the only maximum when $x,y,z,w$ are evenly spaced on the interval $[1, k+1]$ and the only minima when all variables are equal?

The function shouldn't depend on $k$.

$\endgroup$
2
  • $\begingroup$ a function that contains all pairwise distances Those distances are not independent since, for example, $\,(z-x)=(z-y)+(y-x)\,$. How do you define contains, then? Would for example the function $\,z^2-2zx+x^2=(z-x)^2=(z-y)^2+2(z-y)(y-x)+(y-x)^2\,$ contain $\,(z-x)\,$, or $\,(z-y)\,$ and $\,(y-x)\,$, or both? Other than this new "containment" requirement, the question is virtually identical to your previous one, answered here. $\endgroup$
    – dxiv
    Dec 30, 2017 at 7:36
  • $\begingroup$ Contain without cancelling. $\endgroup$
    – eMathHelp
    Dec 30, 2017 at 9:27

2 Answers 2

3
+50
$\begingroup$

Let $\,g\,$ be a strictly concave and strictly increasing function on $\,[\,0,k\,]\,$ such that $\,g(0)=0\,$.

Define $\,f : \left\{\, (x,y,z,w) \in [\,1,k+1\,]^4 \;\mid\; x \le y \le z \le w \,\right\} \to \mathbb{R}\,$ as:

$$ \begin{align} f(x,y,z,w) \;&=\; 2g(y-x)+g(z-y)+2g(w-z) \\[3px] &\quad +\;2 g\left(\frac{z-x}{2}\right) + 2 g\left(\frac{w-y}{2}\right) + \\[3px] &\quad +\;3 g\left(\frac{w-x}{3}\right) \end{align} $$

  • $\,f\,$ is non-negative since so is $\,g\,$.

  • $\,f(x,y,z,w) \gt 0\,$ if at least one of the arguments passed into $\,g\,$ is non-zero, since the respective $\,g(\cdot)\,$ term is strictly positive in that case, so $f(x,y,z,w)=0$ iff all arguments are zero $\;\iff\; x=y=z=w\,$ i.e. the minimum of $\,0\,$ is attained when all variables are equal.

  • It follows from Jensen's inequality that the maximum for a fixed total span $\,w-x\,$ is attained when $y-x$ $=z-y$ $=w-z$ $\displaystyle=\frac{z-x}{2}$ $\displaystyle=\frac{w-y}{2}$ $\displaystyle=\frac{w-x}{3}$ which happens iff the values are evenly spaced, and it follows from monotonicity that the absolute maximum is attained when $x=1,w=k+1$ i.e. at $\displaystyle\,\left(1,\frac{k+3}{3},\frac{2k+3}{3},k+1\right)\,$:

$$\require{cancel} \begin{align} \displaystyle f(x,y,z,w) \;&=\; 2g(y-x)+g(z-y)+2g(w-z) + 2 g\left(\frac{z-x}{2}\right) + 2 g\left(\frac{w-y}{2}\right) +\;3 g\left(\frac{w-x}{3}\right) \\[5px] &\le\; 12 \cdot g\left(\frac{2(y-x)+(z-y)+2(w-z)+2 \cfrac{z-x}{2}+2 \cfrac{w-y}{2}+3 \cfrac{w-x}{3}}{12}\right) \\[5px] &=\; 12 \cdot g\left(\frac{4(w-x)}{12}\right) \\[5px] &\le 12 \cdot g\left(\frac{(k+\bcancel{1})-\bcancel{1}}{3}\right) \\[5px] &= 12 \cdot g\left(\frac{k}{3}\right) \end{align} $$

An example could be $\,g(x) =\ln(1+x)\,$, but any $\,g\,$ satisfying the given conditions would work.


[ EDIT ]  A more general solution along the same line can be constructed from the identity:

$$ \small a (y - x) + b (z - y) + c (w - z) + (c - b) (z - x) + (a - b) (w - y) + (p - a + b - c) (w - x) \;=\; p(w-x) $$

Choose $\,0 \le b \le a,c\,$ and $\,p \ge a-b+c\,$ so that all coefficients are positive. Then the function defined below satisfies the posed requirements:

$$ \begin{align} f(x,y,z,w) \;&=\; a\cdot g(y-x)+ b \cdot g(z-y)+ c \cdot g(w-z) \\[3px] &\quad + 2(c-b) \cdot g\left(\frac{z-x}{2}\right) + 2(a-b) \cdot g\left(\frac{w-y}{2}\right) \\[3px] &\quad + 3(p-a+b-c) \cdot g\left(\frac{w-x}{3}\right) \end{align} $$

The proof goes just like before, and the maximum is $\displaystyle\,3p \cdot g\left(\frac{k}{3}\right)\,$.

The particular case above corresponds to $b=1, a=c=2, p=4\,$, and the case used in this related answer corresponds to $a=b=c=p=1\,$.

$\endgroup$
2
  • $\begingroup$ Thank you. Exactly what I was looking for? How will this change if I have more than 4 variables? $\endgroup$
    – eMathHelp
    Dec 31, 2017 at 13:12
  • $\begingroup$ @AndrewFount Glad it helped. It should work similarly for more variables. First step would be to establish an equivalent identity $\,\sum_{1 \le i \lt j \le n} a_{ij}(x_j-x_i) = p(x_n-x_1)\,$ with $\,a_{ij}, p \ge 0\,$. I don't have a closed form offhand, but pretty sure one can be found. Then, the function $\,f(x) = \sum_{1 \le i \lt j \le n} a_{ij}(j-i) \cdot g\left(\frac{x_j-x_i}{j-i}\right)\,$ would posess all the required properties. $\endgroup$
    – dxiv
    Dec 31, 2017 at 21:27
1
$\begingroup$

Yes, if there are no further restrictions then such a function does exist. Let $$d_1=y-x,\quad d_2=z-y,\quad d_3=w-z,$$ $$\alpha=\begin{cases} d_1+1&\text{if }d_1=d_2=d_3,\\ 0& \text{otherwise},\\ \end{cases}$$ and $$f(x,y,z,w)=\begin{cases}\alpha & \text{if }\alpha>1,\\ 1&\text{if }\alpha=0,\\ 0&\text{if }\alpha=1. \end{cases}$$

$\endgroup$
2
  • $\begingroup$ Where is z-x, w-x, w-y? $\endgroup$
    – eMathHelp
    Dec 30, 2017 at 9:26
  • $\begingroup$ @AndrewFount the domain restriction involving them can't be stated explicitly without mentioning $k$. $\endgroup$ Dec 30, 2017 at 17:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .