🔢 mathematics

Small values of Carmichael's lambda function

This paper establishes an asymptotically sharp upper bound for the count of integers $n \le x$ with small Carmichael lambda function values under a plausible hypothesis on powersmooth shifted primes, and applies this result to derive a new upper bound on the number of odd integers where the multiplicative order of 2 is significantly smaller than $x^{1/2}$ .

Original authors: Paul Pollack

Published 2026-06-18

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Paul Pollack

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Speed Limit" of Numbers

Imagine you have a giant lockbox with a number $n$ on it. Inside this box, there is a special club of numbers (called the multiplicative group) that can play a game of multiplication modulo $n$ .

In this game, if you pick a number $a$ and keep multiplying it by itself ( $a, a^2, a^3, \dots$ ), eventually you will hit the number 1 again. The number of steps it takes to get back to 1 is called the order of $a$ .

Carmichael's $\lambda(n)$ is the "master speed limit" for this club. It is the smallest number of steps you need to guarantee that every member of the club returns to 1 at the same time.

If $n$ is a prime number, the club is huge, and the speed limit is almost as big as the number itself.
If $n$ is a "messy" composite number, the speed limit can be surprisingly small.

The Question: How many numbers $n$ (up to a huge limit $x$ ) have a very small speed limit ( $\lambda(n) \le y$ )?
The paper tries to count these "slow" numbers.

The Analogy: The Library of Numbers

Imagine a massive library containing every book (number) from 1 to $x$ .

The "Typical" Book: Most books in this library are "fast." Their speed limit is huge. If you pick a random number, its $\lambda(n)$ is likely very large.
The "Slow" Books: A few books are "slow." Their speed limit is tiny.

The author, Paul Pollack, is trying to figure out exactly how many "slow" books are in the library when we set a specific speed limit $y$ .

The Main Discovery: A New Map for the "Slow" Zone

Before this paper, mathematicians knew about the "fast" books (the typical ones) and the "super-slow" books (the extremely rare ones). But there was a mysterious middle ground—a "twilight zone" of numbers that were slow, but not too slow.

Pollack draws a precise map for this twilight zone. He provides a formula that predicts the count of these slow numbers with incredible accuracy.

