Page 2 of 2 FirstFirst 12
Results 16 to 21 of 21

Thread: A Theorem generating 3-factor Carmichael Numbers

  1. #16
    Jun 2008
    Quote Originally Posted by Media_Man View Post
    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.
    Ah, I assume your referring to the stuff on pg8 of Pomerance's paper, beginning with his Corollary 1, yes?

    This does seem similar, but its a little confusing. He says we can partition the Carmichaels into families depending on the ''ratios of the p-1's'' for each p dividing n (I assume these ratio numbers are the same as our sets $\displaystyle u_1,u_2,...,u_k$).

    I don't see a proof for this right after, so I figure this must immediately from some other theorem or statement he put above (or elsewhere).

    Afterwards, he constructs a set of $\displaystyle a_1,a_2,...,a_n$ which can be used to produce these ''families''. He doesn't say (at least not on pg8) though that his construction actually partitions or generates all the Carmichaels (maybe its implied).

    Anyway I haven't read through the whole 26 pgs (and some parts I just skimmed through). Let me know what your thoughts are.
    Follow Math Help Forum on Facebook and Google+

  2. #17
    Super Member Aryth's Avatar
    Feb 2007
    In my original post I stated that the upper bound was $\displaystyle p_1^6$ it is in fact $\displaystyle 2p_1^6$, and here's the proof you requested jamix:

    Theorem: Let $\displaystyle n = rst$ be a Carmichael number with r,s, and t prime. Without loss of generality, we assume that $\displaystyle s < t$. The following then hold:

    (i) $\displaystyle s < 2r^2$
    (ii) $\displaystyle t < r^3$
    (iii) $\displaystyle n < 2r^6$

    Proof: Let $\displaystyle n = rst$ be a Carmichael number of three factors. We know that $\displaystyle (p_i - 1)|(n - 1)$ for i = {1,2,3}. We can then see that:

    $\displaystyle (t - 1)|(rs - 1)$ and
    $\displaystyle (s - 1)|(rt - 1)$

    These imply that:

    $\displaystyle rs - 1 = m(t - 1)$ for any $\displaystyle m \in \mathbb{N}$


    $\displaystyle rt - 1 = q(s - 1)$ for any $\displaystyle q \in \mathbb{N}$

    Since we said that $\displaystyle s < t$ we can then say that $\displaystyle m < q$, in particular:

    $\displaystyle m \geqslant 2$ because

    $\displaystyle rt - 1 = 1(s - 1)$ contradicts the primality of s.

    Same for q and 1(t - 1).

    So, we get:

    $\displaystyle t = \frac{(rs + m - 1)}{m}$

    $\displaystyle s = \frac{(rt + q - 1)}{q}$

    Putting the equation for t into the equation for s, we get:

    $\displaystyle s = \frac{r^2s + mq + (r - 1)m - r}{mq}$

    This implies that:

    $\displaystyle (r^2 - mq)s + mq + (r - 1)m - r = 0$

    This gives you:

    $\displaystyle s = \frac{mq + (r - 1)m - r}{mq - r^2} < \frac{mq}{mq - r^2} + \frac{(r - 1)m}{mq - r^2}$

    This result tells you that $\displaystyle mq \neq r^2$ because the opposite yields $\displaystyle m = q = r$ and

    $\displaystyle rs - 1 = r(t - 1)$

    $\displaystyle t = s + 1 - \frac{1}{r}$ which is not in $\displaystyle \mathbb{N}$.

    We are then going to say that $\displaystyle mq > r^2$ because $\displaystyle s > 0$ and $\displaystyle mq + (r - 1)m > 0$

    This will then give us:

    $\displaystyle \frac{mq}{mq - r^2} \leqslant \frac{r^2 + 1}{(r^2 + 1) - r^2} = r^2 + 1$

    It is common in most proofs to now review by using positive real numbers x, y , and z where $\displaystyle x > y > z$, we then have:

    $\displaystyle \frac{x}{x - z} < \frac{y}{y - z}$

    Since we assumed that $\displaystyle s < t$ we have $\displaystyle r(t - 1) > rs - 1 = m(t - 1)$ hence $\displaystyle m < r$. We can then say that:

    $\displaystyle \frac{(r - 1)m}{mq - r^2} < \frac{(r - 1)r}{mq - r^2} \leqslant r^2 - r$

    This gives us:

    $\displaystyle s < r^2 + 1 + r^2 - r < 2r^2$ Assertion 1.

    From $\displaystyle rs - 1 = m(t - 1)$ and $\displaystyle m \geqslant 2$ we get:

    $\displaystyle t \leqslant \frac{rs + 1}{2} < \frac{2r^3 + 1}{2} < r^3$ Assertion 2.

    And finally, we get:

    $\displaystyle n = rst < r(2r^2)(r^3) = 2r^6$ Assertion 3.

    As desired. Pardon my horrible symbols, that's how I write it down... Sorry about that.
    Follow Math Help Forum on Facebook and Google+

  3. #18
    Senior Member
    Apr 2009
    Atlanta, GA

    Verdict from Dr. P.

    Alright gentlemen (and/or ladies), it seems what we have uncovered is indeed new but not terribly important. If anything, it is a means to an end, that most popular end being the statistical distribution of said Carmichaels. Which brings us back to an earlier question of mine: Can what we've uncovered be used to attack any current open conjectures in the field?

    Dr. P. fills us in on the state of affairs on open issues, gives us some further reading, compliments one of our results, and finally, issues us a challenge of sorts.

    Mr. Davis,

    My and other's interest in this way of writing Carmichael numbers has
    been to get a handle on statistical counts for them. In particular the
    paper of mine with Granville separates Carmichael numbers into 2
    classes, which in the case of 3-prime Carmichaels comes down to
    g <= abc and g > abc. We can get good estimates for the latter class,
    and not-so-good estimates for the former.

    You might also check out section 5a in the paper I mentioned. There
    you can see that we have some, but not all, of your results. Also, other
    papers are referenced there at the end, where those authors also knew
    the same kinds of things. There is a newer paper which is not referenced
    there: Carmichael numbers with three prime factors, by D. R. Heath-Brown,
    appearing in the Hardy--Ramanujan Journal 30 (2007), 6--12. (I think this
    journal is available free online.)

    I did not know that g = 0 mod abc only in the case a,b,c = 1,2,3, which is
    one of your results (your point 4 below).

    In any event, we still have not proved the conjecture that for each c > 1/3,
    and x sufficiently large depending on c, the number of 3-prime Carmichaels
    below x is < x^{c}. And results for 4-prime Carmichaels are in a much worse
    state affairs, so there is a lot that needs to be done.

    Sincerely yours,
    Carl Pomerance
    Follow Math Help Forum on Facebook and Google+

  4. #19
    Jun 2008
    Aryth, thanks so much for the proof. It's a neat property. Do you know if something similar holds for Carmichaels with more factors?


    I thought what we had wasn't new (at least not the main aspect). Pomerance's questions are probably very difficult in the sense you'd likely need tools from Complex Analysis to solve them. This is Analytic Number Theory my friend, very tough and unfamiliar subject. I'm going to be taking a grad course in it for the first time next Fall.

    If you want to attempt the question here, I recommend linking some of the papers Pomerance mentioned. It may not matter, as my time is going to be limited again soon as the typical cycle of classes, research, and TAing repeats itself.

    Thanks for the fun coressponence
    Follow Math Help Forum on Facebook and Google+

  5. #20
    Senior Member
    Apr 2009
    Atlanta, GA

    Chernick 1939

    Mathworld and other sites present $\displaystyle (6k+1)(12k+1)(18k+1)$ as the only known Carmichael Polynomial (as we're calling them), found by Chernick in 1939. Turns out, Chernick made it a lot further than that. Check out attachments.

    Chernick investigates what he calls "Universal Forms" which are identical to our formulation, and extends to more than 3 factors.

    Dubner derives a very accurate formula for counting them.

    Looks like we were beat to the punch by seventy years!

    It seems to me that it would be pretty straightforward (theoretically) to combine these two approaches and get a heuristic count for 3-Carmichaels correct to only a few percent error. Consider:

    $\displaystyle U_3(a,b,c)$ is a "Universal Form" a.k.a. "Carmichael Polynomial" that produces approximately $\displaystyle u_{a,b,c}(x)$ 3-factor Carmichael Numbers not greater than $\displaystyle x$. Wouldn't then the total number of 3-factor Carmichael Numbers not greater than x be gotten by taking the sum of all these counting functions over every possible pairwise coprime triplet?

    $\displaystyle u(x) \approx \sum_{a,b,c \in A} u_{a,b,c}(x)$ , for $\displaystyle A=\{a,b,c \in \mathbb{N}|(a,b)=(b,c)=(a,c)=1\}$? With a little ingenuity and a crapload of algebra, can't we find an explicit formula for this? I've been reading up on the logarithmic integral function, and I think this is within reach for a bunch of old amateurs recreating 1930s results
    Attached Files Attached Files
    Follow Math Help Forum on Facebook and Google+

  6. #21
    Jun 2008
    I skimmed through the two papers you listed. Are you saying that we should attempt to generalize Dubner's method for counting the carmichael's (6k+1)(12k+1)(18k+1) to those of each universal form and then just sum everything up?

    Are you sure Pomerance hasn't done this yet?
    Follow Math Help Forum on Facebook and Google+

Page 2 of 2 FirstFirst 12

Similar Math Help Forum Discussions

  1. proof with carmichael numbers
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Dec 15th 2009, 07:28 PM
  2. two definitions of Carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Sep 27th 2009, 10:18 AM
  3. carmichael numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: May 9th 2009, 06:52 PM
  4. Carmichael numbers
    Posted in the Number Theory Forum
    Replies: 17
    Last Post: Apr 21st 2009, 09:09 PM
  5. Carmichael Numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Mar 25th 2007, 05:09 AM

Search Tags

/mathhelpforum @mathhelpforum