The new strong (extended) factoring method using the 4-square representation of an integer.

[mahbel]

Originally Posted by science_man_88

you can break down almost any partition that way though: partitions of 9:

all the red are partitions of another partition. some of these are also duplicates of earlier ones 3,4,2 and 4,3,2 and 2,3,4 for example ( there's actually 6 possible ways to rearrange these but that's also why you can cut the work back searching for the square sums because there are 16 with sign changes, each having 24 orderings.

It simply means that we only need to find the first 4-sq rep, then expand its squares into sum of 4 squares and then use these expansions to form combinations of square and non-squares as done before to find the factor.

[science_man_88]

Originally Posted by mahbel

It simply means that we only need to find the first 4-sq rep, then expand its squares into sum of 4 squares and then use these expansions to form combinations of square and non-squares as done before to find the factor.

It also means, that looking for the partitions where all the number's are the same, is enough to get a factor though.

[science_man_88]

Originally Posted by science_man_88

It also means, that looking for the partitions where all the number's are the same, is enough to get a factor though.

okay not quite turns out you also need to check it's not 1 or N for a non trivial factor.

[Dr Sardonicus]

Originally Posted by mahbel

It turned out that one 4-sq representation can be transformed into another simply by expanding the squares in the first one and re-arranging them to create new 4-sq representations. It can be shown that for N=7*13=91, the first 4-sq rep (5,5,5,4) can be transformed into any other representation.

And in fact, if one used the expanded squares of a given representation, one can find more factors. Take the example of the first 4-sq rep (5,5,5,4).
5^2=4^2+2^2+2^2+1^2
5^2=4^2+2^2+2^2+1^2
5^2=4^2+2^2+2^2+1^2
4^2=2^2+2^2+2^2+2^2....

So, how does this transform one 4-square representation into another? And where does this process stop, short of all the squares being equal to 0 or 1?

Instead of looking at summands n^2, why not use summands 2^n instead? I absolutely guarantee, if N is odd and composite, and you take

1, 2, 4, ... 2^r, with 2^r < sqrt(N) < 2^(r+1), so r < log(N)/(2*log(2)),

then at least one of the sums of these powers of 2 will be equal to a factor of N! I can even spot you that one of the summands must be equal to 1!

[CRGreathouse]

Originally Posted by mahbel

It turned out that one 4-sq representation can be transformed into another simply by expanding the squares in the first one and re-arranging them to create new 4-sq representations. It can be shown that for N=7*13=91, the first 4-sq rep (5,5,5,4) can be transformed into any other representation.

Originally Posted by mahbel

It simply means that we only need to find the first 4-sq rep, then expand its squares into sum of 4 squares and then use these expansions to form combinations of square and non-squares as done before to find the factor.

I'm concerned we're getting tricked by using small numbers again. Here's a random semiprime and the first 4-square partition I found: 815181927142781578628738664212206467553690877685194559413249 = 902874258766292206129956425802^2 + 255400237710160^2 + 19610779^2 + 5938098^2. Could you expand its sum of four squares into a few others to show the process?

[mahbel]

Originally Posted by CRGreathouse

I'm concerned we're getting tricked by using small numbers again. Here's a random semiprime and the first 4-square partition I found: 815181927142781578628738664212206467553690877685194559413249 = 902874258766292206129956425802^2 + 255400237710160^2 + 19610779^2 + 5938098^2. Could you expand its sum of four squares into a few others to show the process?

I cannot do the calculations by hand.
Because we are dealing with a big number, the squares (a,b,c,d) themselves will have many 4-sq reps. The idea of my comment is to limit the search for factors to 4 sub expansions, that is the 1st 4-sq rep of a,b,c,d.

[science_man_88]

Originally Posted by mahbel

I cannot do the calculations by hand.
Because we are dealing with a big number, the squares (a,b,c,d) themselves will have many 4-sq reps. The idea of my comment is to limit the search for factors to 4 sub expansions, that is the 1st 4-sq rep of a,b,c,d.

can't divide those big number's by 2 ? after all (2a)^2= 4(a^2) edit :to prove what you said, most of what you have to do is prove that, any of the squares, once expanded form a lower pair of a Pythagorean triple.

[mahbel]

Originally Posted by science_man_88

to prove what you said, most of what you have to do is prove that, any of the squares, once expanded form a lower pair of a Pythagorean triple.

not necessarily a lower pair of Pythagorean triple. 8^2=4^2+4^2+4^2+4^2 but 4^2=2^2+2^2+2^2+2^2. We may get some Pythagorean triplets but not as a general rule.

[science_man_88]

Originally Posted by mahbel

not necessarily a lower pair of Pythagorean triple. 8^2=4^2+4^2+4^2+4^2 but 4^2=2^2+2^2+2^2+2^2. We may get some Pythagorean triplets but not as a general rule.

then breaking them down doesn't help in general ...

[mahbel]

Originally Posted by science_man_88

then breaking them down doesn't help in general ...

It does. Expanding the squares of a given 4-sq rep helps as a general rule. Look at the simple example of N=7*13=91, the first 4-sq rep is (5,5,5,4). There is not a single combination of squares that gives a factor. But there is at least one combination of non-square that gives a factor, 5+5+4=14=2*7. There is also a mixed combination that gives a factor, 5^2 + 5 + 5 +4 = 39 =3*13.

Now look at what happens when we expand the squares (5,5,5,4).

5^2=(4,2,2,1)
4^2=(2,2,2,2)

combining these squares, it is easy to see that:

4^2 + 2^2 + 1^2 = 21 = 3*7
2^2 + 2^2 + 2^2 + 1^2 = 13
2^2 + 1^2 + 1^2 + 1^2 = 7
4^2 + 2^2 + 2^2 + 2^2 = 28 = 4*7
4^2 + 4^2 + 1^2 + 1^2 + 1^2 = 35 = 5*7
....
What we don't know is how many levels of expansions are needed. If we consider the original 4-sq rep at the top of a pyramid, the successive expansions of squares of that original 4-sq rep will take us all the way down to a^2=1^2+1^2+...+1^2 and the same for b,c,d.

My guess is that it is very hard to prove that the number of expansions of individual squares of the original 4-sq rep is much smaller than the one required if one has to go all the way down to a^2=1^2+1^2+...+1^2. The math is not simple and I don't think the answer is the same for all numbers.

[science_man_88]

Originally Posted by mahbel

It does. Expanding the squares of a given 4-sq rep helps as a general rule. Look at the simple example of N=7*13=91, the first 4-sq rep is (5,5,5,4). There is not a single combination of squares that gives a factor. But there is at least one combination of non-square that gives a factor, 5+5+4=14=2*7. There is also a mixed combination that gives a factor, 5^2 + 5 + 5 +4 = 39 =3*13.

Now look at what happens when we expand the squares (5,5,5,4).

5^2=(4,2,2,1)
4^2=(2,2,2,2)

combining these squares, it is easy to see that:

4^2 + 2^2 + 1^2 = 21 = 3*7
2^2 + 2^2 + 2^2 + 1^2 = 13
2^2 + 1^2 + 1^2 + 1^2 = 7
4^2 + 2^2 + 2^2 + 2^2 = 28 = 4*7
4^2 + 4^2 + 1^2 + 1^2 + 1^2 = 35 = 5*7
....
What we don't know is how many levels of expansions are needed. If we consider the original 4-sq rep at the top of a pyramid, the successive expansions of squares of that original 4-sq rep will take us all the way down to a^2=1^2+1^2+...+1^2 and the same for b,c,d.

My guess is that it is very hard to prove that the number of expansions of individual squares of the original 4-sq rep is much smaller than the one required if one has to go all the way down to a^2=1^2+1^2+...+1^2. The math is not simple and I don't think the answer is the same for all numbers.

you said 4 square representations to another not a mixed representation. to get back squares you need a sum of squares that sum to a square the simplest form is a pythagorean triple.

so 1^2+3^2+4^2+5^2 =1^2+5^2+5^2+0^2 because 3^2+4^2=5^2.