Erdős Problem #520

Erdős Problem 520 --- collection record

PROVENANCE AND STATUS

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

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/520.tex.

REUSED SOURCE 1

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

FORMAL RESTATEMENT. Let $\{\sigma_p\}_{p\ \text{prime}}$ be independent random variables with \[\mathbb P(\sigma_p=1)=\mathbb P(\sigma_p=-1)=\tfrac12.\] Define a random arithmetic function $f:\mathbb N\to\{-1,0,1\}$ by

• $f(1)=1$;
• for each prime $p$, $f(p)=\sigma_p$;
• if $n\ge 2$ is squarefree with prime factorization $n=p_1\cdots p_r$, set $f(n)=\sigma_{p_1}\cdots \sigma_{p_r}$;
• if $n$ is not squarefree (i.e. $p^2\mid n$ for some prime $p$), set $f(n)=0$.

For $N\ge 1$ define the partial sums $S(N)=\sum_{m\le N} f(m)$. (Here and below $\log$ is the natural logarithm; the normalization $\sqrt{N\log\log N}$ is defined for $N\ge 3$.)

Question: Does there exist a deterministic constant $c>0$ such that, with probability $1$, \[\limsup_{N\to\infty}\frac{S(N)}{\sqrt{N\log\log N}}=c\ ?\]

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself reports the following almost-sure upper bounds for $S(N)$: Wintner proved $S(N)\ll N^{1/2+o(1)}$, Erdős strengthened this to $N^{1/2}(\log N)^{O(1)}$, Lau--Tenenbaum--Wu proved $S(N)\ll N^{1/2}(\log\log N)^{2+o(1)}$, and Caich improved this to $S(N)\ll N^{1/2}(\log\log N)^{3/4+o(1)}$. The statement also reports that Harper proved $S(N)$ is almost surely not $O\big(N^{1/2}/(\log\log N)^{5/2+o(1)}\big)$ and conjectured a sharper upper bound $S(N)\ll N^{1/2}(\log\log N)^{1/4+o(1)}$ almost surely.

ATTACK PLAN.

• Proof track idea 1: Find a martingale approximation for $S(N)$ by revealing primes in increasing order and expressing $S(N)$ as a sum of contributions of each prime; then try to apply a law-of-the-iterated-logarithm (LIL) for martingales with a computable quadratic variation.
• Proof track idea 2: Show $S(N)$ is close (in a strong invariance principle sense) to a Gaussian process whose suprema are understood, and identify the correct scaling and constant.
• Disproof track: Attempt to show the limsup constant is random (depends on the realization of $\{\sigma_p\}$), or that $\limsup$ does not stabilize to any constant (e.g. by constructing events forcing unusually large prime-block correlations at infinitely many scales).

I do not complete either track below; I instead record clean, fully proved moment identities and a basic probabilistic consequence.

WORK.

Fast reality check (exact small-$N$ moment computation). For $N=30$ one can average over all $2^{10}=1024$ sign-assignments on primes $\le 30$ and compute exactly:

N=30 #assignments 1024
E[S]= 1.0
E[S^2]= 19.0
#squarefree <=N = 19

(Computation done by brute force enumeration of prime-sign assignments. Here $S=S(30)$.)

A single sample realization with seed $0$ for primes $\le 10^5$ gave:

seed=0 Nmax 100000
S(Nmax)= -392
max ratio for N>=100: 1.199739691784555 at (155, 19)

This is only a sanity check; small $N$ does not meaningfully reflect the asymptotic limsup question.

Lemma 520.1 (mean and pair correlations). For $n\in\mathbb N$ we have \begin{align*} \mathbb E[f(n)] &= \begin{cases}1,& n=1,\\0,& n\ge 2,\end{cases}\\ \mathbb E[f(m)f(n)] &= \begin{cases}1,& m=n\ \text{and $n$ squarefree},\\0,& \text{otherwise}. \end{cases} \end{align*}

Proof. For $n=1$, $f(1)=1$ deterministically, so $\mathbb E[f(1)]=1$.

