JustPostChinaTST wrote: For a non-empty finite set $A$ of positive integers, let $\text{lcm}(A)$ denote the least common multiple of elements in $A$, and let $d(A)$ denote the number of prime factors of $\text{lcm}(A)$ (counting multiplicity). Given a finite set $S$ of positive integers, and $f_S(x)=\sum_{\emptyset \neq A \subset S} \frac{(-1)^{|A|} x^{d(A)}}{\text{lcm}(A)}$. Prove that, if $0 \le x \le 2, then -1 \le f_S(x) \le 0$. FTFY

So for instance $A=\{3,4\}$, then $d(A) = 2 $ ?

$lcm(A)=12,$ so $d(A)=3$ because $12=2^2\cdot 3$. The prime factors are counted with multiplicity.

Ok so we are going to prove the this more general result : Let $a_i(j)\in (0,1)$ for $i=1,2,...,k$ , $ j=1,2,...,n$ then : $$\sum_{I\subseteq [1,2,...,n]} (-1)^{|I|}\min_{j\in I}(a_1(j))\cdot ...\cdot \min_{j\in I}(a_k(j)) \in (0,1)$$. From this we set $a_i(j)=(\frac{x}{p_i})^{t_i(j)}$ to solve the problem ($p_1^{t_1(j)}\cdot ...\cdot p_k^{t_k(j)}$ are the elemets of $A$). Proof: Rearrange for every $i$, $a_i(1),...,a_i(n)$ to $b_i(1)\ge b_i(2)\ge ...\ge b_i(n)\ge b_i(n+1)=0$ such that $b_i(s_i(j))=a_i(j)$ and $s_i$ is a rearrangement of $1,2,...,n$ For $p=1,2,...,n$ define the following mappings $f_p:[1,2,...,n]^k\to \{0,1\}$ where . $f_p=1$ on $[s_1(p),...,n]\times ...\times [s_k(p),...,n]$ and $0$ everywhere else. The following sum evaluates to our LHS. $$\sum_{(i_1,...,i_k)\in [1,...,n]^k}(1-f_1)\cdot ...\cdot (1-f_n)(b_1(i_1)-b_1(i_1+1))...(b_k(i_k)-b_k(i_k+1))$$The mappings are evaluated at each point $(i_1,...,i_k)$ . This clearly is positive and is less than $1$ cause $(1-f_1)...(1-f_n)\le 1$ and $\sum_{(i_1,...,i_k)\in [1,...,n]^k}(b_1(i_1)-b_1(i_1+1))...(b_k(i_k)-b_k(i_k+1))=b_1(1)b_2(1)...b_k(1)\le 1$ Indeed every term in the expansion of $(1-f_1)...(1-f_n)$ : $(-1)^{|I|}\prod_{j\in I}f_j$ is the mapping $(-1)^{|I|} f_I$ where $f_I=1$ on $[\max_{j\in I}s_1(j),...,n]\times ...\times [\max_{j\in I}s_k(j),...,n]$ and evaluate $$\sum_{(i_1,...,i_k)\in [1,...,n]^k}f_I\cdot (b_1(i_1)-b_1(i_1+1))...(b_k(i_k)-b_k(i_k+1))=b_1(\max_{j\in I}s_1(j))...b_k(\max_{j\in I}s_k(j))=\min_{j\in I}(a_1(j))\cdot ...\cdot \min_{j\in I}(a_k(j))$$

