Thread: Polynomial squaring ladders

Consider the polynomial below:

((x^2 - 85)^2 - 4176)^2 - 2880^2 = (x^2 - 1)*(x^2 - 11^2)*(x^2 - 13^2)*(x^2 - 7^2)

This polynomial could be considered a ''type 3'' polynomial,since it can be generated by only 3 squaring operations (ignoring the square on 2880 of course), and it has 2^3 distinct integer roots.

In general, if the integer ''2A'' can be written as a sum of two squares (ie x^2 + y^2) in at least two different ways, then there exists some ''C'' and ''D'' such that

((x^2 - A)^2 - B)^2 - C^2 = (x^2 - a^2)*(x^2 - b^2)*(x^2 - c^2)*(x^2 - d^2)

where ''a,b,c,d'' are all integers

Question:

Do there exist any ''type 4'' polynomials that have this property? That is a polynomial that can be generated in four squaring operations, that has 2^4 integer roots.

I'm having trouble following what exactly the theorem is that you're citing. Here's what I am reading: "Given a degree-8 polynomial with roots , , , and , and given a number A, there exists a B and C such that if 2A is expressible as the sum of two squares in at least two unique ways." Is this correct?

This seems inconsistent. By expanding both sides of the equation, it is clear that given a,b,c,d, there exists one and only one combination A,B,C making this equation work, found by:





The algebra is long but elementary, and I have checked this with the raw data you provided, a=1,b=11,c=13,d=7, and indeed A=85,B=4176,C=2880. In other words, you cannot choose A - it is dependent on a,b,c,d. Is the proper wording of the theorem, "If 2A is expressible as the sum of two squares in two unique ways, then there exist integers B and C..."

I think your overall question can be answered by analyzing the proof of the theorem you are citing, and trying to generalize it.

Hi Media_Man


I completely forgot about this post. I posted it a little while before your response and then left for the cottage (where theres no internet connection) for over a week. Anyway I've finished much of my summer job responsibilities, so I've got time now to talk about mathematics if your up to it.

This question comes from one of Pomerance's and Crandall's book titled ''Prime Numbers: A computational perspective''. It is the first ''research type question'' found in Chapter 6.

The 2005 edition can be downloaded at the bottom of this page: Crandall R., Pomerance C. Prime numbers. A computational perspective (2ed., Springer, 2005)(604s).pdf: eKnigu

The purpose here is to try and develop a powerful integer factoring algorithm, by creating polynomials of the form
, which have distinct integer roots. The idea is that for any composite integer n, if we calculate for various integers , then eventually, were bound to find a value of , in which for some prime factor p of n.

For example, suppose we wanted to factor the integer with the polynomial .

It can be shown that if , , , and , then . Hence if one takes the product , then it becomes increasing likely will give a factorization of (unless of course in which case we need only do some backtracking).


The above algorithm becomes more efficient (ie factors more quickly), when the polynomial has more distinct integer roots. As such, it becomes desirable to find polynomials of this form for larger .

To date, no one has found such polynomials for larger than 4 and such polynomials would have to satisfy some very strict conditions in order to have distinct integer roots. Many do not believe such polynomials exist. This probably isn't too surprising since if one could find such polynomials for arbitrary , one could create a polynomial time factoring algorithm, which would be very bad for things like internet security!

With all that said, there are other types of polynomials one can consider besides the above. I'll post on one of these more fruitful polynomials shortly.

Given , let --(1). We seek integers A,B,C such that --(2). By expanding (1) we can easily write and find the coefficients . By expanding (2) we can find equations relating to . Solving,





There are actually four equations and three unknowns, but the "extra" equation always holds. In linear algebra terms, this system has rank 3. I put together a quick java app to crank out some examples, and uncovered just these two so far:




NOTICE A PATTERN?

where the roots are . This actually follows from the algebra pretty simply, if you want to chase down a proof. The important thing is we can find numbers like 290 extremely easily. Example, pick and factor a random number like 200: . Therefore, . Using as roots, we have:



Your original post can be rephrased formally as such: Given positive integers a,b,c,d, define A and B as shown above (it can be shown trivially they will always be integers). If 2A is expressible as the sum of two squares in two unique ways, then C, as constructed above, will be an integer.

*I am working now on extending all of this from the 3 case to the 4 case, which incidentally, doubles the complexity. See if you can verify what I have so far in this post. Updates soon.

Hi Media_Man

