The Distribution of Prime Numbers: A Geometrical Perspective

Alberto Fraile and Daniel Fernández guest post on random walks generated by the distribution of prime numbers.

In our recent papers, we explored the sequence of prime numbers by defining "random walks" governed by simple algorithms applied to their sequence.

We introduced a prime number visualization called Jacob’s Ladder. The algorithm plots numbers on a 2D graph that oscillates up and down based on the presence of prime numbers, creating a ladder-like structure. The path ascends or descends based on the primality of subsequent numbers. When a prime number is encountered, the path alters direction, leading to a zig-zag pattern. Number 2 is prime, so it flips and goes down. Now 3 is prime, so the next step changes direction and goes up again, so we move up. But 4 is not a prime, so it continues up, and on it goes.

Jacob’s Ladder from 1 to 100,000 (Top) and from 1 to 1,000,000 (Bottom).
The blue line represents y=0, or sea level.

The x-axis can be imagined as sea level, the zig-zag above it as mountains, and those below as ocean chasms. Our intrepid navigator sails eastward, occasionally discovering new lands—sometimes tiny islands, other times vast continents.

As we chart this new world, it is natural to wonder about the location of the next continent (if any), the height of its highest mountain, or the depth of its deepest ocean. One thing we know for sure is that gaps between primes can become arbitrarily large. This suggests there may be no upper bound on the mountains’ heights or the chasms’ depths.

A natural question arises: if the voyage continues into infinity, would this world contain equal amounts of land and sea? Or, more formally, does the construction exhibit symmetry in the limit, with equal numbers of positive and negative points? The beauty of Jacob’s Ladder lies in its simplicity, yet it raises many questions that are surprisingly difficult to answer.

Prime Walk

In our second study, we examined the behavior of a 2D "random walk" determined by the sequence of prime numbers, known as the prime walk (PW), choosing a direction based on the last digit of the next prime (1 down, 3 up, 7 right, 9 left) ignoring the primes 2 and 5.

Graphical representation of three different PWs up to N=108. Color coding represents step progression.

Observing the PW in action raises numerous questions.

For instance, will this PW eventually cover the entire plane as N → ∞? Will the area explored continue expanding indefinitely, or will it reach a limit? Initially, we conjectured the area would be unbounded.

We thought this conjecture might remain unanswered indefinitely, so we challenged the community with a modest prize for anyone who could prove it within two years of publication. Surprisingly, we found the solution ourselves, detailed in our recent work.

Moreover, within the explored region, certain points remain unvisited—small regions or isolated spots. Could some points remain unreachable forever? These straightforward questions, intriguingly, remain remarkably difficult to answer.

If you do well in the UMCP HS Math Competition you may win $1,000,000

The Univ of  MD at College Park holds a HS Math Competition every year. At the reception for the winners Professor Larry Washington points to many past people who did well on the exam. Two stand out for different reasons:

1) Serge Brin did well on the UMCP HS competition and went on to be a Stanford Math Grad Student Drop Out. Oh well. (I originally had Standard instead of Stanford. That sentence will makes sense.) 

2) Sarah Manchester did well on the UMCP HS competition  and went on to win $1,000,000 on Wheel of Fortune. 

Is there a connection between doing well on the UMCP Math Competition and winning $1,000,000 on Wheel of  Fortune? 

Only 4 people have won the $1,000,000. Worse, if you don't win the $1,000,000 you will probably win less than $50,000. An article about those 4 is here. This is so few that while I am sure Sarah is good at Wheel of Fortune (a) she had to also be very lucky, and (b) I doubt being good at Math had much affect on her winning. 

While we are here, lets look at two other game shows.

14 people have won $1,000,000 or more on Who wants to be a Millionaire?, see here. That show has the advantage that even if you don't win $1,000,000 it's not so unusual to get over $100,000.

(What kind of people do not want to be millionaires? I give two answers later.) 

Deal or No Deal has different versions in different countries so it gets more complicated:

UK: 9 big winners, Turkey: 1 big winner, Australia: 4 big winners, America: 2 big winners. 

ANYWAY back to Sarah and Wheel of Fortune: The statement

Sarah did well on the UMCP HS Math Competition and went on to win $1,000,000 on Wheel of Fortune

