Translate

Thursday, October 30, 2008

Easy proof of problem with ring of algebraic integers

Some simple algebra with a basic polynomial reveals a serious problem with the naive use of the ring of algebraic integers, bringing into question over a hundred years of algebraic number theory.

In an integral domain, consider a simple polynomial

P(x) = 175x2 - 15x + 2.

Multiply it times 7, to get

7*P(x) = 1225x2 - 105x + 14. Cleverly re-group terms:

1225x2 - 105x + 14 = (49x2 - 14x)52 + (7x-1)(7)(5) + 72

and now factor into non-polynomials:

7*(175x2 - 15x + 2) = (5a1(x) + 7)(5a2(x)+ 7)

where you'll note that the a's are functions of x that are roots of

a2 - (7x-1)a + (49x2 - 14x) = 0.

But now consider our polynomial again with a factorization before any
multiplying by 7:

175x2 - 15x + 2 = (5b1(x) + 2)(5b2(x)+ 1)

Now multiply by 7, to get

7*(175x2 - 15x + 2) = (5b1(x) + 2)(5(7*b2(x))+ 7)

and use the substitutions b1(x) = c1(x) + 1, and 7*b2(x) = c2(x), and you have

7*(175x2 - 15x + 2) = (5c1(x) + 7)(5c2(x)+ 7)

and of course if c1(x) = a1(x) and c2(x) = a2(x), I have my original factorization, but in so doing I'm PICKING that 7 multiplies times just one of the factors of 175x2 - 15x + 2, but what if I picked wrong?

For instance, consider again

175x2 - 15x + 2 = (5b1(x) + 2)(5b2(x)+ 1)

and again multiply times 7, but split it up so that each factor is multiplied times sqrt(7):

7*(175x2 - 15x + 2) = (5*sqrt(7)*b1(x) + 2*sqrt(7))(5*sqrt(7)b2(x)+ sqrt(7))

but there's an immediate problem!

If you let x=0, then you have the factorization:

7*(2) = (5*sqrt(7)*b1(0) + 2*sqrt(7))(5*sqrt(7)b2(0)+ sqrt(7))

which contradicts at x= 0 with

7*(175x2 - 15x + 2) = (5a1(x) + 7)(5a2(x)+ 7)

where the a's are functions of x that are roots of

a2 - (7x-1)a + (49x2 - 14x) = 0

unless b_2(0) divides off sqrt(7), or b1(0) divides off sqrt(7), as

7*(2) = (5a1(0) + 7)(5a2(0)+ 7) = (0 + 7)(-5+ 7)

because then the a's are roots of

a2 + a = 0.

Therefore, there is no other way to multiply

175x2 - 15x + 2 = (5b1(x) + 2)(5b2(x)+ 1)

by 7, and get the factorization

7*(175x2 - 15x + 2) = (5a1(x) + 7)(5a2(x)+ 7)

where the a's are functions of x that are roots of

a2 - (7x-1)a + (49x2 - 14x) = 0

as ANY other way other than multiplying (5b2(x)+ 1) by 7, will contradict with

7*(175x2 - 15x + 2) = (5a1(x) + 7)(5a2(x)+ 7)

at x=0, as demonstrated above with sqrt(7).

Therefore, one of the a's must have 7 as a factor for all x, but it is trivial to show that NEITHER of them can have 7 as a factor for any integer x, for which the a's are not rational, in the ring of algebraic integers, so there is proven a problem with that ring.

See also: Wrapper theorem


James Harris

Tuesday, October 07, 2008

Diophantine supermap for binary quadratic equations

IN a previous post I noted the discovery of an infinite series. I decided I should name it and came up with the name: Diophantine supermap for binary quadratic equations

The series starts with

1. x2 + Dy2 = F

2. (x-Dy)2 + D(x+y)2 = F(D+1)

3. ((1-D)x-2Dy)2 + D(2x + (1-D)y)2 = F(D+1)2

4. ((1-3D)x + (D2 - 3D)y)2 + D((3-D)x + (1-3D)y)2 = F(D+1)3

5. ((D2 - 6D + 1)x + (4D2 - 4D)y)2 + D((4-4D)x + (D2 - 6D + 1)y)2 = F(D+1)4

and that goes out to infinity. To get successive terms in the series you use the algebraic result that given:

