Mathematicians uncover a new way to count prime numbers
quantamagazine.org
quantamagazine.org
Does it? For any number a, a^2 = a (mod 2), and primes greater than 2 are all odd, so if a prime p = a^2 + b^2, doesn't one of a or b have to be odd? Reducing mod 2, p = 1 (mod 2), a^2 + b^2 = 1 (mod 2), a + b = 1 (mod 2), so either a = 0 (mod 2) and b = 1 (mod 2) or vice-versa?
edit:
If Euler proved infinitely many such primes exist then "With this in hand, Green and Sawhney proved Friedlander and Iwaniec’s conjecture: There are infinitely many primes that can be written as p^2 + 4q^2." makes no sense without a further condition of p or q, let (in my notation) a=p be odd and b=2q be even.
Now having finished the article, I think this was just sloppy writing, and the actual accomplishment is related to the post-perhaps clause: one of p or q has to itself be a perfect square? Anyway, I have very little certainty about what was actually accomplished from reading this article.
https://renaissancephilanthropy.org/news-and-insights/renais...
> Proposals should be aligned with one of the following categories:
> Production grade software tools: AI for auto-formalization, proof generation, synthesis of verifiable code, and more
> Datasets: Open-source collections of theorems, proofs, and math problems Field building: Textbooks, courses, and resources to grow the AI-for-math community
> Breakthrough ideas: High-risk, high-reward approaches to AI-driven math research
I wonder how true this statement is but it probably also relies on the understanding of the word 'random'. In the colloquial sense, it is certainly true in the sense that (truly) 'random' means 'occurring without (discernible) rules'.
However, in a stricter definition 'random' means (if I'm not mistaken, hobby-thinker here) just "a given set of numbers S is called random with respect to a set of binary tests T when all individual procedures in T yield a positive outcome". That is, you can only ever a finite set S and test against a finite set T, meaning the algorithm that generated your random-looking set S can, potentially, always be amended to creep closer to overcome the failed tests (and the reverse is also true: one can, potentially, always move the goalposts and add another test to T to make a set fail that used to pass).
Ultimately, then, randomness—where it is not occurring eo ipso as in radioactive decay—is always a relative (S WRT T), social (people must agree), and finite (can't test against unseen members of S and, per precondition, can't give a rule to cover infinity as in 'divisible by eleven') procedure (that may or may not practically terminate). In other words, once we settle on a given set of tests T to determine what is random, one can (potentially) always come up with an algorithm that passes the tests, thus looks random though it is determined.
So that sounds pretty random to me, yet there are algorithms that give you π in its decimal form, and as far as I can remember there are even ways to compute the n-th digit of π without having to compute the preceding ones—which sounds pretty determined to me.
Concisely:
http://mrob.com/pub/math/numbers.html
The rest of the site it's amazing too.
More importantly, how does Szemeredi theorem fit in here?
Green and Sawhney’s work is especially exciting because it shows how tools from one field—Gowers norms—can unlock progress in another. That kind of cross-disciplinary insight is where breakthroughs happen. And yeah, it’s fair to question funding priorities, but basic research has given us antibiotics, GPS, and even computers. Without it, we’d still be in caves.
In this article, neither is informative.
And even after several paragraphs in, you don't know what the general area of the proof is. Just meandering long-winded story-telling.
If anyone of you authors/editors of this magazine are here; please, for the love of all that's holly, put the crux of the matter at the top and then go off to tell your beautiful, humanized, whatever... story.
Nowadays we are wondering if LLM are going to be the next prime numbers. The question is if solving the language problem is going to provide us the key for solving the AGI problem. We still don't know what is the equivalent of a prime for a LLM, that is the smaller independent part that allow it to express some knowledge, the pieces could be embeddings or the topology of the layers or some new insight.
Some more random ideas, just like Norvig see python as a more practical Lisp, the basic ideas from prime numbers impregnate a great part of mathematics. You can be really far from the root but the principles are always with you, primes are a second nature, you have internalized all their properties and dynamically you learn to see primes like features in many fields (prime ideals, spectrum of a ring, points in commutative algebra).
The problem of how many primes (in relation to positive integers) is like wondering whether a given decomposition exists in a general sense that could allow us to solve the general problem. So few primes implies that the theory could solve some kind of problems but not many. What are LLMs number?, that is the question if solving the language problem will allow us to solve some very general problems, like a good approximation to AGI. The problem of whether LLMS will open the way to AGI could be the next Riemann hypothesis once we succeed in defining what is a prime number in relation to a LLM.
We are trying to prove escalating laws for how LLM improve when increasing the number of parameters, this is like trying to guess the convergence of an infinite serie by using a finite sum. The analogous of a Riemann hypothesis could be defining certain kind of LLM and conjecturing if it could obtain AGI pass some threshold for the number of parameters.
Edited: Sorry for being overly verbose this mornig!
A (reupped) comic (in german) maybe if you like (I think they don't like hotlinkng): https://i.ibb.co/s9vYHHk/GAAAAANZ-ANDERS-24-FINAL-Mail.png
regards...
Stunning to me that a staff writer for a science magazine would type this sentence without referencing the riemann hypothesis.
P(X = p > 0),
that is, the probability that X = p is positive.
So, with X, the prime numbers are random.
References:
With TeX markup, polished details on measure theory are in
H.\ L.\ Royden, {\it Real Analysis: Second Edition,\/} Macmillan, New York, 1971.\ \
Walter Rudin, {\it Real and Complex Analysis,\/} ISBN 07-054232-5, McGraw-Hill, New York, 1966.\ \
and polished details on probability theory based on measure theory are in
Leo Breiman, {\it Probability,\/} ISBN 0-89871-296-3, SIAM, Philadelphia, 1992.\ \
Jacques Neveu, {\it Mathematical Foundations of the Calculus of Probability,\/} Holden-Day, San Francisco, 1965.\ \
Sam, just a minute. Let me draw a sample. Got one: X = 7.
But, Joe 7 is not very surprising or interesting. Is there anything else?
Sam, sure, one more minute. Got one!
Joe, well, then, WHAT is it????
Sam, sorry, it has 2^12345 digits and will take a while to print it out; this morning I have a coffee shop meeting with Susan; and I don't want to miss Susan, cute, pretty, sweet, smart, darling, adorable, precious ..., and single!
Exercise: Show that there is a random variable Y with the same distribution as X and such that X and Y are independent random variables. I.e., knowledge of X tells us nothing about Y.
The intuitive concept of random is closer to unpredictable given even everything else, that is, what probability theory defines as independent.
There are more details in Royden, Rudin, Breiman, and Neveu. To preview, there is a non-empty set Omega with a collection F of subsets that form a sigma algebra and a measure P on F. Then random variable X is a measurable function from Omega to the set of all prime numbers. So, for some point w in Omega and function X, X(w) is a prime number. Can think of w as a trial.
Uh, this morning I'm working on some Rexx code, so here I can't reproduce or compete with the references by Royden, Rudin, Breiman, and Neveu.
Replace
P(X = p > 0)
with
P(X = p) > 0
I’m curious what this does, cause it seemingly changes nothing (tested on mobile, with “desktop version” too).
Most just mean related Riemann's explicit formula for prime when they link Riemann hypothesis and prime number.
> But of course, the primes aren’t random. They’re completely determined,
Also this whole thread that this post started is so stupid.
Is it that the methods required to do serious research on them ends up helping us discover other things?
Is there some deeper truth about the universe hidden in the prime numbers?
Investigating primes is nearly as old as mathematics itself and its reasonable to assume other ideas where discovered in the hopes of applying them to various problems incorporating prime numbers.
From a practical, applied, perspective, “understanding” primes, that is making their “hidden” structure a known “truth”, would either confirm or deny the Riemann hypothesis wherein many other conjectures that assume the hypothesis to be true would also be “truely” known.
Or from TFA:
> …In the 19th century, research on these kinds of statements led to the development of much of modern number theory. In the 20th century, it helped inspire one of the most ambitious mathematical efforts to date, the Langlands program. And in the 21st, work on these sorts of primes has continued to yield new techniques and insights.
> …Their[the article’s sunbjects’] proof, which was posted online (opens a new tab) in October, doesn’t just sharpen mathematicians’ understanding of the primes. It also makes use of a set of tools from a very different area of mathematics, suggesting that those tools are far more powerful than mathematicians imagined, and potentially ripe for applications elsewhere.
Something about it I find humbling and makes me think about the archetype of mathematicians that lose their minds to numbers.
1. Newton and the Bernoulli family developing the theory of infinite series and connecting them to discrete sequences,
2. Wallis developing the first notions of infinite products and demonstrating the first non-trivial convergence of such,
3. Euler solving the Basel problem and linking the zeta function to the prime numbers (giving a new proof of the infinitude of primes),
4. Gauss and Eisenstein further using Euler's ideas and their own unique algebraic insights to understand primes in arithmetic progressions, and finally
5. Riemann taking the zeta function, putting it in the complex plane, revealing the unifying theme connecting the previous discoveries and making his own fundamentally new discoveries with the explicit formula.
And of course the development only accelerated from that point on.
It’s much like physics and the great physics experiments throughout history for me, some of them I’d like to think I may have been able to develop, but others I just marvel at the ingeniousness of the experiments.
Realistically in a vacuum I doubt I’d have even identified/defined prime numbers.
There is no master plan; nobody allocates people to these problems based on strategic need. It’s just interesting.
Sometimes it's right to drag those intuitive feelings into the light and force them to explain themselves, and come up with some clue about in what way futzing around with (for instance) prime numbers might contribute to all the rest of the sprawling web of things we generally value in life. But enthusiasm is a precious and wholesome thing, so people rarely question it.
Many people are completely comfortable pursuing interests without needing or wanting a logical framework to explain/justify.
I enjoy cooking, in the sense that I study and try to understand and improve at a technical level. I probably could come up with a rationale for why, but I suspect it would be post hoc reasoning, so why bother?
(Not to say that the study of prime numbers isn't hugely important to most of cryptography)
The theory of finite fields is based on the theory of prime numbers, because the finite fields are sets of residues modulo a prime number or modulo a power of a prime number.
The theory of finite fields is involved in the design of many other block cipher functions or secure hash functions and also in the design of the most important message-authentication methods, like GCM, which is used to authenticate this HTML page on the HN site.
So prime numbers are important in most cryptographic applications, not only in asymmetric cryptography, like Diffie-Hellman or RSA. Prime numbers are used in one way or another for the transmission of any HTTPS data packet, not only in the key establishment phase of a TLS connection.
It is note quite correct that the finite field of order p^k is the set of residues modulo p^k when k > 1. Instead this field is obtained as a splitting field of the field of order p (which is the set of residues mod p).
There exists absolutely no method of secure communication that does not depend on a piece of information that is transmitted separately, through a presumed trustworthy courier. All the existing methods only attempt to minimize the amount of information that must be sent through the secure courier.
With symmetric crypto without digital signatures but with some kind of Diffie-Hellman, you must send by courier only a pre-shared key that is used only for computing message-authentication codes that are used only in the couple of packets used in a key-exchange algorithm, when establishing a secure connection.
Using only symmetric crypto, secure communication can be performed in pretty much the same way as with asymmetric crypto, by generating fresh random session keys for every connection.
The only difference is that the key exchange packets are authenticated with a MAC using a pre-shared key, instead of being authenticated with digital signatures and a chain of certificates going to trusted root certificates.
If for some weird reason one would not want to use a Diffie-Hellman variant (e.g. with elliptic curves) to protect the session keys, one could use another pre-shared key only for encrypting the key-exchange packets.
There are only two advantages for asymmetric crypto, when used for secure communication connections.
The first is provided by Diffie-Hellman in any of its variants, which ensures perfect forward secrecy, i.e. even knowing all the content of some sessions, including their secret keys, that does not allow the decryption of other sessions. Without Diffie-Hellman, if the pre-shared encryption key that is used to protect the key exchange packets is captured, all recorded sessions could be decrypted. This can be only partially avoided by changing that key frequently, which would prevent the decryption of past sessions, but not the decryption of future sessions.
The second advantage is provided by the authentication of the key exchange with digital signatures instead of MACs based on pre-shared keys, which is the possibility of half authentication, where the server is authenticated based on the certificates provided by it, but the client is not authenticated, which is the most frequent kind of secure communication used on the Internet.
For communication inside a closed environment, i.e. a private network, using key exchange authentication based on pre-shared keys (but with elliptic-curve Diffie-Hellman for protecting the session keys) can be simpler, faster and more secure than using digital signatures and certificates.
While in the beginning I have used your metaphor about sending a pre-shared key or the root certificates by courier, the normal mode of transferring pre-shared authentication keys is by initial physical pairing (e.g. cable connection) of the devices that must be able of communicating securely between themselves.
What have the technologically capable people who were the ones architecting these systems the past few decades given the world: a handful of Big Tech behemoths, with all the terrifically negative, stultifying effects that has had. The computing world has been willfully fragmented, and the landscape is awash with casualties; namely, every person out there who is terrified of their computing devices, who panics when the first pop-up screen appears.
Which is surely the minority on here, but in the big bad world, I would guess it's easily a majority of people.
And then the computer types have the gall to ask what number theory has done for humanity..!
The following should go without saying, but let's say it anyway: just because tech-y startups continue to attract historic levels of investment, doesn't necessarily mean that the stuff the tech world produces is in anyway useful or special or good or interesting. If you're not going to read a book or something on the topic (number theory), at least browse a couple of wikipedia articles, or get an LLM to summarise it for you, or something.
[0] I'm guessing this entirely from the tone and the forum we're on. Please tell me if I'm guessing incorrectly!
I don't want to come off as anti-pig here, pigs are OK. Number theory is OK too, it's probably the branch of mathematics I dislike least. But it's laudable to sometimes ask "what is it all for?", without wanting to attack or threaten anybody's occupation. No easy answer is available, but it's worth asking.
Beyond "expanding our knowledge about 'x'", a lot of disciplines don't have much of an answer, so I don't see the value in asking the question apart from trying to dismiss the relevant discipline.
So many of our technological advances have relied on chance discoveries (e.g. penicillin), so we can't predict ahead of time what the end uses are going to be. This is especially the case with maths as it is so abstract, but where would we be without Boolean logic, public key cryptography, information theory etc.?
> .. trying to dismiss the relevant discipline
Yeah. The question is worth asking yourself, your teachers, colleagues, and your friends.. but usually not worth asking (or answering!) strangers on the internet.
This type of “but what is it all for!” question has a huge asymmetry where it’s easy to ask and hard to answer, so it comes across as trolling. And if you’re talking to an adult individual who wants to argue not even about the priorities of basic research but the fundamental point of any of it, you can be pretty sure any conversation about the subject is pointless. People who want to take an anti intellectual stance aren’t waiting to hear a good argument before they change their point of view..
I wouldn't identify the tech world with intellectual work. I mean, setting up a lemonade stand is arguably intellectual work if we use the term in a broad enough sense.
By intellectual work, I mean (and most people here mean, I think) that which has no clear or intended use other than to explore, master, discover, learn -- pure research, study, teaching -- or isn't justified by real-world, practical "usefulness."
I tend to share just about all of Jaron Lanier's views on the tech world you're describing -- critical of free and open culture, unimpressed by and dismissive of LLMs and "AI," hostile to social media, and overwhelmingly disappointed.
Intellectual, academic, edifying work continues, entirely separately, to be worthwhile. I don't ask what number theory does for humanity, because I don't expect or need it to be useful in any popularly "practical" sense, any more than I expect a poem to be.
100% of all progress is science/technology/infrastructure. Without it we would be living in caves.
I guess there's many things interesting about it, but I see it like: prime numbers are the fundamental pattern of magnitudes, where the next prime is the first place that no multiples of any previous magnitude (prime or not) would ever land on.
In other words, if you took any previous magnitude (ie, any number less than that next prime), and copied it over edge to edge, the edge would never line up with that next prime.
Because counting and magnitude is so simple and fundamental to the space of concepts and even to reality, it's pretty fascinating that this extremely simple to describe pattern, is nevertheless hard to create a description for that's more concise than including all previous primes.
And I think people like finding that kind of 'shorter' description, as it indicates a deeper understanding, a new way of looking at reality that you didn't see before. And when we see that, it will probably be very useful to many other things.
It's fascinating to reflect on all that, and also on how this fundamental pattern of magnitudes, their 'self-similar but scaling' structure, also relates to the 'compressibility' of the number line and information theory.
That's what I think. I think everyone can find their own interest in there, there's probably a lot of ways to look at it. :)
Prime numbers are a core and mysterious numeric progression that has the unique property of being very taxing to determine the factors of any sufficiently large number. This is why they are used in cryptography. Investigations into the nature of primes has produced many mathematical tools and they have bridged many different areas of mathematics together.
But the simplest answer is that prime numbers are a tantalizing mystery that is easy for anyone to understand. The deeper you dig, the deeper the hole gets and it almost doesn't matter if a satisfying "answer" is ever found. Primes are a McGuffin that has led to countless discoveries.
You could have a thought experiment of a world, in which we never developed arabic numerals or roman numerals, but instead did all our math directly on prime numbers. It would be a weird world, but still, you might imagine it :-)
There are basically two ways to produce big numbers: add two small numbers, or multiply two small numbers. You can produce all positive integers by starting with zero and repeatedly adding one. You can almost do the same thing with multiplication too, except for these pesky primes, which are somehow atomic. Naturally then, one might ask: (a) How many primes are there? (b) How frequently do they occur? (c) Can we look at a number and determine whether it is a prime? Now consider: Despite being among the oldest of the mathematical disciplines, there are still open problems about primes that can be explained to high school students.
Also, multiplication and addition are not simply operations that are of interest with respect to integers, but similar ideas apply to a bunch of other domains too. Polynomials, for example. So primality and primality-like ideas are like catnip for mathematicians.
Any maths-y field of study that has the concept of decomposition also has the concept of primality, usually in a way that relates to primality in the natural numbers. This means anything we learn about prime numbers also extends to those other fields of study.
And, it's beautiful to think about. Maybe huge practical innovations might result, or maybe only the pleasure of understanding something deep about numbers in the short time we exist.
Sometimes if we are lucky either one of those yields phenomenal practical applications, just because some nerd thought there was a missing piece in the puzzle and they ought to find it.
I know many nowadays believe that the sole goal of humanity ought to be the increase of shareholder value, even if said increase is at odds with human survival on this planet. Then 99% of us just exist, work our asses off, with little to no time spent with our loved ones while leaving the planet and humanity in a worse state than previous generations — and then we die.
Was that really it then?
How much we want to support that (financially, socially etc) is a question a bit like, how much do we want to support children playing. Some disagree such should be supported at all, others are indifferent about such, yet others take pride in supporting or having supported such. The answer, to both of those questions, does have a large effect on how our societies look like. However, answering in the affirmative to support does not guarantee any positive progress. Likewise, answering in the negative, does not prevent progress, or basic research or children's play from happening.
Mathematics dealing with large primes and their complex structures is likely to find applications in other complex structures, eg in physics or computer science.
Mathematics is modern ontology: even when its self-investigation is not directly applicable, the vocabulary and semantics developed is often useful for articulating other truths.
I do agree on the view that science often discovers useful phenomena. What I tried to stress was that basic research does not, by definition, aim for such utility. Especially with pure math, whether there are any applications for new, even groundbreaking discoveries, is often very unclear. And when there are, they might be only utilized decades or centuries after the initial discovery.
That's true of one particular – albeit very popular – asymmetric cryptosystem, RSA. It isn't a property of asymmetric cryptography in general. There are other asymmetric encryption schemes which aren't based on the hardness of prime factorisation (e.g. DSA, elliptic curves, McEliece, NTRU)