a family of Pellian equations - MathOverflow

a family of Pellian equations

2012-02-19T10:51:19Z

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

Answer by Franz Lemmermeyer for a family of Pellian equations

2012-02-24T17:54:33Z

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?

Answer by Jim White for a family of Pellian equations

2013-01-12T09:20:20Z

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.

Answer by Jim White for a family of Pellian equations

2013-01-16T06:57:19Z

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