# A Theorem generating 3-factor Carmichael Numbers

Show 40 post(s) from this thread on one page
Page 2 of 2 First 12
• April 26th 2009, 05:52 PM
jamix
Quote:

Originally Posted by Media_Man
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 $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 $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.
• April 27th 2009, 04:35 PM
Aryth
In my original post I stated that the upper bound was $p_1^6$ it is in fact $2p_1^6$, and here's the proof you requested jamix:

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

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

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

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

These imply that:

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

and

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

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

$m \geqslant 2$ because

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

Same for q and 1(t - 1).

So, we get:

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

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

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

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

This implies that:

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

This gives you:

$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 $mq \neq r^2$ because the opposite yields $m = q = r$ and

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

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

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

This will then give us:

$\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 $x > y > z$, we then have:

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

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

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

This gives us:

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

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

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

And finally, we get:

$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.
• April 28th 2009, 08:50 AM
Media_Man
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

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
• April 29th 2009, 07:09 PM
jamix
Aryth, thanks so much for the proof. It's a neat property. Do you know if something similar holds for Carmichaels with more factors?

Media_man

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
jshort
• May 9th 2009, 08:13 PM
Media_Man
Chernick 1939
Mathworld and other sites present $(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:

$U_3(a,b,c)$ is a "Universal Form" a.k.a. "Carmichael Polynomial" that produces approximately $u_{a,b,c}(x)$ 3-factor Carmichael Numbers not greater than $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?

$u(x) \approx \sum_{a,b,c \in A} u_{a,b,c}(x)$ , for $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 (Nod)
• May 10th 2009, 07:58 AM
jamix
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?
Show 40 post(s) from this thread on one page
Page 2 of 2 First 12