Register to reply 
A Factorization Algorithm 
Share this thread: 
#37
Jul606, 10:31 PM

P: 92

(10a) [tex]rrs_{k+1}=\{x \Pi_{i=1}^k p_i+rrs_k x = 1...p_{k+1}1\}  \{p_{k+1}rrs_k\}[/tex]
Write this set out in ordered pairs that sum to {itex}\Pi_{i=1}^k p_i{/itex} {tex} (1, 5)_6 \arrow 1+5=6{/tex} six is an example of a number which is the sum of two of it's own divisors 3+3 = 6, this never happens again in the sequence we are looking at since half of any element is greater than the largest prime factor. {tex} (6*0+1, 6*4+5)_30 = (1,29) (6*1+1,6*3+5)=(7,23) (6*1+5,6*3+1)=(11,19) (6*2+1, 6*2+5)=(13,17){/tex} Here we have three sums of odd primes adding to 30, but notice that the sum of multiples of six is four, that is one less than the largest prime in 30 this pattern holds as we climb the ladder. {tex} (30*0+1, 30*6+29)_210 = (1,209) (30*0+11,30*6+19)=(7,23){/tex} etc. So for any element {itex}\Pi_{i=1}^k p_i{/itex} of the sequence p# at least one goldbach ordered pair must exist and it will have the form {tex}(x\Pi_{i=1}^{k1} p_i+r,(p_kx1)\Pi_{i=1}^{k1} p_i + (\Pi_{i=1}^{k1}r)){/tex} So that translates into a system of equations like this {tex}(xP+r,(px1)P+(Pr)){/tex} Where P is the product of primes up to k1, p is the kth prime, r is a reduced residue of P and x is grater thatn or equal to zero and less than or equal to p1. The binding equation is {tex}xP+r+(px1)P+(Pr)=Pp{/tex} Whic is true. However every goldbach pair for this sequence of which P is an element is then given by (10c) {tex}(Px+r,P(px)r)){/tex} where (11c) {tex}x \in {0,....,p1} \and r\ in rrs_P {tex} Where in that array do these ordered prime pairs appear? Well if they lie between p and p^2 the sieve has already told us they are prime because P contains all prime factors less than their square root. So any pairs (10c) that can be formed where both elements are between p and p^2 must be Goldbach ordered pairs. This result can only be an guarantee of existence until P>2p^2. At that point no pairs both between p and p^2 can sum to P. This happens for 2*3*5*7=210. However the elements of the rrs between between 11 and 49 left inclusive must be prime, those between 49 and 121 must either be prime or divisible by 11, those between 121 and 169 prime or divisible by 11 or 13, those between 169 and 219, prime or divisible by 11, 13 or 17... So that covers the set if I form the pairs and test each one equivalently, but notice I can write these ordered pairs down. rrs elements divisible by eleven are {11, 11*11, 11*13, 11*17,11*19} Those divisible by 13 are {13, 13*13} that covers that. And it gives us a clue. If I can calculate the size of the set of composites in the rrs mod P lying between p^2 and P, I then know how many primes lie on that interval and are wihtin the rrs mod Pp. {Note: it is important to note that the only composites in rrs mod Pp come form multiplying elements of rrs mod P} Now synthesize all this into a table that sets up the possible goldbach ordered pairs. If you crank out a few of these and make sure you have all the indexes correct, you see that for small prime products it is not amazing at all that goldbach should be true because most of the element of the rrs mod Pp are going to be prime. However as we go big it might be possible that the rrs mod P contains no primes at all. But then we are saved by a theorem which says that there is always at least one prime between p and 2p. Well the interval defined by P and Pp is sure to contain at least one new prime. This is very loose and needs to be made tighter with a proof. An interesting question here is does the density of primes in the rrs actually get larger approaching one, does it go to zero in the limit or does it settle down to some fixed number. If it settles down to a fixed number or progresses to one Goldbach can probably be proved on this sequence, if it moves towards zero it would be quite striking that Goldbach would hold for very large P. I will come back and flesh this out later also. 


#38
Jul706, 01:49 AM

Sci Advisor
HW Helper
P: 1,994