u2 + Dv2 = C

it must be true that

(u-Dv)2 + D(u+v)2 = C(D+1).

And where whenever the exponent of (D+1) is even, you can have a case where you just have a multiple of x and y, so you can solve for D, which defines possible values for F in terms of x or y.

For instance with

((1-D)x-2Dy)2 + D(2x + (1-D)y)2 = F(D+1)2

I have six possibilities:

(1-D)x-2Dy = +/-(D+1)x or +/-(D+1)y

and

2x + (1-D)y = +/-(D+1)y or +/-(D+1)x

but I will only work through four.

Considering the first gives:

(1-D)x-2Dy = (D+1)x and 2x + (1-D)y = (D+1)y, so

x = -y, from the first and x = Dy, so D=-1. Which gives F=0.

The second gives

(1-D)x-2Dy = -(D+1)x, so x = y,

and 2x + (1-D)y = -(D+1)y, so x = -y, so x=y=0.

The third and fourth also give D=-1.

The next case where D can be set occurs with

((D2 - 6D + 1)x + (4D2 - 4D)y)2 + D((4-4D)x + (D2 - 6D + 1)y)2 = F(D+1)4

which gives again six possibles:

(D2 - 6D + 1)x + (4D2 - 4D)y = +/-(D+1)2x or +/-(D+1)2y

and

(4-4D)x + (D2 - 6D + 1)y = +/-(D+1)2y or +/-(D+1)2x

but I will only show one:

(D2 - 6D + 1)x + (4D2 - 4D)y = (D+1)2x, so 2x = (D - 1)y

and

(4-4D)x + (D2 - 6D + 1)y = (D+1)2y, so (1-D)x = 2Dy,

which solves as D2 + 2D + 1 = 0, so D=-1 again.

D=-1 will always be one of the solutions.

My theory is that other integers will emerge and that you will get all possible integer values for D somewhere in the supermap, and with other values you can get solutions for F, relative to x and y.

I think though mapping the number theoretic structure is best done by computer.


James Harris

Saturday, October 04, 2008

Huge number theoretic structure, major find

One of the more remarkable results from my recent research studying 2 variable quadratic Diophantine equations is a relation from my last post which I used to show a general solution for equations of the form x2 + Dy2 = F.

Here I write that result as, given

x2 + Dy2 = F

it is forced that

z2 + D(x+y)2 = F(D+1)

and you can verify trivially that z=x-Dy, by substituting out F, from the first equation into the second:

z2 + D(x+y)2 = (x2 + Dy2)(D+1)

so, expanding and simplifying:

z2 = (D+1)x2 + D2y2 + Dy2 - Dx2 - 2Dxy - Dy2

gives

z2 = x2 - 2Dxy + D2y2 = (x-Dy)2.

And it may seem like a trivial result, but now you have a chain where the first 3 equations are:

x2 + Dy2 = F

(x-Dy)2 + D(x+y)2 = F(D+1)

and

(x-Dy - D(x+y))2 + D(x-Dy + x+y)2 = F(D+1)2

which is

((1-D)x-2Dy)2 + D(2x + (1-D)y)2 = F(D+1)2.

For each following equation you use the general form that with:

u2 + Dv2 = C

the next equation is given by

(u-Dv)2 + D(u+v)2 = C(D+1)

so the next in the series is

(((1-D)x-2Dy)-D(2x + (1-D)y))2 + D(((1-D)x-2Dy)+(2x + (1-D)y))2 = (F(D+1)2)(D+1).

Which simplifies to

((1-3D)x + (D2 - 3D)y)2 + D((3-D)x + (1-3D)y)2 = F(D+1)3.

And that may not seem remarkable unless you realize that for every solution to the first equation, you have a solution to that last with (D+1)x, and (D+1)y, so what if you go backwards and ask, can

(1-D)x-2Dy = +/-(D+1)x or +/-(D+1)y

and

2x + (1-D)y = +/-(D+1)y or +/-(D+1)x?

But if so, then you have two solutions for x in terms of y, so BOTH must give the same answer or there is a contradiction.

For instance if

(1-D)x-2Dy = (D+1)x, then x=-y, is a solution, and then

2x + (1-D)y = (D+1)y, gives that x = Dy, and only D=-1 can work.

But then I have x2 - y2 = 0 = F, so no solutions.

