Given is a function f:R→R such that |f(x+y)−f(x)−f(y)|≤1. Prove the existence of an additive function g:R→R (that is g(x+y)=g(x)+g(y)) such that |f(x)−g(x)|≤1 for any x∈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 an=f(nx). Then we have s(am+n−am−an)≤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(an−nt)≤1 for all n (just use the fact that s(amn−man)≤m−1 and s(amn−nam)≤n−1 for all m,n -which are direct by induction- to find that s(man−nam)≤m+n; this shows that an/n is a Cauchy sequence and thus it converges to a number t; make m big in s(am/m−an/n)<1/m+1/n and you will find s(an−nt)≤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)≤1/n and the fact that s(f(x)−g(x))≤1 is also clear from s(f(nx)−nf(x))≤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
gn(x)=f(2nx)2n |gn+1(x)−gn(x)|≤1/2n+1 |gn+p(x)−gn(x)|≤1/2n Cauchy criterion is verify gn converge to g |gn(x+y)−gn(x)−gn(y)|≤1/2n 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 → 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 N→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→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)|≤1 for all x. Not hard to deduce that |f(2mx)2m−f(2nx)2n|≤12nfor all positive integers m>n and real number x. This implies that, for every real x, the sequence f(2nx)2n where n∈Z+ is a Cauchy sequence. So we can define g:R→R by g(x)=lim. 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?