digitális matek

When the hangman is being hanged

In my earlier posts I wrote about equations which play a central role in mathematical research and applications.
functions-and-hangman

Roughly speaking, an equation is of the form f(x,y,z,\dots)=g(x,y,z,\dots) where f,g are given functions defined on some set, and the letters x,y,z,\dots, represent the „unknowns” — the quantities which we don’t know, which are hidden in the equation. „Solving” the equation means that we can list, or describe in some way all those possible values a,b,c,\dots of these unknowns from the joint domain of the two functions f,g for which the given equation holds true if we replace x by the value a, y by the value b, z by the value c, etc. It is really hopeless to try to define equations of the most general type: it is better to define some special types, like quadratic equations, ordinary differential equations, linear diophantine equations in two variables, and so on. A relatively simple case is the equation f(x)=0 where f is a given function on some set, and its values belong to a certain set of numbers which includes 0. In this case we say that we are looking for the zeros of f. If, for instance, f is a quadratic polynomial on the real numbers, then we have a well-known formula which produces all zeros — by the way, in this case we know that „all” means „at most two”. But what if in the equation f(x)=0 we don’t know f, the function itself, but we know that the equation holds for each x from its domain? What if the hangman is being hanged? Well, in this trivial case what is the problem? We are looking for a function f which takes the 0 value at each point of its domain. What is this function? Of course, this is the identically zero function. Let’s make it a bit more complicated. Find a function f on the positive reals which maps \sqrt{x} to x for each positive x. This problem can be formulated in the following way: f(\sqrt{x})=x for each x>0. To give the answer observe that every positive real number y is the square root of some x>0: y=\sqrt{x} if and only if y^2=x. Substitution into the above equation we have f(y)=f(\sqrt{x})=x=y^2. So, the only function satisfying the required property is the function y\mapsto y^2, the squaring function. We solved our problem, we described all solutions of the given equation, which is called a functional equation to emphasize that the function is the unknown.

The theory of functional equations is an amazing field of mathematics. Of course, it is very difficult, maybe impossible to give a general definition for the concept we call a functional equation: again, it is better to specify different types of functional equations, like difference equations, differential equations, etc. For instance, an important classification depends on the number of variables in the equation. In our previous equations we had a single variable, denoted by x, but we can consider equations like f(x \cdot y)= f(x+y), f(x_1+x_2+\dots+x_n)=1, etc., where we usually suppose that the variables x,y,x_1,x_2,\dots,x_n may take any value of the domain of the unknown function f. Clearly, we may allow more than one unknown functions in the equation, and all those unknown functions may have more than one variables, and so on. For instance, the functional equation f(x)+f(-x)=0 on the reals characterizes exactly those functions which we call odd functions: the ones with graph symmetric with respect to the origin in the plane. Similarly, the equation f(x)-f(-x)=0 describes those functions whose graph is symmetric with respect to the y-axis in the plane; they are called even functions. These are very simple functional equations in a single variable. Above I mentioned the functional equation f(x\cdot y)=f(x+y) — this is a functional equation in two variables.

Before we try to solve this equation we must specify the expected domain of the unknown function f. Let’s start with the set of all real numbers \R: in this case we have a great degree of freedom, as we can substitute arbitrary real values for x and y in the equation. For instance, substituting y=0 we have f(0)=f(x), that is, f is the constant function taking the value f(0) at each point. Conversely, it is obvious that any constant function satisfies our equation. We express this result by saying that the general solution of our equation on the reals is provided by the family of all constant functions.

We may have the feeling that here the existence of the 0 plays a crucial role: let’s try to solve our equation on the positive reals. There is no 0, we cannot substitute it. It is clear, that on a smaller set we might expect more solutions — indeed, a larger domain means more conditions on the unknown function, which are more difficult to satisfy. So, what to do on the positive reals? Let x>0 be arbitrary and y=\frac{1}{x}. Then we have

    \[f(1)=f(x\cdot \frac{1}{x})=f(x+\frac{1}{x}),\]

and it is easy to see that every real number u\geq 2 can be written in the form u=x+\frac{1}{x} with some x>0. Indeed, for x we have the quadratic equation

    \[x^2-u x+1=0,\]

which implies x=\frac{u\pm \sqrt{u^2-4}}{2}, and both these values are positive. It follows that f(u)=f(1) whenever u\geq 2 — our function is constant on the right of 2. If 1\leq u, then we take x=2 u\geq 2 and with y=\frac{1}{2} we have

    \[f(u)=f(x\cdot \frac{1}{2})=f(x+\frac{1}{2})=f(1),\]

