# a family of Pellian equations

I have a question concering the family of Pellian equations $$x^2 - (k^2+1)y^2 = k^2. \qquad (*)$$

For an integer $k\geq 2$, the equation (*) has at least three classes of solutions in integers, corresponding to the fundamental solutions $(x_0,y_0) = (k, 0)$, $(k^2-k+1, k-1)$, $(k^2-k+1, -(k-1))$. Each fundamental solution induces a sequence (class) of solutions by $$x+\sqrt{k^2+1}y = (x_0+\sqrt{k^2+1}y_0)(k+\sqrt{k^2+1})^{2m}.$$

For certain values of $k$, there are two additional classes of solutions. E.g. for $k=2t^2$, we have also fundamental solutions $(x_0,y_0) = (2t^3+t, \pm t)$, and additional solutions occur also for $k=4s^3-4s^2+3s-1$, for $k=F_{2n}$, and other polynomial or exponential subfamilies. However, I am not able to find any example such that (*) has more than five classes of solutions.

So, I am wondering does it make sense to state the conjecture that for $k\geq 2$, equation (*) always have exactly three or five classes of solutions (e.g. 3 or 5 fundamental solutions). Is there an obvious reason why should (or should not) the number of fundamental solutions of (*) be bounded by an absolute constant (independent on $k$)?

It is easy to see that each fundamental solution $(x_0,y_0)$ has to satisfy $|y_0| < k$, so the conjecture actually says that there is at most one solution of equation (*) with $0 < y < k-1$.

This question is related to the conjecture which says that there does not exist a set of four positive integer with the property that the product of any two of them is 1 greater than a square (see e.g. Section 3.1 of Diophantine m-tuples page and references given there).

-
Let me mention that I have checked "the conjecture" for $k\leq 1000000$. In that range, there are 1045 $k$'s for which this equation has 5 classes of solutions, while for all other $k$'s there are 3 classes. It seems that the number of $k$'s such that $k \leq N$ and the equation has 5 classes of solutions is $O(\sqrt{N})$ (it seems that, asymptotically, the most on such cases comes from $k=2t^2$). –  duje Feb 24 '12 at 18:15
Just a simple observation: this equation is equivalent to $x^2+1=(y^2+1)(k^2+1)$, i.e., when the product of two numbers of the form $m^2+1$ is again a number of this form. –  Max Alekseyev Nov 13 '12 at 23:41

Oh, I think the answer is definitely yes!

Let $\{k \to x,y\}$ be any solution of $x^2 - (k^2+1)y^2 = k^2$, and let $K$ be the set of $k$ for which a solution has $0 < k < y-1$. In a paper recently submitted to Glasnik Matematicki we call these solutions exceptional solutions. Andrej's conjecture is that for any $k$ there is at most 1 exceptional solution.

One interesting result we obtain is that, if $k \in K$, then $y < (2 - \sqrt{3})k$.

A particular feature of this Pell equation is its symmetry wrt $k$ and $y$. These are interchangeable, so for any solution $\{k \to x,y\}$ there is a corresponding solution $\{y \to x,k\}$.

It follows that if $k \neq y \pm{1}$, then either $k \in K$ or $y \in K$.

Now, for any $k \geq 2$, we have 3 particular solution classes $(x_n, y_n)$ with $y_0 = \{0, k-1, -(k-1)\}$. For any $n > \{0, 0, 1\}$ we have $y_n > k-1$ and so $\{y_n \to x_n,k\}$ is exceptional, ie. $y_n \in K$.

We also need to consider $k=1$, for which there is just the one class with $(x_0, y_0) = (1, 0)$ , $(x_1, y_1) = (3, 2)$ and so for any $n > 1$ we have $y_n \in K$. For example $(x_2, y_2) = (17, 12)$ from which we obtain exceptional solution $\{12 \to 17, 1\}$, and so $12 \in K$.

In our paper we call the corresponding set of exceptional solutions "Type 1". But here let us simply define the set $K_1$ to be all of these $y_n > k$ that we find from these 3 classes for any $k > 1$, and from the one class for $k = 1$.

One property shared by all type 1 solutions, ie $\{k \to x, y\}$ with $k \in K_1$ is that either $(y^2 +1) | (x+y)$ or $(y^2 + 1) |(x-y)$.

Now, for any $k \in K_1$ we have a corresponding $\{k \to x,y\}$ for which our Pell eqn has 2 additional solution classes, with fundamental solutions $(x_0, y_0) = (x, \pm y)$. For any $n > \{0,1\}$ we then have $y_n > k-1$ and so $\{y_n \to x_n, k\}$ is exceptional, ie $y_n \in K$.

