Again, this is a Problem From the Book

Say that \(f,g : \mathbb{N}\to \mathbb{N}\) satisfy the following properties:

  1. \(g\) is surjective
  2. \(2f(n)^2 = n^2 + g(n)^2\) for all \(n\in \mathbb{N}\)
  3. \(|f(n)-n|\le 2004 \sqrt{n}\) for all \(n\)

Theorem. \(f\) has infinitely many fixed points.

Proof. Let \(p_n\) be the primes in \((8)+3\), of which there are infinitely many. Note that \(2\) is not a quadratic residue modulo such a prime. So I guess property (2) kind of hints that we can do something with quadratic residue business. Anyways, this set of primes is going to be our angle.

Using (1) we find that there exists \(x_n\) with \(g(x_n) = p_n\). Taking (2) \(\mod p_n\) we find \[2f(x_n)^2 \equiv g(x_n)^2 \mod p_n.\] But \(2\) is not a quadratic resiude. So \(f(x_n)\) cannot be invertable. In other words, \(f(x_n) \equiv 0\mod p_n\) and thus \(g(x_n) \equiv 0 \mod p_n\). Then, there are integer sequences \(c_n,k_n\) so that

  • \(g(k_n p_n) = p_n\)
  • \(f(k_n p_n) = c_n p_n\)

Now we use (3) with some analysis-y tools. In particular, (3) can be re-expressed as: \[| \frac{f(x_n)}{x_n} - 1| \le \frac{2004}{\sqrt{x_n}}\] Hence, \[\lim_{n\to \infty} \frac{f(x_n)}{x_n} = 1.\] But recalling (2) \[2(c_np_n)^2 = (k_n p_n)^2 + p_n^2.\] Then, \[c_n = \sqrt{\frac{k_n^2 + 1}{2}}.\]

But then we have \[\lim_{n\to \infty} \frac{\sqrt{k_n^2+1}}{k_n} = \sqrt{2}\] From which we deduce: \[\lim_{n} k_n = 1.\] But it is an integer sequence, so this means that eventually all \(k_n\) are \(1\). Then \(f(p_n) = p_n\) for all sufficiently large \(n\), and we are done.