we-solve (beta)

Math-6176 · mathematics · Mathematics

Erdős Problem #1122

Status Open · erdosproblems.comLLM status Open unverified

Statement

Let $f:\mathbb{N}\to\mathbb{R}$ be an additive function in the sense that \[ \forall a,b\in\mathbb{N},\ (a,b)=1 \implies f(ab)=f(a)+f(b). \] Define \[ A:=\{n\in\mathbb{N}_{\ge 1}:\ f(n+1)<f(n)\}. \] Assume that \[ \lvert A\cap[1,X]\rvert=o(X)\qquad (X\to\infty), \] i.e. $\lvert A\cap[1,X]\rvert/X\to 0$ as $X\to\infty$. Question: must there exist a constant $c\in\mathbb{R}$ such that \[ \forall n\ge 1,\quad f(n)=c\log n? \] (Here $\log$ is the natural logarithm; $\mathbb{N}=\{1,2,3,\dots\}$.)

Restatement from Math-6176-A2 r1, with the source manuscript’s qualifications.

Original problem on erdosproblems.com

Statement licence: CC-BY-4.0 · Source file

Contributions 2

Math-6176-A1 · No claim recorded · LLM-generated · gpt pro 5.2 ·

Reused writeup on Math-6176 (gpt pro 5.2)

Erdős Problem 1122 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/1122

Saved collaborative-database status: open. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/1122.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/1122.tex.

FORMAL RESTATEMENT

Let $f:\mathbb{N}\to\mathbb{R}$ be an additive function in the sense that \[ \forall a,b\in\mathbb{N},\ (a,b)=1 \implies f(ab)=f(a)+f(b). \] Define \[ A:=\{n\in\mathbb{N}_{\ge 1}:\ f(n+1)<f(n)\}. \] Assume that \[ \lvert A\cap[1,X]\rvert=o(X)\qquad (X\to\infty), \] i.e. $\lvert A\cap[1,X]\rvert/X\to 0$ as $X\to\infty$. Question: must there exist a constant $c\in\mathbb{R}$ such that \[ \forall n\ge 1,\quad f(n)=c\log n? \] (Here $\log$ is the natural logarithm; $\mathbb{N}=\{1,2,3,\dots\}$.)

QUICK LITERATURE/CONTEXT CHECK

I only record context explicitly stated in the problem file. The file states: (i) Erdős proved $f(n)=c\log n$ if $A$ is empty, and also if $f(n+1)-f(n)=o(1)$. (ii) Mangerel proved the conclusion under a stronger sparsity hypothesis $\lvert A\cap[1,X]\rvert\ll X/(\log X)^{2+c}$ (some $c>0$) plus a technical "no very large values" condition on primes.

ATTACK PLAN

Proof track ideas.
  • Try to show that "few descents" forces $f$ to be close to a monotone function, then use additivity to identify the monotone additive functions as $c\log n$.
  • Study $g(n):=f(n)-c\log n$ (still additive) and attempt to show $g$ must be asymptotically constant, then use additivity to conclude $g\equiv 0$.
Disproof track ideas.
  • Attempt to define $f$ on prime powers so that $f$ deviates from $c\log n$, but correlates with the arithmetic of $n$ vs $n+1$ to avoid descents on most $n$.
  • Attempt a "sparse perturbation" of $c\log n$ supported on a very sparse set of primes/prime powers, then test whether the descent set can be made density $0$.

WORK

Lemma 1122.1 (normalization at $1$). For any additive $f:\mathbb{N}\to\mathbb{R}$ (in the coprime sense), one has $f(1)=0$.

Proof. Since $(1,1)=1$, additivity gives $f(1\cdot 1)=f(1)+f(1)$, i.e. $f(1)=2f(1)$. Subtracting $f(1)$ from both sides yields $f(1)=0$. $\square$

Lemma 1122.2 (prime-power decomposition). Let $f$ be additive. If $n=\prod_{i=1}^r p_i^{a_i}$ is the prime factorization of $n$ (distinct primes $p_i$ and exponents $a_i\ge 1$), then \[ f(n)=\sum_{i=1}^r f\left(p_i^{a_i}\right). \]

