1. Originally Posted by Media_Man
(After three days, my program is still running, though not turning up anything new . I am trying to pare it down as much as possible for another run.)
Earlier you mentioned the following

Originally Posted by Media_Man
Something odd/useful though: Using the same exact algorithm to look for solutions for A up to six factors, these are the only solutions I found, the same eight five-factor ones that you guys found before I made my own algorithm. This means that no combination of six prime factors from the list {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857} make a solution. All the six-factor solutions I thought I'd found earlier were simply four-factor primitives with an extra $\displaystyle x^2$ factor. I doubt this means no six-factor primitive solutions exist, but I am now intrigued. I'm going to try to run my algorithm with all primes up to 1000, instead of just this small set. Maybe it will terminate in a few *days* and give me what I'm looking for, a six-factor primitive solution.
So all primitive k = 4 solutions found thus far have only 4 prime factors and they all come from the set {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857}, yes? I wonder if the # of primes in a given $\displaystyle a_1$ is a power of 2. I'm going to attempt looking for $\displaystyle a_1$ that have 2^3 from your list. Perhaps you could try the same, or perhaps try 2^4.

Originally Posted by Media_Man

So $\displaystyle 10^2+11^2=14^2+5^2=221$. So given the factors of a large number N, I can extremely quickly find all integer solutions x,y to $\displaystyle N=x^2+y^2$. For our purposes, we'll need to use a polynomial to approximate sine and cosine for speed, though. This will be much faster than the loop structure and function calls I have in place now.
I'm not sure I follow? If you know the prime factors of N, how does one do this using polar coordinates?

In question 5.17 of Pomerance's book, the reader is asked to derive a polynomial-time algorithm for finding integers $\displaystyle (x,y)$ such that $\displaystyle x^2 + y^2 = p$ where $\displaystyle p$ is prime of the form 1 + 4k (unfortunately no algorithm appears to be described in the text and the question refers to a 1985 paper by Schoof).

Since the primes your using are all under 1000, and that there always exists integers $\displaystyle x,y$ both less than p^0.5, perhaps a brute force is best.

2. Originally Posted by jamix
I'm not sure I follow? If you know the prime factors of N, how does one do this using polar coordinates?
Consider the identity: $\displaystyle (a^2+b^2)(c^2+d^2)=(ac\pm bd)^2+(bc\mp ad)^2$, except let $\displaystyle r_1^2=a^2+b^2,r_2^2=c^2+d^2,\theta_1=\arctan(\frac {b}{a}),\theta_2=\arctan(\frac{d}{c})$

Then the identity becomes $\displaystyle r_1^2r_2^2=(r_1\cos(\theta_1)r_2\cos(\theta_2)\pm r_1\sin(\theta_1)r_2\sin(\theta_2))^2$ $\displaystyle +(r_1\cos(\theta_1)r_2\sin(\theta_2)\mp r_1\sin(\theta_1)r_2\cos(\theta_2))^2$ $\displaystyle =\left(r_1r_2\cos(\theta_1\pm\theta_2)\right)^2+\l eft(r_1r_2\sin(\theta_1\pm\theta_2)\right)^2$. The best way to understand it is to try it!

Always clarifying with an example: If $\displaystyle p=13=2^2+3^2,\theta_p=\arctan(\frac32)=.9827,q=17= 1^2+4^2,\theta_q=\arctan(\frac41)=1.3258$, then $\displaystyle pq=221=(\sqrt{221}\cos(.9827\pm1.3258))^2$ $\displaystyle +(\sqrt{221}\sin(.9827\pm1.3258))^2=10^2+11^2=14^2 +5^2$

The algebra gets hairy, but it can be shown that this process is nested. Given a number N with prime factors $\displaystyle f_i=x_i^2+y_i^2$, define $\displaystyle \theta_i=\arctan{\frac{y_i}{x_i}}$. Then $\displaystyle N=f_1f_2f_3...f_k=(\sqrt{N}\cos(\theta_1\pm\theta_ 2\pm\theta_3...\pm\theta_k))^2+(\sqrt{N}\sin(\thet a_1\pm\theta_2\pm\theta_3...\pm\theta_k))^2$