I knew most of the stuff regarding the k = 3 you mentioned. I'm curious though by what you mean by ''doubling complexity'' regarding the k = 4 case?


I had a theorem awhile back on a necessary condition needed for k = 4, but I can't remember what it was right now. On a positive note though, k = 4 is definitely doable. Furthermore, if generates a k = 4 ladder, then also generates a k = 4 ladder. Using the one ''k = 4'' polynomial generated by from Pomerance's book, one can generate an infinite number of k = 4 such polynomials!
A similar statement can also be made for larger k values as well, but unfortunately no one has been able to find even a single polynomial beyond k = 4.

Here is what you get when expanding the relation :






Conditions:






These four "conditions" are extra equations that are undoubtedly always true. The only way I can imagine proving this is substituting all in terms of and simplifying. Obviously, I am trying to find a simple shortcut around this.

This is a monumental task to be done by hand, but perhaps you have access to Maple or Mathematica? Also, I am pleased you have an actual example in the k=4 case that can be tested, though again, I have no resources for handling numbers that big. Once these verifications are made, the real meat of your quest is finding criteria for which D is a nonzero integer.

(You see what I mean by "doubling complexity"? For k=5, we will have 16 equations with 5 unknowns, leaving 11 "conditions" and undoubtedly a very long definition of for which we seek E as an integer.)

Consider: means that for any . So . Naming these roots as follows...






... it is clear that . This proves your original observation. It also provides a means of construction.

All pythagorean triples can be generated using this relation: Choose positive integers , and , so . Notice that by construction, is always a perfect square. Here is your recipe for constructing a ladder:

1. Pick two triples with the same hypotenuse: and

2. Calculate B and C from the middle terms of the triples as such: and

3. Let A be the length of the hypotenuse, .

4. Your four roots are . These also can be gotten by taking the values in your choice of triples, ,

5. Your final ladder is

I've read through your posts (including your new thread). It's been difficult and I'm still trying to gather my thoughts on what to do for the k = 4 case. Anyway keep up the good work. Hopefully I'll have something to add tonight.

Turns out this problem is intimately connected with Pythagorean Triples. Consider the k=4 case: .
Using a binary counting system for convenience,









(1) -- |
(2) -- |
(3) -- |
(4) -- |

Above is a run-through of how to calculate 's given the roots 's. Below is how to find a suitable set of roots:

ENTER PYTHAGORAS:






Notice that by (1), the four hypotenuses of these four triples are all equal. Notice that by (2), , where the subscript b indicates the second leg of the triple, or the middle term of the above relation. SO, FIND FOUR PYTHAGOREAN TRIPLES MEETING THESE TWO SIMPLE CRITERIA, AND THE M,N VALUES GENERATING THEM GIVE YOU YOUR EIGHT ROOTS!






(This is incidental, and follows easily. It is not an another condition.)

This is about as far as I've gotten. I am trying to derive a method of finding these "triplet quadruples" explicitly, as opposed to searching by trial. This, I believe, is where the fundamental roadblock lies.

Your above post seems similar to a derivation I tried awhile ago. Let me know if the following below is equivalent to what you have.

Originally Posted by Media_Man

(1) -- |
(2) -- |
(3) -- |
(4) -- |

Above is a run-through of how to calculate 's given the roots 's. Below is how to find a suitable set of roots:

ENTER PYTHAGORAS:






Notice that by (1), the four hypotenuses of these four triples are all equal.

I've noticed that the term which needs the most conditioning, is . As you've mentioned, for k = 4, it must be the case that can be written as a sum of two squares in at least 4 ways.

Recall now that an integer can be written as a sum of two squares, iff there are no primes that divide to an odd exponent. This eliminates a ton of candidates for what can be.

Furthermore (and this is just an observation), I've noticed that many integers that can be expressed as a sum of two squares in many distinct ways (or as you've put it, the hypotenus of many different triangles), is a product of many primes of the form .

Notice that any k = 4 ladder generated by can be written as a product of two k = 3 ladders and where and .

The above uses the idea that if for some constant , then .

If we have two k = 3 polynomials, where and , then the difference between them is . So long as this integer is even, then will be a k = 4 ladder.

A motivating question from the above is how can we find two k = 3 polynomials, where and ?

I believe that the main necessary condition, is the following:

Let be the integers such that


(note that in the above, only 4 specific are used to define each ).

