Monthly Archives: April 2016

Fun with simple analysis problems I

This last semester, I ran a fun, informal master class in problem solving. Actually, a graduate student of mine — Yunfeng Hu — who is an expert problem solver, produced all the problems from the immense library he built up over his undergraduate career in China.

I believe that the art and culture of problem solving is not as widely valued in the USA as it ought to be. Of course there are those that do pursue this obsession and we end up with people with high scores on the Olympiad and Putnam competitions. But many (most?) do not having develop this skill to any great degree. While one can certainly argue that too much emphasis on problem solving along the lines of these well known competitions does not help very much in making real progress in current research, I would argue that many have fallen off the other side of the horse — many are sometimes hampered by their lack of experience in solving these simpler problems.


Here is a problem that arose in our Wednesday night session:

Suppose that

     |\frac{df}{dx}(x)| \leq \lambda |f(x)|                    (1)

for all x, that f is continuous and differentiable, and that f(0) = 0. Prove that f(x) = 0 everywhere.

Perhaps you want to fiddle with this problem before looking at some solutions. If so, wait to read further.


Here are three solutions: in these first three solutions we are dealing with f:\Bbb{R}\rightarrow\Bbb{R} and so we will denote \frac{df}{dx} by f'.

(Solution 1) Consider all the solutions to g' = 2\lambda g and h' = -2\lambda h. These are all curves in \Bbb{R}^2 of the form y = g_{C}(x) = Ce^{2\lambda x} and y = h_{C}(x) = Ce^{2\lambda x}. We note that if y=f(x) is any function that satisfies equation (1), then everywhere its graph intersects a graph of a curve of the form y = g_{C}(x) = Ce^{2\lambda x} for some C\in\Bbb{R}, the graph of f must cross the graph of g_{C}. if we are moving form left to right the graph of f moves from above to below the graph of g_{C}. Likewise, f crosses any h_{C} from below to above, when moving from left to right in x. Now, supposing that f(x*) > 0 at some x*. Then simply choose the curves g_{\frac{f(x*)}{e^{2\lambda x*}}}(x) and h_{\frac{f(x*)}{e^{-2\lambda x*}}}(x) as fences that cannot be crossed by f(x) (one for x < x* and the other for x > x* to conclude that f(x) can never equal zero. (Exercise: Verify that this last statement is correct. Also note that assuming f(x*) > 0 is enough since, if instead f(x*) < 0 then -f also satisfies (1) and is positive at x*)

(Solution 2) This next solution is a sort of barehanded version of the first solution. We note that equation (1) is equivalent to

-\lambda |f(x)| \leq f'(x) \leq \lambda |f(x)|            (2)

and if we assume that f(x) > 0 on E\subset\Bbb{R}, then this of course turns into

-\lambda f(x) \leq f'(x) \leq \lambda f(x).            (3)

Assume that [x_0,x_1]\in E and divide by f(x)  to get  -\lambda \leq \frac{f'(x)}{f(x)} \leq \lambda. Integrating this, we have -\lambda (x_1 - x_0) \leq \ln(\frac{f(x_1)}{f(x_0)}) \leq \lambda (x_1 - x_0) or

e^{-\lambda (x_1 - x_0)} \leq \frac{f(x_1)}{f(x_0)} \leq e^{\lambda (x_1 - x_0)}.            (4)

Now assume that f(x*) > 0. Define u = \sup \{ w | f(x) > 0 \text{ for all } x* < x < w\} and l = \inf \{ w | f(x) > 0 \text{ for all }x* > x > w \}. Note that l \neq -\infty implies that f(l)  = 0 and u \neq \infty implies that f(u)  = 0. Use equation (4) together with \{\text{a sequence of }x_0\text{'s} \downarrow l \text{ and }x_1 = x*\} or \{x_0 = x* \text{ and a sequence of }x_1\text{'s} \uparrow u\},  to get a contradiction if either l \neq -\infty or u \neq \infty.

(Solution 3) In this approach, we use the mean value theorem to get what we want. Suppose that f(x_0) = 0. We will prove that f(x) = 0 on the interval I = [x_0 - \frac{1}{2\lambda}, x_0 + \frac{1}{2\lambda}].

(exercise) Prove that this shows that \{f(x) = 0\text{ for some } x\} \Rightarrow \{f = 0\text{ for all } x\in\Bbb{R}\}. (Of course, all this assumes Equation (1) is true.)

Assume that x\in I. Then the mean value theorem says that

|f(x) - f(x_0)| \leq |f'(y_1)| |x - x_0| \leq |f'(y_1)| \frac{1}{2\lambda}               (5)

for some y_1\in I. But using equation (1) and the fact that f(x_0) = 0, this turns into |f(x)| \leq \frac{1}{2}f(y_1). By the same reasoning, we get that  |f(y_1)| \leq \frac{1}{2}f(y_2) for some y_2 \in I, and we can conclude that |f(x)| \leq \frac{1}{2^{2}}f(y_2). Repeating this argument, we have

|f(x)| \leq \frac{1}{2^{n}}f(y_n)                  (6)

for some y_n \in I, for any positive integer n. Because f is continuous, we know that there is an M < \infty such that f(x) < M \text{ for all } x\in I. Using this fact together with Equation (6), we get

|f(x)| \leq \frac{M}{2^{n}} \text{ for all positive integers } n                (7)

which of course implies that f(x) = 0


Now we could stop there, with three different solutions to the problem, but there is more we can find from where are now.


Notice that one way of looking at the result we have shown is that if

(1) f is differentiable,

(2) f(x_0)=0 and

(3) for some \delta > 0, we have that f(x) \neq 0 when x \neq x_0 and x\in [x_0 - \delta, x_0 + \delta],

then

\limsup_{x\rightarrow x_0}A_{f}(x) \equiv \left|\frac{f'(x)}{f(x)}\right|\rightarrow\infty              (8)

Note also that if we define

a(f) \equiv \sup_{x\in\Bbb{R}} A_{f}(x)                  (9)

we find that

a(f) = a(\alpha f) \text{ for all }\alpha\neq 0.               (10)

Let C^{1}(\Bbb{R},\Bbb{R}) denote the continuously differentiable functions from \Bbb{R}\text{ to }\Bbb{R}. If we define C_{\lambda} = \{f | a(f) \leq \lambda\} we find that not only is \bigcup_{n\in\Bbb{Z}^{+}} C_n not all of C^{1}(\Bbb{R},\Bbb{R}), we also have functions satisfying 0 < b \leq f(x) \leq B < \infty whose a(f) = \infty. So we will restrict the class of functions a bit more. The space of continuously differentiable functions from K\subset \Bbb{R} to \Bbb{R}, C^{1}(K,\Bbb{R}), where K = [-R,R] (compact!), is closer to what we want. Now, C_{\infty} \setminus\bigcup_{n\in\Bbb{Z}^{+}} C_n contains only those functions which have a root in K.

We will call the functions in C_{\lambda} \subset C^{1}(K,\Bbb{R}) functions with maximal growth rate \lambda. This is a natural moduli for functions when we are studying stuff whose (maximal) grow rate depends linearly on the current amount of stuff. Of course populations of living things fall in the class of things for which this is true. from the proofs above, we know that if f\in C_\lambda, then it’s graph lives in the cone defined by exponentials. More precisely

If a(f) = \lambda then for x < x_0 ,   \frac{f(x_0)}{e^{\lambda x_0)}}e^{\lambda x}  \leq f(x) \leq  \frac{f(x_0)}{e^{-\lambda x_0)}}e^{-\lambda x}   and for x > x_0 we have \frac{f(x_0)}{e^{-\lambda x_0)}}e^{-\lambda x}  \leq f(x) \leq  \frac{f(x_0)}{e^{\lambda x_0)}}e^{\lambda x}.