as x+\frac{1}{2}\geq 2. Now we have that our function is constant on the right of 1. In the next step we take a u with \frac{1}{2}\leq u, then with the choice x=2 u\geq 1 and y=\frac{1}{2} we have

    \[f(u)=f(x\cdot \frac{1}{2})=f(x+\frac{1}{2})=f(1),\]

as x+\frac{1}{2}\geq 1. Continuing this process we see that for every positive u we have f(u)=f(1), that is, our function is constant. Since every constant function obviously satisfies our original equation we can draw the conclusion again: the general solution on the positive reals is represented by all constant functions.

Cool, right? You can see that the point is to substitute different values for x and y in a smart way so that we get more and more information about f. And we have two „free” variables — fixing one of them we still have another one which can be arbitrary. Yes, but it would be nice to see a functional equation which has non-constant solutions. A famous equation follows: one of the so-called Cauchy equations, the functional equation

    \[f(x+y)=f(x)+f(y),\]

where we suppose that f is defined on the whole real line and it takes real values. We see immediately that every function of the form f(x)=c\cdot x is a solution with an arbitrary real number c — these are the so-called {\it linear functions}. A reasonable question is if there are any other solutions? Augustin Louis Cauchy was the great French mathematician who systematically studied this functional equation and he proved that if we add certain further conditions on f, then f must be a linear function. But he was unable to prove linearity without additional assumptions. Here we show that, for instance, if we assume that f is increasing, or decreasing on any open interval, then it must be linear.

First we derive some basic consequences of the equation without any additional condition on f. Clearly, f(0)=0, which follows from the substitution x=y=0. Then the substitution y=-x gives f(-x)=-f(x) for each real x, that is, f is an odd function. Next, applying induction we obtain that

    \[f(x_1+x_2+\dots+x_n)=f(x_1)+f(x_2)+\dots+f(x_n)\]

for any positive integer n. In particular, f(n\cdot x)=n f(x) holds whenever x is arbitrary and n is any integer — as a consequence of the odd property. Now we have

    \[f(x)=f\bigl(n\cdot \frac{x}{n}\bigr)=n f\bigl(\frac{x}{n}\bigr),\]

which implies f\bigl(\frac{x}{n}\bigr)=\frac{1}{n} f(x). Put here m\cdot x for x with some integer m, then we have

    \[f\bigl(\frac{m}{n}\cdot x\bigr)=f\bigl(\frac{m\cdot x}{n}\bigr)=m f\bigl(\frac{x}{n}\bigr)=\frac{m}{n} f(x),\]

that means, rational numbers can be factored out of f: f(r\cdot x)=r f(x), whenever x is a real number and r is a rational number. So, putting x=1 here we have that, in fact, f is linear on the rational numbers:

    \[f(r)=r\cdot f(1),\enskip\text{or}\enskip f(r)=c\cdot r\]

with c=f(1), for each rational number r. Unfortunately, „most” real numbers are irrational, and our equation does not say too much about the function values at irrational numbers. That’s the point when algebra is not enough anymore: we have to add some analysis to go on.
\vskip.2cm

Now we assume that f is, say, increasing on the interval (a,b). The decreasing case can be treated in a similar manner — or just replace f by (-f), which clearly satisfies the same equation. Let x be any real number — we take an increasing sequence p_n and a decreasing sequence q_n of rational numbers such that

    \[x-\frac{b-a}{2}<p_n\leq x\leq q_n<x+\frac{b-a}{2},\]

and q_n-p_n<\frac{1}{n}; this is possible, as every nonempty open interval on the real line includes rational numbers. Subtracting x-\frac{a+b}{2} from each sides of this chain of inequalities we obtain

    \[a< p_n+\frac{a+b}{2}-x< \frac{a+b}{2}< q_n+\frac{a+b}{2}-x<b,\]

hence we can use the increasing property of f on the interval (a,b), together with the functional equation:

    \[f(p_n)+f\bigl(\frac{a+b}{2}\bigr)-f(x)<f\bigl(\frac{a+b}{2}\bigr)<f(q_n)+f\bigl(\frac{a+b}{2}\bigr)-f(x),\]

or

    \[f(p_n)<f(x)<f(q_n).\]

