2
$\begingroup$

In part of my research, I need to count (or find a polynomial bound for) the number of ‎possible ‎ways to select $n$ distinct integers less than the prime $p$, say $r_1, r_2, …, r_n$, which ‎are pairwise co-prime and the product of ‎any $k$ of them ($k<n$) is less than $p$. I call the ‎number I look for $\alpha$.‎

Let $p_i$ denotes the $i$-th prime number, and $P=\{ p_1, p_2, …, p_s\}$ denotes the set of all primes less than ‎‎$t=\dfrac{p}{p_{n-k}\cdot p_{n-k+1}\cdots p_{n-2}}$. Having in mind the idea of this answer, I think of these two ‎approaches:‎

‎Approach 1. The number of ways to partition a set of $a$ labelled objects into $n$ ‎nonempty ‎unlabelled subsets, for any $n\leq a \leq s$, is a lower bound for $\alpha$, i.e.‎

‎$$\sum_{a=n}^{s}{s \choose a}S(a,n) \leq \alpha,$$‎

‎where $S(a,n)$ is the Stirling number of the second type.‎ This bound, just, does not count the possibilities that in some of the partitions above, some $p_i$'s ‎can be replaced by ‎$p_i^j$, for some $1 ‎‎< j< \log_{p_i}t$.‎

‎Approach 2. The number of possible selections is bounded by:‎ ‎$$ \alpha \leq {{t}\choose{n}}.$$

I am looking forward any idea to improve these bounds.‎

Improve this question
$\endgroup$
2
  • $\begingroup$ For the sake of clarification, I reworded the question. Thanks to @Paseman, I also think that there ‎are enough approaches now, and I need to improve the existing bounds.‎ $\endgroup$
    – Toughee
    Commented Jun 25, 2016 at 14:26
  • $\begingroup$ I recommend grouping these subsets according to the product of their $k$ largest elements. For every $m<p$, the number of ordered factorizations of $m$ into $k$ divisors is roughly $\frac1{(k-1)!}(\log m)^{k-1}$ on average, and restricting these factorizations to being pairwise relatively prime won't change this significantly. For each such factorization, where $s$ is the smallest of the $k$ factors, we would then have about $Cs^{n-k}$ ways to fill out the $k$-tuple into an $n$-tuple, for some constant $C$ related to values of the zeta function and $\phi(m)/m$.... $\endgroup$
    – Greg Martin
    Commented Jun 25, 2016 at 20:03

1 Answer 1

Reset to default
1
$\begingroup$

Here is another approach which may give some light on estimating your desired quantity (the number of sets of $n$ numbers $r_i$ which are mutually coprime and whose product is less than $p$). I don't see the significance of $p$ being prime, and will replace $p$ with $m^n$.

Let $R$ be a finite subset of the primes, let $P$ be the product of the primes in $R$ and let $q_m(R)$ count those multiples of $P$ at most $m$ which are $R$-smooth. Let $S$ be a partition of $n$ parts of some finite subset of primes, with parts called $R_i$. The number of ways of choosing a number from each part is at least $\prod_i q_m(R_i)$ to get a set of $n$ coprime numbers whose product is at most $m^n$. This can be tweaked to change the $m$ to $m_i$ whose product is at most $m^n$, but then one does some double counting if insufficient care is taken.

Now a lower bound for your count can be written using the notation above (where the sum is over all $S$ which are $n$-part partitions of a subset of enough primes) as $$\sum_S \prod_i q_m(R_i).$$ Note that multiple choices of $r_i$ can result in the same product, so it is not enough to consider smooth numbers less than $m^n$.

While the above may help derive a lower bound, it may be more fruitful to consider for each integer $p\lt m^n$ the number of $n$- part coprime factorizations of $p$, then sum that number from $p=1$ to $m^n$. If I get a good idea for estimation with either scheme, I will add it below.

Gerhard "Happy Father's Day To You" Paseman, 2016.06.19.

Improve this answer
$\endgroup$
4
  • $\begingroup$ While your description seems to allow multiple $r_i=1$ (which would make some of the analysis easier) I suspect the intent is to make all of them greater than $1$. It would help the question greatly if you could clarify this and if you could provide some motivation. Gerhard "Really Likes Well Motivated Questions" Paseman, 2016.06.19. $\endgroup$
    – Gerhard Paseman
    Commented Jun 19, 2016 at 19:10
  • $\begingroup$ Let me clarify. Coprime implies distinct only when the items involved are different from 1. 1 is coprime to itself, so if you need the r_i to be distinct but include 1, you should declare that, and proceed as you suggested. I think finding the n-part properly coprime factorizations of p will be easy, and estimating for how many p you need them will need some results from analytic number theory. Also, if permutations of the r_i are counted as distinct, you should also make that clear. Gerhard "Clearer Questions Are Much Preferred" Paseman, 2016.06.19. $\endgroup$
    – Gerhard Paseman
    Commented Jun 19, 2016 at 21:58
  • $\begingroup$ First, you are right, I edited the question and removed my comment. Second, in your approach -‎considering that $P$ is the set of the product of the primes in $R$ - I think the question here is ‎how to calculate/estimate each $q_m(R_i)$? If I got it correctly. Third, for the last scheme, is there ‎any efficient way to count the number of $n$-part coprime factorizations of $p$? Maybe I need to ‎ask it separately! ‎ $\endgroup$
    – Toughee
    Commented Jun 20, 2016 at 15:44
  • $\begingroup$ While you could try the route involving $q_m$, that will at best give you a lower bound, with no clarity on size of error. If you try the prime decomposition, you instead are faced with a known combinatorial problem (h-many distinct balls into n unlabeled bags, where h is the number of distinct prime factors) plus a studied number theory problem (how many integers below x have at least n distinct prime factors). If you aren't too concerned with error, you may get quick estimates this way. Gerhard "Is Unsure About That Way" Paseman, 2016.06.21. $\endgroup$
    – Gerhard Paseman
    Commented Jun 21, 2016 at 20:06

You must log in to answer this question.

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