A problem from the 2021 Moscow Math Olympiad went viral on Russian math channels. The author is Dmitry Krekov.

Problem. Does there exist a number A so that for any natural number n, there exists a square of a natural number that differs from the ceiling of A^{n} by 2?

Fun problem! (Solution provided for other visitors I’m sure you had no problem doing this.)

One way to produce algebraic integers P whose powers are quite close to integers is to observe that the sums of the powers of the conjugates of P are all integral. In particular, if all the other conjugates of P have absolute value less than one, then the closest integer to P^n (for large n) satisfies a linear recurrence relation. For example, if you take P = (sqrt(5)+1)/2 to be the golden ratio, and Q = (-sqrt(5)+1)/2 to be the conjugate of P, then

PQ = -1, |P| = 1.61803… |Q| = 0.61803…

And now the sequence P^n + Q^n consists entirely of integers: 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, and so on. These are the Lucas numbers L_n. Now let’s see what happens if we square both sides. We get

But as observed, PQ = -1 so P^n Q^n = (-1)^n, and Q^(2n) is a (positive!) real number less than one. Hence

P^(2n) + 2 (-1)^n + real number less than one = (L_n)^2.

But that means the ceiling of P^(2n) differs from (L_n)^2 by 2 or -2, and so you can take A = P^2 in the problem. (If you want the sign of the “2” to be the same, you can take A = P^4 instead.)

This argument works equally well if P is any unit in a real quadratic number field, and A=P^2. So you could also take A = (1 + sqrt(2))^2 = (3+2 sqrt(2)) or (2 + sqrt(3))^2 = (7 + 2 sqrt(3)), etc.

“the sums of the powers of the conjugates of P are all integral” Whoa — plural overload! Which conjugates? which powers? What are the terms you’re summing? and for each sum what is the set of terms for that sum?

I think I know a bit about algebraic conjugates but I didn’t understand what I found. How do you find the algebraic conjugates of a number? It seemed to me that the process was defined, not on a number itself, but only on the representation of the number in a certain form, and it gave you another representation.

## Carl Feynman:

No.

4 April 2021, 6:35 pm## Matthew Rose:

Yes.

19 April 2021, 5:38 am## TRidgway:

Arm wrestle!

23 April 2021, 3:45 pm## Iseng Belajar:

Someone please provide the proof?

29 April 2021, 5:32 am## rosie:

A construction like that of Mills’s constant should do it.

16 May 2021, 3:32 am## passerby:

Fun problem! (Solution provided for other visitors I’m sure you had no problem doing this.)

One way to produce algebraic integers P whose powers are quite close to integers is to observe that the sums of the powers of the conjugates of P are all integral. In particular, if all the other conjugates of P have absolute value less than one, then the closest integer to P^n (for large n) satisfies a linear recurrence relation. For example, if you take P = (sqrt(5)+1)/2 to be the golden ratio, and Q = (-sqrt(5)+1)/2 to be the conjugate of P, then

PQ = -1, |P| = 1.61803… |Q| = 0.61803…

And now the sequence P^n + Q^n consists entirely of integers: 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, and so on. These are the Lucas numbers L_n. Now let’s see what happens if we square both sides. We get

P^(2n) + 2 P^n Q^n + Q^(2n) = 1,9,16,49,… = (L_n)^2.

But as observed, PQ = -1 so P^n Q^n = (-1)^n, and Q^(2n) is a (positive!) real number less than one. Hence

P^(2n) + 2 (-1)^n + real number less than one = (L_n)^2.

But that means the ceiling of P^(2n) differs from (L_n)^2 by 2 or -2, and so you can take A = P^2 in the problem. (If you want the sign of the “2” to be the same, you can take A = P^4 instead.)

This argument works equally well if P is any unit in a real quadratic number field, and A=P^2. So you could also take A = (1 + sqrt(2))^2 = (3+2 sqrt(2)) or (2 + sqrt(3))^2 = (7 + 2 sqrt(3)), etc.

27 May 2021, 11:03 am## carl feynman:

You are right and I am wrong! Good puzzle.

27 June 2021, 10:09 am## rosie:

“the sums of the powers of the conjugates of P are all integral” Whoa — plural overload! Which conjugates? which powers? What are the terms you’re summing? and for each sum what is the set of terms for that sum?

I think I know a bit about algebraic conjugates but I didn’t understand what I found. How do you find the algebraic conjugates of a number? It seemed to me that the process was defined, not on a number itself, but only on the representation of the number in a certain form, and it gave you another representation.

22 July 2021, 9:28 am## Tanya Khovanova's Math Blog » Blog Archive » A Splashy Math Problem Solution:

[…] recently wrote a post, A Splashy Math Problem, with an interesting problem from the 2021 Moscow Math […]

16 December 2021, 11:07 am