# Lattice approach

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 [math]\mathcal{A}[/math] be a finite lattice with set of join-irreducibles [math]\mathcal{J}[/math] of cardinality [math]|\mathcal{J}|=j[/math], and write [math]n=|\mathcal{A}|[/math]. Write [math]m[/math] for the maximum of [math]n - \uparrow\{J\}[/math] over all join-irreducibles [math]J[/math]; the goal is to lower bound [math]m[/math] in terms of [math]n[/math], and FUNC claims that [math]m\geq n/2[/math].

## Contents

## General observations

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

**Proof:** For given [math]\mathcal{A}[/math], consider the [math]k[/math]-th cartesian powers [math]\mathcal{A}^k[/math]. (Weak) FUNC holds for any one of these if and only if it holds for [math]\mathcal{A}[/math] itself. Since the number of join-irreducibles of [math]\mathcal{A}^k[/math] is [math]k|\mathcal{J}|[/math], which grows much slower than [math]|\mathcal{A}|^k[/math], the claim follows by choosing [math]k[/math] 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 [math]\mathcal{J}[/math] be the set of join-irreducibles of [math]\mathcal{A}[/math]. Define [math]\hat{\mathcal{A}}[/math] as being equal to [math]\mathcal{A}[/math] together with two additional elements [math]A_J,A'_J[/math] for every [math]J\in\mathcal{J}[/math], ordered such that [math]0\leq A_J,A'_J\leq J[/math], and incomparable to all other elements. Then [math]\hat{\mathcal{A}}[/math] is again a lattice: the join of any two 'old' elements is as before; the join of [math]A_J[/math] with some [math]K\in\mathcal{A}[/math] is [math]J\vee K[/math], and similarly the join of [math]A_J[/math] with [math]A_K[/math] is [math]J\vee K[/math]; and crucially, [math]A_J\vee A'_J = J[/math]. So by virtue of being a finite join-semilattice, [math]\hat{\mathcal{A}}[/math] is automatically a lattice. It is atomistic by construction.

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

Hence we assume wlog that [math]\mathcal{A}[/math] is atomistic.

## Easy lattice classes

**Proposition:** If atomistic [math]\mathcal{A}[/math] has a prime element, then [math]\mathcal{A}[/math] satisfies FUNC.

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

**Proposition (Poonen):** If every downset [math]\downarrow\{A\}[/math] is complemented, then [math]\mathcal{A}[/math] satisfies FUNC.

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

By a result of Björner, we can therefore also assume that [math]\mathcal{A}[/math] 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 [math]\mathcal{J}'\subseteq\mathcal{A}[/math] be a set of join-irreducibles with [math]\bigvee \mathcal{J}' = 1[/math] and minimal with this property. Then some member of [math]\mathcal{J}'[/math] has abundance at most [math]2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|}[/math], resulting in [math]m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}[/math].

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

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

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

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

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

**Proof:** If the maximal chain is [math]0=A_1\subseteq A_2\subseteq\ldots\subseteq A_c = 1[/math], then write [math]A_{k+1} = A_k\lor J_k[/math] for join-irreducible [math]J_k[/math]. Then [math]\bigvee_k J_k = 1[/math], and choose a minimal subset of the [math]J_k[/math]'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 [math]A\leq B[/math] in [math]\mathcal{A}[/math]. Then [math]m\geq\frac{|\uparrow A| - |\uparrow B|}{\log_2|[A,B]|}[/math].

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

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

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

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

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

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

**Lemma:** For [math]A\lt B[/math], we have [math]m\geq\frac{|\uparrow A| - |\uparrow B|}{c(A,B)}[/math].

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

## Wójcik's fibre bundle decomposition

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

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

**Proof:** The intervals are disjoint since if [math]A\in [B,B\vee X]\cap [C,C\vee X][/math], then [math]B\vee X = A\vee X = C\vee X[/math], and therefore [math]B = C[/math] by assumption. So concerning the bundle, the fibre over [math]C\in\mathcal{B}[/math] is precisely the interval [math]\mathcal{B}_C := [C,C\vee X][/math], and the transition map [math]\phi_{B,C} : [B,B\vee X]\to [C,C\vee X][/math] for [math]B\leq C[/math] in [math]\mathcal{B}[/math] is given by [math]\phi_{B,C}(A) := A\vee C[/math]. This is join-preserving and satisfies the required cocycle condition [math]\phi_{C,D}\circ\phi_{B,C} = \phi_{B,D}[/math] for [math]B\leq C\leq D[/math]. It is straightforward to check that the inclusion map of the bundle [math]\mathcal{A}':=\int\mathcal{B}[/math] into [math]\mathcal{A}[/math] 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 [math]\mathcal{A}[/math]. The estimate [math]\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}}[/math] seems to be part of what Wójcik uses. So the challenge is to make [math]\mathcal{B}[/math] and the [math]\uparrow B[/math]'s large, while keeping [math]\uparrow X[/math] small.

The way that Wójcik achieves this is to first fix [math]X[/math] in a clever way. He then considers the join-irreducibles [math]\mathcal{J}_X[/math] in the upset [math]\uparrow X[/math], and then chooses for every [math]J\in\mathcal{J}_X[/math] some join-irreducible [math]G(J)[/math] in [math]\mathcal{A}[/math] with [math]J = G(J)\vee X[/math]. Then [math]\mathcal{B}[/math] is taken to be the semilattice generated by the [math]G(J)[/math]'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 [math]\mathcal{A}[/math] satisfies the Jordan-Dedekind chain condition. In this case, [math]\mathcal{A}[/math] is graded. What can we say in this case?

It may be relevant to distinguish two subcases depending on the height [math]h[/math] and the width [math]w[/math]; since [math](h-1)(w-1)\geq n-1[/math], 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 [math]\mathcal{A}[/math] can be at most [math]h=j+1[/math]. If this value is reached, then [math]\mathcal{A}[/math] has a prime element by the dual of Theorem 15 in this paper, and therefore we can assume [math]h\leq j[/math].

### Case b: large width

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

## From strong FUNC to weighted FUNC

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

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

**Proposition:** Strong FUNC implies weighted FUNC in the special case where every weight is a power of [math]2[/math].

**Proof sketch:** Use the fibre bundle construction with base [math]\mathcal{A}[/math]. For the fibre [math]\mathcal{A}_B[/math], take a Boolean algebra of size [math]w(B)[/math], which is possible since [math]w(B)[/math] is a power of [math]2[/math]. The transition maps [math]\phi_{B,C}:\mathcal{A}_B\to\mathcal{A}_C[/math] are specified by using the fact that the Boolean algebra of size [math]w(B)[/math] is the free join-semilattice on [math]\log_2 w(B)[/math] many generators, and so we take [math]\phi_{B,C}[/math] to be the unique join-preserving extension of a suitable surjective map from a set of size [math]\log_2 w(B)[/math] to a set of size [math]\log_2 w(C)[/math]. In order to guarantee the cocyle condition [math]\phi_{C,D}\circ \phi_{B,C} = \phi_{B,D}[/math], 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 [math]\int\mathcal{A}[/math] is a finite lattice of size [math]\sum_B w(B)[/math]. There are two kinds of join-irreducibles: first, those in the fibre [math]\mathcal{A}_0[/math], which all have an abundance of exactly [math]1/2[/math]; second, the bottom elements of the fibres [math]\mathcal{A}_J[/math] for [math]J[/math] join-irreducible in [math]\mathcal{A}[/math], with abundance [math]\sum_{B\in\uparrow J} w(B)[/math]. Hence by strong FUNC, there is [math]J[/math] with [math]\sum_{B\in\uparrow J} w(B) \lt \frac{1}{2}\sum_B w(B)[/math] if and only if [math]\int\mathcal{A}[/math] is not a Boolean algebra. The latter is guaranteed if [math]\mathcal{A}[/math] 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 [math]\mathcal{A}[/math] is a Boolean algebra anyway, there is no loss in assuming that it isn't. QED.

## Poset FUNC

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

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 [math]A[/math] is join-irreducible if [math]A = B\vee C[/math] implies [math]A=B[/math] or [math]A=C[/math]. This condition seems a bit artificial, since the more natural notion of join-irreducibility would be to require that if [math]A[/math] is a join of an arbitrary collection of elements, then [math]A[/math] 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.