Re: What puzzles me, discovery ignored

On Sep 8, 5:49 pm, Enrico <ungerne...@xxxxxxx> wrote:
On Sep 7, 10:12 pm, Enrico <ungerne...@xxxxxxx> wrote:





On Sep 7, 11:58 am, Mark Murray <w.h.o...@xxxxxxxxxxx> wrote:

Enrico wrote:
I've got a couple of Excel speadsheets that will let you plug in
numbers and see what happens. You will need to have the Greatest
Common Divisor function GCD(X, Y) working - can't remember if GCD
came with the original Excel package or with one of those mysterious
"Add-Ins"

Yikes! :-) I don't do Excel.

It would be safer to receive a text - only explanation. I can pull
comments off the spreadsheets and organize them a bit to the point
where you should be able to try your own calculations. This will
take a few days - I'll have to remove variable name conflicts between
my stuff and JSH's

I can email the text-only stuff or post it here.
Let me know which one you want.

Text is vastly preferable. Please do both, if that is OK?

If your reply-to: is set, may I email you my real email address?

My intention is to code the work as (probably) C++, and then give
it a hammering (pun intended). C++ means I can then trivially modify
the code if I need to start using bignums by using operator
overloading.

There is another constraint that can be used to
limit the choices for x and y.
Ah, useful!

The constraint is: (2*x + 1) divides (2*y +1)^2 -1

Does James mention that anywhere?

Also - I'm more interested in the Diophantine solutions than in
factoring. Does James actually have a general solution, or is
your decryption of his work focussing on factorisation?

M
--
Mark Murray

===================================================================

If your reply-to: is set, may I email you my real email address?

I got one from James, so it should be working.

The constraint is: (2*x + 1) divides (2*y +1)^2 -1

Does James mention that anywhere?

No. James' factorization method relates to forms like:

    P^2 - D*Q^2 = R^2

where D is an odd number to be factored.
My method involved the dot (scalar) product of a pair of vectors,
each of which contain 3 terms, any one of which can be calculated
from the other two. I found a way to convert them to the Pell - like
form above, but its not too obvious.

Also - I'm more interested in the Diophantine solutions than in
factoring. Does James actually have a general solution, or is
your decryption of his work focussing on factorisation?

I've been assuming that it's general because I can start with a
factorization, generate two equations of the form:

a x2 + b xy + c y2 + dx + ey + f = 0

and see that James' method correctly solves each for (x+y)

There are probably equations that I cannot generate from a
factorization, but have solutions. I haven't looked into this.
James mentions a solution existence check, so I have some reason
to think his solution is general. (I have not proved this!)

I'll write up a procedure to let you generate the pairs of
diophantine equations and see James' solution method work.
I expect to have it ready to post sometime tomorrow.

                              Enrico- Hide quoted text -

- Show quoted text -

============================================================

Mark - Check this with numeric values before you start writing
long C programs. Its mostly cut and paste from a functioning
spead***, but there's always the chance of mistyping during
editing or commenting.

Thanks Enrico for the detailed reply to the poster "Mark Murray".

I didn't see it before as I'm operating primarily from the sci.physics
newsgroup but got curious to come to sci.math and take a look.

Example: Factorization, 2 variable diophantine equations, Pell
equations

A=7
B=18
C=23
X=15
Y=19
Z=12

R=2*A*C - B^2 = -2
S = A*X + B*Y + C*Z = 723
D = S^2 + R = 723^2 - 2 = 522727 = 463 * 1129

Two Pell - like equations can be written:

r(v)^2 -D*s(v)^2 = t(v)^2
(S*X + C)^2 - D*X^2 = (Y*C + X*B)^2
10868^2 - 522727 * 15^2 = 707^2
GCD(ABS(r(v)+t(v)),ABS(D)) = 463
GCD(ABS(r(v)-t(v)),ABS(D)) = 1129
Take the GDC of these two and divide out
any common factor to get the factors of D
463 * 1129 = 522727 = D

r(v)^2 -D*s(v)^2 = t(v)^2
(S*Z + A)^2 - D*Z^2 = (Y*A + Z*B)^2
8683^2 - 522727 * 12^2 = 349^2
GCD(ABS(r(v)-t(v)),ABS(D)) = 463
GCD(ABS(r(v)+t(v)),ABS(D)) = 1129
Take the GDC of these two and divide out
any common factor to get the factors of D
463 * 1129 = 522727 = D

James goes on about rational solutions to the Pell Equation.
Rational solutions for the Pell Equation with D can be
gotten by dividing out t(v)^2 from r(v)^2 - D*s(v)^2 = t(v)^2

James uses Pell - like equations written as:
r(v)^2 - D*s(v)^2 = t(v)^2
I have attempted to duplicate this below:

The following two transform pairs on (A, B, C) and (X, Y, Z)
use quadratic functions of v and
preserve the values of D, S, 2*X*Z - Y^2, and 2*A*C - B^2
while changing the values in the Pell Equation

Using the example above,
U(0) = (X, Y, Z) = (15,19,12)
T(0) = (A, B, C) = (7,18,23)

let v = -1 (Domain is integers)

First pair:

Z <= Z
Y <= -2*Z*v + Y
X <= 2*Z*v^2 - 2*Y*v + X