Relabeling the indices if necessary, if these satisfy the condition that , then it follows that is the first term in some sequence of that generates a k = 4 ladder.

I haven't found the time or energy to work out a proof to this yet. However I wonder if this is the same thing which you have in your previous post

For , I know the set would have to come from members of the following list:










The reason why the four must come from the above, is that these are the only integers , such that the pair will be squares.

Most importantly, all squaring ladders of "degree" k MUST be the product of two ladders of "degree" k-1 where are the same. This is an interesting observation, but a bit anticlimactic. Consider...






Now, recall our method of constructing k=3 ladders:

1. Find a hypotenuse shared by two triples...


--


--


2. B is the sum of the squares of the middle legs.

--
--

3. Calculate C by the difference instead of the sum from above.

--
--

So as you can see, in order to find two k=3 ladders with A and B in common, we are bound by the exact same conditions to search for as we have been using already. However, this will be useful for the k=5 case. Consider: If a k=5 case exists, then there exists two k=4 cases with a common A,B,C. If we can find a formula to generate ALL k=4 cases and prove that no two share an A,B,C, we will successfully prove that no k=5 cases exist (as is probably the case).

Alunw is doing a great job spinning out k=4 examples in the other thread (why do we have two??? ). Let's keep collecting solutions and see if we can find a pattern and a formula!

Ah okay I have a better understanding now, thanks.

We can try and find more than two cases if you'd like. Perhaps I'll ask my comp sci friend to see if he can arrange to have alumw's code run on several terminals at school. This might be quicker and might not, depending on whether or not the guys in charge will let me download something like Pari onto the laboratory computers.

Have you read the research question for this (6.17) in Crandall and Pomerance's book?
I've generally noticed that when working on these questions is that the questions themselves are typically unfruitful. Indeed, if k = 5 or higher were possible (or findable), there are many professionals who would have located them by now and this wouldn't be a research question. A general rule of thumb here is that usually one needs to alter the question into a new one, in order to find something fruitful. One idea is to loosen the restrictions on the definition of a squaring ladder, and instead find polynomials of the form where are polynomials of either small degree, or themselves squaring ladders. Furthermore, these polynomials don't necessarily have to be a product of only linear terms. If we decide thats its okay to settle for something less than perfection, we could instead just find polynomial ladders that have a maximal number of integer roots. For instance, is there a k = 5 ladder that has less than distinct integer roots, but more than .

I've finally looked at this question enough to see the "beauty" in the structure and the patterns Below is a rough sketch on how to find a k=5 ladder, if it exists, based on the fact that it must be the product of 8 k=2 ladders...

Suppose . This is Test 1, finding a large number expressible as the sum of two squares in eight unique ways. (Notice that A must have at least 8 prime factors of the form 4k+1.)

Define . We have here 8 k=2 ladders:

Multiplying them in pairs to get a k=3 ladder,

Or . This is Test 2, that our variables a-p satisfy this constraint to produce the same .

Now define . We have here 4 k=3 ladders:

Multiplying these in pairs to get a k=4 ladder,

Or . This is Test 3, that using a-h produces the same value for C as using i-p. This is also the last constraint.

Now define

Or . This gives us 2 k=4 ladders:

Multiplying to give our ultimate k=5 ladder, and

Or

And

And voila, we have our k=5 ladder, . The challenge then, is finding 16 positive integers a-p that satisfy all three constraints. Notice that, all told, there are eleven equations that must be met. So if we really want to brute force it, we can solve the system of 11 equations and 16 unknowns down to a 5-variable Diophantine equation. It should be unfathomably complicated, but it still boils the k=5 case down to finding an integer solution to a 5-variable equation.

This post is not at all a practical way to go about the problem, but perhaps we can all benefit from recognizing the beautifully nested patterns that finally emerge.

On second thought, the system is not that hard to reduce, but still yields no easy results.

-- (1)
-- (2)
-- (3)

The above system simplifies as follows: Given independent variables ...










If anyone wants to take a crack at it, be my guest. Find positive integers A,B,a-p satisfying the above or prove none exist.

Clever stuff. Perhaps you should be an Algebraist. Just looking at all that algebra makes me cringe though, which is probably why I never had the stomach to even attempt k = 5 (in addition to the fact that I didn't think it was doable). I probably should have originally put up a different question back a month ago, however at that time I was fairly enthusiastic about this problem. There is another Integer Factoring question from Chapter 5 I'm going to put up (however I'm gonna modify it) some time in the near future.