Lattice approach

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

General observations

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

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

Concerning abundances, we have [math]\displaystyle{ |\hat{\mathcal{A}}| = |\mathcal{A}| + 2|\mathcal{J}| }[/math], and assume the existence of an atom [math]\displaystyle{ A_J }[/math] such that [math]\displaystyle{ |\hat{\mathcal{A}_{A_J}}| \leq c |\hat{\mathcal{A}}| }[/math]. This implies [math]\displaystyle{ |\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]\displaystyle{ |\mathcal{J}|/|\mathcal{A}| }[/math] to be arbitrarily small. QED.

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

Easy lattice classes

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

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

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

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

By a result of Björner, we can therefore also assume that [math]\displaystyle{ \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]\displaystyle{ \mathcal{J}'\subseteq\mathcal{A} }[/math] be a set of join-irreducibles with [math]\displaystyle{ \bigvee \mathcal{J}' = 1 }[/math] and minimal with this property. Then some member of [math]\displaystyle{ \mathcal{J}' }[/math] has abundance at most [math]\displaystyle{ 2^{|\mathcal{J}'|-1} + \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|} }[/math], resulting in [math]\displaystyle{ m\geq 2^{|\mathcal{J}'|-1} + \frac{n-2^{|\mathcal{J}'|}}{|\mathcal{J}'|}$. Note that at the two extreme values \lt math\gt |\mathcal{J}'|=2 }[/math] or [math]\displaystyle{ |\mathcal{J}'|=\log_2(n) }[/math], this establishes [math]\displaystyle{ m \geq n/2 }[/math]. However, unless [math]\displaystyle{ |\mathcal{J}'| }[/math] is very close to the maximal value [math]\displaystyle{ \log_2(n) }[/math], the bound is only marginally better than Knill's original one, which is [math]\displaystyle{ m\geq \frac{n-1}{|\mathcal{J}'|} }[/math].

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

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

[math]\displaystyle{ w\geq 1 }[/math] already fixes the distribution of a total weight of [math]\displaystyle{ 2^{|\mathcal{J}'|} }[/math]. For the remaining weight of [math]\displaystyle{ n-2^{|\mathcal{J}'|} }[/math], the worst-case scenario is that it is completely concentrated on the coatoms of [math]\displaystyle{ \mathcal{B}_{\mathcal{J}'} }[/math]. (And this can indeed happen.) Since every [math]\displaystyle{ J\in\mathcal{J}' }[/math] is contained in all but one coatoms, the pigeonhole principle guarantees that there is [math]\displaystyle{ J }[/math] whose abundance with respect to the remaining weight is at most [math]\displaystyle{ \frac{(|\mathcal{J}'|-1)(n-2^{|\mathcal{J}'|})}{|\mathcal{J}'|} }[/math]. This means that its total abundance is at most [math]\displaystyle{ 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]\displaystyle{ \mathcal{A} }[/math] contains a maximal chain of length [math]\displaystyle{ c }[/math]. Then [math]\displaystyle{ m \geq \frac{n-1}{c-1} }[/math].

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

Wójcik's argument

Wójcik's proof is based on considerations involving disjoint intervals. These can be generalized to the following:

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

For [math]\displaystyle{ A=0 }[/math] and [math]\displaystyle{ B=1 }[/math], this specializes to Knill's result.

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

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

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

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

Equal maximal chains

Another extreme situation is when all maximal chains have equal length, i.e. that [math]\displaystyle{ \mathcal{A} }[/math] satisfies the Jordan-Dedekind chain condition. In this case, [math]\displaystyle{ \mathcal{A} }[/math] is graded. We distinguish two subcases depending on the height [math]\displaystyle{ h }[/math] and the width [math]\displaystyle{ w }[/math]; since [math]\displaystyle{ (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]\displaystyle{ \mathcal{A} }[/math] can be at most [math]\displaystyle{ h=j+1 }[/math]. If this value is reached, then [math]\displaystyle{ \mathcal{A} }[/math] has a prime element by the dual of Theorem 15 in this paper, and therefore we can assume [math]\displaystyle{ 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]\displaystyle{ x }[/math] such that [math]\displaystyle{ \mathcal{A}_x }[/math] contains as few elements of the antichain as possible.