Graduate Student’s Side Project Proves Prime Number Conjecture
quantamagazine.org
quantamagazine.org
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:
But every once in a while, I still dream about the "complex divisor fractal" and what mysteries might be hidden inside of it.
[1] https://www.reddit.com/r/math/comments/7v02i6/comparison_bet...
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.
https://en.wikipedia.org/wiki/Pi_(film)
I saw it a long time ago, but still vividly remember some of the scenes.
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
[0] https://lh4.googleusercontent.com/proxy/Ls_8QQgRDf4oK6FwliJ7...
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.
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-...
This is easy: consider the spectrum of the ring Z, Spec Z (by definition, the spectrum of a commutative ring consists of its prime ideals; all prime ideals of Z (with the exception of the zero ideal) are generated by the prime numbers; in this sense, we can identify all elements of Spec Z (with the exception of the zero ideal, which is "just another point" of Spec Z) with the prime numbers if we desire).
On Spec Z, we can define a topology, the Zariski topology, by defining
V(I) := {P \in Spec Z | I \subseteq P},
where I is an ideal of Z, as the closed sets of the Zariski topology.
See
* https://en.wikipedia.org/w/index.php?title=Zariski_topology&...
* https://en.wikipedia.org/w/index.php?title=Spectrum_of_a_rin...
for details.
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.
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.
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.
And there is a need for many "normal" people to contribute to research in the field too, because a solid part of the equation is sheer man hours. I get being jaded, and I also don't know what field you were in, but regardless I think it's a bit too pessimistic to assume that only prodigies can meaningfully contribute to research.
In other more practical fields, less,-inspired research is useful, and also research is slower due to real world complexity and expense, not inherent intellectual difficulty. Like plowing through all possible chemical rejection looking for one that works, or fine tuning a radio in engineering, or a NN or a big program in CS, or running psych / sociology surveys.
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-...
One of my favorite stories about Maynard is in another one of Quanta's articles, concerning prime number gaps [1]. Yitang Zhang had just established an upper bound of 70 million for prime number gaps. After that, Terence Tao assembled a crowd of mathematicians to try and refine Zhang's method, and over the summer, they incrementally lowered the bound all the way down to 4680. Then Maynard, who had been working solo on developing an entirely different method, came out of the blue and lowered the bound to 600.
I still find the crowd-sourced "Polymath" approach incredibly cool, and Terence Tao himself discusses the benefits of open collaboration and the dangers of working solo [1]. Though clearly, James Maynard does just fine on his own.
[1]: https://www.quantamagazine.org/mathematicians-team-up-on-twi...
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
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.
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.wikipedia.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
* Damgård–Jurik
* GMR
* Goldwasser–Micali
* Naccache–Stern
* Paillier
* Rabin
* RSA
* Okamoto–Uchiyama
* Schmidt–SamoaWow this confused the hell out of me because I thought, isn't the sieve of eratosthenes already below polynomial time? But from what I read, while the sieve of eratosthenes is sub-polynomial relative to the magnitude of the input, the AKS method is polynomial time relative to the length of the input in binary representation (aka the number of binary digits).
But people forget that natural numbers are just data, and that data can be interpreted at a a natural number.
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.
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.
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).
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.
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.
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.
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.
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
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.
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.
Finite? Surely there must be an operation done to each element of the set before summing to achieve a finite bound.
> 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.
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.
"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-052505...
Minor clarification: exactly k prime factors, counted with multiplicity
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.
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.
> 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?!
Your explanation is clear though, thanks!
Did you read the paper?
(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?
> And associated to the number 55 (5 × 11) would be all multiples of 55 whose smallest prime factor is 11 (therefore excluding all multiples of 2, 3, 5 and 7).
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.