Given a positive integer $n$, let $D$ be the set of all positive divisors of $n$. The subsets $A,B$ of $D$ satisfies that for any $a \in A$ and $b \in B$, it holds that $a \nmid b$ and $b \nmid a$. Show that \[ \sqrt{|A|}+\sqrt{|B|} \le \sqrt{|D|}. \]
Problem
Source: 2022 China TST, Test 4 P6
Tags: number theory, Divisibility, Divisors
20.05.2022 10:36
Solved with Luke Robitaille, Justin Lee, and Espen Slettnes. Let \[V=\bigcup_{a\in A}\{\text{divisors of }a\} \quad\text{and}\quad W=\bigcup_{a\in A}\{\text{multiples of }a\}\cap D\] Claim: \(|V|\cdot|W|\ge|A|\cdot|D|\). Proof. We induct on the number of prime divisors of \(n\), with base case \(n=1\) trivial. For the inductive step, take a prime \(p\mid n\). For any set \(S\), let \(S_i=\{s\in S\mid \nu_p(s)=i\}\). Then \(|V_0|\ge|V_1|\ge\cdots\ge|V_n|\) and \(|W_0|\le|W_1|\le\cdots\le|W_n|\). By Chebyshev's inequality, \begin{align*} |V|\cdot|W|=\left(\sum_{i=0}^n|V_i|\right)\left(\sum_{i=0}^n|W_i|\right) &\ge(n+1)\sum_{i=0}^n|V_i|\cdot|W_i|\\ &\ge(n+1)\sum_{i=0}^n|A_i|\cdot|D_i| =|D|\sum_{i=0}^n|A_i|=|A|\cdot|D|. \end{align*}\(\blacksquare\) We may assume that for any \(d\in D\), if \(d\) has a divisor and a multiple in \(A\), then \(d\in A\). Then \(V\cap W=A\) and \(|V\cup W|=|D|-|B|\), so \[|D|-|B|+|A|=|V|+|W|\ge2\sqrt{V|\cdot|W|}\ge2\sqrt{|A|\cdot|D|},\]which rearranges to the desired.
24.05.2022 06:35
Oops this is pretty much the same as above Let $A_{down} = \{ x \text{ st } x|a \text{ for some } a\in A\}$ and $A_{up} = \{ \text{ st } a|x|n \text{ for some } a\in A\}$. Define $B_{up}, B_{down}$ similarly. Main Claim: $|A| |D| \le |A_{up}||A_{down}|$ Proof: We induct on $\omega(n)$. Let $t=\nu_p(n)$ and for a set $S$, let $S_j=\{x \text{ st } \nu_p(x)=j \text{ and } x\in S\}$ Observe $A_{up,0} \subseteq A_{up,1} \subseteq \cdots \subseteq A_{up,t}$ and $A_{down,t} \subseteq A_{down,t-1} \subseteq \cdots \subseteq A_{down,0}$ Thus, by rearrangement inequality, $|A_{up}| |A_{down}| = \sum\limits_{0\le x,y\le t} |A_{up,x}| |A_{down,y}| \le (t+1) \sum\limits_{0\le x\le t} |A_{up,x}| |A_{down,x}|$ By inductive hypothesis on $\frac{n}{p^t}$, $|A_{up,x}| |A_{down,x}| \ge |A_x| |D_x|$ Therefore, $(t+1) \sum\limits_{0\le x\le t} |A_{up,x}| |A_{down,x}| \ge (t+1) \sum\limits_{0\le x\le t} |A_x| |D_x| = |D| \sum\limits_{0\le x\le t} |A_x| = |D||A|$ Now, notice $A_{up} \cap B_{down} = \emptyset$ because if $t\in A_{up} \cap B_{down}$, there exists $a,b$ st $a\mid t\mid b$, absurd. Similarly, $A_{down}\cap B_{up}=\emptyset$. Thus, $$\sqrt{|A|}+\sqrt{|B|} \le \frac{1}{\sqrt{|D|}} (\sqrt{|A_{up}||A_{down}|} + \sqrt{|B_{up}||B_{down}|}) = \frac{1}{\sqrt{|D|}} (\sqrt{(|A_{up}|+|B_{down}|) (|A_{down}|+|B_{up}|}) = \sqrt{|D|} $$
24.05.2022 08:25
Here is another idea. WLOG, if there exists $a_1,a_2\in A$ st $a_1 | x | a_2$ then $x\in A$. Same for $B$. Let $X$ be the set of integers $x$ st there exists $a \in A, b\in B$ then $x\mid a, x\mid b$, and $Y$ be the set of integers $y$ st there exists $a\in A, b\in B$ st $b\mid y, a\mid y$. If I prove $|A| |B| \le |X| |Y|$ I am done since $(\sqrt{|A|}+\sqrt{B})^2 \le |A|+|B|+2\sqrt{|X||Y|} \le |A|+|B|+|X|+|Y|=|D|$ Wait a minute this rearranges into the main claim of the above solution oops and can be proved inductively in the exact same way.
04.07.2022 23:00
I had posted a solution that used this : (and found out later it's a well known inequality) https://en.wikipedia.org/wiki/Ahlswede%E2%80%93Daykin_inequality
28.07.2022 11:52
it's a difficult question if you don't know Kleitman Lemma during the exam
19.09.2022 12:12
Counterattacker04 wrote: it's a difficult question if you don't know Kleitman Lemma during the exam Could you please tell me what is Kleitman Lemma?
10.10.2022 14:21
\begin{align*} &(n+1)\sum_{i=0}^n|V_i|\cdot|W_i|\ge(n+1)\sum_{i=0}^n|A_i|\cdot|D_i| \end{align*}why?Is this the lemma?
01.09.2023 13:31
wx-78 wrote: Counterattacker04 wrote: it's a difficult question if you don't know Kleitman Lemma during the exam Could you please tell me what is Kleitman Lemma? If you're chinese you can read this article
21.12.2023 01:56
This is an old problem. Here is a reference: "On Intersection Theorems and a lemma of Kleitman"
28.10.2024 09:11
What we need to do is simply generalizing Kleitman Lemma from hypercube $Q_n$ to set of divisors $D_n.$ The proof is actually quite similar. The FKG inequality then says that for any monotonically increasing functions $f$ and monotonically decreasing function $g$ on $X$ the following positive correlation inequality holds: $${\displaystyle \left(\sum _{x\in X}f(x)g(x)\mu (x)\right)\left(\sum _{x\in X}\mu (x)\right)\leq \left(\sum _{x\in X}f(x)\mu (x)\right)\left(\sum _{x\in X}g(x)\mu (x)\right).}$$Here $\mu$ is a log supermodular function. A nice understanding is defining the expectation $$\langle f\rangle:=\frac{\sum _{x\in X}f(x)\mu (x)}{\sum _{x\in X}\mu (x)}$$So FKG inequality shows $\langle fg\rangle\le\langle f\rangle\cdot\langle g\rangle.$ To prove Kleitman Lemma: Quote: $\mathcal A,\mathcal B$ are upset, downset on $D_n$ respectively. Then $$\Pr[\mathcal A]\Pr[\mathcal B]\ge \Pr[\mathcal A\cap\mathcal B]$$ Proof. Let $f: D_n \rightarrow \mathbb{R}^{+}$ be the characteristic function of $\mathcal A$; that is, $f(A) = 0$ if $A \notin \mathcal A$ and $f(A) = 1$ if $A \in \mathcal A$. Similarly, let $g$ be the characteristic function of $\mathcal B$. By the assumptions, $f$ is increasing and $g$ is decreasing. Applying the FKG Inequality with the trivial measure $\mu = 1$ we get $$\Pr[A \cap B] = \langle fg\rangle\le\langle f\rangle\cdot\langle g\rangle = \Pr[A] \Pr[B].\Box$$Back to original problem, Let $A_{-} = \{ x \text{ st } x|a \text{ for some } a\in A\}$ and $A_{+} = \{ \text{ st } a|x|n \text{ for some } a\in A\}$. Define $B_{-}, B_{+}$ similarly. Since $A\subseteq A_-\cap A_+,B\subseteq B_-\cap B_+,$ by the theorem above and Cauchy Schwarz Inequality $$\sqrt{\frac{|A|}{|D|}}+\sqrt{\frac{|B|}{|D|}}\le\sqrt{\Pr[A_-]\Pr[A_+]}+\sqrt{\Pr[B_-]\Pr[B_+]}\le\sqrt{(\Pr[A_-]+\Pr[B_+])(\Pr[A_+]+\Pr[B_-])}\le 1.\Box$$