Given is a function $f:\mathbb{R}\rightarrow \mathbb{R}$ such that $|f(x+y)-f(x)-f(y)|\leq 1$. Prove the existence of an additive function $g:\mathbb{R}\rightarrow \mathbb{R}$ (that is $g(x+y)=g(x)+g(y)$) such that $|f(x)-g(x)|\leq 1$ for any $x \in \mathbb{R}$
Problem
Source: Turkey TST 2000
Tags: function, induction, algebra, inequalities, TST, additive function, functional equation
28.02.2005 22:57
I think we have discussed this one, but I am not sure. Anyway, what is clear is that it is far older than 2000 TST. I am sure we had this in one of our national olympiads in 11-th grade ( 1994 I think), but yet I think it is still far older than that.
28.02.2005 22:59
Thank you for clarifying some sources, but we are solving problems here...
28.02.2005 23:06
Myth, you should know that this kind of attitude does not impress me anymore for quite a long time.
28.02.2005 23:21
And since just you solve problems here, then ignore the following solution: Consider a fixed $n$ and the sequence $ a_n= f(nx)$. Then we have $ s(a_{m+n}-a_m-a_n)\leq 1$ for all m,n. Here $s(x)$ is the absolute value of x. I showed some time ago (in an problem from Austrain Polih competition) that for such a sequence there exists a number $t$ such that $ s(a_n-nt)\leq 1$ for all n (just use the fact that $ s(a_{mn}-ma_n)\leq m-1$ and $ s(a_{mn}-na_m)\leq n-1$ for all m,n -which are direct by induction- to find that $ s(ma_n-na_m)\leq m+n$; this shows that $ a_n/n$ is a Cauchy sequence and thus it converges to a number t; make m big in $ s(a_m/m-a_n/n)<1/m+1/n$ and you will find $ s(a_n-nt)\leq 1$). Thus, we can define $ g(x)$ as the limit of $ f(nx)/n$ and we aare done, since the aditivity is clear from $ s((f(n(x+y))-f(nx)-f(ny))/n)\leq 1/n$ and the fact that $ s(f(x)-g(x))\leq 1$ is also clear from $ s(f(nx)-nf(x))\leq n-1$ (which is true by induction). And, of course, obviously, I did not solve the problem.
28.02.2005 23:23
I said "we are..." and I am not John Nash...
28.02.2005 23:25
I know you said " we are", but how could I suggest the plural form in "just you"? Anyway, Myth, even if this does not make you feel good, you will have to support me on mathlinks. Too bad, I know.
28.02.2005 23:28
I really don't understand this phrase
28.02.2005 23:32
$g_n(x)=\frac{f(2^nx)}{2^n}$ $|g_{n+1}(x)-g_n(x)|\leq 1/2^{n+1}$ $|g_{n+p}(x)-g_n(x)|\leq 1/2^n$ Cauchy criterion is verify $g_n$ converge to $g$ $|g_n(x+y)-g_n(x)-g_n(y)|\leq 1/2^n$ tend n to oo $g(x+y)=g(x)+g(y)$
05.03.2005 02:38
harazi wrote: I think we have discussed this one, but I am not sure. Anyway, what is clear is that it is far older than 2000 TST. I am sure we had this in one of our national olympiads in 11-th grade ( 1994 I think), but yet I think it is still far older than that. I don't know about when it appeared in competitions, but this lemma must go back to Poincare's construction of the rotation number of a map from circle $\to$ circle (circa 1900), and (for quadratic forms) also Tate's construction of the canonical height on elliptic curves (circa 1950-60's). In connection with the latter it appears as an exercise in Serge Lang's large textbook on algebra. Also, Artin (Ph.D. supervisor of Tate and Lang) used the same inequality for functions $\mathbb{N} \to \mathbb{Z}$ as a construction of the real numbers, in one of his textbooks. (Considering two functions the same if their difference is bounded, the equivalence classes are those of $f(x) = [ax]$, with $a$ real.)
05.03.2005 02:41
Can you give precise references fleeting guest ? thx
05.03.2005 06:12
Moubinool wrote: Can you give precise references fleeting guest ? thx I will look for the references. As harazi mentioned, this genre of problem is quite ancient. Tate's idea to use it for constructing a canonical height was quite ingenious, though.
12.03.2005 22:11
Moubinool, the books I was seeking are not in the library, but I would suggest to search in the exercises of Serge Lang, Real Analysis, 2nd or (?) 3rd edition.
12.03.2005 23:00
thank you
13.03.2005 19:10
The problem was sent months ago.
14.03.2005 02:34
Omid Hatami wrote: The problem was sent months ago. I think he was asking about the history of this lemma and similar ones. Silverman's book on elliptic curves should have a reference to Tate's construction of the height, but I don't have access to it right now. The lemma for linear functions must be 100 years old, at least.
13.05.2005 00:40
Moubinool, I located the exercise in Serge Lang, Algebra, first edition (publ. 1965), end of the chapter "Structure of Bilinear Forms". It is attributed to Tate in the generality of $f:E \to F$ a map of complete normed vector spaces with $f(x+y)-f(x)-f(y)$ bounded, and the quadratic generalization is given as an exercise. I think that Tate had constructed the canonical height on elliptic curves well before 1965.
30.06.2018 20:22
WLOG assume $f(0)=0$. We have $|f(2x)-2f(x)|\leq 1$ for all $x$. Not hard to deduce that $$\Big| \frac{f(2^mx)}{2^m}-\frac{f(2^nx)}{2^n}\Big| \leq \frac{1}{2^n}$$for all positive integers $m>n$ and real number $x$. This implies that, for every real $x$, the sequence $\frac{f(2^nx)}{2^n}$ where $n\in \mathbb{Z}^+$ is a Cauchy sequence. So we can define $g:\mathbb{R}\to \mathbb{R}$ by $g(x)=\lim_{n\to \infty}{\frac{f(2^nx)}{2^n}}$. I'll leave the verification process to the diligent readers.
12.07.2020 09:23
This problem was given at the Bulgarian TST's for IMO 2020. There was additional assertion $g$ is unique, but it's easy. I commented it on my blog. The ideas used are different from those used in this thread.
12.07.2020 09:37
Could you post the other problems from the Bulgarian TST 2020, if you have them?