However: And no, this wouldn't mean I'd be at all suprised if Goldbach turns out to be true for the sequence p# (or actually in general). Even a set with asymptotic density of zero can be "numerous" in some ways (like the sum of the recipricols of the primes diverging) ps. use [] instead of {} for your latex tags 


#39
Jul906, 10:41 PM

P: 92

But this stuff is already known, I am just trying to look at the relationship more directly. In fact I have professor friends hwo have tried to sort out all the implications of base a arithmetics as part of Phd dissertations and years later they are still unable to get it all down. I think the key connection is threefold, the first is the way in which a base a alphabet is used to form words that represent natural numbers in a one to one fashion (a grammar that is unique to the base), the second is the way two of these grammars are related, and the third is how those facts limit or shape arithmetic calulation algorithms over the base. From there it is quite clear that diophantine equations have rather interesting properties. If they are true for any natural number they must have a solution over every base. But the word used to express the solution can have unique multiplicative properties over its base, so that addition and multiplication algorithms are conceptually related for all bases but adding the same to integers proceeds in different ways for different bases. For instance 15 = 2^3+2^2+2+1 or 1111 base 2, a special form in any base. However 15 is also equal to 3^2+2*3 base 3 and clearly divisible by three. In a structural sense the change of base has simplified the task of factoring 15. Understanding IN DETAIL how the base a arithmetics are related gives us hope of simplifying any diophantine equation though not by applying the same steps in a mechanical fashion. Rather there probably exists a grab bag of steps, that when allowed to happen in whatever order they are needed suffices to solve every diophantine euqation. Just as Abel has showed us with polynomials, no fifth order general solution, but any fifth order polynomial with natural number solutions can be solved by some method. Until I see a complete exposition of the base a arithmetics with respect to these various questions I won't except that there is nothing worth looking at. In fact what I have already found is quite intersting enough to warrant further investigation. No offense, but I have seen too many middling intellects dismiss hard questions because they require more than a few blackboards worth of chalk. And many of these fellows have Phd's. I despise lazy thinkers. You and Hurk do not seem to be of that ilk. On the goldbach issue, take the rrs mod p#[k] set it up in ordered pairs that sum to p#. Now using some facts about the rrs mod p#[k1] count all of the composite numbers in the set. If this is smaller than phi(p#[k]2)/2 Goldbach must be true by the pidgeon hole principle. That takes us some way up into the atmosphere. The problem will be if the prime density within the rrs mod p#[k] gets much below that, not because the proof cannot be done, but now we have to count the composites and verify where they are to argue that not all of the ordered pairs can have at least one composite element. But so once that proof were varified it shoul dbe extendable to any sequence of the form of p#, meaning a sequence formed by multiplication of primes. Getting past the square free sequences will be the real hurdle I think. There is alot so far in this thread I need to come back to. With some luck I will find the time to do these ideas justice. 


#40
Jul906, 11:42 PM

Sci Advisor
HW Helper
P: 1,994

Just a quick note for now:



#41
Jul1006, 12:14 AM

Emeritus
Sci Advisor
PF Gold
P: 16,091

But there are Diophantine equations for which no algorithm  no "grab bag of steps"  is capable of saying "this Diophantine equation has no solution". The idea of the proof is actually quite simple: we can write down a Diophantine equation and then prove that the statement: "This Diophantine equation has a solution" is logically independent of the axioms of integer arithmetic. It's sort of like the parallel postulate from geometry  you can assume the parallel postulate is true and do Euclidean geometry. Or, you can assume the parallel postulate is false, and do hyperbolic geometry. Either way, you are working in a perfectly consistent^{2} mathematical theory. The same is true with certain Diophantine equations^{3}; you can assume it does have a solution and do one kind of number theory, or you can assume it has no solutions and do another kind of number theory. (I know I keep harping on this  I think it's important, and I can't really tell for sure if the ramifications of this fact has sunk in) I was thinking about how likely it is that you can multiply two ndigit base b numbers so that there are no "carries" involved. The product will have less than 2n digits, and for each of those, there will be less than b nonzero digit products that contribute to it. So, if our original numbers had k nonzero digits, then the number of nonzero products will be kČ, so we must have: kČ < 2bn (This is a very generous bound) So, in general, we see that if we can multiply large base b numbers so that there are no overflows, then (at least one of) the numbers have to be very sparse  for a large n digit number, only about the square root of n digits may be nonzero. 1: Okay, okay, there's a technical detail. We have to assume that it is possible to enumerate the natural numbers. I.E. any particular natural number will (eventually) be printed by the following program:
3: While we have discovered some Diophantine equations with this property, there must exist Diophantine equations for which we cannot prove they have this property. 


