# Lattice approach

Jump to: navigation, search

This is an approach to proving (weak) FUNC in the lattice formulation by distinguishing various regimes of lattices and/or finding suitably large subsemilattices over which one has good control. Let $\mathcal{A}$ be a finite lattice with set of join-irreducibles $\mathcal{J}$ of cardinality $|\mathcal{J}|=j$, and write $n=|\mathcal{A}|$. Write $m$ for the maximum of $n - \uparrow\{J\}$ over all join-irreducibles $J$; the goal is to lower bound $m$ in terms of $n$, and FUNC claims that $m\geq n/2$.

## General observations

Lemma: If there is a constant $C\gt0$ such that (weak) FUNC holds for all lattices with $|\mathcal{J}| \leq C|\mathcal{A}|$, then it holds in general.

Proof: For given $\mathcal{A}$, consider the $k$-th cartesian powers $\mathcal{A}^k$. (Weak) FUNC holds for any one of these if and only if it holds for $\mathcal{A}$ itself. Since the number of join-irreducibles of $\mathcal{A}^k$ is $k|\mathcal{J}|$, which grows much slower than $|\mathcal{A}|^k$, the claim follows by choosing $k$ large enough. QED.

## Reduction to atomistic lattices

Lemma: (Weak) FUNC holds for all lattices if and only if it holds for all atomistic lattices.

Proof: Let $\mathcal{J}$ be the set of join-irreducibles of $\mathcal{A}$. Define $\hat{\mathcal{A}}$ as being equal to $\mathcal{A}$ together with two additional elements $A_J,A'_J$ for every $J\in\mathcal{J}$, ordered such that $0\leq A_J,A'_J\leq J$, and incomparable to all other elements. Then $\hat{\mathcal{A}}$ is again a lattice: the join of any two 'old' elements is as before; the join of $A_J$ with some $K\in\mathcal{A}$ is $J\vee K$, and similarly the join of $A_J$ with $A_K$ is $J\vee K$; and crucially, $A_J\vee A'_J = J$. So by virtue of being a finite join-semilattice, $\hat{\mathcal{A}}$ is automatically a lattice. It is atomistic by construction.

Concerning abundances, we have $|\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}|$, and assume the existence of an atom $A_J$ such that $|\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}|$. This implies $|\mathcal{A}_J| = |\hat{\mathcal{A}_{A_J}}| - 1 \lt c(|\mathcal{A}| + 2|\mathcal{J}|)$. The conclusion follows since the previous lemma allows us to assume the ratio $|\mathcal{J}|/|\mathcal{A}|$ to be arbitrarily small. QED.

Hence we assume wlog that $\mathcal{A}$ is atomistic.

## Easy lattice classes

Proposition: If atomistic $\mathcal{A}$ has a prime element, then $\mathcal{A}$ satisfies FUNC.

Proof: Let $P$ be the prime element. The claim follows if the map $\mathcal{A}\setminus\uparrow\{P\}\to \uparrow\{P\}$ given by $A\mapsto A\vee P$ is surjective. Write any given $B\in\uparrow\{P\}$ as a join of join-irreducibles. Since $P$ is prime, $P$ must be below one of these join-irreducibles; but by atomicity, such a join-irreducible must be equal to $P$. Again by atomicity, the remaining factors are not in $\uparrow\{P\}$, and hence neither is their join. This join is the desired preimage of $B$ under $A\mapsto A\vee P$. QED.

Proposition (Poonen): If every downset $\downarrow\{A\}$ is complemented, then $\mathcal{A}$ satisfies FUNC.

Proof: In this case, any join-irreducible $J$ is rare, since the map $\mathcal{A}\setminus\uparrow\{J\}\to\uparrow\{J\}$ given by $A\mapsto A\vee J$ is surjective: the complement of $J$ in $\downarrow\{B\}$ is a preimage of $B\in\uparrow\{J\}$. QED.

By a result of Björner, we can therefore also assume that $\mathcal{A}$ contains a 3-element interval.

## Knill's argument in lattice terms

The following is a lattice-theoretic formulation of a small tightening of Knill's argument.

