User jim white - MathOverflow

Decision problem wrt Pairs of Polynomials with Integer Coefficients

2013-01-22T00:16:59Z

Given two arbitrary polynomials $G(x)$ and $H(y)$, with integer coefficents, are there any circumstances in which it is possible to decide whether or not $G(x) = H(y)$ has solutions with $x, y \in \mathbb Z$?

Square Roots of Unity modulo N^2

2013-01-18T10:21:47Z

My question relates to square roots of unity modulo N, ie $r^2 = 1 \mod N$.

I have an efficient algorithm for obtaining these for arbitrary $N$. But for a given $N$ what I really want is to obtain the roots for all $N_f = \frac {N^2}{f^2}$ for all $f|N$.

My question is simply this - can these all be deduced from the square roots of unity mod $N$? Or do I need multiple invocations of my root finder?

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

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.

Uniqueness of values in recurrence relations

2013-01-07T07:35:30Z

Given an integer $k > 1$ , define the sequences $X(k,n), Y(k,n)$ as follows:

$a=4k-2,$ $y_0 = 1,$ $y_1 = a + 1,y_n = ay_{n-1} - y_{n-2}$

$b = 4k + 2,$ $ x_0 = 1,$ $x_1 = b - 1,$ $x_n = bx_{n-1} - x_{n-2}$

For example, with $k = 2$ we get

$y_j = 7, 41, 239, 1393, \ldots$

$x_j = 9, 89, 881, 8721, \ldots$

A simple question arises, as to whether there exist $\{k, i, j\}$ such that $X(k,i) = Y(k,j)$ ?

This might well be an open question, and perhaps inappropriate here, but I have trawled the web for many hours and have found no evidence that anybody has even considered it.

Computational experiments suggest that in fact an even stronger result is possible, ie. that there are no $\{k_1, k_2, i>1, j>1\}$ with $X(k_1,i) = Y(k_2,j)$ .

In other words, with the exception of $x_1, y_1$ which can be any odd number > 7, all values generated by these sequences appear to be unique.

Any suggestions as to a way to attack this question would be greatly appreciated!

Update: There are explicit proofs that for $k = 2, 3$ there can be no $X(k,i) = Y(k,j)$ , so we can restrict the question to $k > 3$ . Sadly these proofs are not extendable to other k

Answer by Jim White for Greatest Prime Factors: For any prime p, is there an integer C such that for any x >= C, all but 1 integer in the sequence x+1, x+2, ..., x+p has a greatest prime factor > p.

2013-01-11T00:40:45Z

I don't know how far Larry went in pursuing this problem, but this touches on a topic I've spent some time on, ie. Lehmer's method.

Let $S_j$ be the maximum $S$ for which the pair {$S, S+j$} is $p$-smooth, and let $S_m$ be the maximum of ${S_1, S_2 \ldots S_p}$. Also let k = $\pi(p)$, ie. the number of primes $\leq p$.

It follows then that the minimal $C$ for which the desired property holds is $C = S_m$.

Determining each $S_j$ is not so straight-forward, apart from the cases $j=1, 2$, which are a direct application of Lehmer's method, which provides for the enumeration of all smooth pairs of the form ${S, S+1}$, ${S, S+2}$, by solving roughly $2^k$ standard Pell equations, ie. $x^2 - Dy^2 = 1$, for $D$ ranging over all combinations of the $k$ primes $\leq p$. Both sets of pairs can be obtained with a single pass.

For $3 \leq j \leq p$, however, things are not so simple. Lehmer did not address these cases, and perhaps we can understand why. We can in fact extend Lehmer's method to identify smooth pairs ${S, S+j}$, but this requires solving $x^2 - Dy^2 = j^2$, again for all $2^k$ values of $D$.

The good news is that these equations can be solved from the $x^2 - Dy^2 = 1$ solutions, so that the number of continued fractions we have to compute is still the same. See John Robertson's article on the LMM method (Lagrange-Matthews-Mollin) at JPR_Pell.

Note that there can be multiple solution classes for any $j$.

The bad news is that Lehmer's main achievement, by which he is able to reduce the number of Pell equations from $3^k$ to $2^k$, is not applicable for $j \geq 3$. For $j = 1, 2$ he showed that any smooth pair that does not turn up as a fundamental solution $(x_1, y_1)$ will be found at some $(x_m, y_m)$ with $m \leq (p+1)/2$. This is because the $y_n$ values form a Lucas sequence, and so $y_1$ divides all $y_n$. Thus, if $y_1$ isn't smooth, neither will be any other $y_n$. And if $y_1$ is smooth, we only need check a limited number of $y_n$.

