Parametric solutions of Pell's equation

Question

Given a positive integer $n$ which is not a perfect square, it is well-known that Pell's equation $a^2 - nb^2 = 1$ is always solvable in non-zero integers $a$ and $b$.

Question: Let $n$ be a positive integer which is not a perfect square. Is there always a polynomial $D \in \mathbb{Z}[x]$ of degree $2$, an integer $k$ and nonzero polynomials $P, Q \in \mathbb{Z}[x]$ such that $D(k) = n$ and $P^2 - DQ^2 = 1$, where $a = P(k)$, $b = Q(k)$ is the fundamental solution of the equation $a^2 - nb^2 = 1$?

If yes, is there an upper bound on the degree of the polynomials $P$ and $Q$ -- and if so, is it even true that the degree of $P$ is always $\leq 6$?

Example: Consider $n := 13$. Putting $D_1 := 4x^2+4x+5$ and $D_2 := 25x^2-14x+2$, we have $D_1(1) = D_2(1) = 13$. Now the fundamental solutions of the equations $P_1^2 - D_1Q_1^2 = 1$ and $P_2^2 - D_2Q_2^2 = 1$ are given by

• $P_1 := 32x^6+96x^5+168x^4+176x^3+120x^2+48x+9$,

• $Q_1 := 16x^5+40x^4+56x^3+44x^2+20x+4$

and

• $P_2 := 1250x^2-700x+99$,

• $Q_2 := 250x-70$,

respectively. Therefore $n = 13$ belongs to at least $2$ different series whose solutions have ${\rm deg}(P) = 6$ and ${\rm deg}(P) = 2$, respectively.

Examples for all non-square $n \leq 150$ can be found here.

Added on Feb 3, 2015: All what remains to be done in order to turn Leonardo's answers into a complete answer to the question is to find out which values the index of the group of units of $\mathbb{Z}[\sqrt{n}]$ in the group of units of the ring of integers of the quadratic field $\mathbb{Q}(\sqrt{n})$ can take. This part is presumably not even really MO level, but it's just not my field -- maybe someone knows the answer?

Added on Feb 14, 2015: As nobody has completed the answer so far, it seems this may be less easy than I thought on a first glance.

Added on Feb 17, 2015: Leonardo Zapponi has given now a complete answer to the question in this note.

Answer 1

Let $n$ be a positive integer which is not a square and consider a fundamental solution $(a,b)$ of Pell's equation $$a^2-nb^2=1.$$ Setting $$\begin{cases} D=(a+1)^2b^2X^2+2(a+1)^2X+n,\\ P=b^4(a+1)X^2+2b^2(a+1)X+a,\\ Q=b^3X+b, \end{cases}$$ we have the identity $$P^2-DQ^2=1,$$ with $D(0)=n,P(0)=a$ and $Q(0)=b$. This explicitly answers the (first) question. A second post (below) shows that if $n$ is square-free and congruent to $3$ modulo $4$ then the degree of the polynomial $P$ is at most $2$.

In the rest of the post, we briefly sketch how the polynomials $P,Q$ and $D$ were constructed: let $P,Q,D\in\Bbb C[X]$ be three polynomials with $$P^2-DQ^2=1$$ and $\deg(D)=2$. Here, we assume $\deg(P)=d>1$, so that $\deg(Q)=d-1$. Consider the polynomial $f=P^2$, so that $f'$ has degree $2d-1$. Setting $$P=u\prod_{i=1}^r(X-x_i)^{e_i}\quad\mbox{and}\quad Q=v\prod_{i=1}^s(X-y_i)^{f_i},$$ with $u,v\in\Bbb C,r\leq d$ and $s\leq d-1$, we obtain the factorization $$f'=\prod_{i=1}^r(X-x_i)^{2e_i-1}\prod_{i=1}^r(X-y_i)^{2f_i-1}R,$$ with $R\in\Bbb C[X]$. Since $d=\sum_{i=1}^re_i=1+\sum_{i=1}^sf_i$, we find the identity $$2d-1=\sum_{i=1}^r(2e_i-1)+\sum_{i=1}^s(2f_i-1)+\deg(R)=4d-2-r-s+\deg(R),$$ which leads to $$r+s=2d-1+\deg(R).$$ It then follows that $r=d,s=d-1$ and $\deg(R)=0$, i.e. $P$ and $Q$ are separable. Remark that the polynomial $D$ is then itself separable. In this case, the cover $\Bbb P^1\to\Bbb P^1$ induced by $f$ is only ramified above $\infty,0$ and $1$, i.e. it is a Belyi map. The isomorphism classes of such covers are classified by Grothendieck's dessins d'enfants and, once we have fixed the integer $d$, there is a unique class with the above ramification data (totally ramified above $\infty$, all the points above $0$ have ramification index $2$ and the points above $1$ have ramification $2$ excepted two of them, which are unramified, corresponding to the roots of $D$). More precisely, if $T_d\in\Bbb Z[X]$ denotes the Chebyshev polynomial (of the first kind) of degree $d$, there exist constants $\lambda\in\Bbb C^\times$ and $\nu\in\Bbb C$, such that $$f=\frac{T_{2d}(\lambda X+\nu)+1}2=T_d(\lambda X+\nu)^2.$$ This shows how to construct $P$. For example, in individ's answer, we find $$P=T_2(\lambda X+\nu),$$ with $\lambda=\frac{\sqrt{2}}2$ and $\nu=\sqrt{2}$, while $\lambda=169i$ and $\nu=-99i$ (with $i^2=-1$) leads to Will Jagy's example for $n=29$.

