Distributions of left prime truncations

This paper investigates the statistical distributions, including proportions, variance, and maximal proportions, of the number of left prime truncations for integers and irreducible truncations for polynomials over finite fields.

The Gist

Imagine you have a giant, magical number machine. You feed it a number, and it starts eating the number from the left, one digit at a time.

• The Machine's Test: Every time it eats a digit, it checks if the remaining number is still a "prime" (a number that can only be divided by 1 and itself, like 2, 3, 5, 7, 11).
• The Goal: We want to know: How many times can the machine eat a digit before the remaining number stops being prime?

The paper by Kuperberg and Lalín is like a massive statistical study of this machine. They aren't just looking at one specific number; they are asking: "If we pick a random number (or a random polynomial) and run it through this machine, what is the typical score? How much does the score vary? And what is the highest possible score anyone could ever get?"

Here is a breakdown of their findings using simple analogies.

1. The Two Worlds: Integers and Polynomials

The authors study this problem in two different "universes":

• Universe A (Integers): This is our normal world. We use base 10 (digits 0-9). The number 357686312646216567629137 is famous here because if you chop off the left digit repeatedly, every single piece left behind is a prime number. It's the "champion" of this game in base 10.
• Universe B (Polynomials): This is a more abstract world involving math equations (polynomials) over a finite field (think of a clock with only $q$ hours instead of 12). Instead of chopping off digits, they chop off the highest power of $T$ (like chopping off the "head" of the equation).

The authors realized these two worlds are actually twins. The "digits" in the integer world are like the "coefficients" in the polynomial world. By studying both, they can see patterns that are hidden if you only look at one.

2. The Average Score: "The Prime Lottery"

If you pick a random 100-digit number, how many of its "leftover" pieces will be prime?

• The Intuition: Primes are rare. As numbers get bigger, they become harder to find (like finding a specific grain of sand on a beach).
• The Finding: The authors calculated the average number of prime pieces you get.
  • If you increase the size of the base (like using base 1000 instead of base 10), the average score drops. It's like having a bigger lottery; the odds of winning (finding a prime) get smaller.
  • If you increase the length of the number (more digits), the average score goes up, but only slowly (like the logarithm of the length). It's like buying more lottery tickets; you get more wins, but not a million times more.

3. The Variance: "The Clumping Effect"

This is the most interesting part. The authors asked: "Is the score consistent, or do some numbers get lucky while others get unlucky?"

They found a phenomenon called "Clustering."

