Let $T$ be a finite set of squarefree integers. (a) Show that there exists an integer polynomial $P(x)$ such that the set of squarefree numbers in the range of $P(n)$ across all $n \in \mathbb{Z}$ is exactly $T$. (b) Suppose that $T$ is allowed to be infinite. Is it still true that for all choices of $T$, such an integer polynomial $P(x)$ exists? Allen Wang
Problem
Source: ELMO Shortlist 2024/N5
Tags: Elmo, number theory
23.06.2024 07:22
For part a, let $P=Q^2 R$. Interpolate $T$ in some manner. Let $Q$ be such that $Q(x)=1$ if and only if $x$ is one of the $x$-coordinates in the list of interpolated points and $Q\ne -1$, and let $R(x)=x$ for precisely the $x$ that are $x$-coordinates in said list. It's easy to check that this is all possible. For part b, this solution is not mine, but: No because the set of all $T$ is uncountable but the set of all $P$ is countable so you can't have an injection. My idea is to instead let $T$ be the set of primes which I believe works but is a bit more involved. Another choice for $T$ is all the squarefree numbers except some finite set like $\{2\}$. This works by a density argument.
23.06.2024 07:51
Mine too is related to a density argument(Renyi's Theorem)
01.07.2024 22:32
a. Consider \[ P(x) = x \cdot \left ( 1 + 3 \cdot \prod_{t \in T} (x-t) \right )^2 \]Note that for any $s \in T$ one has $P(s) = s$ and for any $s \not \in T$ we have $P(s) = s \cdot A^2$ for some $A \not = \pm 1$ implying that $P(s)$ is not squarefree. Thus, the only squarefree elements in the range of $P$ are exactly the ones in $T$. b. No, let $S$ denote the set of squarefree positive integers and consider the mapping $\mathbb{Z}[x] \to \mathcal{P}(S)$ sending $P$ to the set of squarefree elements in the range of $P$. Note that this map is not surjective since $\mathbb{Z}[x]$ is countable while $ \mathcal{P}(S)$ is uncountable. Thus, there is a $T \in \mathcal{P}(S)$ which is not the squarefree range of any integer polynomial.