So, it's now possible to see that all integer solutions to equations of the form x2 + Dy2 = F, are part of this immensely huge number theoretic structure, which is infinitely sized, where depending on the value of D, and the value of F, at various points in the chain you will have situations when you have multiples of x and y.

What's remarkable about that super structure is it allows an explanation for all previously noted behavior and indicates that solutions have to do with linear equations and nothing else.

Intriguingly there is other research noting a lack of a need for non-rational numbers with these equations:

Pell's equation without irrational numbers
Authors: N. J. Wildberger
(Submitted on 16 Jun 2008)

Abstract: We solve Pell's equation in a simple way without continued fractions or irrational numbers, and relate the algorithm to the Stern Brocot tree.

Comments: 9 pages, 3 figures
Subjects: Number Theory (math.NT)
Cite as: arXiv:0806.2490v1 [math.NT]


So there is an infinitely sized and static number theoretic structure which is just an infinite expansion where the first four equations are:

1. x2 + Dy2 = F

2. (x-Dy)2 + D(x+y)2 = F(D+1)

3. ((1-D)x-2Dy)2 + D(2x + (1-D)y)2 = F(D+1)2

4. ((1-3D)x + (D2 - 3D)y)2 + D((3-D)x + (1-3D)y)2 = F(D+1)3

and that goes out to infinity. To get successive terms in the series you use the algebraic result that given:

u2 + Dv2 = C

it must be true that

(u-Dv)2 + D(u+v)2 = C(D+1).

And where whenever the exponent of (D+1) is even, you can have a case where you just have a multiple of x and y, so you can solve for D, which defines possible values for F in terms of x or y.

So the previously seen behavior with solutions to these equations can be explained as finding points in the expansion where you have a multiple with a given D, which will allow your F.


James Harris

Friday, September 26, 2008

Solvability and Diophantine Quadratic Chains

Deciding to take my newly discovered Quadratic Diophantine Theorem for a spin against "Pell's Equation" turned out to be a good idea as besides letting me validate that I had derived the theorem correctly, it also showed me that the result I had didn't simply lead in a BFC--Big Freaking Circle.

Still there is more as it indicates a route to finding a general solution for all 2 variable Diophantine equations using what I now call quadratic chains, which are infinite chains of related Diophantine equations.

To derive the full theory I will use

c1x2 + c2xy + c3y2 = c4z2 + c5zx + c6zy

with z=1, so I have

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))v2 + (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))v + (c6 - c5)2 - 4c4(c2 - c1 - c3) = n2 mod p

for some n, where p is any prime coprime to z for a given solution, when

v = -(x+y)z-1 mod p,

like before but because z=1, I can immediately substitute and generalize to all primes as I did in my previous post with Pell's Equation to get

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))(x+y)2 - (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))(x+y) + (c6 - c5)2 - 4c4(c2 - c1 - c3) = S2

for some integer S, and to simplify doing the next calculations let

A = (c2 - 2c1)2 + 4c1(c2 - c1 - c3)

B = 2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3)

and

C = (c6 - c5)2 - 4c4(c2 - c1 - c3)

so I have

A(x+y)2 - B(x+y) + C = S2

and it's immediately clear that I just have another quadratic Diophantine equation!

Now manipulating to complete the square gives

(A(x+y) - B/2)2 + AC - (B/2)2 = AS2

which is

(2A(x+y) - B)2 + 4AC - B2 = 4AS2

and I have then the new quadratic Diophantine:

(2A(x+y) - B)2 - 4AS2 = B2 - 4AC

and have the stunning result that every quadratic Diophantine in two variables is connected to a quadratic Diophantine of the form:

u2 - Dv2 = F

and I get an existence condition as

(2A(x+y) - B)2 = 4AS2 mod (B2 - 4AC)

so I have that A must be a quadratic residue modulo (B2 - 4AC) if A is coprime to B.

Also I have that if solutions exist and A is negative, then there are only a finite number of solutions.

But further

(2A(x+y) - B)2 - 4AS2 = B2 - 4AC

is another Diophantine equation so I can use it to get yet another equation of the same form.

And if one has rational solutions the next must have solutions, all the way out to infinity if the series goes on forever.

Next I note that if B does not equal 0 using the starting equation, with the next member of the chain you have that

c1=1, c2=0, c5 = 0, and c6 = 0, so I have

