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∈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=Q2R. 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≠−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⋅(1+3⋅∏t∈T(x−t))2Note that for any s∈T one has P(s)=s and for any s∉T we have P(s)=s⋅A2 for some A≠±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 Z[x]→P(S) sending P to the set of squarefree elements in the range of P. Note that this map is not surjective since Z[x] is countable while P(S) is uncountable. Thus, there is a T∈P(S) which is not the squarefree range of any integer polynomial.