Perfect polynomials

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Perfect polynomials

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: 2023 Israel TST Test 5 P3

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

396 posts

#1 h Mar 23, 2023, 10:59 PM

Y by

Given a polynomial $P$ and a positive integer $k$ , we denote the $k$ -fold composition of $P$ by $P^{\circ k}$ . A polynomial $P$ with real coefficients is called perfect if for each integer $n$ there is a positive integer $k$ so that $P^{\circ k}(n)$ is an integer. Is it true that for each perfect polynomial $P$ , there exists a positive $m$ so that for each integer $n$ there is $0<k\leq m$ for which $P^{\circ k}(n)$ is an integer?

This post has been edited 1 time. Last edited by Phorphyrion, Apr 5, 2023, 1:48 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

303 posts

R8kt

#2 h Apr 7, 2023, 10:31 PM

Y by

Bumpbump

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

80 posts

#3 h Apr 12, 2023, 8:56 AM

Y by

The answer is negative.

Attachments:

Israel Tst 2023 Day 5 P3.pdf (247kb)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

21 posts

#4 h Apr 18, 2023, 11:10 PM

Y by

CahitArf wrote:

The answer is negative.

You'r polynomial doesn't satisfy the condition as $P(-1)=\frac{3}{2}$ and $\frac{3}{2}$ is a fixed point.
The general idea is correct though.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

80 posts

#5 h Apr 24, 2023, 8:47 AM

Y by

dendimon18 wrote:

CahitArf wrote:

The answer is negative.

You'r polynomial doesn't satisfy the condition as $P(-1)=\frac{3}{2}$ and $\frac{3}{2}$ is a fixed point.
The general idea is correct though.

Sorry for that , i totally forgot n can be negative ,too.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

43 posts

#6 h Apr 24, 2025, 10:41 PM

Y by

\textbf{Claim:} For all integers $n$ , there exists a positive integer $k$ such that the $k$ -fold composition of the function
$P(x) = \frac{4x^3 + 6x^2 + 10x + 3}{2}$ evaluated at $n$ is an integer.

P also satisfies this:
$P\left(\frac{n-1}{2}\right) = \frac{n(n^2 + 7)}{4} - \frac{1}{2}.$
Assume that $P(n) \notin \mathbb{Z}$ . Then $P(n)$ must be a half-integer, i.e., $P(n) = \frac{m}{2}$ for some odd integer $m$ .

Consider the sequence:
$2P(n) + 1,\quad 2P(P(n)) + 1,\quad 2P(P(P(n))) + 1, \ldots$
We claim that this sequence is entirely composed of integers. Furthermore, using the identity above, each term is mapped under the operation:
$m \mapsto (m^3 + 7m)/2.$ Hence, the sequence follows the recurrence:
$a_{i+1} = (a_i^3 + 7a_i)/2.$
We now show that this sequence eventually reaches an odd integer. Observe that if $m$ is even and nonzero, then
$v_2((m^3 + 7m)/2) = v_2(m) - 1,$ where $v_2(\cdot)$ denotes the 2-adic valuation. That is, each iteration reduces the 2-adic valuation by 1. Therefore, after exactly $v_2(2P(n) + 1)$ steps, the resulting term in the sequence will be odd. Since the input to $P$ at that point is an integer, and $P(\text{integer}) \in \mathbb{Z}$ for odd inputs, the composition $P^{\circ k}(n) \in \mathbb{Z}$ .

\bigskip

Two remaining concerns:
\begin{enumerate}
\item Ensure $2P(n) + 1 \neq 0$ .
\item Find $n$ such that the minimal $k$ required is unbounded.
\end{enumerate}

For the first concern, suppose $n$ is odd. Then from the identity:
$2P\left(\frac{n-1}{2}\right) + 1 = n(n^2 + 7),$ we note that $n(n^2 + 7) \neq 0$ for odd $n$ , hence $2P(n) + 1 \neq 0$ .

For the second concern, we want $v_2(2P(n) + 1)$ to be unbounded. Again using the identity:
$2P\left(\frac{n-1}{2}\right) + 1 = n(n^2 + 7),$ we seek odd $n$ such that $v_2(n(n^2 + 7))$ is arbitrarily large. It is known that $-7$ is a quadratic residue modulo any power of 2, so there exist such $n$ with arbitrarily large $v_2$

This post has been edited 2 times. Last edited by Davdav1232, Apr 25, 2025, 7:39 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a