Proposition: Let $\mathcal{J}'\subseteq\mathcal{A}$ be a set of join-irreducibles with $\bigvee \mathcal{J}' = 1$ and minimal with this property. Then some member of $\mathcal{J}'$ has abundance at most $2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}$, resulting in $m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}$.

Note that at the two extreme values $|\mathcal{J}'|=2$ or $|\mathcal{J}'|=\log_2(n)$, this establishes $m \geq n/2$. However, unless $|\mathcal{J}'|$ is very close to the maximal value $\log_2(n)$, the bound is only marginally better than Knill's original one, which is $m\geq \frac{n-1}{|\mathcal{J}'|}$.

Proof: Let $\mathcal{B}_{\mathcal{J}'}$ be the Boolean algebra of subsets of the set $\mathcal{J}'$. Consider the map $\phi:\mathcal{A}\to\mathcal{B}_{\mathcal{J}'}$ given by $\phi(A):=\{J\in \mathcal{J}'\:|\: J\leq A\}$. We claim that $\phi$ is surjective. Indeed, for every $\mathcal{I}\subseteq\mathcal{J}'$ we have $\phi\left(\bigvee \mathcal{I}\right) = \mathcal{I}$; for if $\phi\left(\bigvee \mathcal{I} \right)$ was larger, then $\mathcal{J}'$ would not be minimal with $\bigvee \mathcal{J}' = 1$.

Now consider the weight function $w:\mathcal{B}_{\mathcal{J}'}\to\mathbb{N}$ given by $w(\mathcal{I}) := |\phi^{-1}(\mathcal{I})|$. We know $w(\mathcal{I})\geq 1$ by surjectivity, and moreover $w(\mathcal{J}') = 1$ by the assumption on $\mathcal{J}'$. Since the abundance of each $J\in\mathcal{J}'$ in $\mathcal{A}$ coincides with its $w$-abundance in $\mathcal{B}_{\mathcal{J}'}$, it is enough to derive a suitable bound on the $w$-abundance.

$w\geq 1$ already fixes the distribution of a total weight of $2^{|\mathcal{J}'|}$. For the remaining weight of $n-2^{|\mathcal{J}'|}$, the worst-case scenario is that it is completely concentrated on the coatoms of $\mathcal{B}_{\mathcal{J}'}$. (And this can indeed happen.) Since every $J\in\mathcal{J}'$ is contained in all but one coatoms, the pigeonhole principle guarantees that there is $J$ whose abundance with respect to the remaining weight is at most $\frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}$. This means that its total abundance is at most $2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}$, as was to be shown. QED.

Corollary: Suppose that $\mathcal{A}$ contains a maximal chain of length $c$. Then $m \geq \frac{n-1}{c-1}$.

Proof: If the maximal chain is $0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1$, then write $A_{k+1} = A_k\lor J_k$ for join-irreducible $J_k$. Then $\bigvee_k J_k = 1$, and choose a minimal subset of the $J_k$'s with this property. QED.

## Wójcik's estimates

The following 'relative' Knill-type inequalities are abstract versions of the techniques of Wójcik.

Lemma: Let $A\leq B$ in $\mathcal{A}$. Then $m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}$.

For $A=0$ and $B=1$, this specializes to Knill's result. An alternative point of view on this estimate is that it lower bounds the size of the interval $[A,B]$.

Proof: Let $\mathcal{J}'$ be a minimal set of join-irreducibles with $A \vee \bigvee \mathcal{J}' = B$. Since all the $A\vee\bigvee \mathcal{K}$ must be distinct as $\mathcal{K}\subseteq\mathcal{J}'$ varies by the minimality of $\mathcal{J}'$, we have $|\mathcal{J}'|\leq \log_2 |[A,B]|$. On the other hand, $|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|$ by the union bound, since taking $-\vee J$ for a join-irreducible $J$ decreases the size of the upset by at most $m$. Combining these two inequalities results in the claim. QED.

Proposition: Let $[A_i,B_i]$ be a collection of disjoint intervals that cover $\mathcal{A}$. Then $\sum_i 2^{\frac{|\uparrow A_i|-|\uparrow B_i|}{m}} \leq n$.

For a single interval $[A,B]$, this specializes to the lemma; while for covering $\mathcal{A}$ by all the singleton intervals, one obtains the tight but tautological inequality $n\leq n$.

Proof: Let the $\mathcal{J}'_i$ be as in the previous proof. The arguments there show that $\sum_i 2^{\frac{|\uparrow A|-|\uparrow B|}{m}} \leq \sum_i 2^{|\mathcal{J}'_i|} \leq n$. QED.

Wójcik's actual reasoning generalizes along the following lines. Let $c(A,B)$ be the smallest cardinality of any set of join-irreducibles $\mathcal{J'}$ with $A\vee\bigvee\mathcal{J}' = B$; this is at most the size of a smallest maximal chain or the directed distance in the Hasse diagram. For $A\not\leq B$, we set $c(A,B)=\infty$. This behaves like a quasimetric on $\mathcal{A}$, in the sense that the triangle inequality holds and $c(A,B)=0$ is equivalent to $A=B$.

Lemma: For $A\lt B$, we have $m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}$.

Proof: Let $\mathcal{J}'$ be a set of join-irreducibles of cardinality $c(A,B)$ with $A \vee \bigvee \mathcal{J}' = B$. Then $|\uparrow\{A\}|\leq |\uparrow\{B\}| + m|\mathcal{J}'|$ by the union bound, since taking $-\vee J$ for a join-irreducible $J$ decreases the size of the upset by at most $m$. QED.

## Wójcik's fibre bundle decomposition

Another important ingredient of Wójcik's proof is the identification of a large subsemilattice $\mathcal{A}'\subseteq\mathcal{A}$ that decomposes into a fibre bundle. His construction is an instance of the following.

Lemma: Let $\mathcal{B}\subseteq\mathcal{A}$ be a subsemilattice and $X\in\mathcal{A}$ such that $-\vee X:\mathcal{B}\to\mathcal{A}$ is injective. Then the intervals $[B,B\vee X]$ are disjoint, and $\mathcal{A}':= \bigcup_B [B,B\vee X]$ decomposes into a fibre bundle over $\mathcal{B}$.

Proof: The intervals are disjoint since if $A\in [B,B\vee X]\cap [C,C\vee X]$, then $B\vee X = A\vee X = C\vee X$, and therefore $B = C$ by assumption. So concerning the bundle, the fibre over $C\in\mathcal{B}$ is precisely the interval $\mathcal{B}_C := [C,C\vee X]$, and the transition map $\phi_{B,C} : [B,B\vee X]\to [C,C\vee X]$ for $B\leq C$ in $\mathcal{B}$ is given by $\phi_{B,C}(A) := A\vee C$. This is join-preserving and satisfies the required cocycle condition $\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}$ for $B\leq C\leq D$. It is straightforward to check that the inclusion map of the bundle $\mathcal{A}':=\int\mathcal{B}$ into $\mathcal{A}$ is a semilattice homomorphism. QED.

When applying this, it is likely relevant to have a lower bound on the size of this subsemilattice in order to guarantee that it is not too small relative to $\mathcal{A}$. The estimate $\sum_{B\in\mathcal{B}} |[B,B\vee X]| \geq \sum_B 2^{\frac{|\uparrow B| - |\uparrow(B\vee X)|}{m}} \geq 2^{-\frac{|\uparrow X|}{m}} \sum_B 2^{\frac{|\uparrow B|}{m}}$ seems to be part of what Wójcik uses. So the challenge is to make $\mathcal{B}$ and the $\uparrow B$'s large, while keeping $\uparrow X$ small.

The way that Wójcik achieves this is to first fix $X$ in a clever way. He then considers the join-irreducibles $\mathcal{J}_X$ in the upset $\uparrow X$, and then chooses for every $J\in\mathcal{J}_X$ some join-irreducible $G(J)$ in $\mathcal{A}$ with $J = G(J)\vee X$. Then $\mathcal{B}$ is taken to be the semilattice generated by the $G(J)$'s. Using a Kruskal-Katona type bound (Theorem 3.1) completes his arguments. But more on this some other time.

## Equal maximal chains

Another extreme situation is when all maximal chains have equal length, i.e. that $\mathcal{A}$ satisfies the Jordan-Dedekind chain condition. In this case, $\mathcal{A}$ is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height $h$ and the width $w$; since $(h-1)(w-1)\geq n-1$, they can't both be too small. Using the JD chain condition, do arguments along the lines of Dilworth's theorem or Mirsky's theorem give more information?

### Case a: large height

The height of $\mathcal{A}$ can be at most $h=j+1$. If this value is reached, then $\mathcal{A}$ has a prime element by the dual of Theorem 15 in this paper, and therefore we can assume $h\leq j$.

### Case b: large width

In this case, one can try to choose a large maximal antichain and a join-irreducible element $x$ such that $\mathcal{A}_x$ contains as few elements of the antichain as possible.

## From strong FUNC to weighted FUNC

Strong FUNC (Poonen): Every finite lattice $A$ has a join-irreducible element of abundance at most $1/2$, with equality if and only if $A$ is a Boolean algebra.

Weighted FUNC: If $w:\mathcal{A}\to\mathbb{R}_{\geq 0}$ is monotone in the sense that $w(A)\geq w(B)$ for $A\leq B$, then there exists a join-irreducible element $A$ of $w$-abundance at most $\frac{1}{2}\sum_B w(B)$.

Proposition: Strong FUNC implies weighted FUNC in the special case where every weight is a power of $2$.

Proof sketch: Use the fibre bundle construction with base $\mathcal{A}$. For the fibre $\mathcal{A}_B$, take a Boolean algebra of size $w(B)$, which is possible since $w(B)$ is a power of $2$. The transition maps $\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C$ are specified by using the fact that the Boolean algebra of size $w(B)$ is the free join-semilattice on $\log_2 w(B)$ many generators, and so we take $\phi_{B,C}$ to be the unique join-preserving extension of a suitable surjective map from a set of size $\log_2 w(B)$ to a set of size $\log_2 w(C)$. In order to guarantee the cocyle condition $\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}$, one can choose these in a canonical manner by totally ordering all the sets of generators and then choosing the functions to be those surjective order-preserving maps that e.g. collapse the upper interval of suitable size.

The resulting bundle $\int\mathcal{A}$ is a finite lattice of size $\sum_B w(B)$. There are two kinds of join-irreducibles: first, those in the fibre $\mathcal{A}_0$, which all have an abundance of exactly $1/2$; second, the bottom elements of the fibres $\mathcal{A}_J$ for $J$ join-irreducible in $\mathcal{A}$, with abundance $\sum_{B\in\uparrow J} w(B)$. Hence by strong FUNC, there is $J$ with $\sum_{B\in\uparrow J} w(B) \lt \frac{1}{2}\sum_B w(B)$ if and only if $\int\mathcal{A}$ is not a Boolean algebra. The latter is guaranteed if $\mathcal{A}$ itself is not a Boolean algebra, since then there is some non-trivial relation between join-irreducibles. Since we know weighted FUNC to hold in the case that $\mathcal{A}$ is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

## Poset FUNC

Conjecture: Let $\mathcal{P}$ be a finite poset with a least element and $|\mathcal{P}|\geq 2$. Then there is a join-irreducible element $A\in\mathcal{P}$ with $|\uparrow A|\leq |\mathcal{P}|/2$.

Without the assumption of a least element, taking a Boolean algebra and removing the least element would result in a counterexample.

The meaning of "join-irreducible" here is that $A$ is join-irreducible if $A = B\vee C$ implies $A=B$ or $A=C$. This condition seems a bit artificial, since the more natural notion of join-irreducibility would be to require that if $A$ is a join of an arbitrary collection of elements, then $A$ itself must be a member of this collection. While this definition essentially coincides with the earlier one in case of a lattice, in non-lattice posets there are in general fewer join-irreducible elements with the latter definition. This results in simple counterexamples to Poset FUNC with the latter definition, such as taking the power set of a 5-set and removing all the 2-sets.