MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

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!

share|cite|improve this question
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.


share|cite|improve this answer

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:
alt text

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

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$).

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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