question on diophantine equations in Mathematica

[Ivan Smirnov]

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

[Andrzej Kozlowski]

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!).

[Andrzej Kozlowski]

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 <ak...@mimuw.edu.pl>
> This seems to show that there are only trivial solutions for 1<=t<==90000

[Andrzej Kozlowski]

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 <ak...@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 <ak...@mimuw.edu.pl>

> > This seems to show that there are only trivial solutions for 1<=t<=90000

[Andrzej Kozlowski]

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

>> {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}}}

[Adam Strzebonski]

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

>>>>> 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!).

[Ivan Smirnov]

Am I right that with such constraints Reduce now is many faster than Solve?

2011/1/14 Adam Strzebonski <ad...@wolfram.com>

[Adam Strzebonski]

For Diophantine equations Solve and Reduce use the same code, so there
should be no speed difference.

Best Regards,

Adam Strzebonski
Wolfram Research

Ivan Smirnov wrote:
> Am I right that with such constraints Reduce now is many faster than Solve?
>

> 2011/1/14 Adam Strzebonski <ad...@wolfram.com <mailto:ad...@wolfram.com>>

> <mailto:ak...@mimuw.edu.pl>>

> <mailto:ak...@mimuw.edu.pl>>

[Ivan Smirnov]

If so, why then your PC computed it from 1 to 10^10 (in such big interval)
with only 269.967 and my is still computing yet, more than 20 minutes?
I asked it only from this point. It can be only from hardware difference.
What is your CPU&RAM&bitness, Adam?

2011/1/14 Adam Strzebonski <ad...@wolfram.com>

[Adam Strzebonski]

I am using a 3 GHz Intel Core i7 CPU with 6 GB of RAM available
for the virtual machine. MaxMemoryUsed[] gives 828 MB, so if your
computer has only 1 GB of RAM it might be swapping memory.

Adam

Ivan Smirnov wrote:
> If so, why then your PC computed it from 1 to 10^10 (in such big
> interval) with only 269.967 and my is still computing yet, more than 20
> minutes?
> I asked it only from this point. It can be only from hardware
> difference. What is your CPU&RAM&bitness, Adam?
>

> 2011/1/14 Adam Strzebonski <ad...@wolfram.com <mailto:ad...@wolfram.com>>

>
> For Diophantine equations Solve and Reduce use the same code, so there
> should be no speed difference.
>
>
> Best Regards,
>
> Adam Strzebonski
> Wolfram Research
>
>
> Ivan Smirnov wrote:
>
> Am I right that with such constraints Reduce now is many faster
> than Solve?
>
> 2011/1/14 Adam Strzebonski <ad...@wolfram.com

> <mailto:ad...@wolfram.com> <mailto:ad...@wolfram.com

> <mailto:ak...@mimuw.edu.pl

> <mailto:ak...@mimuw.edu.pl