Originally Posted by jamix
So all primitive k = 4 solutions found thus far have only 4 prime factors and they all come from the set {1,5,13,17,29,37,41,53,61,73,101,109,113,149,157,2 81,401,421,857}, yes? I wonder if the # of primes in a given is a power of 2. I'm going to attempt looking for that have 2^3 from your list. Perhaps you could try the same, or perhaps try 2^4.
Actually, no. We have found 4 4-factor, 5 5-factor, and 1 6-factor solutions thus far (see above posts). Dilcher's 1999 proof does manage to convince us that there are no 3-factor solutions, and it is trivial that there are no 1- or 2-factor solutions.

Originally Posted by jamix
In question 5.17 of Pomerance's book, the reader is asked to derive a polynomial-time algorithm for finding integers $\displaystyle (x,y)$ such that $\displaystyle x^2 + y^2 = p$ where $\displaystyle p$ is prime of the form 1 + 4k (unfortunately no algorithm appears to be described in the text and the question refers to a 1985 paper by Schoof).
This I didn't find any trick in doing, but it doesn't slow down the algorithm because it can be done separately, before everything else. If there are only 168 primes p of the form 4k+1 up to 1000, then the integer solutions x,y to $\displaystyle p=x^2+y^2$ can be found by trial in a split second. Then an array of $\displaystyle p_i$'s can be stored, along with an array of $\displaystyle \theta_i$'s. I'm sure Pomerance is interested in doing this for extremely high values of p, but in our application, I am assuming that the two squares that sum to a given prime are easy to find, unique, and constant throughout the program.

3. Originally Posted by Media_Man
At last here is our generating algorithm in simplest form:

$\displaystyle a^2+b^2=c^2+d^2=e^2+f^2=g^2+h^2=A$
$\displaystyle 2(a^2b^2+c^2d^2)=2(e^2f^2+g^2h^2)=B$
$\displaystyle 2|a^2b^2-c^2d^2|=C_1$
$\displaystyle 2|e^2f^2-g^2h^2|=C_2$
(These are the C-values for the two k=3 ladders that multiply to get the desired k=4 ladder)
$\displaystyle \frac12(C_1^2+C_2^2)=C$
$\displaystyle \frac12|C_1^2-C_2^2|=D$

The eight roots can be gotten by $\displaystyle r=a\pm b, c\pm d, e\pm f, g\pm h$ or by $\displaystyle r^2=A\pm\sqrt{B\pm\sqrt{C\pm D}}$
You know this formula is probably new (It appears only the first condition is described in Dilcher).

In any case, I decided to use the above to actually write out some of the k = 4 polynomials in terms of $\displaystyle (a_1,a_2,a_3,a_4)$. I also used the chance to check that your formula is correct by checking that various roots $\displaystyle r_i$ are such that $\displaystyle P(r_i) = 0$ (I'm too lazy to go through the algebraic proof).

Here are the 4 ones that I did:

1) A = 67405:

$\displaystyle (67405,3525798096,533470702551552000,4692082091913 21600)$

2) A = 600445:

$\displaystyle (600445,172337340816,16685576724080968704000,10660 920170019569049600)$

3) A = 55445869:

(55445869,1164899189250000,44622709555000952072468 7360000,359659829363407799927500800000)

4) A = 5915065:

(5915065,14071276316736,96909018922818605393510400 ,88118108724250005553152000)

Two of these are so long I can't even $\displaystyle Latex$ them, which is also why I chose to stop after doing four of the eight A's.

In any case there is some interesting properties with regards to common factors among the $\displaystyle a_i$ for a particular A.

Have you been following some of the theory I've written in the past couple of posts over in the other thread? Each of these k = 4 ladders is generated by one k = 3 ladder in the sense there exists an $\displaystyle (a_0,c)$ such that $\displaystyle P_3(x) = P_4(y)$ when $\displaystyle x = y^2 - a_0$. The polynomial $\displaystyle P_3(x)$ has the form $\displaystyle (c^2a_1,c^4a_2,c^4a_3)$ where $\displaystyle (a_1,a_2,a_3)$ is some primitive k = 3 ladder.

For example, for the k = 4 given by $\displaystyle A = 67405$ we have $\displaystyle (a_0,c) = (67405,12)$.

