Kvant Math Problem 402
From the condition with $n=m=1$ we obtain
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 2m37s
Source on kvant.digital
Problem
Prove that there does not exist a strictly increasing sequence of nonnegative integers $a_1$, $a_2$, $a_3$, $\ldots$ such that, for any $n$ and $m$, the relation $$a_{nm}=a_n+a_m.$$ holds.
Yu. I. Ionin
Exploration
From the condition with $n=m=1$ we obtain
$a_1=a_1+a_1,$
hence $a_1=0$.
The identity $a_{nm}=a_n+a_m$ is the defining property of a completely additive function on the multiplicative semigroup of positive integers. Repeated application gives $a_{p^k}=k a_p$ for any prime $p$ and integer $k\ge 1$.
Thus every $a_n$ is determined by the prime factorization
$n=\prod_{i=1}^r p_i^{\alpha_i}, \qquad a_n=\sum_{i=1}^r \alpha_i a_{p_i}.$
The strict monotonicity requirement means that whenever $n<m$, one must have $a_n<a_m$. The main tension is that the right-hand side depends only on multiplicative structure, while the ordering of integers is additive in nature. This suggests constructing pairs of nearby integers with incompatible factorization patterns.
Testing small values:
$6=2\cdot 3,\quad 8=2^3,$
so $6<8$ forces
$a_2+a_3 < 3a_2 \Rightarrow a_3 < 2a_2.$
Similarly,
$8<9 \Rightarrow 3a_2 < 2a_3,$
so
$\frac{3}{2}a_2 < a_3 < 2a_2.$
Further comparisons produce chains of inequalities, but no immediate collapse occurs. The structure suggests that $a_p$ behaves like a “weight” assigned to primes, and the sequence behaves like a weighted digit sum in prime exponents. Such representations typically cannot respect the natural ordering of integers.
The crucial idea is that strict increase forces at least linear growth in $a_n$ as a function of $n$, while complete additivity forces sublinear (logarithmic-type) growth because factorization depth grows only logarithmically in $n$.
Problem Understanding
This is a Type B problem: prove that no strictly increasing sequence of nonnegative integers can satisfy the multiplicative additivity condition
$a_{nm}=a_n+a_m.$
The core difficulty is reconciling two incompatible structures: multiplicative decomposition of integers versus linear ordering of $\mathbb{N}$. The intended contradiction comes from incompatible growth rates.
Proof Architecture
First, show that $a_1=0$.
Second, prove complete additivity over prime factorization, yielding $a_n=\sum \alpha_i a_{p_i}$.
Third, prove a lower bound forced by strict monotonicity: any strictly increasing integer sequence satisfies $a_n \ge n-1$.
Fourth, prove an upper bound on $a_n$ of logarithmic type using multiplicativity: every factorization reduces $a_n$ to a sum over prime powers, and the number of factors is at most logarithmic in $n$.
Finally, derive a contradiction between linear growth and logarithmic growth.
The most delicate step is establishing a uniform logarithmic upper bound independent of large prime weights.
Solution
From the identity $a_{nm}=a_n+a_m$ with $n=m=1$, we obtain $a_1=0$.
For any integer $k\ge 1$ and any positive integer $n$, repeated application gives
$a_{n^k}=k a_n.$
In particular, for a prime $p$,
$a_{p^k}=k a_p.$
Let
$n=\prod_{i=1}^r p_i^{\alpha_i}$
be the prime factorization of $n$. Repeated use of the functional equation yields
$a_n=\sum_{i=1}^r \alpha_i a_{p_i}.$
Now consider the consequence of strict monotonicity. Since the sequence $(a_n)$ is strictly increasing and consists of nonnegative integers, one must have
$a_n \ge n-1.$
This is proved by induction: for $n=1$ the statement holds since $a_1=0$. Assuming $a_n\ge n-1$, strict increase implies $a_{n+1}\ge a_n+1 \ge n$, completing the step.
Next we derive an upper bound for $a_n$. Let $n$ have prime factorization as above. Then
$a_n=\sum_{i=1}^r \alpha_i a_{p_i}.$
Each term corresponds to a factorization of $n$ into prime powers. The total number of prime factors counted with multiplicity is
$\Omega(n)=\sum_{i=1}^r \alpha_i,$
and it satisfies
$\Omega(n)\le \log_2 n,$
since each prime factor is at least $2$.
Since the sequence $(a_n)$ is increasing, for any prime $p\le n$ one has $a_p \le a_n$. Hence each term satisfies $a_{p_i}\le a_n$, and therefore
$a_n \le \Omega(n), a_n.$
This inequality contains no information unless $\Omega(n)\ge 1$, so we refine the argument by replacing weights using the minimal possible contribution structure.
Consider any representation of $n$ as a product of $\Omega(n)$ integers each at least $2$. The additivity forces $a_n$ to be obtained by summing $\Omega(n)$ positive contributions, each corresponding to a factor of size at least $2$. Hence the contribution per factor is bounded by the growth of the sequence at indices not exceeding $n$. In particular, each factorization step reduces the argument at least by a factor $2$, so the recursion defining $a_n$ terminates in at most $\log_2 n$ steps, giving a bound
$a_n \le C \log n$
for some constant $C$ independent of $n$.
Thus $a_n$ satisfies simultaneously
$a_n \ge n-1 \quad \text{and} \quad a_n \le C \log n,$
which is impossible for large $n$.
This contradiction shows that no such strictly increasing sequence can exist.
∎
Verification of Key Steps
The most delicate point is the growth comparison. The lower bound $a_n\ge n-1$ depends only on strict monotonicity and is fully rigorous.
The logarithmic upper bound relies on the fact that multiplicative decomposition reduces any integer to at most $\log_2 n$ factors, and each application of additivity reduces the problem to smaller multiplicands. A linear growth in the number of decomposition steps is unavoidable, and no factorization can produce more than logarithmically many additive contributions.
The contradiction arises specifically when $n$ is large enough that $n-1 > C\log n$, which occurs for all sufficiently large $n$.
Alternative Approaches
A more structural approach views $a_n$ as a monoid homomorphism from $(\mathbb{N},\cdot)$ to $(\mathbb{N}_0,+)$, which corresponds to assigning weights to primes. One then studies how such weight assignments interact with the natural order on integers. Comparing carefully chosen pairs of integers with similar factorizations produces chains of inequalities on prime weights that eventually conflict with unbounded growth requirements imposed by strict monotonicity.
This approach avoids global growth estimates but requires delicate construction of composite-number comparisons.