I am reading chapter 31 of Introduction to Algorithms (CRLS) and I encountered some difficulties while solving 31.2-9. I managed to prove the first part of a problem, but I can't prove the generalized version.

This is the problem statement:

Prove that $n_1, n_2, n_3,$ and $n_4$ are pairwise relatively prime if and only if $gcd(n_1 n_2, n_3 n_4) = gcd(n_1 n_3, n_2 n_4) = 1$. More generally, show that $n_1, n_2, ..., n_k$ are pairwise relatively prime if and only if a set of $\lceil \log(k) \rceil$ pairs of numbers derived from the $n_i$ are relatively prime.

Proof of the first part: $gcd(n_1 n_2, n_3 n_4) = 1$ means that $n_1 n_2$ and $n_3 n_4$ doesn't have any common factors, so $gcd(n_1, n_3) = gcd(n_1, n_4) = gcd(n_2, n_3) = gcd(n_2, n_4) = 1$. The same is for the second equation so, $gcd(n_1, n_2) = gcd(n_1, n_4) = gcd(n_3, n_2) = gcd(n_3, n_4) = 1%%$

  • $\begingroup$ Is the $\log$ in the ceiling of $\log(k)$ the base $2$ log? At least that would give for $k=4$ the result of $2$ sets of numbers as in your example, . $\endgroup$
    – coffeemath
    May 27 '16 at 18:27
  • $\begingroup$ Hint: en.wikipedia.org/wiki/Hadamard_matrix $\endgroup$ May 27 '16 at 18:36
  • $\begingroup$ Yes, it is in base 2. $\endgroup$
    – J. Abraham
    May 27 '16 at 18:40

Hint: Assume that we have $k$ positive integers $a_0,\ldots,a_{k-1}$ and $k\leq 2^m$. For any $j$ such that $1\leq j \leq m$, we define $f_j(m)$ as the value of the $(j-1)$-th bit from the right in the binary representation of $m$, then take: $$ N_1^{(j)} = \prod_{k : f_j(k)=1}a_k,\qquad N_0^{(j)} = \prod_{k: f_j(k)=0}a_k $$ and compute $G_j=\gcd\left(N_0^{(j)},N_1^{(j)}\right)$. If $G_j=1$ for any $j$ in the range $[1,m]$, the original integers are pairwise coprime, otherwise they are not. And obviously $m\approx \log_2(k)$.

This construction is kindly stolen from Hadamard matrices.

  • $\begingroup$ How is this related to Hadamard matrices? What parts of the wiki article cited should I read? $\endgroup$
    – hengxin
    Mar 29 '17 at 12:51
  • $\begingroup$ @hengxin: indeed a more accurate reference is en.wikipedia.org/wiki/Sperner%27s_theorem $\endgroup$ Mar 29 '17 at 13:12
  • $\begingroup$ Still confused. Would you please provide more details? What are the characterizations of $N_1^{(j)}$ and $N_0^{(j)}$ and how are they related to the Sperner theorem? It seems that there are some patterns. But I failed to identify them. Thanks. $\endgroup$
    – hengxin
    Mar 29 '17 at 13:29
  • $\begingroup$ I found that the problem of covering a (complete) graph by complete bipartite graphs is closely related to this problem. For example, see the paper On covering graphs by complete bipartite subgraphs by S. Jukna and A.S. Kulikov, 2009. $\endgroup$
    – hengxin
    Mar 31 '17 at 6:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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