Now take $n\ge 2$. If $n$ is not squarefree then $f(n)=0$ deterministically and $\mathbb E[f(n)]=0$. If $n$ is squarefree, write $n=\prod_{p\mid n}p$. Then \[f(n)=\prod_{p\mid n}\sigma_p.\] Because the $\sigma_p$ are independent and $\mathbb E[\sigma_p]=0$ for each prime $p$, we get \[\mathbb E[f(n)] = \prod_{p\mid n} \mathbb E[\sigma_p] = 0,\] since the product runs over at least one prime.

For the correlation, note first that if either $m$ or $n$ is not squarefree then $f(m)f(n)=0$ deterministically, hence expectation $0$. Assume now that both $m$ and $n$ are squarefree. Write \[m=\prod_{p\mid m} p,\qquad n=\prod_{p\mid n} p.\] Then \[f(m)f(n)=\Big(\prod_{p\mid m}\sigma_p\Big)\Big(\prod_{q\mid n}\sigma_q\Big)=\prod_{r\mid mn} \sigma_r^{e_r},\] where $e_r\in\{0,1,2\}$ is the number of times $r$ appears in the combined product. By independence, \[\mathbb E[f(m)f(n)] = \prod_{r\mid mn} \mathbb E[\sigma_r^{e_r}].\] But $\sigma_r^{0}=1$ has expectation $1$, $\sigma_r^{2}=1$ has expectation $1$, and $\sigma_r^{1}=\sigma_r$ has expectation $0$. Therefore this product is $0$ unless every $e_r$ is even, i.e. unless each prime divides $m$ and $n$ simultaneously. Since $m$ and $n$ are squarefree, this condition is equivalent to $m=n$. If $m=n$ and is squarefree, then $f(m)f(n)=f(n)^2=1$ deterministically, giving expectation $1$. $\square$

Lemma 520.2 (exact second moment of partial sums). Let $S(N)=\sum_{m\le N}f(m)$ and let $Q(N)=\#\{1\le m\le N: m\ \text{squarefree}\}$. Then \[\mathbb E\big[S(N)^2\big] = Q(N).\] In particular, $\mathrm{Var}(S(N))=Q(N)-1\le N$.

Proof. Expand the square: \[S(N)^2 = \sum_{m\le N}\sum_{n\le N} f(m)f(n). \] Taking expectation and using Lemma 520.1, \[\mathbb E[S(N)^2]=\sum_{m\le N}\sum_{n\le N} \mathbb E[f(m)f(n)] = \sum_{n\le N\atop n\ \text{squarefree}} 1 = Q(N). \] The variance identity $\mathrm{Var}(S(N))=\mathbb E[S(N)^2]-(\mathbb E[S(N)])^2$ follows from Lemma 520.1, which gives $\mathbb E[S(N)]=\sum_{m\le N}\mathbb E[f(m)]=1$. Finally, $Q(N)\le N$ is immediate. $\square$

Lemma 520.3 (a weak bound in probability). For every $\varepsilon>0$, \[\mathbb P\big(|S(N)|\ge N^{1/2+\varepsilon}\big) \le N^{-2\varepsilon}\qquad (N\ge 1). \] Consequently $S(N)=o(N^{1/2+\varepsilon})$ in probability as $N\to\infty$.

Proof. By Chebyshev's inequality, \[\mathbb P\big(|S(N)|\ge N^{1/2+\varepsilon}\big)\le \frac{\mathbb E[S(N)^2]}{N^{1+2\varepsilon}}. \] Lemma 520.2 gives $\mathbb E[S(N)^2]=Q(N)\le N$, hence the bound $\le N^{-2\varepsilon}$. The probability therefore tends to $0$. $\square$

VERIFICATION.

• Lemma 520.1: The only subtlety is non-squarefree inputs. We explicitly set $f(n)=0$ for non-squarefree $n$, making all expectations involving such $n$ equal to $0$.
• Lemma 520.2: We used only linearity of expectation and Lemma 520.1. No hidden independence assumptions between $f(m)$ and $f(n)$ were made beyond what Lemma 520.1 already encodes.
• Lemma 520.3: Chebyshev uses only the second moment, which we computed exactly.
• Normalization: $\sqrt{N\log\log N}$ requires $\log\log N>0$; formally the limsup statement concerns large $N$, so this is not an issue.

