# A calculus question related to quantization dimension

Going through some old papers, I came up with a simple-looking problem I thought about 5 years ago or so.

MO wants motivation ... Associated to a probability measure on a metric space is something called "quantization dimension" ... this involves defining a function $D \colon (0,\infty) \to (0,\infty)$. Exactly how is not the point here, but see for example

http://www.ams.org/mathscinet-getitem?mr=1877974

Lindsay, L. J. and Mauldin, R. D. Quantization dimension for conformal iterated function systems. Nonlinearity 15 (2002), no. 1, 189--199.

It was observed numerically that $D$ is increasing and concave, but proof was lacking. When we do this for the simplest possible self-similar measure (similarities with ratios $s_1, s_2$ and probabilities $p_1, p_2$) I still did not solve it, even though it looks like an elementary calculus exercise. Here it is.

Let $s_1, s_2, p_1, p_2$ be positive real numbers such that $s_1 < 1$, $s_2 < 1$, $p_1+p_2=1$. For $r>0$ define $D = D(r)$ implicitly by $$\left(p_1 s_1^r\right)^{D/(r+D)} + \left(p_2 s_2^r\right)^{D/(r+D)} = 1.$$ Then:
Does it follow that $D'(r) \ge 0$? [YES]
Does it follow that $D''(r) \le 0$? [OPEN]

At least it was open back then!

-
Actually $D$ may fail to be concave though you need to tune the parameters very carefully to achieve it. If you are still interested, let me know and I'll post the counterexample. –  fedja Jun 5 '11 at 0:42
Yes, please!  –  Gerald Edgar Jun 5 '11 at 3:08
Done. Do you want a one-line proof of the inequality $D'\ge 0$ too or you know that one? :) (alas, the paper you quoted is not an open access one so I'm in dark as to what you've done there :(). –  fedja Jun 5 '11 at 20:13
Thanks, I'll take a look at it. –  Gerald Edgar Jun 5 '11 at 22:32

All right. The hardest thing is to do all algebra right (I am always prone to misplacing + and -, so check everything I say in the first part. :)).

Let $\lambda=\log \frac 1p$ and $\Gamma=\log\frac 1s$. We want to create a situation when there are 3 points on the line $D=1+br$ ($b>0$). Let's write $(ps^r)^{D/D+r}$ as the exponent of minus $\lambda\frac{1+br}{1+(b+1)r}+\Gamma\frac{r(1+br)}{1+(b+1)r}$. Our first step will be to replace $(b+1)r$ by $r$. Since $\Gamma>0$ is free ($\lambda$'s are restricted to $\sum_j e^{-\lambda_j}=1$), we still get $\lambda\frac{1+br}{1+r}+\Gamma\frac{r(1+br)}{1+r}$ but now $b\in(0,1)$. Now replace $1+r$ with $r$. We'll get $\lambda\frac{1-b+br}{r}+\Gamma\frac{(r-1)(1-b+br)}{r}$. Now let's open the parentheses and group the terms. If I haven't made an odd number of errors, we get $(\lambda-\Gamma)(1-b)r^{-1}+\Gamma b r+(\lambda-\Gamma)b+\Gamma(1-b)$ ($r\ge 1$). Now let us replace $r$ by $\frac{1-b}{b}r$ to get $(\lambda-\Gamma)br^{-1}+\Gamma(1-b) r+(\lambda-\Gamma)b+\Gamma(1-b)$ ($r\ge \frac b{1-b}$)and denote $X=(\lambda-\Gamma)b$, $Y=\Gamma(1-b)$. Thus, the problem is reduced to asking whether the sum of two exponents of the kind $$\exp(-Xr^{-1}-Yr-X-Y)$$ where $r> 0$, $Y>0$ and $X$ is unrestricted can take the value $1$ three times on the positive semiaxis (the leftmost root will be $b/(1-b)$ after which you can go back and discern the initial values).

The rest is simple analysis.

Let for one exponent $X=Y=B$. Then at $1$, it is $e^{-4B}$ and at $1/2$ it is $e^{-4.5B}$. Now for the second exponent choose $Y=A$ and $X=-\varepsilon$. Then $X$ guarantees that we have $+\infty$ at $0+$ but is invisible for any noticeable positive $r$. Also, at $+\infty$, we have $0$, so we just want the value at $1$ to be larger than $1$ and the value at $1/2$ to be smaller than $1$, which results in the system of inequalities $$e^{-1.5A}+e^{-4.5B}<1;\qquad e^{-2A}+e^{-4B}>1$$ Now, take relatively small $A$ and put $e^{-4B}=2A$. The second inequality is then fine and the first one is $e^{-1.5 A}+A^{9/8}<1$, which is true if $A$ is small enough.

UPDATE: The counterexample failed, so let's try the proof. The same chain of changes of variable can be applied to the line $D=ar+b$. Note that $D'>0$ and $(D/r)'<0$ so the only chance to have this line to intersect the graph of $D$ more than once is to take $a,b>0$.