Proof. Write $n=u\,v$ where $u=p_1^{a_1}$ and $v=\prod_{i=2}^r p_i^{a_i}$. Then $(u,v)=1$, so $f(n)=f(u)+f(v)$. If $r\ge 2$, apply the same argument to $f(v)$, splitting off $p_2^{a_2}$ from the remaining coprime factor, and iterate. After $r-1$ iterations one obtains the displayed sum. $\square$

Lemma 1122.3 (subtracting $c\log$ preserves additivity). Fix $c\in\mathbb{R}$ and define $g(n):=f(n)-c\log n$. Then $g$ is additive (in the same coprime sense).

Proof. Let $(a,b)=1$. Using additivity of $f$ and the identity $\log(ab)=\log a+\log b$, we compute \[ g(ab)=f(ab)-c\log(ab)=(f(a)+f(b)) - c(\log a+\log b)=g(a)+g(b). \] Thus $g$ is additive. $\square$

FAST REALITY CHECK (small $X$ computations). The condition $\lvert A\cap[1,X]\rvert=o(X)$ is very strong. As a sanity check, I computed $\lvert A\cap[1,X]\rvert$ for several standard additive functions that are not of the form $c\log n$:

  • $f(n)=\omega(n)$ (number of distinct prime factors),
  • $f(n)=\Omega(n)$ (number of prime factors counted with multiplicity),
  • $f(n)=\log\operatorname{rad}(n)=\sum_{p\mid n}\log p$.
For each, I computed $A=\{n\le X: f(n+1)<f(n)\}$. 
X=1000
  log: |A∩[1,1000]|=0  ratio=0.000000
  omega: |A∩[1,1000]|=346  ratio=0.346000
  Omega: |A∩[1,1000]|=424  ratio=0.424000
  lograd: |A∩[1,1000]|=345  ratio=0.345000

X=5000
  log: |A∩[1,5000]|=0  ratio=0.000000
  omega: |A∩[1,5000]|=1809  ratio=0.361800
  Omega: |A∩[1,5000]|=2137  ratio=0.427400
  lograd: |A∩[1,5000]|=1701  ratio=0.340200

X=20000
  log: |A∩[1,20000]|=0  ratio=0.000000
  omega: |A∩[1,20000]|=7354  ratio=0.367700
  Omega: |A∩[1,20000]|=8597  ratio=0.429850
  lograd: |A∩[1,20000]|=6787  ratio=0.339350

X=100000
  log: |A∩[1,100000]|=0  ratio=0.000000
  omega: |A∩[1,100000]|=37494  ratio=0.374940
  Omega: |A∩[1,100000]|=43077  ratio=0.430770
  lograd: |A∩[1,100000]|=33910  ratio=0.339100
This does not prove anything about the conjecture, but it indicates that "generic" additive functions have a descent set $A$ of positive density (at least for these examples).

VERIFICATION

  • Lemma 1122.1 uses only the defining property at $(1,1)=1$ and is correct.
  • Lemma 1122.2 uses only repeated splitting into coprime factors; it does not assume complete additivity.
  • Lemma 1122.3 uses that $\log$ is exactly additive for products.
  • The computations above were performed by sieve-based evaluation of $\omega,\Omega,\log\operatorname{rad}$ and direct counting of descents.

FINAL

UNRESOLVED

(i) Strongest proved partial result. For any additive $f$, $f(1)=0$ and $f$ decomposes over prime powers as $f(n)=\sum_{p^a\parallel n} f(p^a)$ (Lemmas 1122.1--1122.2). Also, for any $c\in\mathbb{R}$, $g(n):=f(n)-c\log n$ remains additive (Lemma 1122.3).

(ii) First gap (crisp). Show that the density-zero descent condition \[ \lvert\{n\le X: f(n+1)<f(n)\}\rvert=o(X) \] forces an additive function $f$ to satisfy $f(n)=c\log n$ for all $n$.

(iii) Top 3 next moves.

  • Prove a rigidity lemma: if $\lvert A\cap[1,X]\rvert=o(X)$ then there exists $c$ such that $f(p)=c\log p+o(\log p)$ for primes $p\to\infty$.
  • Prove a prime-power control lemma: under the same hypothesis, for each fixed prime $p$ one has $f(p^k)=k f(p)+o(1)$ as $k\to\infty$ (or a suitable uniform variant).
  • Attempt a "consecutive integers" transfer: prove that if $f$ is close to $c\log$ on a set of integers of density $1$, then additivity forces $f\equiv c\log$.