• The Analogy: Imagine a party where everyone is wearing a badge.
  • If your badge number shares a factor with the party's theme (e.g., the theme is "Multiples of 3" and your badge is 6), you are immediately kicked out of the "Prime Club." You get zero points.
  • If your badge is "coprime" (doesn't share factors), you have a chance to win.
• The Result:
  • When the base is huge: Everyone is roughly equally likely to be kicked out. The scores are spread out evenly.
  • When the base is small (like 10): There is a huge divide. Numbers that share factors with 10 (like 2, 4, 5, 6, 8) almost never have prime leftovers. They get a score of 0. But the numbers that don't share factors (like 1, 3, 7, 9) get to play the game properly.
  • The Consequence: This creates a "clump." You have a massive group of zeros and a smaller group of winners. This makes the variance (the spread of scores) much higher than you would expect. It's like a classroom where half the students get a 0 and the other half get an A, making the class average very misleading.

4. The Maximum Score: "The Record Breakers"

Finally, they asked: "What is the absolute best score possible?"

• The Analogy: Imagine flipping a coin. Most people get a mix of heads and tails. But if you flip enough coins, eventually, someone will get a streak of 100 heads.
• The Finding:
  • In the integer world, the maximum number of prime truncations for a number with $\ell$ digits is roughly proportional to $\frac{\ell \times \text{base}}{\log(\ell)}$.
  • In the polynomial world, it's similar but depends on the size of the field ($q$).
  • The Takeaway: No matter how long the number is, you can almost always find one special number that survives the chopping process almost all the way to the end. It's a "super-prime" that refuses to break.

Summary of the "Big Picture"

The paper is a deep dive into the statistics of luck.

1. The Average: Tells us what a "typical" number looks like (usually not very lucky).
2. The Variance: Tells us that "typical" is a dangerous word. Because of the "clumping" effect (numbers that share factors with the base), the results are very unpredictable. Some numbers are doomed to fail immediately; others are incredibly lucky.
3. The Maximum: Tells us that even in a world of rare primes, there are always "super-heroes" (the longest truncatable primes) that defy the odds.

The authors used advanced math (like the Riemann Hypothesis and complex number theory) to prove these patterns, but the core idea is simple: Primes are rare, but they cluster in specific ways, and if you look at enough numbers, you will find the ultimate champions.

Technical Summary

Here is a detailed technical summary of the paper "Distributions of Left Prime Truncations" by Vivian Kuperberg and Matilde Lalín.

1. Problem Statement and Motivation

The paper investigates the statistical distribution of left prime truncations in two distinct mathematical settings:

1. Integers: The number of prime numbers obtained by successively removing the leftmost digit of an integer $n$ in base $b$.
2. Polynomials: The number of irreducible polynomials obtained by successively removing the "leftmost" terms (highest degree terms) of a polynomial $f(T)$ over a finite field $\mathbb{F}_q$, viewed in a generalized base $b(T)$.

Core Questions:

• What is the average number of such truncations for a typical $n$-digit integer (or degree-$\ell$ polynomial)?
• What is the variance of this count?
• What is the maximal proportion of truncations that are prime/irreducible?

The authors aim to provide asymptotic answers as various parameters grow to infinity: the number of digits/degree ($\ell$), the base size ($b$ or $q$), and the degree of the base polynomial ($m$).

2. Methodology

The authors employ a combination of analytic number theory, probabilistic heuristics, and algebraic geometry over finite fields.

A. Definitions and Generalization

• Left Truncation (Integer): For $n = \sum_{j=0}^\ell a_j b^j$, a truncation is $n_k = \sum_{j=0}^k a_j b^j$.
• Left Truncation (Polynomial): For $f(T) = \sum_{j=0}^\ell a_j(T) b(T)^j$, a $b(T)$-truncation is $f_i(T) = \sum_{j=0}^i a_j(T) b(T)^j$.
• Generalization: The paper generalizes the standard polynomial case (where base is $T$) to an arbitrary base polynomial $b(T)$ of degree $m$. This creates a direct analogy where $m \to \infty$ in polynomials mirrors $b \to \infty$ in integers.

B. Analytic Tools

• Prime Number Theorem (PNT): Used to estimate the density of primes ($\pi(x) \sim x/\log x$) and irreducible polynomials.
• Dirichlet Characters & L-functions: Used to handle congruence conditions required for truncations.
  • In the integer setting, the Generalized Riemann Hypothesis (GRH) is assumed to derive unconditional-looking variance estimates for large $b$.
  • In the polynomial setting, the Riemann Hypothesis for Function Fields (a proven theorem) is used, allowing for unconditional results in the large $q$ and large $m$ limits.
• Von Mangoldt Function: The authors first estimate sums involving the von Mangoldt function $\Lambda(n)$ or $\Lambda(f)$ to handle prime powers, then subtract these contributions to isolate the indicator functions for primes/irreducibles.
• Borel-Cantelli Lemmas: Used in the heuristic sections to estimate the maximum number of truncations by analyzing the convergence of probabilities of rare events.
• Cramér Random Model: A probabilistic model where integers/polynomials are treated as random variables with probability $1/\log n$(or$1/\deg$) of being prime/irreducible, used to derive conjectures for the maximum values.

3. Key Contributions and Results

A. Average Number of Truncations

The paper establishes precise asymptotic formulas for the average number of prime truncations, denoted $\langle \text{Trun} \rangle$.

• Integer Case ($b \to \infty$):
  $$\langle \text{Trun}_b \rangle_{b^\ell} \sim \frac{1}{\log b} \sum_{h=1}^\ell \frac{1}{h} \sim \frac{\log \ell}{\log b}$$
  The average grows logarithmically with the number of digits $\ell$ and inversely with the logarithm of the base.

• Polynomial Case:

  • As $q \to \infty$: The average is dominated by terms involving $1/h$where$h \equiv -1 \pmod m$.
  • As $m \to \infty$: The behavior mirrors the integer case with $b \to \infty$, where $1/\log b$is replaced by$1/m$.
  • As $\ell \to \infty$: The average grows as $\frac{1}{m} (1 - q^{-m}) \log \ell$.

Significance: The results confirm that the polynomial setting (with large $m$ or $q$) is a robust analog to the integer setting with a large base $b$.

B. Variance Analysis

The variance is significantly more difficult to compute, particularly in the integer setting where it relies on deep conjectures about primes in arithmetic progressions.

• Integer Case ($b \to \infty$, assuming GRH):
  The variance is shown to be of order $\frac{\log \ell}{\log b}$.
  $$\text{Var} \sim \frac{1}{\log b} \sum \frac{1}{h} + \frac{1}{\log^2 b} \left(\frac{b}{\phi(b)} - 1\right) \left[ \left(\sum \frac{1}{h}\right)^2 - \sum \frac{1}{h^2} \right]$$
• Integer Case ($\ell \to \infty$):
  The authors conjecture that the variance scales as $(\log \ell)^2$. This is a qualitative shift from the $b \to \infty$ case.
  • Reasoning: When $b$ is fixed and $\ell$ is large, integers not coprime to $b$ have zero (or very few) prime truncations. This creates a "clustering" effect where the variance is dominated by the gap between coprime and non-coprime numbers.
• Polynomial Case:
  • Large $q$ and Large $m$: Unconditional results are proven using the Riemann Hypothesis for function fields. The variance behaves similarly to the integer case with large $b$.
  • Large $\ell$: A conjecture is proposed where the variance scales as $(\log \ell)^2$, mirroring the integer conjecture. The term $\frac{q^m}{\Phi(b)} - 1$ plays the role of the arithmetic factor $\frac{b}{\phi(b)} - 1$.

C. Maximum Number of Truncations

Using the Cramér model and Borel-Cantelli lemmas, the authors derive heuristics for the maximum number of prime truncations $K(\ell)$ possible for an $\ell$-digit number.

• Integer Case: $K(\ell) \asymp \frac{\ell \log b}{\log \ell}$.
• Polynomial Case: $K(\ell) \asymp \frac{m \ell \log q}{\log \ell}$.
• Interpretation: These results suggest that for sufficiently large bases or fields, one can almost certainly find numbers/polynomials where every truncation is prime/irreducible, provided the length is not too large relative to the base size.

4. Significance and Implications

1. Unification of Number Theory: The paper successfully bridges the gap between the distribution of primes in integers and irreducible polynomials over finite fields. It demonstrates that the "large base" limit in integers is structurally identical to the "large degree of base polynomial" limit in function fields.
2. Variance Phenomenon: The discovery that the variance scales as $\log \ell$ in the large-base limit but as $(\log \ell)^2$ in the large-length limit (for fixed base) is a significant insight. It highlights the importance of coprimality with the base in the distribution of prime truncations.
3. Methodological Rigor: The paper provides rigorous proofs for the polynomial case (unconditional due to the proven RH for function fields) while offering well-founded conjectures for the integer case (conditional on GRH or heuristic arguments).
4. Recreational Math Connection: The work provides a theoretical foundation for "left-truncatable primes" (like the famous 357686312646216567629137), explaining their rarity and distribution properties.

5. Conclusion

Kuperberg and Lalín provide a comprehensive analysis of left prime truncations. They prove that the average number of truncations follows a harmonic series distribution scaled by the density of primes in the respective setting. They identify a critical phase transition in the variance depending on whether the base or the length tends to infinity. Finally, they use probabilistic models to predict the maximal length of such sequences, confirming that while they are rare, they exist in abundance for large parameters. The paper serves as a definitive reference for the statistical properties of truncatable primes and polynomials.