User jim white - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T08:11:57Z http://mathoverflow.net/feeds/user/30445 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119524/decision-problem-wrt-pairs-of-polynomials-with-integer-coefficients Decision problem wrt Pairs of Polynomials with Integer Coefficients Jim White 2013-01-22T00:16:59Z 2013-01-22T02:27:59Z <p>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$?</p> http://mathoverflow.net/questions/119250/square-roots-of-unity-modulo-n2 Square Roots of Unity modulo N^2 Jim White 2013-01-18T10:21:47Z 2013-01-20T11:56:11Z <p>My question relates to square roots of unity modulo N, ie $r^2 = 1 \mod N$.<br><br> 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$.<br><br> 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?</p> http://mathoverflow.net/questions/88929/a-family-of-pellian-equations/119044#119044 Answer by Jim White for a family of Pellian equations Jim White 2013-01-16T06:57:19Z 2013-01-16T10:03:43Z <p>I will illustrate the enumeration process with some examples in order to make clear the structure described above.<br><br></p> <p>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 <code>$x^2 - 2y^2 = 1$</code>: <br><br><blockquote><pre> <i> n x y</i> 0 1 0 1 3 2 2 17 12 3 99 70 4 577 408 5 3363 2378 </pre></blockquote><br><br> Because of the symmetry of the equation wrt $k$ and $y$ we know that each pair $(x_n, y_n)$ for <code>$n &gt; 1$</code> means that <code>$\{y_n \to x_n, 1\}$</code> is an exceptional solution. For example, we can see that <code>$17^2 - (12^2 + 1).1^2 = 12^2$</code>. Clearly <code>$1 &lt; 12-1$</code>, 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$. <br><br> For all <code>$k &gt; 1$</code> 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: <br><br><blockquote><pre> <i> n x y</i> 0 2 0 1 18 8 2 322 144 3 5778 2584 4 103682 46368 5 1860498 832040</p> <p><i> n x y</i> 0 3 1 1 47 21 2 843 377 3 15127 6765 4 271443 121393</p> <p><i> n x y</i> 0 3 -1 1 7 3 2 123 55 3 2207 987 4 39603 17711 5 710647 317811 </pre></blockquote><br><br> <br><br> Each $y_n$ where <code>$n&gt;0$</code> (or <code>$n&gt;1$</code> for the 3rd class) provides an exceptional solution <code>$\{y_n \to x_n, 2\}$</code>, and so each $y_n$ is added to $K_1$.<br><br> Now every value we add to $K_1$ is an exceptional solution of the form <code>$\{k \to x,y\}$</code>, so for each $k$ in $K_1$ we have an additional pair of conjugate solution classes <code>$(x, \pm{y})$</code>. Assuming the Dujella conjecture is true, these will always be the 4th and 5th classes.<br><br> 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 <code>$\{18 \to 8,2\}$</code>, we enumerate the classes $(8, 2)$ and $(8, -2)$ for $k=18$:</p> <p><br><br> <blockquote><pre> <i> n x y</i> 0 18 2 1 4402 546 2 1135698 140866 3 293005682 36342882</p> <p><i> n x y</i> 0 18 -2 1 242 30 2 62418 7742 3 16103602 1997406 </pre></blockquote><br><br> Again, every $(x_n, y_n)$ for <code>$n&gt;0$</code> gives a new exceptional solution <code>$\{y_n \to x_n,18\}$</code>, 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.<br><br> 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$.<br><br> 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$.</p> http://mathoverflow.net/questions/88929/a-family-of-pellian-equations/118718#118718 Answer by Jim White for a family of Pellian equations Jim White 2013-01-12T09:20:20Z 2013-01-15T06:14:25Z <p>Oh, I think the answer is definitely yes!<br><br> <br> Let <code>$\{k \to x,y\}$</code> 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 <code>$0 &lt; k &lt; y-1$</code>. In a paper recently submitted to <i>Glasnik Matematicki</i> we call these solutions <i>exceptional</i> solutions. Andrej's conjecture is that for any $k$ there is at most 1 exceptional solution. <br><br>One interesting result we obtain is that, if <code>$k \in K$</code>, then <code>$y &lt; (2 - \sqrt{3})k$</code>. <br><br>A particular feature of this Pell equation is its symmetry wrt $k$ and $y$. These are interchangeable, so for any solution <code>$\{k \to x,y\}$</code> there is a corresponding solution <code>$\{y \to x,k\}$</code>. <br><br> It follows that if $k \neq y \pm{1}$, then either $k \in K$ or $y \in K$. <br><br> Now, for any $k \geq 2$, we have 3 particular solution classes <code>$(x_n, y_n)$</code> with <code>$y_0 = \{0, k-1, -(k-1)\}$</code>. For any <code>$n &gt; \{0, 0, 1\}$</code> we have <code>$y_n &gt; k-1$</code> and so <code>$\{y_n \to x_n,k\}$</code> is exceptional, ie. <code>$y_n \in K$</code>. <br><br> 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 <code>$\{12 \to 17, 1\}$</code>, and so $12 \in K$. <br><br> 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 <code>$y_n &gt; k$</code> that we find from these 3 classes for any <code>$k &gt; 1$</code>, and from the one class for $k = 1$. <br><br> One property shared by all type 1 solutions, ie <code>$\{k \to x, y\}$</code> with $k \in K_1$ is that either $(y^2 +1) | (x+y)$ or $(y^2 + 1) |(x-y)$. <br><br> Now, for any $k \in K_1$ we have a corresponding <code>$\{k \to x,y\}$</code> for which our Pell eqn has 2 additional solution classes, with fundamental solutions <code>$(x_0, y_0) = (x, \pm y)$</code>. For any <code>$n &gt; \{0,1\}$</code> we then have <code>$y_n &gt; k-1$</code> and so <code>$\{y_n \to x_n, k\}$</code> is exceptional, ie $y_n \in K$. <br><br> And of course we can apply the same process to any of these new $y_n$ <i>ad infinitum</i>, each $y_n$ seeding a forest of others. For example, just considering $n = 1$ alone in each case, from <code>$\{8 \to 18,\pm{2}\}, 8 \in K_1$</code> we obtain <code>$\{546 \to 4402,8\}$</code> and <code>$\{30 \to 242,8\}$</code>, so $546, 30 \in K$, and from <code>$\{30 \to 242, \pm{8}\}$</code> we get <code>$\{28928 \to 868322,242\}$</code> and <code>$\{112 \to 3362,30\}$</code>, so $28928, 112 \in K$. <br><br> 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$. <br><br>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$. <br><br>The enumeration algorithm is given below. Solution classes are referred to as $0, -1, +1$, the interpretation of which I hope is reasonably clear! <br><br></p> <p><b>Proc <i>Enum_K:</i></b><br><blockquote> Enum_K1(1,0)<br><br> for k = 2 to <code>$\infty$</code><br><blockquote> Enum_K1(k, 0)<br> Enum_K1(k, +1)<br> Enum_K1(k, -1)</blockquote></blockquote> <br><br> <br><br> <b>Proc <i>Enum_K1(k, class):</i></b><br><blockquote> set $(x_0, y_0), (x_1, y_1)$ according to class<br> n1 = if (class = -1 or k = 1) then 2 else 1<br><br> for n = n1 to $\infty$<br><blockquote> add $y_n$ to $K_1$<br> Enum_K2($y_n$, +1)<br> Enum_K2($y_n$, -1)</blockquote></blockquote> <br><br> <br><br> <b>Proc <i>Enum_K2(k, class):</i></b><br><blockquote> set $(x_0, y_0), (x_1, y_1)$ according to class<br> n1 = if (class = -1) then 2 else 1<br><br> for n = n1 to $\infty$<br><blockquote> add $y_n$ to $K_2$<br> Enum_K2($y_n$, +1)<br> Enum_K2($y_n$, -1)</blockquote></blockquote> <br><br> <br><br> To generate the solution sequences in any class, we note that each class has the same recurrence relation: <br><blockquote> $R = 2k^2 + 1$<br> $x_n = 2Rx_{n-1} - x_{n-2}$<br> $y_n = 2Ry_{n-1} - y_{n-2}$<br> </blockquote> <br>but of course have different initial conditions:<br><blockquote> $R = 2k^2 + 1, S = 2k, D = k^2 + 1$<br><br> $K_1, class 0: (x_0, y_0) = (k, 0), (x_1, y_1) = (kR, kS)$<br> $K_1, class +: (x_0, y_0) = (k^2-k+1, k-1)$<br> $K_1, class -: (x_0, y_0) = (k^2-k+1,1-k)$<br> $K_2, class +: (x_0, y_0) = (x_n, +y_n)$ for any $y_n \in K_1 \cup K_2$<br> $K_2, class -: (x_0, y_0) = (x_n, -y_n)$ " "<br> <br>and in all cases above $(x_1, y_1)$ satisfy<br><blockquote> $x_1 = Rx_0 + DSy_0$<br> $y_1 = Ry_0 + Sx_0$<br> </blockquote></blockquote> <br><br> <br><br> Now if Andrej's conjecture is true, and we believe it is, then each operation "<i>add</i> $y_n$" always adds a new $y_n$ to its list, and the two lists $K_1, K_2$ have no common elements. <br><br> An implementation of <i>Enum_K</i> with a bailout parameter finds that with <code>$k &lt;10^6$</code> we have $|K_1| = 882, |K_2| = 163, |K| = 1045$, and that every $k$ enumerated was unique. This agrees with Andrej's figure. <br><br></p> http://mathoverflow.net/questions/118247/uniqueness-of-values-in-recurrence-relations Uniqueness of values in recurrence relations Jim White 2013-01-07T07:35:30Z 2013-01-12T11:06:35Z <p>Given an integer <code>$k &gt; 1$</code>, define the sequences <code>$X(k,n), Y(k,n)$</code> as follows: <br><br></p> <p><code>$a=4k-2,$</code> <code>$y_0 = 1,$</code> <code>$y_1 = a + 1,y_n = ay_{n-1} - y_{n-2}$</code> <br><br></p> <p><code>$b = 4k + 2,$</code> <code>$x_0 = 1,$</code> <code>$x_1 = b - 1,$</code> <code>$x_n = bx_{n-1} - x_{n-2}$</code></p> <p><br><br> For example, with <code>$k = 2$</code> we get </p> <p><code>$y_j = 7, 41, 239, 1393, \ldots$</code></p> <p><code>$x_j = 9, 89, 881, 8721, \ldots$</code></p> <p>A simple question arises, as to whether there exist <code>$\{k, i, j\}$</code> such that <code>$X(k,i) = Y(k,j)$</code>?</p> <p>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.</p> <p>Computational experiments suggest that in fact an even stronger result is possible, ie. that there are no <code>$\{k_1, k_2, i&gt;1, j&gt;1\}$</code> with <code>$X(k_1,i) = Y(k_2,j)$</code>.</p> <p>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.</p> <p>Any suggestions as to a way to attack this question would be greatly appreciated!</p> <p>Update: There are explicit proofs that for <code>$k = 2, 3$</code> there can be no <code>$X(k,i) = Y(k,j)$</code>, so we can restrict the question to <code>$k &gt; 3$</code>. Sadly these proofs are not extendable to other <i>k</i></p> http://mathoverflow.net/questions/106738/greatest-prime-factors-for-any-prime-p-is-there-an-integer-c-such-that-for-any/118592#118592 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. Jim White 2013-01-11T00:40:45Z 2013-01-11T00:54:41Z <p>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.<br><br> 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 <i>k</i> = $\pi(p)$, ie. the number of primes $\leq p$.<br><br> It follows then that the minimal $C$ for which the desired property holds is $C = S_m$. <br><br> 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.<br><br> 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$.<br><br> 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 <a href="http://www.jpr2718.org/pell.pdf" rel="nofollow">JPR_Pell</a>.<br><br> Note that there can be multiple solution classes for any $j$.<br><br> 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$ <b><i>is</b></i> smooth, we only need check a limited number of $y_n$.<br><br> 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.<br><br> 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 <code>$\{ 0, 1, 2 \}$</code>, thus requiring roughly $3^k$ equations to be solved. That's very slow, but guarantees that smooth pairs occur only as fundamental solutions.<br><br> 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 &lt; S_1$, so this property can't be ruled out.<br><br> 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.</p> http://mathoverflow.net/questions/103885/consecutive-integers-with-no-large-prime-factors/118572#118572 Answer by Jim White for Consecutive integers with no large prime factors Jim White 2013-01-10T21:04:02Z 2013-01-10T21:15:07Z <p>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.<br><br> 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. <br><br> I have had a particular interest in this subject for some years, and have provided most of the high-end values at OEIS, see <a href="http://oeis.org/A002072" rel="nofollow">http://oeis.org/A002072</a>. I intend to raise some questions arising from this work in a new posting here at mathoverflow.<br><br></p> <p>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. <br><br>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.</p> http://mathoverflow.net/questions/118247/uniqueness-of-values-in-recurrence-relations/118519#118519 Answer by Jim White for Uniqueness of values in recurrence relations Jim White 2013-01-10T10:43:44Z 2013-01-10T10:43:44Z <p>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$. <br><br> I found that, for any <i>k</i>, 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 <i>j</i> where $V_i &lt; U_j &lt; U_{j+1} &lt; 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$. <br><br> 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?</p> http://mathoverflow.net/questions/118247/uniqueness-of-values-in-recurrence-relations/118424#118424 Answer by Jim White for Uniqueness of values in recurrence relations Jim White 2013-01-09T06:56:31Z 2013-01-09T13:25:25Z <p>Ok, Aaron has generalised my sequences <code>$X(k), Y(k)$</code> to <code>$U(m), V(m)$</code> for arbitrary <i>m</i> > 2. <br><br> It will be found that any pair <code>$(u, v) = (U_j(m), V_j(m))$</code> corresponds to a solution to the generalised Pell equation<br></p> <blockquote>$(m+2)v^2 - (m-2)u^2 = 4$</blockquote> <p><br><br> If <code>$m = 4k$</code> then this reduces to <code>$(2k+1)v^2 - 2ku^2 = 2$</code>, and for <code>$m = 4k-2$</code> we get <code>$kv^2 - (k-1)u^2 = 1$</code>. <br><br> This explains why cases <code>$m = 3, 4, 6$</code> produce convergents to <code>$\sqrt{5}, \sqrt{3}, \sqrt{2}$</code> respectively, since they correspond to regular Pell equations: <br><br></p> <blockquote> $m=3: 5v^2 - u^2 = 4$<br> $m=4: 3v^2 - u^2 = 2$<br> $m=6: 2v^2 - u^2 = 1$</blockquote> <p><br><br>My original question is thus restated as "Does <code>$U_j(4k-2) = V_i(4k+2)$</code> have any solutions?". Which itself can be restated as, are there any solutions to the simultaneous equations: <br><br><blockquote> $kx^2 - (k-1)y^2 = 1$<br> $(k+1)y^2 - kz^2 = 1$<br> </blockquote> <br> with <i>k</i> > 1, noting again that cases <i>k</i> = 2, 3 have been resolved in the negative. <br><br>And the motivating question is this: do there exist squares in arithmetic progression that can be written <code>$(k-1)n +1, kn+1, (k+1)n+1$</code>, with $n > 0, k > 1$? <br><br>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)$</p> http://mathoverflow.net/questions/118247/uniqueness-of-values-in-recurrence-relations/118322#118322 Answer by Jim White for Uniqueness of values in recurrence relations Jim White 2013-01-08T00:43:54Z 2013-01-08T00:59:27Z <p>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. <br><br> By the way, I have reversed the definitions of <i>X</i> and <i>Y</i> above as they were the opposite of what I have in all existing code and research notes. My apologies! <br><br> In terms of <i>k</i> the first few polynomials are<br><br> <code>$Py_1 = 4k - 1$</code><br> <code>$Px_1 = 4k + 1$</code> <br><br> <code>$Py_2 = 16k^2 - 12k + 1$</code><br> <code>$Px_2 = 16k^2 + 12k + 1$</code> <br><br> <code>$Py_3 = 64k^3 - 80k^2 + 24k - 1$</code><br> <code>$Px_3 = 64k^3 + 80k^2 + 24k + 1$</code> <br><br> <code>$Py_4 = 256k^4 - 448k^3 + 240k^2 - 40k + 1$</code><br> <code>$Px_4 = 256k^4 + 448k^3 + 240k^2 + 40k + 1$</code> <br><br> If we define the distance polynomial <code>$D_{j,i} = Py_j - Px_i$</code> then <code>$D_{2,1} = 16k^2 - 16k$</code> so the quadratic case is disposed of, as you say.<br><br> We can also rule out the cubic case, and in fact all odd <i>j</i>. We have<br><br> <code>$D_{3,1} = 64k^3 - 80k^2 + 20k - 2$</code><br> <code>$D_{3,2} = 64k^3 - 96k^2 + 12k - 2$</code><br><br> For all odd <i>j</i> we get even coefficients and $c_0 = -2$, so no <code>$D_{2e+1,i}$</code> can have an integer root <code>$k &gt; 1$</code>.<br><br> For even <i>j</i> we get polys like these:<br><br> <code>$D_{4,1} = 56k^4 - 448k^3 + 240k^2 - 44k$</code><br> <code>$D_{4,2}= 256k^4 - 448k^3 + 224k^2 - 52k$</code><br> <code>$D_{4,3} = 256k^4 - 512k^3 + 160k^2 - 64k$</code><br><br> What I'm hoping to find is some magic property for even <i>j</i> that will tell us that all <code>$D_{2e,i}$</code> are either irreducible or have a single integer root <code>$k=1$</code>.<br><br> Since <code>$Y(1,j) = 3,5,7 \ldots$</code>, all of <code>$X(1,i) = 5, 29, 169 \ldots$</code> are to be found in <code>$Y(1,j)$</code> so the corresponding <code>$D_{14,2}, D_{84,3}$</code> etc will all have root <code>$k=1$</code>.<br><br> I suspect that all other <i>D</i> are irreducible, but these isolated exceptions are a bit of a fly in the ointment!<br><br> Oh yes, and I can tell you that a search on all pairs of sequences <code>$Y(k,j), X(k,i)$</code> revealed no match for a rather staggering <i>j</i> up to 100,000. For a given depth limit <i>j &lt; J</i>, such a search is finite, since beyond a certain <i>k</i> we find that all <code>$Y(k,J) &gt; X(k,J-1)$</code> and so we need look no further.<br><br> It follows then that the proposition, that all <code>$D_{j,i}$</code> are either irreducible or have a single integer root <code>$k=1$</code> is true for all <i>j</i> &lt; 100,000.</p> http://mathoverflow.net/questions/119524/decision-problem-wrt-pairs-of-polynomials-with-integer-coefficients Comment by Jim White Jim White 2013-01-22T00:43:00Z 2013-01-22T00:43:00Z If only it were that simple! :) http://mathoverflow.net/questions/119250/square-roots-of-unity-modulo-n2/119275#119275 Comment by Jim White Jim White 2013-01-20T10:23:32Z 2013-01-20T10:23:32Z BTW, I believe the RHS above should be $-2s\lambda$ http://mathoverflow.net/questions/119250/square-roots-of-unity-modulo-n2/119275#119275 Comment by Jim White Jim White 2013-01-18T15:07:57Z 2013-01-18T15:07:57Z Thank you very much, that helps, and I can see how it extends to $N^2/f^2$. http://mathoverflow.net/questions/119250/square-roots-of-unity-modulo-n2 Comment by Jim White Jim White 2013-01-18T14:35:23Z 2013-01-18T14:35:23Z If that proviso makes this a trivial question, my apologies, and please could I have a reference? http://mathoverflow.net/questions/119250/square-roots-of-unity-modulo-n2 Comment by Jim White Jim White 2013-01-18T14:32:01Z 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. http://mathoverflow.net/questions/88929/a-family-of-pellian-equations/118718#118718 Comment by Jim White Jim White 2013-01-14T14:47:59Z 2013-01-14T14:47:59Z Corrected mistake in the statement &quot;One property shared by all $y_n \in K_1 \ldots$. The divisibility property involves $y_n^2 + 1$, not $y_n$. http://mathoverflow.net/questions/106738/greatest-prime-factors-for-any-prime-p-is-there-an-integer-c-such-that-for-any/118592#118592 Comment by Jim White Jim White 2013-01-12T11:38:12Z 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. http://mathoverflow.net/questions/88929/a-family-of-pellian-equations/118718#118718 Comment by Jim White Jim White 2013-01-12T10:49:52Z 2013-01-12T10:49:52Z Apologies, the bounds for $k$ above should read $2^{32}$ and $2^{64}$ http://mathoverflow.net/questions/88929/a-family-of-pellian-equations/118718#118718 Comment by Jim White Jim White 2013-01-12T10:47:57Z 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 <a href="http://www.numbertheory.org/pdfs/dujella_slides.pdf" rel="nofollow">numbertheory.org/pdfs/dujella_slides.pdf</a> http://mathoverflow.net/questions/88929/a-family-of-pellian-equations/118718#118718 Comment by Jim White Jim White 2013-01-12T10:39:53Z 2013-01-12T10:39:53Z There are too many $k \in K$ to make verification practical for <code>$k &lt; 2^64$</code>, but for the record we believe that $|K_1| = 3,040,378,747$ and $|K_2| = 1,725,632$. http://mathoverflow.net/questions/88929/a-family-of-pellian-equations/118718#118718 Comment by Jim White Jim White 2013-01-12T10:38:05Z 2013-01-12T10:38:05Z For <code>$k &lt; 2^32$</code> we have $|K_1| = 48717, |K_2| = 1657, |K| = 50374$. These were all verified to be unique, so Andrej's conjecture is confirmed for <code>$k &lt; 2^32$</code>, given that we accept that the enumeration process finds all $k$. http://mathoverflow.net/questions/106738/greatest-prime-factors-for-any-prime-p-is-there-an-integer-c-such-that-for-any/118592#118592 Comment by Jim White Jim White 2013-01-12T03:12:54Z 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 &quot;patterns like A213523&quot;. This could just be attention-deficit on my part, but can you explain in more detail what you are looking for? http://mathoverflow.net/questions/103885/consecutive-integers-with-no-large-prime-factors/118572#118572 Comment by Jim White Jim White 2013-01-12T03:00:25Z 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 &quot;St&#248;rmer&quot;. Apologies to Wiki and anybody else I might have inadvertently offended! :-) http://mathoverflow.net/questions/106738/greatest-prime-factors-for-any-prime-p-is-there-an-integer-c-such-that-for-any/118592#118592 Comment by Jim White Jim White 2013-01-11T02:40:09Z 2013-01-11T02:40:09Z I meant $(pS_1, pS_1 + p)$. You can't edit comments! http://mathoverflow.net/questions/106738/greatest-prime-factors-for-any-prime-p-is-there-an-integer-c-such-that-for-any/118592#118592 Comment by Jim White Jim White 2013-01-11T02:38:57Z 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).