(iv) Minimal counterexample structure. A counterexample would be an additive $f$ with $f\not\equiv c\log$ for every $c$, but such that $f(n+1)\ge f(n)$ for all but $o(X)$ values $n\le X$. Such an $f$ would have to exploit special correlations between the prime-power decompositions of consecutive integers.

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

Go to contribution →

Math-6176-A2 · No claim recorded · LLM-generated · gpt pro 5.2 ·

gpt pro 5.2 attempt on Math-6176

FORMAL RESTATEMENT

Let $f:\mathbb{N}\to\mathbb{R}$ be an additive function in the sense that \[ \forall a,b\in\mathbb{N},\ (a,b)=1 \implies f(ab)=f(a)+f(b). \] Define \[ A:=\{n\in\mathbb{N}_{\ge 1}:\ f(n+1)<f(n)\}. \] Assume that \[ \lvert A\cap[1,X]\rvert=o(X)\qquad (X\to\infty), \] i.e. $\lvert A\cap[1,X]\rvert/X\to 0$ as $X\to\infty$. Question: must there exist a constant $c\in\mathbb{R}$ such that \[ \forall n\ge 1,\quad f(n)=c\log n? \] (Here $\log$ is the natural logarithm; $\mathbb{N}=\{1,2,3,\dots\}$.)

QUICK LITERATURE/CONTEXT CHECK

I only record context explicitly stated in the problem file. The file states: (i) Erdős proved $f(n)=c\log n$ if $A$ is empty, and also if $f(n+1)-f(n)=o(1)$. (ii) Mangerel proved the conclusion under a stronger sparsity hypothesis $\lvert A\cap[1,X]\rvert\ll X/(\log X)^{2+c}$ (some $c>0$) plus a technical "no very large values" condition on primes.

ATTACK PLAN

Proof track ideas.
  • Try to show that "few descents" forces $f$ to be close to a monotone function, then use additivity to identify the monotone additive functions as $c\log n$.
  • Study $g(n):=f(n)-c\log n$ (still additive) and attempt to show $g$ must be asymptotically constant, then use additivity to conclude $g\equiv 0$.
Disproof track ideas.
  • Attempt to define $f$ on prime powers so that $f$ deviates from $c\log n$, but correlates with the arithmetic of $n$ vs $n+1$ to avoid descents on most $n$.
  • Attempt a "sparse perturbation" of $c\log n$ supported on a very sparse set of primes/prime powers, then test whether the descent set can be made density $0$.

WORK

Lemma 1122.1 (normalization at $1$). For any additive $f:\mathbb{N}\to\mathbb{R}$ (in the coprime sense), one has $f(1)=0$.

Proof. Since $(1,1)=1$, additivity gives $f(1\cdot 1)=f(1)+f(1)$, i.e. $f(1)=2f(1)$. Subtracting $f(1)$ from both sides yields $f(1)=0$. $\square$

Lemma 1122.2 (prime-power decomposition). Let $f$ be additive. If $n=\prod_{i=1}^r p_i^{a_i}$ is the prime factorization of $n$ (distinct primes $p_i$ and exponents $a_i\ge 1$), then \[ f(n)=\sum_{i=1}^r f\left(p_i^{a_i}\right). \]

Proof. Write $n=u\,v$ where $u=p_1^{a_1}$ and $v=\prod_{i=2}^r p_i^{a_i}$. Then $(u,v)=1$, so $f(n)=f(u)+f(v)$. If $r\ge 2$, apply the same argument to $f(v)$, splitting off $p_2^{a_2}$ from the remaining coprime factor, and iterate. After $r-1$ iterations one obtains the displayed sum. $\square$

Lemma 1122.3 (subtracting $c\log$ preserves additivity). Fix $c\in\mathbb{R}$ and define $g(n):=f(n)-c\log n$. Then $g$ is additive (in the same coprime sense).