Using the linearity of f on the rationals we have

    p_n f(1)<f(x) <span class="ql-right-eqno">   </span><span class="ql-left-eqno">   </span><img src="http://mymath4u.com/wp-content/ql-cache/quicklatex.com-50b842406876085bf89474793f4d8522_l3.png" height="18" width="379" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[x f(1)-f(x)\leq q_n f(1)-p_n f(1)=(q_n-p_n) f(1),\]" title="Rendered by QuickLaTeX.com"/> and also <span class="ql-right-eqno">   </span><span class="ql-left-eqno">   </span><img src="http://mymath4u.com/wp-content/ql-cache/quicklatex.com-8aa78458a1a2b690d00c91ee7b3c1982_l3.png" height="18" width="379" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[f(x)-x f(1)\leq q_n f(1)-p_n f(1)=(q_n-p_n) f(1),\]" title="Rendered by QuickLaTeX.com"/> which gives

|f(x)-x f(1)|\leq (q_n-p_n) f(1)\leq\frac{1}{n} f(1)for each positive integern. It followsf(x)= f(1)\cdot xfor each real numberx, that is,fis linear.  Using a similar argument we can prove that iffis bounded above or below on some open interval, thenfmust be linear. These types of statements make the question more and more exciting: is there any nonlinear function satisfying Cauchy's functional equation? If so, then that function must be very strange: it cannot be increasing, nor decreasing, nor bounded above, nor bounded below on any small open interval! How does the graph of such a function look like? Does there exist such a pathological function? An answer to this question was given in 1905, 48 years after Cauchy's death, by Georg Hamel, who proved the unbelievable: yes, there are such functions, in fact, there are "much more" pathological solutions of Cauchy's equation than linear.  This extraordinary behavior of some functional equations makes this area delicate and amazing. The simple algebraic condition, that the function maps the sum of any two numbers onto the sum of their images has unexpected consequences: this can happen only with the two extremes -- the function is either very nice, the next simplest besides constants, or it is the worst kind among all functions. These wild monsters, however, can be calmed down, can be "domesticated" by some mild regularity conditions, like monotonicity, boundedness, etc.  And there is another unusual phenomena in the field of functional equations. Jan Vilém Pexider, Czech mathematician had the funny idea to replace the three occurrences off

    in Cauchy's equation by three different functions obtaining the following functional equation <span class="ql-right-eqno">   </span><span class="ql-left-eqno">   </span><img src="http://mymath4u.com/wp-content/ql-cache/quicklatex.com-3d165866d25da8f9d840fc7888fc7966_l3.png" height="18" width="181" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[f(x+y)=g(x)+h(y),\]" title="Rendered by QuickLaTeX.com"/> where again, the domain of the three unknown functions can be the real line and they take real values. This equation is called the Pexider equation. You may think that now we'll have a very large set of solutions, as our "degree of freedom" has essentially increased: we have just a single equation with three unknown quantities. Nevertheless, the situation is quite simple: we can substitute

y=0to getf(x)=g(x)+h(0), andx=0to getf(y)=g(0)+h(y). In other words, the functionsgandhdiffer fromf

    by a constant only: Pexider's equation can be rewritten in the form <span class="ql-right-eqno">   </span><span class="ql-left-eqno">   </span><img src="http://mymath4u.com/wp-content/ql-cache/quicklatex.com-f18fda40b4fc53fec661f8e3da7fb46e_l3.png" height="18" width="215" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[f(x+y)=f(x)+f(y)+k,\]" title="Rendered by QuickLaTeX.com"/> where

k=-h(0)-g(0)

    , a constant. From this equation we immediately obtain <span class="ql-right-eqno">   </span><span class="ql-left-eqno">   </span><img src="http://mymath4u.com/wp-content/ql-cache/quicklatex.com-e7613029af10a0e1386ebdbd74cc7b2d_l3.png" height="18" width="277" class="ql-img-displayed-equation quicklatex-auto-format" alt="\[f(x+y)-k=f(x)-k +f(y)-k,\]" title="Rendered by QuickLaTeX.com"/> that is, the new function

x\mapsto f(x)-ksatisfies Cauchy's equation, andg,hcan be obtained fromfby adding a constant. All in all, Pexider's equation does not bring anything new, it can be reduced to Cauchy's equation.  On the other hand, we should not forget that in this reduction the0played a crucial role: if0$ is not in the domain of the unknown functions, then the above method does not work. In fact, in the theory of functional equations, it is a common feature that changing the domain can make serious troubles. A functional equation, which can be treated nicely on some domain, may be very difficult, or even impossible to solve on another set. So, the field is open, your creativity can be tested on different types of functional equations. Don’t hesitate, go to the Problems and Solutions!