Thread: A Theorem generating 3-factor Carmichael Numbers

Choose three arbitrary positive integers such that any two are coprime.

Define:




Lemma: See proof here: http://www.mathhelpforum.com/math-he...tml#post303617

Let and
Note that the above lemma is a necessary and sufficient condition for to exist.

Define:




Theorem: For any m such that are all prime, is a Carmichael Number.

Proof: Assume are all prime. For their product to be a Carmichael Number, it is sufficient to show that

Substituting via the above construction,




Since , each of these divide the cubed term, and divides all terms.

Thus, the sufficient condition becomes: for all
Alternatively,
Or,


Notice that by construction, and , therefore this condition is true for all .
Also notice that for this to hold for all , and . Therefore this choice for is unique.
Q.E.D

We now have a method, given an arbitrary pairwise coprime triplet , of generating a string of Carmichael Numbers!

Results:
For generates Carmichaels 1729, 294409, 56052361, 118901521 …
For generates Carmichaels 29341, 1152271, 64377911, 775368901 … (For this one, k must be even, so a=30 works as a refinement)
For generates Carmichaels 2465, 6189121, 19384289, 34153717249 …
For generates Carmichaels 6601, 191614761361, 5124854089205401 ...

It can also be shown that assuming, without loss of generality, that .

You're theorem is interesting though, it is a lot more concise than the other theorems I see, how did you come up with this method?

I agree, neat stuff. I don't think I see any errors either this time. I suspect your method encompasses all 3-factor Carmichaels too I believe.


So is it up to 4-factor Carmichaels now? You might be able to prove something similar using the same lines of attack as above. If your hoping to do original stuff, maybe take Aiden's advice from previous thread and send Pinch an email, or perhaps even C. Pomerance. Those guys know whats been done and whats around.

Originally Posted by Aryth

It can also be shown that assuming, without loss of generality, that .

Can you show me the proof for this (or a link to a proof)? Thanks.

Media_Man


I was thinking instead of starting with a fixed set , we define a single integer which is a product of at least two prime numbers. You can show that for such an , there exists a finite number of distinct sets such that where each are pairwise coprime and







where for each distinct set . This is a cleaner defined partition of your 3-factor Carmichaels I believe.


For reference let us call an integer a Media_man number if ( prime), and there exists an integer such that the are pairwise coprime, and for each .


I suspect many but not all 3-factor Carmichael numbers are Media_man numbers.

Originally Posted by Media_Man

Notice that by construction, and , therefore this condition is true for all .
Also notice that for this to hold for all , and . Therefore this choice for is unique.[/tex]

Questions for you: What happens if we pick different than above such that holds only for some ? In particular, if for such chosen we have that all prime, then would be a 3-factor Carmichael that isn't a Media_man number?


