22
$\begingroup$

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)$.

$\endgroup$
  • $\begingroup$ From the linked question it seems that $s_n$ grows faster than $n$ so that $f(n)$ doesn't go to zero. $\endgroup$ – lcv Apr 8 at 10:18
  • 1
    $\begingroup$ @lcv No $s_n$ doesn't grow faster than $n$. What are you looking at? $\endgroup$ – Nilos Apr 8 at 10:27
  • 1
    $\begingroup$ "...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. $\endgroup$ – user74900 Apr 8 at 13:56
  • $\begingroup$ I have verified that $f$ is injective over composites less than 10,000,000. $\endgroup$ – Matt F. Apr 8 at 14:00
  • $\begingroup$ @AknazarKazhymurat I have reworded that line. Hope it is clearer now? $\endgroup$ – Nilos Apr 8 at 14:02
22
$\begingroup$

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}) $$

$\endgroup$
  • 6
    $\begingroup$ 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." $\endgroup$ – Michael Seifert Apr 8 at 18:13
  • 2
    $\begingroup$ @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. $\endgroup$ – Yakk Apr 8 at 19:08
  • 1
    $\begingroup$ @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?..) $\endgroup$ – Asymptotiac K Apr 8 at 20:05
  • 1
    $\begingroup$ @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 $\endgroup$ – Nilotpal Kanti Sinha Apr 9 at 6:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.