Thus, when $\displaystyle x = y^2 - 67405$ this ladder is created by the k = 3 $\displaystyle P(x)$, given by
$\displaystyle (c^224484709,c^425726789282000,c^422627710705600)$ where $\displaystyle c = 12$.

Similarly, for the k = 4 polynomial given by $\displaystyle A = 5915065$, we have $\displaystyle (a_0,c) = (5915065,24)$.

When $\displaystyle x = y^2 - 5915065$, this ladder is created by the k = 3 ladder given by
$\displaystyle (c^224429299161,c^4292091709233997050400,c^4265595 186885880852000)$ where $\displaystyle c = 24$.

For $\displaystyle A = 600445$ we have $\displaystyle c = 12$ and for $\displaystyle A = 55445869$, we have $\displaystyle c = 60$. I wonder if the value for $\displaystyle c$ is always divisible by $\displaystyle 12$?

Unfortunately this idea probably doesn't add anything of value that would make finding a k = 5 or k = 4 go any faster. It can however be used to find partial ladders (ie ladders of degree 2^k where many of the terms are linear, but not necessarily all of them are).

4. Banking on the converse

Consider the roots of $\displaystyle P_3(x)=((x^2-a_1)^2-a_2)^2-a_3^2$, $\displaystyle r_i=\pm\sqrt{a_1\pm\sqrt{a_2\pm a_3}}$

Now substitute $\displaystyle x=y^2-a_0$, so the roots of $\displaystyle P_4(y)$ become $\displaystyle s_i^2-a_0=\pm\sqrt{c^2a_1\pm\sqrt{c^4a_2\pm c^4a_3}}$ or $\displaystyle s_i=\pm\sqrt{a_0\pm c\sqrt{a_1\pm\sqrt{a_2\pm a_3}}}=\pm\sqrt{a_0\pm c r_i}$

So, the question becomes: Given four integers $\displaystyle r_1,r_2,r_3,r_4$, for what values $\displaystyle a_0,c$ is $\displaystyle a_0\pm cr_i$ a perfect square for all i?

To use your example, the roots of $\displaystyle P_3(24484709,25726789282000,22627710705600)$ are

$\displaystyle \sqrt{24484709-\sqrt{25726789282000- 22627710705600}}=4767$
$\displaystyle \sqrt{24484709-\sqrt{25726789282000+ 22627710705600}}=4187$
$\displaystyle \sqrt{24484709+\sqrt{25726789282000- 22627710705600}}=5123$
$\displaystyle \sqrt{24484709+\sqrt{25726789282000+ 22627710705600}}=5607$

Transforming it into $\displaystyle P_4(a_0,c^2a_1,c^4a_2,c^4a_3)$ with $\displaystyle a_0=67405,c=12$ gives our familiar 67405 k=4 ladder, whose roots are:

$\displaystyle \sqrt{67405-12*4767}=101$
$\displaystyle \sqrt{67405-12*4187}=131$
$\displaystyle \sqrt{67405-12*5123}=77$
$\displaystyle \sqrt{67405-12*5607}=11$
$\displaystyle \sqrt{67405+12*4767}=353$
$\displaystyle \sqrt{67405+12*4187}=343$
$\displaystyle \sqrt{67405+12*5123}=359$
$\displaystyle \sqrt{67405+12*5607}=367$

So now given $\displaystyle (a_1,a_2,a_3,a_4)=(67405,3525798096,53347070255155 2000,469208209191321600)$, for what values $\displaystyle a_0,c$ is $\displaystyle a_0\pm cr_i$ a perfect square for all $\displaystyle r={101,131,77,11,353,343,359,367}$? If you find this, then $\displaystyle P_5(a_0,c^2a_1,c^4a_2,c^8a_3,c^8a_4)$ will be a k=5 ladder!

The operative word here is "if." Even though every k=4 ladder can be spawned from a k=3 ladder, the converse is not true. Just because you have a k=3 ladder does NOT mean a $\displaystyle a_0,c$ pair can be found producing the above results. Likewise, we have only uncovered 10 k=4 ladders so far. It is highly unlikely that one of these will be the one to spawn the lowest k=5 ladder using the above algorithm. But hey, it's worth a try