And of course we can apply the same process to any of these new $y_n$ ad infinitum, each $y_n$ seeding a forest of others. For example, just considering $n = 1$ alone in each case, from $\{8 \to 18,\pm{2}\}, 8 \in K_1$ we obtain $\{546 \to 4402,8\}$ and $\{30 \to 242,8\}$, so $546, 30 \in K$, and from $\{30 \to 242, \pm{8}\}$ we get $\{28928 \to 868322,242\}$ and $\{112 \to 3362,30\}$, so $28928, 112 \in K$.

We call these "Type 2" solutions, so let's define $K_2$ to be all of the $y_n$ found this way. These do not have the divisibility property that was noted above for the $y_n \in K_1$.

In the paper we show that all exceptional solutions can be enumerated recursively in this fashion, ie. that $K = K_1 \cup K_2$. This is done by showing any $k \in K$ can be traced back to a root in $K_1$.

The enumeration algorithm is given below. Solution classes are referred to as $0, -1, +1$, the interpretation of which I hope is reasonably clear!

Proc Enum_K:

Enum_K1(1,0)

for k = 2 to $\infty$
Enum_K1(k, 0)
Enum_K1(k, +1)
Enum_K1(k, -1)

Proc Enum_K1(k, class):
set $(x_0, y_0), (x_1, y_1)$ according to class
n1 = if (class = -1 or k = 1) then 2 else 1

for n = n1 to $\infty$
add $y_n$ to $K_1$
Enum_K2($y_n$, +1)
Enum_K2($y_n$, -1)

Proc Enum_K2(k, class):
set $(x_0, y_0), (x_1, y_1)$ according to class
n1 = if (class = -1) then 2 else 1

for n = n1 to $\infty$
add $y_n$ to $K_2$
Enum_K2($y_n$, +1)
Enum_K2($y_n$, -1)

To generate the solution sequences in any class, we note that each class has the same recurrence relation:
$R = 2k^2 + 1$
$x_n = 2Rx_{n-1} - x_{n-2}$
$y_n = 2Ry_{n-1} - y_{n-2}$

but of course have different initial conditions:
$R = 2k^2 + 1, S = 2k, D = k^2 + 1$

$K_1, class 0: (x_0, y_0) = (k, 0), (x_1, y_1) = (kR, kS)$
$K_1, class +: (x_0, y_0) = (k^2-k+1, k-1)$
$K_1, class -: (x_0, y_0) = (k^2-k+1,1-k)$
$K_2, class +: (x_0, y_0) = (x_n, +y_n)$ for any $y_n \in K_1 \cup K_2$
$K_2, class -: (x_0, y_0) = (x_n, -y_n)$ " "

and in all cases above $(x_1, y_1)$ satisfy
$x_1 = Rx_0 + DSy_0$
$y_1 = Ry_0 + Sx_0$

Now if Andrej's conjecture is true, and we believe it is, then each operation "add $y_n$" always adds a new $y_n$ to its list, and the two lists $K_1, K_2$ have no common elements.

An implementation of Enum_K with a bailout parameter finds that with $k <10^6$ we have $|K_1| = 882, |K_2| = 163, |K| = 1045$, and that every $k$ enumerated was unique. This agrees with Andrej's figure.

-
For $k < 2^32$ we have $|K_1| = 48717, |K_2| = 1657, |K| = 50374$. These were all verified to be unique, so Andrej's conjecture is confirmed for $k < 2^32$, given that we accept that the enumeration process finds all $k$. –  Jim White Jan 12 '13 at 10:38
There are too many $k \in K$ to make verification practical for $k < 2^64$, but for the record we believe that $|K_1| = 3,040,378,747$ and $|K_2| = 1,725,632$. –  Jim White Jan 12 '13 at 10:39
My co-author Keith Matthews has made available a set of slides he used when giving a recent presentation based on our submitted paper. These can be found at numbertheory.org/pdfs/dujella_slides.pdf –  Jim White Jan 12 '13 at 10:47
Apologies, the bounds for $k$ above should read $2^{32}$ and $2^{64}$ –  Jim White Jan 12 '13 at 10:49
Corrected mistake in the statement "One property shared by all $y_n \in K_1 \ldots$. The divisibility property involves $y_n^2 + 1$, not $y_n$. –  Jim White Jan 14 '13 at 14:47

This is an interesting question. Let me explain why I believe that the answer is no.

