AI Proved What?

Episode 011, October 2026

How does p − 1 break?

Prime-factor statistics of p − 1: the Poisson–Dirichlet law, and Erdős’s totient conjecture

Covers result 011 in OpenAI’s catalog: all 3 papers. See its connections to other results and the work it cites.

Play Episode 011: How does p − 1 break? The broken-stick law for primes, and Erdős’s totient conjecture. Six bars, each p − 1 for a prime p near a million, split into colored pieces by the logarithms of its prime factors.

6:11. English captions available. The video loads from YouTube when you press play.

Chapters

  1. 0:00Breaking a number
  2. 0:57A broken stick
  3. 1:37Primes minus one
  4. 2:56The claims
  5. 3:40Totient collisions
  6. 4:45How the proof goes
  7. 5:33The caveats

The claim, in plain words

Factor a number and measure each prime factor by its logarithm. The logarithms add up to the logarithm of the number, so each prime gets a share of one whole: 1,000,002 = 2 × 3 × 166,667 splits as about 5%, 8% and 87%. For a large random number, sorted from largest to smallest, these shares follow a precise limiting law, the Poisson–Dirichlet law PD(1) (Billingsley, 1972). It is the law of a stick broken at random again and again: break off a uniformly random fraction, set it aside, break a uniformly random fraction off what is left, and so on, then sort the pieces. It also describes the relative cycle lengths of a large random permutation. Under it, the largest piece is more than half with probability log 2 ≈ 69%, and no piece reaches a third with probability ρ(3) ≈ 4.9%, where ρ is Dickman’s function.

Result 011 claims the same law for p − 1, where p is a random prime, in three papers:

  • The Poisson–Dirichlet law for prime predecessors (74 pages). For a prime p ≤ x chosen at random, list the prime factors of p − 1 with multiplicity, largest first, and divide their logarithms by log(p − 1). As x → ∞, every fixed number of these shares jointly converges to PD(1). This is the conjecture of Ford, Konyagin and Luca, and it includes Granville’s prediction for the largest factor.
  • Smooth shifted primes and totient fibers (68 pages; listed first in OpenAI’s catalog). For every fixed δ > 0 there are x1−o(1) primes p in (2x, 5x] with every prime factor of p − 1 at most xδ. By an argument going back to Erdős, this proves Erdős’s conjecture on Euler’s totient function: for every ε > 0, infinitely many n are values φ(m) = n for more than n1−ε different m.
  • Prime predecessors with an even number of prime factors (45 pages). Infinitely many primes p have p − 1 squarefree with an even number of prime factors, that is, μ(p − 1) = 1.

What it doesn’t claim

The law is a limit: it comes with no rate, and the data approach it slowly (below). The smoothness count x1−o(1) on its own is not a positive proportion of primes; the Poisson–Dirichlet paper gives that, a proportion ρ(1/δ), using the second paper’s graph theorems. Ford, Konyagin and Luca’s probabilistic model of prime chains needs further independence across generations, which is not claimed.

Where it stands

Posted as preprints
OpenAI, dated September 17 and 24, 2026; released October 6, 2026
Peer reviewed
Not yet
Checked in Lean
No: OpenAI published no Lean proof for this result

Last checked October 19, 2026. The claim has not been withdrawn, and we found no public critique. Erdős problem #821, the totient question, is still listed as open on erdosproblems.com.

What was known

  • For ordinary integers: Dickman (1930) found the law of the largest prime factor, Billingsley (1972) the joint law of the large ones, and Donnelly and Grimmett gave the size-biased, broken-stick description.
  • For p − 1: requiring a large prime q to divide p − 1 puts p in an arithmetic progression with modulus q. The Bombieri–Vinogradov theorem controls such progressions on average only up to about √x, and special methods go only slightly beyond. Under the Elliott–Halberstam conjecture, Bharadwaj and Rodgers (2024) obtain the full law; Ford, Konyagin and Luca (2010) had recorded it as widely expected.
  • Smooth shifted primes: Baker and Harman (1998) found many primes with every prime factor of p − 1 below p0.2961, and Lichtman (2022) below p0.2844. For totients, Erdős (1935) proved that some exponent c > 0 works; the best exponents became 0.7039 (Baker–Harman) and 0.7156 (Lichtman). Exponent 1 is the best possible.

How the proof goes

  1. Sieve plus a bilinear estimate. To count primes p = 2u + 1 with u of a prescribed shape, a sieve handles the divisibility conditions, but on its own it cannot separate primes from products of two large primes (the parity problem). A bilinear, or Type II, estimate supplies the missing information.
  2. Marks. The new Type II estimates let the numbers carry marks, weights recording which of certain small primes divide them. In the Poisson–Dirichlet paper the marks sit on one side only, and a determinant relation between lattice vectors, averaged with a signed “memory” expansion, makes each prime’s divisibility probability count only once.
  3. Dilation graphs. The totient paper joins integers by edges built from shared marked primes and compares this graph with an ideal model in which prime labels are independent, with probabilities proportional to 1/p; a small ideal norm gives cancellation. The Poisson–Dirichlet paper uses these graph theorems for its two-sided estimate.
  4. From interior statistics to the law. The estimates give the statistics of the pieces away from the extremes; a size-biased probability argument turns them into the full sorted law.