#42
Jul1006, 01:48 AM

Sci Advisor
HW Helper
P: 3,684




#43
Jul1006, 07:03 AM

Emeritus
Sci Advisor
PF Gold
P: 16,091

What I stated follows naturally from a formal logic/computability theory standpoint. Briefly, the idea is that if there is no algorithm for deciding whether a given Diophantine equation has a solution, then we cannot derive a contradiction by assuming it does or does not. 


#44
Jul1006, 02:11 PM

Sci Advisor
HW Helper
P: 3,684




#45
Jul1006, 04:35 PM

Sci Advisor
HW Helper
P: 9,484

DAVIS, ROBINSON, AND PUTNAM, are usually credited as well. matiasevich just put in the last brick in the wall.



#46
Jul1406, 03:42 PM

P: 92

[tex]C_0=x_0y_0 < a[/tex] The first order coefficient must obey [tex]C_1=x_0y_1+x_1y_0 < a[/tex] In general the nth order coefficient has to obey [tex]C_n=\sum_{i+j=n}x_iy_j < a[/tex] For polynomials of high degree it becomes exceptionally unlikely that they will mutliply wihtout carrying. However once we have identified this space where no carrying happens, we can begin categorizing the carrying spaces. For instance it is know that for any base a and residues x and y, [tex]xy\leq(a1)^2[/tex] So the zeroth order carry is between zero and a2. This can be done for each order. In general the carry L (for leap) obeys [tex]0\leq L_n \leq \{(i,j)i+j=n\}(a1)^2[/tex] As you start looking at how the various possible carries cover the full set of possibilities, they start to cover it very quickly, so that most numbers are factorable starting with the no carry space and simply walking through the possibilities. In fact we strarted with say a cubic polynomial and order all the possible carries in terms of the size of factor set they cover (with respect to a particular number to be factored and a given base a expansion) we could arrive at a solid estimate of the probablity of factoring a number in a given number of steps. My thoughts are that these things I have been talking about are not new per se, but may simply be a different way of looking at the same mathematical objects. The particular shape of those objects does not really change, we just develop different projections of it. In fact it should be easy to see that the solutions to any and all congruences are governed by the unchanging relationship of primes and composites within the natural numbers. Well of course that should be clear from the fundamental homomorphism theorem taught in first semester abstract algebra. My thing, that I do not have time now to think much about, is wondering if there is not some discrete embedding space which opens this onion up even more. I realize we may start running into Godel type issues as you mentioned above. But I am still thinking that there may exist a further insight here that allows us to recognize the path of the carrying operation. At first glance that seems unlikely because it is not one to one. But we have the ability to jump between bases as often as needed. Perhaps a unique signature can be deduced in that fashion. Perhaps by some series of base changes we might arrive at a polynomial whose solutions are in fact the carrying values for each order. Polynomials which do not allow such a mapping would be very special indeed. or they may be the norm. But alas, now I must seek to make money, and number theory is no way in which to do that, at least for now! Also the algorithm I mentioned above where we map a number n onto other numbers base ten with similar multiplicative structures seems quite plausible to me. But that one opens up alot of time questions, expecially if we are choosing larger numbers. Schmoe already mentioned most of that. Later 


#47
Jul1406, 10:30 PM

P: 92

I know schmoe I can see that plainly. But there is still more detail to be had in the relationship between successive rrs for p#, just use the theorem I mentioned above for generating the rrs for consecutive elements in p#. You'll see that the nonprimes are all found by taking products of units in the smaller element. This pattern can be worked out of that I am certain but we will have to pay attention to discrete details that most analytical minded folks try to avoid. The density is a truth but it is a bounding type of thing, it does not prove that no path to Goldbach exists using the outline I have provided. It's not going to be easy but few things worth doing are. I just don't have time right. Maybe in a year or two if I decide to go for the Phd I will do number theory. Right now I have to try and find a job. Once that is done I will have more leisure time. Then I can get a bottle of Courvoisier and really think about it. 


