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.
Best Answer
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.