Finally now, can we directly generalize this to 4 or higher factor Carmichaels? The following below suggests that the answer is ''not always'' (I'm not sure about this one though, so you should read this part carefully). Indeed, suppose we tried to do this for Carmichaels that had distinct prime factors (i bigger than 3) .


For a given set where the terms in this set are pairwise coprime, define the following:




.
.
.





and where are constants yet to be determined.


Now in order for to be a Carmichael, we would need the following condition:





Unlike for i=3, I don't think a solution pair exists for every set . Hence we may need to put some conditions on .

You're theorem is interesting though, it is a lot more concise than the other theorems I see, how did you come up with this method?

Jamix and I have been looking at Carmichaels here: http://www.mathhelpforum.com/math-he...l-numbers.html

is known to produce Carmichaels, and after finding two other such polynomials, I wanted to try to (a) find more or all of them and (b) generalize them.

I suspect your method encompasses all 3-factor Carmichaels too I believe.

This is possible, but improbable. On excel, I calculated for the known Carmichaels up to and looked for patterns. The "blueprint" left behind, was pairwise prime in every 3-Carmichael I looked at, which is odd. If you pick three primes at random, some such blueprints should be pairwise prime and some not. It is probable that if you go high enough, you will invariably find a counterexample. I hadn't looked at this yet, because I assumed it to be false. But if we don't find any counterexamples up to , we ought to try to prove it. This result would surprise even me.

So is it up to 4-factor Carmichaels now? You might be able to prove something similar using the same lines of attack as above.

I've looked at the 4-factor case. If we use the same logic, it gets much more complicated much more quickly. For the three factor, we end up with the modular equation (using your much better notation):



With the 4-factor case, Mr. Pascal puts us here:



Undoubtedly more complicated. We can find b via the quadratic equation (this still holds in modulo, yes?), requiring to exist as before, must be a square, must exist ( must be odd). Going further, , and lastly, either OR . Before you get overzealous and solve for every possibility, remember that each of these conditions must be proved by going back to the definitions of all your 's.

Add to the fact that several very low 4-Carmichaels have "blueprints" NOT pairwise prime. In a nutshell, I do not believe we can reach the same conclusions as we did in the 3-factor case. If we do, it will be insanely more complex, and moving to the 5-factor case will only get worse. I think at this point we need to find a new approach.

Originally Posted by jamix

I was thinking instead of starting with a fixed set , we define a single integer which is a product of at least two prime numbers. You can show that for such an , there exists a finite number of distinct sets such that where each are pairwise coprime and







where for each distinct set . This is a cleaner defined partition of your 3-factor Carmichaels I believe.

Yes, indeed it is. This would associate each such Carmichael with a natural number, and conversely, every natural number - - would generate one or more cubic polynomial producing Carmichaels.

I suspect many but not all 3-factor Carmichael numbers are Media_man numbers.

This is a very important question. It is equivalent to the following: (1) The set is always pairwise prime for Carmichael numbers . And (2) each Media_Man polynomial produces a unique string of Carmichaels mutually exclusive from the others.

Questions for you: What happens if we pick different than above such that holds only for some ? In particular, if for such chosen we have that all prime, then would be a 3-factor Carmichael that isn't a Media_man number?

If the above question is false, then yes. Probably we would simply generate another Media_Man number whose "natural" construction was some other .

This is an interesting question, Jamix. Letting , and 's be all possible pairwise prime collections. We know that any natural number S - - begets a 3-factor Carmichael, but can we place restrictions on S in order to generate 4-Carmichaels?

Let's not forget another very important question. It is still unknown if (6k+1)(12k+1)(18k+1) produces infinite Carmichaels. When we construct a polynomial , we still require that every factor be prime for the same k. Therefore it is possible that no such k exists, or only a finite number of k's. Conjecture: For every Media_Man cubic polynomial, there exists an infinite number of k values producing Carmichaels.

Okay, guys. Attached is a more formal write-up. I've sent an email to Dr. Pinch asking if this result is new. We'll see soon enough how he responds. In the meantime, please review the attached pdf file for any mistakes.

I did manage to prove that they're mutually exclusive. I also proved that every 3-Carmichael can be expressed by a 3-polynomial, which was very surprising to me and does not work in the 4-factor case. Therefore, these polynomials do indeed partition the set.

The most important open questions - in my opinion - now are (1) extending this idea to Carmichaels with more factors and (2) proving that these polynomials each produce an infinite string of Carmichaels.

Also, it seems silly now, but can anyone think of a practical use for this? Are there any open questions or conjectures about Carmichael Numbers that can be answered by these polynomials?

p.s. If somehow someway this result was important enough that the powers that be deemed it publishable, I'll send everyone a personal message requesting your "real" names, so you can be properly credited.

Good stuff! You weren't kidding when you said you've been doing your research (creative thinking?). You should think about going back to school sometime to increase your mathematical knowledge, so as to become an even better researcher some day. You'd be pretty good in academia I believe.

Anyway's regarding your attachment, I have the following advice:

1. On pg1 where you define your you should also include in it (or right after) a definition of what a ''Carmichael Polynomial'' (''3-factor Carmichael polynomial''?) is. This term is central in your paper, hence it should be given a formal definition as well. Something like,

Definition: 3-factor Carmichael polynomial :

For pairwise relatively prime positive integers and defined as above, denote , where and
.

2. Regarding Corollary 1.1, you should write this one down on pg5 right after Theorem 2

3. Corollary 1.2 is fairly important. I would recommend writing it as a theorem. Also Corollary 2.1 and 2.2 say the same thing pretty much. I'd write only corollary 2.2 and put it under the new theorem corresponding to what used to be called Corollary 1.2.

4. In the section Continuations, you say the Carmichaels with 4 prime factors or more cannot be partitioned, because theorem 2 is false. You may want to explain your reasoning here somewhat.

5. Good luck!

Originally Posted by Media_Man

The most important open questions - in my opinion - now are (1) extending this idea to Carmichaels with more factors and (2) proving that these polynomials each produce an infinite string of Carmichaels.

I doubt we'll be able to prove (2), however with regards to the question ''Are there some Carmichael polynomials that produce more Carmichaels than other Carmichael polynomials?'', I'd guess that those whose ''blueprints'' , are such that the product is highly composite (ie divisible by many small prime numbers) is likely to produce more Carmichaels, then those that have a product that is not highly composite.

Originally Posted by Media_Man

Also, it seems silly now, but can anyone think of a practical use for this? Are there any open questions or conjectures about Carmichael Numbers that can be answered by these polynomials?

Primality testing is a very applicative field since prime numbers play important roles in various crytosystems. Since finding integers that are prime require proving that these integers are prime, and because a Fermat primality test is a typical way to test for the primality of an integer, Carmichaels and pseudoprimes in general become an interesting area of study since these integers are composite despite passing the Fermat test. My personal interest is not so much Carmichaels, but rather pseudoprime integers that pass a Fermat test for a particular number of bases (starting from base a=2 and going up from there). By studying pseudoprimes and their distribution, we are able to make conclusions about the probability that a particular number is prime given that it passes the Fermat test to several bases.

2. Regarding Corollary 1.1, you should write this one down on pg5 right after Theorem 2

Are you saying it is customary to list all corollaries after all theorems? Or are you saying that 1.1 does not immediately follow from theorem 1?

3. Corollary 1.2 is fairly important. I would recommend writing it as a theorem. Also Corollary 2.1 and 2.2 say the same thing pretty much. I'd write only corollary 2.2 and put it under the new theorem corresponding to what used to be called Corollary 1.2.

I rewrote it to be more clear. Cor 1.1 establishes that for each 3-Carmichael with a pairwise coprime "blueprint," at least one exists. Cor 1.2 says that at most one exists. These can be lumped into the same theorem, but since they have two distinct proofs, I listed them separately. Is 1.1 circular reasoning? Perhaps I need to define "blueprint" in the paper. I wanted to nail down the fact that a Carmichael with blueprint must be generated by polynomial , which seems reasonable but still requires a proof.

I edited a lot of stuff to make it more clear, but didn't change any proofs or anything. You might want to skim through the new document before commenting further. Thanks for the feedback!

According to the Prime Number Theorem for arithmetic progression , for , the number of primes produced less than is . So, the probability of three such progressions being prime at the same time is therefore

By our construction, the approximate number of 3-Carmichaels produced by

Note 1: decreases to zero asymptotically, so the number of 3-Carmichaels produced by a specific 3-Polynomial gradually decreases, as expected.

Note 2: produces more Carmichaels for a lower value of .

Note 3: The total number of 3-Carmichaels under x is approximately equal to the infinite sum of such terms for all pairwise coprime triplets, which is verifiable.

*I included this as an argument for our last conjecture, but this material is over my head. Can someone verify what I have so far? Can this last Note be simplified and verified?

Mr. Davis,

I have something similar in a paper with Andrew Granville,
it is #124 on my website. In particular, section 2 shows
that every Carmichael number belongs to a family similar
to the ones you have with 3 prime factors. The family is infinite
assuming some standard conjecture about the factors of
the polynomial involved being prime infinitely often.
Let me know if you still think what you have is genuinely
new. My website is Carl Pomerance .

Carl Pomerance

************************************************** **************
Here's the paper: http://www.math.dartmouth.edu/~carlp/PDF/paper125.pdf

It appears to prove that every Carmichael Number falls into a "family" of other Carmichael Numbers. Same concept, but I think we have something much more constructive and concise. What do you guys think?

Ah C. Pomerance then eh. He's a better choice then Pinch I believe (in my opinion he's the one guy whose really leading the field in Computational Number Theory).