A = - 4c3, B=0, C = 4c4(1 + c3)

so I have

(2c3(x+y))2 + c3S2 = 4c3c4(1 + c3)

which is

4c3(x+y)2 + S2 = 4c4(1 + c3)

which is

(S/2)2 + c3(x+y)2 = c4(1 + c3)

so for the next iteration I'd have

4c3(S/2+x+y)2 + T2 = 4c4(1 + c3)2

and I can again re-group and divide off 4 from both sides to have

(T/2)2 + c3(S/2+x+y)2 = c4(1 + c3)2

and see the emergence of a pattern where c3 remains the same throughout.

Intriguingly some prior number theory can now be explained as in general after the initial equation, following equations in the chain look like

u2 + c3v2 = c4(1 + c3)j

where j can be 0 or a natural number

So with c3=-2, you just have

u2 - 2v2 = c4(-1)j

and the remarkable result that you have only two primary forms.

The only simpler case is with c3=-1, when you just get

u2 = v2.

So if A is negative and B2 - 4AC is 1, -1, 2 or -2--where the quadratic residue requirement is of no use--I can simply go down the chain until it applies and may have a solution.

However, there has to be an additional constraint along with the initial quadratic residue constraint, as consider

x2 - 10y2 = 3

as it has no solutions; although 10 mod 3 = 1, so 10 is a quadratic residue modulo 3.

Going back to the general case

u2 + c3v2 = c4(1 + c3)j

I have also that -c3 must be a quadratic residue modulo c4(1+c3), but I also importantly have that

c4(1 + c3)j

must be a quadratic residue modulo c3 as long as c4 does not have any square factors so that dual requirement provides the full existence conditions, and the dual residue requirement can be a means to a solution.

Author's note: Square factors are a big deal which have to be addressed more fully than I first hoped. If x2 + Dy2 = n2 then -D may not be a quadratic residue modulo n2, but dividing n2 from both sides gives

(x/n)2 + D(y/n)2 = 1

which has any solutions to u2 + Dv2 = 1, so x=nu, and y=nv.

In general with u2 + Dv2 = F, if F = Gn2, and -D is not a quadratic residue modulo F, then check modulo G. 10/19/08


For instance, if v2=1 mod c4(1 + c3)j from my little congruence result:

With c3 coprime to c4(1 + c3), if u2 = r1 mod c3 and u2 = r2 mod c4(1 + c3)j, you can find u2 mod c3c4(1 + c3)j with

u2 = r1 + kc3 mod c3c4(1 + c3)j

where k = (r2 - r1)c3-1 mod c4(1 + c3)j

where

r1 = c4(1 + c3)j mod c3 and

r2 = -c3 mod c4(1 + c3)j

and you find k, such that r1 + kc3 is a perfect square, where you increment up from j=0.

Picking v may seem suspect but if there are an infinity of solutions then unless particular residues are excluded for some unknown reason there would be solutions for any residue, but if there is a problem finding solutions with v2=1 mod c4(1 + c3)j, you can search with other values using

r2 = -c3v2 mod c4(1 + c3)j.

So if no residues are excluded that is the general theory for finding solutions.

Not bad for a theorem just recently discovered, and it shows the incredible power of what I call tautological spaces.

They have the power to simplify.


James Harris

Thursday, September 18, 2008

Considering a Diophantine chain

I am curious about the latest result and figured a simple test would allow me to see what Diophantine chains look like, so here goes.

The method works with an equation of the form

c1x2 + c2xy + c3y2 = c4 + c5x + c6y

and to keep things easy for me, I'll use

x2 + 2xy + 3y2 = 4 + 5x + 6y

so I have

c1 = 1, c2 = 2, c3 = 3, c4 = 4, c5 = 5, and c6 = 6

so next I need to calculate

A = (c2 - 2c1)2 + 4c1(c2 - c1 - c3) = -8

B = 2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3) = -40

and

C = (c6 - c5)2 - 4c4(c2 - c1 - c3) = 33

and I have then the new quadratic Diophantine:

(2A(x+y) - B)2 - 4AS2 = B2 - 4AC

which is

(-16(x+y) + 40)2 + 32S2 = 2656

and dividing off 16, I have

(-4(x+y) + 10)2 + 2S2 = 166.

Which has a solution at S=9, giving