(Exercise) Prove this. Hint: use the first proof where instead of 2\lambda you use \alpha\lambda and let \alpha\downarrow 1.

(Remark) Notice that Equation (10) and \lambda < \infty implies that scaling a function in C_\lambda by any non-zero scalar yields another function in C_\lambda. As a result, we might choose to consider only

F \equiv f\in c_\lambda\text{ such that }f(0) = 1

or

F \equiv \{\text{ functions whose minimum value on }K\text{ is }1\}.

In both cases we end up with subsets that generate C_\lambda when we take all multiples of those functions by nonzero real numbers.

(Exercise) If we move to high dimensional domains, how wild can the compact set K be and still get these results? It must clearly be connected, so in \Bbb{R}^1 we are already completely general with our K above.


Moving back to Equation (1), we can look for generalizations: for example, will this result hold when f:\Bbb{R}^{n} \rightarrow \Bbb{R}^{m}? How about when f maps from one Banach space to another? How about the case in which f is merely Lipschitz?

Lets begin with f:\Bbb{R}^{n} \rightarrow \Bbb{R}^{m}.

In this case, the appropriate version of Equation (1) is

||Df(x)|| \leq \lambda ||f(x)||                    (11)

where ||Df(x)|| denotes the operator norm of the derivative Df(x) and ||f(x)|| is the euclidean norm of f(x) in \Bbb{R}^m.

