Help with programming problem: a^4+8b^4 = c^4+8d^4? (Relevant for quasi-Waring problem)
TPiezas
By Ryley's Theorem, it has long been known that any N is the sum of
three rational cubes (positive or negative). The proof is a rather
simple algebraic identity. Also, by means of an identity, A.J.
Choudhry proved than any N is the sum of 6 fifth powers of rationals,
and 8 seventh powers of rationals (On Sums of Seventh Powers; 1999).
Though he didn't spell it out, the latter result depended on solving
the simultaneous eqns:
a^2+32b^2 = c^2+32d^2 (eq.1a)
a^4+8b^4 = c^4+8d^4 (eq.1b)
He gave a 33-digit soln {a,b,c,d}. But this was a decade ago, with
slower computers, so he may have used assumptions that skipped the
smaller ones. Question 1: Anyone can find smaller solns to eq.1a and
b?
To make things easier, the general case is this:
a^2+m^5b^2 = c^2+m^5d^2 (eq.2a)
a^4+m^3b^4 = c^4+m^3d^4 (eq.2b)
for m > 1. (Note how the paired exponents add up to 7.) Choudhry
simply chose m = 2.
Question 2: If anyone can find small solns to eq.2a,b for any m > 1,
then you'll have a new proof that any number N is the sum of 8 seventh
powers of rationals.
- Titus
alainv...@gmail.com
Bonjour Titus,
Question 1 reminds me about 'Gauss forms',
(p,q) = p+q*2sqrt(2),
(p,-q)= p-q*2sqrt(2),
(p,q)^2 =(p^2+8q^2,2pq) ,(p,-q)^2 =(p^2+8q^2,-2pq)
So, in our case(a^2,b^2)=(a^4+8b^4,2a^2b^2) ,
(a^2,-b^2)=(a^4+8b^4,-2a^2b^2)
Won't tell you more,
Alain
TPiezas
>
> - Show quoted text -
I dissected Choudhry's approach (he didn't spell it out in his paper)
and managed to reverse-engineer how he did it. It reduces to solving
the "elliptic curve",
(p^2-m^12q^2)(m^2p^2-q^2) = y^2
for some constant m. For m = 2, he found the non-trivial 16-and-17-
digit soln:
p = 5911167604843137
q = 12317476831120126
Multiplied together with some other numbers results in his 33-digit
soln to the system.
But how do we check if this {p,q} is the smallest? (Using this soln,
I found some bigger ones instead.)
(At least this curve reduces the number of variables we have to deal
with, and proves that there are an INFINITE number of ways to express
any number N as the sum of eight 7th powers of rationals.
- Titus
dave.rusin
> Choudhry proved than any N is the sum of 6 fifth powers of rationals,
> and 8 seventh powers of rationals (On Sums of Seventh Powers; 1999).
>
> Though he didn't spell it out, the latter result depended on solving
> the simultaneous eqns:
>
> a^2+32b^2 = c^2+32d^2 (eq.1a)
> a^4+8b^4 = c^4+8d^4 (eq.1b)
>
> He gave a 33-digit soln {a,b,c,d}. But this was a decade ago, with
> slower computers, so he may have used assumptions that skipped the
> smaller ones. Question 1: Anyone can find smaller solns to eq.1a and
> b?
I can find 33-digit solutions. These are almost surely the smallest
available (setting aside trivial solutions like (1,1,1,1) of course).
So the answer to Question 1 must be "no".
You then propose a generalization:
> a^2+m^5b^2 = c^2+m^5d^2 (eq.2a)
> a^4+m^3b^4 = c^4+m^3d^4 (eq.2b)
> Question 2: If anyone can find small solns to eq.2a,b for any m > 1,
> then you'll have a new proof that any number N is the sum of 8 seventh
> powers of rationals.
There are values of m for which solutions exist. I didn't find any;
I expect them to be larger, not smaller, than the solutions for m=2.
What follows is a detailed summary of what I found and what remains to
be done. The only thing standing in the way of finding "small"
solutions
is computer speed; check back in ten years or so and they should be
easy to find. (In 2009 I find the solutions for m=2 in just minutes.)
You probably intended the solutions to eq2 to be integral
but there is no loss of generality in settling for rational
solutions, since we can always scale (a,b,c,d) to integers.
With this in mind, note that there is a one-to-one correspondence
(a,b,c,d) -> (a,B,c,D)
(given by the equations B = b/m, D = d/m) between the solutions
to your system and the solutions to the system
a^2 + m^7 B^2 = c^2 + m^7 D^2 (eq.3a)
a^4 + m^7 B^4 = c^4 + m^7 D^4 (eq.3b)
I like this formulation better because I can simply abbreviate
M = m^7 and avoid some of the large exponents. In other words,
our goal is to find rational solutions to the systems
a^2 + M B^2 = c^2 + M D^2 (eq.4a)
a^4 + M B^4 = c^4 + M D^4 (eq.4b)
where our interest is in the cases where M is a seventh power,
but we can perform the same analysis for any M .
Now, you can solve these equations for B^2 and D^2; I get
B^2 = r * a^2 + s * c^2 and D^2 = s * a^2 + r * c^2
where r = (1 - 1/M)/2 and s = (1 + 1/M)/2 (so that r+s=1).
So the equations "eq4" can simply be stated in this way: we are
looking
for pairs (a,c) which make each of two quadratic expressions into
perfect
squares. That alone guarantees that you are looking at an elliptic
curve.
Indeed, in our case, each condition may be "solved" separately: if r
+s=1,
then r * a^2 + s * c^2 is a square precisely when a/c = (S^2-s)/
(R^2-r)
for some rational R,S with R+S=1. So, given r,s with r+s=1 we
seek
R1,S1,R2,S2 with R1+S1=1, R2+S2=1, and
(S1^2-s)/(R1^2-r) = (R2^2-r)/(S2^2-s) .
We can remove the symmetry, exchanging all r's for 1-s's; then this
system
becomes a single cubic equation in S1 and S2 :
S1*S2*(S1+S2) - ( 2*S1*S2 + s*(S1^2+S2^2) ) + s*(S2+S1) = 0
With some experimentation I find that the transformation
{ S1=X-Y/(X+s-1), S2=X+Y/(X+s-1) }
changes this into Y^2 = X(X-1)(X-s)(X+s-1) . From Y^2=quartic
it's a standard move to change the equation into V^2=cubic: I might
use
{X = (s-1)/((U+1)*s-1), Y=(s-1)*V*s^2/((U+1)*s-1)^2}
to get the normal form for an elliptic curve: it is simply
V^2 = U * (U + 1) * (U + q^2) (eq 5)
where in our case q = (1 - 1/s) = (1-M)/(1+M) = (1-m^7)/(1+m^7)
Note that by allowing M to vary over all rational numbers, we will
get
every elliptic curve of the type in (eq 5), i.e. q will range over
all rational numbers too.
You can trace all this back, too: from a point (U,V) on the elliptic
curve of eq5, we successively get (X,Y), then (S1,S2), then
(a,c),
then (B,D), and then (if M = m^7 for some m), (b,d) too.
I get
a = ( (M-1)^3+(M-1)*(5*M^2+3)*U+3*(M-1)*(M+1)^2*U^2-(M+1)^3*U^3 )
+ 4*M*(M-1)*(M+1) * V ,
B = ( (M-1)^3+(3*M-1)*(M-1)^2*U+(3*M+1)*(M+1)^2*U^2+(M+1)^3*U^3 )
+ ( 2*(M+1)*(M-1)^2+2*(M+1)^3*U ) * V,
c = ( -(M-1)^3+3*(M+1)*(M-1)^2*U+(M+1)*(5*M^2+3)*U^2+(M+1)^3*U^3 )
+ 4*M*(M+1)^2*U * V,
D = ( (M-1)^3+(M-1)*(3*M+1)*(M+1)*U+(M-1)*(3*M-1)*(M+1)*U^2+(M+1)
^3*U^3 )
+ ( 2*(M-1)*(M+1)^2+2*(M-1)*(M+1)^2*U ) * V
and you can check directly that these satisfy your eq4 as long as
V^2 = U * (U+1) * (U + ((1-M)/(1+M))^2 )
Very well, then: we see now that your question can be reframed
precisely as: for which values of M, which are rational 7th powers,
does the elliptic curve described by eq 5 have rational points?
Here we have to watch out for "trivial" solutions. These curves all
have "points of order 2" at (U,V) = (r,0) where r = 0, -1, -q^2
are the roots of the cubic in eq5. Also the point (0,0) is the
double of the point at (U,V) = (q, q^2+q), making the latter an
element of order 4. So these curves automatically have Z4 x Z2
torsion.
The 8 torsion elements on the curve correspond to the 16 solutions
(a,B,c,D)= (+-1,+-1,+-1,+-1) .
But are there other points, too? The answer in general is "no",
even if we add the stipulation that M be 7th power. I tried some
examples using the Maple package APECS. When q= 0 or +-1, the curve
is
not elliptic. Otherwise it is an elliptic curve, and as such the
rational
points form a group; modulo the torsion subgroup Z2xZ4 it is a free
abelian group of finite rank.
For these curves it turns out that this rank is 0 (i.e. there are no
rational points besides the torsion points) if
q = 2,3,4,5,6,8,9; 1/2,3/2,7/2,11/2; 4/3,5/3,7/3,8/3,11/3; ...
The rank is 1 if q=7, 10, 5/2, 9/2, 10/3, 11/4, 13/4, ...
I did not encounter any curves with rank 2 or larger but I have no
doubt that they exist.
Your interest is when q = (1-m^7)/(1+m^7). Even for small integers
m,
the coefficients in a minimal model of these elliptic curves tend to
be large, making it a slower process to compute the rank, and indeed
APECS is not able to resolve these curves with much success.
The rank is definitely 0 when m=3 or m=7. It's probably also zero
when m=4 or m=8 , based on computations testing the vanishing of L-
series.
So there is no point to looking for solutions to your original
Diophantine problem for these values of m.
On the other hand, the rank is evidently 1 when m=5 or m=6.
I was unable to find any points in these cases but a parity conjecture
(which is almost surely true) implies there must be non-torsion
points.
So these might be candidates for you to search for solutions.
In my analysis there is no reason to restrict to integral m; I
don't know whether that is true in the original application, but I
tested some fractional m as well. From the symmetry of the situation
-m and 1/m give the same elliptic curve as m itself, so I just
tried some m between 0 and 1. In some cases the rank is 0 (i.e.
there
are no non-torsion rational points), or likely zero (I didn't wait for
an L-series computation): m=2/3, 5/6, 6/7, ... In other cases the
rank is likely 1 by the parity conjecture, but I found no points:
m = 3/4, 2/5, 3/5, 4/5, 2/7.
So there are some candidate values of m for which we can expect to
find rational points. Since the ranks are 1 in all these cases, the
points will come in clusters of 8 (because there are 8 torsion
points),
and roughly speaking the number of digits needed to write down the
clusters will grow linearly from cluster to cluster.
Actually finding the points is difficult! Fortunately, these curves
have a lot of 2-torsion, which makes them at least not as difficult as
one might fear. For curves with 2-torsion, there is a process called
"2-descent" that allows one to search smaller spaces of candidates;
indeed within the last decade or so it has been possible to use an
enhanced version of this known as "4-descent"; this is even encoded
in the computer-algebra program Magma. The algorithms do work here;
but the parameters involved are so large that the algorithms will
need run times measured in days or weeks or more.
I did use Magma to find points on one of these curves, namely the one
for m=2.
<***Warning: I am now launching into high-tech speak for this
paragraph**>
The case m=2 leads to the elliptic curve whose minimal model is
[0, 1, 0, -89554944, -325154859084]. The process of 2-descent leads
to
the covering space y^2 = 1153*x^4 + 1452*x^3 + 34648*x^2 + 16632*x +
229156
and then the process of 4-descent leads to a certain quadratic form in
4 variables (described by 1- and 2-digit coefficients). There is a
point (-277: 2328: -832: 77) on this curve, which then can be traced
back to the original elliptic curve, giving a point
x= -35162436586491838806/6160687792022401
y= -4514425977711897984681000960/483552686669540063587649
in that minimal model; translating from those coordinates to the
coordinates used in eq5, we have found the point
U = 6034953010201600/125734781820801,
V = 5434062187470986141812960/16013195429712680038527
Taking the previous (U,V) pair through the transformations earlier
in this article, we find the solution (a,B,c,D) =
( 292565171139318137956759657471297,
431710411310215968145096114505983,
534407060429869176086407612538177,
429896971805380956160913115810943)
of the original pair of Diophantine equations. I assume that (after
doubling two of these to get (a,b,c,d) instead) these are the 33-digit
solutions you spoke of. (Obviously you can change signs on a,b,c,d to
get the full cluster of 16 quadruples.)
The next cluster involves points like this one:
U =
1325348417100162540645100726062969127084261146152135130017692161/
115126399316506788691607329692770944349968693080044545516441600,
V =
225218744543831505166405322378873555512239195841098051246440443$
4227939355213365762575305988723413/
5311666976897167889582811972524389489956376964713508524271559260$
0121258031886545925692162048000
so as you can see there is little hope of getting "nicer" solutions
than the one in the previous paragraph, if we stay on the curve for
m=2.
(This particular point (U,V) leads to a solution with a =
10458426706611658974242356821584852747222445600876291195633397326$
761434112935159060976480699895946813024357269367986512562534257921 .)
(It is possible that this process has failed to find some rational
points: that is, it is possible that I have found a point which is a
multiple of a generator rather than being a generator of this cyclic
group. In practice this is unlikely, especially when the points'
coordinates are so large. But it does mean that I cannot assert that I
have found the "smallest" points on the curve.)
Still reading along? OK!
I tried the other curves of interest to you which APECS reported to
have rank 1: those for m=5, 6, 3/4, 2/5, 3/5, 4/5, 2/7. These
numbers
may not look "big" to you, but they are for this problem! Recall that
I said the "minimal model" for m=2 is written this way:
[0, 1, 0, -89554944, -325154859084]
Well, moving next to the case m=5 we find the corresponding model to
be
[0, 1, 0, -776102147293090820, -263163975043291295376530400]
For similarly-structured elliptic curves (like these), the run time of
the algorithms I use depends on the size of these arguments; so
increasing
these arguments by many orders of magnitude is going to mean a much,
much longer run time in general. After a day of poking around on
several curves, I did not succeed in finding any points in any of
these elliptic curves, even though it is to be expected that they
exist.
And these are the simplest cases of curves with positive rank; we
can try larger values of m but they will give some very large
integer coefficients (and correspondingly large search spaces).
In summary, then, I have shown how the original pair of equations
leads to a nice 1-parameter family of elliptic curves. Some of these
curves have positive rank, i.e. there are interesting rational
solutions
to your original equations for some m. But the range of m which may
be tested at all, and the sizes (heights) of the rational points that
do exist in some cases, make it likely that the known examples for
m=2 are the simplest ones that can occur for this or any other m.
I hope this helps.
dave
OwlHoot
On Nov 12, 10:35 pm, "dave.rusin" <dave.ru...@gmail.com> wrote:
>
> [...]
>
> I like this formulation better because I can simply abbreviate
> M = m^7 and avoid some of the large exponents. In other words,
> our goal is to find rational solutions to the systems
>
> a^2 + M B^2 = c^2 + M D^2 (eq.4a)
> a^4 + M B^4 = c^4 + M D^4 (eq.4b)
>
> where our interest is in the cases where M is a seventh power,
> but we can perform the same analysis for any M .
Dunno if it helps, but this system is equivalent to the following
in which m := (M + 1)/(M - 1) :
x^2 + 1, x^2 + m^2 = z^2, t^2 [*]
which seems to confirm what you said about it being elliptic:
Excluding trivial solutions with |a| = |c|, we can divide
each side of :
a^4 - c^4 = M.(D^4 - B^4)
by:
a^2 - c^2 = M.(D^2 - B^2)
to obtain:
a^2 + c^2 = d^2 + b^2
so that:
a, b, c, d = p - q, p.q - 1, p.q + 1, p + q
and replacing these in [4a] gives after some manipulation:
((p^2 - 1) / 2p) . ((q^2 - 1) / 2q) = m (defined as above)
This is equivalent to:
x^2 + 1, y^2 + 1, x.y = z^2, T^2, m
and finally plugging y = m/x into y^2 + 1 = T^2 gives:
x^2 + m^2 = (T.x)^2
I have a proof that [*] is soluble if and only if m.(m - 1)
can be expressed as the sum of two rational squares; but I'll
check this and post it tomorrow.
Cheers
John Ramsden
TPiezas
Thanks D. Rusin for the very thorough analysis! It's amazing that the
problem of expressing ANY rational N as the sum of 8 rational 7th
powers can be reduced to an elliptic curve. Furthermore, that N can
then be so expressed in an infinite number of ways.
Here's how Choudhry did it. Use the form,
F(x): = (x+a)^7+(x-a)^7+(mx+b)^7+(mx-b)^7-(x+c)^7-(x-c)^7-(mx+d)^7-(mx-
d)^7
(though in his paper he set m = 2). Expanding and collecting powers of
x, this resolves to,
F(x): = 42(a^2+m^5b^2-c^2-m^5d^2)x^5 + 70(a^4+m^3b^4-c^4-m^3d^4)x^3 +
14(a^6+mb^6-c^6-md^6)x
To get rid of the x^5 and x^3 terms, find {a,b,c,d,m} such that,
a^2+m^5b^2 = c^2+m^5d^2 (eq.1)
a^4+m^3b^4 = c^4+m^3d^4 (eq.2)
and only the linear term is left. Since x is arbitrary, let x = 14^6
(a^6+mb^6-c^6-md^6)N. Thus,
F(x): = 14^7(a^6+mb^6-c^6-md^6)^7 N
Dividing by the numerical factor, N then is the sum of 8 rational 7th
powers as claimed. (End proof.)
My approach to solving (eq.1) was to use Euler's complete soln to,
a^2+Kb^2 = c^2+Kd^2
as {a,b,c,d} = {pr+Kqs, -ps+qr, pr-Kqs, ps+qr}
Applying these on eq.2, and it reduces to the eqn,
(m^2p^2-q^2)r^2 = (p^2-m^12q^2)s^2
which has rational solns, if
(m^2p^2-q^2)(p^2-m^12q^2) = y^2 (eq.3)
Using Choudhry's 33-digit {a,b,c,d}, it was easy to find the 16-and-17-
digit {p,q} = {5911167604843137, 12317476831120126}. From these, one
can then find even larger {p,q}.
Some remarks:
1. Yes, one can use rational m (I should have specified that in my
original post) and, in fact, it is enough to consider just the
interval 0 < m < 1, since any rational m = u/v gives eq.1 and 2 as,
u^5a^2+v^5b^2 = u^5c^2+v^5d^2
u^3a^4+v^3b^4 = u^3c^4+v^3d^4
where Choudhry's was either {u,v} = {1,2} or {u,v} = {2,1}. The case m
= 0 or 1 should be avoided as it gives only trivial results to eq.3.
2. I was hoping that there were smaller {a,b,c,d,m} since the
algebraic identity that proves Choudhry's theorem had such unwieldy 33-
digit coefficients. Rusin has pointed out that, other than Choudhry's
m = 1/2, the values m = 1/5 and 1/6 probably have non-trivial solns as
well, though even larger. Oh well, I guess any is better than none.
3. A similar approach using another algebraic identity can prove that
any rational N can be expressed as 6 rational 5th powers, though I
don't have access to Choudhry's paper for that yet.
See Form 2, for a family that starts with Ryley's Theorem for 3rd
powers: http://sites.google.com/site/tpiezas/001
P.S. I still have to update that with Rusin's input.
- Titus
OwlHoot
>
> On Nov 12, 6:18 pm, OwlHoot <ravensd...@googlemail.com> wrote:
> >
> >
> > John Ramsden
>
> Thanks D. Rusin for the very thorough analysis!
Despite what James Harris thinks, Dave Rusin and myself
are different people!
Cheers
John Ramsden
alainv...@gmail.com
>
> - Afficher le texte des messages précédents -
Dear titus,
It pleases me to meet ideas I am working with
such as polynomials and parity:
indeed here the function f(x)=
(x+a)^7+(x-a)^7+(mx+b)^7+(mx-b)^7-(x+c)^7-(x-c)^7-(mx+d)^7-(mx-
d)^7
Verifies:
f(x)/2 = Odd((a+x)^7-(c+x)^7+(b+mx)^7-(d+mx)^7)
Since there are neither x^2n terms nor x^7
and it does simplify a lot!
Alain
TPiezas
>
> > Thanks D. Rusin for the very thorough analysis!
>
> Despite what James Harris thinks, Dave Rusin and myself
> are different people!
>
> Cheers
>
> John Ramsden
Actually, I was refering to D. Rusin's post prior to yours, but thank
you also... :-)
- Titus
OwlHoot
>
> [..]
>
> I have a proof that [*] is soluble if and only if m.(m - 1)
> can be expressed as the sum of two rational squares; but I'll
> check this and post it tomorrow.
I checked this, and there was a mistake. So please ignore it.
But the preceding calculations in my post, for what they're
worth, seem OK.
Cheers
John Ramsden