The Formula's Secret:
The paper reveals that the number of these slow integers depends on a specific, complicated function involving logarithms (let's call it the "Log-Log-Log function").

If you set your speed limit $y$ to be very small, the number of slow books drops off sharply.
If you set $y$ to be moderately small, the number of slow books follows a specific curve.

The paper proves that his formula is an upper bound (a ceiling) for how many slow numbers can exist. He also shows that if a certain reasonable guess about prime numbers (called "Hypothesis U") is true, then this ceiling is actually the exact number. In other words, the formula isn't just a limit; it's the real answer.

The "Shifted Prime" Mystery (Hypothesis U)

To prove his formula is perfect, Pollack relies on a hypothesis about shifted primes.

Think of a prime number $p$ as a special key.
A "shifted prime" is $p-1$ .
The hypothesis suggests that the "smoothness" (how easily $p-1$ can be broken down into small factors) of these shifted primes behaves just like random numbers of the same size.

If this hypothesis holds, Pollack's map is 100% accurate. If it doesn't, his map is still a very tight ceiling that no one can break.

The Real-World Application: The "Order of 2"

The paper ends with a practical application involving the number 2.
In cryptography and computer science, we often care about the "order of 2 modulo $n$ ." This is how many times you have to multiply 2 by itself to get back to 1 modulo $n$ .

The Old Knowledge: We knew that for almost all odd numbers $n$ , the order of 2 is huge (at least the square root of $n$ ).
The New Result: Pollack uses his new map to prove that if you look for numbers where the order of 2 is significantly smaller than the square root of $n$ , there are almost none of them.

He gives a strict upper limit on how many such "super-slow" numbers exist. It's like saying, "If you are looking for a car that drives slower than 10 mph on a highway, you will find almost zero of them, and here is the exact mathematical proof of why."

Summary of the "Twilight Zone" Results

The paper focuses on a specific range where $y$ (the speed limit) is neither tiny nor huge.

The Upper Bound: He proves you can't have more than a certain number of slow integers.
The Sharpness: He argues that this limit is likely the exact count, provided our understanding of prime numbers is correct.
The Method: He uses a mix of old tricks (from mathematicians like Erdős and Pomerance) and new, delicate techniques to count these numbers, treating them like a complex puzzle of factors and primes.

In a Nutshell

Paul Pollack has built a highly accurate "speedometer" for a specific group of numbers. He showed that while most numbers are fast, the ones that are "slow" are incredibly rare, and he gave us the precise mathematical formula to count exactly how rare they are. This helps us understand the hidden structure of numbers and improves our knowledge of how the number 2 behaves in modular arithmetic, which is a cornerstone of modern encryption.

Technical Summary of "Small Values of Carmichael's $\lambda$ -Function" by Paul Pollack

Problem Statement
The paper investigates the distribution of "intermediate" values of Carmichael's $\lambda$ -function, $\lambda(n)$ , which represents the exponent of the multiplicative group $(\mathbb{Z}/n\mathbb{Z})^\times$ . While the maximal order of $\lambda(n)$ is trivial ( $n-1$ for primes) and the typical order is well-understood (Erdős, Pomerance, and Schmutz showed $\lambda(n) \approx n(\log n)^{-\log \log \log n - A}$ for almost all $n$ ), the distribution of values significantly smaller than the typical size but larger than the minimal order remains less explored.

The central object of study is the counting function $L(x, y) = \#\{n \le x : \lambda(n) \le y\}$ . The paper aims to establish an upper bound for $\log L(x, y)$ that is asymptotically sharp in the range where $y$ is "reasonably large" relative to $x$ , specifically for $y$ satisfying:
$\exp((\log_2 x)^{1+\varepsilon}) \le y \le x / \exp((\log_2 x)^{1+\varepsilon})$
where $\log_k$ denotes the $k$ -th iterate of the natural logarithm.

Methodology
The proof strategy is divided into establishing rigorous upper bounds and conditional lower bounds (assuming a specific hypothesis on shifted primes) across different ranges of $y$ .

Upper Bounds for Small $y$ :
For the range $\exp((\log_2 x)^{1+\varepsilon}) \le y \le x^{1/\log_2 x}$ , the author adapts techniques from Erdős and Pomerance. The core argument utilizes Rankin's trick to bound the number of integers $n \le x$ with a fixed $\lambda(n) = m$ . By analyzing the condition that $p-1 \mid m$ for all prime factors $p$ of $n$ , the author derives an exponential upper bound involving the function $\mathcal{L}(x, y) = \exp\left(\frac{\log x \log_3 x}{\log_2 y}\right)$ .
Lower Bounds (Conditional):
To show the upper bounds are sharp, the paper assumes Hypothesis U, a conjecture regarding the distribution of powersmooth shifted primes. Specifically, it posits that the count of primes $p \le x$ such that the largest prime power dividing $p-1$ is at most $y$ behaves like the count of $y$ -powersmooth integers up to $x$ .
- For small $y$ , the author constructs "popular" values of $\lambda(n)$ by forming products of primes $p$ where $p-1$ is powersmooth, adapting arguments from Erdős and Pomerance regarding Euler's totient function.
- For large $y$ (specifically $y \ge \mathcal{L}(x)^2$ ), a different construction involving pairs of integers $(a, b)$ is used to demonstrate the existence of sufficiently many $n$ with small $\lambda(n)$ .
Upper Bounds for Large $y$ :
The most novel contribution of the paper is the rigorous upper bound for large $y$ (up to $x/\exp((\log_2 x)^{1+\varepsilon})$ ). This section revisits and refines methods from previous works on the preimage of Euler's $\phi$ -function and factorization counting functions.
- The proof involves a detailed stratification of integers based on their prime factorization properties.
- It utilizes multiplicative compositions (ordered factorizations) and bounds on the number of such compositions, denoted $g_w(n)$ .
- Key lemmas establish that for a set of integers $S$ with density $x^{1-\beta}$ , the sum of multiplicative compositions is bounded by $x/\mathcal{L}(x)^\beta$ .
- The argument reduces the problem to counting squarefree integers and uses the Brun-Titchmarsh inequality and properties of the radical of integers to bound the number of $n$ where $\phi(n)/\lambda(n)$ falls into specific dyadic intervals.

Key Results
The main result is Theorem 1.1, which provides an upper bound for $L(x, y)$ in the specified domain. Let $\mathcal{L}(x) = \exp\left(\frac{\log x \log_3 x}{\log_2 x}\right)$ . As $x \to \infty$ :
$\frac{L(x, y)}{x} \le \begin{cases} \mathcal{L}(x/y)^{-1+o(1)} & \text{if } y \ge \mathcal{L}(x)^2, \\ \mathcal{L}(x, y)^{-1+o(1)} & \text{otherwise.} \end{cases}$
The paper asserts that under Hypothesis U, these upper bounds are asymptotically sharp (i.e., equality holds).

Application to Multiplicative Orders
As a direct application, the paper derives Corollary 1.2, which provides a new upper bound on the count of odd integers $n \le x$ for which the multiplicative order of 2 modulo $n$ , denoted $l(n)$ , is small.
Specifically, for any fixed $\delta > 0$ and $\beta \ge 0$ :
$\#\{ \text{odd } n \le x : l(n) \le x^\beta \} \le \frac{x}{\mathcal{L}(x)^{\frac{1}{2} - \beta - \delta}}$
This result improves upon previous knowledge, which could not establish non-trivial bounds for exponents $\beta$ significantly below $1/2$ . The author notes that while the exponent $1/2 - \beta$ appears in the bound, the "correct" version likely involves $1 - \beta$ , a refinement that would require further work on the distribution of primes with small multiplicative orders.

Significance and Claims
The paper claims to provide the first precise asymptotic upper bounds for the distribution of intermediate values of $\lambda(n)$ . The significance lies in:

Bridging the Gap: It fills the gap between the typical order and the minimal order of $\lambda(n)$ , a regime previously unquantified in the literature.
Sharpness: The results are shown to be asymptotically sharp under a plausible hypothesis (Hypothesis U) concerning the smoothness of shifted primes, a conjecture supported by heuristic principles and related work on pseudoprimes.
Methodological Novelty: The proof of the upper bound for large $y$ introduces refined techniques involving multiplicative compositions and factorization counting, which the author suggests may have applications to other problems in analytic number theory, such as the distribution of popular values of Euler's $\phi$ -function.
Application to Orders: The corollary regarding $l(n)$ offers the strongest known upper bounds for the frequency of small multiplicative orders, addressing a long-standing limitation in the field where the exponent $1/2$ was previously a barrier.

The author maintains a modest tone regarding the conditional nature of the lower bounds and the potential for improving the exponent in the application to $l(n)$ , noting that current knowledge does not yet permit proving the "correct" exponent without further conjectures.