2

This is a follow-up question to Positive integer solutions to the diophantine equation $(xz+1)(yz+1)=z^4+z^3 +z^2 +z+1$

Let \begin{equation} P(x,n)= 1+x+x^2+ \cdots + x^n, \end{equation}

\begin{equation} h(m,n)= \frac{m^n-1}{m+1} \end{equation} if $n$ is even and \begin{equation} h(m,n)=\frac{m^{n}-m}{m^2-1} \end{equation} if $n$ is odd, where $x, n > 0, m>1$ are non negative integers. Then;

Claim 1: For all $n>0, m>1$, $m\cdot h(m,n)+1$ divides $P(h(m,n), n)$

Claim 2: Furthermore, for a fixed pair $(m,n), h(m,n)$ is the largest integer $x$ such that $mx+1 \ | \ P(x,n)$ i.e $mx+1 \ \nmid \ P(x,n)$ for all $x>h(m,n)$.

These claims are verified for all $n < 10^4, m < 10^2$, a high level of certainty! To prove these claims, my idea would be to use proof by induction but it appears tricky to proceed with induction. How does one go about proving these results? (An elementary proof is preferred or a counterexample).

Claim 2 is particularly interesting because, if its true, then, by just looking at the sizes of $m, n$, one will be able to rule out divisors of $P(x,n)$ of the form $mx+1$.

There’s nothing particularly unique about polynomial $P(x, n)$ and $mx+1$ to limit Claim 2 to $P(x, n) $ or $mx+1$; Only that $P(x,n)$ has no factor $mx+1$ with $m>1$ in its factorization which is why $m$ is set greater than $1$. If $m=1$ is allowed, claim 2 is false as $x+1$ divides $P(x,n)$ for all $x$ when $n+1$ is composite. If Claim 2 is true, the following conjecture is reasonable enough;

Conjecture 1

Let $f(x)$ and $g(x)$ be two polynomials of a non negative integer $x$ with integer coefficients, g(x) does not factor into $ (a/b)h(x)f(x) $ for some integers $a, b \not = 0 $ and polynomial $h(x) $ with integer coefficients. Then, $f(x)$ divides $g(x)$ for finitely many $x$.

ASP
  • 319
  • 1
    Conjecture 1 is false: let $f(x)=2$ (constant) and $g(x)=x$. – Wojowu Sep 26 '21 at 17:56
  • sorry I forgot to add that f and g have a degree greater or equal to 1 – ASP Sep 26 '21 at 19:34
  • fixed in the question – ASP Sep 26 '21 at 19:48
  • Meanwhile any counterexamples to Claims 1 and 2? – ASP Sep 26 '21 at 19:58
  • 1
    Conjecture 1 looks interesting - it is easy to state, and sounds very powerful if true. – Per Alexandersson Sep 26 '21 at 20:11
  • Still false for degree $\geq 1$, take $2x$ and $x^2$. – Wojowu Sep 26 '21 at 20:15
  • Okay. What's the best way of fixing these few cases? Restrict $x$ to be prime? – ASP Sep 26 '21 at 20:39
  • How about restricting $f$ and $g$ to have non zero free coefficients in addition to being non constant? – ASP Sep 26 '21 at 20:59
  • Conjecture 1 is true if you do divisibility in $\mathbf{Q}[X]$. More precisely if we divide the polynomials in $\mathbf{Q}[X]$ we know that $g=fh+r$ with $\deg(r)<\deg(f)$. Then multiplying by a suitable $N$ we have $Ng=f(Nh)+Nr$ where now $Nh, Nr$ have integer coefficients. It's still true that $f(x)|Ng(x)$ for infinitely many values so $\cfrac{Nr}{f}\in\mathbb{Z}$ for these $x$ but the limit is zero and thus it must be zero for infinitely many $x$ and thus $r=0$. – Vlad Matei Sep 27 '21 at 05:02
  • Actually putting a requirement of non zero free coefficient weakens the Conjecture more. It's sufficient to have $g(x) \not = (a/b) x^kf(x) $ where $a, b\not = 0, k \ge 0$ are integers. For example $f(x) = 3x+5$ and $g(x) = x^2$ – ASP Sep 27 '21 at 05:04
  • Indeed if $g(x) = (a/b)x^kf(x) $, then $f(x) \ | \ g(x) $ for all $ x$ with $b \ | \ x$ – ASP Sep 27 '21 at 05:15
  • Update: Rather than take $g(x) \not = (a/b)x^k$, we should take $g(x) \not = (a/b)u(x) f(x) $ where $u(x) $ is a polynomial with integer coefficients. – ASP Sep 27 '21 at 05:29
  • With this update, the non zero free coefficient on $f$ and $g$ can be dropped. – ASP Sep 27 '21 at 05:48

1 Answers1

6

Conjecture 1 follows from a (multiple of) Bezout identity for polynomials: $$mu(x)f(x)+mv(x)g(x)=md(x),$$ where $d(x) :=\gcd(f(x),g(x))$ and a positive integer $m$ is chosen such that polynomials $mu(x)$, $mv(x)$, $md(x)$ have integer coefficients. Then $f(x)\mid g(x)$ for some $x$ implies that $\frac{f(x)}{d(x)}\mid m$, which has a finite number of solutions as soon as $d(x)$ has degree smaller than $f(x)$.

In fact, I used this identity to design an algorithm for finding all $x$ with $f(x)|g(x)$.

Also, when $d(x)\equiv 1$ (i.e., $f(x)$ and $g(x)$ are coprime), the smallest possible $m$ is called the reduced resultant, which can be computed as explained in https://mathoverflow.net/q/333279

ADDED. As for the claims, they follow from the formula for the absolute value of resultant of $P(x,n)$ and $mx+1$ (see A062160) given by $$P(m,n)=\frac{m^{n+1} - (-1)^{n+1}}{m+1}.$$ It follows that if $(mx+1)\mid P(x,n)$, then $(mx+1)\mid P(m,n)$. And as soon as $mx+1 > P(m,n)$, i.e., $x > \frac{m^n - 1}{m+1}$, no divisibility can happen.

Max Alekseyev
  • 30,425
  • Can this be used to prove Claim 2? – ASP Sep 28 '21 at 06:50
  • @DavidJones: See addition to the answer. – Max Alekseyev Sep 28 '21 at 12:00
  • Let me first read and understand these new concepts : Absolute value resultant, reduced resultant, gcd of two polynomials. I will come back to the answer later. – ASP Sep 28 '21 at 12:15
  • I also observed that if $n=p-1$, $p$ prime then there are finitely many primes $x$ such that $P(x, n) $ has a divisor of the form $mx+1$. For instance if $p=5$, $P(x) = x^4+x^3 +x^2 +x+1$ we see that $2 \cdot 5+1 \mid P(5)$ and $14 \cdot 5+1 \mid P(5)$. It appears $P(x) $ is not divisible by any positive integer of the form $mx+1$ for all primes $x>5 $. Is this method still adaptable to proving this? – ASP Oct 06 '21 at 09:14
  • And if this is true for all odd primes $p$, then there's an interesting application in primality testing https://mathoverflow.net/questions/405529/are-there-finitely-many-primes-x-such-that-for-a-fixed-odd-prime-p-n-xp – ASP Oct 06 '21 at 09:14