FINAL. UNRESOLVED

(i) Strongest proved partial result: Exact second moment identity $\mathbb E[S(N)^2]=Q(N)$ (Lemma 520.2), and the consequent bound $S(N)=o(N^{1/2+\varepsilon})$ in probability for every $\varepsilon>0$ (Lemma 520.3).

(ii) First gap (crisp): Upgrade moment control / bounds in probability to an almost sure law at the iterated-log scale, i.e. prove or disprove the existence of a deterministic constant $c>0$ such that \[\limsup_{N\to\infty}\frac{S(N)}{\sqrt{N\log\log N}}=c\quad\text{a.s.}\]

(iii) Top 3 next moves (concrete):

1. Find an explicit martingale difference decomposition $S(N)=\sum_{p\le N} D_p(N)$ (revealing primes in increasing order) with computable conditional variance $\sum_p \mathbb E[D_p(N)^2\mid \mathcal F_{p^-}]$, and check Lindeberg-type conditions needed for a martingale LIL.
2. Prove a sharp asymptotic for the quadratic variation of that martingale (show it is $\asymp N\log\log N$ at the relevant scale, with a deterministic leading constant).
3. Computationally: simulate $\max_{N\le X} S(N)/\sqrt{N\log\log N}$ for increasing $X$ across many seeds to see whether the putative constant appears stable or drifts.

(iv) Minimal counterexample structure: A disproof would likely show that the limsup constant is not deterministic (depends on the random realization of $\{\sigma_p\}$), or that the limsup is infinite/does not exist. Concretely, one would seek events occurring infinitely often that force unusually coherent signs of $f(n)$ on long ranges (strong prime-block correlations), pushing $S(N)$ above any fixed multiple of $\sqrt{N\log\log N}$.

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.

FORMAL RESTATEMENT. Let $\{\sigma_p\}_{p\ \text{prime}}$ be independent random variables with \[\mathbb P(\sigma_p=1)=\mathbb P(\sigma_p=-1)=\tfrac12.\] Define a random arithmetic function $f:\mathbb N\to\{-1,0,1\}$ by

• $f(1)=1$;
• for each prime $p$, $f(p)=\sigma_p$;
• if $n\ge 2$ is squarefree with prime factorization $n=p_1\cdots p_r$, set $f(n)=\sigma_{p_1}\cdots \sigma_{p_r}$;
• if $n$ is not squarefree (i.e. $p^2\mid n$ for some prime $p$), set $f(n)=0$.

For $N\ge 1$ define the partial sums $S(N)=\sum_{m\le N} f(m)$. (Here and below $\log$ is the natural logarithm; the normalization $\sqrt{N\log\log N}$ is defined for $N\ge 3$.)

Question: Does there exist a deterministic constant $c>0$ such that, with probability $1$, \[\limsup_{N\to\infty}\frac{S(N)}{\sqrt{N\log\log N}}=c\ ?\]

QUICK LITERATURE/CONTEXT CHECK. The problem statement itself reports the following almost-sure upper bounds for $S(N)$: Wintner proved $S(N)\ll N^{1/2+o(1)}$, Erdős strengthened this to $N^{1/2}(\log N)^{O(1)}$, Lau--Tenenbaum--Wu proved $S(N)\ll N^{1/2}(\log\log N)^{2+o(1)}$, and Caich improved this to $S(N)\ll N^{1/2}(\log\log N)^{3/4+o(1)}$. The statement also reports that Harper proved $S(N)$ is almost surely not $O\big(N^{1/2}/(\log\log N)^{5/2+o(1)}\big)$ and conjectured a sharper upper bound $S(N)\ll N^{1/2}(\log\log N)^{1/4+o(1)}$ almost surely.

ATTACK PLAN.