We can then try to find a solution for general $n$ from the case $d=2$ in the above discussion. Consider a fundamental solution $(a,b)$ of the Pell's equation $a^2-nb^2=1$. It is clear that in Stefan Kohl's question, we can reduce to the case $k=0$.We have the identity $T_2=2X^2-1$ and we therefore set $$P=2(\lambda X+\nu)^2-1.$$ The condition $P(0)=a$ leads to the relation $\nu=\frac12\sqrt{2a+2}$, while $P\in\Bbb Z[X]$ gives the identity $P=NX^2+MX+a$, with $N$ and $M$ integers such that $4(a+1)N=M^2$. We then find the factorization $$P^2-1=\left(\frac14M^2X^2+M(a+1)X+nb^2\right)\left(\frac M{2(a+1)}X+1\right)^2.$$ Finally, setting $M=2(a+1)b^2$, we can factor $b^2$ on the first factor of the above identity and put it in the second factor, which leads to the result.

Added on Feb 17, 2015: A complete answer to the question can be found in this note.

Answer 2

Not sure degree 6 is necessary. See what you can do with $$ n=29, \; k=1, \; D = 169 x^2 - 198 x + 58, $$ $$ n=53, \; k=1, \; D = 625 x^2 - 886 x + 314, $$

The coefficient of $x^2$ seems to be $w^2,$ where $v^2 - n w^2 = -1.$ Such a $w$ is guaranteed to exist when $n \equiv 1 \pmod 4$ is prime.

Ummm; the discriminants of the quadratic forms $169 x^2 - 198 xy + 58y^2$ and $625 x^2 - 886 xy + 314y^2$ are $-4.$ Same for $25 x^2 \pm 14 xy + 2 y^2$ and $x^2 + y^2,$ also the ones for primes $73,89,113,$ also cases where you found $P$ quadratic and $Q$ linear.

LATER: $29$ worked very well. $$ n=29, \; k=1, \; D = 169 x^2 - 198 x + 58, $$ $$ P = 57122 x^2 - 66924 x + 19603, $$ $$ Q = 4394 x - 2574, $$ $$ P^2 - D Q^2 = 1, $$ $$ P(1) = 9801, \; Q(1) = 1820, \; D(1) = 29. $$

Answer 3

Here are some results concerning the degree of the polynomial $P$. We only treat the cases where $n$ is a positive, square-free integer congruent to $3$ modulo $4$, showing that the degree of $P$ is less than or equal to $2$.

We start by the weaker assumption that, given the positive integer $n$ and a solution $(a,b)$ of Pell's equation $a^2-nb^2=1$, there exist polynomials $D,P,Q\in\Bbb Q[X]$ and a rational number $k$ such that $P^2-DQ^2=1$, with $D(k)=n,P(k)=a$ and $Q(k)=b$. Let $d$ be the degree of $P$. As mentioned in my other post, and following the conventions and results in David Speyer's answer, there exist constants $\alpha\in\Bbb C$ and $\beta,\gamma\in\Bbb Q$, with $\alpha^2,\gamma^2\in\Bbb Q$ such that $$\begin{cases} P=\pm T_d\left(\alpha(X+\beta)\right),\\ Q=\gamma U_{d-1}\left(\alpha(X+\beta)\right),\\ D=\gamma^{-2}\left(\alpha^2(X+\beta)^2-1\right), \end{cases}$$ where $T_d$ (resp. $U_d$) denotes the degree $d$ Chebyshev polynomial of the first kind (resp. of the second kind). From the hypothesis on $P$, we can assume $\beta=0$. We have the identity $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X+\sqrt{X^2-1}\right)^d,$$ which leads to $$P+Q\sqrt{D}=\left(\alpha X+\sqrt{\alpha^2X^2-1}\right)^d.$$ If $d$ is odd then the explicit expression of $T_d$ shows that $\alpha$ (and therefore $\gamma$) is rational. Evaluating at $k$, we then obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^d,$$ with $u,v\in\Bbb Q$. It then follows that $u+v\sqrt{n}$ is a unit in the ring of integers of $\Bbb Q(\sqrt{n})$ and, since we are assuming $n\equiv3\pmod4$, the elements $u$ and $v$ are integers. In particular, for $d>1$, the couple $(a,b)$ cannot be a fundamental solution of Pell's equation.

