[HN Gopher] Graduate Student's Side Project Proves Prime Number ...
___________________________________________________________________
Graduate Student's Side Project Proves Prime Number Conjecture
Author : theafh
Score : 351 points
Date : 2022-06-06 13:40 UTC (9 hours ago)
(HTM) web link (www.quantamagazine.org)
(TXT) w3m dump (www.quantamagazine.org)
| vishnugupta wrote:
| This 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
|
| [1] https://frontline.thehindu.com/other/article30245904.ece
| q-big wrote:
| > 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 wrote:
| Oops; 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 wrote:
| No, factoring being in P would not imply P == NP. Factoring
| is not NP-hard.
| Laakeri wrote:
| Well, 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.
| q-big wrote:
| > showing prime factorisation in P will imply P == NP
|
| Whether "Factorization is in P" actually implies "P=NP" is
| another open problem (most researchers in this area don't
| believe that this is the case).
|
| What does hold is that if we found a "fast" algorithm for
| factorization, this would break some cryptosystems. The
| most well-known example is RSA, but other, more academic
| cryptosystems would be broken, too.
|
| In its "Public key cryptography" template (https://en.wikip
| edia.org/wiki/Template:Cryptography_public-k... click
| "[show]"), Wikipedia lists the following cryptosystems to
| be dependent on the hardness of integer factorization:
| * Benaloh * Blum-Goldwasser * Cayley-Purser
| * Damgard-Jurik * GMR * Goldwasser-Micali
| * Naccache-Stern * Paillier * Rabin * RSA
| * Okamoto-Uchiyama * Schmidt-Samoa
| scrubs wrote:
| >>Erdos found that for any primitive set, including infinite
| ones, that sum -- the "Erdos sum" -- is always finite. No matter
| what a primitive set might look like, its Erdos 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.
| alanh wrote:
| Upvoting because this post shouldn't have a negative score
| simply for being confused. Treating it as a reasonable
| question.
| yunwal wrote:
| The 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 wrote:
| It 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 wrote:
| > "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).
|
| Erdos found that for any primitive set, including infinite
| ones, that sum -- the "Erdos sum" -- is always finite."
|
| Read the paragraph just above it.
| adenozine wrote:
| THIS ONE is definitely the worst HN title gore I've seen so far.
| Jesus, I nearly choked on my bagel.
| oh_my_goodness wrote:
| The title's fine.
| tomp wrote:
| What 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?!
| coliveira wrote:
| Of course there is at least one such multiple: 103 * 618.
| Twisol wrote:
| > Of course there is at least one such multiple: 103 * 618.
|
| 103 * 618 is divisible by 2, which is a prime strictly
| smaller than 103. Every multiple of 618 is divisible by 618,
| and so is _also_ divisible by anything that divides 618.
|
| A cousin comment clarifies that, for x * 618, we're
| interested in the divisors of x, not x * 618. The article,
| however, is at best ambiguous in its language; you'd have to
| interpret the term "multiple" as meaning the multiplier
| applied to the base number, not the result of said
| multiplication. The latter is what is usually understood.
| jwilk wrote:
| They make the same mistake earlier on:
|
| > And associated to the number 55 (5 x 11) would be all
| multiples of 55 whose smallest prime factor is 11 (therefore
| excluding all multiples of 2, 3, 5 and 7).
| [deleted]
| [deleted]
| kens wrote:
| The tan box in the article explains this set. The multiples are
| nx618 where the smallest prime factor of _n_ (not of nx618) is
| >=103 (if any). I.e. 618, 103x618, 107x618, 109x618, etc.
| tomp wrote:
| No, 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 wrote:
| > Did anyone figure out what they actually wanted to say?!
|
| Did you read the paper?
| thaumasiotes wrote:
| You 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 x 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 wrote:
| So, does he just get to walk away with a PhD for this?
| Olphs wrote:
| Well 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 wrote:
| I think he is implying that this is such an accomplishment
| that the rest of the process of getting a PhD should just be
| waived.
| t_mann wrote:
| In this specific case the guy has 16 other published papers
| already, so if he'd wanted to walk away with a PhD he
| probably could easily have done so already. That being
| said, I'd imagine that Oxford would be one of the places
| that could find a way to award a PhD for genuinely
| outstanding but unusually short work if that had been his
| only achievement and he'd asked for it. Seems like one of
| the few universities still run chiefly by academics, not
| administrators.
| tantalor wrote:
| That would defeat the purpose of the process.
| ryanianian wrote:
| > 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 wrote:
| How 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.
| pknomad wrote:
| I think there's a precedence for it too. I believe George
| Dantzig's doctoral advisor offered to accept the
| solutions to a homework set as a thesis since it solved
| major open statistical problems.
| anonymousisme wrote:
| For those who don't know, here's some background on
| Dantzig:
|
| "During his first year as a doctoral student at the
| University of California-Berkeley, Dantzig arrived late
| to the class of Jerzy Neyman, one of the great founders
| of modern statistics. On the blackboard were two problems
| that Dantzig assumed to be homework.
|
| "A few days later I apologized to Neyman for taking so
| long to do the homework--the problems seemed harder to do
| than usual," Dantzig once recalled. It turned out the
| conundrums, which Dantzig solved, were two famous
| unsolved problems in statistics."
|
| https://news.stanford.edu/news/2005/may25/dantzigobit-052
| 505...
| mjfl wrote:
| I can't even get my main project to work...
| phkahler wrote:
| >> 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 wrote:
| For 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.
| mg wrote:
| I 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
|
| 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
|
| But every once in a while, I still dream about the "complex
| divisor fractal" and what mysteries might be hidden inside of it.
| frogperson wrote:
| There are many visualizations of the primes in 2D and many are
| fascinating. I've always wondered what it would look like in 3d
| or 4d or higher. what if the primes were mapped on to some
| crazy topological shape? Is there some shape and dimension out
| there that produces a "perfect" pattern?
| coldtea wrote:
| > _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._
|
| There are several of visualizations of prime numbers, and they
| do, look beautiful.
|
| E.g.:
|
| https://jaketae.github.io/study/prime-spirals/
|
| https://www.cantorsparadise.com/unexpected-beauty-in-primes-...
|
| https://mathworld.wolfram.com/PrimeSpiral.html
| CapmCrackaWaka wrote:
| I 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_bet...
| mg wrote:
| There is a movie from 1998 called "pi" about a number
| theorist who got sucked into it:
|
| https://en.wikipedia.org/wiki/Pi_(film)
|
| I saw it a long time ago, but still vividly remember some of
| the scenes.
| CyborgCabbage wrote:
| Knew I remembered that spiral from somewhere
| https://www.youtube.com/watch?v=EK32jo7i5LQ
| hinkley wrote:
| This 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.
| mananaysiempre wrote:
| You have seen the Ulam spiral[1] from 1963, right? I don't know
| that it provides any actual insight into this stupenduously
| complicated[2] topic, but if you want something to draw about
| prime numbers that's probably the best-known option. Or see the
| story about "primons"[3] for a view that's less visual but no
| less tangible (given a certain kind of background at least).
|
| And yes, as you note, your CDF very much looks like a square
| grid after an inversion. That is to say: draw a square grid on
| a horizontal plane, lay down a ball on that plane, project the
| image onto the surface of the ball by straight rays through its
| topmost point (imagine a lightbulb there; see? "projection"),
| then take a parallel plane touching that same ball and project
| back onto it from the surface (now casting rays from the
| bottommost point).
|
| But if so, it's boring in that it should have little to do with
| prime numbers. Let me think about this. (The story of complex
| numbers and projective transformations is not boring, of
| course, it's quite pretty, just doesn't provide much of an
| insight into the primes; and, in turn, its connection to
| hyperbolic geometry, most widely known through Escher's
| drawings, is also quite wonderful, but removed even further
| from the original picture, so might not be necessary to
| understand it.)
|
| [1] https://en.wikipedia.org/wiki/Ulam_spiral
|
| [2] https://arxiv.org/abs/math/0210327
|
| [3] https://math.ucr.edu/home/baez/week199.html
| shaunxcode wrote:
| The thing I found was that if you start the spiral with a 0
| you get a similar pattern. Further if you layer each of the
| triangular sections you get a really cool pattern[0].
|
| [0] https://lh4.googleusercontent.com/proxy/Ls_8QQgRDf4oK6Fwl
| iJ7...
| noasaservice wrote:
| Hmm.. I keep looking at your first (
| https://www.gibney.org/images/size02/-1_-1_to_1_1.jpg ) image,
| and I swear it looks 3 dimensional positively curved space,
| with vertices intersecting in depth. Just that since it's a
| picture, its being compressed from 3d->2d.
|
| Even though the lines are curved, I'm parsing them as
| straight.. somehow. Perhaps this is the wrong projection, and
| maybe it needs to be mapped on a sphere using lat/lon/alt
| (parametric)? That would also explain the infinite border
| asymptotes, and going from 2d mercator->spherical would modify
| those.
| pilotneko wrote:
| Nice work. You might be interested in this visualization of the
| first million prime numbers from UMAP: https://umap-
| learn.readthedocs.io/en/latest/exploratory_anal...
| paxys wrote:
| Solves a prime number conjecture, not _the_ prime number
| conjecture
| (https://en.wikipedia.org/wiki/Goldbach%27s_conjecture).
| ouid wrote:
| typical Quanta though. I am pretty close to no longer clicking
| on their links.
| paulpauper wrote:
| if it was _the_ conjecture, it would be in the headline
| Melatonic wrote:
| At first this is what I thought was solved - still cool
| regardless though!
| [deleted]
| raverbashing wrote:
| It's the Erdos primitive set conjecture
| https://www.maths.ox.ac.uk/node/36408
| Sniffnoy wrote:
| I 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 wrote:
| Goldbach'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.
| alisonkisk wrote:
| Goldbach's Conjecture is not _the_ Prime Number Conjecture ,
| because there is no such thing. There are several prime number
| conjectures.
| deathgripsss wrote:
| When I initially read the headline I was stunned
| imranq wrote:
| Same. Especially the "side project" part
| t_mann wrote:
| Can 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?
| Victerius wrote:
| Link to Arxiv pre-print: https://arxiv.org/abs/2202.02384
| renewiltord wrote:
| > _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
| nabla9 wrote:
| > 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
|
| 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.pd...
| Donald Knuth further simplified it into one page
| https://www.cs.stanford.edu/~knuth/papers/huang.pdf
|
| These kind of proofs are very creative.
| zasdffaa wrote:
| I get creative, but comprehensibility eludes me. To some
| 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 wrote:
| the 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.
| zasdffaa wrote:
| How is the bitstring 'embedded' in the n-cube? It must be a
| linearisation from a 1-dimensional string to vertices of
| the n-dimensional object but...? What does 'embedded' even
| mean, mathematically.
|
| Edit: neighbouring vertices can't be collapsed to a 1-dim
| string such that each bit x in the string abuts bit y if x
| is a neighbouring vertex of y (neighbouring = 1 edge away).
| Works for 1 and 2 dim cubes (line and square) fails for 3.
| Maybe am missing something.
|
| 'incidence matrices' something is incident on something
| else? It occurs to me that in some sense the recursive
| matrices might represent the n-cube, each sub-matrix being
| an n-1 cube. If this is so it is starting to make a little
| sense.
|
| But that's not the point, which is, how are you seeing this
| so clearly? It's like a pea-souper over at my end.
|
| (https://en.wikipedia.org/wiki/Pea_soup_fog)
| thaumasiotes wrote:
| > Edit: neighbouring vertices can't be collapsed to a
| 1-dim string such that each bit x in the string abuts bit
| y if x is a neighbouring vertex of y (neighbouring = 1
| edge away). Works for 1 and 2 dim cubes (line and square)
| fails for 3. Maybe am missing something.
|
| It sounds like you're missing something. A 3-dimensional
| cube has 2^3 = 8 vertices: x y z
| 0 0 0 0 0 1 0 1 0 0
| 1 1 1 0 0 1 0 1 1 1
| 0 1 1 1
|
| Since there are three dimensions, each vertex has three
| neighbors. If you imagine the vertex at (0, 1, 1), you
| can travel across the x-dimension to the neighbor at (1,
| 1, 1), or across the y-dimension to the neighbor at (0,
| 0, 1), or across the z-dimension to the neighbor at (0,
| 1, 0). Obviously, you represent this by flipping the x-,
| y-, or z-bit in the corresponding bitstring
| representation. The bitstring representation itself is
| blindingly straightforward: the vertex at (0, 1, 1) has
| the representation 011, etc.
|
| It's not really clear to me where you're becoming
| confused?
|
| > What does 'embedded' even mean, mathematically.
|
| In this case, it means that a complex structure (the
| cube) includes a simpler structure (the collection of
| discrete bitstrings). You can analyze the bitstrings by
| themselves if you want to, or you can imagine them as
| being the vertices of a cube that may or may not have
| properties other than its vertices, but however you
| describe the cube, it will include the bitstrings.
| zasdffaa wrote:
| > It's not really clear to me where you're becoming
| confused?
|
| Got it. I was interpreting the bitstring as 1 bit mapped
| to each vertex of the cube, I so badly, utterly
| misinterpreted it (my string would be 2^n length, not
| n-length). A simple example and the intent here is
| totally clear. I guess the problem is at least partly I
| tend to read what I expect, not what's there. Sigh.
|
| > In this case, it means that a complex structure (the
| cube) includes....
|
| Righto, a model of interest, a *-morphism or bijection
| between the string-set and the cube (where * =
| iso/homo/auto/whatever, it's been a long time)
|
| Thanks for this.
| mwest217 wrote:
| It'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!
| paulpauper wrote:
| It 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.
___________________________________________________________________
(page generated 2022-06-06 23:00 UTC)