4 ms·
Summary: 1. Fermat's Little Theorem: if p is prime, then b^p = b (mod p) for all integers b. i.e. b^p - b is always a multiple of p. 8^3-8 = 512-8 = 504 = 168
by renewiltord 4y ago
Summary:
1. Fermat's Little Theorem: if p is prime, then b^p = b (mod p) for all integers b. i.e. b^p - b is always a multiple of p. 8^3-8 = 512-8 = 504 = 168 x 3.
2. Is the inverse true? Does b^n - b = 0 (mod n) mean that n is prime? No. Sometimes n is non-prime (like n=561, divisible by 3). We call these n, Carmichael numbers.
3. Okay, so these numbers exist. How common are they? For primes we know they're common. Bertrand postulated (Chebyshev proved) that for any n>1, there is a prime p between n and 2n. That's cool!
4. Is it true that there is such a bound for these pretend-primes? Well, we have an interesting fact that there are x^(1/3) of them below any x, once we pass a certain point (i.e. there exists an X such that there are x^(1/3) of them below any x > X) so that makes us think it could be true! Worth seeing!
5. But what about this common-ness measure like the B-C result for primes? Well, it turns out that it exists. It ain't as pretty as just between straight integer multiples, but the fact that it exists in some shape at all is cool! That's what this kid proved. Absolutely rollicking fact. https://arxiv.org/abs/2111.06963 https://arxiv.org/abs/2111.06963
- vorticalbox 4y agoThanks for this. I find articles like this super hard to read due to the mixing of the topic and all the "back ground". It does sometimes feel like it's only there to bulk out the article.
- renewiltord 4y agoOne can hope that future AI autosummarizers can be aware of our personal level of knowledge!
- jbverschoor 4y agoLazy writers and/or who get paid per word. The writer can fix the article, or let every reader fix it in his mind.
- Ar-Curunir 4y agoMaybe just consider that the audience of the article is not you?
- SilasX 4y agoThe article is not for technically minded people who would like a lucid explanation of the math behind the result? Because they're pretty clearly trying to hit that target, and frequent interruption of that kind of exposition works against it...
- jbverschoor 4y agoIt could've easily been split up in different articles covering different aspects. It's not only lazy, but it doesn't account for what's going on in the world, where attention is super scarce.
- phkahler 4y agoBut from the article: >> In fact, Larsen’s argument didn’t just allow him to show that a Carmichael number must always appear between X and 2X. And yet the Wikipedia page says 2821 and 6601 are the 5th and 6th Carmichael numbers, which means there are not between 3000 and 6000 (X and 2X). So is his result actually that one must always exist between X and 2.5X or some other small multiple? If so, what multiple did he prove?
- bibanez 4y agoI only read the abstract and the result is in the same spirit but doesn't say exactky between X and 2X. It's between some more complicated expressions (using logs like usual in number theory)
- zeroonetwothree 4y agoThe bounds are tighter than n and 2n. So he actually proved a stronger result.
- renewiltord 4y agoAh I didn't mean to mislead that it was x and 2x. Corrected to be slightly clearer. The bound is easiest seen on the arxiv link above, in the abstract. The HN forum software doesn't do math very well.
- zeroonetwothree 4y agoIt’s true for x sufficiently large. So there will be some small counterexamples.
- jll29 4y agoBy the way, if you don't like reading bulky proprietary PDFs, there is a trick: substitute the x in arxiv.org by the digit 5, and you will see the paper rendered in HTML5, e.g.: https://ar5iv.labs.arxiv.org/html/1910.06709 https://ar5iv.labs.arxiv.org/html/1910.06709 (great work by FAU Erlangen's Michael Kohlhase and team).
- renewiltord 4y agoGood tip. I should have just linked the arxiv.org page for the article and not the PDF directly https://arxiv.org/abs/2111.06963 https://arxiv.org/abs/2111.06963
- sohkamyung 4y agoInteresting. Entering [ https://ar5iv.org/abs/2111.06963 https://ar5iv.org/abs/2111.06963 ] also gives me the HTML render of the paper. Saves one step, since I don't have to fetch the PDF first. :-)
- vitus 4y ago> It ain't as pretty as just between straight integer multiples, but the fact that it exists in some shape at all is cool! Actually: the form that Larsen proved is stronger than "for sufficiently large X, there is at least one Carmichael number between X and 2X". So with the more specific proof, he also proved the simpler statement that's easier to express.
- renewiltord 4y agoHaha very good!
- gnubison 4y agoWhat is the stronger version?
- renewiltord 4y agoBertrand's postulate is that there is at least one prime between x and 2x for x>=1 Daniel Larsen's result here is that there are e^((log x)/((log log x)^(2+d))) Carmichael numbers between x and (x + x/((log x)^(1/(2+d)))) for x>=X (depends on d) e^((log x)/((log log x)^(2+d))) is >= 1 for all x >= 1. (x + x/((log x)^(1/(2+d)))) <= 2x Stronger by being tighter than the (x,2x) bound and being more specific about the >= 1 number of Carmichael numbers
- gnubison 4y agoThank you!
- sagaro 4y agothanks for the really good and concise summary