Special Polynomials

This is not rigorous, but intended to start discussion.

Let $f(x) = x(x - r_{1})(x - r_{2})...(x - r_{n}) + 1024$

Then, if all the roots are distinct, we have $f(x) = 1024$ for $n$ values of $x$

We want to make $f(x) = -1024$ so let $x(x - r_{1})(x - r_{2})...(x - r_{n}) = -2048$ Note that $2048 = 2^{11}$ , we want to maximize the number of terms in a distinct product of factors that will equal 2048.

Clearly this is done by choosing the factors as $1,-1,2,-2,4,-4,32)$ (or any other combination of length 7). So our polynomial must have degree at most 7.

I am stuck on how to make my argument more complete and rigorous. Any hints or suggestions?

It is obvious that, for any integer $x$ and $y$ , $x - y$ divides $f(x) - f(y)$ ( $f(x) - f(y) = \sum_i a_i (x^i - y^i)$ , the $a_i$ are integer, and $x - y$ divides $x^i - y^i$ ). We will use this to show that 7 is an upper bound on $d$ , and in the process be led toward an $f$ that achieves that bound.

Suppose we have some maximum degree $f$ , and with it two integer sequences $a_0, a_1, \dots, a_{n - 1}$ and $b_0, b_1, \dots, b_{m - 1}$ such that $f(a_i) = 2^{10}$ and $f(b_i) = -2^{10}$ for all $i$ . Each $a_i$ is a unique integer, distinct from any other $a_j$ or $b_j$ , and vice versa. Using the property from before, we see that each difference $a_i - b_j$ is a divisor (positive or negative) of $2^{11}$ .

We will now derive a contradiction in the case that both sequences have more than one element.