Can you build a program that inputs $\displaystyle r_1,r_2,r_3,r_4,r_5,r_6,r_7,r_8$, loops through candidate values of $\displaystyle a_0= 1\to 1000000$ and $\displaystyle c=1\to 1000$ and checks to see that $\displaystyle a_0\pm cr_i$ is a perfect square for all i?

5. Originally Posted by Media_Man
Can you build a program that inputs $\displaystyle r_1,r_2,r_3,r_4,r_5,r_6,r_7,r_8$, loops through candidate values of $\displaystyle a_0= 1\to 1000000$ and $\displaystyle c=1\to 1000$ and checks to see that $\displaystyle a_0\pm cr_i$ is a perfect square for all i?
I'll run my current program again, except this time put in your larger parameters. A few days ago I ran it for $\displaystyle a_0= 1\to 100000$ and $\displaystyle c=1\to 500$. I didn't find a k = 5 ladder that was a product of only linear terms, however with $\displaystyle (a_0,c) = (33317,92)$ I found that 6 of the sixteen terms $\displaystyle a_0\pm cr_i$ were squares when I was using the k = 4 generated by $\displaystyle a_1 = 67405$.

As I said earlier, this method is no better than your method for finding a k = 5 by sieving through various $\displaystyle a_1$ and checking that they satisfy the necessary conditions (in fact its probably even worse than yours). The only positive, is that you can easily find many partial ladders. The programming may also be slightly easier.

Anyways, if you are able to download Pari/gp, you can input the following code yourself:

