I have two very related questions:

If $f(N)$ is the number of square-free integers in the interval $[1, N]$, it is well known that $$f(N) \sim \frac{6}{\pi^{2}} N.$$

My first question is, if we impose the additional condition that the integer is not divisible by any prime smaller than $ N^{1/k}$, for some fixed integer $k \geq 2$, then what is the precise asymptotic? Clearly it is at least $\frac{N}{\log{N}}$ by the prime number theorem. Furthermore, by an asymptotic for squarefree integers divisible by precisely $c$ prime factors here we see that it is at most $\frac{k_{1}N(\log \log{N})}{\log{N}}$ with $k_{1}$ a constant depending on $k$.

Secondly, there's a connection with a product over all primes. That is, analogously to finding the density of square-free integers, we have that the density of squarefree integers not divisible by any prime less than $N^{1/k}$ is

$$ \prod_{p < N^{1/k}} \left( 1 - \frac{1}{p} \right) \prod_{p > N^{1/k}} \left( 1 - \frac{1}{p^2} \right). $$ Now the second term converges to some constant, and the first one decreases, by Mertens' theorem, like $\frac{c_{2}}{\log{N}}$. This looks similar to what I mentioned before, with the $\log{N}$ appearing in the denominator, but this doesn't a priori tell us anything about what happens inside the interval $[1, N]$ - only an interval $[1, M]$ where $M$ is sufficiently large (and this might be much larger than $N$). So, is there a way to formulate this so that one can find the asymptotic up to $N$ by looking at this product (or perhaps, see how large relative to $N$ that $M$ must be)?

  • 1
    $\begingroup$ Some very rough heuristics suggest a constant times $\frac{kN}{\log N}$; see qchu.wordpress.com/2012/11/10/… for a rough description of those heuristics. $\endgroup$ Apr 11 '14 at 4:27
  • $\begingroup$ I suggest going through the pain of estimating how many of those numbers have precisely c such factors for c=2,3,4. Qiaochu's heuristics above may help with that. Then you might safely conjecture how to bump it up to c=k. My guess is that the number decreases sharply when c reaches log k, which should give you nice estimates. Gerhard "Ask Me About System Design" Paseman, 2014.04.10 $\endgroup$ Apr 11 '14 at 4:35

Forgetting the squarefree condition for a moment, the number of integers up to $N$ that are not divisible by any primes less than $N^{1/k}$ is asymptotic to $$ \omega(k) \frac N{\log N} \sim e^\gamma \omega(k) N \prod_{p\le N^{1/k}} \bigg( 1-\frac1p \bigg), $$ where $\omega$ is the Buchstab function. (In particular, the first half of the density you derive in your answer is not correct: there is a correction factor of the form $e^\gamma \omega(k)$.)

Now the number of integers up to $N$ that are divisible by the square of a particular prime $p$ is at most $N/p^2$. So the number of integers up to $N$ that are divisible by the square of a prime greater than $N^{1/k}$ is at most $$ \sum_{p>N^{1/k}} \frac N{p^2} < N \sum_{n>N^{1/k}} \frac1{n^2} < N \cdot \frac1{N^{1/k}}. $$ Therefore the above asymptotic also holds for squarefree numbers not divisible by small primes.

  • $\begingroup$ Thanks for the helpful reply. Do you know offhand of any source in English with a proof/discussion of this (everything I've found just references non-English papers)? Also, do you know of any generalizations to k-tuples of integers (where I believe one should expect the $\log{N}$ term to be raised to the $k$th power, and something else in place of Buchstab). Despite my searching I can't find anything. $\endgroup$
    – 112358
    Apr 15 '14 at 4:09
  • $\begingroup$ Montgomery-Vaughan's book and Tenenbaum's book should both have the Buchstab material. I think extending Buchstab's result to $k$-tuples, even to pairs, would be difficult, because one can no longer set up the Buchstab iteration (which gives the differential-difference equation defining $\omega$), as far as I can tell. $\endgroup$ Apr 15 '14 at 4:29
  • 1
    $\begingroup$ I believe that there is a factor of $k$ missing somewhere since $$\prod_{p\leq N^{1/k}}\left(1-\frac{1}{p}\right)\sim \frac{e^{-\gamma}}{\log N^{1/k}}=\frac{ke^{-\gamma}}{\log N}.$$ $\endgroup$ Oct 26 '15 at 20: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.