• Proof track idea 1: Find a martingale approximation for $S(N)$ by revealing primes in increasing order and expressing $S(N)$ as a sum of contributions of each prime; then try to apply a law-of-the-iterated-logarithm (LIL) for martingales with a computable quadratic variation.
• Proof track idea 2: Show $S(N)$ is close (in a strong invariance principle sense) to a Gaussian process whose suprema are understood, and identify the correct scaling and constant.
• Disproof track: Attempt to show the limsup constant is random (depends on the realization of $\{\sigma_p\}$), or that $\limsup$ does not stabilize to any constant (e.g. by constructing events forcing unusually large prime-block correlations at infinitely many scales).

I do not complete either track below; I instead record clean, fully proved moment identities and a basic probabilistic consequence.

WORK.

Fast reality check (exact small-$N$ moment computation). For $N=30$ one can average over all $2^{10}=1024$ sign-assignments on primes $\le 30$ and compute exactly:

N=30 #assignments 1024
E[S]= 1.0
E[S^2]= 19.0
#squarefree <=N = 19

(Computation done by brute force enumeration of prime-sign assignments. Here $S=S(30)$.)

A single sample realization with seed $0$ for primes $\le 10^5$ gave:

seed=0 Nmax 100000
S(Nmax)= -392
max ratio for N>=100: 1.199739691784555 at (155, 19)

This is only a sanity check; small $N$ does not meaningfully reflect the asymptotic limsup question.

Lemma 520.1 (mean and pair correlations). For $n\in\mathbb N$ we have \begin{align*} \mathbb E[f(n)] &= \begin{cases}1,& n=1,\\0,& n\ge 2,\end{cases}\\ \mathbb E[f(m)f(n)] &= \begin{cases}1,& m=n\ \text{and $n$ squarefree},\\0,& \text{otherwise}. \end{cases} \end{align*}

Proof. For $n=1$, $f(1)=1$ deterministically, so $\mathbb E[f(1)]=1$.

Now take $n\ge 2$. If $n$ is not squarefree then $f(n)=0$ deterministically and $\mathbb E[f(n)]=0$. If $n$ is squarefree, write $n=\prod_{p\mid n}p$. Then \[f(n)=\prod_{p\mid n}\sigma_p.\] Because the $\sigma_p$ are independent and $\mathbb E[\sigma_p]=0$ for each prime $p$, we get \[\mathbb E[f(n)] = \prod_{p\mid n} \mathbb E[\sigma_p] = 0,\] since the product runs over at least one prime.

For the correlation, note first that if either $m$ or $n$ is not squarefree then $f(m)f(n)=0$ deterministically, hence expectation $0$. Assume now that both $m$ and $n$ are squarefree. Write \[m=\prod_{p\mid m} p,\qquad n=\prod_{p\mid n} p.\] Then \[f(m)f(n)=\Big(\prod_{p\mid m}\sigma_p\Big)\Big(\prod_{q\mid n}\sigma_q\Big)=\prod_{r\mid mn} \sigma_r^{e_r},\] where $e_r\in\{0,1,2\}$ is the number of times $r$ appears in the combined product. By independence, \[\mathbb E[f(m)f(n)] = \prod_{r\mid mn} \mathbb E[\sigma_r^{e_r}].\] But $\sigma_r^{0}=1$ has expectation $1$, $\sigma_r^{2}=1$ has expectation $1$, and $\sigma_r^{1}=\sigma_r$ has expectation $0$. Therefore this product is $0$ unless every $e_r$ is even, i.e. unless each prime divides $m$ and $n$ simultaneously. Since $m$ and $n$ are squarefree, this condition is equivalent to $m=n$. If $m=n$ and is squarefree, then $f(m)f(n)=f(n)^2=1$ deterministically, giving expectation $1$. $\square$

Lemma 520.2 (exact second moment of partial sums). Let $S(N)=\sum_{m\le N}f(m)$ and let $Q(N)=\#\{1\le m\le N: m\ \text{squarefree}\}$. Then \[\mathbb E\big[S(N)^2\big] = Q(N).\] In particular, $\mathrm{Var}(S(N))=Q(N)-1\le N$.

