# Divisibility labeling on a boolean lattice and positive Euler totient

Let $B_n$ be the rank $n$ boolean lattice (i.e. the subset lattice of $\{1,2, \dots , n \}$). Let $\hat{0}$ and $\hat{1}$ be the minimum and the maximum of $B_n$. Let $f: B_n \to \mathbb{N}$ be a labeling satisfying:

• $f(\hat{0}) = 1$
• $a < b \Rightarrow f(a) < f(b)$ and $f(a) \mid f(b)$
• $f(a)f(b) \le f(a \vee b)f(a \wedge b)$, $\forall a,b \in B_n$

Let $\varphi(f) := (-1)^n\sum_{a \in B_n} (-1)^{|a|}f(a)$, with $|a|$ the cardinal of $a$ as subset of $\{1,2, \dots , n \}$.

Example: For $B_3$ labeled as below we have $\varphi(f) = 30-6-10-15+2+3+5-1 = 8$.

Question: Is it true in general that $\varphi(f) > 0$ ?

Examples: the divisor lattice of a square-free integer is a labeled boolean lattice satisfying the properties above, and $\varphi(f)$ is exactly the Euler totient of this integer, so that $\varphi(f) > 0$.
If we label a boolean interval of finite groups $[H,G]$ with $f(K) = |K:H|$, the labeling satisfies the properties above using the product formula, and $\varphi(f)$ is exactly the number of cosets $Hg$ such that $\langle Hg \rangle = G$, so that $\varphi(f)>0$ by Ore's theorem.

Checking: We have checked $B_3$ by SAGE for $f(\hat{1})<10^6$.

Remark: it is immediate for $B_1$, and for $B_2$, take $x_1 = f(\{1,2\})$, $x_2 = f(\{1\})$, $x_3 = f(\{2\})$ and $x_4 = f(\emptyset)$, then $x_2 + x_3 \le \frac{x_1}{2} + \frac{x_1}{2} < x_1+x_4$.

• I don't know if the following is of any use: if we define $g(a)=\sum_{b\le a}(-1)^{|a-b|}f(b)$ so that $\varphi_f=g(1)$, we have the inverse relation $f(a)=\sum_{b\le a}g(b)$. – Emil Jeřábek Sep 29 '16 at 17:20

It's false in general, there is a counter-example of rank $6$.

Consider the labeling $f$ on a boolean lattice of rank $n$ such that for every maximal chain $$\hat{0} = a_0 < a_1< \cdots <a_n = \hat{1}$$ we have $$(f(a_0), f(a_1), \dots , f(a_n)) =(1,k,k^2, \dots, k^{n-2}, k^{n-2}x, k^{n-2}x^2)$$ with $k,x \in \mathbb{N}_{\ge 2}$ and $k \le x$. Then, all the properties are satisfied. But $$\varphi(f)= k^{n-2}x^2 - n k^{n-2}x + \sum_{r=0}^{n-2} {n \choose r} (-1)^{n-r} k^r$$ $$= k^{n-2}x^2 - n k^{n-2}x + (k-1)^n - k^n + nk^{n-1}$$ $$= (k-1)^n + k^{n-2}(x-k)(x+k-n)$$ For $x = k+1$ and $n = x+k+1$, we have $\varphi(f) = (k-1)^{2k+2} - k^{2k}<0$ for $k \le 4.$

So with $k=2$, we have a counter-example of rank $6$, whose labeling on every maximal chain is $$(1,2,4,8,16,48,144)$$ and $\varphi(f) = -15$.

Now, the natural questions are the following:

• Is $6$ the smallest rank for the existence of a labeling $f$ (as in the question) with $\varphi(f) \le 0$?
• Is $\varphi(f)$ always nonzero for such $f$? (see this post)

This answer is dedicated to prove the following theorem (complementary to the accepted answer).

Theorem 1: At rank $\le 5$, $\varphi(f)>0$.

Notation: Let $d_{i_1i_2\dots i_r}:=f(\{ i_1,i_2,\dots, i_r \})$. Let $s_i:=\frac{f(\hat{1})}{f(\{i \}^{\complement})} \in \mathbb{N}_{\ge 2}$.

Proposition 1: $\varphi(f)>0$ at rank $1$.
Proof: $\varphi(f) = d_1- 1 \ge 2-1 = 1$. $\square$

Proposition 2: $\varphi(f)>0$ at rank $2$.
Proof: $\varphi(f) = d_{12}- d_1-d_2+1 \ge d_{12}- d_{12}/2-d_{12}/2+1 = 1$. $\square$

Lemma 1: For any $i$, and for any subset $S \subset \{1,2,\dots,n\}$ with $i\not \in S$, we have:
$$\frac{f(S \cup \{i\})}{f(S)} \le s_i$$ Proof: By assumption $f(S \cup \{i\})f(\{i \}^{\complement}) \le f(\{1,2,\dots,n\}) f(S)$. $\square$

Corollary 1: $f(\hat{1}) \le \prod_i s_i$.
Proof: $f(\hat{1}) = \prod_i \frac{f(\{1,2,\dots,i\})}{f(\{1,2,\dots,i-1\})}$. The result follows by Lemma 1. $\square$