-4(x+y) + 10 = +/- 2

and trying the positive first gives x+y = 2, while the negative gives x+y = 3.

Trying the first case, x = 2-y and plugging that into the equation gives

(2-y)2 + 2(2-y)y + 3y2 = 4 + 5(2-y) + 6y

which is

4 - 4y + y2 + 4y - 2y2 + 3y2 = 4 + 10 - 5y + 6y

which is

2y2 -y - 10 = 0,

so y = (1 +/- sqrt(1 + 80))/4 = (1+/-9)/2 = -2 as the other case is a fraction.

Then x=4, so I can try x=4, y=-2, with

x2 + 2xy + 3y2 = 4 + 5x + 6y

and get

16 + 2(4)(-2) + 3(-2)2 = 4 + 5(4) + 6(-2)

which is 12 = 12, so they balance out as they must. I'll leave the second solution to the reader. Notice there are only two.

That was easy to solve but I'm curious about the next value in the chain, so looking again at

(-4(x+y) + 10)2 + 2S2 = 166

I now have c1 = 1, c3=2, and c4 = 166, while all other values are 0, so

A = -8, B = 0, and C = 1992

so the new quadratic Diophantine after some simplifying is:

(-4(-4(x+y)+10 + S))2 + 2T2 = 3984

where the right hand side is definitely increasing which indicates an infinite chain.

Intriguingly 3984 = 16(3)(83), which is intriguing because -2 must be a quadratic residue modulo each prime or 0 modulo that prime, and notice that 3 - 2 = 1, and 83 - 2 = 81.

The existence condition from the quadratic residues is probably the absolute determinant as to whether or not integer solutions exist, I'd surmise.


James Harris

Sunday, September 07, 2008

Quadratic Diophantine Theorem and Pell's Equation

With the Quadratic Diophantine Theorem derived, it makes sense to try it out with a well-known equation in Diophantine theory which is Pell's Equation:

x2 - Dy2 = 1

with D a natural number.

Now again, the Quadratic Diophantine Theorem:

Quadratic Diophantine Theorem:

In the ring of integers, given the quadratic expression

c1x2 + c2xy + c3y2 = c4z2 + c5zx + c6zy

where the c's are constants, for solutions to exist it must be true that

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))v2 + (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))v + (c6 - c5)2 - 4c4(c2 - c1 - c3) = n2 mod p

for some n, where p is any prime coprime to z for a given solution, when

v = -(x+y)z-1 mod p.

So with Pell's Equation I have

c1 = 1, c2=0, c3 = -D, c4 = 1, c5 = 0, c6 = 0, and z=1

which gives

4Dv2 - 4D + 4 = n2 mod p

and v = -(x+y) mod p, so I have

4D(x+y)2 - 4D + 4 = n2 mod p

and since that must be true for all primes p, since z=1, I have in general that the left hand side must be a perfect square so it must be true then that

D(x+y)2 - D + 1 = S2

where S is some integer, and I have in general that

x+y = sqrt((S2 + D - 1)/D).

Example: From a reference I have that with D=2, x=17 and y=12 are solutions.

Working backwards I found that S=41 gives that solution, verifying the result.

Notice also that S2 = 1 mod D. It is of interest to consider the special case of S = 1 mod D or S = -1 mod D, and as that's tedious in what I follows I just use S = +/-1 mod D, where it's an OR, so both cases are not true.

So I can make the substitution S = jD +/- 1, to find

x+y = sqrt(Dj2 +/- 2j + 1)

which is

x+y = sqrt((D-1)j2 + (j +/- 1)2)

and I have the existence of solutions related to another Diophantine relation of the form

(D-1)u2 + v2 = w2

with the condition that u = j and v = j+/-1.

For instance with D=2, I have that I need solutions to

u2 + v2 = w2

with u=j, and v=j+/-1, and j=20 works as 202 + 212 = 292, and gives x+y = 29, and again x=17, y=12 is a known solution to x2 - 2y2 = 1.

So then x2 - 2y2 = 1 is related to certain Pythagorean triples, when D is prime.

Also notice that from

x+y = sqrt((S2 + D - 1)/D)

I have

S2 - D(x+y)2 = -D + 1

which means a second Diophantine equation connected to the first!

With D=2, I get then that x2 - 2y2 = 1, is connected to

