For $ n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$ define $\Omega(n)= \alpha_1+\cdots+\alpha_k$.

What is known about the asymptotic behavior as $N\rightarrow\infty$ for sums of the form

$$\sum_{n=1}^N |\Omega(n+1)-\Omega(n)| \quad ?$$

  • $\begingroup$ By considering prime n, you should get a lower bound of order like NloglogN/logN, while an upper bound of order NloglogN should be clear. Likely the latter asymptotic holds. Gerhard "Probably Very Many Nonzero Summands" Paseman, 2018.05.24. $\endgroup$ – Gerhard Paseman May 24 '18 at 21:39
  • $\begingroup$ @GerhardPaseman Could you provide some details, besides heuristic arguments? $\endgroup$ – Alan Haynes May 24 '18 at 22:54
  • $\begingroup$ For the upper bound, the difference term is bounded by the sum. For the lower bound, letting n or n+1 be prime, we carve out a piece roughly 1/log N the size of the domain, and observe the terms are nonzero. It is conceivable that the terms involving primes are of size near log N, or that they are all near 1, but they are not zero, and if almost all the terms are below loglogN in size, I would like to see it. Do you have a reason for challenging the proposed lower bound? Gerhard "Is Thinking Out Loud Here" Paseman, 2018.05.24. $\endgroup$ – Gerhard Paseman May 25 '18 at 1:50
  • 2
    $\begingroup$ Alternate heuristic: for almost all $n$, both $\Omega(n)$ and $\Omega(n+1)$ differ from $\log\log n$ by a "random" multiple of $\sqrt{\log\log n}$, where "random" means a number drawn from a standard normal distribution (that's the Erdös–Kac therorem). Assuming $\Omega(n+1)$ and $\Omega(n)$ are asymptotically independent (surely true and probably even known), most terms in the sum will be about $\sqrt{\log\log n}$ in magnitude, leading to a total of around $N\sqrt{\log\log N}$ for the sum. $\endgroup$ – Greg Martin May 25 '18 at 3:04
  • 1
    $\begingroup$ @Greg and Alan, the result you're talking about is in "On the Distribution of Additive Number‐Theoretic Functions II", H. Halberstam (londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/…; put "sci-hub.tw/" in front to get without institutional access). As you suggest, with a little more work I think the answer will follow from Theorem 2 there. $\endgroup$ – Brad Rodgers May 26 '18 at 15:37

I'm just filling in the details in a comment left above, which in turn builds off a comment left by Greg Martin. If I haven't made a mistake it works out that $$ \sum_{n\leq x} |\Omega(n+1)-\Omega(n)| \sim \frac{2}{\sqrt{\pi}} x \sqrt{\log \log x}. $$

This result is essentially due to Halberstam in "On the Distribution of Additive Number‐Theoretic Functions II"; a few small tricks take you from his result to this one. Halberstam's paper is at https://londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms/s1-31.1.1.

The most important result of Halberstam is Theorem 1 of that paper, but he uses this to deal almost exactly with the question you're after; as a special case of Theorem 2 (for $f(p)=1$), we get that $$ \sum_{n\leq x} (\omega(n+1)-\omega(n))^k = (c_k+o(1)) (2 \log \log x)^{k/2}, $$ where $$ c_k:=\int_{-\infty}^\infty t^k \frac{e^{-t^2/2}}{\sqrt{2\pi}}\, dt, $$ and $\omega(n)$ is the number of prime factors of $n$ without multiplicity.

Morally then this result just follows by 1) replacing the functions $t^k$ with $|t|$ above and evaluating the integral, and 2) showing that the transition from $\omega(n)$ to $\Omega(n)$ doesn't change anything since $$ \sum_{n\leq x} \Omega(n)-\omega(n) = O(x). $$ I'll leave 2) to you (but please ask if you have questions about it), but I'll expand a little on 1). This is essentially the method of moments in probability (see section 30 of Billingsley's Probability and Measure, and in particular Theorem 30.2 [I'm using the 3rd edition]). Using the abbreviation, $$ A_{n,x}:= \frac{\omega(n+1)-\omega(n)}{\sqrt{2\log \log x}}, $$ this theorem from probability combined with Halberstam's tells us for any continuous and bounded function $g(x)$, $$ \frac{1}{x} \sum_{n\leq x} g(A_{n,x}) = \int_{-\infty}^\infty g(t) \frac{e^{-t^2/2}}{\sqrt{2\pi}}\, dt + o(1). $$ With just a little bit of extra work on the probability side, one can see that this claim holds more generally for functions $g(x)$ that are continuous and increase only polynomially, so in particular using $g(x) = |x|$, $$ \frac{1}{x} \sum_{n\leq x} |A_{n,x}| \sim \int_{-\infty}^\infty |t| \frac{e^{-t^2/2}}{\sqrt{2\pi}}\, dt = \sqrt{\frac{2}{\pi}}, $$ and this gives us the result.

| cite | improve this answer | |
  • $\begingroup$ I voted this up at first, but on closer examination I have a question: Are you sure that you are applying the result of Halberstam correctly? When k=1 the sum (without absolute values) telescopes. Also, the integral defining the constant c_1 vanishes, which is consistent with the telescoping. In fact I do not think that there can be an asymptotic in this case, because of elementary considerations. Am I misunderstanding your explanation? $\endgroup$ – Alan Haynes May 28 '18 at 16:16
  • $\begingroup$ The result of Halberstam doesn't give an asymptotic in the case k=1,3,..., it only gives a $o(...)$ bound, but that's all we need. To be clear I'm using the information Halberstam's theorem gives for each of k=1,2,3,... in order to reach the conclusion, not just k=1. (One could argue you only need k=2,4,6,... but that's beyond the point.) The general result ('the method of moments') that I'm citing is that if for some generic sequence $A_{n,x}$, we have $\frac{1}{x}\sum_{n\leq x} (A_{n,x})^k = c_k+o(1)$, then more generally (continued below...) $\endgroup$ – Brad Rodgers May 28 '18 at 20:25
  • $\begingroup$ (cont.) we have $\frac{1}{x}\sum_{n\leq x} g(A_{n,x}) = \int_{-\infty}^\infty g(t) e^{-t^2/2}/\sqrt{2\pi}\, dt +o(1)$ for a larger class of functions $g(t)$ than power functions. It is common to let this more general class be "all continuous and bounded functions $g$," but it is relatively easy to bootstrap such a result to also include continuous and polynomially increasing functions $g$. We use this result for $g(x) = |x|$. The idea behind this result is just to approximate $g(x)$ by a polynomial, but some extra work goes into the proof since this can only be done on a compact interval. $\endgroup$ – Brad Rodgers May 28 '18 at 20:29
  • $\begingroup$ Ok that makes more sense and I think I roughly understand the argument you are using... basically you are constructing a sequence of measures with the property that any weak-* limit integrates polynomials the same way that the normal distribution does. However, since the normal distribution is determined by its moments, that means that the limit must converge to the normal distribution in the weak-* topology (hence for any test function, which for example could be continuous with compact support)... (continued) $\endgroup$ – Alan Haynes May 28 '18 at 22:17
  • $\begingroup$ I was also concerned for a moment that the sequence the measures you are constructing (Borel probability measures on the real line, which is a non-compact space of measures) might not have a weak-* limit, but now that I think about it I guess that is ok as well. Nice, thanks! $\endgroup$ – Alan Haynes May 28 '18 at 22:41

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.