C <= 2*A*v^2 + 2*B*v + C
B <= 2*A*v + B
A <= A

U(-1) = (77,43,12)
T(-1) = (7, 4 1)

Second pair:

Z <= 2*X*v^2 - 2*Y*v + Z
Y <= -2*X*v + Y
X <= X

C <= C
B <= 2*C*v + B
A <= 2*C*v^2 + 2*B*v + A

U(-1) = (15, 49, 80)
T(-1) = (17, -28, 23)

Notice that the dot product of U(v) and T(v) remains unchanged
You can take your starting values of U and T and apply one of the
transforms with any integer value of v, then apply the other transform
to the result with a new value of v, then go back to the first
transform
with yet another value of v, etc - alternating transforms and using
any
value of v each time and stopping at the end of any transform.

The factorizations will remain unchanged,
but the Pell - like equations will change.

Part 2 - Using (X, Y, Z) and (A, B, C) to generate equations
of the form c1*x^2 + c2*x*y+ c3*y^2 + c4 + c5*x + c6*y = 0
and showing James' method giving correct solutions as (x + y)

Note: X ,Y, Z, A, B, C are different variables than x, y, z, a, b, c

Problem - Factor D^2 + R = 723 ^ 2 - 2
Surrogate is (A + B) ^ 2 - (B ^ 2 - 2 * A * C) = 25 ^ 2 - 2

(Surrogate is small, has the same form as D^2 + R, namely R =
-2)

You can use the transform pairs to pump it up if you want.
The factors of the surrogate are A and 2*(B + C) + A

A=7
B=18
C=23

X, Y, Z values are unknown and are to be found such that
S = A*X + B*Y + C*Z = 723

X is odd
Y is odd
Z is a multiple of 4

Y ^ 2 - 2 * X * Z = 1

Define new variables x, y, z
x = (X - 1) / 2
y = (Y - 1) /2
z = Z / 4

Use A, B, C, and S to set up a diophantine equation to find x and y

4*A*x^2+4*B*x*y+2*C*y^2+2*(2*A+B-S)*x+2*(B+C)*y+A+B-S = 0
28*x^2 + 72*x*y +46*y^2 - 1382*x + 82*y - 698 = 0
Dividing out the 2's gives

14*x^2 + 36*x*y + 23*y^2 -691*x + 41*y - 349 = 0

c1 = 14
c2 = 36
c3 = 23
c4 = -349
c5 = -691
c6 = 41

James' solution method uses the variable names A, B, C, and S,
so I will assign new values for them:

A = (c2 - 2c1)^2 + 4c1(c2 - c1 - c3)
B = 2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3)
C = (c6 - c5)^2 + 4c4(c2 - c1 - c3).

A(x+y)^2 + B(x+y) -S^2 + C = 0

rearrage terms:

A(x+y)^2 + B(x+y) + C = S^2

A = 8
B = 14476
C = 537220

x+y = 16 gives S = 878

by trial and error, find that x = 7 and y = 9 give

X = 2 * x + 1 = 15
Y = 2 * y + 1 = 19
Z = (Y^2 -1) / 2*X = 12

Using the original values for A, B, C = 7, 18, 23 redefine
S:
S = A*X + B*Y + C*Z = 723
and the factorization is done as in the example at the beginning
using

(S*X + C)^2 - D*X^2 = (Y*C + X*B)^2
or
(S*Z + A)^2 - D*Z^2 = (Y*A + Z*B)^2

A second diophantine equation can be set up to find y and z
using the original values:
A=7
B=18
C=23
S = 723

32*C*z^2+16*B*z*y+4*A*y^2+8*(B-S)*z+4*A*y+0 = 0
Divide out the common factor 4:
8*C*z^2+4*B*z*y+A*y^2+2*(B-S)*z+A*y = 0

184*z^2 + 72*z*y + 7*y^2 - 1410*z +7*y = 0

c1 = 184
c2 = 72
c3 = 7
c4 = 0
c5 = -1410
c6 = 7

James' solution method uses the variable names A, B, C, and S,
so I will assign new values for them:

A = (c2 - 2c1)^2 + 4c1(c2 - c1 - c3)
B = 2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3)
C = (c6 - c5)^2 + 4c4(c2 - c1 - c3).

A(z+y)^2 + B(z+y) -S^2 + C = 0

rearrage terms:

A(z+y)^2 + B(z+y) + C = S^2

A = 32
B = -167704
C = 2007889

z + y = 12 gives S = 7

by trial and error, find that z = 3 and y = 9 give

Z = 4 * z = 12
Y = 2 * y + 1 = 19
X = (Y^2 - 1) / (2*Z) = 15

Which are the same values of X, Y, and Z found the first time.

One important thing I have not checked is the question of
have many solutions exist for each these diophantine equations.

                        Enrico

I didn't read through the post checking in detail for various reasons
but I think it pertinent that no sensible reply was given to Enrico,
and that was days ago, while "Mark Murray" and "MichaelW" have been
bugging me in replies on the sci.physics newsgroup.

Makes you wonder if they just played the gambit in the hopes that I
wouldn't see Enrico's posts here?

Annoying.


James Harris
.

Loading