Let $X, Y$ be positive real numbers, and let $p_1, ... p_n$ be the primes less than $Y$. How many subsets $S$ of the integers from 1 to $n$ are there such that the product of the $p_i$'s with $i$ in $S$ is less than $X$, as a function of $X,Y$?

Clearly, if $X$ is sufficiently large relative to $Y$, then all choices of $S$ work. I am interested in the case when $Y$ is not too small compared to $X$, say $Y = X/C$ for some fixed positive constant $C$ larger than 1.

  • $\begingroup$ If I understand the question correctly, it is $2^{-\pi(Y)}$ times the number of square-free $Y$-smooth numbers below $X$. If $X=CY$ for fixed $C$, a $6/\pi^2$ fraction of numbers below $X$ are square-free, and all but an $O(1/\log X)$ fraction are $Y$-smooth, so the result is ~ $2^{-\pi(Y)}6/\pi^2=2^{-(1+o(1))Y/\log Y}$. $\endgroup$ – Emil Jeřábek Jun 20 '14 at 14:28
  • $\begingroup$ Sorry, a factor of $X$ is missing in the last but one expression (but it is swamped in the final $o(1)$, so it doesn’t matter). $\endgroup$ – Emil Jeřábek Jun 20 '14 at 14:38
  • $\begingroup$ Can you clarify? Do you mean you are taking the product of a fixed number $n$ of primes randomly chosen from all the primes less than $Y$? Obviously if at least two of those primes are greater than $Y/k$ the product will be greater than $Y^2/k^2$... $\endgroup$ – Robert Israel Jun 20 '14 at 15:05
  • $\begingroup$ I phrased thr question in terms of counting, which is hopefully more clear. $\endgroup$ – Stanley Yao Xiao Jun 20 '14 at 15:18

Distinct sets of primes have distinct products, hence you are counting the number of square-free $Y$-smooth integers below $X$.

The number of $Y$-smooth integers below $X$ is $$\Psi(X,Y)=X\rho(u)+O(X/\log Y),$$ where $X=Y^u$, and $\rho$ is Dickman’s function, which is $1-\log u$ for $u\in[1,2]$. In the range you are interested in (or more generally, if $X=Y^{1+o(1)}$), we have $u=1+o(1)$, hence $\rho(u)=1+o(1)$, and $$\Psi(X,Y)=X+o(X).$$ In other words, the number of integers below $X$ that are not $Y$-smooth is $o(X)$. Since there are $(6/\pi^2)X+O(\sqrt X)$ square-free integers below $X$, the number of your sets is $$\frac6{\pi^2}X+o(X).$$


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.