is technically true but conveys a causality that is not true. 

Who does not want to be a millionaire? 

Would be a terrible name for a quiz show. However, taking it as a question the answer is with one caveat: I define Millionaire as someone who has AROUND $1,000,000. 

a) Billionaires. Actually, anyone who has much more than  $1,000,000 would not want to come down to only $1,000,000.

b) People who think it would change their life in ways they don't want. 

Fulbright Memories

As the entire Fulbright board resigned last week and as the program that promotes international visits for US researchers, and vice-versa, may not survive the Trump administration, I thought I would recount some memories from my Fulbright scholarship to the Netherlands in 1996-97.

The program had considerable paperwork for a relatively small stipend, but it went beyond the compensation. I went to a meeting in Amsterdam with the other fellows, mostly grad students and postdocs. I was the old one as a recently tenured associate professor. The others had strong reasons for being in the Netherlands: An historian who wanted to research the Dutch army, and a piano player with hands too small who came to study with the world's leading teacher on a specialized narrow-keyboard grand.

And so they asked me why I would go to the Netherlands from the US to study computer science. But I spent the sabbatical year at the Centrum Wiskunde & Informatica (Center for Mathematics and Computer Science) in Amsterdam working with Harry Buhrman, Leen Torenvliet, Paul Vitányi and others. I also made several trips to universities in Germany, England, France and Israel, and had one of my best research years.

My coolest Fulbright experience was having Thanksgiving dinner at the US ambassador's house in The Hague, perhaps the most American thing I did during the year.

I also participated in celebrations marking the fiftieth anniversary of the Fulbright program, established in 1946 to encourage international educational and research collaborations, alongside the Marshall Plan and NATO, to draw the US closer to Europe and later the rest of the world. Too bad we seem to be moving away from those ideals today. 

Lance never thought he would see a Pope who roots for the same team as him. And now...

 A year ago if I showed you a picture of The Pope wearing a Baseball cap for the Chicago White Sox  (or any Amercan team) you would assume it was computer-generated.  And you would likely be right. 

Are there any real pictures of any Pope before Pope Leo XIV with a baseball cap on? 

I doubt it 

A real picture of Pope Leo wearing a Chicago White Sox baseball cap is here.

1) Having an American Pope is so incongruent with how we think of Popes that pictures like Pope Leo XIV in a baseball cap look very odd.

2) Pope Francis was a soccer fan (see here).  Is there a real  pictures of him wearing a soccer jersey?

3) Before the web we didn't know much about the personal lives of leaders. I don't just mean we didn't know about (say) their affairs; we didn't even know about non-controversial things like what sports team they root for. 

4) Lance has tweeted that he never thought he would see the day where he and The Pope rooted for the same baseball team. I want to see a picture of The Pope and Lance together at a game, both wearing Chicago White Sox caps. A real picture may be hard to do, but I suspect that once The Pope  sees this post he will create such a picture. 

5) I hope the next Pope is a fan of the San Diego Padres for two reasons

a) The name of the team.

b) They have never won a World Series. They need all the help they can get.

Defending Theory

In the June CACM, Micah Beck writes an opinion piece Accept the Consequences where he is quite skeptical of the role of theory in real-world software development, concluding

It is important that we teach practical computer engineering as a field separate from formal computer science. The latter can help in the understanding and analysis of the former, but may never model it well enough to be predictive in the way the physical sciences are.

I certainly agree that theoretical results can't perfectly predict how algorithms work in practice, but neither does physics. The world is much more complex, both computationally and physically, to perfectly model. Physics gives us an approximation to reality that can help guide engineering decisions and theory can do the same for computation.

You need a basis to reason about computation, lest you are just flying blind. Theory gives you that basis.

Let's consider sorting. Beck complains that Quicksort runs in \(O(n^2)\) time in the worst case even though it is used commonly in practice, while the little-used Insertion sort runs in worst-case \(O(n\log n)\). Let's assume Beck meant an algorithm like heapsort that actually has \(O(n\log n)\) worst-case performance. But theorists do more than fixate on worst-case performance, Quicksort runs in \(O(n\log n)\) on average, and on worst-case if you use a random pivot, or a more complex deterministic pivoting algorithm. Introsort combines Quicksort efficiency and worst-case guarantees and is used in some standard libraries.

Beck worries about secondary storage and communication limitations but theorists have studied sorting in those regimes as well. 

The other example he talks about is about a theoretical result that one cannot use an unreliable network to implement one that is completely reliable while textbooks consider TCP to be reliable. But in fact TCP was designed to allow failure because it took account of the theoretical result, not in spite of it.

Beck ends the article talking about Generative AI where theory hasn't kept up with practice at all. Beck calls for using classical AI tools based on formal logic as guardrails for generative AI. However, the lack of theoretical understanding suggests that such guardrails may significantly weaken generative AI's expressive power. Without adequate theory, we must instead rely more heavily on extensive testing, particularly for critical systems.

There are stronger examples Beck could have used, such as algorithms that solve many NP-complete problems efficiently in practice despite their theoretical intractability. Even here, understanding the theoretical limitations helps us focus on developing better heuristics and recognizing when problems might be computationally difficult.

I agree with Beck that relying solely on the theoretical models can cause some challenges but rather than have the students "unlearn" the theory, encourage them to use the theory appropriately to help guide the design of new systems.

Beck's call to separate software development from theory only underscores how important we need to keep them intertwined. Students should know the theoretical foundations, for they shape problem solving, but they should also understand the limitations of these models.

The New Godel Prize Winner Tastes Great and is Less Filling

David Zuckerman

The 2025 Gödel Prize has been awarded to Eshan Chattopadhyay and David Zuckerman for their paper

Explicit two-source extractors and resilient functions

which was in STOC 2016 and in the Annals of Math in 2019. 

We (Bill and Lance) care about this result for two different reasons.

BILL: The result has applications to constructive Ramsey---

LANCE: Ramsey Theory? Really? This is a great result about

Eshan Chattopadhyay

pseudorandomness! In fact the only interesting thing to come out of Ramsey Theory is the Probabilistic Method (see our discussion of this here). 

BILL: Can't it be BOTH a great result in derandomization AND have an application to Ramsey Theory. Like Miller Lite: Less Filling AND Tastes Great (see here)

LANCE: But you don't drink!

BILL: Which means I can give a sober description of their application to Ramsey Theory.

All statements are asymptotic.

Let \(R(k)\) be the least \(n\) so that for all 2-colorings of \(K_n\) there is a homog set of size \(k\).

Known and easy: \(R(k)\le 2^{2k}/\sqrt{k} \)

Known and hard: \(R(k) \le 3.993^k \). How do I know this is true? Either I believe the survey papers on these kinds of results (see here) or a former student of mine emailed me a picture of a T-shirt that has the result (see here) from (of course) Hungary.

Known and Easy and Non-Constructive: \(R(k)\ge k2^{k/2}\)

Can we get a constructive proof? There were some over the years; however, the paper by Eshan Chattopadhyay and David Zuckerman improves the constructive bound to exponential in \(  2^{(\log k)^\epsilon}.\) 

SO Lance, why do you care?

LANCE: First of all when I chose this paper as one of my favorite theorems (a far bigger honor than the so-called Gödel Prize) I gave the post the clever title Extracting Ramsey Graphs that captures both the pseudorandomness and the Ramsey graphs. But of course the Ramsey result is just a minor corollary, the ability to get a near perfect random bit out of two independent sources of low min-entropy is the true beauty of this paper. 

BILL: You have no sense of good taste.

LANCE: Well at least I'm not less filling.

Rules vs Standards

You can write laws that are very specific, like the US tax code, or open to interpretation like the first amendment. In the literature these are known as rules and standards respectively. 

In computational complexity, we generally think of complexity as bad. We want to solve problems quickly and simply. Sometimes complexity is good, if you want to hide information, generate randomness or need some friction. But mostly we want simplicity. How does simplicity guide us in setting guidance, either through rules or standards?

 

Rules are like a computer program. Feed in the input and get an output. Predictable and easy to compute. So why not always have tight rules?

Nobody ever gets a computer program right the first time, and the same goes for rules. Rules can be overly restrictive or have loopholes, leading to feelings of unfairness. Rules can require hoops to jump through to get things done. Rules don't engender trust to the ones the rules apply to, like very tight requirements on how grant funds can be spent. We know that in general we can't predict anything about how a computer program behaves, so why do we trust the rules? 

