26
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This is curve defined over Q and of degree 2. So it will be a rational curve if it has a point defined over Q. For the so called Pell's equation the hypothesis holds. $\endgroup$ – P Vanchinathan Jan 26 '15 at 14:31
  • 2
    $\begingroup$ Also, if the answer is yes, then the degress are definitely unbounded, since if $\sqrt{n}$ has a long period for its continued fraction, then $\sqrt{D}$ also has a long period, so $P,Q$ will be of large degree. $\endgroup$ – Dror Speiser Jan 26 '15 at 23:27
  • 1
    $\begingroup$ Dear Stefan, I know have a complete proof that if $n$ is square-free then the degree of $P$ is bounded by $6$. I'm writing a short, summarizing note; you will receive it shortly. $\endgroup$ – Leonardo Feb 14 '15 at 23:23
  • 1
    $\begingroup$ The note is now available here. It is a draft version, which might soon be modified. It turns out that the possible degrees for $P$ are $1,2,3$ and $6$ (and they actually all occur). $\endgroup$ – Leonardo Feb 16 '15 at 13:57
  • 1
    $\begingroup$ This is not yet clear... I will work on the question. $\endgroup$ – Leonardo Feb 16 '15 at 18:23
18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Great! -- Thank you! -- Can you also say something on whether there exist series where $P$ has degree larger than $6$, or whether the degree of $P$ is bounded at all? $\endgroup$ – Stefan Kohl Jan 27 '15 at 17:16
  • 2
    $\begingroup$ A table of Leonardo's polynomials for $n \leq 100$ is available here. $\endgroup$ – Stefan Kohl Jan 27 '15 at 18:15
  • 1
    $\begingroup$ Dear Stefan, I found a partial answer concerning the degree of $P$. In order to keep the above comments consistent, instead of editing my answer, I decided to write a new post. $\endgroup$ – Leonardo Feb 2 '15 at 14:55
  • 1
    $\begingroup$ It can be proved that setting $P_1=P(c^{-1}X), Q_1=Q(c^{-1}X)$ and $D_1=D(c^{-1}X)$, with $c=\mbox{gcd}\left(b^3,(a+1)b,2(a+1)^2\right)$ we obtain the parametric solutions whose coefficients have the smallest absolute values (try for $n=31,a=1530$ and $b=273$). Indeed, given $n,a$ and $b$, all the parametric solutions (for $P$ of degree $2$) are given by $P_1(mX),Q_1(mX)$ and $D_1(mX)$, with $m\neq0$ integer. $\endgroup$ – Leonardo Feb 15 '15 at 18:37
  • $\begingroup$ Very nice -- thank you! -- A table of these polynomials for $n \leq 100$ can be found here. -- Though compare e.g. the polynomial $D = 821559147201x^2+14158405x+61$ you obtain for $n = 61$ with the one for the degree-6-solution ($100x^2-44x+5$) here ... . $\endgroup$ – Stefan Kohl Feb 15 '15 at 20:26
3
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ Nobody said degree $6$ would be 'necessary' -- there are just series where degree $6$ occurs. For example, as you correctly noticed, $n = 29$ and $n = 53$ not only belong to the series with $D = 4x^2+4x+5$, where the solution with $P$ of degree $6$ stems from $\sqrt{D} = [2x+1,\overline{x,1,1,x,4x+2}]$ (odd period length, three $x$-es occur -- thus $P$ has degree $2 \cdot 3 = 6$), but also to the series with the two $D$ you mention and $\sqrt{D} = [13x-8,\overline{2,1,1,2,26x-16}]$ and $\sqrt{D} = [25x-18,\overline{3,1,1,3,50x-36}]$, respectively. $\endgroup$ – Stefan Kohl Jan 27 '15 at 10:20
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Interesting. -- Thank you! If one could show that, say, $r \leq 3$, would this imply that the degree of $P$ is at most $6$? $\endgroup$ – Stefan Kohl Feb 2 '15 at 15:29
  • 1
    $\begingroup$ Exactly. Actually, the integer $r$ is equal to the order of the finite (cyclic) group $R^\times/\Bbb Z[\sqrt{n}]^\times$, where $R$ denotes the ring of integers of the quadratic field $\Bbb Q(\sqrt{n})$. In any case, for a given $n$, the degree of $P$ is bounded; it only remains to prove that this bound does not depend on $n$ (and, ideally, that it equals $3$). $\endgroup$ – Leonardo Feb 2 '15 at 16:24
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As your "sufficiently divisible" $M$, you can just take $b^2$. Then for ${\rm deg} P = 1$, we obtain the very short expressions $D(x) = b^2x^2+2ax+n$, $P(x) = b^2x+a$, $Q = b$. These expressions yield solutions with much smaller coefficients than Leonardo's. -- Thank you very much for this! I have tabulated the polynomials for $n \leq 100$ here. With our setting $M := b^2$, your solution for ${\rm deg} P = 2$ however gets identical to Leonardo's solution. $\endgroup$ – Stefan Kohl Jan 27 '15 at 21:07
  • $\begingroup$ Though I am not sure you are right where you say that for ${\rm deg} P > 2$ there would be "rarely any solutions" -- to me it seems there are plenty of them -- for a list of examples, see here. $\endgroup$ – Stefan Kohl Jan 28 '15 at 0:17
  • $\begingroup$ Hmm ... More than I would have naively guessed. I took the list of primitive solutions to Pell's equation for the first $60$ nonsquares oeis.org/A033313 and solved $T_3(x)=a$. There were rational roots in $12$ cases. I still think the density has to drop to $0$, but I wouldn't have guessed it was so common in the first $60$. $\endgroup$ – David E Speyer Jan 28 '15 at 1:05
  • $\begingroup$ I have checked the first 10000 nonsquares in that sequence, and found that for 1793 of them, $T_3(x)-a$ has a rational root. Thus the density seems roughly the same as for the first 60 which you checked. -- Do you still think the density drops to 0? $\endgroup$ – Stefan Kohl Jan 29 '15 at 0:12
  • $\begingroup$ Furthermore, $T_4(x)-a$ is reducible in $\mathbb{Q}[x]$ for 151 among the first 1000 values of $a$, and $T_5(x)-a$ is reducible for 10 among the first 1000 values of $a$, and $T_6(x)-a$ is reducible for 311 among the first 1000 values of $a$, and $T_7(x)-a$ is reducible for 6 among the first 1000 values of $a$, and $T_8(x)-a$ is reducible for 151 among the first 1000 values of $a$. $\endgroup$ – Stefan Kohl Jan 29 '15 at 0:24
1
$\begingroup$

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$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.