S2 - 2(x+y)2 = -1

so for every solution of the first there is a solution of the second.

So there is an immediate result with the classical Pell's Equation, with little effort at all using the theorem, which can be used against any Diophantine quadratic in 2 variables, almost as easily, and also give results in 3 variables, though not quite as generally.


James Harris

Saturday, September 06, 2008

Quadratic Diophantine Result

Quadratic Diophantine Theorem:

In the ring of integers, given the quadratic expression

c1x2 + c2xy + c3y2 = c4z2 + c5zx + c6zy

where the c's are constants, for solutions to exist it must be true that

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))v2 + (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))v + (c6 - c5)2 - 4c4(c2 - c1 - c3) = n2 mod p

for some n, where p is any prime coprime to z for a given solution, when

v = -(x+y)z-1 mod p.

For example with x2 + y2 = z2, I have

c1 = 1, c2 = 0, c3 = 1, c4 = 1, c5 = 0, and c6 = 0

which gives

-4v2 + 8

is a quadratic residue modulo p, for every prime coprime to z, when v = -(x+y)z-1 mod p.

Making the substitution gives

-4(-(x+y)z-1)2 + 8 = n2 mod p

for some n, which is

-4(x+y)2 + 8z2 = n2z2 mod p

and since x2 + y2 = z2, I can substitute out z on the left side, to get

4(x-y)2 = n2z2 mod p.

Proof of theorem:

The theorem is proven using what I call a tautological space, where

x+y+vz = 0(mod x+y+vz)

as then I have x+y = -vz (mod x+y+vz), and can square both sides to get

x2 + 2xy + y2 = v2z2 (mod x+y+vz)

and multiply both sides by c1 and subtract from

c1x2 + c2xy + c3y2 = c4z2 + c5zx + c6zy

and use x = -y-vz (mod x+y+v) to substitute out x, and simplify to get

(c4 - c5v - c1v2)z2 + ((c2 -2c1)v - c5 + c6)zy + (c2 - c1 - c3)y2 = 0 (mod x+y+vz)

and then it's just a matter of completing the square, and collecting terms multiplied times y2 on the right, as you have an equation of the form

(Az + By)2 = Cy2 (mod x+y+vz)

and noting then that C must be a quadratic residue modulo p, where p is any prime such that

x+y+vz = 0 mod p

where coprimeness with z is required by the solution v = -(x+y)z-1 mod p.

Proof complete.

The Quadratic Diophantine Theorem allows determination of whether or not integer solutions are prohibited from existence for the given specified quadratic expression for various constants, because of the requirement that any prime coprime to z for a solution must have the given quadratic residue.

The theorem can be used prime by prime, or a more general result can be obtained by substituting out for v, in

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))v2 + (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))v + (c6 - c5)2 - 4c4(c2 - c1 - c3) = n2 mod p

to get

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))(x+y)2 + (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))(x+y)z + [(c6 - c5)2 - 4c4(c2 - c1 - c3)]z2 = n2z2 mod p

as then the left hand side must be a quadratic residue for any prime p, which requires then that

((c2 - 2c1)2 + 4c1(c2 - c1 - c3))(x+y)2 + (2(c2 - 2c1)(c6 - c5) + 4c5(c2 - c1 - c3))(x+y)z + [(c6 - c5)2 - 4c4(c2 - c1 - c3)]z2 = m2

where m is some integer.

Then you can substitute out for z2 as with my example before, and either have a perfect square as with that example, or solve for cases when integer solutions are available with something of the general form

A(x+y) = +/-Bz

for specific cases of m that will give integers.

Note: You have a requirement on a general quadratic diophantine solution in two variables by letting x=1.

The reach of the theorem is remarkable considering how simply it is derived and shows with yet another mathematical result the power of what I call tautological spaces.


James Harris

Friday, July 25, 2008

Optimal path algorithm?

Given two travelers T1 and T2 and m nodes N, where m is a natural number, each traveler can be at a particular node, and each node has a distance from every other node in the space. However, it is not assumed that each node is reachable from every other node, but that at least one path exists between each node and one other node.

If no distance information is given then the travelers are assumed to be in a m-1 dimensional space with each node the same unit distance from every other node.

There is also a weight associated with the path from each node to another, which is given in general as cost. But cost can be any weight between nodes including distance.