A good example of a standard is that a PhD dissertation requires significant original research. Rules are things like the exact formatting requirements of a thesis, or statements like a CS thesis must contain three papers published in a specific given set of conferences. 

As an administrator I like to focus on making decisions based on what's best for my unit, as opposed to ensuring I followed every letter of every rule. Because if you live by the rules, you'll die by the rules.  People will try to use their interpretation of the rules to force your hand.

Sometimes we do need strict rules, like safety standards, especially for people unfamiliar with the equipment. Structured rules do give a complete clarity of when an action is allowed. But it also gives an excuse. Have you ever been satisfied by someone who did something you didn't like but said "I was just following the rules"?

Even strict rules tend to have an out, like a petition to take a set of courses that don't exactly match the requirements of a major. The petition is a standard, open to interpretation to capture what the rules don't. 

As a complexity theorist I know what programs can't achieve, and as an administrator I see the same with rules. I prefer standards, principles over policies. Set your expectations, live by example, and trust the people, faculty, staff and students, to do the right thing and push back when they don't. People don't want strict rules, but they mostly act properly when they believe they are trusted and have wide latitude in their work. 

Complexity theory of hand-calculations

 (Thanks to David Marcus who sent me the video I point to in point 4 of this post. Tip for young bloggers (if there are any) you can have a half-baked idea for a post and then someone sends you something OR you later have an idea to make it a full-baked idea for a post. That's what happened here. So keep track of your half-baked ideas.)

1) When I was 10 years old I wanted to find out how many seconds were in a century. I didn't have a calculator (I might not have known what they were). I spend a few hours doing it and I got AN ANSWER. Was it correct? I didn't account for leap years. Oh well.

(An astute reader pointed to a website that does the centuries-to-seconds conversion as well as many other conversions. It is here. If such was around when I was a kid, what affect would it have on my interest in math? Impossible to know.) 

2) Fast forward to 2024: I wanted to find the longest sequence of composites all \( \le 1000\). One long sequence I found by hand is the following (I also include the least prime factor):

114-2, 115-5, 116-2, 117-3, 118-2, 119-7, 120-2, 121-11, 122-2, 123-3, 124-2 , 125-5, 126-2

length 13.

I wanted to find the answer WITHOUT using a computer program or looking at list of primes online (though I do allow a calculator just for division and multiplication). 

Of more interest mathematically is trying to prove that there is no sequence of length 14. (If there is, then perhaps the attempt will lead us to it.) 

Assume there was a sequence of consecutive composites \(\le 1000\) of length 14.

Map each one to the least prime that divides it. 

At most 7 of them map to 2

At most 3 of them map to 3

At most 2 of them  map to 5

At most 1 of them  map to 7.

At most 1 maps to 11. (Can look at 11*p for all primes \(11\le p \le 89\) and see any of them are in a sequence of length 14.) 

I'll stop here. This is getting tedious and might be wrong. So I asked Claude. It gave me a  sequence of composites of length 19. Here it is (I include the least prime factor):

888-2, 889-7, 890-2, 891-3, 892-2, 893-19, 894-2, 895-5, 896-2, 897-3, 898-2, 899-29, 900-2, 901-17, 902-2, 903-3, 904-2, 905-5, 906-2.

Can one show by hand that there is no sequence of length 20? 

3) The more general question: what is the complexity of finding the longest string of composites all \( \le n\) . This is actually many questions:

a) By hand: by which I mean only allowing multiplication and division and only of numbers \(\le n.\)

b) Theoretically. Use whatever fancy algorithms you want.

c) Theoretically but can assume some Number theory Conjectures that are widely believed. The Wikipedia page on prime gaps is here. (ADDED LATER- an astude commenter pointed out that we want LARGE gaps between primes, but the wikipedia article is about SHORT gaps between primes.) 

d) Do a,b,c for the set version which is as follows:  Given \(n\) and\( L\) determine if there a sequence of consecutive composites of length L that are all \(\le n\).  

4) Does anyone else care about calculation-by-hand? Yes! There are people who want to compute\(\ pi\) to many places JUST BY HAND. Here is a video about them here. Spoiler alert: they did very well.