1
$\begingroup$
  1. Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of picking $n$ pairwise coprime integers each of $m$ bits when they exist?

  2. Given $m$ and $n$ in $\mathbb Z_{>0}$ what is the computational complexity of deciding if there are $n$ pairwise coprime integers each of $m$ bits?

$\endgroup$
1
$\begingroup$

What exactly interests you? It might be more interesting to ask about finding $m$ pairwise relatively prime numbers between $s$ and $t$ when $t-s$ is "small" with respect to $s.$ The case $s=2^n$ and $t=2^{n+1}$ seems too broad. The best you can do is to take all the primes and prime powers in that range and augment that with some products $p\cdot p'$ where $p$ ranges over the primes less than $\sqrt{2^{n}}$ not used so far and, for each one, an appropriate prime cofactor $p'$.

Let me first discuss $n=20.$

The number of primes with exactly $20$ bits is $N=\pi(2^{21})-\pi(2^{20}) =73586$. Given that, the answer to your question 2 with $n=20$ is definitely yes for $m$ below $N+1$ Then you can use just primes. One can stuff in $234$ more using prime powers and semi-primes (detals below). Doing question 1 for $m=70000$ would be tedious. If you wanted $n=20$ and $m=481$ then one could find $k$ , a $20$ bit multiple of $2\cdot 3\cdot 5\cdot 7\cdot 11=2310$ and take it along with $k+j$ for the $480$ numbers $j$ less than $2310$ and relatively prime to it.

What about finding the absolute largest size set of pairwise relatively prime $20$-bit integers? I claim that it is not hard to find that it is $N+57+5+6+166$ the extra terms are for

  • $57$ prime squares, $p^2$ for $1331 \leq p \leq 1447$.
  • $5$ prime cubes, $p^3$ for $p=103,107,109,113,127$
  • $6$ more: $37^4 ,17^5 ,11^6, 5^9,3^{13}$ and $2^{20}.$
  • $166$ primes under $1024$ not yet used (we will give each one a prime cofactor)

If we pair each of the $166$ small ones with the largest possible large prime we get

$7 \cdot 299569, 13\cdot 161309, 19\cdot 110359, 23\cdot 91163, 29\cdot 72313, 31\cdot 67631, 41\cdot 5113$

and continue on to $991\cdot 2113, 997 \cdot 2099, 1009 \cdot \mathbf{2069},1013 \cdot 2069,1019 \cdot \mathbf{2053},1021 \cdot 2053 $

The only overlaps are the two shown in bold which can be replaced with somewhat smaller primes such as $1997, 1999, 2003, 2011, 2017, 2027, 2029, 2039.$

The only "hard" step was perhaps that of computing $N=\pi(2^{21})-\pi(2^{20})=155611-82025=73586.$ Without that we wouldn't know exactly for what $m$ we pass from possible to not possible. But we would know how to get about where. For example easy estimates give $81519 \lt \pi(2^{20}) \lt 82158$ and $154701 \lt \pi(2^{21}) \lt 155852.$

$\endgroup$
  • $\begingroup$ There are so many issues with this obvious answer that everyone is first aware of 1. What is the gap between primes? 2. What is the complexity of choosing a prime? 3. What is the gap between coprime versus gap between prime numbers? 4. It is easier to choose two coprimes in $m+1$ time complexity while it is unclear how to choose even two primes and many other issues such as not quantifying 'might be as good as it gets'. $\endgroup$ – Brout Oct 8 '18 at 7:47
  • $\begingroup$ OK, I made it less vague. $\endgroup$ – Aaron Meyerowitz Oct 8 '18 at 20:04
  • $\begingroup$ What is the complexity of picking one prime of $m$ bits? $\endgroup$ – Brout Oct 9 '18 at 0:49
  • $\begingroup$ To find $m$ pairwise relatively prime $n$ bit integers is not hard for manageable size $m.$ For $m=1$ anything will do. For $m=3$ use $\{2^n+j \mid j=1,2,3\}.$ Instead of primes take probable primes (or numbers with no small prime factors) and just check gcds. Or find $km$ primes each with $n/k$ bits and take products. $\endgroup$ – Aaron Meyerowitz Oct 9 '18 at 3:46
  • $\begingroup$ Please answer my question. Do you know the complexity of choosing a probable prime? Are you aware of polymath project on deterministic selection of primes? Please take a look. The last point you mention is the most relevant. $\endgroup$ – Brout Oct 9 '18 at 7:18

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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