# Does the average primeness of natural numbers tend to zero?

This question was posted in MSE. It got many upvotes but no answer hence posting it in MO.

A number is either prime or composite, hence primality is a binary concept. Instead I wanted to put a value of primality to every number using some function $$f$$ such that $$f(n) = 1$$ iff $$n$$ is a prime otherwise, $$0 < f(n) < 1$$ and as the number divisors of $$n$$ increases, $$f(n)$$ decreases on average. Thus $$f(n)$$ is a measure of the degree of primeness of $$n$$ where 1 is a perfect prime and 0 is a hypothetical perfect composite. Hence $$\frac{1}{N}\sum_{r \le N} f(r)$$ can be interpreted as a the average primeness of the first $$N$$ integers.

After trying several definitions and going through the ones in literature, I came up with:

Define $$f(n) = \dfrac{2s_n}{n-1}$$ for $$n \ge 2$$, where $$s_n$$ is the standard deviation of the divisors of $$n$$.

One reason for using standard deviation was that I was already studying the distribution of the divisors of a number.

Question 1: Does the average primeness tend to zero? i.e. does the following hold?

$$\lim_{N \to \infty} \frac{1}{N}\sum_{r = 2}^N f(r) = 0$$

Question 2: Is $$f(n)$$ injective over composites? i.e., do there exist composites $$3 < m < n$$ such that $$f(m) = f(n)$$?

My progress

• $$f(4.35\times 10^8) \approx 0.5919$$ and decreasing so the limit if it exists must be between 0 and 0.5919.
• For $$2 \le i \le n$$, computed data shows that the minimum value of $$f(i)$$ occurs at the largest highly composite number $$\le n$$.

Note: Here standard deviation of $$x_1, x_2, \ldots , x_n$$ is defined as $$\sqrt \frac{\sum_{i=1}^{n} (x-x_i)^2}{n}$$. Also notice that even if we define standard deviation as $$\sqrt \frac{\sum_{i=1}^{n} (x-x_i)^2}{n-1}$$ our questions remain unaffected because in this case in the definition of $$f$$, we will be multiplying with $$\sqrt 2$$ instead of $$2$$ to normalize $$f$$ in the interval $$(0,1)$$.

• From the linked question it seems that $s_n$ grows faster than $n$ so that $f(n)$ doesn't go to zero. – lcv Apr 8 at 10:18
• @lcv No $s_n$ doesn't grow faster than $n$. What are you looking at? – Nilos Apr 8 at 10:27
• "...I wanted to have a continuous function...". In what topology is $f$ continuous? If you put discrete topology on natural numbers, then any function is continuous so you probably have something else in mind. – user74900 Apr 8 at 13:56
• I have verified that $f$ is injective over composites less than 10,000,000. – Matt F. Apr 8 at 14:00
• @AknazarKazhymurat I have reworded that line. Hope it is clearer now? – Nilos Apr 8 at 14:02

The answer to Question 1 is "yes". To see this, notice that $$s_n$$ is at most square root of the average square of divisor, i.e. $$s_n\leq \sqrt{\frac{\sum_{d\mid n}d^2}{\sum_{d\mid n} 1}}=\sqrt{\frac{\sigma_2(n)}{\sigma_0(n)}},$$

where $$\sigma_k(n)$$ is the sum of $$k$$-th powers of divisors of $$n$$. Now,

$$\sigma_2(n)=n^2\sigma_{-2}(n),$$

so

$$\sigma_2(n)<\frac{\pi^2}{6}n^2$$

for all $$n$$. Therefore we have

$$f(n)\leq \frac{2}{n-1} \sqrt{\frac{\pi^2}{6}n^2/\sigma_0(n)}\leq \frac{5.14}{\sqrt{\sigma_0(n)}}$$

for all $$n$$. Now, almost all $$n\leq N$$ have at least $$0.5\ln\ln N$$ distinct prime factors. In particular, for almost all $$n\leq N$$ we have $$\sigma_0(n)\geq 0.5\ln\ln N$$. Therefore, our bound for $$f(n)$$ together with the trivial observation that $$0\leq f(n)\leq 1$$ gives

$$\sum_{n\leq N} f(n)\leq \sum_{n\leq N, \sigma_0(n)\geq 0.5\ln\ln N} \frac{5.14}{\sqrt{\sigma_0(n)}}+\sum_{n\leq N, \sigma_0(n)<0.5\ln\ln N} 1= o(N),$$

as needed.

Using contour integration method one can even prove something like

$$\sum_{n\leq N} f(n)=O(N(\ln N)^{1/\sqrt{2}-1})$$

• That last expression reminds me an XKCD alt-text: "If you ever find yourself raising $\log(\text{anything})^{1/\sqrt{2}}$, set down the marker and back away from the whiteboard; something has gone horribly wrong." – Michael Seifert Apr 8 at 18:13
• @MichaelSeifert Bah, it was $\log(anything)^e$ not $\frac{1}{\sqrt{2}}$. Log to the power of one over the sqrt of 2 is mundane; log of something to the power e is a sign of insanity. – Yakk Apr 8 at 19:08
• @Yakk Yeah, but Randall also says that taking $\pi$-th root of anything is insane. However, the paper "Mean values of multiplicative functions" by Montgomery and Vaughan, Theorem 5, contains $(\log x)^{1/\pi-1}$ and is totally fine! (P.S. Is inequality $n_p<p^{\frac{1}{4\sqrt{e}}+o(1)}$ ok?..) – Asymptotiac K Apr 8 at 20:05
• @AsymptotiacK: Thanks for the good answer to Question 1. I think that in general if $f(n)$ is any function who value decreases from 1 to zero as its defined measure of primness decreases then the mean value of $f$ must tend to zero because as we go higher up the number line, for any $k \ge 2$, the probability of of finding numbers with $\le k$ factors should decrease – Nilotpal Kanti Sinha Apr 9 at 6:11