Lattice approach

From Polymath Wiki
Revision as of 00:28, 14 March 2016 by TobiasFritz (talk | contribs) (clarified)
Jump to navigationJump to search

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}|=m }[/math], and write [math]\displaystyle{ n=|\mathcal{A}| }[/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.

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^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|} }[/math].

Note that at the two extreme values [math]\displaystyle{ |J|=2 }[/math] or [math]\displaystyle{ |J|=\log_2(n) }[/math], this establishes an element of abundance at most [math]\displaystyle{ 1/2 }[/math]. Unless [math]\displaystyle{ 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{ n - \frac{n-1}{|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^{|J|} }[/math]. For the remaining weight of [math]\displaystyle{ n-2^{|J|} }[/math], the worst-case scenario is that it is completely concentrated on the coatoms of [math]\displaystyle{ \mathcal{B}_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{(|J|-1)(n-2^{|J|})}{|J|} }[/math]. This means that its total abundance is at most [math]\displaystyle{ 2^{|J|-1} + \frac{(|J|-1)(n-2^{|J|})}{|J|} }[/math], as was to be shown.

Corollary: Suppose that [math]\displaystyle{ \mathcal{A} }[/math] contains a maximal chain of length [math]\displaystyle{ c }[/math]. Then there is a join-irreducible element of abundance at most [math]\displaystyle{ n - \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.

Case 2: Equal maximal chains

The opposite extreme is that 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 2a: large height

The height of [math]\displaystyle{ \mathcal{A} }[/math] can be at most [math]\displaystyle{ h=m+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 we are done since every prime element is rare.

Case 2b: large width

In this case, 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.