4
$\begingroup$

Question: Is there a solution for the following system?
(if so I'm interested in an explicit solution)

$x_1>x_2, \ \ x_1>x_3, \ \ x_1>x_4,$
$ x_2>x_5, \ \ x_2>x_6, \ \ x_3>x_5, \ \ x_3>x_7, \ \ x_4>x_6, \ \ x_4>x_7,$
$x_5>1, \ \ x_6>1, \ \ x_7>1,$
$x_2 x_3 \le x_1 x_5, \ \ x_2 x_4 \le x_1 x_6, \ \ x_3 x_4 \le x_1 x_7$
$x_5 x_6 \le x_2, \ \ x_5 x_7 \le x_3, \ \ x_6 x_7 \le x_4$
$x_1-x_2-x_3-x_4+x_5+x_6+x_7-1 \le 0$

Motivation: Let $B_n$ be the rank $n$ boolean lattice (i.e. the subset lattice of $\{1,2, \cdots , n\}$).
A labeling $f: B_n \to \mathbb{R}_+$ is called allowed if it satisfies:

  • $f(\emptyset) = 1$
  • $a \subset b \Rightarrow f(a) < f(b)$
  • $ f(a)f(b) \le f(a \cup b)f(a \cap b)$, $\forall a,b \in B_n$

Let $\varphi(f) := (-1)^n\sum_{a \in B_n} (-1)^{|a|} f(a)$ be the Euler totient of the labeling $f$.

Remark: For $n=1$, we see directly that $\varphi(f)>0$, and for $n=2$ it is proved in this answer.

Our system admits a solution iff there is an allowed labeling of $B_3$ with a negative Euler totient.
To understand that take $f(\{1,2,3\})=x_1$, $ f(\{1,2\})=x_2 $, $f(\{1,3\})=x_3$, $f(\{2,3\})=x_4$, $f(\{1\})=x_5$, $f(\{2\})=x_6$, $f(\{3\})=x_7$ and $f(\emptyset)=1=x_8$.

enter image description here $ \ \ \ \ \ \ \ \ \ \ \ \ $ enter image description here

Remark: If $f$ maps to $\mathbb{N}$ and $x_1 < 100$ then $\varphi(f) > 0$ (checked by SAGE).
If moreover $a \subset b \Rightarrow f(a) \mid f(b)$, then we get the same for $x_1 < 10^5$.
If $ f(a)f(b) = f(a \cup b)f(a \cap b)$ then $\varphi(f) = (x_5-1)(x_6-1)(x_7-1)>0$.


Bonus question: What's the lowest $\varphi(f)$ for $f$ an allowed labeling of $B_3$?

Lemma: $\varphi(f)>-1$.
Proof: First $(x_1-x_2)(x_1-x_3)(x_1-x_4)>0$,
so $x_1^3 + x_1(x_2x_3+x_2x_4+x_3x_4) > x_1^2(x_2+x_3+x_4)+x_2x_3x_4$,
then $x_1 + \frac{x_2x_3}{x_1}+\frac{x_2x_4}{x_1}+\frac{x_3x_4}{x_1} > x_2+x_3+x_4+\frac{x_2x_3x_4}{x_1^2}$,
but $x_5 \ge \frac{x_2x_3}{x_1}, x_6 \ge \frac{x_2x_4}{x_1}, x_7 \ge \frac{x_3x_4}{x_1}$.
It follows that $\varphi(f) > \frac{x_2x_3x_4}{x_1^2}-1>-1$. $\square$

The following shows that $\frac{x_2x_3x_4}{x_1^2} \le 1$, so that we can't get a better lower bound for $\varphi(f)$ by this method.

Lemma: $x_2x_3x_4 \le x_1^2$.
Proof: First $(x_2x_3)(x_2x_4)(x_3x_4) \le (x_1x_5)(x_1x_6)(x_1x_7)$,
so $(x_2x_3x_4)^2 \le x_1^3x_5x_6x_7$,
Then, $(x_2x_3x_4)^4 \le x_1^6(x_5x_6)(x_5x_7)(x_6x_7) \le x_1^6(x_2x_3x_4)$.
It follows that $(x_2x_3x_4)^3 \le x_1^6$, so $x_2x_3x_4 \le x_1^2$. $\square$

$\endgroup$
1
$\begingroup$

Yes, take $0< \epsilon \le 1/100$ and $2 \le x \le 3$, then the following labeling is a solution:

enter image description here

by assumption on $\epsilon$ and $x$ we can check that:

  • $1< 1+\epsilon < \sqrt{x} < x$,
  • $x(1+\epsilon) \ge (\sqrt{x})^2$ and $\sqrt{x} > (1+ \epsilon)^2$,
  • $\varphi(f) = x-3\sqrt{x} + 3(1+ \epsilon)-1 = x+2-3\sqrt{x}+3\epsilon < 0 $.

Moreover $x+2-3\sqrt{x}$ has a minimum for $x=9/4$ where $\varphi(f) = -1/4+3 \epsilon$.

About the bonus question: Is it true that $\varphi(f) > -1/4$, for any allowed labeling $f$ of $B_3$?

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