Take two elements from each sequence and call them $a_0, a_1$ and $b_0, b_1$ . Then, considering the differences between the $a_i$ and $b_0$ , we get $b_0 = a_0 + 2^{x_0}$ and $b_0 = a_1 + 2^{x_1}$ (there are actually arbitrary signs in front of of the powers of two, but they don't break our argument, and are tedious write in TeX so I'm not going address them; we're also assuming here that $x_0 > x_1$ , and that's also a minor detail that doesn't affect the argument). This gives $a_1 - a_0 = 2^{x_1} (2^{x_0 - x_1} - 1)$ .

Doing the same with $b_1$ gives $a_1 - a_0 = 2^{y_1} (2^{y_0 - y_1} - 1)$ . But the uniqueness of factorizations combined with this implies that $x_0 = y_0$ and $y_0 = y_1$ , implying $b_0 = b_1$ , contradicting our assumptions about distinctness.

So in all cases, we will have either exactly one $a$ such that $f(a) = 2^{10}$ or one $b$ such that $f(b) = -2^{10}$ . Without loss of generality we consider the latter case.

So we have a sequence $a_0, a_1, \dots, a_{n - 1}$ and some $b$ . The maximum degree of the polynomial $f(x)$ is then $n$ . We know that the polynomial $f(x) - 2^{10}$ , has $n$ roots, so, in fact, $f$ must have degree $n$ , and $f(x) - 2^{10}$ is determined up to a constant, in turn determining $f(x)$ (up to that constant).

So $f(x) - 2^{10} = c (x - (b \pm 2^i))(x - (b \pm 2^j)) \cdots (x - (b \pm 2^k)$ . Plugging in $b$ we get that $2^{11} = \pm c X$ where $X$ is the product of a bunch of distinct positive and negative divisors of $2^{11}$ . For $c$ to be integer, $X$ needs to divide $2^{11}$ . So really we're looking to maximize the number of distinct divisors $2^{11}$ such that their product divides $2^{11}$ . But this is easy to do greedily! We can choose, for example, $-2^3, -2^2, -2^1, -2^0, 2^0, 2^1, 2^2$ , and this will give the maximum number, namely, 7.

|f(x)|=1024=2^10, Equation can be written as follows, f(x)=(x-a)(x-b)....-1024 or (x-a)(x-b)....+1024 were a,b,... are the 'd' integer roots of |f(x)|=1024. |f(x)|=1024=2^10=1 2 8 (-1) (-2) (-4) (-8), 1024 can only be written as multiple of up to 7 different integers. Substituting these sample values as a,b,... we get |f(x)|=1024 not only for these 7 values but also for 0 (|-1024|=1024).Thus a total of d+1 integer values this case is satisfied. Thus we can conclude that 7 is the top limit for the given case.

Consider the polynomial f(x)=(x-r 1)(x-r 2)...(x-r n)+1024. At any x=r n, the value of |f(x)| is 1024 (n solutions, degree n). For there to be more solutions, the value of f(x) must be -1024 at an integer value of x. Thus (x-r 1)(x-r 2)...(x-r n) must equal -2048, and each x-r i is an integer. The highest n for which this is possible is 7; the values of r_i are -4, -2, -1, 1, 2, 4, 32.

If we write that $f(x)-1024=g(x)$ , where $g(x)$ has degree $d$ , then it is possible (for a certain polynomial $g(x)$ ) that there are $d$ solutions to the equation we must satisfy.

However, this is not good enough. We need at least one extra solution, for $f(x)=-1024$ .

Then, we can say there must be at least one solution to $g(x) = -2048$ . Therefore, because $g(x)$ must have integer roots, we are looking for the maximum possible number of integers that multiply to $-2048$ , which will be our answer.

It turns out this maximum can be achieved by $(-8)(-4)(-1)(1)(2)(4)(8)$ , so our answer is $d=7$ .

No -8

Without loss of generality, let $f(x)=C(x-a_{1})(x-a_{2})⋅⋅⋅(x-a_{d})-1024$ . $|f(x)|=1024 if x=a_{1},a_{2}, \ldots, a_{d}$ . Another value of $x$ , say $x_{0}$ , gives $|f(x)|$ =1024 if $f(x_{0})=2048$ . This happens when $f(x_{0}=C(\pm 1)(\pm 2)(\pm 2^2)(2^3)$ , where $C=4$ . Adding another term of (-8) gives $C=\frac{1}{2}$ . Hence, the max value of d is $7$ .

Let f(x)=g(x)-1024 (+1024 is another approach to the solution). Let $a_{1}, a_2, \ldots, a_d$ be the roots of g such that $g(x)=C(x-a_{1})(x-a_{2}) \cdot \cdot \cdot (x-a_{d})$ . g vanishes if x is any root of f. If $g(x_{0})=2048$ for some $x_{0}$ , then $f(x_{0})=1024$ . This $x_{0}$ is the (d+1)th value of x such that $|f(x)|=1024$ . Since the polynomial has integer coefficients, Since $2048=2^{11}$ , each term of $g(x_{0}$ has to be a power of 2. The highest value of d occurs when $g(x_{0})=C(1)(-1)(2)(-2)(4)(-4)(8 [or -8])=2048$ where C=4 [or -4].) Had we let $g(x_{0})=C(1)(-1)(2)(-2)(4)(-4)(8)(-8)=2048$ , C becomes non-integral. Hence, the answer is $7$ .

I will try my best to achieve all the level 5 expectations for this solution, although I have a feeling that my solution will be very similar to but more complicated than the one already submitted. Also I am new to English writing so sorry if some sentences are hard to understand.

First of all, $\mid f(x)\mid$ =1024 is equivalent to $f(x)-1024=0$ and $f(x)=-1024$ .

To approach this problem, I tried constructing a polynomial that satisfies the problem. To do this, let's assume that $r_i$ ,where $i=1,2,...,d$ are distinct(repeated integers are counted once), are the integer solutions to the first equation. This polynomial can be written as: $f(x)=a(x-r_1)(x-r_2)...(x-r_d)+1024$ for some integer $a$ (note that $f(x)$ has integer coefficients). Now consider the second equation with this polynomial:

$f(x)=a(x-r_1)(x-r_2)...(x-r_d)+1024=-1024$

$a(x-r_1)(x-r_2)...(x-r_d)=-1024=-2^{11}$ ($)

Since there are already d solution for the first equation, so to fulfill the problem's condition that we want more than d solutions, we hope for at least one integer solution for ($).

Since the LHS of ($) are all integers, therefore they must all be factors of and multiply to get $-2^{11}$ . Since we want to maximize d, we have to find the largest number d such that $-2^{11}$ can be expressed as the product of d distinct integers(in doing so we'll set $a=1$ ). To answer this sub-question, one can easily come up with and check these 7 integers : $S=1,-1,2,-2,2^2,-2^2,2^5$ . This means that one of the $x-r_i$ corresponds with one of the factors. In other words, we have 7 equations: $x-r_i=p_i$ where $p_i$ is an element of $S$ and $i=1,2,...,7$ .

Since there are 7 equations with 8 variables, there's at most one solution for x if one $r_i$ is numerically defined. Therefore, we can find $r_1,r_2,...,r_7$ to make the second equation to have one integer solution(i.e. they are a permutation of $S$ and $x=0$ ). Hence this suggests that the answer should be $7$ .

At this point, I've summarized how I arrived at the solution. To ensure that 7 is indeed the largest integer, let's assume that $d\ge 8$ . Since it's shown above that we can only have most 7 distinct factors on the LHS of ($), there are $d-7\ge 1$ factors that will reoccur. Thus if we list out the 7 distinct equations again, by the same argument shown above, we will get at most 1 solution for x. This makes the total number of distinct solutions at most $7+1=8$ , which doesn't fulfill the requirements for $d\ge 8$ .