Problem A. 838. (November 2022)
A. 838. Sets \(\displaystyle X\subset \mathbb{Z}^{+}\) and \(\displaystyle Y\subset \mathbb{Z}^{+}\) are called comradely, if every positive integer \(\displaystyle n\) can be written as \(\displaystyle n=xy\) for some \(\displaystyle x\in X\) and \(\displaystyle y\in Y\). Let \(\displaystyle X(n)\) and \(\displaystyle Y(n)\) denote the number of elements of \(\displaystyle X\) and \(\displaystyle Y\), respectively, among the first \(\displaystyle n\) positive integers.
Let \(\displaystyle f\colon \mathbb{Z}^{+}\to \mathbb{R}^{+}\) be an arbitrary function that goes to infinity. Prove that one can find comradely sets \(\displaystyle X\) and \(\displaystyle Y\) such that \(\displaystyle \frac{X(n)}{n}\) and \(\displaystyle \frac{Y(n)}{n}\) goes to \(\displaystyle 0\), and for all \(\displaystyle \varepsilon>0\) exists \(\displaystyle n \in \mathbb{Z}^+\) such that
\(\displaystyle \frac{\min\big\{X(n), Y(n)\big\}}{f(n)}<\varepsilon. \)
(7 pont)
Deadline expired on December 12, 2022.
Lemma 1
\(\displaystyle \prod_{p} \frac{p-1}{p}=0\)
if the product runs through all prime numbers.
proof:
Let \(\displaystyle p_1, p_2, \ldots p_n\) be the first \(\displaystyle n\) prime numbers.
\(\displaystyle \prod_{i=1}^{n} \frac{p_i-1}{p}=\frac{1}{\prod_{i=1}^{n} \frac{p}{p-1}}=\frac{1}{\prod_{i=1}^{n} (1+\frac{1}{p}+\frac{1}{p^2}+\ldots)}\)
\(\displaystyle \prod_{i=1}^{n} (1+\frac{1}{p}+\frac{1}{p^2}+\ldots)\) is the sum of reciprocal of the numbers that are the product of the powers \(\displaystyle p_i\), where the prime factors \(\displaystyle p_i\) are the first \(\displaystyle n\) primes. Since every number less than \(\displaystyle p_n\) is the product of the powers of \(\displaystyle p_i\), therefore
\(\displaystyle \prod_{i=1}^{n}(1+\frac{1}{p}+\frac{1}{p^2}+\ldots)\)
The sum of reciprocals of all positive integers is known to be infinite, so \(\displaystyle \prod_{i=1}^{n}(1+\frac{1}{p}+\frac{1}{p^2}+\ldots)\) goes to infinity, so the reciprocal, \(\displaystyle \prod_{i=1}^{n} \frac{p_i-1}{p}\) goes to \(\displaystyle 0\), so by definition
\(\displaystyle \prod_{p} \frac{p-1}{p}=0.\)
Lemma 2
Let \(\displaystyle P\) be an infinite set of primes such that \(\displaystyle \prod_{p\in P} \frac{p-1}{p}=0\). Let \(\displaystyle S\) be the set of numbers which are not divisible by any prime of \(\displaystyle P\). Then \(\displaystyle \frac{S(n)}{n}\) goes to \(\displaystyle 0\).
proof:
Let \(\displaystyle \varepsilon>0\) be fixed. Let \(\displaystyle p_1, p_2,\ldots p_N\) be the smallest primes in \(\displaystyle P\). Since \(\displaystyle \prod_{p\in P} \frac{p-1}{p}=0\), we can choose \(\displaystyle N\) sufficiently large such that \(\displaystyle \prod_{i=1}^N \frac{p_i-1}{p_i}< \frac{\varepsilon}{2}\).
By the Chinese remainder theorem, from \(\displaystyle 1\) to \(\displaystyle Kp_1p_2\ldots p_N\), there are \(\displaystyle K(p_1-1)(p_2-1)\ldots (p_N-1)<\frac{\varepsilon}{2} Kp_1p_2...p_n\) numbers that are not divisible by any of the primes \(\displaystyle p_1, p_2,\ldots p_n\), so it has a chance of being in \(\displaystyle S\).
Let \(\displaystyle n>\frac{2}{\varepsilon}p_1p_2\ldots p_N\). Let \(\displaystyle K\) be the integer part of \(\displaystyle \frac{n}{p_1p_2\ldots p_N}\).
Then
\(\displaystyle S(n)\le K(p_1-1)(p_2-1)\ldots (p_N-1)+n-Kp_1p_2\ldots p_N<\frac{\varepsilon}{2} Kp_1p_2\ldots p_n+p_1p_2\ldots p_n<\varepsilon Kp_1p_2\ldots p_n\le \varepsilon n\)
Thus we see that for every \(\displaystyle \varepsilon>0\) it is true that for sufficiently large \(\displaystyle n\) that \(\displaystyle \frac{S(n)}{n}<\varepsilon\), i.e. \(\displaystyle \frac{S(n)}{n}\) goes to \(\displaystyle 0\).
Lemma 3
Let \(\displaystyle S\) be a set of positive integers such that \(\displaystyle \frac{S(n)}{n}\) goes to \(\displaystyle 0\). Let \(\displaystyle Y\) be the set of positive integers that can be written in \(\displaystyle sm^2\), where \(\displaystyle s\in S\) and \(\displaystyle m\) is an integer. Then \(\displaystyle \frac{Y(n)}{n}\) also goes to \(\displaystyle 0\).
proof:
I call \(\displaystyle Y_m\) the set of numbers \(\displaystyle y\in Y\) for which \(\displaystyle m\) is the smallest integer such that \(\displaystyle \frac{y}{m^2}\in S\). Then \(\displaystyle Y_1, Y_2,\ldots\) are disjoint sets and their union is \(\displaystyle Y\).
\(\displaystyle Y_m(n)\) is less or equal than the number of numbers \(\displaystyle y\in Y, y\le n\) for which \(\displaystyle \frac{y}{m^2}\in S\). So \(\displaystyle |Y_m(n)|\le S(\frac{n}{m^2})\).
It follows that
\(\displaystyle Y(n)\le \sum_{m=1}^{\infty} S(\frac{n}{m^2})\)
Let \(\displaystyle \varepsilon>0\) be a constant. Since \(\displaystyle \sum_{m=1}^{\infty} \frac{1}{m^2}\) is finite, there exists \(\displaystyle M\) for which \(\displaystyle \sum_{m=M}^{\infty} \frac{1}{m^2}<\frac{\varepsilon}{2}\).
Furthermore, since \(\displaystyle \frac{S(n)}{n}\) goes to \(\displaystyle 0\), it is true for sufficiently large \(\displaystyle n\) and \(\displaystyle m<M\) that
\(\displaystyle S(\frac{n}{m^2})<\frac{\varepsilon}{8}\frac{n}{m^2}.\)
So for sufficiently large \(\displaystyle n\)
\(\displaystyle Y(n)\le \sum_{m=1}^{M-1} S\left(\frac{n}{m^2}\right)+\sum_{m=M}^{\infty} S\left(\frac{n}{m^2}\right)< \frac{\varepsilon}{8} \sum_{m=1}^{M- 1} \frac{n}{m^2}+n\left(\sum_{m=M}^{\infty} \frac{1}{m^2}\right)<n\left(\frac{\varepsilon}{8}\sum_{m=1}^{M-1} \frac{1}{m^2}+\frac{\varepsilon}{2}\right). \)
Since
\(\displaystyle \sum_{m=1}^{M-1} \frac{1}{m^2}<\sum_{m=1}^{M-1} \frac{1}{m^2}<4,\)
therefore \(\displaystyle Y(n)<\varepsilon n\) for sufficiently large \(\displaystyle n\). This is true for all \(\displaystyle \varepsilon>0\), so \(\displaystyle \frac{Y(n)}{n}\) goes to \(\displaystyle 0\).
Using these lemmas, we now create good comradely sets \(\displaystyle X\) and \(\displaystyle Y\).
We create an infinite set \(\displaystyle P\) of primes in an iterative way. Let \(\displaystyle P_1=\{2\}\). Then \(\displaystyle P_{k+1}\) is always an expansion of \(\displaystyle P_k\) in the following way:
Let \(\displaystyle |P_k|=t_k\). Since \(\displaystyle f\) goes to infinity, there exists a value \(\displaystyle r\) such that \(\displaystyle f(r)> 2^{2t_k}\). We choose such an \(\displaystyle r\) for which \(\displaystyle r>\prod_{p\in P_k} p\). We call this \(\displaystyle r_k\).
We form \(\displaystyle P_{k+1}\) by adding to \(\displaystyle P_k\) the first \(\displaystyle h\) prime numbers greater than \(\displaystyle r_k\). Let us call them \(\displaystyle q_1, q_2,\ldots , q_h\). We choose \(\displaystyle h\) such that
\(\displaystyle \prod_{i=1}^h \frac{q_i-1}{q_1}<\frac{1}{2}.\)
Since, by Lemma 1, for all primes, the product \(\displaystyle \prod \frac{p-1}{p}\) goes to \(\displaystyle 0\), it is true that for any \(\displaystyle r\), the product must also go to \(\displaystyle 0\) for primes larger than \(\displaystyle r\), so there exists a sufficiently large \(\displaystyle h\) for which the condition is satisfied.
Having generated the prime set \(\displaystyle P\) by iterative expansions, let \(\displaystyle X\) be the set of square-free numbers that have prime divisors only in \(\displaystyle P\).
Then, for any \(\displaystyle k\), it is satisfied that \(\displaystyle X(r_k)\) contains exactly the square-free products of the primes in \(\displaystyle P_k\), since \(\displaystyle r_k>\prod_{p\in P_k} p\). Since \(\displaystyle |P_k|=t_k\), the number of such square-free products is \(\displaystyle 2^{t_k}\).
On the other hand, \(\displaystyle f(r_k)>2^{2t_k}\), so
\(\displaystyle \frac{X(r_k)}{f(r_k)}<\frac{1}{2^{t_k}}.\)
\(\displaystyle t_k\) goes to infinity, so \(\displaystyle \frac{1}{2^{t_k}}\) goes to \(\displaystyle 0\), so for any \(\displaystyle \varepsilon>0\) there exists \(\displaystyle n=r_k\), for which
\(\displaystyle \frac{\min\{X(n),Y(n)\}}{f(n)}\le \frac{X(n)}{f(n)}<\varepsilon.\)
The set \(\displaystyle P\) is constructed such that \(\displaystyle \prod_{p\in P} \frac{p-1}{p}=0\).
Let \(\displaystyle S\) be the set of numbers which are not divisible by any prime in \(\displaystyle P\). Then, by Lemma 2, \(\displaystyle \frac{S(n)}{n}\) goes to \(\displaystyle 0\).
Let \(\displaystyle Y\) be the set of positive integers that can be written in the form \(\displaystyle sm^2\), where \(\displaystyle s\in S\) and \(\displaystyle m\) is an integer. By Lemma 3, \(\displaystyle \frac{Y(n)}{n}\) also goes to \(\displaystyle 0\).
Every positive integer \(\displaystyle n\) can be written in the form \(\displaystyle n=m^2sx\), where \(\displaystyle m\) is an integer and \(\displaystyle s\) and \(\displaystyle x\) are square-free numbers, where \(\displaystyle s\) has prime factors only outside \(\displaystyle P\) and \(\displaystyle x\) has prime factors only inside \(\displaystyle P\). Thus, every positive integer can be written as a product of \(\displaystyle m^2s\in Y\) and \(\displaystyle x\in X\), i.e. \(\displaystyle X\) and \(\displaystyle Y\) are comradely sets.
If, in the definition of \(\displaystyle r_k\), we also stipulate that the \(\displaystyle q\) primes between the largest element of \(\displaystyle P_k\) and \(\displaystyle r_k\) must be \(\displaystyle \prod \frac{q-1}{q}<\frac{1}{2}\), we also ensure that \(\displaystyle \frac{X(n)}{n}\) must always go to \(\displaystyle 0\), since the elements of \(\displaystyle X\) are not divisible by these \(\displaystyle q\) primes, so we can refer to Lemma 2.
Thus, the resulting \(\displaystyle X\) and \(\displaystyle Y\) are comradely sets that satisfy our conditions.
Source: This is one of the simpler theorems appearing in the soon-to-be-uploaded research paper Multiplicative Complements II by Anett Kocsis, Dávid Matolcsi, Csaba Sándor and György Tőtős.
Statistics:
5 students sent a solution. 7 points: Varga Boldizsár. 1 point: 2 students. 0 point: 2 students.
Problems in Mathematics of KöMaL, November 2022