A calculus question related to quantization dimension - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T08:40:49Z http://mathoverflow.net/feeds/question/34671 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34671/a-calculus-question-related-to-quantization-dimension A calculus question related to quantization dimension Gerald Edgar 2010-08-05T18:52:15Z 2011-06-09T21:17:36Z <p>Going through some old papers, I came up with a simple-looking problem I thought about 5 years ago or so. </p> <p>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 </p> <p><a href="http://www.ams.org/mathscinet-getitem?mr=1877974" rel="nofollow">http://www.ams.org/mathscinet-getitem?mr=1877974</a></p> <p>Lindsay, L. J. and Mauldin, R. D. Quantization dimension for conformal iterated function systems. Nonlinearity 15 (2002), no. 1, 189--199. </p> <p>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.</p> <blockquote> <p>Let $s_1, s_2, p_1, p_2$ be positive real numbers such that $s_1 &lt; 1$, $s_2 &lt; 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:<br> Does it follow that $D'(r) \ge 0$? [YES]<br> Does it follow that $D''(r) \le 0$? [OPEN]</p> </blockquote> <p>At least it was open back then!</p> http://mathoverflow.net/questions/34671/a-calculus-question-related-to-quantization-dimension/66983#66983 Answer by fedja for A calculus question related to quantization dimension fedja 2011-06-05T20:07:35Z 2011-06-09T21:17:36Z <p>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. :)).</p> <p>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). </p> <p>The rest is simple analysis.</p> <p>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}&lt;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}&lt;1$, which is true if $A$ is small enough.</p> <p>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)'&lt;0$ so the only chance to have this line to intersect the graph of $D$ more than once is to take $a,b>0$.</p> <p>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.</p> <p>If $A,C\le 0$, then $F$ is decreasing and the claim is trivial. So, let us assume that $C> 0$.</p> <p>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$):</p> <p>$e^{-\frac Ax-\frac By}+e^{-\frac Cx-\frac Dy}=1$</p> <p>$\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$</p> <p>$\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$</p> <p>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&lt;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 </p> <p>$\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}$.</p> <p>Using the estimate $e^{-t}\ge 1-te^{-t}$ for $t>0$, we conclude that the first equality implies </p> <p>$e^{-\frac Ax-\frac By}\ge \left(\frac C{x}+\frac D{y}\right)e^{-\frac Cx-\frac Dy}$.</p> <p>Now, the second inequality certainly implies that</p> <p>$\left|\frac A{x^2}-\frac B{y^2}\right|e^{-\frac Ax-\frac By}&lt;\left(\frac C{x^2}+\frac D{y^2}\right)e^{-\frac Cx-\frac Dy}$.</p> <p>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.</p> <p>In the second case $A&lt;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.</p> <p>TO BE CONTINUED... </p> http://mathoverflow.net/questions/34671/a-calculus-question-related-to-quantization-dimension/67010#67010 Answer by Gerald Edgar for A calculus question related to quantization dimension Gerald Edgar 2011-06-06T04:06:33Z 2011-06-06T04:13:54Z <p>My response to the answer by fedja, Jun 5, 2011. This should be a comment, but won't fit. </p> <p>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:<br> <img src="http://i53.tinypic.com/339lrox.jpg" alt="alt text"> </p> <p>It crosses the line $y=1$ three times, as required. But the function $D$ defined as specified implicitly, looks like this:<br> <img src="http://i51.tinypic.com/2z86umw.jpg" alt="alt text"> </p> <p>It does <em>not</em> cross the line three times. The value $r=0$ is no good for this (because in fact <em>every</em> number $D$ satisfies the equation when $r=0$).</p>