Thus, using the tangent line to the graph of $D$ at some positive point where concavity is violated, the problem can be restated as follows: the sum $F(r)=e^{-Ar^{-1}-Br-(A+B)}+e^{-Cr^{-1}-Dr-(C+D)}$ cannot have the value $1$, the derivative $0$ and positive second derivative at any point except the point corresponding to the case when the original $r$ is $0$. Here $B,D>0$ and $A,C$ are unrestricted.

If $A,C\le 0$, then $F$ is decreasing and the claim is trivial. So, let us assume that $C> 0$.

The nice case is when $A>0$ as well. In this case, we just need to switch to the variables $x=\frac 1{r+1}$ and $y=\frac r{r+1}$ and write $F$, $F'$ and $F''$ explicitly (differentiating with respect to $x$ instead of $r$):

$e^{-\frac Ax-\frac By}+e^{-\frac Cx-\frac Dy}=1$

$\left(\frac A{x^2}-\frac B{y^2}\right)e^{-\frac Ax-\frac By}+\left(\frac C{x^2}-\frac D{y^2}\right)e^{-\frac Cx-\frac Dy}=0$

$\left[\left(\frac A{x^2}-\frac B{y^2}\right)^2-2\left(\frac A{x^3}+\frac B{y^3}\right)\right]e^{-\frac Ax-\frac By}+\left[\left(\frac C{x^2}-\frac D{y^2}\right)^2-2\left(\frac C{x^3}+\frac D{y^3}\right)\right]e^{-\frac Cx-\frac Dy}\ge 0$

Note that the first square bracket can be non-negative only if $\max(A/x,B/y)>2$, in which case the first exponent is at most $e^{-2}$. This tells us that the second exponent is certainly above $1/e$, so $\frac Cx+\frac Dy<1$ and the cubic sum in the second square bracket beats the square of the quadratic sum even with coefficient $1$. Thus, the last inequality implies

$\left(\frac A{x^2}-\frac B{y^2}\right)^2 e^{-\frac Ax-\frac By}\ge\left(\frac C{x^3}+\frac D{y^3}\right)e^{-\frac Cx-\frac Dy}$.

Using the estimate $e^{-t}\ge 1-te^{-t}$ for $t>0$, we conclude that the first equality implies

$e^{-\frac Ax-\frac By}\ge \left(\frac C{x}+\frac D{y}\right)e^{-\frac Cx-\frac Dy}$.

Now, the second inequality certainly implies that

$\left|\frac A{x^2}-\frac B{y^2}\right|e^{-\frac Ax-\frac By}<\left(\frac C{x^2}+\frac D{y^2}\right)e^{-\frac Cx-\frac Dy}$.

Now, looking at the left hand sides, which form a geometric progression, we see that the right hand sides violate Cauchy-Schwarz, so this case is done.

In the second case $A<0$, we start with noticing that a dip on the line $F=1$ implies that $F$ takes the same value $1$ five or more times (counting with multiplicity). So, we need to show that it cannot happen. My original idea was to show that $X,Y,X^2,XY,Y^2$ is a Chebyshev system on the curve $e^{-X}+e^{-Y}=1$. This can be done (differentiating quotients and getting rid of the functions one by one, as usual) but I couldn't finish the necessary computations without Maxima and posting the resulting long expressions was certainly out of question. Finally I settled on a different change of variable.

TO BE CONTINUED...

-

My response to the answer by fedja, Jun 5, 2011. This should be a comment, but won't fit.

It didn't work. Taking values of $A,B,\epsilon$ that satisfy your conditions, then tracing back through using 20-digit arithmetic, I get these values: $s_1=0.34018988053902955186$, $s_2=0.98903555253485545775$, $p_1=0.0000000004309513037$, $p_2=0.99999999956904869628$, $b = 0.050000002052149145975$. And this does what you wanted: function $(p_1 s_1^r)^{(1+b r)/(1+b r+r)}+ (p_2 s_2^r)^{(1+b r)/(1+b r+r)}$ looks like this:

It crosses the line $y=1$ three times, as required. But the function $D$ defined as specified implicitly, looks like this:

It does not cross the line three times. The value $r=0$ is no good for this (because in fact every number $D$ satisfies the equation when $r=0$).

-
Ah, you're right! $D(0)$ is undefined, so I need 3 strictly positive points on the line (the dip instead of the hump). It is also easy when you have more than 2 summands (I don't know if it is meaningful, but $D'\ge 0$ works for every number) but for 2 it may be, indeed, impossible. I'll check by the evening and update the post :). –  fedja Jun 6 '11 at 12:51
It took more than one evening but by now (I believe that) I have a proof. I'll try to update my answer as soon as I have more computer time (I'm traveling right now, so it is not always easy to find a quiet place and time; the proof is a bit long, so maybe I'll write piece after piece bumping the post :). Let's see if I'll make more silly mistakes). –  fedja Jun 9 '11 at 20:37