The numbers in the video

  • 1,000,003 is prime and 1,000,002 = 2 · 3 · 166,667, with log shares 5.0%, 8.0% and 87.0%.
  • ρ(2) = 1 − log 2 ≈ 0.3069 and ρ(3) ≈ 0.0486. A simulated broken stick, 400,000 times, puts the largest piece above one half 69.3% of the time.
  • How often the largest prime factor of p − 1 exceeds √(p − 1): 57.8% of primes up to 104, 61.4% up to 105, 63.2% up to 106, 64.4% up to 107, against log 2 ≈ 69.3%. For ordinary integers up to 107 it is 72.8%, approaching from above.
  • φ(m) = 72 has exactly 17 solutions: 73, 91, 95, 111, 117, 135, 146, 148, 152, 182, 190, 216, 222, 228, 234, 252, 270.
  • All checked with a short Python script.

Read the source

The 3 papers in this result

OpenAI groups related papers, such as alternative proofs, supporting results and consequences, into one result; we label the first paper it lists the main paper and the others companions.

Transcript

Read the full script

0:00Breaking a number

Take the number 1,000,002, and break it into primes: 2 × 3 × 166,667. Now measure each prime by its logarithm, roughly its number of digits. The pieces add up to the whole number’s logarithm, so each prime gets a share of one whole: 5%, 8%, and 87%. Do this for a random number, and the shares look random too. In 1972, Patrick Billingsley proved that, for large numbers, they follow a precise limiting law, the same law that governs the relative cycle lengths of a large, randomly shuffled deck. Now pick a random prime p, and break up p − 1. The same law was expected there too. Result 011 in OpenAI’s math repository claims to prove it, and, along the way, a conjecture of Paul Erdős about Euler’s totient function.

0:57A broken stick

Here is the law. Take a stick of length one. Break off a piece of uniformly random length, and set it aside. Break a uniformly random fraction off what’s left, set that aside, and keep going. Sort the pieces from largest to smallest. Their distribution is called Poisson–Dirichlet, with parameter one. It makes sharp predictions. The largest piece is more than half the stick with probability log 2, about 69%. For a large random whole number, that is, in the limit, the chance its largest prime factor is bigger than its square root. And the chance that no piece reaches a third is under 5%: Dickman’s function at 3.

1:37Primes minus one

Now the primes. For a prime p above 2, p − 1 is even, so a factor of 2 always shows up, but on this scale a single 2 barely matters. In 2010, Kevin Ford, Sergei Konyagin and Florian Luca wrote down the widely expected conjecture: the shares of p − 1 follow the same broken-stick law. The data agree, slowly. Among primes up to 10,000, the largest piece of p − 1 is more than half about 58% of the time. Up to 10 million, it is 64%, creeping toward 69. Why is this hard? To say a large prime q divides p − 1 is to say that p is 1 more than a multiple of q. That puts p in an arithmetic progression with a huge modulus. The general unconditional tools handle such progressions, on average, only for moduli up to about the square root, and special methods go only slightly beyond. A deep conjecture, Elliott–Halberstam, would go all the way, and would give the full law. Without it, results were partial. One landmark is smooth shifted primes: in 2022, Jared Lichtman showed that many primes have p − 1 with no prime factor above about p^0.284.

2:56The claims

Result 011 has three papers. The headline one claims the full law: for a random prime up to x, the shares of the prime factors of p − 1, sorted by size, converge to the broken-stick law as x grows, for any number of the largest pieces at once. A second paper claims that p − 1 is often as smooth as you like: for any fixed power of x, however small, the number of primes near x whose p − 1 has no prime factor above that power is x^(1 − o(1)). The main law makes it a positive proportion. The third paper claims that infinitely many primes have p − 1 squarefree, with an even number of prime factors.

3:40Totient collisions

Why care whether p − 1 is smooth? Euler’s totient function, φ(m), counts the numbers up to m that share no prime factor with m. Different numbers can share a value: φ(m) = 72 for 17 different m. Erdős saw where such collisions come from. For a prime p, φ(p) is p − 1, and for a product of distinct primes, φ multiplies their values of p − 1. 73 gives 72. So does 7 × 13, because 6 × 12 = 72, and so do 5 × 19 and 3 × 37. If many primes have p − 1 built only from small primes, there are far more products than possible values, so many products must collide. He conjectured that, for any ε, infinitely many values n are hit more than n^(1 − ε) times. The best exponent known was about 0.72, from Lichtman’s work. The second paper claims the full conjecture, exponent one, the best possible.

4:45How the proof goes

How do you count primes whose predecessors have a prescribed shape? A sieve counts numbers with the right divisibility, but on its own it can’t tell primes from products of two primes. The extra ingredient is a bilinear estimate. The new ones here let the numbers carry marks: labels recording which of certain small primes divide them. That turns the problem into a graph: integers joined when they are related through shared marked primes. The papers compare it to an idealized random graph, where each prime divides independently with probability 1/p. A memory device makes sure each prime’s divisibility is paid for only once, even when it comes back again and again. Finally, a probability argument turns statistics for pieces away from the extremes into the full sorted law.

5:33The caveats

The caveats. These are three preprints, about a hundred and ninety pages, not peer reviewed, and with no Lean proof. The law is a limit with no rate, and the data show the approach is slow. The smoothness count alone isn’t a positive proportion; that comes from the headline paper, which uses the second paper’s graph theorems. And Erdős problem #821, the totient question, is still listed as open on the Erdős problems website. Break p − 1 into its primes, and the pieces fall like a randomly broken stick. If the proof holds.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.