Lemma 2: If there is $i$ such that $s_i = 2$, then $\varphi(f) = \varphi(f_{| \ [\hat{0},\{i \}^{\complement}]})$.
Proof: By Lemma 1, for any $S \not \ni i$, $\frac{f(S \cup \{i\})}{f(S)} = 2$, so $\varphi(f) = 2\varphi(f_{| \ [\hat{0},\{i \}^{\complement}]})-\varphi(f_{| \ [\hat{0},\{i \}^{\complement}]})$. $\square$

Proposition 3: $\varphi(f)>0$ at rank $3$.
Proof: If there is $i$ such that $s_i=2$, then $\varphi(f)>0$ by Lemma 2 and Proposition 2.
Else, for all $i$, $s_i \ge 3$. Then $\forall i<j$, $d_{ij}\le d_{123}/3$, so $$\varphi(f) := d_{123}-d_{12}-d_{13}-d_{23}+d_1+d_2+d_3-1 \ge$$ $$d_{123}-d_{123}/3-d_{123}/3-d_{123}/3 +d_1+d_2+d_3-1\ge 8$$ The result follows. $\square$

Proposition 4: $\varphi(f)>0$ at rank $4$.
Proof: First we can assume $s_i \ge 3$, for all $i$, by Lemma 2 and Proposition 3. Next, if $\sum_i s_i^{-1} \le 1$, then we can use the argument of the proof of Proposition 3. So we can assume that $\sum_i s_i^{-1} > 1$. We are reduced to the following cases: $(s_1,s_2,s_3,s_4) =$

• $(3,3,3,r)$, for $r \in \mathbb{N}_{\ge 3}$.
• $(3,3,4,r)$, for $r=4,5, \dots, 11$. Then $f(\hat{1}) \le 3 \cdot 3 \cdot 4 \cdot 11 = 396$, by Corollary 1.
• $(3,3,5,r)$, for $r=5,6,7$; and so $f(\hat{1}) \le 3 \cdot 3 \cdot 5 \cdot 7 = 315$.
• $(3,4,4,r)$, for $r=4,5$; and so $f(\hat{1}) \le 3 \cdot 4 \cdot 4 \cdot 5 = 240$.

We quickly check by this code that if $\forall i$, $s_i \ge 3$, $\sum_i s_i^{-1} > 1$ and $f(\hat{1}) \le 400$, then $\varphi(f) \ge 5$:

gap>  CombinatEuler4(400);
[ [ [ 1 ], [ 2, 2, 2, 2 ], [ 4, 4, 4, 4, 4, 4 ], [ 12, 12, 12, 12 ], [ 36 ] ], 5 ]


So we are reduced to the first case, for $r \ge 400/27 > 14$. Then $d_{123} = d_{1234}/r < d_{1234}/14$, but $d_{14} \ge d_{1234}/9$, so $d_{14} > d_{123}$ ; it follows easily that $\varphi(f) \ge 13$. $\square$

Remark 1: At rank $\le 8$, if $\sum_i s_i^{-1} \le 1$, then $\varphi(f)>0$, because ${n \choose 3}/{n \choose 2} \le 2$ iff $n \le 8$.

Proposition 5: $\varphi(f)>0$ at rank $5$.
Proof: We can take $s_1 \le s_2 \le \cdots \le s_5$, and by Lemma 2 and Proposition 4, we can assume that $3 \le s_1$. Moreover, by Remark 1, we can assume $\sum_{i=1}^5 s_i^{-1} > 1$. Then, we check by this code that if $f(\hat{1}) \le 10000$, we have $\varphi(f) \ge 1$:

gap>  CombinatEuler5(10000);
[ [ [ 1 ], [ 2, 2, 2, 2, 2 ], [ 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 ], [ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 ], [ 24, 24, 24, 24, 24 ], [ 72 ] ], 1 ]


If $\sum_{i=1}^4 s_i^{-1} \le 1$ then $d_{12345} \ge d_{2345} + d_{1345} + d_{1245} + d_{1235}$. If moreover $s_5 \ge s_1s_2$, then $d_{345} \ge d_{1234}$, and so $\varphi(f) > 0$; so we can assume $s_5 < s_1s_2$, but then we can check by the following code that $\prod_{i=1}^5 s_i \le 5808$, realized by $(s_1,s_2,s_3,s_4,s_5) = (3,4,4,11,11)$.

r:=5800;
for s1 in [3..4] do for s2 in [s1..6] do for s3 in [s2..9] do for s4 in [s3..s1*s2-1] do for s5 in [s4..s1*s2-1] do
if (1/s1 + 1/s2 + 1/s3 + 1/s4 <= 1) and (1/s1 + 1/s2 + 1/s3 + 1/s4 + 1/s5 > 1) then r0:=s1*s2*s3*s4*s5;
if r0>r then  r:=r0; Print([[s1,s2,s3,s4,s5],r]);
fi; fi; od; od; od; od; od;


