A tricky functional equation

(David here.) In this post, I go through a surprisingly tricky functional equation that appeared on the 2018 edition of the IMO Revenge, a contest where the contestants made problems for their trainers.

The problem

(IMO Revenge 2018/4) Find all functions $f:\mathbb{Q}\rightarrow\mathbb{R}$ such that $$f(x)^2-f(y)^2=f(x+y)\cdot f(x-y)$$ for all $x,y\in \mathbb{Q}$.

Fun fact - I was actually at that IMO as an observer! I had good memories of attempting the test, solving problem 3 and meeting the contestant-proposer (who later went on to propose an actual IMO Q3).

Initial observations

Clearly, $f(x) = x$ works. Furthermore, the equation is homogeneous in $f$ - if $f$ works then so must $cf$. It's also cheap to get that $f(0) = 0$ and $f(-x) = -f(x)$.

This was roughly where I ran out of cheap things to find - I didn't manage to get any more special values or any standard properties (like injectivity or surjectivity).

Some progress

When you get stuck on a functional equation (e.g. on $\mathbb Q$ or $\mathbb R$), it's often fruitful to try to solve for all integer inputs first. I'll spare you the trial and error and point at these: $$\begin{align*} f(x+1)^2 - f(x)^2 &= f(2x+1)f(1)\\ f(x)^2 - f(x-1)^2 &= f(2x-1)f(1)\\ f(x+1)^2 - f(x-1)^2 &= f(2x)f(2)\\ \end{align*}$$ Therefore, because the first two add up to the third, we get $$f(2x)f(2) = f(1)\cdot (f(2x+1) + f(2x-1))$$

So either:

• $f(1)=0$, which must mean that $f\equiv 0$, or
• $x_n=f(n)$ satisfies a linear recurrence of the form $$x_{n+2} = cx_{n+1} - x_n$$ where $c = f(2)/f(1)$.

This linear recurrence can be solved using standard methods: consider the characteristic equation $$x^2 - cx + 1 = 0$$

• When $c=2$, we get that $x_n = An+B$ for some $A,B$. But because $x_0=0$, we have that $x_n=An$.
• When $c=-2$, we get that $x_n = (-1)^n (An+B)$, which is really forced to be $x_n= (-1)^n\cdot A \cdot n$.
• When $c\neq 0$, the equation has two roots $\alpha, \alpha^{-1}$ satisfying $c=\alpha + \alpha^{-1}$, and the general form of the sequence is $$x_n = A\alpha^n + B \alpha^{-n}$$ for some constants $A,B$. But again, because $x_0=0$ we must have $B=-A$, so $x_n = A(\alpha^n-\alpha^{-n})$.
  • Notice that if $|c|>2$ then $\alpha$ is real, otherwise if $c<2$ then $\alpha$ is a complex number of norm 1.

So we're done, at least for the integers. (Secretly, we're done also for any integer multiple of some fixed real number.)

Generalizing to the rationals

You might expect this step to be very easy or very hard. It turns out to be a bit of both.

Suppose we have two rational numbers $p$ and $q$. Then, we end up with two sequences $$\begin{align*} 0, f(p), f(2p), f(3p), \ldots \\ 0, f(q), f(2q), f(3q), \ldots \end{align*}$$

each satisfying a linear recurrence, which we can solve for separately. However, nothing stops a nasty "mixture of solutions": could it happen that $f(pn) = An$ but $f(qn) = A(\alpha^n-\alpha^{-n})$?

It turns out that this is impossible - we can always find some common subdivision $s$ where both $p$ and $q$ are multiples of $s$. Then we note that each of those sequence are subsequences of $$0, f(s), f(2s), f(3s), \ldots$$ so we have to be able to generate both from a single "formula". In other words, any such sequence must be "consistent" with some underlying sequence!

It's useful to divide the solutions that we had for $\mathbb Z$ into three classes that cannot "mix" for this reason:

• ("hyperbolic") $f(x) = A(\alpha^x - \alpha^{-x})$ for real $\alpha > 1$
• ("parabolic") $f(x) = Ax$ or $f(x) = (-1)^n Ax$
• ("elliptic") $f(x) = A(\alpha^x - \alpha^{-x})$ for complex $\alpha$ of norm 1. If we write $\alpha = e^{2i \theta}$, this can also be written as $f(x) = A'\sin (\theta x)$.