Define $\omega(n) = d(\{n\})$. For each prime power $p^k$, independently toss a coin $C(p^k)$ with probability $x/p$ of being heads, and define $C(n)$ to be heads if $C(p^k)$ is heads for all $p^k\mid n$. The probability of $C(n)$ being heads is thus $x^{\omega(n)} / n$. Now define $$f(x) = \mathbb E\left[ \prod_{a\in S} (1 - \mathbb I[C(a)\text{ is heads}] ) \right]$$ (Note that $\mathbb I [\text{random clause}]$ is a random variable which is 1 if the clause is true and 0 otherwise.) Clearly $C(a)$ is heads for all $a\in A\subseteq S$ iff $C(\operatorname{lcm} A)$ is heads. It is clear that $0\le f(x) \le 1$ when $0\le x \le 2$ (because this holds before taking expectation). However, by linearity of expectation: \begin{align*} f(x) &= 1 + \sum_{\varnothing \neq A \subseteq S} (-1)^{|A|} \mathbb P[C(\operatorname{lcm} A)\text{ is heads}]\\ &= 1+ \sum_{\varnothing \neq A \subseteq S} \frac{(-1)^{|A|}x^{d(A)}}{\operatorname{lcm} A} \end{align*}so the conclusion follows.

Is this how I did this in mock two years ago? Smoothing, inductive approach. Let $p_1, \cdots, p_m$ be the prime factors dividing $lcm(S)$ and $t_j=\frac{x}{p_j}$. Note $t_j\in [0,1]$. Let $g_j(A)=\nu_{p_j}(lcm(A))$ and let $f(S)$ stand for $f_S(x)$. Note $\frac{x^{\Omega(lcm(A))}}{lcm(A)}= \prod\limits_{p_j} \frac{x^{\nu_{p_j}(lcm(A))}}{p_j^{\nu_{p_j}(lcm(A))}} = \prod_{p_j} \left( \frac{x}{p_j} \right)^{\nu_{p_j}(lcm(A))} = \prod_{j=1}^m t_j^{g_j(A)}$ The sum we are dealing with is simply $$\sum_{A \subseteq S} (-1)^{|A|} \prod\limits_{j=1}^m t_j^{g_j(A)}$$ We proceed by strong induction on $|S|+\sum_{j\in S} j$ with base case being $|S|=1$ and clear. Inductive step: we first show $f(S)\le 0$ let $M$ be the set of elements in $S$ not divisible by $p_m$. If $M$ is nonempty, we multiply all elements of $M$ by $p_m$ which changes the sum by incrementing all $g_m(A)$ by 1 if they are originally nonzero (for form a new set S'). This only affects $A\subseteq M$. The change in sum is $\sum_{A\subseteq M, A\ne \emptyset} (-1)^{|A|} (t_m-1) \prod\limits_{j=1}^{m-1} t_j^{g_j(A)}= (t_m-1)(\sum_{A\subseteq M, A\ne \emptyset} (-1)^{|A|}\prod\limits_{j=1}^{m-1} t_j^{g_j(A)})$ which is the product of two nonpositive terms by IH, so $f(S')\ge f(S)$. Now we can divide each element in $S'$ by $p_m$. Note for all nonempty sets, $g_j(A)$ is decremented by exactly 1. Therefore, $f(S)\le f(S') = t_m f(S'/p_m) \le 0$ It remains to show the sum is $\ge -1$. Add the emptyset into the calculation for this part and call this sum $g(S)=f(S)+1$. Now, again let $M$ be the set of elements in $S$ not divisible by $p_m$. For each $A\subseteq M$ (this time I include the emptyset) we add 1 to $g_j(A)$, which is originally 0. By induction, the difference in sum is $(t_m-1) \sum_{A\subseteq M} (-1)^{|A|} \prod\limits_{j=1}^{m-1} t_j^{g_j(A)}$ (A is not necessarily nonempty) which is nonpositive because $t_m-1\le 0$ and the other sum is $\ge 0$ by our inductive hypothesis. Therefore, $g(S)\ge \sum_{A\subseteq S} (-1)^{|A|} \prod\limits_{j=1}^{m-1} t_j^{g_j(A)} \cdot t_m^{\max(g_m(A),1)}=t_m \sum_{A\subseteq S} (-1)^{|A|} \prod\limits_{j=1}^{m-1} t_j^{g_j(A)} \cdot t_m^{\max(g_m(A)-1,0)}=t_m f(M \cup (S\backslash M)/p_m) \ge 0$