1
$\begingroup$

I've seen some Q&A's here which put light on the continued-fractions approach to finding solutions for the Pell-equation. I'm trying to get familiar with this method to apply it to my style of generalized Pell-equations $$ a^2 + b^2 = D \cdot c^2 \qquad \qquad \text{always with }D=u^2+v^2 \tag 1$$
For many of combinations of $(u,v)$ my understanding suffices to get the correct set of solutions from the convergents of the cont.frac, of $\sqrt D$ , but some combinations give problems, and while the brute-force search gives solutions, my cont.-frac. search gives nothing.

The problematic cases seem to be those when $u=v$.
I start with the ansatz $a=u$ and thus look at solutions of (eq 1) with the constant parameters $(u,v)$ used for some set of solutions $$u^2 + b^2 = (u^2+v^2) \cdot c^2 \qquad \text{solving for integer $b$ and $c$} \tag 2 $$ (Of course, I ignore cases where $(u,v)$ are part of of a pythagorean triple) For instance, with $(u,v)=(2,2)$ I get the c.f.-convergents for $\sqrt D$

  2  3  14  17  82  99  478  577
  1  1   5   6  29  35  169  204

and the solutions of the (eq.2) $$\small \begin{array} {rrr|r} a& b& c& \text{iteration-height} \\ \hline 2 & 2 & 1 & 0.0 \\ 2 & 14 & 5 & 1.00000000000 \\ 2 & 82 & 29 & 2.00000000000 \\ 2 & 478 & 169 & 3.00000000000 \\ 2 & 2786 & 985 & 4.00000000000 \\ 2 & 16238 & 5741 & 5.00000000000 \\ 2 & 94642 & 33461 & 6.00000000000 \\ 2 & 551614 & 195025 & 7.00000000000 \end{array}$$ (here "iteration-height" is the exponent to which I have to take the power of the iteration-matrix to arrive at the solution given in the row).
We see, that the values in $(b,c)$ can be found in the c.f.-convergents above.
This worked for all tested (small combinations) of $(u,v)$ until suddenly just the very small problemparameter $(u,v)=(3,3)$ breaks. The c.f.-convergents are

  4  17  140  577  4756  19601  161564  665857
  1   4   33  136  1121   4620   38081  156944

The list of solutions for (eq.2) found by brute-force is $$\small \begin{array} {rrr|r} a& b& c& \text{iteration-height} \\ \hline 3 & 3 & 1 & 0.0 \\ 3 & 21 & 5 & 0.500000 \\ 3 & 123 & 29 & 1.00000 \\ 3 & 717 & 169 & 1.50000 \\ 3 & 4179 & 985 & 2.00000 \\ 3 & 24357 & 5741 & 2.50000 \\ 3 & 141963 & 33461 & 3.00000 \\ 3 & 827421 & 195025 & 3.50000 \\ 3 & 4822563 & 1136689 & 4.00000 \end{array} $$ but I can't see any relation to the convergents of the continued fraction of $\sqrt D$... (The existence of half-integer values in the iteration-heights indicate that we have actually 2 separate lists of solutions and don't matter much here).


Update
Just found the/a relation using the generalized convergents. Using (in my notation) the "upper gen. cvgts" which occur as list:

***                                ***                                           ***                                                        ***
  4  21  38  55  72  89  106  123  140  717  1294  1871  2448  3025  3602  4179  4756  24357  43958  63559  83160  102761  122362  141963  161564  827421  1493278  2159135  2824992  3490849  4156706  4822563
  1   5   9  13  17  21   25   29   33  169   305   441   577   713   849   985  1121   5741  10361  14981  19601   24221   28841   33461   38081  195025   351969   508913   665857   822801   979745  1136689
     *                         *         *                                   *           *                                            *              *                                                    *

Here the entries marked with *** are true convergents, and the entries marked with * the solutions found by brute-force. end-update


One more example which is working: $(u,v)=(3,7), D=58$.
The first few c.f.-convergents:

  7  8  15  23  38  61  99  1447  1546  2993  4539  7532  12071  19603  286513  306116
  1  1   2   3   5   8  13   190   203   393   596   989   1585   2574   37621   40195

