11 ms·
Graduate Student’s Side Project Proves Prime Number Conjecture
- renewiltord 4y ago> The conjecture deals with primitive sets — sequences in which no number divides any other. Since each prime number can only be divided by 1 and itself, the set of all prime numbers is one example of a primitive set. So is the set of all numbers that have exactly two or three or 100 prime factors. Minor clarification: exactly k prime factors, counted with multiplicity
- phkahler 4y ago>> In 2019, he and Carl Pomerance, his adviser at Dartmouth — who, according to Lola Thompson, a mathematician at Utrecht University and a former student of Pomerance, essentially “came out of retirement to work with him” Somehow that made this whole story a lot more human to me. Pomerance is a big name in modern number theory (to me anyway) but apparently at the end of the day he's just another guy with a particular set of interests who will pop up again when the right thing comes his way.
- ashton314 4y agoFor those who don't know, Carl Pomerance was the guy who came up with/discovered the quadratic field sieve which for a time was the fastest factoring algorithm for large (100-ish digits) semiprimes. He has a beautiful write-up describing the algorithm and the story of its discovery: Pomerance, Carl. “A Tale of Two Sieves.” In Biscuits of Number Theory, edited by Arthur Benjamin and Ezra Brown, 85–104. Providence, Rhode Island: American Mathematical Society, 2009. https://doi.org/10.1090/dol/034/15 https://doi.org/10.1090/dol/034/15.
- phkahler 4y agoTo this day the question I have about the Quadratic Seive is something like "what is being reduced in degrees of freedom by each relation added to the matrix?" It seems like the sequence of primes in the factor base (which are quadratic residues) is very much related to the residues of the factors (they are) and somehow this it's doing in the abstract something like CRT to construct the factors. But I have never read a deeper explanation beyond the mechanics of implementation.
- scrubs 4y ago>>Erdős found that for any primitive set, including infinite ones, that sum — the “Erdős sum” — is always finite. No matter what a primitive set might look like, its Erdős sum will always be less than or equal to some number. And so while that sum “looks, at least on the face of it, completely alien and vague,” Lichtman said, it’s in some ways “controlling some of the chaos of primitive sets,” making it the right measuring stick to use. Finite? Surely there must be an operation done to each element of the set before summing to achieve a finite bound.
- yunwal 4y agoThe paragraph directly before the one you quoted explains the sum: > For every number n in the set, plug it into the expression 1/(n log n), then add up all the results. The size of the set {2, 3, 55}, for instance, becomes 1/(2 log 2) + 1/(3 log 3) + 1/(55 log 55).
- S4M 4y agoIt said that the quantity sum(1/(n log n) for n in A) is always finite when A is a primitive set. The "operation done to each element of the set" is n -> 1 / (n log n).
- Enginerrrd 4y ago> "For example, rather than counting how many numbers are in a set, they might do the following: For every number n in the set, plug it into the expression 1/(n log n), then add up all the results. The size of the set {2, 3, 55}, for instance, becomes 1/(2 log 2) + 1/(3 log 3) + 1/(55 log 55). Erdős found that for any primitive set, including infinite ones, that sum — the “Erdős sum” — is always finite." Read the paragraph just above it.
- alanh 4y agoUpvoting because this post shouldn't have a negative score simply for being confused. Treating it as a reasonable question.
- tomp 4y agoWhat a crap article. > Typically, you might associate to it all multiples of 618 whose smallest prime factor is 103. There are no multiples like that. All multiples of 618 (= 2 * 3 * 103) have 2as the smallest prime factor. Did anyone figure out what they actually wanted to say?!
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- kens 4y agoThe tan box in the article explains this set. The multiples are n×618 where the smallest prime factor of n (not of n×618) is ≥103 (if any). I.e. 618, 103×618, 107×618, 109×618, etc.
- tomp 4y agoNo, the tan box is similarly non-sensical and the example is 3 primes so it doesn’t explain it either. Your explanation is clear though, thanks!
- williamscales 4y ago> Did anyone figure out what they actually wanted to say?! Did you read the paper?
- Ensorceled 4y agoNo, I tried to read the article.
- thaumasiotes 4y agoYou would generally hope that the popular coverage of the paper would (1) avoid making statements that are obviously nonsense, such as "And associated to the number 55 (5 × 11) would be all multiples of 55 whose smallest prime factor is 11"; and (2) not require reading the paper itself in order to interpret the popular coverage. If you're going to read the paper, why would you read someone else's paper-inspired gibberish? What value does that add?
- ashton314 4y agoSo, does he just get to walk away with a PhD for this?
- Olphs 4y agoWell he worked on it for 4 years (for fun?), so I'm not sure what you mean by walk away with a PhD. To me it seems like he has earned it, and even if he doesn't get one he obviously is able to
- scrumbledober 4y agoI think he is implying that this is such an accomplishment that the rest of the process of getting a PhD should just be waived.
- tantalor 4y agoThat would defeat the purpose of the process.
- ryanianian 4y ago> That would defeat the purpose of the process. On the contrary, this is the exception that proves the rule. The process exists because we can't expect once-in-a-lifetime works to appear from every candidate.
- alisonkisk 4y agoHow so? The "process" of getting PhD is writing up his proof and getting it reviewed by the university, and verifying via oral defense that he knows the proof and didn't just plagiarize it.
- adgjlsfhk1 4y agoIt's pretty obvious when someone discovers a proof to a famous problem that it's not plagiarized because no one has proved it before.
- paxys 4y agoSolves a prime number conjecture, not the prime number conjecture (https://en.wikipedia.org/wiki/Goldbach%27s_conjecture https://en.wikipedia.org/wiki/Goldbach%27s_conjecture).
- deathgripsss 4y agoWhen I initially read the headline I was stunned
- imranq 4y agoSame. Especially the "side project" part
- Melatonic 4y agoAt first this is what I thought was solved - still cool regardless though!
- deleted 4y ago[deleted]
- Sniffnoy 4y agoI mean, there isn't anything known as "the prime number conjecture". Goldbach's conjecture is a prominent conjecture about primes, but it's not "the prime number conjecture".
- paxys 4y agoGoldbach's conjecture is possibly the most famous unsolved problem in mathematics. When people refer to prime number conjecture, this is the most obvious one everyone's thoughts will go to.
- SAI_Peregrinus 4y agoI'd say the Riemann hypothesis is more famous. Goldbach's conjecture didn't make the Milennium Prize Problems list, and Perleman's refusal of the award for his proof of the Poincaré conjecture popularized that list quite widely.
- Victerius 4y agoLink to Arxiv pre-print: https://arxiv.org/abs/2202.02384 https://arxiv.org/abs/2202.02384
- mwest217 4y agoIt's always fun to see one of these articles pop up about someone I know - I knew Jared from the ultimate frisbee team at Dartmouth!
- nabla9 4y ago> Mathematicians noted that the work is particularly striking because it relies entirely on elementary arguments. “It wasn’t like he was waiting for all this crazy machinery to develop,” Thompson said. “He just had some really clever ideas.” the proof: https://arxiv.org/pdf/2202.02384.pdf https://arxiv.org/pdf/2202.02384.pdf Last time I saw something so simple that I think I could understand the idea because it has not too many new concepts was Hao Huang Sensitivity Conjecture: http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pd... Donald Knuth further simplified it into one page https://www.cs.stanford.edu/~knuth/papers/huang.pdf https://www.cs.stanford.edu/~knuth/papers/huang.pdf These kind of proofs are very creative.
- zasdffaa 4y agoI get creative, but comprehensibility eludes me. To some https://www.cs.stanford.edu/~knuth/papers/huang.pdf https://www.cs.stanford.edu/~knuth/papers/huang.pdf may be obvious in its statements and steps and I guess that, aside from having the necessary background in this area, they fundamentally differ from me in how they 'see' this. They the underlying meaning, to me it's a jungle. Take the statement of the problem ??? ??? ? ?? ? ??? / ? ???????? ?? ??? ????? ? ???????? ? ?????? ???? ?? ????? ? ? ?????? ??? ?? ? ok, so you can't C&P from that PDF :) by hand then: "Any set H of 2^(n-1) + 1 vertices of the n-cube contains a vertex with at least sqrt(n) neighbors in H" Nothing in that makes intuitive sense to me except vertices will have neighbouring vertices. It's not even dimension limited and I can just about manage 4 dimensions at a push. Next, a bunch of recursively defined 2x2 matrices with no apparent link to anything. I'm lost twice now. Yet to a Knuth or a Von Neumann, it just makes sense. This stuff makes me feel like a different species. Just a reflection on things. Professional mathematicians in-chimings welcome.
- ouid 4y agothe combinatorial object "the n-cube" is just length n bitstrings, neighbor means one bit flip away. It can be thought of as being embedded in the geometric n cube. the recursive matrices as they are defined are, if you ignore the signs, the incidence matrices of the n cubes. This is only mentioned in the final line of the paper (which is not totally unreasonable). The rest of the result is just some pretty basic facts in linear algebra, but you still have to be comfortable with linear algebra in order to see why they might be natural constructions.
- adenozine 4y agoTHIS ONE is definitely the worst HN title gore I’ve seen so far. Jesus, I nearly choked on my bagel.
- oh_my_goodness 4y agoThe title's fine.
- paulpauper 4y agoIt shows how there are two types of mathematics; research-level math in which important stuff is proved, and then teaching/pedagogical math, which doesn't get as much attention. I don't think teachers, authors get enough credit. There are also a huge differences in individual ability eve between math PHDs and profs. This may see obvious but the differences can be huge.
- mg 4y agoI like to put things on x/y-charts to get a visual overview. Even things that usually are not displayed in this fashion. When it comes to prime numbers, it always irked me, that one cannot easily look at them in a visual way. I always thought that they would probably look beautiful. One day, I had the idea to counter this by visualizing prime numbers in the complex plane. I then wrote a little script to colorize each number in the complex plane by how "prime" it is. And indeed, the result looks beautiful: https://www.gibney.org/does_anybody_know_this_fractal https://www.gibney.org/does_anybody_know_this_fractal Then I went back to do more mundane things with x/y charts. The one that became most popular is Product Chart: https://www.productchart.com https://www.productchart.com But every once in a while, I still dream about the "complex divisor fractal" and what mysteries might be hidden inside of it.
- CapmCrackaWaka 4y agoI have seen many “plots” of prime numbers that look really good. In addition to looking good, I sometimes _swear_ I see a pattern. It’s really frustrating, to see something on a graph which looks like it follows some pattern or algorithm[1], and to know that finding the mathematical definition of that pattern would would be revolutionary, world news. I can see why so many people get sucked into this problem. [1] https://www.reddit.com/r/math/comments/7v02i6/comparison_between_5000_and_50000_prime_numbers/ https://www.reddit.com/r/math/comments/7v02i6/comparison_bet...
- CyborgCabbage 4y agoKnew I remembered that spiral from somewhere https://www.youtube.com/watch?v=EK32jo7i5LQ https://www.youtube.com/watch?v=EK32jo7i5LQ
- hinkley 4y agoThis is a very good video. The tl;dr on it is that all primes are of the pattern 3n±1, and 2𝞹 (polar coordinates) is .283 mod 3, hence the primary curve. Then he explains about fractions that approximate pi, but I think he's over-explaining. Reducing a fraction means making the denominator and numerator co-prime, and in the case of pi approximations, the interesting ones all have prime numbers as the denominator, so the 3n±1 pattern appears again.
- vishnugupta 4y agoThis brings back memories to me. Almost exactly 2 decades ago a related theorem, prime factorisation being in P, was proved by a couple of undergrads working with a professor in IIT Kanpur, India [1]. The story and the sensation it caused is still fresh in my memory because I had just begun my post-graduation studies in another IIT (IIT Bombay). There was sort of a festival atmosphere in the campus; with all sorts of seminars arranged, discussion groups and what not. To this day I have not tried to understand the paper; just that it was hailed as one of the shortest and most elegant proofs. [1] https://frontline.thehindu.com/other/article30245904.ece https://frontline.thehindu.com/other/article30245904.ece [1] https://frontline.thehindu.com/other/article30245904.ece https://frontline.thehindu.com/other/article30245904.ece
- q-big 4y ago> Almost exactly 2 decades ago a related theorem, prime factorisation being in P, was proved by a couple of undergrads working with a professor in IIT Kanpur, India It is still an open problem whether prime factorization is in P or not. What Manindra Agrawal, Neeraj Kayal and Nitin Saxena showed is that checking whether a given (binary) number is prime is in P. Up to today, no polynomial-time method has been published to obtain a non-trivial factor of the input if the AKS algorithm returns that it is not prime.
- vishnugupta 4y agoOops; you are right. If my memory serves right, showing prime factorisation in P will imply P == NP; which would have been a sensational news at a different level altogether.
- Ar-Curunir 4y agoNo, factoring being in P would not imply P == NP. Factoring is not NP-hard.
- Laakeri 4y agoWell, it is also not proved to not be NP-hard, so it could also be NP-hard to our current knowledge. But you are right that researchers believe that it's not NP-hard.
- mjfl 4y agoI can’t even get my main project to work…
- pabzu 4y agothis guy raise procrastination to a whole new level
- t_mann 4y agoCan we also talk about how this guy is in the third year of his PhD and has no less than 18 papers listed under "major/recent publications", all but two of which are published, and one of the latter 'shocked' the math community?
- ramraj07 4y agoSeems to not be surprising? Prodigies be prodigies, like him and T.Tao, while the rest of us compete out our own mostly insignificant games..
- joppy 4y agoT.Tao's first publication (at least the first one that shows up on MathSciNet) was in 1996, the same year he finished his mathematics PhD. I would say for most people working towards the pure side of mathematics, having over 5 papers before the end of a PhD is not at all typical.
- lupire 4y agoTerence Tao finished his PhD at age 21. So he both didn't publish major work before PhD, but did publish major work at a young age. Most math PhDs including OP topic Lichtman would start after age 20 and finish at age 24-28. So Lichtman might be on a similar trajectory as Tao, but not accelerated through formal schooling. And since Lichtman's work is in elementary number theory (similar to combinatorics, one of Tao's main subjects), it's more accessible to early results from a brilliant person with less experience. Other subjects require more background study before reaching new territory. People on this thread say that in recent years there has been a lot of pressure for math researchers to publish far more often partial / lower quality work to match the publication rate of other fields. https://academia.stackexchange.com/questions/48399/how-many-papers-should-a-phd-student-in-math-try-to-publish-before-graduating https://academia.stackexchange.com/questions/48399/how-many-...
- bentoner 4y agoIt’s very surprising. How many papers do you think Terence Tao had published by the third year of his PhD?
- rob_c 4y agoFor anyone who speaks maths https://arxiv.org/abs/2202.02384 https://arxiv.org/abs/2202.02384 Unfortunately without a maths UG it's a hard slog I'll agree, but not the most impenetrable paper over ever seen. Not going to pretend I get the subtleties though.
- lotaezenwa 4y agoJared is doing great things! Got a chance to work with him in undergrad. Well deserved.
- dragon96 4y agoFor anyone interested in a more technical summary of the some of the main ideas: Problem Statement The Erdos conjecture that all primitive sets S satisfy f(S) <= f(PRIMES), where f(S) = sum_{s} (1/(s log s)) and PRIMES is the set of all primes. Definitions Define A_q to be a primitive set such that all elements a are divisible by prime q, but no primes less than q. * Example: A_3 contains multiples of 3, but no even numbers. Define A*_q to be the set of all integers divisible by only primes >= q. * Example: A_q is a subset of A*_q. * Example: A_q is also a subset of q \* A*_q (i.e. multiply each element by q). Define g(a) = 1/a * Product_{p<LargestPrimeDivisor(a)}[(1 - 1/p)]. * Example: if a=7, then the Product term (excluding the 1/a) is the "density" of A*_7. This is because (1-1/2) of integers aren't divisible by 2, (1-1/3) aren't divisible by 3, and (1-1/5) aren't divisible by 5. * Example: if a=7, then g(7) is the density of all multiples of 7 that aren't divisible by 2,3,5. Results In [1], Author proves that for all A_q, with A_q \neq {q}: f(A_q) < k*\sum_{a\in A_q} g(a) <= k*g(q), for a constant k. * The first half of the inequality comes from a cited result: 1/(a log(2a)) < k*g(a). * The second half of the inequality comes from clever construction of the sets S_a = (a \* A*_{LargestPrimeDivisor(a)}), for all a in A_q. These sets are constructed to satisfy g(a) = |S_a|/|NaturalNumbers|. So because (1) S_a and S_b are disjoint for a\neq b (2) S_a is a subset of A*_q, this implies that sum(g(a)) = sum(|S_a|) <= sum(|A*_q|) = g(q). In [2], Author shows that k\*g(q) <= 1/(q log q). Note that the right-hand side of the inequality is equal to f({q}). * This uses a pretty clever partitioning of the primitive set A into A_2 U A_3 U A_5 U ... U A_q U .... Combining with part 1, this implies f(A_q) < f({q}) for all primes q, so f(A) < f(PRIMES). [1] https://arxiv.org/pdf/1806.02250.pdf https://arxiv.org/pdf/1806.02250.pdf [2] https://arxiv.org/pdf/2202.02384.pdf https://arxiv.org/pdf/2202.02384.pdf
- dschuetz 4y agoWhy is it always a shock? Because he's just a graduate student with too much time?
- kaba0 4y agoBecause it is was a long-standing conjecture. Also, from the article: Mathematicians noted that the work is particularly striking because it relies entirely on elementary arguments. “It wasn’t like he was waiting for all this crazy machinery to develop,” Thompson said. “He just had some really clever ideas.” I also hate click-bait titles, but I think it is aptly fitting for a change.
- jb1991 4y agoI wonder how the conjecture originally came up with 1.64 anyway, seems like a rather arbitrary number to establish a conjecture that takes decades to prove. If there was some way to actually come up with that number initially, wouldn’t that itself have been on the way to a proof?