🔢 mathematics

Exceptional sets for compositions involving Euler's function,the divisor-sum function and Dedekind's function

This paper establishes quantitative upper bounds and density-zero estimates for exceptional sets of integers involving compositions of Euler's totient, Dedekind's, and the sum-of-divisors functions, thereby refining previous density results by Sandor, Dixit, and Bhattacharjee.

Original authors: Aimin Guo

Published 2026-08-21

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Aimin Guo

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

In the vast landscape of number theory, mathematicians often study how numbers behave when they are broken down into their building blocks. Three specific tools are used to measure these properties. The first tool is a variation of the sum of divisors, adding a specific twist to how those divisors are calculated to create a slightly different profile for each number. The second tool counts how many smaller numbers can fit into a given number without leaving a remainder, a measure of its internal structure. The third tool adds up all the divisors of a number, giving a sense of its total weight in the world of factors. While these tools work well on their own, mathematicians have long been curious about what happens when they are stacked on top of one another. If you take a number, apply one tool, and then immediately apply a different tool to the result, does the final number stay close to the original, or does it drift far away? This question of how these functions interact when composed is the heart of a new study that seeks to map the rare exceptions where these mathematical relationships break their usual patterns.

For decades, a specific conjecture suggested that when you apply the second tool to the result of the first tool for any number greater than one, the result would always be smaller than the starting number. It was a tidy, predictable rule that seemed to hold for the first ten thousand numbers checked. However, this rule was eventually proven false. A specific counterexample was found at the number 39,270, where the process actually produced a result larger than the original. While this single exception shattered the idea of a universal rule, the new research confirms that such exceptions are incredibly rare. The study demonstrates that as you look at larger and larger collections of numbers, the proportion of those that violate the expected behavior becomes vanishingly small. In fact, the researchers have calculated precise limits on how many such outliers can exist within any given range, showing that the vast majority of numbers still follow the expected trend, even if the rule is not absolute.

The paper focuses on four specific combinations of these mathematical tools. The researchers investigated what happens when the second tool is applied to the result of the first, when the second tool is applied to the sum of divisors, when the first tool is applied to itself, and when the first tool is applied to the sum of divisors. For the first two combinations, the team established strict upper limits on the number of integers that produce unusually large results. They found that the number of these "exceptional" cases grows much more slowly than the total number of integers being examined. Specifically, they improved upon previous estimates by showing that the count of these rare numbers is significantly lower than earlier mathematicians had predicted, refining the understanding of how quickly these anomalies disappear as numbers get larger.

The study also looked at the cases where the results were unusually small. When the first tool is applied twice, or when it is applied to the sum of divisors, the researchers proved that the number of integers resulting in a value smaller than a fixed fraction of the original is also negligible. They showed that these sets of numbers are so sparse that they effectively disappear from the landscape of all integers as the range expands. This was achieved by developing a method to count how many numbers avoid having certain small prime factors, a technique that allowed the team to bound the size of these exceptional groups with high precision.

Beyond these fixed limits, the researchers explored a more flexible scenario where the threshold for what counts as an "exception" is allowed to change slowly as the numbers get larger. Even with this added complexity, the results held firm. The study confirmed that as long as the threshold grows at a moderate pace, the number of integers that fail to meet the condition remains a tiny fraction of the total. This suggests a robust underlying order in how these arithmetic functions interact, where deviations from the norm are not just rare, but mathematically constrained to be almost non-existent in the grand scheme of things. The work does not claim to have found the absolute best possible limits, acknowledging that there may be room for further refinement, but it provides a much sharper and more accurate picture of the behavior of these composed functions than was previously available.

Technical Summary: Exceptional Sets for Compositions Involving Euler's Function, the Divisor-Sum Function, and Dedekind's Function

Problem Statement
This paper investigates the distribution of integers $n$ for which specific compositions of classical arithmetic functions deviate significantly from their expected magnitude. Specifically, the author studies "exceptional sets" where the values of $\phi(\psi(n))$ , $\phi(\sigma(n))$ , $\psi(\psi(n))$ , and $\psi(\sigma(n))$ are either unusually large or unusually small relative to $n$ .

Here, $\phi(n)$ is Euler's totient function, $\psi(n)$ is Dedekind's arithmetic function, and $\sigma(n)$ is the sum-of-divisors function. While these functions are multiplicative, their compositions generally lose this property, rendering classical theories of multiplicative functions inapplicable. The study focuses on refining qualitative density-zero results (established by Sándor and others) into quantitative upper bounds for the size of these exceptional sets.

Methodology
The proofs rely on three primary analytical ingredients:

