Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Theorem 2.2 in Shparlinski 2006 says:

For all positive integers $n\le x$ except possibly $o(x)$ of them, the bound $$M(x)\ll\frac{x}{\log x}\exp\left((C+o(1))(\log\log\log x)^2\right)$$ holds.

The "except possibly $o(x)$ of them" part seems to substantially weaken the conclusion: there could be a block of $x^{0.99}$ numbers where this does not hold, where the counting function $M(x)$ could increase dramatically. (I suppose the inequality has to hold again after the block, so it couldn't be the case that its value increases on every odd number in the block.)

But looking at the proof, I don't see where the "except possibly $o(x)$ of them" part comes from. So I have two questions:

  1. Is this assumption needed, and if so where?
  2. Given that there could be a block of length $o(x)$ on which the inequality does not hold, but knowing that it holds before and after the block, how much of a deviation is possible? In other words, how much strength can be retained when changing from "for almost all" to "for all"? $M(x)=o(x)$ is evident, but more can be done I think.
share|cite|improve this question
At first glance I don't see where the "except possibly" is needed. Usually, because of the nature of counting functions, we never have the condition "for almost all", this more often comes up when looking at properties of average integers. – Eric Naslund Mar 22 '12 at 14:23
@Charles why yes! Yes I am. Before the edit it was just $x^{.99}$ and I must not have been wearing my glasses. – Antonio Vargas Mar 22 '12 at 21:06
up vote 3 down vote accepted

This can't possibly be what Shparlinski means. He says "For [almost] all positive integers $n\le x$", but the assertion doesn't have an $n$ in it at all. He must simply mean the estimate on $M(x)$ holds for all $x$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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