Kvant Math Problem 795

Consider small values of $n$ and their divisor sums $\sigma(n)$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 3m19s
Source on kvant.digital

Problem

Let $\sigma (n)$ denote the sum of all divisors of the natural number $n$ (Fig. 3). Prove that there exist infinitely many $n$ such that

  1. $\sigma(n)\gt 2n$;
  2. $\sigma(n)\gt 3n$.

Prove that for any $n$

  1. $\sigma(n)\lt n(\log_2n+2)$;
  2. $\sigma(n)\lt n(\ln n+1)$.

Figure 3

V. F. Lev

Exploration

Consider small values of $n$ and their divisor sums $\sigma(n)$. For prime $p$, $\sigma(p) = 1 + p$, which is less than $2p$, so primes do not satisfy the first condition. For $n = 6$, $\sigma(6) = 1 + 2 + 3 + 6 = 12 = 2 \cdot 6$, reaching equality in the first case. For powers of $2$, $n = 2^k$, we have $\sigma(2^k) = 1 + 2 + 4 + \dots + 2^k = 2^{k+1} - 1 < 2^{k+1} = 2n$, so no power of $2$ alone works. Consider numbers of the form $2^k \cdot 3$; for $k = 1$, $2 \cdot 3 = 6$, which we already observed. Increasing $k$, $\sigma(2^k \cdot 3) = (1 + 2 + 4 + \dots + 2^k)(1 + 3) = (2^{k+1} - 1) \cdot 4 = 4 \cdot 2^{k+1} - 4$. Compare to $2n = 2 \cdot 2^k \cdot 3 = 2^{k+1} \cdot 3 = 3 \cdot 2^{k+1}$. Then $\sigma(n) - 2n = (4 \cdot 2^{k+1} - 4) - 3 \cdot 2^{k+1} = 2^{k+1} - 4$, positive for $k \ge 2$. Thus infinitely many $n$ exist with $\sigma(n) > 2n$. A similar construction can be attempted for $\sigma(n) > 3n$, possibly using numbers of the form $2^k \cdot 3^m$ with sufficiently large $k$ or $m$.

For upper bounds, note that $\sigma(n)$ is multiplicative: if $n = p_1^{a_1} \cdots p_k^{a_k}$, then $\sigma(n) = \prod_{i=1}^k \frac{p_i^{a_i + 1} - 1}{p_i - 1} < \prod_{i=1}^k \frac{p_i^{a_i + 1}}{p_i - 1} = n \prod_{i=1}^k \frac{p_i}{p_i - 1}$. Bounding each factor by $\frac{p}{p-1} \le 1 + \frac{1}{p}$ and estimating the product gives a connection to $\log_2 n$ and $\ln n$. These heuristics suggest the stated inequalities hold, but a precise argument requires careful estimation of the products.

The crucial step likely to fail is establishing $\sigma(n) > 3n$ for infinitely many $n$ without overestimating the contribution from small primes. Similarly, the upper bounds must carefully control the contribution of each prime factor to avoid underestimating $\sigma(n)$.

Problem Understanding

The problem requires proving four claims: two about the existence of infinitely many $n$ with large divisor sums and two general upper bounds for $\sigma(n)$. The first pair is a Type D problem, existence; the second pair is a Type B problem, a general inequality. The core difficulty in the existence claims is constructing an explicit infinite family that exceeds the given multiples of $n$, and for the bounds, estimating the product of factors $\frac{p^{a+1} - 1}{p-1}$ in terms of $n$. The expected constructions are products of small primes with sufficiently large exponents. The answer is not a specific set but an explicit family of numbers for the existence claims.

Proof Architecture

Lemma 1: If $n = 2^k \cdot 3$, then $\sigma(n) = (2^{k+1} - 1)(1 + 3) = 4 \cdot 2^{k+1} - 4$; for $k \ge 2$, $\sigma(n) > 2n$. Proof: expand the geometric series and subtract $2n$; check positivity for $k = 2$.

Lemma 2: If $n = 2^k \cdot 3^2$, then $\sigma(n) = (2^{k+1} - 1)(1 + 3 + 9) = (2^{k+1} - 1) \cdot 13$; for sufficiently large $k$, $\sigma(n) > 3n$. Proof: compute $\sigma(n) - 3n$ and find $k \ge 3$ suffices.

Lemma 3: For any $n$ with prime factorization $n = p_1^{a_1} \cdots p_k^{a_k}$, $\sigma(n) = \prod_{i=1}^k \frac{p_i^{a_i+1}-1}{p_i-1} < n \prod_{i=1}^k \frac{p_i}{p_i-1}$. Proof: factor each term as $\frac{p_i^{a_i+1}-1}{p_i-1} < \frac{p_i^{a_i+1}}{p_i-1}$.

Lemma 4: $\prod_{i=1}^k \frac{p_i}{p_i-1} \le \log_2 n + 2$ and $\le \ln n + 1$. Proof: estimate the product by splitting $p_i = 2$ and $p_i \ge 3$, using $\frac{p}{p-1} \le 1 + \frac{1}{p}$, then apply inequalities $\prod (1 + x_i) \le \exp(\sum x_i)$ and relate $\sum 1/p_i$ to $\log_2 n$ and $\ln n$.

The hardest step is Lemma 4, as it requires careful control of the product over all prime factors and connecting it to logarithmic functions of $n$.

Solution

For the first existence claim, consider $n = 2^k \cdot 3$. Then

$$\sigma(n) = \sigma(2^k) \cdot \sigma(3) = (1 + 2 + 4 + \dots + 2^k)(1 + 3) = (2^{k+1} - 1) \cdot 4 = 4 \cdot 2^{k} \cdot 2 - 4 = 2^{k+2} - 4.$$

Compute $2n = 2 \cdot 2^k \cdot 3 = 3 \cdot 2^{k+1}$. Then

$$\sigma(n) - 2n = (2^{k+2} - 4) - 3 \cdot 2^{k+1} = 2^{k+1} - 4.$$

This expression is positive for $k \ge 2$, giving an infinite family $n = 2^k \cdot 3$ with $\sigma(n) > 2n$.

For the second existence claim, consider $n = 2^k \cdot 3^2$. Then

$$\sigma(n) = \sigma(2^k) \cdot \sigma(3^2) = (2^{k+1} - 1)(1 + 3 + 9) = (2^{k+1} - 1) \cdot 13,$$

and $3n = 3 \cdot 2^k \cdot 9 = 27 \cdot 2^k$. Then

$$\sigma(n) - 3n = 13 \cdot 2^{k+1} - 13 - 27 \cdot 2^k = (26 - 27) \cdot 2^k - 13 = -2^k - 13.$$

This is negative for small $k$, so choose $n = 2^k \cdot 3^3$:

$$\sigma(n) = (2^{k+1} - 1)(1 + 3 + 9 + 27) = (2^{k+1} - 1) \cdot 40, \quad 3n = 3 \cdot 2^k \cdot 27 = 81 \cdot 2^k,$$

then $\sigma(n) - 3n = 40 \cdot 2^{k+1} - 40 - 81 \cdot 2^k = (80 - 81) \cdot 2^k - 40 = -2^k - 40$, still negative. To satisfy $\sigma(n) > 3n$, we need to increase the $2$-power more aggressively. Let $n = 2^6 \cdot 3^3 = 64 \cdot 27 = 1728$. Then $\sigma(2^6) = 2^7 - 1 = 127$, $\sigma(3^3) = 1 + 3 + 9 + 27 = 40$, so $\sigma(n)