But $f(\hat{1}) \le \prod_{i=1}^5 s_i \le 5808 < 10000$, so by the checking above, $\varphi(f) \ge 1$.
So, we can assume $\sum_{i=1}^4 s_i^{-1} > 1$. If $s_4 \ge s_1s_2$ and $s_5 \ge s_1s_3$, then $d_{245} \ge d_{1234}$ and $d_{345} \ge d_{1235}$, so that $\varphi(f) > 0$; so we can assume that $s_4 < s_1s_2$ or $s_5 < s_1s_3$. If $s_4 < s_1s_2$ and $s_5 < s_1s_3$, then we check as before that $\prod_{i=1}^5 s_i \le 4410$, realized by $(3, 3, 5, 7, 14)$. If $s_4 \ge s_1s_2$ and $s_5 < s_1s_3$, then we check as before that $\prod_{i=1}^5 s_i \le 4356$, realized by $(3, 3, 4, 11, 11)$. So we can assume $s_4 < s_1s_2$ and $s_5 \ge s_1s_3$. Now let $\varphi_1$ be $d^{-1}_5 \varphi(f_{| \ [\{5 \},\hat{1}]})$ and let $\varphi_2$ be $\varphi(f_{| \ [\hat{0},\{5 \}^{\complement}]})$. Then $\varphi(f) = d_5 \varphi_1 - \varphi_2$. But, $$s_5 d_{1234} = d_{12345} \le (\prod_{i=1}^4 s_i)d_5.$$ Now $s_i \ge 3$ and $\sum_{i=1}^4 s_i^{-1} > 1$, so by the proof of Proposition 4, we have $\varphi_1 \ge 5$, moreover we observe that $$\varphi_2 \le d_{1234} – d_{234} \le d_{1234} (1-1/s_1).$$ It follows that $$\varphi(f) = d_5 \varphi_1 - \varphi_2 \ge d_{1234}(\frac{5s_5}{\prod_{i=1}^4 s_i} - \frac{s_1-1}{s_1})$$
So, if $s_5 > (s_1-1)s_2s_3s_4/5$ then $\varphi(f) > 0$; so we can assume $s_5 \le (s_1-1)s_2s_3s_4/5.$
Now $d_{1234} \le d_1 s_2 s_3 s_4$, and if $d_1 = s_1$, then (as for the proof of Lemma 2) $$\varphi(f) = (s_1 – 1) \varphi(f_{| \ [\hat{0},\{1 \}^{\complement}]}) >0$$ by Proposition 4; so we can assume that $d_1 \le s_1-1$, so that $d_{1234} \le (s_1-1) s_2s_3s_4.$ Then, $$d_{12345}= s_5 d_{1234} \le [(s_1-1)s_2s_3s_4]^2/5,$$ but for $s_4 < s_1s_2$ and $\sum_{i=1}^4 s_i^{-1} > 1$, we check as before that $(s_1-1)s_2s_3s_4 \le 210$, realized by $(s_1,s_2,s_3,s_4) = (3,3,5,10)$, so $$f(\hat{1}) = d_{12345} \le 210^2/5 = 8820 < 10000,$$ and the result follows by the checking above. $\square$

After some investigations with this code, it seems that if $\varphi(f) \le 0$, then there is an atom $a$ such that all the maximal chains of $[\hat{0}, a^{\complement}]$ are labeled by $(1,2,4,8,16,48)$ expect $k ( = 0, 1 )$ of them with $(1,2,4,8,24,48)$, and those of $[a, \hat{1}]$ by $(2r,4r,8r,16r,48r,144r)$ with $r \ge 1$. Then, $\varphi(f)=2r +8k-17$ with $1 \le r \le 8$ for $k=0$ and $1 \le r \le 4$ for $k=1$, and $f(\hat{1})\le 1152$.
Question 1: Is it the complete classification at rank $6$ with $\varphi(f) \le 0$ ?
It is checked for $f(\hat{1})\le 500$. It would follow that, at rank $6$, $\varphi(f) \ge -15$ and $\varphi(f) \neq 0$.
There is an atom $a$ such that all the maximal chains of $[\hat{0}, a^{\complement}]$ are labeled by $$(1,m,m^2, \dots , m^{n-2},m^{n-2}x)$$ expect $k$ of them with $$(1,m,m^2, \dots , m^{n-3},m^{n-3}x, m^{n-2}x),$$ and those of $[a, \hat{1}]$ by $$(mr,m^2r, \dots , m^{n-2}r, m^{n-2}rx, m^{n-2}rx^2),$$ with $2 \le m \le x$, $k \ge 0$ and $r \ge 1$. Then $$\varphi(f) = (m-1)^{n-1}(rm-1) + m^{n-3}(x-m)(m[r(m+x+1-n)-1)]+ k).$$ Note that $\varphi(f) \equiv (-1)^n \mod m$, which proves that $\varphi(f) \neq 0$. A necessary condition for having $\varphi(f) < 0$ is $m < x$ and $n \ge m+x+1$, so the smallest possible $n$ is $6$ with $m=2$ and $x=3$ (and $k=0,1$), which is exactly the series above.