Notice that

D\ln(||f(x)||) = \frac{1}{||f(x)||}\left(\frac{f(x)}{||f(x)||}\right)^{t}Df(x)                    (12)

where \left(\frac{f(x)}{||f(x)||}\right)^{t} is an m dimensional row vector and Df(x) is an n\text{ by }m dimensional matrix. (Thus the gradient vector is the transpose of the resulting n dimensional row vector.)  Now we can use this to get the result.

Let \gamma(s) be the arclength parameterized line segment that starts at x_0 and ends at x_1 the The above equation tells us that

\int_{\gamma} D\ln(||f(x(s))||) ds =  \int_{\gamma} \frac{1}{||f(x)||}\left(\frac{f(x)}{||f(x)||}\right)^{t}Df(x)  \leq \int_{\gamma} \frac{||Df(x(s))||}{||f(x))||} ds.        (13)

Thus, we can conclude that

\ln(||f(x_1)||) - \ln(||f(x_0)||) \leq \lambda ||x_1 - x_0||

which implies that

-\lambda ||x_1 - x_2|| \leq \ln\left(\frac{||f(x_1)||}{||f(x_0)||}\right) \leq \lambda ||x_1 - x_0||

and we can proceed as we did in the second proof of the problem in the case that f:\Bbb{R}\rightarrow \Bbb{R}. We end up with the following result

If ||Df(x)|| \leq \lambda ||f(x)||  and ||f(x)|| \neq 0 \text{ for all } x\in B(x*,r)\subset\Bbb{R}^n, then

e^{-\lambda ||x - x*||} \leq \frac{||f(x)||}{||f(x*)||} \leq e^{\lambda ||x - x*||}

for all x\in B(x*,r).

(Exercise) Show that this result implies that if f(x) = 0 anywhere, it equals 0 everywhere.

(Exercise) Show that this is implies the one dimensional result we proved above (the first theorem we proved above).

(Exercise) Our proof of the result for the case f:\Bbb{R}^n\rightarrow\Bbb{R}^m can be carried over to the case of f:B_1 \rightarrow B_2 where B_1\text{ and }B_2 are Banach Spaces — carry out those steps!


We come now to the question of what we can say when we are less restrictive with the constraints on differentiability.  We consider the case in which f:\Bbb{R}^n\rightarrow\Bbb{R}^m is Lipschitz. The complication here is that while we know that f is differentiable almost everywhere, it might not be differentiable anywhere on the line segment from x_0 to x_1.

