On certain sums involving the largest prime factor over integer sequences

This paper derives asymptotic formulas for the sums of the smallest integer $f(n)$ such that $f(n)!$ is divisible by $n$, considering both all integers up to $x$ and the subset of $k$-free integers.

The Gist

Imagine you have a giant warehouse filled with boxes, numbered from 1 up to a massive number $x$. Inside each box is a secret code: a unique combination of prime numbers (the "atoms" of math) multiplied together to make that number.

For example, the number 12 is made of $2 \times 2 \times 3$. The number 30 is made of$2 \times 3 \times 5$.

The Game: "How Big a Party Do You Need?"

The paper introduces a character named $f(n)$. Think of $f(n)$ as the answer to a party planning question:

"What is the smallest number of people ($N$) I need to invite to a party so that if everyone shakes hands with everyone else (which mathematically creates a 'factorial' number of handshakes), the total number of handshakes is perfectly divisible by the number on the box?"

• If the box says 12 ($2 \times 2 \times 3$), you need a party of **4** people. Why? Because$4!$(4 factorial, or$4 \times 3 \times 2 \times 1 = 24$) is divisible by 12. A party of 3 people ($3! = 6$) isn't enough. So,$f(12) = 4$.
• If the box says 7 (a prime number), you need a party of 7 people. You can't get a multiple of 7 from a smaller group's handshakes. So, $f(7) = 7$.

The author, Mihoub Bouderbala, wants to know: If we add up the "party sizes" ($f(n)$) for every single box in the warehouse, what is the total?

The Two Main Questions

The paper tackles two specific scenarios:

1. The General Warehouse: Add up $f(n)$ for every number from 1 to $x$.
2. The "Square-Free" (or Cube-Free) Warehouse: Add up $f(n)$ only for numbers that don't have any repeated prime factors.
   • Analogy: Imagine a rule where you can't have a "double" ingredient. 12 ($2 \times 2 \times 3$) is banned because it has two 2s. But 30 ($2 \times 3 \times 5$) is allowed because all ingredients are unique. These are called **$k$-free numbers**.

The Big Discovery

The author found a surprisingly simple way to predict the total sum without having to count every single box.

1. The General Sum

When you add up the party sizes for all numbers up to $x$, the total grows roughly like this:
$$\text{Total} \approx \frac{\pi^2}{6} \times \frac{x^2}{\log x}$$
(Note: $\frac{\pi^2}{6}$ is a famous math constant called $\zeta(2)$, roughly 1.645).

The Analogy: Imagine the warehouse is a pyramid. The total sum isn't just a straight line; it's a massive curve that grows very fast (like $x^2$), but it's slightly slowed down by the "noise" of prime numbers (the $\log x$ part). The author proves that the "noise" doesn't change the main shape of the curve, just the fine details.

2. The "Special" Sum (k-free numbers)

When you only count the numbers with unique ingredients (no repeats), the total sum changes slightly. It becomes:
$$\text{Total} \approx \frac{(\pi^2/6)^2}{2 \times \zeta(2k)} \times \frac{x^2}{\log x}$$

The Analogy: It's like filtering the warehouse. You throw out all the boxes with "duplicates." The total sum gets smaller, but it still follows the same giant curve shape. The new formula just adjusts the "height" of the curve based on how strict the "no duplicates" rule is.

How Did They Figure It Out? (The Secret Sauce)

The author used a clever trick involving the Largest Prime Factor.

Think of any number as a tower built of blocks. The largest prime factor is the biggest block at the very top of the tower.

• If the tower is short (the number is small compared to the square of its biggest block), the "party size" $f(n)$ is exactly equal to that biggest block.
• If the tower is very tall and complex, the "party size" is still dominated by that biggest block, plus a little bit of extra work.

The author realized that for most numbers, the "party size" is basically just the size of the biggest prime block. By summing up the biggest prime blocks of all numbers (a problem mathematicians have studied before), they could easily predict the sum of the party sizes.

Why Does This Matter?

You might ask, "Who cares about party sizes for numbers?"

1. Understanding the DNA of Numbers: Just as biologists study how genes combine, mathematicians study how prime numbers combine. This paper helps us understand the "anatomy" of integers.
2. Predicting the Unpredictable: Prime numbers seem random, but they follow hidden laws. This paper shows that even complex functions like $f(n)$ settle into a predictable pattern when you look at them on a large scale.
3. The "Smooth" Connection: The paper links to "smooth numbers" (numbers with small prime factors). This has applications in cryptography and computer science, where understanding how numbers break down is crucial for security.

In a Nutshell

This paper is like a map for a massive, chaotic city of numbers. The author draws a line through the chaos and says, "Even though every number is unique, if you look at the whole city, the total 'effort' required to understand them all follows a beautiful, simple curve."

They proved that whether you look at all numbers or just the "clean" ones (without repeated factors), the total sum grows in a very specific, predictable way, governed by the famous number $\pi$ and the distribution of prime numbers.

Technical Summary

Here is a detailed technical summary of the paper "On Certain Sums Involving the Largest Prime Factor over Integer Sequences" by Mihoub Bouderbala.

1. Problem Statement

The paper investigates the asymptotic behavior of sums involving the function $f(n)$, defined as the smallest positive integer such that $f(n)!$ is divisible by $n$. Given an integer $n \ge 2$ with prime factorization $n = p_1^{a_1} p_2^{a_2} \cdots p_s^{a_s}$ (where $p_1 < p_2 < \dots < p_s$), the function $f(n)$ is intrinsically linked to the largest prime factor of $n$, denoted as $P(n) = p_s$.

