0
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Jun 20, 2014 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$ Jun 20, 2014 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$ Jun 20, 2014 at 15:05
  • $\begingroup$ I phrased thr question in terms of counting, which is hopefully more clear. $\endgroup$ Jun 20, 2014 at 15:18

1 Answer 1

5
$\begingroup$

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).$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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