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.‎

$\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
    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$ Jun 25, 2016 at 20:03

1 Answer 1

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.

$\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$ 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$ 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
    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$ Jun 21, 2016 at 20:06

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.