Product Estimates over Primes: Utilizing asymptotic formulas for products of the form $\prod (1 \pm 1/p)$ to bound the values of the functions.
Sieve Estimates: Applying sieve methods to estimate the proportion of integers free of specific prime factors. A key component is Lemma 2.4, which establishes an upper bound for the number of integers $n \le x$ such that a prescribed prime $p$ does not divide $\psi(n)$ . This adapts sieve arguments previously used by Dixit and Bhattacharjee.
Small Prime Divisor Results: Leveraging existing results (Guo et al., Sándor) stating that for almost all $n$ , $\psi(n)$ , $\sigma(n)$ , and $\phi(n)$ are divisible by all small prime powers up to a threshold of roughly $c \frac{\log_2 x}{\log_3 x}$ .

The general strategy involves:

Defining an exceptional set $E(x)$ of size $O(x/(\log_3 x)^2)$ where the small prime divisor property fails.
For $n \notin E(x)$ , using the divisibility of $\psi(n)$ or $\sigma(n)$ by small primes to bound the composition from above or below.
Applying Markov's inequality to the resulting inequalities (e.g., $\psi(n)/n > c \log y_x$ ) to bound the count of integers satisfying the condition.
Using partial summation on known asymptotic formulas for $\sum \psi(n)$ and $\sum \sigma(n)$ .

Key Contributions and Results

1. Quantitative Refinements for $\phi(\psi(n))$ and $\phi(\sigma(n))$
The paper provides explicit upper bounds for the number of integers $n \le x$ satisfying $\phi(\psi(n)) \ge cn$ and $\phi(\sigma(n)) \ge cn$ for a fixed $c > 0$ .

Result for $\phi(\psi(n))$ : The count is bounded by $\left(\frac{15}{\pi^2 c} + o(1)\right) \frac{x}{\log_3 x}$ . This refines Sándor's qualitative density-zero result.
Result for $\phi(\sigma(n))$ : The count is bounded by $\left(\frac{\pi^2}{6c} + o(1)\right) \frac{x}{\log_3 x}$ . This improves upon the result of Dixit and Bhattacharjee, who obtained a bound of order $x/\log^4 x$ ; the current work improves the order to $x/\log^3 x$ .

2. Variable Thresholds
The author generalizes the fixed threshold $c$ to non-decreasing functions $g(n)$ and $h(n)$ satisfying $g(x), h(x) = o(\log_3 x)$ .

The size of the set $\{n \le x : \phi(\psi(n)) \ge n/g(n)\}$ is shown to be $O\left(\frac{x}{g(x) \log_3 x}\right)$ .
Similarly, the set $\{n \le x : \phi(\sigma(n)) \ge n/h(n)\}$ is bounded by $O\left(\frac{x}{h(x) \log_3 x}\right)$ .
Both results confirm that these sets have density zero.

3. Lower Bounds for Iterates of $\psi$
The paper establishes quantitative density-zero estimates for integers where the second iterate of Dedekind's function is small: $\psi(\psi(n)) \le cn$ and $\psi(\sigma(n)) \le cn$ .

Result: For a fixed $c > 0$ , there exists a constant $z_c$ such that the count is $\ll_c x \left(\frac{\log_2 x}{\log x}\right)^{1/z_c}$ .
This implies the sets have density zero. The proof relies on showing that if $\psi(\psi(n)) \le cn$ , then $\psi(n)$ must lack a product of small primes, an event with low probability derived from sieve estimates.
Corollary: This result extends to the $k$ -th iterate $\psi^{(k)}(n)$ for any fixed $k \ge 2$ .

Significance and Claims
The paper claims to provide quantitative refinements of previously known qualitative results.

It corrects the order of magnitude for the upper bound of the exceptional set associated with $\phi(\sigma(n))$ , moving from $x/\log^4 x$ to $x/\log^3 x$ .
It establishes the first quantitative estimates for the exceptional sets involving $\psi(\psi(n))$ and $\psi(\sigma(n))$ being small.
The author explicitly notes in the concluding remarks that the derived upper bounds are not claimed to be optimal. The use of Markov's inequality on a superset of the target exceptional set introduces a potential loss in precision.

The work is situated within the broader context of studying compositions and iterates of arithmetic functions, building on the foundational work of Alaoglu, Erdős, Granville, Pomerance, Spiro, Sándor, and others. It clarifies the frequency of "exceptional" behavior in these composite functions, demonstrating that while counterexamples to inequalities like $\phi(\psi(n)) \le n$ exist (e.g., $n=39270$ ), they are sparse.

Technical Summary: Exceptional Sets for Compositions Involving Euler's Function, the Divisor-Sum Function, and Dedekind's Function

More like this