For instance, if it takes $200 U.S. to go from N1 to N2, then that cost is what's used for a traveler at N1 considering going to N2.

Assume T1 is at N1 and T2 is at Nm. For the first iteration T1 considers moving to N2 which is reachable, and then T2 considers moving from each reachable node in turn EXCEPT N1 or N2 as it excludes the node that T1 is already at, and also excludes the one being considered.

For each potential move T2 calculates the cost from that node to Nm, as T2 is moving backwards in time, which I'll call cost2, and then it takes, if the node is reachable, the cost to T1 at N2--not at N1, as it is checking where T1 will be--and it multiplies the cost for that move times the cost of the move T1 is considering, which I'll call cost1, times the cost to T1, and stores that data.

After T2 has gone through every possible move, it simply takes the one that is smallest cost1*cost2*cost, and stores that info. If there are more weights, like time, it'd multiply time1*time2*time*cost1*cost2*cost, and so forth with as many multiplications as there are weights.

Now T1 considers moving to another reachable node, like N3 if there is a path from its current node to that one, and T2 does the same calculation again, and stores the smallest cost1*cost2*cost.

This process continues until all possible moves by T1 are done, and now T1 has a set of cost1*cost2*cost values from the calculations by T2, and selects the smallest one. If there is more than one path with the least value then it doesn't matter which is taken, so the first can be taken.

Now both T1 and T2 actually move to their respective nodes given by that smallest value.

Now the paths from nodes N1 and Nm to the chosen nodes in the direction moved is removed from consideration. However, the reverse path for each is still available.

And you have a complete iteration.

Note that you have a maximum (m-2)2 checks, if the travelers start at different nodes and every node is reachable from every other node, but you still have nearly the same number after the first iteration as now only paths are being removed and not nodes, but the algorithm is still polynomial time.

T1 and T2 continue until there are no more paths available or there is only one node available.

Note that in the latter case then EITHER can move to complete, so you can arbitrarily say that T1 moves forward in that case.

And that is how every node is reached, even if some nodes are not reachable from certain other nodes.

To have a complete circle back to a starting point, you have both T1 and T2 start at the same node, like N1.

The cost for a round trip path with a starting point from each node in turn is stored with the optimum path being the one with the minimum total cost.

Notice with this algorithm you may go to a node multiple times, and a well-visited node is called a hub.

If the optimum path from each node is the same then the graph is said to be perfectly correlated, and corresponds with a case where the costs correlate very well with the distance between nodes.

If only one path is optimal then the graph is said to be dis-correlated, and that corresponds to a case where costs have little or no relation to distances between nodes.

The percentage correlation can be found then by dividing the number of starting nodes that give an optimal path by the total number of nodes, where a graph for which there is a high percentage correlation is said to be a rational graph, where it seems to me that a 67% correlation or higher would qualify.

That could have real world relevance for determining, say, whether or not prices along paths correlate well between measures along the path, or it might reveal problem spots, where, for instance, there is a high cost associated with an otherwise desirable path, which, for instance, might help a city plan places for new roads.


James Harris

Monday, May 19, 2008

Spherical packing problem

I concluded in the mid-nineties that I had a proof of the spherical packing problem with a relatively short time of pondering, and held that view.

So I concluded within about a year or two of working on spherical packing that I'd solved the problem.

I did write a paper and presented it to the Proceedings of the AMS, and the editor who reviewed it while not claiming an error that I can remember did reject it, of course, as that was back I think in 1996 (or 1995), but I think part of his objecting to the paper was the idea that the answer was too simple. He couldn't accept if I remember correctly that a couple of pages and some relatively simple calculations solved the problem, so it was rejected as not complicated enough.

Which brings up the question of what was the argument, except I've since lost the paper--I'm not good with keeping up with old research as I tend to just lose the paperwork over time which is why modern technology is good as now I just keep things on my blogs or much of what is on it would be lost as well--and haven't been motivated to go into detail explaining it much since because it was so simple, so it's just not exciting enough.

But now as I think back it's worth putting out what I think was the approach I used, and you can judge for yourself, if you think it is a route to the solution to the problem.

Ok, so I would do a lot of drawing of 10 of the 13 spheres that closely pack in a hexagonal close-packing structure, which I knew was the closest packing.