From now on, we assume $d=2m$ even. For $\alpha\in\Bbb Q$, we proceed as above and deduce that $(a,b)$ cannot be a fundamental solution for $d>1$. Suppose then that $\alpha=\sqrt{w}$, we $w\in\Bbb Q$ not a square, so that $\gamma=t\alpha$, with $t\in\Bbb Q$. We have the relation $$T_d+U_{d-1}\sqrt{X^2-1}=\left(X^2-1+2X\sqrt{X^2-1}\right)^m$$ and thus $$P+Q\sqrt{D}=\left(\alpha^2X^2-1+2\alpha\sqrt{\alpha^2X^2-1}\right)^m.$$ Evaluating at $k$, we then easily obtain the identity $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^m,$$ with $u,v\in\Bbb Q$. Once again, for $m>1$, it then follows that the couple $(a,b)$ cannot be a fundamental solution, leading to the result.

A final remark: for general $n$, if $(a,b)$ is a fundamental solution then $$a+b\sqrt{n}=\left(u+v\sqrt{n}\right)^r,$$ where $u+v\sqrt{n}$ is a fundamental unit of $\Bbb Q(\sqrt{n})$. For example, in Stefan Kohl's example for $n=13$, we have $$649+180\sqrt{13}=\left(\frac{11}2+\frac32\sqrt{13}\right)^3.$$ I'm definitely not an expert on this subject, but the above discussion combined with an explicit bound for the integer $r$ would lead to a bound for the degree of $P$ and therefore give a complete answer to the second question.

Answer 4

For $\deg P = 1$ or $2$, yes. For $\deg P=1$, take $$P(x) = Mx+a,\ Q(x) = b,\ D(x) = \frac{M^2}{b^2} x^2 + \frac{2 Ma}{b^2} x + n.$$ For $M$ a sufficiently divisible integer, this will have integer coefficients. For $\deg P=2$, take $$P(x) = (a+1) (Mx+1)^2 - 1,\ Q(x) = (Mx+1) b,\ D(x) = \frac{M^2(a+1)^2}{b^2}x^2+ \frac{2 M (a+1)^2}{b^2}x + n.$$ For sufficiently divisible $M$, this will have integer coefficients.

---

For $\deg P>2$, there will rarely be any solutions.

At the risk of confusion, I'm going to rename some variables: Our given solution to Pell's equation is $a^2 - d b^2 =1$, and our goal is to find integer polynomials $A(x)$, $B(x)$ and $D(x)$ such that $A(x)^2 - D(x) B(x)^2 = 1$ and $(A(0), B(0), D(0)) = (a,b,d)$. The degree of $A$ is $n$. (As Leonardo observes, we can always translate $x$ to assume the polynomials are being evaluated at $0$.) Cleaning up some of Leonardo's formulas, we get that $$(A(x), B(x), D(x)) = (T_{n}(\alpha (x+ \beta)), \ \gamma U_{n-1}(\alpha (x+\beta)), \ \gamma^{-2} (\alpha^2 (x + \beta)^2 - 1))$$ for some constants $(\alpha, \beta, \gamma)$, where $T_n$ and $U_{n-1}$ are Chebyshev polynomials of the first and second kinds. Note the formula $T_n(x)^2 - (x^2-1) U_{n-1}(x)^2=1$.

Taking the ratio of the $x^2$ and $x$ terms in $D(x)$, we see that $\beta$ is rational. The $x^n$ and $x^{n-2}$ terms in $A(x)$ are $2^{n-1} \alpha^n$ and $\alpha^{n-2} (n 2^{n-1} + 2^{n-1} \binom{n}{2} \beta \alpha^2 )$. Taking the ratio of these, we deduce that $n 2^{n-1} + 2^{n-1} \binom{n}{2} \beta \alpha^2$ is rational, so $\alpha^2$ is rational.

For any given $n$, the equation $T_n(\alpha \beta) = a$ determines $\alpha \beta$ up to finitely many values. But we have also seen that $(\alpha \beta)^2$ is rational. But, for generic $a$, the Galois group of $T_n(x) = a$ should be dihedral of order $2n$, by Hilbert's irreducibility theorem.

I suspect that you might be able to get solutions whenever $a$ happens to be of the form $T_n(\sqrt{m})$ for some $m$ and some Chebyshev polynomial $T_n$, but I haven't thought it through carefully.

Answer 5

Perhaps I wrote too short. So will write more. Our goal is to find out - is there a maximum degree of these polynomials? Therefore, to simplify calculations it is possible to choose any ratio of the Pell equation. For example, for the equation:

$$P^2-DQ^2=1$$

Knowing the previous solution of the Pell equation $(P1;Q1)$ can be found following the $(P2;Q2)$. Where $(P;Q)$ the first solution of this equation. For this you can use the formula.

$$P_2=PP_1+DQQ_1$$

$$Q_2=QP_1+PQ_1$$

We will use such polynomials.

$$P=x^2+4x+3$$

$$D=x^2+4x+2$$

$$Q=x+2$$

We substitute these values into the formula can be obtained for other factor the polynomial. He will be a multiple of the square. This way you can be of any degree.

$$P=8x^8+128x^7+864x^6+3200x^5+7080x^4+9536x^3+7600x^2+3264x+577$$

$$D=16(x^2+4x+2)(x+2)^2(x^2+4x+3)^2$$

$$Q=2x^4+16x^3+44x^2+48x+17$$