🔢 mathematics

Sign changes of the Liouville function in arithmetic progressions

This paper proves that for any sufficiently large prime $q$ and any residue class $a$ coprime to $q$ , the Liouville function $\lambda$ takes both values $+1$ and $-1$ within the arithmetic progression $a \pmod{q}$ for integers up to $q^{5/2 + \varepsilon}$ .

Original authors: Kevin Ford, Maksym Radziwiłł

Published 2026-05-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Kevin Ford, Maksym Radziwiłł

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

Imagine you are organizing a massive, infinite line of numbered lockers, starting from 1 and going up forever. Each locker contains a secret code: either a +1 or a -1. This code is determined by a special rule called the Liouville function (let's call it "The Switch").

The rule for The Switch is simple but tricky:

If a number is made of an even number of prime building blocks (like $6 = 2 \times 3$ , which has 2 blocks), the code is +1.
If a number is made of an odd number of prime building blocks (like $12 = 2 \times 2 \times 3$ , which has 3 blocks), the code is -1.

Usually, these codes flip back and forth randomly as you walk down the line. Sometimes you see a +1, then a -1, then a +1. It's like a coin toss.

The Big Question

Mathematicians have long been interested in a specific way of looking at these lockers: Arithmetic Progressions.

Imagine you only look at lockers that are spaced out by a specific distance, say every 7th locker (7, 14, 21, 28...). Or every 100th locker. The question is: How far do you have to walk down this specific line before you are guaranteed to see both a +1 and a -1?

If you stop too early, you might get lucky and find only +1s (or only -1s) by chance. The authors of this paper wanted to find the "safe distance"—the point where it becomes mathematically impossible to keep seeing only one sign.

The Previous Attempts

The Prime Number Problem: A famous mathematician, Dirichlet, proved that if you look at a specific line (like every 7th number), you will eventually find a prime number. But how big is that first prime?
The "Square Root" Barrier: For a long time, mathematicians thought the answer was related to the square of the spacing. If you skip by $q$ , you might need to go out to $q^2$ to find what you're looking for.
The Record Holder: A mathematician named Linnik proved that you don't need to go that far. He showed there is a constant $L$ such that you only need to go to $q^L$ . Over the years, people tried to make $L$ smaller. The current best record is $L=5$ , meaning you need to go out to $q^5$ .

What This Paper Does

Kevin Ford and Maksym Radziwiłł tackled a slightly different version of this problem. Instead of looking for primes, they are looking for sign changes in The Switch (the Liouville function).

They proved a new, stronger result:
If you pick any spacing $q$ (a prime number), and you look at lockers up to a distance of roughly $q^{2.5}$ (that is, $q$ to the power of 2.5), you are guaranteed to find both a +1 and a -1.

This is a huge improvement over the previous "prime number" record of $q^5$ . They cut the required distance down significantly.

How They Did It (The Detective Story)

The authors used a clever "proof by contradiction" strategy. Here is the analogy of their logic:

The Hypothetical Nightmare: They started by assuming the opposite of what they wanted to prove. They said: "Imagine a world where, for a very long distance (up to $q^{2.5}$ ), every single number in our specific line (e.g., numbers that are 3 mod 7) has the SAME sign. Let's say they are all +1."
The Ripple Effect: They showed that if this "all +1" nightmare were true, it would force the entire universe of numbers to behave in a very rigid, unnatural way.
- It would mean the Switch isn't random at all; it would have to follow a strict, repeating pattern (periodicity) that mimics a specific mathematical shape called a "Legendre symbol."
- Essentially, the randomness of the numbers would have to vanish and become a perfect, predictable dance.
The Trap: They then showed that this "perfect dance" is impossible.
- The First Trap: If the pattern were one way, the number of primes would be all wrong (too few).
- The Second Trap: If the pattern were the other way, it would violate a famous mathematical law (Siegel's Theorem) about how these numbers distribute.
The Conclusion: Since the "all +1" (or "all -1") assumption leads to a mathematical contradiction, the assumption must be false. Therefore, the signs must change within that distance.

A Note on "Magic"

The paper mentions one catch. While they proved the distance is roughly $q^{2.5}$ , their proof relies on a mathematical tool (Siegel's Theorem) that is like a "black box." It tells us the result is true, but it doesn't give us a specific number for how "large" $q$ needs to be before this rule kicks in. It's like knowing a bridge is safe, but not knowing exactly how many cars it can hold until you build it.

Summary

In simple terms: The authors proved that if you look at a specific sequence of numbers spaced out by a prime number $q$ , you don't have to walk very far (only up to $q^{2.5}$ ) to see the "switch" flip from positive to negative. If you didn't see a flip by then, the entire structure of mathematics would break.

Technical Summary: Sign Changes of the Liouville Function in Arithmetic Progressions

Problem Statement
The paper addresses a multiplicative function analogue to Linnik's theorem on the least prime in an arithmetic progression. While Linnik's theorem guarantees the existence of a prime $p \equiv a \pmod q$ with $p \ll q^L$ (currently $L=5$ ), this work investigates the distribution of the Liouville function $\lambda(n)$ within arithmetic progressions. Specifically, the authors ask: for a prime modulus $q$ and a reduced residue class $a \pmod q$ , how large must $N$ be to guarantee the existence of integers $n, m \le N$ such that $n \equiv m \equiv a \pmod q$ , yet $\lambda(n) = -1$ and $\lambda(m) = +1$ ? In other words, at what scale does the Liouville function necessarily change signs within a fixed arithmetic progression?

Methodology
The proof proceeds by contradiction. The authors assume that for a sufficiently large prime $q$ , the Liouville function maintains a constant sign $\kappa \in \{-1, +1\}$ for all $n \equiv a \pmod q$ with $n \le q^{5/2+\varepsilon}$ . The argument is structured into three main phases:

Periodicity and Balance via Combinatorial Arguments:
Using Lemma 7, the authors show that if $\lambda(n)$ is constant on a progression up to $N \ge q^{2+\varepsilon}$ , then $\lambda(n)$ must be $q$ -periodic for $n \le N/q$ (specifically $\lambda(n+q) = \lambda(n)$ for $(n,q)=1$ ). Furthermore, this assumption forces the sum of $\lambda(n)$ over reduced residues modulo $q$ to be exactly zero. This step relies on combinatorial set theory (Lemma 6, a pigeonhole principle application) to show that if the counts of $+1$ and $-1$ values in an interval of length $q$ were unbalanced, one could construct products of integers in the progression that violate the constant sign hypothesis.
Approximation by a Dirichlet Character:
Assuming the periodicity and zero-sum conditions hold, Lemma 8 utilizes the large sieve inequality and Poisson summation to demonstrate that $\lambda(n)$ must essentially coincide with a real Dirichlet character $\chi_q$ (the Legendre symbol) scaled by a constant $\kappa' \in \{-1, 1\}$ . Specifically, $\lambda(n) = \kappa' \chi_q(n)$ for all $n \le q$ , with at most $O(q^{1-\varepsilon/4})$ exceptions.
Elimination of the Two Cases:
The proof concludes by ruling out both possible values for $\kappa'$ :
- Case $\kappa' = -1$ : If $\lambda(n) \approx -\chi_q(n)$ , the authors analyze the distribution of primes $p \le q^{1/2}$ where $\chi_q(p) = \pm 1$ . By considering products of such primes, they show that the number of exceptions required to satisfy the hypothesis would contradict the known density of primes (via the Prime Number Theorem).
- Case $\kappa' = +1$ : If $\lambda(n) \approx \chi_q(n)$ , the authors construct a multiplicative function $g(n) = \sum_{d|n} \chi_q(d)$ . They show that under this hypothesis, $g(n)$ vanishes for most non-square integers. However, using Lemma 5 (Mellin inversion) and Siegel's lower bound for $L(1, \chi_q)$ (Lemma 3), they derive a lower bound for the sum $\sum g(n)W(n/q)$ that contradicts the upper bound derived from the vanishing property.

Key Results
The main theorem (Theorem 1) establishes that for any $\varepsilon > 0$ , and for any prime $q$ sufficiently large with respect to $1/\varepsilon$ , and any residue class $(a, q)=1$ , there exist integers $n, m \le q^{5/2+\varepsilon}$ such that $n \equiv m \equiv a \pmod q$ with $\lambda(n) = -1$ and $\lambda(m) = +1$ .

Significance and Limitations
The authors position this result as a significant step in understanding the sign changes of multiplicative functions in arithmetic progressions. The bound $q^{5/2+\varepsilon}$ improves upon previous unconditional results for general multiplicative functions and matches the quality of results previously known only under the Generalized Riemann Hypothesis (GRH) for specific cases.

The paper explicitly notes a limitation regarding the effectiveness of the result: unlike Linnik's theorem, where the exponent and implied constants are effectively computable, the argument here relies on Siegel's theorem. Consequently, the threshold for $q$ being "sufficiently large" in terms of $1/\varepsilon$ is uncomputable.

The authors distinguish their approach from concurrent work by Matomäki and Teräväinen [7], which achieves a stronger bound of $q^{2+\varepsilon}$ for general real-valued multiplicative functions (unconditionally for the Liouville function). The authors emphasize that their argument is short and proceeds along different lines, specifically utilizing the interplay between the large sieve, Poisson summation, and the specific properties of the Liouville function to derive the $q^{5/2}$ threshold.