Date: Sat, 12 Nov 1994 04:10:27 -0800 From: prem@ix.netcom.com (Prem Sobel) Subject: Re: Algorithm for Diofantine Analysis To: rusin@math.niu.edu (Dave Rusin) You wrote: >Uh, this is a joke, right? Or can you find all solutions to the >diophantine equation x y = 2^1024 + 1 ? I can put it takes time proportioanal to sqrt(2^1024+1) which is a bit long. For factoring Fermats function I have a different method based on his work and group theory which searches for number of the form (d = k*2^12+1) which a special property which can be tested in time O(1024). Prem ============================================================================== Date: Sat, 12 Nov 94 14:22:05 CST From: rusin (Dave Rusin) To: prem@ix.netcom.com, rusin@math.niu.edu Subject: Re: Algorithm for Diofantine Analysis >For factoring Fermats function I have a different method >based on his work and group theory which searches for number of the >form (d = k*2^12+1) which a special property which can be tested in >time O(1024). I think you mean time O(sqrt(2^1024)/(2^12)=2^500). This is the smallest fermat number not yet fully factored. While I expect it to be factored in my lifetime, at present this is a more difficult challenge than any task taking O(1024) steps (unless the big-O constant is very large!) Still I am perplexed. Can you tell me how many solutions the diophantine equation x^n+y^n=z^n has for _any_ n? How about x^3+axz^2+bz^3=y^2z for any a and b? (I was under the impression it was still an open question to determine a general algortihm for computing the rank of any elliptic curve over the rationals.) More generally I thought it was one of Hilbert's problems to find a general algorithm for deciding whether a family of diophantine equations had a solution; and that the answer was, "there can be no such algorithm". Perhaps you can share your technique so I can see how you solve any diophantine equation? dave Prem ============================================================================== Date: Sat, 12 Nov 1994 12:49:28 -0800 From: prem@ix.netcom.com (Prem Sobel) Subject: Re: Algorithm for Diofantine Analysis To: rusin@math.niu.edu (Dave Rusin) You wrote: > >>For factoring Fermats function I have a different method >>based on his work and group theory which searches for number of the >>form (d = k*2^12+1) which a special property which can be tested in >>time O(1024). >I think you mean time O(sqrt(2^1024)/(2^12)=2^500). This is the smallest >fermat number not yet fully factored. While I expect it to be factored in >my lifetime, at present this is a more difficult challenge than any >task taking O(1024) steps (unless the big-O constant is very large!) To be precise, if you you give me a number and say it divides (or does not divide) 2^1024+1, I can tell you if it does or not in 1024 steps (with very small constant factor). >Still I am perplexed. Can you tell me how many solutions the diophantine >equation x^n+y^n=z^n has for _any_ n? Sure, if you allow for imaginary 2-adic numbers (or b-adic) the answer is an infinite number. If you wish to restict that to natural numbers (which I presume you do), the imaginary (annd complex) numbers get in the way. I am still searching for a method which will filter them out. >How about x^3+axz^2+bz^3=y^2z for any >a and b? (I was under the impression it was still an open question >to determine a general algortihm for computing the rank of any elliptic >curve over the rationals.) More generally I thought it was one of >Hilbert's problems to find a general algorithm for deciding whether >a family of diophantine equations had a solution; and that the answer >was, "there can be no such algorithm". If a solution exists my program will find it (if it does not need too much memory - those darn imaginaries fill it up :) For the equation above, I will try some examples with "random" choices of a and b and send the results to you later today. The fact that it is cubic may finness the imaginaries, I have to see. >Perhaps you can share your technique so I can see how you solve any >diophantine equation? I am writing a book about it, but can send you a binary version of the program (initially without explanation) for testing. The program will run on any 80386 or higher PC. Thi can probably be donnen by ftp. Prem ============================================================================== Date: Sat, 12 Nov 1994 13:39:57 -0800 From: prem@ix.netcom.com (Prem Sobel) Subject: Re: Algorithm for Diofantine Analysis To: rusin@math.niu.edu (Dave Rusin) Dave, I ran the program on four cases (results below). The solutions that were found were detected within a few seconds at most. After that, the program was busy calculating the digits of imaginary numbers so I interrupted it after disk activity stopped for about a minute. x^3+axz^2+bz^3=zy^2 This program solves simultaneous Diophantine equation each of different degree v variables for finite integer roots. [for a=3 b=2 the program yielded:] solution: x[0]=2 x[1]=-4 x[2]=1 solution: x[0]=2 x[1]=4 x[2]=1 solution: x[0]=-2 x[1]=-4 x[2]=-1 solution: x[0]=-2 x[1]=4 x[2]=-1 solution: x[0]=4 x[1]=-8 x[2]=2 solution: x[0]=4 x[1]=8 x[2]=2 solution: x[0]=-4 x[1]=-8 x[2]=-2 solution: x[0]=-4 x[1]=8 x[2]=-2 solution: x[0]=-6 x[1]=12 x[2]=-3 solution: x[0]=6 x[1]=12 x[2]=3 [for a=2 b=3 the program yielded:] solution: x[0]=3 x[1]=6 x[2]=1 solution: x[0]=-3 x[1]=6 x[2]=-1 solution: x[0]=6 x[1]=12 x[2]=2 solution: x[0]=-6 x[1]=12 x[2]=-2 [for a=2 b=6 the program yielded:] solution: x[0]=-1 x[1]=3 x[2]=-1 solution: x[0]=1 x[1]=3 x[2]=1 solution: x[0]=-2 x[1]=6 x[2]=-2 solution: x[0]=2 x[1]=6 x[2]=2 solution: x[0]=1 x[1]=-3 x[2]=1 solution: x[0]=-1 x[1]=-3 x[2]=-1 solution: x[0]=-4 x[1]=12 x[2]=-4 solution: x[0]=4 x[1]=12 x[2]=4 solution: x[0]=2 x[1]=-6 x[2]=2 solution: x[0]=-2 x[1]=-6 x[2]=-2 [for a=12 b=17 the program yielded:] solution: x[0]=-1 x[1]=-2 x[2]=1 solution: x[0]=-1 x[1]=2 x[2]=1 solution: x[0]=1 x[1]=-2 x[2]=-1 solution: x[0]=1 x[1]=2 x[2]=-1 solution: x[0]=-2 x[1]=-4 x[2]=2 solution: x[0]=-2 x[1]=4 x[2]=2 solution: x[0]=2 x[1]=-4 x[2]=-2 solution: x[0]=2 x[1]=4 x[2]=-2 solution: x[0]=3 x[1]=6 x[2]=-3 solution: x[0]=-3 x[1]=6 x[2]=3 solution: x[0]=2 x[1]=7 x[2]=1 solution: x[0]=-2 x[1]=7 x[2]=-1 solution: x[0]=-4 x[1]=-8 x[2]=4 solution: x[0]=-4 x[1]=8 x[2]=4 solution: x[0]=4 x[1]=-8 x[2]=-4 solution: x[0]=4 x[1]=8 x[2]=-4 solution: x[0]=6 x[1]=12 x[2]=-6 solution: x[0]=-6 x[1]=12 x[2]=6 solution: x[0]=4 x[1]=14 x[2]=2 solution: x[0]=-4 x[1]=14 x[2]=-2 ============================================================================== Date: Tue, 15 Nov 94 11:09:04 CST From: rusin (Dave Rusin) To: prem@ix.netcom.com, rusin@math.niu.edu Subject: Re: Algorithm for Diofantine Analysis I would be happy to look at your PC program. I can FTP it from your site if you'll give me a pointer. Any program that alleviates manual computation is always welcome. The real difficulty in Diophantine analysis is, typically, not the cumbersome computation but the lack of a stopping time. It is, I believe, basically impossible to write a general program which can be given enough information so that it can confidently say "no solutions exist" at any point; note the distinction between this and "I haven't found any solutions". Here are a couple of test problems for your program. Do the following have any solutions? If not, at what point do you make that conclusion? If so, can you find an explicit solution? Can you determine whether the solution set is finite or infinite? 1) y^2=x^3+1090 2) y^2z=x^3z+877xz^2 3) 3x^3+4y^3+5z^3=0 dave ============================================================================== Date: Wed, 16 Nov 1994 04:25:23 -0800 From: prem@ix.netcom.com (Prem Sobel) Subject: Re: Algorithm for Diofantine Analysis To: rusin@math.niu.edu (Dave Rusin) >I would be happy to look at your PC program. I can FTP it from your >site if you'll give me a pointer. <<<<<< Keep the following as user manual. >>>>> The net software that I have does not let my PC at home be ann ftp server, nor does the service provider give me that possibility. Either I can ftp the executable to you, or I can write a simple program to convert it to ascii and sennd you the C course to convert it back >Any program that alleviates manual computation is always welcome. The >real difficulty in Diophantine analysis is, typically, not the >cumbersome computation but the lack of a stopping time. It is, I >believe, basically impossible to write a general program which can be >given enough information so that it can confidently say "no solutions >exist" at any point; note the distinction between this and "I haven't >found any solutions". Yes, I am well aware of this and have designed in ways to guarantee termination of the program by setting various limits. One of these limits "sometimes" means no solutttion, but I have not made the program test for that because of the few ercent speed savings. Since it is a program for PCs and CTRL-C is not reliable under DOS (CTRL-ALT-DEL is safer under windows without rebooting the machine most of the time :), I had to put in a simple test in the inner loop). To stop the program push both shift keys simultaneously and hold until it stops. >Here are a couple of test problems for your program. Do the following >have any solutions? If not, at what point do you make that conclusion? >If so, can you find an explicit solution? Can you determine whether the >solution set is finite or infinite? My program makes no attempt at all to look for or identify cases where there ate an infinite number of solutions. I have another program, using the a sub set of the methods for first degree equations of any number of variables. It does print out a parameterized list of solutions or say if there is none, gcd>1. The program can be told to ignore different categories: trivial (0 solution), negative, and to stop at absolute value limit. I also can be told that another variable is a related denominator to oneother variable after *manual* substitution: (x=xn/xd), and multiplying by xd^d (where d is degree of equation) for each variable. The program will then make sure that gcd(xn,xd)==1 before reporting it. The program asks a series of questions to get the info of the equation(s) to solve. It writes this innformation to the file with name UTIL.INP. If a mistake has been made, or you wish to change just anything except the number of equations, variables and degree of the equation(s) then rename the file: REN UTIL.INP TEST.INP then edit the file and redirect it to the program: E_V_D_ 1) y^2=x^3+1090 solutions from program are: x y -9 19 -1 33 -9 -19 -1 -33 then program ran out of memory because I told it for this equation to use breadth first analysis of cases. For the other two I specified depth first and manually interrupted them (with both shift keys) after some many minutes. > 2) y^2z=x^3z+877xz^2 solutions from program: x y z 0 0 0 -1 -1 0 < -1 0 0 < -1 1 0 < 0 -1 0 < 0 0 -1 0 0 1 0 1 0 < 1 -1 0 1 0 0 < 1 1 0 More trivial solutions were not foun because the program is smart enough to test for internal repetitions of certain states and rejects persuing that line. The trivial solutions marked by '<' were not given when I manually divide by 'Z' befire entering the equation. > 3) 3x^3+4y^3+5z^3=0 Only the trivial solution x=y=z=0 was reported before I stopped it. Prem ============================================================================== Date: Wed, 16 Nov 94 11:38:28 CST From: rusin (Dave Rusin) To: prem@ix.netcom.com, rusin@math.niu.edu Subject: Re: Algorithm for Diofantine Analysis >Either I can ftp the executable to you, or I can write a simple Fine; ftp to math.niu.edu, go to pub/contrib and let me know you've put something there. >program to convert it to ascii and sennd you the C course to You ought to just use a standard uuencode for this since uudecode programs are common (on many platforms). >> 1) y^2=x^3+1090 >solutions from program are: > x y > -9 19 > -1 33 > -9 -19 > -1 -33 >then program ran out of memory because I told it for this equation >to use breadth first analysis of cases. Yes, this example is of interest for the following reason. It can be proven that except in trivial cases a cubic has a finite number of integral solutions. The bound is even explicit, but it's pretty frightening: best I know is that if y^2=x^3-k, then there can only be a finite number of solutions because x and y can be no greater than exp(k^8000000000). Whew! This example is illustrative. You found the only solutions with x<0. But you missed the solution x=28 187 351, y=149 651 610 621. So we have this theme: lack of small solutions doesn't mean there are no solutions. >> 2) y^2z=x^3z+877xz^2 >solutions from program: all trivial. This example underscores the previous theme: the basic solution to this one has x=(612 776 083 187 947 368 101)^2 z=(7 884 153 586 063 900 210)^2 See Bremmer-Cassels, Math of Computation 1984 >> 3) 3x^3+4y^3+5z^3=0 >Only the trivial solution x=y=z=0 was reported before I stopped it. Yes, but in light of the previous problems this leaves you uncertain whether or not any solutions exist. It turns out there are no solutions to this one, but this is for a very interesting reason. For quadratic equations one can show that a solution in integers exists if and only if the equation can be solved in the real line and in the p-adics for every p. This is known as the local-to-global principle. The example above shows the failure of this principle for cubics: while there are no solutions in Z , there are real solutions and solutions in the p-adics for every p. (Incidentally, this principle provides an efficient method of solving homogeneous quadratics, since it is straightforward to solve equations mod p^n for any p and n). I hope you don't feel I'm giving you a hard time here, it's just that you need to be really up front about what your program can propose to do. Undoubtedly it will only present correct solutions to equations, and you may well have ways of finding some quickly. The difficulty is that you cannot reasonably have the program stop itself at any point, nor can you let its silence convince a user that the equation has no solutions. It sounds like you have incorporated specific routines for certain families of problems. I don't know if you are aware of methods for solving other types. For example, single quadratics in 2 or 3 variables often reduce to Pell's equation. The solutions to most cubics form elliptic curves. In both cases, there are known methods (e.g. continued fractions) for solving some problems, and there is a lengthy literature on the use of group structure for finding all solutions given just some. You may wish to compare the programs provided in the PC package UBASIC (available at Simtel, etc.); these programs efficiently solve certain common number-theoretic problems. dave ============================================================================== Date: Wed, 16 Nov 1994 19:16:03 -0800 From: prem@ix.netcom.com (Prem Sobel) Subject: Re: Algorithm for Diofantine Analysis To: rusin@math.niu.edu (Dave Rusin) Dave >>Either I can ftp the executable to you, or I can write a simple >Fine; ftp to math.niu.edu, go to pub/contrib and let me know you've >put something there. Ok, the program has been up loaded. Remember it is an executable for a PC running DOS with an 80386 or higher CPU. So when you move it to a PC remember to use binnary mode or the file will get modified. The program asks you describe the equation(s). The only question that may be not obvious is the one about associated denominators. All variables are named x[0], x[1], ... So if you wanted a rational solution for variable, z, substitute: z=x[i]/x[j] (i~=j) multiply by x[j] to the highest power of z. Then when filling the questions give 'j' as the associated denominator. For all others give -1 as the associated denominator. This version of the program is limited to 32 bit integers. >You ought to just use a standard uuencode for this since uudecode >programs are common (on many platforms). On UNIX, but I am running DOS and WIndows and dod not have it. Anyway the binnary is there. Experiment and enjoy. Let me know what happens. >>> 1) y^2=x^3+1090 >>solutions from program are: >> x y >> -9 19 >> -1 33 >> -9 -19 >> -1 -33 >>then program ran out of memory because I told it for this equation >>to use breadth first analysis of cases. > ... You found the >only solutions with x<0. But you missed the solution >x=28 187 351, y=149 651 610 621. >So we have this theme: lack of small solutions doesn't mean there are >no solutions. A PC is probaly too small for numbers like order 10^11 for y because of the memory constraints. >>> 2) y^2z=x^3z+877xz^2 >>solutions from program: >all trivial. This example underscores the previous theme: the basic >solution to this one has >x=(612 776 083 187 947 368 101)^2 >z=(7 884 153 586 063 900 210)^2 >See Bremmer-Cassels, Math of Computation 1984 Interesting. Why isn't the common factor of 'z' removed? >>> 3) 3x^3+4y^3+5z^3=0 >>Only the trivial solution x=y=z=0 was reported before I stopped it. >Yes, but in light of the previous problems this leaves you uncertain >whether or not any solutions exist. It turns out there are no solutions >to this one, but this is for a very interesting reason. For quadratic >equations one can show that a solution in integers exists if and only >if the equation can be solved in the real line and in the p-adics for >every p. This is known as the local-to-global principle. The example >above shows the failure of this principle for cubics: while there are >no solutions in Z , there are real solutions and solutions in >the p-adics for every p. Yes, in the 2-adics the imaginary solutions would be of the form: sqrt(-7-8*k) >(Incidentally, this principle provides an efficient method of solving >homogeneous quadratics, since it is straightforward to solve equations >mod p^n for any p and n). >I hope you don't feel I'm giving you a hard time here, it's just that >you need to be really up front about what your program can propose to >do. I am well aware of that. There is no promise to find all solutionns. But will find those that exist within its range if memory is not a problem. Unfortunately equationns with high v+d (v: number of variables, d: degree of equation) take a lot of memory: proportional to (v+d)!/(v!*d!) >Undoubtedly it will only present correct solutions to equations, and >you may well have ways of finding some quickly. The difficulty is that >you cannot reasonably have the program stop itself at any point, nor >can you let its silence convince a user that the equation has no >solutions. Agreed, and the program asks before starting for explicit magnitude limits in two forms. Onne the maximim bit to try for, and for each variable an absolute magnitude limit. >It sounds like you have incorporated specific routines for certain >families of problems. I don't know if you are aware of methods for >solving other types. For example, single quadratics in 2 or 3 variables >often reduce to Pell's equation. The solutions to most cubics form >elliptic curves. In both cases, there are known methods (e.g. continued >fractions) for solving some problems, and there is a lengthy literature >on the use of group structure for finding all solutions given just some. I need to investigate these some more. The program uses a more general approach using 2-adics and parity. Prem ============================================================================== Date: Wed, 16 Nov 1994 19:16:03 -0800 From: prem@ix.netcom.com (Prem Sobel) Subject: Re: Algorithm for Diofantine Analysis To: rusin@math.niu.edu (Dave Rusin) Dave >>Either I can ftp the executable to you, or I can write a simple >Fine; ftp to math.niu.edu, go to pub/contrib and let me know you've >put something there. Ok, the program has been up loaded. Remember it is an executable for a PC running DOS with an 80386 or higher CPU. So when you move it to a PC remember to use binnary mode or the file will get modified. The program asks you describe the equation(s). The only question that may be not obvious is the one about associated denominators. All variables are named x[0], x[1], ... So if you wanted a rational solution for variable, z, substitute: z=x[i]/x[j] (i~=j) multiply by x[j] to the highest power of z. Then when filling the questions give 'j' as the associated denominator. For all others give -1 as the associated denominator. This version of the program is limited to 32 bit integers. >You ought to just use a standard uuencode for this since uudecode >programs are common (on many platforms). On UNIX, but I am running DOS and WIndows and dod not have it. Anyway the binnary is there. Experiment and enjoy. Let me know what happens. >>> 1) y^2=x^3+1090 >>solutions from program are: >> x y >> -9 19 >> -1 33 >> -9 -19 >> -1 -33 >>then program ran out of memory because I told it for this equation >>to use breadth first analysis of cases. > ... You found the >only solutions with x<0. But you missed the solution >x=28 187 351, y=149 651 610 621. >So we have this theme: lack of small solutions doesn't mean there are >no solutions. A PC is probaly too small for numbers like order 10^11 for y because of the memory constraints. >>> 2) y^2z=x^3z+877xz^2 >>solutions from program: >all trivial. This example underscores the previous theme: the basic >solution to this one has >x=(612 776 083 187 947 368 101)^2 >z=(7 884 153 586 063 900 210)^2 >See Bremmer-Cassels, Math of Computation 1984 Interesting. Why isn't the common factor of 'z' removed? >>> 3) 3x^3+4y^3+5z^3=0 >>Only the trivial solution x=y=z=0 was reported before I stopped it. >Yes, but in light of the previous problems this leaves you uncertain >whether or not any solutions exist. It turns out there are no solutions >to this one, but this is for a very interesting reason. For quadratic >equations one can show that a solution in integers exists if and only >if the equation can be solved in the real line and in the p-adics for >every p. This is known as the local-to-global principle. The example >above shows the failure of this principle for cubics: while there are >no solutions in Z , there are real solutions and solutions in >the p-adics for every p. Yes, in the 2-adics the imaginary solutions would be of the form: sqrt(-7-8*k) >(Incidentally, this principle provides an efficient method of solving >homogeneous quadratics, since it is straightforward to solve equations >mod p^n for any p and n). >I hope you don't feel I'm giving you a hard time here, it's just that >you need to be really up front about what your program can propose to >do. I am well aware of that. There is no promise to find all solutionns. But will find those that exist within its range if memory is not a problem. Unfortunately equationns with high v+d (v: number of variables, d: degree of equation) take a lot of memory: proportional to (v+d)!/(v!*d!) >Undoubtedly it will only present correct solutions to equations, and >you may well have ways of finding some quickly. The difficulty is that >you cannot reasonably have the program stop itself at any point, nor >can you let its silence convince a user that the equation has no >solutions. Agreed, and the program asks before starting for explicit magnitude limits in two forms. Onne the maximim bit to try for, and for each variable an absolute magnitude limit. >It sounds like you have incorporated specific routines for certain >families of problems. I don't know if you are aware of methods for >solving other types. For example, single quadratics in 2 or 3 variables >often reduce to Pell's equation. The solutions to most cubics form >elliptic curves. In both cases, there are known methods (e.g. continued >fractions) for solving some problems, and there is a lengthy literature >on the use of group structure for finding all solutions given just some. I need to investigate these some more. The program uses a more general approach using 2-adics and parity. Prem ============================================================================== Date: Thu, 17 Nov 94 01:27:24 CST From: rusin (Dave Rusin) To: prem@ix.netcom.com, rusin@math.niu.edu Subject: Re: Algorithm for Diofantine Analysis I'll have a look at your program tomorrow; just thought I'd correct my typo: >>>> 2) y^2z=x^3z+877xz^2 >>>solutions from program: >>all trivial. This example underscores the previous theme: the basic >>solution to this one has >>x=(612 776 083 187 947 368 101)^2 >>z=(7 884 153 586 063 900 210)^2 >>See Bremmer-Cassels, Math of Computation 1984 >Interesting. Why isn't the common factor of 'z' removed? Whoops! There shouldn't be a 'z' next to the x^3. I was trying to make the 2-variable problem homogeneous. sorry. Anyway the point was just to impress you with an equation with small coefficients and large solution. You can find more such examples of the type x^2 - N y^2 = 1 for different N. This problem is critical in algebraic number theory and fortunately admits an efficient solution but the smallest x and y can be much larger than N (something like O( exp sqrt N ). ) dave