I haven't gone through his paper you put yet, but if you really think you've got something new, then the next step is to make the communications of your ideas with him as clear and easy to follow as possible. When I was reading your papers (even your edited one) I didn't find any errors in the proofs, however I thought it was a little disorganized (at least compared to publishable stuff). I could work my way through it, however thats only because I've been discussing this with you this whole time. I'm not sure how well Pomerance was able to pick out the important points and reference them with his own work. In any case, Iike I said, try as hard as you can to express yourself as clearly as possible.

With regards to your six page stuff, I've gone through it now, and have made many reccommendations below. My advice is that you try to incorporate some of these simplifying ideas in your work.

Also make sure you've understood Pomerance's result so as to be able to understand how its different from yours (or what exactly it is thats NEW that your result gives). This may sound a little unfair on your end, however it would be great if you can grab the attention of a star like Pomerance, and even better if he was willing to add to your result so you could write a joint paper with him.

NOW FOR THE RECOMMENDATIONS

1. You should add the following line at the end of your Abstract.

''Furthermore, we shall partition the polynomials and show that such a partition, also partitions the Carmichael integers that have 3 prime factors. A few other interesting results shall also be discussed''.


2. On pg1 you define a Carmichael Polynomial as an expression of the form such that when each term is prime, the product is Carmichael. From here you go on to make various definitions and prove a lemma which shows how we can construct each such that the above property holds. This looks a little confusing in my opinion. As a simplification, I recomennd the following definition.