Rewrite the equation in the form $$(x-k)(x+k) = (k^2+1)y^2.$$ Interpreting this as an equation in the polynomial ring ${\mathbb Z}[k]$ and using unique factorization you end up with equations of the form $$x - k = (k^2+1)A^2, \quad x + k = B^2,$$ which implies $$2k = B^2 - (k^2+1)A^2.$$ The solution $A = 1$ and $B = k+1$ gives rise to one of yours.

In order to be able to find a lot more fundamental solutions you will have to substitute $k = f(t)$ for a polynomial $f$ that makes $k^2+1$ reducible. the simplest choice is $k = 2t^2$ since $$k^2+1 = 4t^4 + 1 = (2t^2+1)^2 - 4t^2 = (2t^2+2t+1)(2t^2-2t+1).$$ Going through the game above will reveal your additional solution in this case.

If you substitute $k = t + 2t^3$ (I hope I remember my calculations well), the polynomial $k^2+1$ splits into three quadratic factors. Whether the resulting Pell type equations have more solutions is difficult to check. But my impression is that of you can find many substitutions for which $k^2+1$ splits into many factors, chances are that you get more than 2*2+1 = 5 fundamental solutions. Where's Noam when you need him?

-
I swapped $A$ and $B$, it was not correct as it was. –  Aaron Meyerowitz Jan 14 '13 at 12:23

I will illustrate the enumeration process with some examples in order to make clear the structure described above.

We start with $k = 1$, the only case with a single solution class $(k, 0)$. We have $k^2+1 = 2$ and $k^2 = 1$. Here is a partial enumeration of all solutions to $x^2 - 2y^2 = 1$:

       n            x            y
0            1            0
1            3            2
2           17           12
3           99           70
4          577          408
5         3363         2378


Because of the symmetry of the equation wrt $k$ and $y$ we know that each pair $(x_n, y_n)$ for $n > 1$ means that $\{y_n \to x_n, 1\}$ is an exceptional solution. For example, we can see that $17^2 - (12^2 + 1).1^2 = 12^2$. Clearly $1 < 12-1$, and so $k = 12$ has an exceptional solution, and because it came from an enumeration of a root class $(1, 0)$ it is a type-1 solution and so we add $12$ to the set $K_1$.

For all $k > 1$ we have 3 root classes, $(k, 0)$, $(k^2-k+1, k-1)$ and $(k^2-k+1, -k+1)$. Partial enumerations for $k=2$ are shown below:

       n            x            y
0            2            0
1           18            8
2          322          144
3         5778         2584
4       103682        46368
5      1860498       832040

n            x            y
0            3            1
1           47           21
2          843          377
3        15127         6765
4       271443       121393

n            x            y
0            3           -1
1            7            3
2          123           55
3         2207          987
4        39603        17711
5       710647       317811


Each $y_n$ where $n>0$ (or $n>1$ for the 3rd class) provides an exceptional solution $\{y_n \to x_n, 2\}$, and so each $y_n$ is added to $K_1$.

Now every value we add to $K_1$ is an exceptional solution of the form $\{k \to x,y\}$, so for each $k$ in $K_1$ we have an additional pair of conjugate solution classes $(x, \pm{y})$. Assuming the Dujella conjecture is true, these will always be the 4th and 5th classes.

We simply enumerate these classes in similar fashion, except we add the new $y_n$ values to the list $K_2$, since they come from these additional classes for $k \in K_1$, not from the 3 root classes. For example taking exceptional solution $\{18 \to 8,2\}$, we enumerate the classes $(8, 2)$ and $(8, -2)$ for $k=18$:

       n            x            y
0            18           2
1          4402         546
2       1135698      140866
3     293005682    36342882

n            x            y
0            18          -2
1           242          30
2         62418        7742
3      16103602     1997406


Again, every $(x_n, y_n)$ for $n>0$ gives a new exceptional solution $\{y_n \to x_n,18\}$, and so we add each $y_n$ to $K_2$. And every item $k$ we add to $K_2$ represents 2 new classes for that $k$, so we can apply the same procedure recursively to each and every one.

The reason that I have kept $K_1$ and $K_2$ as two distinct lists is that the members of $K_1$ have properties not shared by $K_2$. The divisibility property noted above is one such property, another is the fact that all of the root classes for any $k$, from which we poulate $K_1$, have explicit polynomial descriptions, which lend themselves to the sort of analysis that we can't readily apply to $K_2$.

For example, we can (I believe) deduce from the properties of these polynomials that every operation "add $y_n$ to $K_1$" provides a unique value. It remains to be seen whether we can prove the same holds for $K_2$.

-