IMO 2013 Q5

Suppose f:\mathbb Q^+ \to \mathbb R satisfies:

  1. f(x)f(y)\ge f(xy),\forall x,y\in \mathbb Q^+
  2. f(x+y)\ge f(x)+f(y),\forall x,y \in \mathbb Q^+
  3. \exists a \in \mathbb Q^+, a >1, f(a)=a.

Show that f(x)=x,\forall x \in \mathbb Q^+.

All right. This looks like a spin-off of Cauchy equation, which, when fixed on rational numbers, admits only trivial solutions, and the deduction is done by first doing it on integers and then extending it to rational numbers.

The codomain being \mathbb R hints that it is not advisable to iterate the function. We might want to perform preliminary investigation on it first.

Let the condition 1 be P(x,y), condition 2 be Q(x,y).

P(1,a) \implies f(1) f(a) \ge f(a), or, f(1)a \geq a . Thus, f(1) \geq 1, since a>0.

Q(n-1,1) \implies f(n)\ge f(n-1)+f(1)\ge f(n-1)+1. This can be used to inductively prove that f(n) \ge n,\forall n \in \mathbb N^+.

P(\frac mn , n)\implies f(\frac mn)f(n)\ge f(m)\ge m. Since f(n) >0, f(\frac mn)\ge \frac m{f(n)}>0, where m,n \in \mathbb N^+, and \frac mn \in \mathbb Q^+.

Let x_1 < x_2, x_1, x_2 \in \mathbb Q^+, Q(x_1, x_2-x_1)\implies f(x_2)\ge f(x_1)+f(x_2 - x_1) > f(x_1). Thus f is strictly monotically increasing.

That was the (trivial) preliminary investigation. We have obtained some upper bounds on the function’s values at integers, but further investigation seems beyond reach. This is because we cannot really find any upper bound on the function values f(x) that does not involve further reference to function values. 

(In fact, at this point, if the fixed point condition is ignored, f(x)=x^2 fits into all the above equations. I did not realise this when I attempted the problem, but it does, in hindsight, point at the necessity of utilising the fixed point condition.)

P(a, a^{k-1})\implies f(a^{k-1})a\ge f(a^k). This can be used inductively to prove that a^k \ge f(a^k).

YES! I has it! Upper bound! From now on we will just try to compare the function value with the powers of a in order to apply a sandwich squeezing type of idea to fix the f(x) because we were worried about f growing too rapidly.

Claim: \forall x \in \mathbb Q^+, f(x) \le x.

Fix \lambda \in \mathbb Q^+. We define l(x) = \left\lfloor \frac x \lambda \right\rfloor \lambda, and u(x)= \left\lceil \frac x \lambda \right\rceil \lambda. We thus have 0\le u(x)-x < \lambda, 0\le x-l(x) < \lambda.

(Here we are defining extensions of floor and ceiling functions.)

Let h:\mathbb N^+ \to \mathbb Q^+ be h(k)=a^{k+1} - a^k, and g:\mathbb N^+ \to \mathbb Q^+ be g(k) = l(a^{k+1})-u(a^k). Let k\to \infty, as since a>1, we have g(k) \to \infty. We will let k be large enough such that g(k) >0. Thus h(k) \ge g(k), from which \displaystyle \frac {f(h(k))}{f(g(k))}\ge 1.

\displaystyle  Q(h(k),a^k)\implies f(a^{k+1}-a^k) + f(a^k) \le f(a^{k+1}) \\  \implies f(h(k))\le f(a^{k+1})-f(a^k)\\  \le af(a^k)-f(a^k) =(a-1)f(a^k) \le (a-1)a^k \\  =h(k) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (*)

as f(a^{k+1}) \le af(a^k) and f(a^k)\le a^k

At this point we are still extending the property of a to obtain more points with f(x)\le x. But the next inequality involves the idea of approximating the “a polynomials” with “multiples” of \lambda. The approximation idea is why we defined that generalisation of floor and ceiling function in the first place: we cannot use a‘s polynomials to attack \lambda straightaway, we then do it approximately and then analysis will take care of the error.

On the other hand,

\displaystyle P(\frac{g(k)}{\lambda},\lambda)\implies \\  f(g(k))\ge f(\frac{l(a^{k+1})-u(a^k)}{\lambda})f(\lambda)\\  \ge \frac{g(k)}{\lambda}f(\lambda) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (**)

as \frac {l(a^{k+1})-u(a^k)}{\lambda} \in \mathbb N^+ (by the definition of l(x) and u(x), and our choice of k being large enough), and the fact that f(n)\ge n, \forall n\in \mathbb N^+.

Dividing (*) by (**) (as both inequalities have their both sides positive), we get

\displaystyle \frac {f(h(k))}{f(g(k))}\le \frac{\lambda}{f(\lambda)} \frac{h(k)}{g(k)} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (!).

The equation (!) is our main breakthrough. We will very soon let both sides tend to their limit as k\to \infty, thus the inequality will practically look like 1\le \frac {\lambda}{f(\lambda)}

Thus it only remains to show that both \lim _ {k \to \infty} \frac {h(k)}{g(k)}=1 and \lim _ {k\to \infty} \frac{f(h(k))}{f(g(k))}=1. The first one: 0\le h(k)-g(k) < 2\lambda, thus \frac { h(k)-g(k) }{g(k)}<\frac {2\lambda}{g(k)}. Now let g(k)\to \infty shows that \lim _{k \to \infty}\frac { h(k)-g(k) }{g(k)}=0.

If we consider the worse case scenario, h(k)-g(k)>0. But if the worse case does not happen, substituting h(k)-g(k) into the functional inequality is illegitimate.

If h(k)>g(k), Q(h(k)-g(k),g(k))\implies 0< f(h(k))-f(g(k)) \le f(h(k)-g(k)) < f(2\lambda). (The last inequality is true by the monotonicity of f !) If h(k)=g(k), f(h(k))-f(g(k))=0<2\lambda.

In either case, f(h(k))-f(g(k)) \in [0,2\lambda] is inevitable.

This is the approximation idea at work. We have successfully controlled the error uniformly. We only need to show that f(g(k)) \to \infty as k\to \infty to establish the claim.

But this is obvious since f(g(k))\ge \frac {g(k)}{\lambda} f(\lambda) (As \frac{g(k)}{\lambda}\in \mathbb N^+, and f(qn) \ge nf(q),\forall n\in \mathbb N^+ . And now g(k)>(a-1)a^k -2\lambda \to \infty as k\to \infty, our claim is proven.

We already have f(n)\ge n, \forall n\in \mathbb N^+, and thus we automatically have f(n)=n,\forall n\in \mathbb N^+.

P(\frac mn , n) \implies nf(\frac mn) \ge f(m)=m. Thus f(\frac mn ) \ge \frac mn. This combined with the claim, which requires f(\frac mn) \le \frac mn, gives f(\frac mn)=\frac mn ,\forall m,n\in \mathbb N^+.












Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s