For a given set of integers , all coprime, we shall define the polynomial , which shall be called the 3-factor Carmichael Polynomial, as follows:




where






(note: It can be shown that hence the definition for is well defined)

You should mention here that by construction, it can be shown that .


Now, state (then prove) Theorem 1, which instead, should say the following:

Theorem 1: for each and for all m.

After you've done this, state Cor 1.1 as follows:

For the values of such that is a product of 3 primes, is a Carmichael number.

As Cor 1.2, state the following:

There exists infinitely many polynomials of the form that satisfy Korselt's Criteria for all k.

This is what I'd do next:

1. From your paper, write Theorem 3 as ''Proposition 1'' (followed by proof), then write your old Cor 1.1 as ''Proposition 2'' (followed by proof), then write Theorem 2 as ''Proposition 3'' (followed by proof). If you've decided to apply some of the above recommended changes, then you may want to reword one or two of these currents Propositions. Finally, after all this, write a Theorem that says something like the following:
   
   
   
   
   ''For every 3-factor Carmichael , there exists one and only one 3-factor Carmichael Polynomial such that has a solution''. For such a , only one solution exists

Finally, write down your old corollary 1.2 as is, then wrap things by retyping in your final comments and conclusions.

PS: I may have gotten a little carried away with all my above suggestions. Just change whatever you think it is that will simplify things.

PS: I may have gotten a little carried away with all my above suggestions. Just change whatever you think it is that will simplify things.

Haha, yes very thorough indeed. I had some very clear ideas, but my problem is putting them to paper as clearly as I am able to think them. Your suggestions are therefore much appreciated.

I simplified as best I could, lumping all our definitions under one section. I think in coining the phrase "Carmichael Polynomial," it should remain generic, simply any polynomial that returns a Carmichael Number when each of the polynomial's factors is prime. We're then proving that our construction encompasses all of them for the 3-factor case, and not simply stealing the name.

I also did away with the conjecture at the end, and its corresponding argument, as it is already an open conjecture.

Pomerance's paper seems to say that given a Carmichael n, a polynomial exists that produced it and this same polynomial produces more Carmichaels - same idea as ours. I think, therefore, our strongest point is that these polynomials are homeomorphic to the set of all triplets (a,b,c) satisfying lcm(a,b,c)=abc. We also provide some more rigorous proofs about these corresponding families.