6
$\begingroup$

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$.

enter image description here

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$.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Emil Jeřábek Sep 29 '16 at 17:20
2
$\begingroup$

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)
$\endgroup$
2
$\begingroup$

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$


About rank 6

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$.


Note that these series generalizes as follows :
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.