The first few solutions, $$ \small \begin{array} {rrr|r} a& b& c& \text{iteration-height} \\ \hline 3 & 7 & 1 & 0.0 \\ 3 & 297 & 39 & 0.350284 \\ 3 & 12071 & 1585 & 0.700567 \\ 3 & 286513 & 37621 & 1.00000 \\ 3 & 11644479 & 1528995 & 1.35028 \\ 3 & 473255633 & 62141509 & 1.70057 \\ 3 & 11233028671 & 1474968925 & 2.00000 \\ 3 & 456533443377 & 59945777931 & 2.35028 \end{array} $$ Some solutions are found assuming they have common factor $a=u=3$ and multiples of $3$ in the convergents are tested (for instance $(279,39) = 3\cdot (99,13)$).
(Again, the fractional iteration-heights indicate, that we have three intertwined subsequences of solutions here)


The problem seems to occur with all cases $(u,v)$ with $u=v$ except for $u=v \in [2,5,25,???]$

Q: Is there any (possibly obvious) reason for this inconvenient behave and some remedy?

$\endgroup$
2
  • $\begingroup$ Upps, I see now in the $(u,v)=(3,3)$ case, that the first brute-force-found solutions agree to generalized convergents , but still cannot recognize some generalizable rationale behind this... $\endgroup$ Dec 16, 2021 at 13:47
  • $\begingroup$ Hmm, and with $(u,v)=(8,8)$ we have solutions which are not even in the generalized convergents... $\endgroup$ Dec 16, 2021 at 16:43

1 Answer 1

1
$\begingroup$

The problem of finding the sequences of solutions for the "problematic cases" - in my question focused to cases of $u^2+v^2=D$ and $u=v$ such that $D=2u^2$ - seems to be intractable with the tools shown so far.

With the help of heuristics we can find some suggestive scheme which at least reduces the complexity.
Of course, for the combination $(u,v)=(u,u), D=2 u^2$ and the "keys" $[a,b_k,c_k]=[u,b_k,c_k]$ with $u^2+b^2 = D c^2= 2 u^2 c^2$ we find, using brute force, some solutions in small numbers. The first is of course trivial; we must have a first solution as $[a,b,c]=[u,u,1]$ and need only a second one to generate an initial transfer-matrix $T$ which allows then to create the sequence of solutions by $[u,u,1] \cdot T^k$ .
Heuristics gave a simple scheme to compute $T$ directly from the value $u$: $$ \begin{matrix}T_u=\begin{bmatrix}1 & .& .\\. & 3& \frac2u\\. & 4 u& 3 \end{bmatrix} & \to & R_u=\begin{bmatrix} 3& \frac2u\\ 4 u& 3 \end{bmatrix} \end{matrix} \tag 1$$ In the following I reduce the notation to the $2x2$-matrix $R_u$ which contains only the nontrivial part of $T_u$ : $R_u=T_u[2..3,2..3]$ So, having some initial key $[u,1]$ we can construct all further solutions by $$[b_k,c_k] = [u,1] \cdot R_u^k \tag 2$$ Now, by basic assumptions, we do not allow transfer-matrices $R_u$ with fractional values. But, again heuristically, we find, that each $u$-parameter produces a $R_u$ matrix, having fractional entries, but whose $ex$'th-power gives a full integer matrix: $$ R_u ^{ex_u} = S_u \qquad \text{ having $ex_u$ such that $S_u$ is an integer matrix} \tag 3$$

This is a pattern which gives consistent results (which means: solutions of the associated generalized Pell-equation) without referring to very likely intractable compositions of generalized convergents of the continued fraction for $\sqrt D$.

However, still I don't have an analytic formula for the results involved, but a pattern that emerges and helps to reduce the searchspace for solutions.

Here is a subset of solutions which I got by heuristics. The matrices $R_u$ are created following my mentioned heuristic.
For $u=v=2$ we have

u=2 D=   8 ex=1   R=[3, 1; 8, 3]        S=R^ex=[3, 1; 8, 3]

Note: the matrix-notation is that of Pari/GP, which means that a ";" indicates beginning of a new row.