These classes don't mix because the first grows exponentially, the second grows linearly and the last is bounded, so any subsequence you take must also be in the same "class" of growth rate.

The easy cases

The hyperbolic case turns out to be really easy - suppose $$f(ns) = A(\alpha_s^{n} - \alpha_s^{-n})$$ then it follows that $\alpha_p = \alpha_s^{p/s}$ and $\alpha_q=\alpha_s^{q/s}$ (because we're simply taking a subsequence going from multiples of $s$ to multiples of $p$). Therefore there is a single canonical value of $$\alpha = \alpha_x^{1/x}$$ for which $f(x)=A(\alpha^x - \alpha^{-x})$.

The parabolic case is also really easy - basically $f(x) = (-1)^nAx$ cannot happen. I'll omit the $A$ for rescaling, but imagine if you just considered every "half-step" of such a sequence: $$0, ?, -1, ?, 2, ?, -3, ? , \ldots$$ There are no solutions we found previously that fit this pattern, so this cannot happen. Hence the only "parabolic" solution is $f(x) = Ax$.

The elliptic case... remember that I said something about "very hard"?

Uh oh

In what follows we assume that we are firmly in the elliptic case.

You might be wondering what goes wrong if we just follow the argument for the hyperbolic case. The problem is that $\alpha\mapsto \alpha^n$ is injective, but $\sin \theta \mapsto \sin n\theta$ is certainly not (and so there is no unique single $\theta$ that we can infer).

At this point, I had a scary thought. Clearly, because the elliptic case solution is a solution, we have the identity $$\sin(X)^2 - \sin(Y)^2 = \sin(X+Y)\sin(X-Y),$$ but what if we had $f(x) = \sin(2\pi g(x))$ and simply had $g(x) + g(y)\equiv g(x+y) \pmod 1$? Then it would still follow that $$f(x+y) = \sin(2\pi\cdot g(x+y)) = \sin(2\pi\cdot (g(x) + g(y)))$$ so then such an $f$ satisfies the original function! But, consider this problem:

(USA TST 2015/4) Does there exist an additive $g: \mathbb Q/\mathbb Z \to \mathbb Q/\mathbb Z$ that's not linear mod 1? ($\mathbb Q/\mathbb Z$ denotes "$\mathbb Q$ mod 1".)

Cue some vertical space, in case you don't want the answer spoiled.

...

...

...

...

...

The answer is that such $g$ exists 👻.

Additive but nonlinear

How can such a thing be possible? We briefly mentioned that that over "$\mathbb R$ mod 1", there is no canonical halving operation, so one possible solution here (in the AoPS thread) is to construct a function by iteratively defining the half-step values in a self-consistent way that doesn't match any linear function.

But here's also a conceptual way. Let's think about the minimum amount of information that we'd need to specify such a function. The perhaps surprising claim is that we only need to specify $$f(1) = 0, f(1/2), f(1/3!), f(1/4!), ... \pmod 1$$ subject to some consistency conditions, like $$\frac{n!}{m!}f(1/n!)\equiv f(1/m!) \pmod 1, \quad \text{for any }n>m$$ and that's basically a well-defined function $f$, since any $f(q)$ is a multiple of some $1/n!$.

This "consistency" clause gets a little less mysterious if we focus less on the value on $f$ and more on the "implied coefficient" of the linear function $c_{n!} := n!f(1/n!)$ - then, for any $n>m$, we have $$c_{n!} \equiv c_{m!} \pmod {m!}$$

So really, what we want is a sequence of integers $c_n$ that satifies this strong "modular" relation. This leads to the following slick solution (also in the AoPS thread): consider $$c = 1 + 2! + 3! + 4! + \ldots$$ which makes no sense as a number, but considering $f(x) \equiv cx \pmod 1$ makes total sense over $\mathbb Q$ and yet cannot match any "regular" linear function. (This solution certainly makes my top 10 list for shock value.)

Diversion: really solving it

We can attempt the more ambitious:

(Harder?) Find all additive $g: \mathbb Q/\mathbb Z \to \mathbb Q/\mathbb Z$.

To really classify all the solutions, we resort to the one important trick when we deal with modulos in general. By the Chinese Remainder Theorem, to specify something mod $n$ (or mod $n!$), all you really have to do is to specify things modulo the prime powers that divide it. So in our case, we can have a consistent sequence of integers $$c_1 = 0, c_p, c_{p^2}, ...$$ satisfying $c_{p^n} \equiv c_{p^m} \pmod {p^m}$.

These things have a name: they are the $p$-adic integers $\mathbb Z_p$. Usually we write a $p$-adic integer (in $\mathbb Z_p$) as $$a_0 + a_1p + a_2p^2 + a_3p^3 + \cdots, \qquad a_i\in \mathbb Z$$ but really, it can also be thought of a sequence of partial sums that are consistent mod $p$, mod $p^2$ starting from the second term, mod $p^3$ starting from the third and so on.

In conclusion, to produce a $g$, we pick some element of $\mathbb Z_p$ for each prime $p$, which corresponds to picking $c_{p^k}$ for all $k\geq 1$. However, these are completely indepdent choices! So the set of $g$'s can be reasonably called $$\widehat{\mathbb Z} := \mathbb Z_2 \times \mathbb Z_3 \times \cdots.$$

Hello from the other side

I'll talk about some interesting connections to advanced math here, but feel free to skip this section.

Categorical limits. Let's rephrase how we defined the $p$-adic integers. I'll write the integers mod $n$ as $\mathbb Z/(n)$. Then we have the following diagram $$\mathbb Z / (p) \leftarrow \mathbb Z / (p^2) \leftarrow \mathbb Z/(p^3) \leftarrow \cdots$$ where each arrow describes an additive function - for example, the $\mathbb Z / (p) \leftarrow \mathbb Z / (p^2)$ refers to the function of "taking mod $p$" (that is, we are given something mod $p^2$, and we take mod $p$ to get something mod $p$).

There's a general idea (that works for any kind of diagram with arrows) that we can define a (direct) limit from this diagram by considering consistent choices of elements, exactly in the way that we had to do from this problem. We can therefore reasonably write something like $$\mathbb Z_p = \underleftarrow \lim\ \mathbb Z/(p^n).$$

You can see some parallels between this idea of a "limit" vs a limit that you'd meet in analysis - both are defined from sequence of things satisfying some kind of consistency relations between elements of the sequence.

Pontryagin duality. Let $\mathbb T$ be "$\mathbb R$ mod 1". We can talk about the so-called Pontryagin dual of $\mathbb Q/\mathbb Z$ - the set of all continuous group homomorphisms $\mathbb Q/\mathbb Z \to \mathbb T$. It turns out that this ends up being simply "all additive functions $\mathbb Q/\mathbb Z \to \mathbb Q/\mathbb Z$", which is the exact question that we solved, so we can reasonably say that:

$\widehat{\mathbb Z}$ is the Pontryagin dual of $\mathbb Q/\mathbb Z$.

In general, Pontryagin duality is an indication that we can do a kind of generalized Fourier analysis on the group, but I won't attempt to explain it further here.

Adele rings. If you google "adele ring", you'll get lots of pictures of Adele's 10-carat engagement ring. But for us, the adelic ring ends up being the "rational version" of $\mathbb Z \times \widehat{\mathbb Z}$. I unfortunately don't have any concrete understanding of what this is for - based on Wikipedia/ncatlab it seems to (also?) be related to a more general "Fourier analysis".

Back to the problem

We've looked at a class of pathological $f$'s, but we know nothing about whether this was the end of it. Luckily for us, we're kinda close!

There are two differences between our problem and the USA TST problem:

• instead of being just mod 1, we have some kind of equivalence condition based on the value of $\sin$. Let's write $x\sim y$ if $\sin(x) \sim \sin(y)$, and work mod $2\pi$.
• instead of the target being $\mathbb Q$, it can now be any real number.
• there's one additional step to make sure that the $A$'s are consistent

These turns out to be not too hard to work around, and I leave you to conclude that in the elliptic case, $f$ must be of the form $$f(x) = \sin (2\pi g(x))$$ where $g$ is additive mod 1.

Meta-epilogue

Over the years, there has been much chatter about how "olympiad problems" are not reflective of "real mathematics", and there is certainly some truth to that. However, if you've reached the top-tier of contest problem-solving, you'll certainly have bumped into some problems where the solution seems unsatisfying.

My advice is to hold on to those problems, because occasionally, like we've done with these two problems, you'll get to connect the dots. Sometimes, such problems show up years apart, but I think the mathematical adventure that comes out of it is well worth the wait, and you would have learned some things that people would consider "deep mathematics" by accident.