I only drew 10 because the arrangement is symmetric to a plane that slices through so that you see a circular close packing of 6 circles surrounding one central circle.

I then connected the dots of the centers and drew lines on the top half connecting all the top half spheres together and then I noted that I now had an inner structure made up of 4 triangular pyramids and three rectangular pyramids.

I then calculated the density of each type of pyramid, and noted that the triangular pyramid has the maximum possible density as it is the closest packing possible of 4 spheres, while the rectangular pyramid has a much lesser density.

And then I'd guess that I proved that any deformation of the triangular pyramid, as that would decrease its density, could not be made up for by the deformation of the rectangular pyramids, so that any deformation would lead to a smaller density, and that was it.

(Oh, now I think I remember what I did. It was a linear argument as I think I had one line that was like 0.77x + 0.72y equals something or other where x=4 and y=3, for the hexagonal close, and then noted that the line would be something else for the deformation and did some kind of slope thing to prove. Really damn simple I think it was. Like I said, the reviewer objected because it was too simple. Nothing else.)

Even as a thought experiment you can note that if you smoothly deform the rectangular pyramids in order to increase their density, as you move the spheres in tighter you pull them out further with the triangular pyramids decreasing their density, until at the limit you have turned your rectangular pyramid into a triangular pyramid, and deformed out your triangular pyramid into a rectangular one, while on the top you have a triangular pyramid at all times but the lengths along its base deform outward until they pull back in to the close packed structure.

So as you imagine going from hexagonal close-packing and move the spheres, if you had a density increase then you'd get a density curve that has to increase at some point and then drop back down, as at the end of the deformation you just have what you started with--4 triangular pyramids and 3 rectangular pyramids in a hexagonal close-packing.

Then you can simply prove that deformation in any direction leads to a drop in density, or more rigorously you can look for maxima or minima along any gradient, and note that you only get minima and no maxima showing the density decreases steadily with deformation until it increases back to the hexagonal close-packing density.

(Yeah, but I think that as I mentioned above, as I've come back to edit this post after puzzling over what my past self did, I did something incredibly simple using lines and slope!!! Wow. So it was like incredibly simple. But still kind of boring as I moved on and pondered Fermat's Last Theorem for years later.)

Not sure what I did in that paper back then but I concluded the solution was easy enough that I didn't worry much about it afterwards, and moved on to concentrating on Fermat's Last Theorem exclusively.

(Ok, so no need to be coy: if d is the packing density then approximately you have

(0.77x + 0.72y)/7 = d

where x = 4 and y = 3, for hexagonal close packing, but with any smooth deformation you get another linear equation, with alternate densities:

(4d1 + 3d2)/7 = d*

but d1 is less than 0.77 for one set while d2 is slightly more than 0.72 for the other but the 4 versus 3 makes the difference. So if you look at the slope of the line for any intervening values it cannot cross the previous line, so then that solves the spherical packing problem. Wow. I figured that out over ten years ago, if that's how I did it, and it seems familiar so I think it is.)

Oh, so how does that apply to packings in general if I'm just using 13 spheres?

Well, I noted that if you expand out to more spheres you can see them as being built up by these units that have 8 triangular pyramids and 6 rectangular pyramids--remember I was looking at half the structure before--which could be assembled to build a larger structure of arbitrary size, and since each individual element was as closely packed as possible and locked in perfectly with the larger structure, the hexagonal close-packing provided the maximum packing.

The entire proof if I remember correctly flowed easily from noting that 4 spheres could most closely pack only one way, which was in a triangular pyramid.

There really isn't any way to objectively attack the approach, but it's also more of a straight-forward no-nonsense way of solving the problem which is how I do things, and in my opinion, modern mathematicians, like people in computer tech fields, don't like simple and straightforward for the "hard" problems, so my solution is not something that they'd care to know, even though there is no way mathematically to invalidate the approach.


James Harris

Sunday, February 03, 2008

Little congruence result

With non-zero coprime integers n1 and n2, if f1 = r1 mod n1 and f1 = r2 mod n2, you can find f1 mod n1n2 with

f1 = r1 + jn1 mod n1n2

where j = (r2 - r1)n1-1 mod n2.

I like this result better than the Chinese Remainder theorem, as you can just go by two's and I re-discovered it.

Looks to be equivalent to what the Wikipedia calls the "method of successive substitution".


James Harris