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.

Thank you for clarifying some sources, but we are solving problems here...

Myth, you should know that this kind of attitude does not impress me anymore for quite a long time.

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.

I said "we are..." and I am not John Nash...

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.

I really don't understand this phrase

$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)$

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.)

Can you give precise references fleeting guest ? thx

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.

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.

thank you

The problem was sent months ago.

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.

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.

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.

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.

Could you post the other problems from the Bulgarian TST 2020, if you have them?