(note: for the below I decided not to sieve out the $\displaystyle a_0$ that are divisible by primes $\displaystyle 3 + 4k$ to an odd exponent because I don't think this condition is necessary for partial ladders)
roots1(a_0,c) = { local(y);
y = 0;
if( issquare(a_0 - 367*c) == 1, y++);
if( issquare(a_0 - 359*c) == 1, y++);
if( issquare(a_0 - 353*c) == 1, y++);
if( issquare(a_0 - 343*c) == 1, y++);
if( issquare(a_0 - 131*c) == 1, y++);
if( issquare(a_0 - 101*c) == 1, y++);
if( issquare(a_0 - 77*c) == 1, y++);
if( issquare(a_0 - 11*c) == 1, y++);
if( issquare(a_0 + 367*c) == 1, y++);
if( issquare(a_0 + 359*c) == 1, y++);
if( issquare(a_0 + 353*c) == 1, y++);
if( issquare(a_0 + 343*c) == 1, y++);
if( issquare(a_0 + 131*c) == 1, y++);
if( issquare(a_0 + 101*c) == 1, y++);
if( issquare(a_0 + 77*c) == 1, y++);
if( issquare(a_0 + 11*c) == 1, y++);
return(y);
}

roots2(a_0) = { local(y);
y = 0;
for( c = 1,1000,
s = roots1(a_0,c);
if( s > y, y = s);
);
return(y);
}

roots3(a,b) = { local(y);
y = 0;
for( a_0 = a,b,
s = roots2(a_0);
if( s > 5, print(s));
);
}
In the code for ''roots2'', you can see I have c = 1,1000. To check every single $\displaystyle a_0$ from 1-1000000, I input ''roots3(1,1000000)''. I have the program set such that when I input the command ''roots3(a,b)'' it will output any $\displaystyle a_0$ such that there exists a $\displaystyle c$ for which at least 6 of the 16 integers $\displaystyle a_0\pm cr_i$ are squares. When this finishes, one can go back and slightly alter the code for ''roots2'' in order to find out exactly how many are squares, and what the $\displaystyle c$ values are.

I'll post here again when my program finishes.

6. Partial ladders = partially useful?

Jamix -

You know the original factoring algorithm better than I do. Are "partial" ladders of any use? By partial, of course, we're talking about polynomials with some non-integer, and possibly non-real roots, correct?

7. Media_Man...

So long as your polynomial ladder is a product of a very large # of smaller polynomials, then it can be used as an Integer factoring algorithm. To tell how efficient your polynomial is for Integer factoring, you need only calculate the following ratio:

Let $\displaystyle K$ be the # of squaring/multiplications one needs to do in order to calculate the polynomial ( say $\displaystyle P(x)$) and let $\displaystyle L$ be the # of distinct irreducible polynomials that divide $\displaystyle P(x)$.

Call the ratio $\displaystyle P = \frac{L }{K}$.

The larger $\displaystyle P$ is, the better the polynomial is for factoring integers.

In 6.17 of the Pomerance book, there is a rudimentary description on how one can create a factoring algorithm using these polynomials. I'll go into more descriptive detail later. Personally, I feel like this methology is more beneficial for sieving out composite integers when one wishes to find very large primes, as appose to full factorization for its own sake (after all there are far more superior algorithms for that).

.................................................. ...........................

With regards to the current situation:

Now that I think about it, the above program is really slow. In fact if one simply checks the condition of whether or not $\displaystyle a_0$ is a quadratic residue over the primes 367,359,353,343,131,101,77,11, we can immediately determine if $\displaystyle a_0\pm cr_i$ is not a square for any $\displaystyle c$ for some of these primes.

To check if an $\displaystyle a_0$ is a quadratic residue for a particular prime p, we need only apply Euler's criterion ( ie does a_0 satisfy (a_0)^(p - 1)/2 = 1 mod(p)).

Here is some new code which is similar to the code above, but which goes significantly faster:

residues(a_0) = { local(y);
y = 0;
if( ((a_0)^183) % 367 == 1, y++);
if( ((a_0)^179) % 359 == 1, y++);
if( ((a_0)^176) % 353 == 1, y++);
if( ((a_0)^147) % 343 == 1, y++);
if( ((a_0)^65) % 131 == 1, y++);
if( ((a_0)^50) % 101 == 1, y++);
if( ((a_0)^30) % 77 == 1, y++);
if( ((a_0)^5) % 11 == 1, y++);
return(y);
}

roots1(a_0,c) = { local(y);
y = 0;
if( issquare(a_0 - 367*c) == 1, y++);
if( issquare(a_0 - 359*c) == 1, y++);
if( issquare(a_0 - 353*c) == 1, y++);
if( issquare(a_0 - 343*c) == 1, y++);
if( issquare(a_0 - 131*c) == 1, y++);
if( issquare(a_0 - 101*c) == 1, y++);
if( issquare(a_0 - 77*c) == 1, y++);
if( issquare(a_0 - 11*c) == 1, y++);
if( issquare(a_0 + 367*c) == 1, y++);
if( issquare(a_0 + 359*c) == 1, y++);
if( issquare(a_0 + 353*c) == 1, y++);
if( issquare(a_0 + 343*c) == 1, y++);
if( issquare(a_0 + 131*c) == 1, y++);
if( issquare(a_0 + 101*c) == 1, y++);
if( issquare(a_0 + 77*c) == 1, y++);
if( issquare(a_0 + 11*c) == 1, y++);
return(y);
}

roots2(a_0) = { local(y);
y = 0;
for( c = 1,1000,
s = roots1(a_0,c);
if( s > y, y = s);
);
return(y);
}

roots3(a,b) = { local(y);
y = 0;
for( a_0 = a,b,
k = roots(a_0);
if( 6 > k, next);
s = roots2(a_0);
if( s > 5, print(a_0));
);
}
Basically if $\displaystyle a_0$ isn't a quadratic residue for at 6 of the primes, then I immediately move to the next $\displaystyle a_0$ integer.

8. Integer factoring and programming results

My program has finished running. My code for the residues function was flawed yesterday, so if your going to copy it, make sure to note the corrections made. You can see the results and my comments below, but first you asked earlier how it is polynomials can be used to create an integer factoring algorithm in this context, so I'll go into that now.

Suppose $\displaystyle n = pq$ is a composite integer we wish to factor. Furthermore, let $\displaystyle P_(x)$ be some polynomial such that there exists an $\displaystyle x_0$ such that $\displaystyle P(x_0) \equiv 0 mod(p)$. Even if we reduce $\displaystyle P(x)$ over $\displaystyle Z_n$ (that is we calculate $\displaystyle P_n(x) = P(x)mod(n)$), it will still be the case that $\displaystyle gcd(P_n(x_0),n) = p$ giving us a factorization of $\displaystyle n$. Occasionally the $\displaystyle gcd$ will equal $\displaystyle n$ but thats not a big issue since this doesn't happen often. The real problem here is that we do not know what $\displaystyle x_0$ is, hence we must plug in multiple values of the variable $\displaystyle x$ and calculate $\displaystyle gcd(P_n(x),n)$ for each of them untill we get a $\displaystyle gcd$ that factorizes $\displaystyle n$.

Now if $\displaystyle P(x) = Q_1(x)*Q_2(x)*....Q_k(x)$, then there likely exists many integers $\displaystyle x_0,x_1,x_2,x_s$ such that $\displaystyle P(x_i) \equiv 0 mod(p)$. This means we have less values of $\displaystyle x$ to check before we obtain a nontrivial $\displaystyle gcd$. This is why we want to maximize the $\displaystyle L$ value in the equation $\displaystyle P = \frac{L}{K}$. On the other hand, increasing $\displaystyle L$ by multiplying together a bunch of polynomials may not be such a great strategy since we now have to do more multiplications or squaring operations to calculate $\displaystyle P(x)$. That is, the value for $\displaystyle K$ in $\displaystyle P = \frac{L}{K}$ has also increased. To determine if changing $\displaystyle P(x)$ just to increase to $\displaystyle L$ was worth it, we need only determine if $\displaystyle P$ has increased. If it has, then this new polynomial is more efficient for factoring. If not, then our first choice was more efficient.

Lets do one example:

Suppose we wish to factor the integer $\displaystyle n = 851$ using the polynomial $\displaystyle P(x) = ((x^2 - 85)^2 - 4176)^2 - 2880^2$. Reducing this polynomial over $\displaystyle Z_{851}$ gives us the polynomial $\displaystyle P_n(x) = ((x^2 - 85)^2 - 772)^2 - 554$. To make sure that the values $\displaystyle x$ checked are uniformly distributed, let us define $\displaystyle x_i = 2^i mod(851)$ and plug these in until a nontrivial $\displaystyle gcd$ is found.

We have the following results:

$\displaystyle P_{851}(2^1) = 438$ and $\displaystyle gcd(438,851) = 1$

$\displaystyle P_{851}(2^2) = 420$ and $\displaystyle gcd(420,851) = 1$

$\displaystyle P_{851}(2^3) = 79$ and $\displaystyle gcd(79,851) = 1$

$\displaystyle P_{851}(2^4) = 368$ and $\displaystyle gcd(368,851) = 23$

The last $\displaystyle gcd$ is nontrivial and factores $\displaystyle 851$ into $\displaystyle 23*37$ which are both prime. Hence we have factored $\displaystyle 851$.

The efficiency of this polynomial, is given by $\displaystyle P = \frac{L}{K} = \frac{8}{3} = 2.67$.

If we had used one of the k = 4 polynomials, we might have been able to factor 851 even faster since then $\displaystyle P = \frac{16}{4} = 4$. On the other hand, the partial k = 5 ladder which is mentioned in the other thread, might do even better since in that case $\displaystyle P = \frac{22}{5} = 4.4$.

Did you understand all this well enough?

.................................................. ..............................

I've finished running the code for $\displaystyle a_0$ in the interval 100000-1000000 and $\displaystyle c$ in the interval 1-3000 (generally for larger $\displaystyle a_0$ one needs to use larger $\displaystyle c$ to rule out $\displaystyle a_0$ as a particular candidate) . My program only ouputed 7 integers $\displaystyle a_0$, all of which created 6 squares among the 16 terms $\displaystyle a_0 \pm cr_i$, hence they're no better than the $\displaystyle (33317,92)$ term I found awhile ago (ie they all have a $\displaystyle P = 4.4$).

I believe it is not inconceivable that an $\displaystyle (a_0,c)$ may exist which will produce seven squares among the $\displaystyle a_0 \pm cr_i$, although perhaps one may have to use a different k = 4 ladder. On the other hand, if this is as far as we can get using a $\displaystyle 2^5$ degree polynomial, then perhaps we should go up to $\displaystyle 2^6$ and see if we can obtain a $\displaystyle P$ value that is higher than $\displaystyle 4.4$ this way.

9. Heuristics :-\

This is an interesting tangent of the original problem. A k-ladder with all integer roots will have an efficiency of $\displaystyle \frac{2^k}{k}$, so a k=5 ladder, if we can find one, will have an efficiency of 5.67, but a partial ladder should have a range with this as an upper bound.

Consider: The probability of a random number n be a square is about 1 in n, right? So take a known k=4 ladder with roots $\displaystyle r_i$ and guess $\displaystyle a_0,c$ -- the chances of $\displaystyle s_i=\sqrt{a_0\pm cr_i}$ being an integer is about 1 in $\displaystyle a_0\pm cr_i$. Multiplying, the chances of $\displaystyle s_{i+}$ and $\displaystyle s_{i-}$ both being integers are 1 in $\displaystyle (a_0+cr_i)(a_0- cr_i)=a_0^2-c^2r_i^2$. The chances of all 32 roots being integers is therefore 1 in $\displaystyle c^{16}(\frac{a_0^2}{c^2}-r_1^2)...(\frac{a_0^2}{c^2}-r_8^2)$ or 1 in $\displaystyle c^{16}P_4(\frac{a_0}{c})$.

To minimize this, it makes sense that $\displaystyle a_0,c$ are both small. Does it seem strange that the bigger we start guessing for these numbers, the less likely we are to find a solution?

This may be a bad argument, but it's an interesting result. Take a perfectly good k=4 ladder with 16 integer roots, and the more you keep guessing $\displaystyle a_0,c$ combinations, the less likely you are to find a k=5 ladder. If this result is valid, then it makes sense that there are so few of them. Am I misinterpreting something here?

10. Originally Posted by Media_Man
This is an interesting tangent of the original problem. A k-ladder with all integer roots will have an efficiency of $\displaystyle \frac{2^k}{k}$, so a k=5 ladder, if we can find one, will have an efficiency of 5.67, but a partial ladder should have a range with this as an upper bound.

Consider: The probability of a random number n be a square is about 1 in n, right? So take a known k=4 ladder with roots $\displaystyle r_i$ and guess $\displaystyle a_0,c$ -- the chances of $\displaystyle s_i=\sqrt{a_0\pm cr_i}$ being an integer is about 1 in $\displaystyle a_0\pm cr_i$. Multiplying, the chances of $\displaystyle s_{i+}$ and $\displaystyle s_{i-}$ both being integers are 1 in $\displaystyle (a_0+cr_i)(a_0- cr_i)=a_0^2-c^2r_i^2$. The chances of all 32 roots being integers is therefore 1 in $\displaystyle c^{16}(\frac{a_0^2}{c^2}-r_1^2)...(\frac{a_0^2}{c^2}-r_8^2)$ or 1 in $\displaystyle c^{16}P_4(\frac{a_0}{c})$.
It would be about 1 in $\displaystyle (2c)^{8}\sqrt{P_4(\frac{a_0}{c})}$ since the probability of a given integer $\displaystyle n$ being square is closer to $\displaystyle \frac{1}{\sqrt{2n}}$. For example, if $\displaystyle n = 50$ then $\displaystyle n$ is at the midpoint of the interval from $\displaystyle 1-100$. Since there are $\displaystyle \sqrt{100} = 10$ squares in this interval, the probability that 50 is a square is arguably $\displaystyle \frac{1}{10}$.

Originally Posted by Media_Man
To minimize this, it makes sense that $\displaystyle a_0,c$ are both small. Does it seem strange that the bigger we start guessing for these numbers, the less likely we are to find a solution
Its best that $\displaystyle (a_0,c)$ is chosen so that the majority of $\displaystyle a_0 \pm r_ic$ are small. On the other hand, if $\displaystyle (a_0,c)$ is large, than so are all the $\displaystyle a_0 + cr_i$, so yeah its best if $\displaystyle (a_0,c)$ is small unfortunately.

I'm going to try and take out a book at my library that discusses an algebraic version of the Pollard rho factorization algorithm since I believe it may shed some light on this issue (note: The Pomerance book discusses the Pollard rho method, however its not the algebraic version).

11. Mathematica

Expand and simplify in terms of $\displaystyle x_i$: $\displaystyle (e_0-e_2+e_4)^2(e_1-e_3)^2$, where
$\displaystyle e_0=1$
$\displaystyle e_1=x_1+x_2+x_3+x_4$
$\displaystyle e_2=x_1x_2+x_1x_3+x_1x_4+x_2x_3+x_2x_4+x_3x_4$
$\displaystyle e_3=x_2x_3x_4+x_1x_3x_4+x_1x_2x_4+x_1x_2x_3$
$\displaystyle e_4=x_1x_2x_3x_4$

You should see a lot of patterns and symmetry here, but this simple algebraic leap is close to intractable by hand.

12. Not sure how to compress this. Is this the discriminant for a polynomial of degree 4 with 4 roots?

I wrote a little program that will output this discriminant when you input $\displaystyle (x_1,x_2,x_3,x_4)$, but I suppose this isn't necessarily what you want.

expres(x_1,x_2,x_3,x_4) = { local(e_0,e_1,e_2,e_3,e_4,k);
e_0 = 1;
e_1 = x_1 + x_2 + x_3 + x_4;
e_2 = x_1*x_2 + x_1*x_3 + x_1*x_4 + x_2*x_3 + x_2*x_4 + x_3*x_4;
e_3 = x_2*x_3*x_4 + x_1*x_3*x_4 + x_1*x_2*x_4 + x_1*x_2*x_3;
e_4 = x_1*x_2*x_3*x_4;
k = (e_0-e_2+e_4)^2*(e_1-e_3)^2;
return(k);
}

13. Not sure how to compress this. Is this the discriminant for a polynomial of degree 4 with 4 roots?
I have no idea. I do know that this algebraic step could provide a link between our two conditions necessary to find a k=4 ladder, and the solutions p,q to $\displaystyle f=p^2+q^2$ for prime factors f of $\displaystyle a_1$.

Expanding this thing fully results in about 150 terms, but I suspect (or hope dearly) that a lot of stuff cancels out, resulting in a simple, intuitive expression of x's.

With a little luck, this approach could help us predict which factors most likely appear in $\displaystyle a_1$. What is the output of this program? Have you tried it?

14. Media_Man...

Sorry for the delay. I have less time to come here now since classes and teaching are back in full swing. I don't know how to compress the expression $\displaystyle (e_0-e_2+e_4)^2(e_1-e_3)^2$, however as a general rule of thumb, if you can express something as a square, then you should compress whatever is in the square. That is, you should attempt to compress $\displaystyle k = (e_0-e_2+e_4)(e_1-e_3)$ instead, as this will lead directly to a compression for $\displaystyle k^2$ which is what you want.

15. Odd?

Okay, I have pared down my algorithm as much as possible using this line of reasoning, and found no other solutions. This seems odd.

(1) No values for A have been even numbers. My algorithm didn't even look for them, since I let A be every possible combination of prime factors 1,5,13,17,etc. But you guys initially counted A from 1 to 2 billion, right?

(2) No more 4-factor solutions exist for factors under 5000. No more 5-factor solutions exist for factors under 2000. No more 6-factor solutions exist for factors under 500. (These upper bounds simply represent the computing limits of my pc.) This seems extremely odd. Why should A=67405,600445,55445869,242048509 be the first 4-factor solutions we find, all with prime factors under 1000, and then suddenly, they stop? Or, phrased another way: Of all possible combinations of 4 4k+1 primes less than 5000, not a single solution contained a factor greater than 1000! This means that if more 4-factor solutions exist, they would have to be greater than $\displaystyle 5000^4=625$ trillion! That's a pretty big leap for a sequence of integers following any kind of law. EDIT: Just upped the bound to 10000 and let it run overnight. No results. I am at a loss.

I have attached my source code in case anyone thinks I have made some kind of programming error.

Perhaps there are a finite number of k=4 ladders whose A value has a given number of factors? Perhaps there are a finite number of k=4 ladders, and we have here most or all of them! I believe these two observations are correct, but they do not make sense. I know this only seems like theoretical pouting for churning out 10 solutions and then hitting a wall, but come on...

Page 3 of 3 First 123