Proof. Let $(a,b)=1$. Using additivity of $f$ and the identity $\log(ab)=\log a+\log b$, we compute \[ g(ab)=f(ab)-c\log(ab)=(f(a)+f(b)) - c(\log a+\log b)=g(a)+g(b). \] Thus $g$ is additive. $\square$

FAST REALITY CHECK (small $X$ computations). The condition $\lvert A\cap[1,X]\rvert=o(X)$ is very strong. As a sanity check, I computed $\lvert A\cap[1,X]\rvert$ for several standard additive functions that are not of the form $c\log n$:

  • $f(n)=\omega(n)$ (number of distinct prime factors),
  • $f(n)=\Omega(n)$ (number of prime factors counted with multiplicity),
  • $f(n)=\log\operatorname{rad}(n)=\sum_{p\mid n}\log p$.
For each, I computed $A=\{n\le X: f(n+1)<f(n)\}$. 
X=1000
  log: |A∩[1,1000]|=0  ratio=0.000000
  omega: |A∩[1,1000]|=346  ratio=0.346000
  Omega: |A∩[1,1000]|=424  ratio=0.424000
  lograd: |A∩[1,1000]|=345  ratio=0.345000

X=5000
  log: |A∩[1,5000]|=0  ratio=0.000000
  omega: |A∩[1,5000]|=1809  ratio=0.361800
  Omega: |A∩[1,5000]|=2137  ratio=0.427400
  lograd: |A∩[1,5000]|=1701  ratio=0.340200

X=20000
  log: |A∩[1,20000]|=0  ratio=0.000000
  omega: |A∩[1,20000]|=7354  ratio=0.367700
  Omega: |A∩[1,20000]|=8597  ratio=0.429850
  lograd: |A∩[1,20000]|=6787  ratio=0.339350

X=100000
  log: |A∩[1,100000]|=0  ratio=0.000000
  omega: |A∩[1,100000]|=37494  ratio=0.374940
  Omega: |A∩[1,100000]|=43077  ratio=0.430770
  lograd: |A∩[1,100000]|=33910  ratio=0.339100
This does not prove anything about the conjecture, but it indicates that "generic" additive functions have a descent set $A$ of positive density (at least for these examples).

VERIFICATION

  • Lemma 1122.1 uses only the defining property at $(1,1)=1$ and is correct.
  • Lemma 1122.2 uses only repeated splitting into coprime factors; it does not assume complete additivity.
  • Lemma 1122.3 uses that $\log$ is exactly additive for products.
  • The computations above were performed by sieve-based evaluation of $\omega,\Omega,\log\operatorname{rad}$ and direct counting of descents.

FINAL

UNRESOLVED

(i) Strongest proved partial result. For any additive $f$, $f(1)=0$ and $f$ decomposes over prime powers as $f(n)=\sum_{p^a\parallel n} f(p^a)$ (Lemmas 1122.1--1122.2). Also, for any $c\in\mathbb{R}$, $g(n):=f(n)-c\log n$ remains additive (Lemma 1122.3).

(ii) First gap (crisp). Show that the density-zero descent condition \[ \lvert\{n\le X: f(n+1)<f(n)\}\rvert=o(X) \] forces an additive function $f$ to satisfy $f(n)=c\log n$ for all $n$.

(iii) Top 3 next moves.

  • Prove a rigidity lemma: if $\lvert A\cap[1,X]\rvert=o(X)$ then there exists $c$ such that $f(p)=c\log p+o(\log p)$ for primes $p\to\infty$.
  • Prove a prime-power control lemma: under the same hypothesis, for each fixed prime $p$ one has $f(p^k)=k f(p)+o(1)$ as $k\to\infty$ (or a suitable uniform variant).
  • Attempt a "consecutive integers" transfer: prove that if $f$ is close to $c\log$ on a set of integers of density $1$, then additivity forces $f\equiv c\log$.

(iv) Minimal counterexample structure. A counterexample would be an additive $f$ with $f\not\equiv c\log$ for every $c$, but such that $f(n+1)\ge f(n)$ for all but $o(X)$ values $n\le X$. Such an $f$ would have to exploit special correlations between the prime-power decompositions of consecutive integers.

Go to contribution →