#48
Jul1506, 09:30 AM

Sci Advisor
HW Helper
P: 1,994

You might want to take the time to work out phi(p#) and pi(p#) to some distance. pi(p#) gets difficult to find pretty quick, but the prime number theorem will work well. I think Dusart's work is the latest on concrete bounds for error terms, so it might be worth looking into that if you don't like the bigO term with unspecified constant in the prime number theorem. 


#49
Jul1506, 10:52 AM

P: 92

Now it is quite possible that the number of composites relatively prime to p# is quite large and I will look at it eventually. The density going to zero means as we go further out it becomes quite amazing to suppose that Goldbach should be true for this sequence. So therefore I expect to find some very interesting things as I pursue the details. Conceded, pidgeon hole only works to p#[13], but more details of the relationship between p#[k] and p#[k+1] remain to be understood. You are an expert in number theory, surely you realize that all of the composites in rrs p#[k+1] are generated by multiplying units in p#[k]? Meaning set up the multiplication table for rrs p#[k] and simply count the points less than the hyperbola xy=p#[k+1]. Think about that graphically and useful patterns beyond the plain gray of the pidgeon hole principle start to emerge. I really do not have time now to get into it. Bit I will and perhaps it will fail. If it does then it does. You know sometimes instead of using big powerful theorems to avoid the details, we actually have to go in and start looking at things on a case by case basis until patterns start to emerge. I know it's a method not to be generally recommended, experimental number theory is only advocated by fools who believe Chaitin is correct. 


#50
Jul1606, 01:17 AM

Sci Advisor
HW Helper
P: 1,994

I'm not sure I see the relevance of this comment? Is it a supposed failing of analytic techniques? This shouldn't be suprising. Density zero sets can still be 'dense enough' for 'stuff' to happen. for example if a sequence has positive upper density then it contains arbitrarily long arithmetic progressions (Szemerdi). The primes have density zero, yet this is also true for the primes (Green,Tao). 


#51
Oct606, 08:30 PM

P: 92

I will probably have to open a separate thread in the general discussion area about the culture in mathematics. There is much ot be discussed there. Having been around the community for some amount of time I too have had my share of dealing with folks who think that .999... >< 1. What can you do. But not everyone who has a unique approach is of that vein. Of course it is rare to meet the exception and I do not claim to be the one who can reinvent number theory or that it even needs to be reinvented. But I do chaff, and begin gnawing at the bit when I see a mathematician that is effectively a social retard making others feel bad because they don't get it. Those types of things lead to Bastille Day. Being smart is not enough, the mindless masses pay your salary through taxes. Either get your attitude in check with reality or take your chalk and go home! That is a rebuke I am willing to accept myself. I spent many years after my BS puffed up by the 'mentoring' of various elements in the math community. So yes experimentation. I mean free and creative thinking, which De Morgan felt was essential to all mathematical progress. That does not remove the precedent of established mathematical truths. However techniques are still growing. We all should aspire to do something where we can be original, in my opinion. If math isn't that for someone, then maybe they would be happier somewhere else. At any rate, we need library books. Some folks function as wetware, library collections of facts about math and science. I have no problem with that but a jerk is a jerk is a jerk. A saying I really like is by Plutarch , "Be kind, everyone you meet is fighting a hard battle." I came back because I am working out a partial proof of the Goldbach Conjecture, at least I have a solid idea. I will post the key question in the number theory thread. 


#52
Oct1106, 07:59 AM

Sci Advisor
HW Helper
P: 1,994




#53
Oct1506, 09:18 PM

P: 92




Register to reply 
Related Discussions  
Integer Factorization Algorithm  Linear & Abstract Algebra  9  
LUFactorization Algorithm?  Calculus & Beyond Homework  0  
Construct for a Base a Factorization Algorithm  Linear & Abstract Algebra  0  
Factorization Algorithm II  Linear & Abstract Algebra  3  
LDL factorization  Calculus & Beyond Homework  3 