2

Let $1<t<2$ be a real number. Prove that for all sufficiently large positive integers $d$, there is a monic polynomial $P(x)$ of degree $d$, such that all of its coefficients are either $+1$ or $-1$ and $$\left|P(t)-2019\right| <1.$$

This problem is from https://artofproblemsolving.com/community/c6h1862283p12600279

I think the dgrozev methods have somewrong,becuase he only prove $|P(t)-2019|\le 1$ ,can you agree with me

mathworker21
  • 34,399
math110
  • 93,304

3 Answers3

2

I mean, dgrozev specifically points out that he proves $|P(t)-2019| \le 1$ and that an extension needs to be made to $|P(t)-2019| < 1$. He said he can provide that extension, but didn't. So I don't see how you can call his methods "wrong"; he just didn't provide the complete proof.

In any event, I have a proof that shows that at least $50\%$ of all large $d$ have such a polynomial. Clearly, from dgrozev's proof, there is only an issue if there are some $\epsilon_0,\epsilon_1,\dots,\epsilon_d \in \{\pm 1\}$ with $\epsilon_dt^d+\dots+\epsilon_1 t+\epsilon_0 = 2018$. Now, I claim that if there are such $\epsilon_0,\dots,\epsilon_d$, then there won't be $\epsilon_0',\dots,\epsilon_{d+1}'$ with $\epsilon_{d+1}'t^{d+1}+\dots+\epsilon_1't+\epsilon_0' = 2018$.

To show this claim, it suffices to show that two polynomials with only $\pm 1$ coefficients that are one degree apart have no common roots. It of course suffices to show that any two such polynomials have gcd $1$ over $\mathbb{Q}[X]$, which is equivalent to showing any two such polynomials share no common factor in $\mathbb{Q}[X]$, which essentially by Gauss's lemma (or its proof) is equivalent to two such polynomials sharing no common factor in $\mathbb{Z}[X]$. So suppose for the sake of contradiction that they did share a common factor in $\mathbb{Z}[X]$. This common factor must, of course, be monic or have first coefficient $-1$. Then, reducing everything mod $2$, $x^{d+1}+\dots+x+1$ and $x^d+\dots+x+1$ would share a nontrivial common factor in $\mathbb{F}_2[X]$, but they don't since $x^{d+1}+\dots+x+1-x(x^d+\dots+x+1) = 1$.

mathworker21
  • 34,399
  • Please could you clarify a point in your interesting proof. The two polynomials you give at the end of para 2 have a common value but not necessarily a common root so how did you then proceed? –  Aug 27 '19 at 06:18
  • @S.Dolan you're right. surprised I didn't notice that (I was playing around with $\pm 1$ polynomials a lot). however, it's easily fixable. all that my last paragraph used was that the two polynomials reduced to $x^{d+1}+\dots+x+1$ and $x^d+\dots+x+1$, so just apply that paragraph to $\epsilon_dt^d+\dots+\epsilon_1 t+[\epsilon_0-2018]$ and $\epsilon_{d+1}'t^{d+1}+\dots+\epsilon_1't+[\epsilon_0'-2018]$ (lucky for me, $2018$ is even :) ). – mathworker21 Aug 27 '19 at 13:48
  • Thanks. I assumed that's what you were intending but I wanted to check that I wasn't missing something. Like you, I've played around with these polynomials and I had convincedmyself that there is a problem with dgrozev's statement about an extension. (See the 'answer' below.) –  Aug 28 '19 at 01:14
1

The method used by dgrozev cannot be used to prove the strict inequality because there is nothing in the method to distinguish 2019 from any other integer and yet and yet it's not the case that the result is true for all integers.

Counterexample.

Let $t$ be the golden ratio and let $d$ be 2 modulo 3. Then |P(t)|is either 0 or at least 2.

(To prove this result about |P(t)| first show that it is true for $d=2$ and then use the inequality $|2t^3-(1+t+t^2)|\ge 2$ to extend the result.)

  • This is the better answer, though I can't figure out the proof of $|P(t)-1| \ge 1$. Very nice +1. One very small nitpick though. You should instead say "and yet it's not the case that the result is true for all integers", to avoid ambiguity. – mathworker21 Aug 28 '19 at 17:24
  • Agreed - thanks. Are you interested in seeing a properly written out proof? –  Aug 28 '19 at 17:34
  • Yes, if it's not too much work on your part (I'll read it regardless) – mathworker21 Aug 28 '19 at 17:34
  • Can I email it? –  Aug 28 '19 at 17:36
  • Done - it wasn't as long as I thought it was going to be. I could have typed it up in TeX. –  Aug 28 '19 at 18:11
  • It has been sent successfully according to my computer but I've added an answer below - hope I didn't make too many typos in TeX. –  Aug 28 '19 at 18:40
0

Without loss of generality, we can assume that the coefficient of $t^d$ is +1.

If $d=2$
The possibilities for $P(t)$ are $0=-1-t+t^2$ and values which are at least 2 greater than this.

If $d>2$
The terms in $t^{(d-2)},t^{(d-1)}$ and $t^d$ sum to $0$ or at least $2t^{(d-2)}$.

If they sum to $0$ then we can proceed inductively. Otherwise we have $$P(t)\ge2t^{(d-2)}-t^{(d-3)}-t^{(d-4)}-t^{(d-5)}-t^{(d-6)}-…$$ $$=t^{(d-3)}+t^{(d-4)}-t^{(d-5)}-t^{(d-6)}-…$$ $$>2t^{(d-4)}-t^{(d-5)}-t^{(d-6)}-…$$ and again we can proceed inductively.