Consider a cylinder C_{x_0}^{x_1}(1), with radius 1 and axis equal to the segment from x_0\text{ to }x_1. Let E = C_{x_0}^{x_1}(1) \cap \{x| Df(x)\text{ exists }\}. Since f is differentiable almost everywhere, we have that \mathcal{L}^n( C_{x_0}^{x_1}(1)\setminus E) = 0. Therefore almost every segment L generated by the intersection of a line parallel to the cylinder axis and the cylinder, intersects E in a set of length ||x_1 - x_0||. We can therefore choose a sequence of such segments converging to [x_0,x_1].

lip-cylinder

Since Df exists \mathcal{H}^1 almost everywhere on the segments [x_0^k, x_1^k]  and f is continuous everywhere, we can integrate the derivatives to get:

-\lambda ||x_1^k - x_0^k|| \leq \ln\left(\frac{||f(x_1^k)||}{||f(x_0^k)||}\right) \leq \lambda ||x_1^k - x_0^k||.

And because f is continuous we get that

-\lambda ||x_1 - x_0|| \leq \ln\left(\frac{||f(x_1)||}{||f(x_0)||}\right) \leq \lambda ||x_1- x_0||.

so that we end up with the same result that we had for differentiable functions.


There are other directions to take this.

From the perspective of geometric objects, the ratio \frac{||Df||}{||f||} is a bit funky — for example, if f(x) = volume of a set E(x)\subset \Bbb{R}^n  = \mathcal{L}^n(E(x)), where x can be thought of as the center of the set, we have that Df will be a vectorfield \eta times \mathcal{H}^{n-1} restricted to the \partial E(x). Thus, ||Df|| will be an n-1-dimensional quantity and f a n-dimensional quantity. We would usually expect there to be exponents, as in the case of the Poincare ineqaulity,  making the ratio non-dimensional.

On the other hand, one can see this ratio as a sort of measure of reciprocal length of the objects we are dealing with. From the perspective, this result seems to say that no matter what you do, you cannot get to objects with no volume from objects with non-zero volume without getting small (i.e. without the reciprocal length diverging). This is not profound. On the other hand, that ratio is precisely what is important for certain physical/biolgical processes. So this quantity being bounded has consequences in those contexts.

This does not lead to a new theorem: as long as the set evolution is smooth, the f and Df are just a special case where f:\Bbb{R}^n\rightarrow\Bbb{R}^1 and even though actually computing everything from the geometric perspective can be interesting, the result stays the same.

in order to move into truly new territory, we need to consider alternative definitions, other measures of change, other types of spaces. An example might be the following:

Suppose that X is a metric space and f:X\rightarrow \Bbb{R}. Suppose that \gamma:\Bbb{R}\rightarrow X is continuous and is a geodesic in the sense that for any three points in \Bbb{R}, s_1 < s_2 < s_3, we have that \rho(\gamma(s_1),\gamma(s_3)) = \rho(\gamma(s_1),\gamma(s_2)) + \rho(\gamma(s_2),\gamma(s_3)).

If:

(1) for any two points in the metric space there is a gamma containing both points and

(2) for all such \gamma, g_{\gamma} \equiv f\circ\gamma is differentiable

(3) and \frac{|g_{\gamma}(s)|}{|f(\gamma(s))|} \leq \lambda

then, we have that

-\lambda \rho(x_1, x_0) \leq \ln\left(\frac{|f(x_1)|}{|f(x_0)|}\right) \leq \lambda \rho(x_1,x_0).                       (14)

And, again we get the same type of result for this case as we got in the Euclidean cases above.

(Exercise)  Prove Equation (14).

(Remark) We start with any metric space and consider curves \gamma:[a,b]\subset\Bbb{R}\rightarrow X for which

l(\gamma)\equiv\sup_{\{\{s_i\}_{i=1}^{n}| a = s_1 \leq s_2 \leq ... \leq s_n = b\}} \sum_{i=1}^{n-1} \rho(\gamma(s_{i}),\gamma(s_{i+1})) \leq \infty.

We call such curves rectifiable. We can always reparameterize such curves by arclength, so that \gamma(s) = \gamma(s(t)), t\in[0,l(\gamma)] and l([\gamma(s(d)),\gamma(s(c))] ) = d-c. We will assume that all curves have been reparameterized by arclength. Now define a new metric

