Lattice approach

From Polymath Wiki
Revision as of 01:51, 11 March 2016 by TobiasFritz (talk | contribs)
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 containing [math]\displaystyle{ m }[/math] join-irreducibles, and write [math]\displaystyle{ n=|\mathcal{A}| }[/math].

Throwing in a new atom below every join-irreducible creates a new lattice in which abundances differ by less than a factor of 2. So for the purposes of weak FUNC, it should be possible to assume wlog that [math]\displaystyle{ \mathcal{A} }[/math] is atomistic.

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.