Proof. Expand the square: \[S(N)^2 = \sum_{m\le N}\sum_{n\le N} f(m)f(n). \] Taking expectation and using Lemma 520.1, \[\mathbb E[S(N)^2]=\sum_{m\le N}\sum_{n\le N} \mathbb E[f(m)f(n)] = \sum_{n\le N\atop n\ \text{squarefree}} 1 = Q(N). \] The variance identity $\mathrm{Var}(S(N))=\mathbb E[S(N)^2]-(\mathbb E[S(N)])^2$ follows from Lemma 520.1, which gives $\mathbb E[S(N)]=\sum_{m\le N}\mathbb E[f(m)]=1$. Finally, $Q(N)\le N$ is immediate. $\square$

Lemma 520.3 (a weak bound in probability). For every $\varepsilon>0$, \[\mathbb P\big(|S(N)|\ge N^{1/2+\varepsilon}\big) \le N^{-2\varepsilon}\qquad (N\ge 1). \] Consequently $S(N)=o(N^{1/2+\varepsilon})$ in probability as $N\to\infty$.

Proof. By Chebyshev's inequality, \[\mathbb P\big(|S(N)|\ge N^{1/2+\varepsilon}\big)\le \frac{\mathbb E[S(N)^2]}{N^{1+2\varepsilon}}. \] Lemma 520.2 gives $\mathbb E[S(N)^2]=Q(N)\le N$, hence the bound $\le N^{-2\varepsilon}$. The probability therefore tends to $0$. $\square$

VERIFICATION.

• Lemma 520.1: The only subtlety is non-squarefree inputs. We explicitly set $f(n)=0$ for non-squarefree $n$, making all expectations involving such $n$ equal to $0$.
• Lemma 520.2: We used only linearity of expectation and Lemma 520.1. No hidden independence assumptions between $f(m)$ and $f(n)$ were made beyond what Lemma 520.1 already encodes.
• Lemma 520.3: Chebyshev uses only the second moment, which we computed exactly.
• Normalization: $\sqrt{N\log\log N}$ requires $\log\log N>0$; formally the limsup statement concerns large $N$, so this is not an issue.

FINAL. UNRESOLVED

(i) Strongest proved partial result: Exact second moment identity $\mathbb E[S(N)^2]=Q(N)$ (Lemma 520.2), and the consequent bound $S(N)=o(N^{1/2+\varepsilon})$ in probability for every $\varepsilon>0$ (Lemma 520.3).

(ii) First gap (crisp): Upgrade moment control / bounds in probability to an almost sure law at the iterated-log scale, i.e. prove or disprove the existence of a deterministic constant $c>0$ such that \[\limsup_{N\to\infty}\frac{S(N)}{\sqrt{N\log\log N}}=c\quad\text{a.s.}\]

(iii) Top 3 next moves (concrete):

1. Find an explicit martingale difference decomposition $S(N)=\sum_{p\le N} D_p(N)$ (revealing primes in increasing order) with computable conditional variance $\sum_p \mathbb E[D_p(N)^2\mid \mathcal F_{p^-}]$, and check Lindeberg-type conditions needed for a martingale LIL.
2. Prove a sharp asymptotic for the quadratic variation of that martingale (show it is $\asymp N\log\log N$ at the relevant scale, with a deterministic leading constant).
3. Computationally: simulate $\max_{N\le X} S(N)/\sqrt{N\log\log N}$ for increasing $X$ across many seeds to see whether the putative constant appears stable or drifts.

(iv) Minimal counterexample structure: A disproof would likely show that the limsup constant is not deterministic (depends on the random realization of $\{\sigma_p\}$), or that the limsup is infinite/does not exist. Concretely, one would seek events occurring infinitely often that force unusually coherent signs of $f(n)$ on long ranges (strong prime-block correlations), pushing $S(N)$ above any fixed multiple of $\sqrt{N\log\log N}$.