Sadly, the multiple solutions in any class of solutions to $x^2 - Dy^2 = N$, $(N=j^2)$, do not have these Lucasian properties. So we don't know how many $(x_n, y_n)$ to look at, and we can't assume that $y_1$ not being smooth means that $y_2$ isn't either.

We could of course revert to the original Störmer method, where we solve for $D$ being all possible combinations of the $k$ primes to the power $\{ 0, 1, 2 \}$ , thus requiring roughly $3^k$ equations to be solved. That's very slow, but guarantees that smooth pairs occur only as fundamental solutions.

Alternately, it might well be that $S_1 > S_j$ always, in which case we would avoid all of these complications, solving only the standard equations $x^2 - Dy^2 = 1$. I have not yet done any investigation of this question, but I remember that generally $S_2 < S_1$, so this property can't be ruled out.

Finally, I would like to know if Larry looked into the method described above involving $X^3 - Y^3 = C$, and if so, how it works.

Answer by Jim White for Consecutive integers with no large prime factors

2013-01-10T21:04:02Z

Yuta is correct, Størmer's method, or preferably, D.H. Lehmer's 1963 refinement of that method, applies to a finite set of primes.

If the set contains $k$ primes, then you have $2^k-1$ Pell equations to solve (Størmer's original method involved solving $3^k$ Pell's.

I have had a particular interest in this subject for some years, and have provided most of the high-end values at OEIS, see http://oeis.org/A002072. I intend to raise some questions arising from this work in a new posting here at mathoverflow.

But to Yuta's original question, the only way I can think of to identify smooth numbers in a particular range is to use a smart sieving algorithm. But if the interval is really large, and the number of primes is also very large, this may not be practical.

By the way, in Lehmer's paper, "Størmer" appears as "Störmer", I have yet to determine which is correct! I suspect Lehmer was probably correct.

Answer by Jim White for Uniqueness of values in recurrence relations

2013-01-10T10:43:44Z

Aaron prompted me to investigate the behaviour of gaps in the sequences $X(k), Y(k)$, or equivalently $U(m), V(m')$ with $m = 4k-2, m' = 4k+2$, with $k>3$.

I found that, for any k, the distance $D_j$ of any $U_j$ to the nearest $V_i$ is nearly always increasing, with $log_m(D_j) = j - \epsilon$. The only time the distance decreased was at a "sync point", ie a point j where $V_i < U_j < U_{j+1} < V_{i+1}$. The $D_j, D_{j+1}$ values tend to be very close together and sometimes $D_{j+1}$ is marginally less than $D_j$.

Given this trend, I wonder whether the case for "no coincidences" is strengthened. If coincidences were possible, then wouldn't I expect to see $D_j$ fluctuate?

Answer by Jim White for Uniqueness of values in recurrence relations

2013-01-09T06:56:31Z

Ok, Aaron has generalised my sequences $X(k), Y(k)$ to $U(m), V(m)$ for arbitrary m > 2.

It will be found that any pair $(u, v) = (U_j(m), V_j(m))$ corresponds to a solution to the generalised Pell equation

$(m+2)v^2 - (m-2)u^2 = 4$

If $m = 4k$ then this reduces to $(2k+1)v^2 - 2ku^2 = 2$ , and for $m = 4k-2$ we get $kv^2 - (k-1)u^2 = 1$ .

This explains why cases $m = 3, 4, 6$ produce convergents to $\sqrt{5}, \sqrt{3}, \sqrt{2}$ respectively, since they correspond to regular Pell equations:

$m=3: 5v^2 - u^2 = 4$
$m=4: 3v^2 - u^2 = 2$
$m=6: 2v^2 - u^2 = 1$

My original question is thus restated as "Does $U_j(4k-2) = V_i(4k+2)$ have any solutions?". Which itself can be restated as, are there any solutions to the simultaneous equations:

$kx^2 - (k-1)y^2 = 1$
$(k+1)y^2 - kz^2 = 1$

with k > 1, noting again that cases k = 2, 3 have been resolved in the negative.

And the motivating question is this: do there exist squares in arithmetic progression that can be written $(k-1)n +1, kn+1, (k+1)n+1$ , with $n > 0, k > 1$?

If so, they necessarily correspond to solutions ${x,y,z}$ of these equations, with $n = (x^2 -1)/(k-1) = (y^2 -1)/k = (z^2-1)/(k+1)$

Answer by Jim White for Uniqueness of values in recurrence relations

2013-01-08T00:43:54Z

Thanks, Aaron. Your comment has reminded me that I have been negligent in the computational searches conducted so far, in that I have failed to report any information on minimum distances encountered. I will attend to that.

By the way, I have reversed the definitions of X and Y above as they were the opposite of what I have in all existing code and research notes. My apologies!

In terms of k the first few polynomials are

$Py_1 = 4k - 1$
$Px_1 = 4k + 1$

$Py_2 = 16k^2 - 12k + 1$
$Px_2 = 16k^2 + 12k + 1$

$Py_3 = 64k^3 - 80k^2 + 24k - 1$
$Px_3 = 64k^3 + 80k^2 + 24k + 1$

$Py_4 = 256k^4 - 448k^3 + 240k^2 - 40k + 1$
$Px_4 = 256k^4 + 448k^3 + 240k^2 + 40k + 1$

If we define the distance polynomial $D_{j,i} = Py_j - Px_i$ then $D_{2,1} = 16k^2 - 16k$ so the quadratic case is disposed of, as you say.

We can also rule out the cubic case, and in fact all odd j. We have

$D_{3,1} = 64k^3 - 80k^2 + 20k - 2$
$D_{3,2} = 64k^3 - 96k^2 + 12k - 2$

For all odd j we get even coefficients and $c_0 = -2$, so no $D_{2e+1,i}$ can have an integer root $k > 1$ .

For even j we get polys like these:

$D_{4,1} = 56k^4 - 448k^3 + 240k^2 - 44k$
$D_{4,2}= 256k^4 - 448k^3 + 224k^2 - 52k$
$D_{4,3} = 256k^4 - 512k^3 + 160k^2 - 64k$

What I'm hoping to find is some magic property for even j that will tell us that all $D_{2e,i}$ are either irreducible or have a single integer root $k=1$ .

Since $Y(1,j) = 3,5,7 \ldots$ , all of $X(1,i) = 5, 29, 169 \ldots$ are to be found in $Y(1,j)$ so the corresponding $D_{14,2}, D_{84,3} $ etc will all have root $k=1$ .

I suspect that all other D are irreducible, but these isolated exceptions are a bit of a fly in the ointment!

Oh yes, and I can tell you that a search on all pairs of sequences $Y(k,j), X(k,i)$ revealed no match for a rather staggering j up to 100,000. For a given depth limit j < J, such a search is finite, since beyond a certain k we find that all $Y(k,J) > X(k,J-1)$ and so we need look no further.

It follows then that the proposition, that all $D_{j,i}$ are either irreducible or have a single integer root $k=1$ is true for all j < 100,000.

Comment by Jim White

2013-01-22T00:43:00Z

If only it were that simple! :)

Comment by Jim White

2013-01-20T10:23:32Z

BTW, I believe the RHS above should be $-2s\lambda$

Comment by Jim White

2013-01-18T15:07:57Z

Thank you very much, that helps, and I can see how it extends to $N^2/f^2$.

Comment by Jim White

2013-01-18T14:35:23Z

If that proviso makes this a trivial question, my apologies, and please could I have a reference?

Comment by Jim White

2013-01-18T14:32:01Z

We can assume N is factorable, ie we know all $f|N$. @Felipe, I don't see how Hensel helps with this specific problem.

Comment by Jim White

2013-01-14T14:47:59Z

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

Comment by Jim White

2013-01-12T11:38:12Z

I ask because I've always been interested in investigating an extension to Lehmer's method as described above, but have had no particular motivation to do so.

Comment by Jim White

2013-01-12T10:49:52Z

Apologies, the bounds for $k$ above should read $2^{32}$ and $2^{64}$

Comment by Jim White

2013-01-12T10:47:57Z

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

Comment by Jim White

2013-01-12T10:39:53Z

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

Comment by Jim White

2013-01-12T10:38:05Z

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

Comment by Jim White

2013-01-12T03:12:54Z

I'm kind of preoccupied with a couple of other questions, so I don't quite know what you mean by "patterns like A213523". This could just be attention-deficit on my part, but can you explain in more detail what you are looking for?

Comment by Jim White

2013-01-12T03:00:25Z

You are absolutely right. Indeed, within Lehmer's paper, it's only in the title that an umlaut is used, within the text proper it's always "Størmer". Apologies to Wiki and anybody else I might have inadvertently offended! :-)

Comment by Jim White

2013-01-11T02:40:09Z

I meant $(pS_1, pS_1 + p)$. You can't edit comments!

Comment by Jim White

2013-01-11T02:38:57Z

Ah, but then again, we might still get lucky, for perhaps our $S_m$ is in fact always $(pS_1, pS_1 + p).