\tilde{\rho}(x,y) = \inf_{\{\gamma | \gamma(a) = x\text{ and }\gamma(b) = y\}} l(\gamma).

You can check that this will not change the length of any curve. Define an upper gradient of f:X\rightarrow \Bbb{R} be any non-negative function \eta_f:X\rightarrow \Bbb{R} such that |f(y) - f(x)| \leq \int_{\gamma} \eta_f(\gamma(t)) dt.

Now, if \frac{|\eta_f(x)|}{|f(x)|} \leq \lambda, we again get the same sort of bounds that we got in equation (14) if we replace \rho with \tilde{\rho}. To read more about upper gradients, see Juha Heinonen’s book Lectures on Analysis in Metric Spaces.


While there are other directions we could push, what we have looked at so far demonstrates that productive exploration can start from almost anywhere. While we encounter no big surprises in this exploration, the exercise illuminates exactly why the result is what it is and this solidifies that understanding in our minds.

Generalization is not an empty exercise — it allows us to probe the exact meaning of a result. And that insight facilitates a more robust, more useful grasp of the result. While some get lost in their explorations and would benefit from touching down to the earth more often, it seems to me that in this day and age of no time to think, we most often suffer from the opposite problem of never taking the time to explore and observe and see where something can take us.

Finding Quietness

Rereading parts of Glynne Robinson Betts’ 1981 book, Writers in Residence, recalled simpler, deeper times, when finding places of quietness and taking time to think was part of the routine many people used in order to hear themselves and others. In fact, reading this again prompted me to expand the time I spend without Internet interruptions. Steps as simple as ignoring email for extended periods or as comprehensive as turning the computer off for the entire weekend, are emerging as a necessary part of reclaiming quietness and time to think.

There is nothing profound in these decisions to disconnect — whatever is profound happens as a result of taking that time to see and listen and think.

When I do slow down, every pause, every quietness, every moment taken to see, to listen, to think, rewards with a rich, living connectedness and depth that cannot be exhausted. The fabrics of the past and future join with the present, without seams, without a sense that I am working to recall, to see, to feel. Time opens up, I enter, to travel my own path, to sit or stand or walk … stopping time, finding passage to places beyond space and time.

To the strictly modern intellect, what I have just said probably seems like non-sense. Reason, based on easily observable facts, will find little irrefutable evidence that a skeptic would find compelling.

I therefore offer no argument to convince the skeptic. Instead I say, “Come and see”.

When we begin to let go of dogma, the regard of peers, and the comfort of the in-group, room for discovery is created. Launching into quiet spaces, where fear is replaced by stillness, a boundless infinity surprises. We find flow.  In this personal place without limits, I find an overflowing garden, teeming with life. On the living path, everything is illuminated.

Yet this is something I cannot really transmit. It is only something I can hint at in what I write, faintly, incompletely. The experience of discovery, of knowing, of traveling to those places that are here and beyond at the same time, cannot be captured in words.

To see, you must see though your own eyes. To see, you must choose to slow down, find quietness, and dwell there.

I believe that most – possibly all – human beings have, at one time or another, experienced immersion in flow and a connection to the place without limits. There is a resonance emerging from any such experience, no matter how brief, that enables those with that experience to hear each other.  But life often seems to conspire to crush those memories, to remove our ability to hear and see. In the quiet, we can be moved to remember, to see, to hear. In the quiet we remember the place without limits.

In writing something of what I see and hear, there is a chance that faint recollections will be stirred in those that read, in the way Writers in Residence stirred my memories, my recollections of a time when quietness and time to think was plentiful.

The thought of this possibility brings a subtle sense of connection, of silent conversation, with those as yet undiscovered friends. Lingering in rediscovered quietness, we move against the flow of noise and commotion and modern distraction, encouraging all those in our circle of influence to rediscover for themselves their own place without limits.