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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .