Proof. Suppose \(p^k\) is the largest power of \(p\) dividing \(n\), with \(k\geq p\). We can partition the \(\tau(n)\) divisors of \(n\) into \(k+1\) sets each having size \(\tau(n/p^k)\) according to the power to which \(p\) appears as a factor. Only one of those sets will contain integers coprime to \(p\), and so the total number of divisors of \(n\) coprime to \(p\) is \(\frac{\tau(n)}{k+1} \leq \frac{\tau(n)}{p+1}\). On the other hand, the number of integers in \([1,\tau(n)]\) divisible by \(p\) is \[\left\lfloor\frac{\tau(n)}{p}\right\rfloor = \frac{\tau(n) - r}{p}.\label{eq:taupratio}\tag{1}\] Since \(\tau(n)>r(p+1)\) we find that \((\tau(n) -r)(p+1)>\tau(n)p\) and thus the quantity in 1 is strictly greater than \(\frac{\tau(n)}{p+1}\), the upper bound we just found for the number of divisors of \(n\) coprime to \(p\). Thus, there are too few divisors of \(n\) coprime to \(p\) to match with these integers up to \(\tau(n)\) divisible by \(p\). ◻

Proof. It suffices to show that the set of matchable numbers that are not M-numbers has asymptotic density 0. The set of integers divisible by some \(p^p\) for \(p\ge N\) has density \(\ll N^{-N}\). If \(p^p{\,|\,}n\) and \(n\) is matchable, then Corollary 1 implies that \(\omega(n) \le 2\log p/\log 2\). So, if \(n\) is matchable and not an M-number, it is either divisible by some \(p^p\) for \(p\ge N\) or \(\omega(n)\le 2\log N/\log 2\).

The counting function to \(x\) of the latter numbers \(n\) is \(\ll x(\log\log x)^{2\log N/\log 2}/\log x\), so for \(N\) fixed, the set has density 0. Putting the two together, the upper density is \(\le N^{-N}\), and since \(N\) is arbitrary, the corollary is proved. ◻

Proof. We may assume \(n\) is odd. A coprime matching for \(2n\) pairs \(D(2n)=D(n)\cup 2D(n)\) with \([1,\tau(2n)]=[1,2\tau(n)]\). Since the even divisors \(2D(n)\) must be paired with odd integers in \([1,2\tau(n)]\), the odd divisors \(D(n)\) are paired with the even integers \(\{2,4,\ldots,2\tau(n)\}\). Dividing by 2, this gives a coprime matching of \(D(n)\) with \([1,\tau(n)]\), so \(n\) is matchable. ◻

Proof. We proceed by induction on the construction of \(S\). For the base case, let \(S\) be an arithmetic progression of length \(m\) with common difference \(q\) where \(\gcd(d,q)=1\). If \(m\geq d\), the elements of \(S\) form a complete residue system modulo \(d\), and among any \(d\) consecutive terms, exactly one is divisible by \(d\). So, the count of \(d\)-multiples is \(m/d+\theta\) with \(|\theta| \le 1\).

For the inductive step, suppose \(S=S_1\cup S_2\) with \(S_1\cap S_2=\emptyset\). Then the count of \(d\)-multiples in \(S\) equals \[(|S_1|/d+\theta_1)+(|S_2|/d+\theta_2)=|S|/d+(\theta_1+\theta_2),\] where \(|\theta_1|\le k_1\), \(|\theta_2|\le k_2\), so \(|\theta_1+\theta_2|\le k_1+k_2\).

If \(S_2\subseteq S_1\) and \(S=S_1\setminus S_2\), then the count of \(d\)-multiples in \(S\) equals \[(|S_1|/d+\theta_1)-(|S_2|/d+\theta_2)=|S|/d+(\theta_1-\theta_2),\] where \(|\theta_1-\theta_2|\le k_1+k_2\). ◻

Proof. The error bound of \(2^{j-1}\) follows from Lemma 2. We prove the existence of the stated partition by induction on \(j\).

For \(j=1\), since \(p_1=2\) by assumption, we partition \(I\) into \(A_{1,1}\), the even integers in \(I\), and \(A_{2,1}\), the odd integers. Each is a single arithmetic progression, hence a \(1\)-AP combination.

For \(j=2\), let \(p=p_2\) be the second prime. We construct the four sets as follows. Let \(x\) be chosen so that the number of odd integers in \(I\cap[1,x]\) that are not divisible by \(p\) equals \(L/ 4\). To see that such an \(x\) exists, note that the majority of odd integers in \(I\) are not divisible by \(p\). Indeed, the number of odd elements of \(I\) divisible by \(p\) is \(\le L/(2p)+1\), and this is \(< L/4\) by the assumption \(L\ge4^j\). Set \[\begin{align} A_{2p,2} &= \{\text{odd } i\in I : i\le x,\, p\nmid i\},\\ A_{2,2} &= \{\text{odd } i\in I : p\mid i,\, i\le x\}\cup\{\text{odd } i\in I : i>x\}. \end{align}\] Similarly, let \(y\) be chosen so that the number of even integers in \(I\cap[1,y]\) not divisible by \(p\) equals \(L/4\), and set \[\begin{align} A_{p,2} &= \{\text{even } i\in I : i\le y,\, p\nmid i\},\\ A_{1,2} &= \{\text{even } i\in I : p\mid i,\, i\le y\}\cup\{\text{even } i\in I : i>y\}. \end{align}\] Each of \(A_{2p,2}\) and \(A_{p,2}\) is the difference of two arithmetic progressions, hence a \(2\)-AP combination by rule (3). Each of \(A_{2,2}\) and \(A_{1,2}\) is the disjoint union of two arithmetic progressions, hence a \(2\)-AP combination by rule (2). Thus each set is a \(2\)-AP combination.

For \(j\ge 3\), assume the result holds for \(j-1\): each \(A_{v,j-1}\) is a \(2^{j-2}\)-AP combination. For each \(v\mid m_{j-1}\), we partition \(A_{v,j-1}\) into \(A_{v,j}\) and \(A_{p_jv,j}\) using a cutoff as follows. Let \(z_v\) be chosen so that the number of elements of \(A_{v,j-1}\) that are \(\le z_v\) and not divisible by \(p_j\) equals \(L/2^j\). Set \[\begin{align} A_{p_jv,j} &= \{i\in A_{v,j-1}: i\le z_v,\, p_j\nmid i\},\\ A_{v,j} &= \{i\in A_{v,j-1}: p_j\mid i,\, i\le z_v\}\cup\{i\in A_{v,j-1}: i>z_v\}. \end{align}\] Every element of \(A_{p_jv,j}\) is coprime to \(p_j\) (and was already coprime to \(v\)), so is coprime to \(p_jv\). Every element of \(A_{v,j}\) was already coprime to \(v\).

We now verify the sizes. By the induction hypothesis, the number of \(p_j\)-multiples in \(A_{v,j-1}\) is within \(2^{j-2}\) of \(|A_{v,j-1}|/p_j=L/(p_j2^{j-1})\), hence at most \[\frac{L}{p_j2^{j-1}}+2^{j-2}\le \frac{L}{ 3\cdot2^{j-1}}+\frac{L}{ 2^{j+2}}<\frac{L}{2^j},\] using \(p_j\ge 3\) and \(L\ge 4^{j}\). Thus there are enough non-\(p_j\)-multiples in \(A_{v,j-1}\) to fill \(A_{p_jv,j}\) to size \(L/2^j\), and \(A_{v,j}\) receives the remaining \(L/2^j\) elements.

It remains to show each new set is a \(2^{j-1}\)-AP combination. By induction, we know that each set \(A_{v,j-1}\) is a \(2^{j-2}\)-AP combination.

A key observation is that intersecting with \(\{i:i\le z_v\}\) or \(\{i:i>z_v\}\) preserves the AP-combination structure of a set. If \(T\) is a \(k\)-AP combination, then \(\{i\in T:i\le z_v\}\) and \(\{i\in T:i>z_v\}\) are each \(k\)-AP combinations. (We simply truncate each constituent arithmetic progression. This could result in some of them being empty.) Similarly, restricting to \(p_j\)-multiples preserves the AP-combination structure, since if \(T\) is a \(k\)-AP combination, then \(\{i\in T:p_j\mid i\}\) is a \(k\)-AP combination (just replace each arithmetic progression by the sub-arithmetic progression of its \(p_j\)-multiples).

Now consider each of the sets used to construct \(A_{v,j}\) and \(A_{p_jv,j}\). First, \(\{i\in A_{v,j-1}:p_j\mid i,\,i\le z_v\}\) is just \(A_{v,j-1}\) restricted to \(p_j\)-multiples and then to \(\{i\le z_v\}\). So, it has the same combination structure as \(A_{v,j-1}\), hence is a \(2^{j-2}\)-AP combination. Similarly \(\{i\in A_{v,j-1}:i>z_v\}\) is \(A_{v,j-1}\) restricted to \(\{i>z_v\}\), hence also a \(2^{j-2}\)-AP combination. Since \(A_{v,j}\) is the disjoint union of these two it is a \(2^{j-1}\)-AP combination.

For \(A_{p_jv,j}\), we note that \[\begin{align} A_{p_jv,j} &= \{i\in A_{v,j-1}:p_j\nmid i,\,i\le z_v\} \\ &= \{i\in A_{v,j-1}:i\le z_v\}\setminus\{i\in A_{v,j-1}:p_j\mid i,\,i\le z_v\}. \end{align}\] As argued above, each of these sets is a \(2^{j-2}\)-AP combination, and the latter is a subset of the former, so their difference is a \(2^{j-1}\)-AP combination. This completes the induction. ◻

Proof of Theorem 1. Let \(u\) be a squarefree number satisfying the hypotheses with \(\ell=\omega(u)\). If \(u\) is odd, then \(2u\) is even with \(\omega(2u)=\ell+1\ge46\) prime factors. If we can show that \(2u\) is matchable, then \(u\) is matchable by Lemma 1. Thus we may assume \(u\) is even, so that \(2=p_1<p_2<\cdots<p_\ell\) where \(u=p_1p_2\cdots p_\ell\).

For an integer \(j\le\omega(u)/2\) to be chosen later, we let \(m_j=p_1p_2\cdots p_j\) and \(n = u/m_j\), so that \(m_j\) is the product of the \(j\) smallest primes dividing \(u\) while \(n\) contains the rest. We then apply Lemma 3 using these \(j\) smallest prime factors and \(I=[1,\tau(u)]=[1,2^{j+\omega(n)}]\). Since \(4^{j} \le \tau(u)\), the lemma allows us to produce a partition of \(I\) into sets \(A_{v,j}\) as described in the lemma, each having size \(\tau(n)\).

Thus it now suffices to show that there are one-to-one correspondences between \(D(n)\) and each of the sets \(A_{v,j}\) with corresponding numbers relatively prime. Indeed, for \(v{\,|\,}m_j\), the correspondence can instead be between \(A_{v,j}\) and \(vD(n)\), keeping the coprime property. Then, as \(D(u)\) is the disjoint union of the sets \(vD(n)\) as \(v\) runs over all of the divisors of \(m_j\), we can piece together these matchings and so have a coprime matching of all divisors of \(u=m_jn\) to \([1,\tau(u)]\).

To show the existence of these one-to-one correspondences we note that any divisor \(d\mid n\) is coprime to \(m_j\), so by Lemma 3, the number of integers in \(A_{v,j}\) divisible by \(d\) is within \(2^{j-1}\) of \(\tau(n)/d\).

We choose \(j\) as follows. For \(\ell \ge68\) we take \(j=\lfloor\sqrt{\ell}\rfloor\) and for \(45\le\ell\le67\) we take \(j=4\) except \(j=3\) when \(\ell\in\{46,47,48\}\) and \(j=5\) when \(\ell=52\). Note that in every case we have \(j\le\sqrt\ell\). With these choices, \(\omega(n) = \ell - j \geq 41\) and one can verify that \[f(n) :=\sum_{p\,|\,n}\frac{1}{p}= \sum_{i=j+1}^{\ell} \frac{1}{p_i} \leq \sum_{i=j+1}^{\ell} \frac{1}{P_i} < \frac{93}{100}, \label{eq:primesumbound}\tag{2}\] where \(P_i\) is the \(i\)-th prime. To see this in the case that \(j=\lfloor\sqrt\ell\rfloor\), we use that \(P_i>i\log i\) (see [8]), so \[f(n)<\frac{1}{\sqrt{68}\log\sqrt{68}}+\int_{\sqrt\ell}^\ell\frac{dt}{t\log t}<0.06+\log2<0.76.\]

We use Hall’s theorem for the bipartite graph on \(A=A_{v,j}\) to \(D(n)\) where there is an edge precisely when \(a\in A\) and \(d{\,|\,}n\) are coprime. Suppose that \(S\subset A\) and that \(s\in S\) minimizes \(k=\omega((s,n))\). We wish to show that \(|S|\) is bounded above by the size of the neighborhood \(N(S)\) of \(S\). If \(k=0\) then the neighborhood of \(S\) is all of \(D(n)\), so the condition holds.

Assume that \(k\ge1\). Since each element \(s\) of \(S\) is in \(A\subset[1,\tau(u)]\) and is divisible by some \(d\mid n\) with \(\omega(d)=k\), we have \[|S|\le\sum_{\substack{d\,|\,n\\\omega(d)=k\\d\leq \tau(u)}}\sum_{\substack{a\in A\\d\,|\,a}}1 \le\sum_{\substack{d\,|\,n\\\omega(d)=k}}\left(\frac{\tau(n)}{d}+2^{j-1}\right).\] By the multinomial theorem, we have \[\sum_{\substack{d\,|\,n\\\omega(d)=k}}\frac{1}{d}\le\frac{f(n)^k}{k!},\] so that \[\begin{align} |S| &\le\tau(n)\frac{f(n)^k}{k!}+2^{j-1}\binom{\omega(n)}{k} \notag \\ &< \frac{\tau(n)}{2^{k}}\left(\frac{(93/50)^k}{k!}+2^{2j-1+k-\ell + \log_2{\binom{\omega(n)}{k}}}\right). \label{eq:keq2Sbound} \end{align}\tag{3}\] Since the primes dividing \(n\) are all at least \(P_{j+1}\), a divisor \(d\) of \(n\) with \(\omega(d)=k\) satisfies \(d \geq P_{j+1}P_{j+2}\cdots P_{j+k}\). For such a \(d\) to divide any element of \(A\subset [1,\tau(u)]\), we need \(d \leq \tau(u) = 2^\ell\), as we have seen, so we only need consider \(k \leq \overline{k}\), where \(\overline{k}\) is the largest integer with \(P_{j+1} P_{j+2} \cdots P_{j+ \overline{k}} \leq 2^\ell\).

3.1 Case \(k\ge4\).↩︎

For Hall’s condition to hold, since the neighborhood of \(S\) has size at least \(\tau(n)/2^k\), it suffices if \[\label{eq:kge4constraint} \frac{(93/50)^k}{k!}+2^{2j-1+k-\ell + \log_2\binom{\omega(n)}{k}} < 1\tag{4}\] for each \(k\) with \(4 \leq k \leq \overline{k}\). Note that \((93/50)^4/24 < 0.50\), so we need only show that the second term is at most \(\frac{1}{2}\).

Let \(E_k:= 2j-1+k-\ell+\log_2\binom{\omega(n)}k\) denote the exponent, so the second term equals \(2^{E_k}\).

Large \(\ell\) (\(\ell \geq 192\)). Set \(j = \lfloor\sqrt{\ell}\rfloor\). We first bound \(\overline{k}\). Since \(j = \lfloor\sqrt{\ell}\rfloor \geq 13\) for \(\ell\ge192\), we have \(P_{j+1} \geq P_{14} = 43\). The constraint \(\prod_{i=1}^{k} P_{j+i} \leq 2^\ell\) implies \(43^k < 2^\ell\), giving \(\overline{k} <\ell/\log_243 < 0.185\ell\). With \(\omega(n)= \ell - j > \ell - \sqrt{\ell}\), we have \(\overline{k}/ \omega(n)< 0.20\) for \(\ell \geq 192\).

Using the entropy function \(H(x)=-x\log_2 x-(1-x)\log_2(1-x)\) and the standard bound \(\log_2\binom{a}{b}<a\cdot H(b/a)\), writing \(c=k/\omega(n)<0.20\) and using that \(H\) is increasing on \((0,\tfrac{1}{2})\), we have \(H(c)<H(0.20)<0.722\), so \(c+H(c)<0.922\). Thus \[\begin{align} E_k&\le 2j-1+(c+H(c))\omega(n)-\ell\\ &<2\sqrt{\ell}-1+0.922(\ell-\sqrt{\ell})-\ell\\ &=-0.078\ell+1.078\sqrt{\ell}-1<-1.03 \end{align}\] for \(\ell\ge192\). Since \((93/50)^4/4!<0.50\) and \(2^{E_k}<0.50\), we have 4 for \(4\le k\le\overline{k}\).

Moderate \(\ell\) (\(68 \leq \ell < 192\)). We use \(j = \lfloor\sqrt{\ell}\rfloor\) and verify 4 by direct computation. For each \(\ell\) in this range, we find \[\overline{k} = \max\{k:\prod_{i=j+1}^{j+k} P_i <2^\ell\}.\] Then, for each \(k\) with \(4 \leq k \leq \overline{k}\), we compute \(E_k = k + 2j-1 - \ell + \log_2\binom{\ell-j}{k}\) and verify that \((93/50)^k/k! + 2^{E_k} < 1\).

Small \(\ell\) (\(45 \leq \ell \leq 67\)). Here we take (as above) \(j=4\) when \(\ell=45\), \(j=3\) for \(46\le\ell\le48\), \(j=4\) for \(49\le\ell\le67\) (except \(j=5\) when \(\ell=52\)). As above, we verify 4 directly for all \(4\leq k \leq \overline{k}\). This concludes the case \(k\ge4\) for all \(\ell\ge45\).

3.2 Case \(k=3\).↩︎

Here the neighborhood of \(S\) has at least \(\tau(n)/8\) elements. Let \(a_1\in S\) with \((a_1,n)=q_1q_2q_3\) for distinct primes \(q_1,q_2,q_3\) dividing \(n\).

First, suppose that the triple \(\{q_1,q_2,q_3\}\) is unique (every \(a\in S\) has \((a,n)=q_1q_2q_3\) or \(\omega((a,n))>3\)). Then \[\begin{align} |S| &\leq \sum_{\substack{a\in A\\q_1q_2q_3\mid a}}1 + \sum_{\substack{d\mid n\\\omega(d)=4}} \left(\frac{\tau(n)}{d}+2^{j-1}\right)\\ &\leq \frac{\tau(n)}{q_1q_2q_3}+2^{j-1} + \tau(n)\frac{f(n)^4}{24} + 2^{j-1}\binom{\omega(n)}{4}\\ &< \frac{\tau(n)}{8}\left(\frac{8}{q_1q_2q_3}+\frac{8f(n)^4}{24}+ 2^{2\sqrt{\ell}+2-\ell}\left(1+ \binom{\ell}{4}\right)\right), \end{align}\] using that \(\tau(n)=2^{\ell-j}\). Since \(q_1q_2q_3 \geq 7\cdot11\cdot13 = 1001\) for \(j=3\) and \(f(n)<0.93\), the expression in parentheses is at most \(8/1001 + 8(0.93)^4/24 + 2^{2\sqrt{\ell}+2-\ell}\binom{\ell}{4} < 0.26 + 2^{2\sqrt{\ell}+2-\ell}\binom{\ell}{4}\), which is \(<1\) when \(\ell\ge27\).

Now suppose \(S\) contains at least 2 elements \(a_1,a_2\) with \(\omega((a_i,n))=3\), say \((a_1,n)=q_1q_2q_3\) and \((a_2,n)=q_4q_5q_6\), with \(\{q_1,q_2,q_3\}\ne\{q_4,q_5,q_6\}\). The two triples share at most 2 primes, so by inclusion-exclusion \(|N(S)|\ge 2\cdot\tau(n)/8 - \tau(n)/16 = 3\tau(n)/16\). Also, \[\begin{align} |S| &\leq \tau(n)\frac{f(n)^3}{6} + 2^{j-1}\binom{\omega(n)}{3}\\ &< \frac{3\tau(n)}{16}\left(\frac{16f(n)^3}{18} + \frac{16}{3}\cdot 2^{2\sqrt{\ell}-1-\ell}\binom{\ell} {3}\right). \end{align}\] Since \(f(n)<0.93\), we have \(16(0.93)^3/18 < 0.72\), and \(\frac{16}{3}\cdot 2^{2\sqrt{\ell}-1-\ell} \binom{\ell}{3}<0.28\) for \(\ell\ge 25\). This completes the case \(k=3\).

3.3 Case \(k=2\).↩︎

Here the neighborhood of \(S\) has at least \(\tau(n)/4\) elements. Let \(a_1 \in S\) with \((a_1,n)=q_1q_2\) for distinct primes \(q_1,q_2 \mid n\).

First, suppose that the pair \(\{q_1,q_2\}\) is unique (every \(a\in S\) has \((a,n)=q_1q_2\) or \(\omega((a,n))>2\)). Then \[\begin{align} |S| &\leq \sum_{\substack{a\in A\\q_1q_2\mid a}}1 + \sum_{\substack{d\mid n\\\omega(d)=3}} \left(\frac{\tau(n)}{d}+2^{j-1}\right) \leq \frac{\tau(n)}{q_1q_2}+2^{j-1} + \tau(n)\frac{f(n)^3}{6} + 2^{j-1}\binom{\omega(n)}{3}\\ &< \frac{\tau(n)}{4}\left(\frac{4}{q_1q_2}+\frac{4f(n)^3}{6}+ 2^{2\sqrt{\ell}+1-\ell}\left(1+\binom{\ell} {3}\right)\right). \end{align}\] Since \(q_1q_2 \geq 77\) for \(j \geq 3\) and \(f(n)<0.93\), we have \(4/77 + 4(0.93)^3/6 < 0.59\), and \(2^{2\sqrt{\ell}+1-\ell}(1+\binom{\ell}{3})<0.33\) for \(\ell \geq 23\).

Now suppose \(S\) contains 2 elements \(a_1,a_2\) with \(\omega((a_i,n))=2\), say \((a_1,n)=q_1q_2\) and \((a_2,n)=q_3q_4\), with \(\{q_1,q_2\}\ne \{q_3,q_4\}\). Assume also that every other \(a\in S\) has either \((a,n)=q_1q_2\), \((a,n)=q_3q_4\) or \(\omega((a,n))\ge3\). The pairs share at most one prime, so by inclusion-exclusion \(|N(S)|\ge 2\cdot\tau(n)/4 - \tau(n)/ 8 = 3\tau(n)/8\).

Also, \[\begin{align} |S| &\leq \sum_{\substack{a\in A\\q_1q_2\mid a}}1 + \sum_{\substack{a\in A\\q_3q_4\mid a}}1 + \sum_{\substack{d\mid n\\\omega(d)\ge 3}}\left(\frac{\tau(n)}{d}+2^{j-1}\right)\\ &< \frac{3\tau(n)}{8}\left(\frac{8}{3}\cdot\frac{2}{77}+\frac{8f(n)^3}{18}+ \frac{8}{3}\cdot 2^{2\sqrt{\ell}-1-\ell}\left(2+\binom{\ell}{3}\right)\right). \end{align}\] Since \(f(n)<0.93\), we have \(16/(3\cdot 77) + 8(0.93)^3/18 < 0.43\), and \(\frac{8}{3}\cdot 2^{2\sqrt{\ell}-1-\ell}(2+\binom{\ell}{3})<0.5\) for \(\ell\ge21\).

So now assume that there are at least 3 different values of \((a,n)\) for \(a\in S\) with exactly 2 prime factors. If the 3 values are \(q_1q_2,q_3q_4,q_5q_6\), then the case when one prime is shared among all 3 numbers gives the smallest size for \(N(S)\) and that size is \((7/16)\tau(n)\). Then \[|S|<\frac{7\tau(n)}{16}\left(\frac{16f(n)^2}{14}+\frac{16}{7}\cdot2^{2\sqrt{\ell}-1-\ell}\binom{\omega(n)} 2\right)<\frac{7\tau(n)}{16}(0.99+0.01),\] for \(\ell\ge26\), completing the case \(k=2\).

3.4 Case \(k=1\).↩︎

Here the neighborhood of \(S\) has at least \(\tau(n)/2\) elements, so we may assume that \(|S| \geq \tau(n)/2\). Let \(a_1 \in S\) with \((a_1,n)=q_1\) for some prime \(q_1 | n\).

First, suppose that \(q_1\) is unique (every \(a\in S\) has \((a,n)=q_1\) or \(\omega((a,n))\ge2\)). Then \[\begin{align} |S|&\le \sum_{\substack{a\in A\\q_1\mid a}}1+ \sum_{\substack{a\in A,\,q_1\nmid a\\\omega((a,n))\ge2}}1 \le \frac{\tau(n)}{q_1}+2^{j-1}+\sum_{\substack{d\mid n,\,q_1\nmid d\\\omega(d)=2}} \left(\frac{\tau(n)}{d}+2^{j-1} \right)\\ &\le\frac{\tau(n)}{q_1}+2^{j-1}+\tau(n)\frac{(f(n)-1/q_1)^2}{2}+2^{j-1}\binom{\omega(n)-1}2\\ &<\tau(n)\left(\frac{f(n)^2}{2}+\frac{1-f(n)}{q_1}+\frac{1}{2q_1^2}\right)+2^{j-1}\left(1+ \binom{\omega(n)-1}2\right). \end{align}\] Using \(f(n) < 93/100\) and \(q_1\geq P_{j+1} \geq 7\) for \(j\ge3\), the coefficient of \(\tau(n)\) is at most \(0.432 + 0.07/7 + 0.5/49 < 0.453\). Since \(\tau(n)=2^{\ell-j}\), \[\begin{align} |S|&<0.453\tau(n)+2^{j-1}\left(1+\binom{\omega(n)-1}2\right)\\ &\le \frac{\tau(n)}{2}\left(0.906+2^{2\sqrt{\ell}-\ell}\left(1+\binom{\ell-4}2\right)\right). \end{align}\] This is \(<\tau(n)/2\) when \(\ell\ge30\).

Now suppose \(S\) contains elements \(a_i\) with \((a_i,n)=q_i\) for \(r\ge2\) distinct primes \(q_1,\dots,q_r\) dividing \(n\). The neighborhood of \(S\) contains all divisors of \(n\) coprime to at least one of \(q_1,\dots,q_r\).

If \(r=2\), this neighborhood has cardinality \(\frac{3}{4}\tau(n)\). We have \[\begin{align} |S|&\le\sum_{i=1}^2\left(\frac{\tau(n)}{q_i}+2^{j-1}\right)+\sum_{\substack{d{\,|\,}n\\\omega(d)=2}} \left(\frac{\tau(n)}{d}+2^{j-1}\right)\\ &<\tau(n)\left(\frac{1}{q_1}+\frac{1}{q_2}+\frac{f(n)^2}{2}\right)+2^{j-1}\left(2+\binom{\omega(n)}2\right). \end{align}\] Since \(q_1,q_2\ge P_{j+1}\) and \(f(n)<93/100\), the first term is at most \(2/7 + 0.433 < 0.72\tau(n)\) for \(j\ge3\). Thus, \[|S|<\frac{3\tau(n)}{4}\left(0.96+\frac{4}{3}\cdot 2^{2\sqrt{\ell}-1-\ell}\left(2+\binom{\ell-3}2\right)\right).\] This is \(<\frac{3}{4}\tau(n)\) when \(\ell\ge22\).

If \(r=3\), the neighborhood has cardinality at least \(\frac{7}{8}\tau(n)\), and \[\begin{align} |S|&<\tau(n)\left(\frac{1}{q_1}+\frac{1}{q_2}+\frac{1}{q_3}+\frac{f(n)^2}{2}\right)+2^{j-1}\left(3+ \binom{\omega(n)}2\right)\\ &<\frac{7\tau(n)}{8}\left(\frac{0.862}{7/8}+\frac{8}{7}\cdot 2^{2\sqrt{\ell}-1-\ell}\left(3+\binom{\ell-3} 2\right)\right), \end{align}\] using that \(q_1,q_2,q_3\) are distinct primes \(\ge7\) for \(j\ge3\) and \(f(n)<93/100\). Our estimate for \(|S|\) is \(<\frac{7}{8}\tau(n)\) for \(\ell\ge35\).

If \(r\ge4\), the neighborhood has cardinality at least \(\frac{15}{16}\tau(n)\), and \[\begin{align} |S|&\le\sum_{\substack{a\in A\\\omega((a,n))\ge1}}1\le\sum_{q\mid n}\sum_{\substack{a\in A\\q{\,|\,}a}}1 \le\tau(n)f(n)+2^{j-1}\omega(n)\\ &<\frac{93}{100}\tau(n)+2^{j-1}\omega(n)<\frac{15\tau(n)}{16}\left(\frac{93/100}{15/16}+\frac{16}{15}\cdot 2^{2\sqrt{\ell}-1-\ell}\ell\right). \end{align}\] This is \(<\frac{15}{16}\tau(n)\) for \(\ell\ge13\). Hall’s condition holds, completing the proof. ◻

Proof. Set \(v=u/q\), so \(u=vq\) and \(u\cdot p/q=vp\). We construct an injection \(f\) from integers counted by \(c_{\ge i}(vq)\) to those counted by \(c_{\ge i}(vp)\). For each integer \(a\) counted by \(c_{\ge i}(vq)\), set \[f(a)=\begin{cases} a & \text{if } \omega((v,a))\ge i, \text{ or } pq\mid a \text{ and } \omega((v,a))=i-1, \\ a\cdot p^j/q^j & \text{otherwise (where } q^j\,\|\, a\text{)}. \end{cases}\] Note that if \(a\) falls into the second case above, we must have \(\omega((v,a))=i-1\) and \(p\nmid a\). In each of the conditions for the first case above we find that \(a=f(a)\) is counted by both \(c_{\ge i}(vq)\) and \(c_{\ge i}(vp)\). Note that in the second case above, since \(p<q\) we have \(f(a)<a\le 2^{25}\) and \(f(a)\) odd, and since \(p,q\nmid v\) the primes of \(v\) dividing \(f(a)\) are the same as those dividing \(a\), so \(\omega((vp,f(a)))=(i-1)+1=i\). Thus \(f\) maps into the target set.

For injectivity note that in the second case, since \(q\nmid f(a)\), \(\omega((vq,f(a)))=i-1<i\), so the images \(f(a)\) lie outside the domain and cannot collide with the images from the first-case. ◻

Proof of Theorem 2. If \(u\) is squarefree, odd, and has at most 44 prime factors, then \(u\) is matchable by Proposition 3. If \(u\) is even and has \(\ell \leq 44\) prime factors, write \(u=2u'\); we create a matching as follows. By Proposition 2 applied to \(u'\) (which has \(\ell-1\) odd prime factors), there exists a coprime matching of the divisors of \(u'\) to the odd integers in \([1,2^\ell]\). We associate to each even divisor \(2d\) of \(u\) the odd integer matched to \(d\) by this proposition. Then, by Proposition 3 applied to \(u'\), there exists a coprime matching of \(D(u')\) to the integers in \([1,2^{\ell-1}]\); for every odd divisor \(d\) of \(u\) (which is also a divisor of \(u'\)), we match \(d\) to \(2a\), where \(a\in[1,2^{\ell-1}]\) is the integer matched to \(d\).

The first construction matches the \(2^{\ell-1}\) even divisors of \(u\) bijectively to the \(2^{\ell-1}\) odd integers in \([1,2^\ell]\), and the second matches the \(2^{\ell-1}\) odd divisors bijectively to the \(2^{\ell-1}\) even integers in \([2,2^\ell]\); together they give a perfect matching from \(D(u)\) to \([1,2^\ell]=[1,\tau(u)]\). Coprimality is preserved: \((2d,a)=(d,a)=1\) since \(a\) is odd, and \((d,2a)=(d,a)=1\) since \(d\) is odd. ◻

Proof. We follow the same plan as Lemma 3, with two modifications to handle tight primes and primes of \(m_j\) with exponent greater than \(1\).

The tight primes are handled first and all at once using an argument akin to the one in the introduction with \(M_p\). Since \(v_p(n)=p-1\) for each prime \(p\mid r\), the Chinese remainder theorem gives a bijection \(\rho\colon D(n_T)\to\{0,1,\ldots,r-1\}\) defined by \(\rho(d)\equiv v_p(d)\pmod p\) for each \(p\mid r\). We partition \([1,\tau(n)]=[1,r\tau(n_R)]\) into \(\tau(n_T)=r\) residue classes modulo \(r\), pairing \(d\) with the class \(\rho(d)\pmod r\). Each class is an arithmetic progression of length \(\tau(n_R)\) and common difference \(r\), and for any \(a \equiv \rho(d)\pmod r\) for \(d\mid n_T\), the coprimality \((a,d)=1\) holds because \(p\mid a\) if and only if \(p\nmid d\) for each \(p\mid r\). This plays exactly the role of the even/odd split on the prime \(2\) in Lemma 3, producing \(\tau(n_T)\) equal-length arithmetic progressions, one per divisor of \(n_T\), with no contribution to the size of \(K\).

The primes of \(m_j\) are then handled inductively. After processing \(p_1,\ldots,p_{i-1}\), we have \(r\cdot\tau(m_{i-1})\) sets (one per divisor of \(n_Tm_{i-1}\)), each a \(2^{i-1}\)-AP combination of size \(L'=\tau(m_j)\tau(n')/\tau(m_{i-1})\) with constituent APs having common differences coprime to \(p_i\). We then split each current set \(S\) into \(a_i+1\) equal subsets of size \(L'/(a_i+1)\), one for each \(v_{p_i}(d)\in\{0,\ldots,a_i\}\), with those for \(v_{p_i}(d)\ge1\) consisting of non-multiples of \(p_i\). Choose a cutpoint \(z\) so that the non-multiples of \(p_i\) in \(S\) before \(z\) number exactly \(a_i\cdot L'/(a_i+1)\). By Lemma 2, the count of \(p_i\)-multiples in \(S\) is within \(2^{i-1}\) of \(L'/p_i\), hence at most \(L'/p_i+2^{i-1}\). The M-number condition \(a_i<p_i-1\) and the hypothesis \(\tau(n')\ge4^j\) give \[\frac{L'}{a_i+1}-\frac{L'}{p_i} \ge \frac{L'}{p_i(a_i+1)} \ge \frac{\tau(n')}{p_i} \ge \frac{4^j}{p_j} > 2^{j-1} \ge 2^{i-1},\] using that \(p_i-a_i-1\ge1\), \(L'/(a_i+1)=\tau(m_j)\tau(n')/\tau(m_i)\ge\tau(n')\), and \(p_i\le p_j\). Thus \(L'/p_i+2^{i-1}<L'/(a_i+1)\), so there are more than \(a_i L'/(a_i+1)\) non-multiples of \(p_i\) in \(S\) and the cutpoint \(z\) is well-defined. The non-multiples before \(z\) and the complementary set (multiples before \(z\) together with everything after \(z\)) are each \(2^i\)-AP combinations by the same set-difference and union arguments as in Lemma 3. The non-multiples before \(z\) are then divided into \(a_i\) equal contiguous parts by \(a_i-1\) further interval cuts; restricting a \(2^i\)-AP combination to \(\{a\le z'\}\) or \(\{a>z'\}\) preserves the AP-combination number (as in Lemma 3), so each part remains a \(2^i\)-AP combination. After all \(j\) steps the sets are \(2^j\)-AP combinations of size \(\tau(n')\), giving \(K=2^j\). ◻

Proof. The proof follows closely that of Theorem 1, using Lemma 5 in place of Lemma 3. Lemma 5 partitions \([1,\tau(n)]\) into sets \(A_d\), one for each \(d\mid n_Tm_j\), each of size \(\tau(n')\) and forming a \(K\)-AP combination with common differences dividing \(rm_j\). (The hypothesis \(\tau(n')\ge4^j\) holds because \(\tau(n')=2^{\ell-j}\ge2^{2j}=4^j\), since \(\ell-j\ge2j\) once \(\ell \geq 9\).)

The hypothesis that \(n\) is not divisible by the square of any non-tight prime \(q>p_j\) ensures that \(n'\) is squarefree. For each \(d\mid n_Tm_j\) we apply Hall’s theorem to match \(D(n')\) to \(A_d\). Setting \(\tilde{\ell}=\ell+1\) and \(\tilde{\jmath}=j+1\) gives \(K=2^{\tilde{\jmath}-1}\) and \(\omega(n')=\tilde{\ell}-\tilde{\jmath}\), so the Hall’s theorem arguments of Theorem 1 apply verbatim with \((\tilde{\ell},\tilde{\jmath})\) in place of \((\ell,j)\), covering all \(\ell\ge44\). (The shift \(\tilde{\ell}=\ell+1\) reflects that the prime \(2\), here a tight prime contributing to \(n_T\), plays the same structural role as \(p_1=2\) in Theorem 1. In both cases it contributes to neither \(K\) nor to \(f\), and the bound \(f(n')\le\sum_{i=\tilde{\jmath}+1}^{\tilde{\ell}}1/P_i<0.93\) matches that theorem’s bound precisely.)

Once we have obtained the matchings \(\phi_d\colon D(n')\to A_d\), we can construct the coprime matching of \(D(n)\) to \([1,\tau(n)]\) via \(\psi(d\cdot e)=\phi_d(e)\), as in Theorem 1. ◻

Proof. We prove the contrapositive. Suppose \(n\) is not an M-number, and so \(p^p{\,|\,}n\) for some prime \(p\). Then at least \(p/(p+1)\) of the members of \(D(n)\) are divisible by \(p\). Let \(I\) be a coprime arithmetic progression of length \(\tau(n)\). Each shift \(I+m\) is again a coprime arithmetic progression of length \(\tau(n)\). On average as \(m\) varies, exactly \((p-1)/p\) of the integers in the set are coprime to \(p\), so there is at least one such \(m\) where \(I+m\) has less than \(p/(p+1)\) of its members coprime to \(p\). We cannot coprimely match \(D(n)\) with \(I+m\), so \(n\) is not strongly matchable. ◻

Proof. We have \(\tau(p^{p-1}n)=p\tau(n)\). Let \(I\) be a coprime arithmetic progression of length \(p\tau(n)\), say \(I=\{i_1,i_2,\dots,i_{p\tau(n)}\}\). For \(j=1,2,\dots,p\), let \(I_j\) be the subsequence \((i_{j+kp})_k\) of length \(\tau(n)\). At most one of these subsequences has its terms all divisible by \(p\), and the other subsequences are all coprime to \(p\). If there is some \(j\) where all the terms of \(I_{j}\) are divisible by \(p\), denote this \(j\) by \(j_0\), otherwise let \(j_0=1\). There are coprime matchings \(\psi_j\) from \(D(n)\) to \(I_j\) for each \(j\). We construct a coprime matching from \(D(p^{p-1}n)\) to \(I\) as follows. For \(D(n)\), we already have \(\psi_{j_0}\). For \(p^kD(n)\), \(1\le k\le p-1\), \(k\ne j_0\), we map it to one of the subsequences \(I_j\) not used via \(\psi_j\); that is, we map \(p^kd\in p^kD(n)\) to \(\psi_j(d)\). The union of these maps gives a coprime matching from \(D(p^{p-1}n)\) to \(I\), completing the proof. ◻

Proof. We first note that if \(n\) is strongly matchable and \(p\) is a prime with \(p{\,\nmid\,}n\) and \(p>2\tau(n)\), then \(pn\) is also strongly matchable. Indeed, take an arbitrary coprime arithmetic progression \(I\) of \(\tau(pn)=2\tau(n)\) integers. There are coprime matchings of \(D(n)\) to both the first half of \(I\) and the second half of \(I\), say \(\psi_1,\psi_2\). Not both of these halves contain a multiple of \(p\), so map \(pD(n)\) to a half not containing a multiple of \(p\) via \(p\psi_i\), and use the unadorned injection for the other half.

Let \(S_j\) be the set of odd squarefree numbers \(s\) with \(\omega(s)=j\) and each prime factor of \(s\) is \(< 2^{j}\), and let \(S\) be the union of the sets \(S_j\). Suppose that \(n>1\) is an odd squarefree number not divisible by any member of \(S\). Then \[n=q_1q_2\dots q_k,\quad 3\le q_1<q_2<\dots <q_k,\quad each q_j prime, \quadeach q_j\ge2^{j}.\] Indeed, if not and \(q_j< 2^{j}\) for some \(j\), then \(q_1q_2\dots q_j\in S_j\), contradicting our assumption that \(n\) is not divisible by any member of \(S\).

We claim that any odd squarefree \(n\) not divisible by any element of \(S\) is strongly matchable. First, \(n=1\) is strongly matchable, and any odd prime \(q\) is strongly matchable by the argument above, since \(q>2\tau(1)\). Now suppose that \(n_j:=q_1q_2\cdots q_j\) is strongly matchable. Since \(\tau(n_j)=2^j\) and \(q_{j+1}>2^{j+1}\), it follows by the argument above that \(n_jq_{j+1}\) is strongly matchable. Induction completes the argument that \(n\) is strongly matchable.

It remains to show that such numbers \(n\) comprise a set of positive lower density. The reciprocal sum of the primes \(q\le 2^{j}\) is \(\log j+O(1)\), and in fact from [9] and a calculation, this sum is \(<\log j\) when \(j\ge4\). Since \(\sum_{p\le 7}1/p > 1.17619\), it follows that \[\sum_{s\in S'_j}\frac{1}{s}\le\frac{(\log j-1.17619)^j}{j!},\quad j\ge4,\] where \(S'_j\) is the set of \(s\in S_j\) with all prime factors \(>8\). Let \(T\) denote the set of squarefree numbers \(n\) with all prime factors \(>8\). Then \(T\) has an asymptotic density equal to \[\frac{6}{\pi^2}\prod_{p\le7}\left(1-\frac{1}{p}\right)\left(1-\frac{1}{p^2}\right)^{-1}=0.221640\dots\,.\] If \(s\in S\) divides some \(n\in T\), then each prime factor of \(s\) is \(>8\), so for some \(j\ge4\), we have \(s\in S_j\), and so \(s\in S_j'\). The upper asymptotic density of the set of multiples of the elements in \(\cup_{j\ge4}S'_j\) is at most \[\sum_{j\ge4}\frac{(\log j-1.17619)^j}{j!}<0.000331239.\] Let \(T'\) denote the subset of \(T\) consisting of numbers not divisible by any member of \(S\), so that every member of \(T'\) is strongly matchable. The lower asymptotic density of \(T'\) is greater than \(0.2213\). We can boost this using Proposition 5. For each \(n\in T'\) and each \(p\in\{2,3,5,7\}\), we have \(p\nmid n\) (since all prime factors of \(n\) exceed \(8\)), so Proposition 5 shows that \(p^{p-1}n\) is also strongly matchable. Taking potential prime factors of this form into account improves the lower bound for the lower density of the set of strongly matchable numbers to at least \[0.2213\cdot\left(1+\frac{1}{2}\right)\left(1+\frac{1}{9}\right)\left(1+\frac{1}{5^4}\right)\left(1+\frac{1}{7^6}\right) >0.3694>\frac{4}{11}.\] ◻