Re: question on diophantine equations in Mathematica
- To: mathgroup at smc.vnet.net
- Subject: [mg115542] Re: question on diophantine equations in Mathematica
- From: Adam Strzebonski <adams at wolfram.com>
- Date: Fri, 14 Jan 2011 06:17:16 -0500 (EST)
Reduce does a case-by-case search here, but it chooses the variables
with smallest ranges of values for the search.
In[1]:= form = x^10 + y^10 + z^10 == t^2 && x >= 0 && y >= 1 &&
x <= y && y <= z && 1 <= t <= 250000;
In[2]:= vars = {x, y, z, t};
In[3]:= {Ceiling[MinValue[#, form, vars]],
Floor[MaxValue[#, form, vars]]}&/@vars
Out[3]= {{0, 10}, {1, 11}, {1, 12}, {2, 250000}}
Reduce does case-by-case search for the first 3 variables,
so the problem reduces to solving
In[4]:= 11 11 12
Out[4]= 1452
univariate quadratic equations. The most time-consuming part
here is computing the MinValue/MaxValue (8 CAD problems with
4 variables).
This method will do exhaustive search on {x, y, z} as long as
the number of possible {x, y, z} values does not exceed 10000.
If you want it to do larger searches you need to change
the second value of the system option
In[5]:= "ExhaustiveSearchMaxPoints"/.("ReduceOptions"/.SystemOptions[])
Out[5]= {1000, 10000}
This increases the maximum number of search points to 10^6.
In[6]:= SetSystemOptions["ReduceOptions"->{"ExhaustiveSearchMaxPoints"->
{1000, 10^6}}];
This proves that the problem has no solutions with t <= 10^10
(a search over 828630 cases).
In[7]:= Reduce[x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y &&
x <= y && y <= z && 1 <= t <= 10^10, {x, y, z, t}, Integers] // Timing
Out[7]= {269.967, False}
Best Regards,
Adam Strzebonski
Wolfram Research
Andrzej Kozlowski wrote:
> Actually Solve (and Reduce) are remarkably efficient at solving this problem. It is better to reformulate it by requiring that the two smallest values be larger than 0. This eliminates all trivial solutions. Solve (and Reduce) then work remarkably fast for very large numbers t, e.g.
>
> Solve[
> x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y && x <= y && y <= z &&
> 1 <= t <= 250000, {x, y, z, t}, Integers] // Timing
>
> {1.80372,{}}
>
> Now look at this:
>
>
> In[1]:= Solve[
> x^10 + y^10 + z^10 == t^2 && 0 <= x && 0 < y && x <= y && y <= z &&
> 1 <= t <= 350000, {x, y, z, t}, Integers] // Timing
>
> Out[1]= {1.90608,{}}
>
> This is so fast that it almost excludes the possibility of "case by case" verification. Moreover, solving the problem for t= 350,000 took only slightly longer than for t= 250,000.
>
> If this is indeed a valid proof (and I think it is - Reduce gives the same answer) then it looks like Solve is really using some knowledge of Diophantine equations to solve this. It would be really interesting to know what is going on. I almost inclined to believe that Solve is able to prove that there are no solutions for all t, but running it without a bound on t produces a useless (in this context) "conditional" answer:
>
> Solve[x^10+y^10+z^10==t^2&&0<=x&&0<y&&x<=y&&y<=z,{x,y,z,t},Integers]
> (Output deleted).
>
> I do hope we get some insight into what Solve is doing. It is beginning to look fascinating, although I am probably missing something simple...
>
> Andrzej Kozlowski
>
> On 12 Jan 2011, at 19:41, Andrzej Kozlowski wrote:
>
>> Yes, but I think I unintentionally deceived you (and myself). Mathematica caches its results and recall that I tried solving this several times with different numbers before I run Timing. mathematica obviously remembered all the answers and when I tried measuring the time taken it was amazingly fast. I should have found it suspicious but as I was busy with other things I did not notice anything.
>>
>> Now that I tried again with a fresh kernel the results are much less impressive: in fact much closer to yours.
>>
>> But note that now it is clear that Solve is very much faster than PowersRepresentatins (it looked the other way round before). In fact Solve deals with this impressively fast:
>>
>> Timing[
>> Select[Table[
>> PowersRepresentations[t^2, 3, 10], {t, 1, 90000}], #1 != {} & ]]
>>
>> {641.343049, {{{0, 0, 1}}, {{0, 0, 2}}, {{0, 0, 3}}, {{0, 0,
>> 4}},
>> {{0, 0, 5}}, {{0, 0, 6}}, {{0, 0, 7}}, {{0, 0, 8}},
>> {{0, 0, 9}}}}
>>
>>
>> Timing[
>> Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y <= z &&
>> 1 <= t <= 90000, {x, y, z, t}, Integers]]
>>
>> {1.161798, {{x -> 0, y -> 0, z -> 1, t -> 1},
>> {x -> 0, y -> 0, z -> 2, t -> 32}, {x -> 0, y -> 0, z -> 3,
>> t -> 243}, {x -> 0, y -> 0, z -> 4, t -> 1024},
>> {x -> 0, y -> 0, z -> 5, t -> 3125}, {x -> 0, y -> 0, z -> 6,
>> t -> 7776}, {x -> 0, y -> 0, z -> 7, t -> 16807},
>> {x -> 0, y -> 0, z -> 8, t -> 32768}, {x -> 0, y -> 0, z -> 9,
>> t -> 59049}}}
>>
>> This suggests strongly that you should in fact use Solve. However, you should not try to test for too large a group of solutions at a time. For example, you can get the next 10,000 quickly:
>>
>> Timing[
>> Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y <= z &&
>> 90000 <= t <= 100000, {x, y, z, t}, Integers]]
>>
>> {1.48964,{{x->0,y->0,z->10,t->100000}}}
>>
>> But the time for this 10,000 is longer than for the previous 90,000!
>>
>> With best regards
>>
>> Andrzej
>>
>>
>>
>> On 12 Jan 2011, at 16:03, Ivan Smirnov wrote:
>>
>>> Oh, it's very cool computer. What model of CPU, Intel or AMD?
>>> I just thought that time was in seconds, but surprised that it took so few time and asked.
>>> I have only 1.6 Ghz Acer (Intel T5500) with 1 GB Ram, so for 1..90000 it took 1034 seconds to compute...
>>>
>>> 2011/1/12 Andrzej Kozlowski <akoz at mimuw.edu.pl>
>>> I am using Mathematica 8 on 2.66 Ghz Mac Book Pro with 8 gigabytes of Ram. The time is measured in seconds. With Mathematica 8 you can also get the same answer with Solve:
>>>
>>> Timing[
>>> Solve[x^10 + y^10 + z^10 == t^2 && 0 <= x && x <= y && y <= z &&
>>> 1 <= t <= 90000, {x, y, z, t}, Integers]]
>>>
>>> {1.01969,{{x->0,y->0,z->1,t->1},{x->0,y->0,z->2,t->32},{x->0,y->0,z->3,t->243},{x->0,y->0,z->4,t->1024},{x->0,y->0,z->5,t->3125},{x->0,y->0,z->6,t->7776},{x->0,y->0,z->7,t->16807},{x->0,y->0,z->8,t->32768},{x->0,y->0,z->9,t->59049}}}
>>>
>>> I think for very large numbers PowersRepresentations will give you more satisfactory answers. For example, compare the output
>>>
>>> Solve[x^10 + y^10 + z^10 == 10^20 && 0 <= x && x <= y && y <= z, {x,
>>> y, z, t}]
>>>
>>> with
>>>
>>> PowersRepresentations[10^21, 3, 10^20]
>>>
>>> {}
>>>
>>> Andrzej Kozlowski
>>>
>>>
>>>
>>>
>>> On 12 Jan 2011, at 13:16, Ivan Smirnov wrote:
>>>
>>>> Hello, Andrzej.
>>>> Many thanks for reply.
>>>> What PC do you use (OS, CPU & RAM) and how many minutes did it take to compute, what is 0.872...?
>>>> What is the upper margin for t which can cause overflow?
>>>> Do you have any other ideas how to increase performance for my task?
>>>> Will be very glad for help
>>>>
>>>> 2011/1/12 Andrzej Kozlowski <akoz at mimuw.edu.pl>
>>>> This seems to show that there are only trivial solutions for 1<=t<=90000
>>>>
>>>> Timing[
>>>> Select[Table[
>>>> PowersRepresentations[t^2, 3, 10], {t, 1, 90000}], #1 != {} & ]]
>>>>
>>>> {0.8722430000000259, {{{0, 0, 1}}, {{0, 0, 2}}, {{0, 0,
>>>> 3}}, {{0, 0, 4}}, {{0, 0, 5}}, {{0, 0, 6}}, {{0, 0, 7}},
>>>> {{0, 0, 8}}, {{0, 0, 9}}}}
>>>>
>>>> The algorithm basically uses "brute force" so you will start getting overflows for very large t.
>>>>
>>>> Andrzej Kozlowski
>>>>
>>>>
>>>>
>>>> On 12 Jan 2011, at 01:25, Ivan Smirnov wrote:
>>>>
>>>>> Hi all,
>>>>> I've installed trial of Mathematica 8.
>>>>> I would like to search for possible solutions of diophantine equation
>>>>> x^10+y^10+z^10=t^2.
>>>>> How to do this efficiently?
>>>>> FindInstance seems to be VERY slow! And indeed it doesn't always find every
>>>>> solution of diophantine equations. For example I've tried it with
>>>>> x^4+y^4+z^4=t^4 and it didn't find anything (but there are solutions!).
>>>>> And Solve command just don't want to search! With some seconds it gives
>>>>> During evaluation of In[1]:= Solve::svars: Equations may not give solutions
>>>>> for all "solve" variables. >>
>>>>> I will be very glad if someone make INDEED FAST algorithm for searching.
>>>>>
>>>>> Ivan
>>>>
>>>
>>
>>
>
>