prove for all $k> 1$ equation $(x+1)(x+2)...(x+k)=y^{2}$ has finite solutions.
Problem
Source: iran tst 2014 second exam
Tags: algebra, polynomial, number theory proposed, number theory
22.05.2014 18:45
This seems a pretty huge overkill. I have an elementary proof for $k=$ even but without the odd part its not complete. This works so here goes: Fix $k$. Consider the polynomial $P_{k}(x)=(x+1)(x+2)\ldots(x+k)$. Now suppose there are infinitely many solutions of the given equation, that is: there is an infinite sequence $\{x_{\ell}\}_{\ell\ge 1}$ such that $P_k(x_{\ell})=y_{\ell}^2$ for some integer $y_{\ell}$. Now use this post to show that when a polynomial is square at infinitely many points it is a perfect square. But it is impossible since $P_k$ has all roots with multiplicity $1$. Thus a contradiction. Also see Erdos-Selfridge Theorem for some stronger conclusions.
28.05.2014 17:27
for odd k: there exist $q(x)$ such that $q(x)^2=p(x^2)$ so $p(1)$ is perfect square which is impossible hence we are done.(i used this)
28.05.2014 17:43
mmaht wrote: for odd n: there exist $q(x)$ such that $q(x)^2=p(x^2)$ so $p(1)$ is perfect square which is impossible hence we are done.(i used this) your lemma is true for polynomials wهth even degree
28.05.2014 17:53
nima1376 wrote: mmaht wrote: for odd n: there exist $q(x)$ such that $q(x)^2=p(x^2)$ so $p(1)$ is perfect square which is impossible hence we are done.(i used this) your lemma is true for polynomials wهth even degree yes because $p(x^2)$ is a polynomial with even degree so what i wrote is true.but my mistake is that from where we know $p(x^2)$ is perfect square for infinity many x(if p(x) was perfect square for infinity many x)
04.09.2018 20:38
Here is an overkill:It is well known that multiply of some consecutive integers is never a perfect power so we are done.
04.09.2018 22:24
joybangla wrote: This seems a pretty huge overkill. I have an elementary proof for $k=$ even but without the odd part its not complete. This works so here goes: Fix $k$. Consider the polynomial $P_{k}(x)=(x+1)(x+2)\ldots(x+k)$. Now suppose there are infinitely many solutions of the given equation, that is: there is an infinite sequence $\{x_{\ell}\}_{\ell\ge 1}$ such that $P_k(x_{\ell})=y_{\ell}^2$ for some integer $y_{\ell}$. Now use this post to show that when a polynomial is square at infinitely many points it is a perfect square. But it is impossible since $P_k$ has all roots with multiplicity $1$. Thus a contradiction. Also see Erdos-Selfridge Theorem for some stronger conclusions. doesn't seem to work (the link about perfect squares polynomial )
08.11.2018 16:34
mmaht wrote: for odd k: there exist $q(x)$ such that $q(x)^2=p(x^2)$ so $p(1)$ is perfect square which is impossible hence we are done.(i used this) Why?
08.11.2018 16:36
I was wrong
02.11.2019 16:08
Can somebody prove that an polynominal which does not have real roots can become an sum for two polynominals?
11.03.2020 09:15
Bump... Any try for odd $k$?
09.11.2020 02:39
Solved with Amol Rama, Ankit Bisain, Raymond Feng, and William Wang. We first establish an important lemma. Lemma: Let $P$ be a polynomial of even degree with integer coefficients. If $P(n)$ is a square of an integer for infinitely many integers $n$, then $P$ is the square of some polynomial. Proof: It is easy to see that there are polynomials $Q$ and $R$ such that $P=Q^2+R$, where $\deg Q=\frac{1}{2}\deg P$ and $\deg R<\deg Q$ or $R=0$. Note that $Q$ and $R$ have rational coefficients. Thus, there exists an $\varepsilon>0$ such that for any integer $n$, $Q(n)$ is either an integer or at least $10\varepsilon$ away from an integer. WLOG, suppose that the leading coefficient of $Q$ is positive. Then, for positive integers $n$ that are sufficiently large, \[(Q(n)-\varepsilon)^2 = Q(n)^2-2\varepsilon\cdot Q(n)+1<Q(n)^2+R(n),\]as $\deg Q>\deg R$ and $Q$ has positive leading coefficient, and similarly, \[(Q(n)+\varepsilon)^2>Q(n)^2+R(n).\]Thus, \[(Q(n)-\varepsilon)^2 < Q(n)^2+R(n) < (Q(n)+\varepsilon)^2.\]Similarly, if $n$ is negative with large absolute value, then a similar inequality as above holds, with directions potentially swapped if $\deg Q$ is odd. Thus, for sufficiently large $|n|$, $Q(n)^2+R(n)$ being a square of an integer implies that \[|Q(n)|-\varepsilon < \sqrt{Q(n)^2+R(n)} < |Q(n)|+\varepsilon.\]Thus, $Q(n)$ is an integer, and in fact $\sqrt{Q(n)^2+R(n)}=|Q(n)|$, so $R(n)=0$. We are given that this happens infinitely many times, so in fact $R\equiv 0$, so $P=Q^2$, as desired. $\blacksquare$ The lemma immediately implies the problem for $k$ even, as $(x+1)\cdots(x+k)$ is not the square of a polynomial. Suppose now that $k$ is odd. Suppose we have integers $x$ and $y$ such that \[(x+1)\cdots(x+k) = y^2.\]Each prime $p\ge k$ can appear as a factor of at most one of $x+1,x+2,\ldots,x+k$. Thus, $v_p(x+i)$ is always even for $1\le i\le k$. Now, let $p_1,\ldots,p_\ell$ be the list of all primes that are less than $k$. For $1\le i\le k$, let \[w_i = (v_{p_1}(x+i),\ldots,v_{p_\ell}(x+i))\mod{2}.\]View the $w_j$s as vectors in $\mathbb{F}_2^\ell$. Since $k>\ell$, the set $\{w_1,\ldots,w_k\}$ is linearly dependent, so there is some nontrivial partition $A\sqcup B$ of $[k]$ such that \[\sum_{i\in A}w_i=\sum_{i\in B}w_i=0,\]in $\mathbb{F}_2^\ell$. This implies that \[v_{p_j}\left(\prod_{i\in A}(x+i)\right)\]is even for all $j$, and same for $B$. Combined with the observation above about primes $\ge k$, we see that \[\prod_{i\in A}(x+i)\]and \[\prod_{i\in B}(x+i)\]are perfect squares. WLOG, let $A$ be the one of even size. Thus, for each solution $(x,y)$, there is a nonempty $A\subseteq[k]$ of even size such that \[\prod_{i\in A}(x+i)\]is a perfect square. Since there are infinitely many such solutions, there is some even nonempty subset $S\subseteq[k]$ such that $\prod_{i\in S}(x+i)$ is a square for infinitely many values of $x$. This contradicts our lemma, as the product cannot be the square of a polynomial, as it has all distinct roots. This completes the proof.
17.11.2020 12:23
Solved with Th3Numb3rThr33. We cite the following well-known lemma: Lemma: If \(P(X)\in\mathbb Z[X]\) has even degree and its leading coefficient is a perfect square, then either \(P(X)\) is a square finitely often or \(P\) is the square of a polynomial. Proof. Bound between two squares. \(\blacksquare\) The lemma immediately solves the problem for \(k\) even, so henceforth \(k\) is odd. For each \(i\in[k]\), let \[x+i=a_i\cdot b_i^2,\quad\text{where }a_i\text{ is squarefree.}\]Observe that each prime \(p\ge k\) can divide at most one of \(x+1\), \ldots, \(x+k\), so it must have even exponent. It follows that all primes \(p\) dividing \(a_i\) satisfy \(p<k\). I claim: Claim: For sufficiently large \(x\), the product \(\prod_{i\in S}a_i\) is distinct over all \(S\subseteq[k]\). Proof. Assume for contradiction \(\prod a_S=\prod a_T\). We can assume \(S\cap T=\varnothing\), since we may delete elements in \(S\cap T\) from both products. Then \[\prod_{i\in S\cup T}(x+i)=\left(\prod a_S\right)^2\cdot b_i^2\cdot b_j^2\]is a perfect square. Moreover, \[\prod_{i\in[k]\setminus(S\cup T)}(x+i)\]is also a perfect square. Since \(k\) is odd, one of these has an even number of linear terms, so by the lemma, it is not a square for sufficiently large \(x\). \(\blacksquare\) Take \(x\) sufficiently large (so the claim holds). There are \(2^{\pi(k-1)}\) possible products \(\prod a_S\) using primes \(p<k\), but we have exhibited \(2^k\) distinct products. This is a contradiction.
15.08.2021 10:25
Evidently we may assume $x>0$, since for $k$ odd, $x<-k$ produces no solution and for $k$ even, $x<-k$ may be replaced with $-(x+k+1)$. For $k=2$ we have $(x+1)^2<(x+1)(x+2)<(x+2)^2$. For $k=3$, we have $\gcd(x+2,(x+1)(x+3))$, so $(x+1)(x+3)=(x+2)^2-1$ is a perfect square, which never happens. For $k=4$, we have $(x^2+5x+4)^2<(x+1)(x+2)(x+3)(x+4)<(x^2+5x+5)^2$. For $k\ge5$, the hyperelliptic curve $y^2=(x+1)(x+2)\cdots(x+k)$ has genus $\ge2$, so by Faltings' theorem it contains finitely many rational points, the end.
20.08.2021 19:15
I will re edit this
22.01.2022 03:26
Claim: If $P(x)\in \mathbb{Z}[x]$, $\deg P$ is even and the leading coefficient of $P$ is a perfect square, then one of the two is true: 1. $P(x)=Q(x)^2$ for some $Q(x)\in \mathbb{Z}[x]$. 2. There exists $N$ such that for all $x>N$, $P(x)$ is not a perfect square. Proof: The idea is to write $P(x)=Q(x)^2+R(x)$ where $R(x)=O(x^{n-1})$, which solves the problem because if $R(x)$ is not identically 0, $Q(x)^2 < P(x) < (Q(x)+1)^2$ or $(Q(x)-1)^2 < P(x) < Q(x)^2$ We construct $Q$ this way: let $2k=\deg P$, $q_k=\sqrt{[x^{2k}]P(x)}$ and $2q_jq_k + \sum\limits_{t=j+1}^{k-1} q_tq_{j+k-t} = [x^{j+k}]P(x)$. Then if $Q(x)=\sum\limits_{j=0}^k q_jx^j$ where $q_j\in \mathbb{Q}$, we can consider $C^2P(x)=(CQ(x))^2+R(x)$ and apply the "bound between two squares". This solves the problem for $k$ even. For $k$ odd, the idea is that if I rewrite $(x+1)\cdots (x+k)=A(x)B(x)$ then one of $\deg(A), \deg(B)$ is even. If for a sufficiently large $x$, we force $\gcd(A(x),B(x))$ to be a perfect square, then $A(x)$ must a perfect square, which contradicts the above lemma. Let $[k]=\{1,\cdots,k\}$, $A(x)=\prod\limits_{t\in S} (x+t)$ and $B(x)=\prod\limits_{t\in [k]\backslash S} (x+t)$. Note $\gcd(A(x),B(x))$ can only have primes up to $k-1$ because a prime $p$ must divide $x+m, x+n$ for some $m\ne n$. We represent $f(S)=\langle x_2, x_3\cdots,x_{p_m} \rangle$ where $2,3,\cdots,p_m$ are the primes at most $k-1$ and $x_p\equiv \nu_p(\prod\limits_{t\in S} (x+t)) (\bmod\; 2)$. Essentially we are working in an additive space in $(\mathbb{F}_2)^m$ because $f(S\bigoplus T)=f(S) + f(T)$. We also know that $f([k])=\langle 0,\cdots, 0\rangle$ because $\prod\limits_{t=1}^k (x+t)$ is a perfect square. This means $f(S)=f([k]\backslash S)$. For each $(S, [k]\backslash S)$, we focus on the one with even cardinality. We have $2^{k-1}$ even subsets of $[k]$ and there are $2^{\pi(k-1)}$ values for $f(S)$. Since $k\ge 3$, $k-1>\pi(k-1)$, so it follows by pigeonhole principle that there exists $S\ne T$ where $S,T$ are subsets of $[k]$ with an even number of elements such that $f(S)=f(T)$. Now, $S\bigoplus T$ must also be a subset of even cardinality and $f(S\bigoplus T)=0$, implying $A(x)=\prod\limits_{j\in S\bigoplus T} (x+j)$ is perfect square, as needed.
06.09.2023 03:40
Very nice and unexpected problem. First, we prove a well known lemma. Lemma: Let $P$ be an integer-coefficient polynomial with even degree and whose leading coefficient is a perfect square. If $P(x)$ is a square for infinitely many integers $x$, then $P$ is the square of a polynomial. Proof: We bound $P$ between two perfect squares. Assume FTSOC that $P(x)=a^2x^{2n}+a_{2n-1}x^{2n-1}+\cdots+a_0$ is not the square of a polynomial. We claim that there exist polynomials $Q(x),R(x) \in \mathbb{Q}[x]$ such that $P=Q^2+R$ and $\deg R<\deg Q$. Let $Q(x)=ax^n+b_{n-1}x^{n-1}+\cdots+b_0$ for unknown constants $b_0,\ldots,b_{n-1}$. The coefficients of $x^{n+i}$ in $P(x)$ and $Q(x)^2$ agree if \[a_{n+i}=ab_i+b_{n-1}b_{i+1}+\cdots+b_ia \Longleftrightarrow b_i=\frac{a_{n+i}-b_{n-1}b_{i+1}-\cdots-b_{i+1}b_{n-1}}{2a}.\]Using this for $i=n-1,n-2,\ldots,0$, we can find rational values of $b_{n-1},\ldots,b_0$ such that the coefficients of $P$ and $Q^2$ agree on all terms of degree at least $n$. This makes $R(x) \in \mathbb{Q}[x]$ have degree less than $n$. Let $c$ be a positive integer such that $cQ(x) \in \mathbb{Z}[x]$. If $P(x)$ is a perfect square, then $c^2P(x)=c^2Q(x)^2+c^2R(x)$ is a perfect square. However, notice that $c^2Q(x)^2+c^2R(x)$ is bounded between $(cQ(x)-1)^2$ and $(cQ(x)+1)^2$ and is not equal to $c^2Q(x)^2$ for all $x$ with large enough absolute value. Thus, $c^2Q(x)^2+c^2R(x)$ is a perfect square for finitely many integers $x$, so $P(x)$ is a perfect square for finitely many integers $x$. $\square$ This lemma solves the problem for even $k$. For odd $k$, we only need to consider nonnegative values of $x$. Let $x_0$ be a nonnegative integer such that $(x_0+1) \cdots (x_0+k)$ is a perfect square. By the lemma, we can choose an integer $N$ such that for all monic nonconstant factors $P(x)$ of $(x+1) \cdots (x+k)$ with even degree and for all integers $n>N$, $P(n)$ is not a perfect square. For any prime $p>k$, we see that $p$ can divide at most one of $x_0+1,\ldots,x_0+k$, so we have $2 \mid \nu_p(i)$ for $i=x_0+1,\ldots,x_0+k$. Let $p_1<p_2<\cdots<p_l$ be the set of primes at most $k$, and let the signature of a positive integer $i \le k$ be the vector $(\nu_{p_1}(x_0+i),\ldots,\nu_{p_l}(x_0+i))$ in $\mathbb{F}_2^l$. Notice that the sum of the signatures of $x_0+1,\ldots,x_0+k$ is $0$. Since $\mathbb{F}_2^l$ is $l$-dimensional and $l<k$, we can partition $\{x_0+1,\ldots,x_0+k\}$ into two nonempty subsets $A$ and $B$ such that the sums of the signatures of the elements of $A$ and $B$ are $0$. Hence, the products of the elements of $A$ and $B$ are perfect squares. One of $A$ and $B$ must have even size; assume WLOG that it is $A$. Since $\prod\nolimits_{i \in A}(x_0+i)$ is a perfect square, we have $x_0 \le N$. Thus, there are finitely many values of $x$ that satisfy the equation, as desired. $\square$
14.08.2024 06:25
Assume the contrary . [for my ease i will leave out on the small values of $k$ cases u can casework them out pretty easily] Claim: $k$ is odd. Proof: Assume the contrary, It can be easily proved that if any monic polynomial with integral coefficients becomes perfect square infinitely often itself is a square polynomial. through bounding it between two square polynomials. this easily gives contradiction. Now as $k$ is odd $x$ cant be a large negative number coz then LHS$<0$. SO it has infinite positive solutions, let $S$ be that set by infinite PHP there exist an integer $r$ such that $S'=\{e| e \in S , e\equiv r(mod k!)\}$ must be an infinite set. Let $t$ be the smallest element in $S'$ pick any other large solution $x>t$ in $S'$. Say $x=k!X+t$. Now before we jump into the next we prove a key lemma: Lemma: If $p^{\beta}$ is the power of some prime in the canocial factorization of $k!$ then $p^{\beta}>\frac{k}{2}$. Proof: if $p>\frac{k}{2}$ the result is obvious. So we assume thats not the case. Then $p^{\beta} \geq p^{\frac{n}{p}-1}$. Now bit of calculus shows $f(x)=x^{1/x}$ starts decreasing pretty quickly finsihing the proof for large enough $k$'s. Now call an element $e$ in $t+1,t+2,....,t+k$ as "amazing" if for any prime $p \leq k$ , $v_p(e) < v_p(n!)$. Now say $(k!X+t+1)(k!X+t+2)....(k!X+t+k)=y^2$ Write this as $(t+1,k!)(t+2,k!)....(t+k,k!)(\frac{k!}{(k!,t+1)}X+\frac{t+1}{(k!,t+1)})(\frac{k!}{(k!,t+2)}X+\frac{t+2}{(k!,t+2)}).....(\frac{k!}{(k!,t+k)}X+\frac{t+k}{(t+k,k!)})$ All the terms are in the product $(\frac{k!}{(k!,t+1)}X+\frac{t+1}{(k!,t+1)})(\frac{k!}{(k!,t+2)}X+\frac{t+2}{(k!,t+2)}).....(\frac{k!}{(k!,t+k)}X+\frac{t+k}{(t+k,k!)})$ are relatively prime this is easy to see. Now observe all prime factors in $(t+1,k!)(t+2,k!)...(t+k,k!)$ are at max $k$ now if $e$ is an amazing element. We can say $\frac{k!}{(k!,e)}X+\frac{e}{(k!,e)}$ does not have any prime factor less than $k$. due to the relatively prime relation as well we can say it has to be a perfect square!. Now let $A$ be the set of all amazing integers. due to $p^{\beta}>\frac{k}{2}$ relation each prime can cause issue in creating amazing integers at max twice that is it can divide at max two numbers in $t+1,....,t+k$ , so $|A| \geq k-2\pi(k)$. Now let limit our attention purely to the elements of $A$. Define $G=\{\frac{k!}{(k!,e)}|e \in A\}$[counted with duplicates]. Time for some combinatorics magic now. Claim: There exist two distinct non empty subsets $S_1,S_2$[duplicate terms are kept distinct] of $G$ such the product of elements in $S_1$ multiplied with the product of the elements in $S_2$ gives a perfect square. and $|S_1|$ and $|S_2|$ have same parity. Proof: For any non empty subset $S$ of $G$ with product $P$ define its binary representation as the tuple $(v_2(P),v_3(P),...,v_p(P),|S|)$ each term of the tuple evaluated modulo $2$. and $p$ largest prime at max $k$. This gives us a total of $2^{|A|}-1$ such representations but there are only $2^{\pi(k)+1}$ possible such representations. As $|A|\geq k-2\pi(k)$ for large $k$'s by PHP two representations must match this however gives needed selection of subsets. Once done with that for any element $e$ in $A$ define its "crazy" polynomial to be $\frac{k!}{(k!,e)}X+\frac{e}{(k!,e)}$. Now compute the product of the crazy polynomials of elements in $S_1$ and the product of crazy polynomials of elements in $S_2$ say the polynomials we got are $p_1(x)$ and $p_2(x)$ as per claim there are infinitely many positive integers $x$ such that both are simultaneiously perfect squares. We contradict this as leading coefficient of $p_1(x)$ multipled with that of $p_2(x)$ is a perfect square morever their degrees have same parity. say $G(x)=p_1(x)p_2(x)$ which must also be a perfect square infinitely often. so leading coefficient of $G(x)$ is perfect square and its degree is even using similar proof as to what we did to prove $k$ is odd $G(x)$ must be a square polynomial which is easy to see cannot hold
26.12.2024 07:29
We are going to use this well known lemma. Lemma: If a polynomial $Q(X) \in \mathbb{Z}[X]$ has even degree and the leading coefficient is a perfect square, then either it takes the value of a perfect square finitely many times or it is a square of a polynomial. Case A: $k$ is even Immediate from the main lemma. Case A: $k$ is odd Let \[S=\{x+1,\dots x+k \}\]Claim: There exists an nonempty proper subset $T$ of $S$ such that $\prod_{t \in T} t$ is a perfect square and $|T|$ is even. Proof: Let $p_1,\dots,p_{\ell}$ be all primes less than $k$. See that if $q$ is a prime atleast $k$, then there exists atmost one $i$ such that $q \mid x+i$ such that $q \mid x+i$ for $1 \leq i \leq k$. And also we have $\nu_q(x+i) \equiv 0 \pmod 2$. Consider this $\ell \times k$ table in $\mathbb{F}_2$. \begin{align*} & \nu_{p_1}(x+1) \text{ } \nu_{p_2}(x+1) \text{ } \dots \text{ } \nu_{p_{\ell}} (x+1) \\ & \nu_{p_1}(x+2) \text{ } \nu_{p_2}(x+2) \text{ } \dots \text{ } \nu_{p_{\ell}} (x+2) \\ & \nu_{p_1}(x+3) \text{ } \nu_{p_2}(x+3) \text{ } \dots \text{ } \nu_{p_{\ell}} (x+3) \\ & \qquad \text{ } \text{ } \vdots \qquad \qquad \text{ } \vdots \qquad \dots \text{ } \text{ } \qquad \vdots \\ & \nu_{p_1}(x+k) \text{ } \nu_{p_2}(x+k) \text{ } \dots \text{ } \nu_{p_{\ell}} (x+k) \\ \end{align*}See sum of elements in each column in $0$. Now consider each row, there are $2^{\ell}$ possible values of it. If we take some nonzero (and not all) combination of rows, we can choose it in $2^k-2$ ways. See that $2^k-2>2^{k-1} \geq 2^{\ell}$ and so by PHP, two distinct combinations of these rows, when added up column by column, they are isomorphic to each other. Now take any common intersection out, and consider the sum of the two remaining combination of rows (column by column) and see that, it is filled with a bunch of $0$s. Because sum of all rows (column by column) in the original $\ell \times k$ table is just bunch of $0$s and $k$ is odd; either the set we were talking about or its complement has even number of rows. $\square$ See that number of subsets of $S$ is obviously finite and now apply the main lemma bunch of times and we are done. Remark: A Diophantine which is a combo in disguise, that's a first.