Lattice approach

From Polymath Wiki
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 [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].

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.