SHORTLISTED PROBLEMS FOR THE 62nd NMO

Let us try to find all functions $f: \mathbb{Z} \to \mathbb{N}$ such that:

i) $f(m+n) = f(m) + f(n) + 2mn$ for all $m, n \in \mathbb{Z}$;
ii) $f(f(x)) - f(1)$ is a perfect square for all $x \in \mathbb{Z}$.

Let us first solve the functional equation (i).

Let $P(m, n)$ denote the assertion $f(m+n) = f(m) + f(n) + 2mn$.

Let us try to find the general form of $f$.

Let us try $f(x) = ax^2 + bx + c$ for some $a, b, c \in \mathbb{R}$.

Plug into (i):

$f(m+n) = a(m+n)^2 + b(m+n) + c$

$f(m) + f(n) + 2mn = a m^2 + b m + c + a n^2 + b n + c + 2 m n$

$= a(m^2 + n^2) + b(m + n) + 2c + 2 m n$

But $a(m+n)^2 = a(m^2 + 2 m n + n^2) = a m^2 + 2 a m n + a n^2$

So:

$f(m+n) = a m^2 + 2 a m n + a n^2 + b m + b n + c$

Set equal to $a(m^2 + n^2) + b(m + n) + 2c + 2 m n$:

$a m^2 + 2 a m n + a n^2 + b m + b n + c = a m^2 + a n^2 + b m + b n + 2c + 2 m n$

$2 a m n + c = 2 m n + 2c$

$2 a m n + c = 2 m n + 2c$

$2 a m n - 2 m n = 2c - c$

$2(a-1) m n = c$

But this must hold for all $m, n$, so $a = 1$ and $c = 0$.

Therefore, $f(x) = x^2 + b x$ for some $b \in \mathbb{R}$.

But $f: \mathbb{Z} \to \mathbb{N}$, so $f(x) = x^2 + b x$ must be a positive integer for all $x \in \mathbb{Z}$.

Let us check for which $b$ this is possible.

For $x = 0$, $f(0) = 0$.

But $\mathbb{N}$ usually means positive integers, i.e., $\mathbb{N} = \{1, 2, 3, \ldots\}$, so $f(0) = 0$ is not in $\mathbb{N}$.

Therefore, there is no such function unless $\mathbb{N}$ is defined to include $0$ (some conventions do this, but usually $\mathbb{N}$ is positive integers).

Alternatively, perhaps the problem means $\mathbb{N}_0 = \{0, 1, 2, \ldots\}$.

Let us proceed anyway.

For $x = -b$, $f(-b) = (-b)^2 + b(-b) = b^2 - b^2 = 0$.

So $f(-b) = 0$.

Thus, unless $b = 0$, $f(x)$ takes the value $0$ for some $x$.

If $b = 0$, $f(x) = x^2$, which is always non-negative, and $f(0) = 0$.

So $f(x) = x^2$ is a solution if $0 \in \mathbb{N}$.

If $\mathbb{N}$ is positive integers, then there is no solution.

Let us check the second condition for $f(x) = x^2$:

$f(f(x)) - f(1) = f(x^2) - 1^2 = (x^2)^2 - 1 = x^4 - 1$

Is $x^4 - 1$ always a perfect square?

For $x = 0$, $0^4 - 1 = -1$, not a perfect square.

For $x = 1$, $1^4 - 1 = 0$, which is a perfect square.

For $x = 2$, $16 - 1 = 15$, not a perfect square.

So $f(x) = x^2$ does not satisfy the second condition.

Let us try $b = 1$, $f(x) = x^2 + x$.

Then $f(0) = 0$, $f(-1) = 1 - 1 = 0$.

So again, $f(x)$ takes value $0$.

Let us try $b = 2$, $f(x) = x^2 + 2x$.

Then $f(0) = 0$, $f(-2) = 4 - 4 = 0$.

So for any integer $b$, $f(x)$ takes value $0$ at $x = 0$ or $x = -b$.

Therefore, unless $0 \in \mathbb{N}$, there is no solution.

If $0 \in \mathbb{N}$, let us check the second condition for $f(x) = x^2 + b x$.

$f(f(x)) - f(1) = f(x^2 + b x) - (1^2 + b \cdot 1) = (x^2 + b x)^2 + b(x^2 + b x) - (1 + b)$

$= (x^4 + 2 b x^3 + b^2 x^2) + b x^2 + b^2 x - (1 + b)$

$= x^4 + 2 b x^3 + (b^2 + b) x^2 + b^2 x - (1 + b)$

Is this always a perfect square for all $x$?

For $x = 0$, $f(f(0)) - f(1) = f(0) - f(1) = 0 - (1 + b) = -(1 + b)$, which is negative unless $b = -1$.

But for $b = -1$, $f(x) = x^2 - x$, $f(0) = 0$, $f(1) = 1 - 1 = 0$, $f(f(0)) - f(1) = 0 - 0 = 0$, which is a perfect square.

Check $f(f(2)) - f(1)$:

$f(2) = 4 - 2 = 2$

$f(f(2)) = f(2) = 2$

$f(1) = 0$

So $f(f(2)) - f(1) = 2 - 0 = 2$, not a perfect square.

So $b = -1$ does not work.

Therefore, there is no function $f: \mathbb{Z} \to \mathbb{N}$ of the form $x^2 + b x$ that satisfies both conditions.

Therefore, there is no function $f: \mathbb{Z} \to \mathbb{N}$ satisfying both conditions, unless $\mathbb{N}$ includes $0$ and $f(1) = 1$.

But in all cases, the second condition fails for some $x$.

Therefore, the answer is:

There is no function $f: \mathbb{Z} \to \mathbb{N}$ satisfying both conditions.