for $u=v \in [2,3,4,6,12]$ we have

 2 D=   8 ex=1   R=[3, 2/ 2;   8, 3]   S=R^ex=[3, 1; 8, 3]
 -----------------------------------------------------------------
 3 D=  18 ex=2   R=[3, 2/ 3;  12, 3]   S=R^ex=[17, 4; 72, 17]
 4 D=  32 ex=2   R=[3, 2/ 4;  16, 3]   S=R^ex=[17, 3; 96, 17]
 6 D=  72 ex=2   R=[3, 2/ 6;  24, 3]   S=R^ex=[17, 2; 144, 17]
12 D= 288 ex=2   R=[3, 2/12;  48, 3]   S=R^ex=[17, 1; 288, 17]
=========================================================================

for $u=v \in [2,5,7,10,14,35,70]$ we have

 2 D=   8 ex=1   R=[3, 1; 8, 3]        S=R^ex=[3, 1; 8, 3]
-----------------------------
 5 D=  50 ex=3   R=[3, 2/ 5;  20, 3]   S=R^ex=[99, 14; 700, 99]      --> krit=5*14=70
 7 D=  98 ex=3   R=[3, 2/ 7;  28, 3]   S=R^ex=[99, 10; 980, 99]
10 D= 200 ex=3   R=[3, 2/10;  40, 3]   S=R^ex=[99, 7; 1400, 99]
14 D= 392 ex=3   R=[3, 2/14;  56, 3]   S=R^ex=[99, 5; 1960, 99]
35 D=2450 ex=3   R=[3, 2/35; 140, 3]   S=R^ex=[99, 2; 4900, 99]
70 D=9800 ex=3   R=[3, 1/35; 280, 3]   S=R^ex=[99, 1; 9800, 99]
=========================================================================

Here we find the pattern, that after we have heuristically found the $ex$ for $u=v=5$ we can immediately conclude the transfermatices for all that $u$ which are divisors of $5 \cdot 14$ where $14$ is the entry $S[1,2]$ and we have for all that $u$ a constant product of $u \cdot S[1,2]$

The next block for illustration is longer, but I'll not continue that more. We find (for $u \in $ divisors of $408 = 8 \cdot 3 \cdot 17$) for $ex=4$

  2 D=   8 ex=1   R=[3, 1; 8, 3]        T2^ex=[3, 1; 8, 3]
-----------------------------
  3 D=  18   ex=2   R=[3, 2/ 3;  12, 3]    S=R^ex=[17, 4;  72, 17]
  4 D=  32   ex=2   R=[3, 2/ 4;  16, 3]    S=R^ex=[17, 3;  96, 17]
  6 D=  72   ex=2   R=[3, 2/ 6;  24, 3]    S=R^ex=[17, 2; 144, 17]
 12 D= 288   ex=2   R=[3, 2/12;  48, 3]    S=R^ex=[17, 1; 288, 17]
-----------------------------
  8 D= 128   ex=4   R=[3, 2/ 8;   32, 3]   S=R^ex=[577, 51;  6528, 577]   --> krit=8*51=8*3*17=408
 17 D= 578   ex=4   R=[3, 2/17;   68, 3]   S=R^ex=[577, 24; 13872, 577]
 24 D=1152   ex=4   R=[3, 1/12;   96, 3]   S=R^ex=[577, 17; 19584, 577]
 34 D=2312   ex=4   R=[3, 1/17;  136, 3]   S=R^ex=[577, 12; 27744, 577]
 51 D=5202   ex=4   R=[3, 2/51;  204, 3]   S=R^ex=[577, 8;  41616, 577]
 68 D=9248   ex=4   R=[3, 1/34;  272, 3]   S=R^ex=[577, 6;  55488, 577]
102 D=20808  ex=4   R=[3, 1/51;  408, 3]   S=R^ex=[577, 4;  83232, 577]
136 D=36992  ex=4   R=[3, 1/68;  544, 3]   S=R^ex=[577, 3; 110976, 577]
204 D=83232  ex=4   R=[3, 1/102; 816, 3]   S=R^ex=[577, 2; 166464, 577]
408 D=...    ex=4   R=[3, 1/204;1632, 3]   S=R^ex=[577, 1; 332928, 577]
=========================================================================

Well, this is an interesting and not too complex pattern. Unluckily it still does not allow to determine the sequences of solutions for some pair $(u,v=u)$ for that type of generalized Pell-equations which are considered here without heuristical search.

So the question is still unresolved, and I hope someone steps in and has possibly a more productive idea...

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .