MathOverflow is a question and answer site for professional mathematicians. 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

Although the answer to my question is probably implicit in the answers to the question asked here: Density of numbers having large prime divisors (formalizing heuristic probability argument), I can't extract it.

Problem: find decent bounds on the number of positive integers $n$, such that, for all primes $p$ dividing $n$, if $p^k$ exactly divides $n$, then $n > p^{k+1}$.

My idea for a first upper bound: if $n$ is divisible by a prime larger than $n^{\frac{1}{2}}$, it is immediately exluded that $n$ is of the above form, so the density can never be larger than $1 - \log{2}$

My idea for a first lower bound: if $n$ has two prime divisors between $n^{\frac{1}{3}}$ and $n^{\frac{1}{2}}$, then $n$ is of the above form. But I don't know the density of these numbers.

I am probably very happy with a (reference to) a proof/theorem that implies that we have a positive lower density, but asymptotics would be great.

EDIT (after the first response of GH, for which I'm thankful!): assume $n$ lies in some moduloclass, say $a \pmod{b}$. Can we still show a positive lower density, whatever the values of $a$ and $b$?

share|cite|improve this question
Woett, I believe my proof can be easily adapted to residue classes, but I am lazy to check all the details. – GH from MO Mar 31 '11 at 17:51
Here is how to deduce the statement for any residue class $a \pmod{b}$ using my construction. Choose $z > 5b$, then the construction yields a set of good integers $x < n \leq 2x$ coprime with $b$, which is of positive lower density. This set intersects at least one reduced residue class $c \pmod{b}$ with positive lower density. Multiply this intersection with the residue $1 \leq a\bar c \leq b$, where $\bar c$ stands for multiplicative inverse mod $b$. For $x > b^2$ the result is a set of good integers $x < n \leq 2bx$ in the residue class $a \pmod{b}$, which is of positive lower density. – GH from MO Mar 31 '11 at 19:20
Thanks a lot! Not that it matters much, but isn't it for large $b$ better (in the sense that, when $b$ is actually known, we get a better lower bound on the number of good integers) to choose $z$ to be $\max{17, b}$ instead of $> 5b$? – Woett Mar 31 '11 at 19:53
$z=\max(17,b)$ is fine, I was lazy typing and had to fit my message in a bounded box :-) Also I made no attempt to optimize any of my estimates. Perhaps I should add that the original problem naturally reduces to square-free numbers as the density of numbers with a square divisor exceeding $u^2$ is less than $1/u$ (think of $u$ as a large constant). Actually, this is how I was led to my solution. – GH from MO Mar 31 '11 at 20:30

Your numbers have positive lower density. To see this let $z$ be a positive integer to be fixed later, and denote $$ c:=\prod_{p \leq z}(1-1/p). $$ Consider all square-free integers $x < n \leq 2x$ which are composed of primes $z < p \leq \sqrt{x}$. Note that these numbers satisfy the requirements. Their number, by a crude estimate, is at least $$ cx+O(1)-\sum_{\sqrt{x} < p \leq 2x}(cx/p+O(1)) - \sum_{z < p \leq \sqrt{2x}}(cx/p^2 +O(1)), $$ which is at least $$ c(1-\log 2-1/z+o(1))x. $$ That is, the lower density is at least $$ c(1-\log 2-1/z)/2.$$ For $z:=5$ the left hand side exceeds $0.0142$, while for $z:=17$ it exceeds $0.0223$.

EDIT: I improved slightly my original argument.

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.