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$ – Qiaochu Yuan 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$ – Gerhard Paseman 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$ – Greg Martin 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$ – Eric Naslund Oct 26 '15 at 20:41

Your Answer