The author aims to derive precise asymptotic formulas for two specific sums as $x \to \infty$:

1. The general sum: $\sum_{n \le x} f(n)$
2. The restricted sum over $k$-free integers: $\sum_{n \le x, n \in S_k} f(n)$, where $S_k$ is the set of integers $n$ such that no prime factor appears with an exponent $\ge k$ (i.e., $\max(a_i) < k$).

This work extends classical results on sums weighted by $P(n)$ (notably by Alladi and Erdős) to the function $f(n)$, exploring the arithmetic structure of factorial divisibility.

2. Methodology

The proof strategy relies on analytic number theory techniques, specifically the decomposition of the summation range based on the magnitude of the largest prime factor relative to $n$.

Key Definitions and Lemmas

• Lemma 1 (Crucial Identity): The author establishes that if $P(n)^2 > n$, then $f(n) = P(n)$.
  • Reasoning: If $P(n)^2 > n$, the largest prime $p_s$ must appear with exponent 1 ($a_s=1$), and all other prime factors are smaller than $p_s$. Consequently, $n$ divides $p_s!$, and since $p_s$ does not divide $(p_s-1)!$, $f(n)$ must be exactly $p_s$.
• Lemma 2 (Analytic Tool): A technical lemma providing an asymptotic estimate for sums of the form $\sum_{n \le x^{1/2}} \frac{\delta(n)}{n^2 \log(x/n)}$, where $\delta(n)$ is a bounded arithmetic function. This allows the conversion of discrete sums into expressions involving infinite series and Riemann zeta values.

Decomposition Strategy

The main sums are split into two parts based on the condition $P(n)^2 > n$:
$$\sum_{n \le x} f(n) = \sum_{\substack{n \le x \\ P(n)^2 \le n}} f(n) + \sum_{\substack{n \le x \\ P(n)^2 > n}} f(n)$$

1. The "Small" Part ($P(n)^2 \le n$):

   • The author uses the bound $f(n) \ll P(n) \log n$.
   • Since $P(n) \le n^{1/2}$ in this region, the sum is bounded by $\sum n^{1/2} \log n$, which is shown to be $O(x^{3/2} \log x)$. This is a lower-order error term compared to the main term $x^2/\log x$.

2. The "Large" Part ($P(n)^2 > n$):

   • By Lemma 1, $f(n) = P(n)$ in this region.
   • The sum is rewritten as $\sum_{mp \le x, p^2 > mp} p$. This is re-indexed by iterating over $m$ (the cofactor) and $p$ (the prime).
   • The condition $p^2 > mp$ implies $m < p$. The summation is split into ranges for $m$ and $p$, utilizing the Prime Number Theorem ($\pi(x) \sim x/\log x$) and Abel's summation formula.
   • The resulting double sums are evaluated using Taylor expansions and the convergence of series involving $1/n^2$.

3. Key Contributions and Results

Theorem 1: Asymptotic for the General Sum

The paper proves that for $x \ge 1$:
$$\sum_{n \le x} f(n) = \frac{\zeta(2) x^2}{\log x} + O\left(\frac{x^2}{\log^2 x}\right)$$

• Significance: The main term involves $\zeta(2) = \pi^2/6$. This result parallels the Alladi-Erdős result for $\sum P(n)$ but yields a different constant factor due to the specific nature of $f(n)$ and the density of integers where $P(n)^2 > n$.

Theorem 2: Asymptotic for $k$-Free Integers

For any integer $k \ge 2$, the sum over $k$-free integers is:
$$\sum_{\substack{n \le x \\ n \in S_k}} f(n) = \frac{\zeta^2(2)}{2\zeta(2k)} \frac{x^2}{\log x} + O\left(\frac{x^2}{\log^2 x}\right)$$

• Derivation: The proof utilizes the generating function for $k$-free numbers, $\sum \frac{\delta_k(n)}{n^s} = \frac{\zeta(s)}{\zeta(ks)}$.
• Significance: The constant term depends on the ratio of zeta values $\frac{\zeta^2(2)}{2\zeta(2k)}$. As $k \to \infty$, the set $S_k$ approaches all integers, and the constant converges to $\zeta(2)$, consistent with Theorem 1.

4. Significance and Implications

• Connection to Integer Anatomy: The results deepen the understanding of the "anatomy" of integers by linking factorial divisibility ($f(n)$) directly to the distribution of their largest prime factors.
• Extension of Classical Results: The paper successfully adapts the methodology used for sums of $P(n)$ to the more complex function $f(n)$, demonstrating that despite the non-multiplicative nature of $f(n)$, its average order is dominated by the same structural constraints as $P(n)$.
• Role of Zeta Functions: The appearance of $\zeta(2)$ and $\zeta(2k)$ highlights the underlying Euler product structure governing these sums, suggesting potential links to Dirichlet series and $L$-functions associated with factorial divisibility.
• Generalizability: The author notes in Remark 1 that the developed methods can be extended to higher moments ($\sum f(n)^r$), predicting asymptotic forms of the shape $C_r x^{r+1} / (\log x)^r$.

Conclusion

Mihoub Bouderbala provides rigorous asymptotic formulas for sums of $f(n)$ over all integers and $k$-free integers. By leveraging the condition $P(n)^2 > n$ to simplify $f(n)$ to $P(n)$, and employing advanced analytic techniques (Abel summation, Prime Number Theorem, and properties of the Riemann zeta function), the paper establishes that the dominant term for these sums is of order $x^2/\log x$, with explicit constants derived from zeta values. This work bridges the gap between factorial divisibility problems and the distribution of prime factors.