We use the standard convention that a two-intersecting family satisfies for every pair of members, including . In particular every member has at least two elements.
An intersecting shadow lemma. If is an intersecting family of -sets, , then
Here is a proof, so no additional shadow theorem is being assumed. For , an elementary set shift replaces a member containing but not by exactly when that replacement is not already in the family. This preserves cardinality and the intersecting family property. The only potentially troublesome pair consists of a moved member and an unmoved member containing but not . But then 's replacement was already present, and the two original members obtained by using that replacement would have been disjoint if the new pair were disjoint.
Also
so an elementary set shift cannot increase the lower shadow. For completeness, a shadow set containing neither or both has an unchanged witness in the original lower shadow. A shadow set containing but not is either originally present or the replacement of an originally present shadow set. If a shadow set contains but not , its witnessing member survived the elementary set shift; either that member contains both coordinates, or its replacement was already present. In either case both the shadow set and its replacement were originally present, so the former survives in the shifted lower shadow.
Repeated elementary set shifts terminate because the sum of the elements of all members decreases whenever the family changes. In the resulting shifted set family , if is a member and satisfies for every , then is also a member. Every has a prefix containing of its elements. Otherwise its sorted elements satisfy , and the first elements outside form a disjoint member componentwise no larger than , contradicting the intersecting family property.
Choose the first such prefix and reflect membership inside it:
This has size . The set is componentwise no larger than : before the first excess, the prefix counts of are at most half the prefix length, and reflection only moves selected positions to the left. Thus belongs to . This ballot reflection injection is injective: in , the reflected prefix ends at the first position where unselected positions outnumber selected ones, and reflecting it again recovers . Consequently . Since elementary set shifts did not increase the lower shadow, this proves the intersecting shadow lemma.
The nonuniform two-intersecting family bound. Write . No member of can be the complement of a member of : such an inclusion would make the intersection of the two original members have at most one element. The intersecting shadow lemma therefore gives
For , sum this over . These pairs cover all nonempty levels, so
Equality is attained by all subsets of size at least : any two intersect in at least two elements.
For , the same pairs cover every level except . Complements of the members of form an intersecting family of -sets, since
For , the permitted Erdős-Ko-Rado theorem bounds this middle level by . Hence
Equality is attained by all -sets inside , together with all subsets of of size at least . Two members of the first group intersect in at least two elements; a member from each group intersects in at least two; two members of the second group intersect in at least three. For the only two-intersecting family is empty, which also gives equality. The empty-ground-set case is likewise immediate.
The pair-cover bound for a two-intersecting uniform family. If is nonempty, fix , with . Every member contains one of the pairs inside . Each fixed pair belongs to exactly -sets, so counting their union gives
The empty family is immediate; a nonempty two-intersecting family requires .
Witness-pair concentration for an intersecting uniform family. Let now be an intersecting family of -sets. If it is two-intersecting, the preceding bound, together with for , shows that any chosen has the required property. Otherwise there are members with . Every member not containing must contain some and some . These two sets of possible witnesses are disjoint. There are witness pairs, and each is contained in -sets. Thus
For , a nonempty intersecting family consists of one singleton; choose its element and the number avoiding it is zero. This is the natural separate interpretation of the degenerate case, where the printed binomial coefficient has lower index . For an empty family any works, provided as usual.
The Kruskal-Katona theorem. For a uniform set family of -sets, its lower shadow is
If consists of the first -sets in colexicographic order, then
Here in colexicographic order means that the largest element of the symmetric difference belongs to . In terms of the unique greedy binomial representation
the bound is
For the right side is zero. We prove both the minimizing assertion and this formula.
First, the lower shadow of a colexicographic initial segment is a colexicographic initial segment. One way to check this is to extend an -set by its least missing positive integer; this is its earliest -set extension in colexicographic order. If , the earliest extension of is no later than the earliest extension of . To see the latter assertion, let . If misses an integer below , its least missing integer is below , so its earliest extension is still earlier than the earliest extension of . Otherwise contains every integer below . Above the two sets agree, and their equal sizes force to contain and all but one integer below . Adding that missing integer to , or adding to , gives the same earliest extension. Thus every set earlier than a member of the lower shadow is also in that lower shadow.
We now prove the minimizing assertion by induction on the size of a finite ground set. The case is immediate: a nonempty uniform set family of singletons has lower shadow . The empty case and are also immediate. For a coordinate , write the two sections of as
They are respectively - and -uniform set families on . Perform a colexicographic section compression: replace each section by the colexicographic initial segment of the same size. The two sections of the lower shadow before this operation are
By the inductive hypothesis the individual lower shadows do not grow. After colexicographic section compression, both families in the displayed union are colexicographic initial segments, so their union has the larger of their two sizes. This is no greater than the original union. Consequently colexicographic section compression preserves and does not increase . A section of size zero causes no difficulty; a section of -sets is already compressed and its lower shadow is empty.
Repeat any colexicographic section compression that changes the family. The sum of the positions of its members in colexicographic order strictly decreases, since restriction to either fixed-coordinate section preserves that order. Hence the process terminates at a family all of whose sections are colexicographic initial segments.
There is only one possible obstruction to itself being a colexicographic initial segment. Suppose , and . No coordinate can belong to both , or to neither: either possibility would contradict the compressed section at that coordinate. Thus partition , and . Moreover, every such inversion must use this same complementary pair: any omitted set below equals , and any included set above equals . These observations also rule out an inversion completely before or after this pair. A set strictly between and would have to be both present, by comparison with , and absent, by comparison with . Therefore are consecutive in colexicographic order. Since contains and does not, they must be
Thus the exceptional family is . For , deleting leaves every -set of in the lower shadow: each has extensions inside , so at least one remains. Its lower shadow therefore contains the lower shadow of the equally sized colexicographic initial segment . The case was already handled. This proves the minimizing assertion in all cases.
Finally the greedy binomial representation describes the successive blocks of a colexicographic initial segment. Its first block is , and the remaining sets are obtained by adding to an initial segment of -sets inside . The lower shadow without has members; the lower shadow containing is the corresponding lower-rank lower shadow. Repeating this decomposition proves the displayed binomial coefficient formula and completes the Kruskal-Katona theorem proof.
The specified initial segment covers every -set of . Assume and , the nontrivial range. The last -set of in colexicographic order is
Its earliest -set extension is . Exactly sets of come after this extension: they are with . Its position is therefore
At the stated threshold, belongs to . Since the lower shadow is a colexicographic initial segment,
For , the threshold is and a nonempty family of singletons has in its lower shadow. If , the threshold is again ; the first -set is , which contains . If , the desired inclusion is empty and automatic.
The nonuniform bound. Suppose first that and, contrapositively, that . Let be the colexicographic initial segment of -sets of size ; this consists of with its last member removed. For each , put , and replace it by the equally sized colexicographic initial segment .
Iterating the Kruskal-Katona theorem shows that the iterated lower shadow down to size of has no more members than the corresponding iterated lower shadow of . Indeed, at each step initial segments minimize the next lower shadow, and its minimum size is increasing in the input size. The latter iterated lower shadow lies in . Therefore every -subset of every member of lies in .
For , a -set with this property must lie inside : otherwise an -subset containing an element larger than would lie outside . Among -sets inside , exactly those containing are forbidden. Hence
Adding these bounds proves the contrapositive. Thus the strict threshold forces
When , the threshold merely says that is nonempty, so . When , the claimed lower bound is zero. The strict inequality is sharp: the family of all subsets of of size at least that do not contain attains the displayed sum and has exactly members in its size- iterated lower shadow.
The LYM inequality. For an antichain in the Boolean lattice,
To prove this by double counting, generate a maximal chain in a Boolean lattice from a permutation of : its members are the first entries of , for . A particular -set belongs to exactly of the resulting maximal chains in a Boolean lattice. Each such maximal chain in a Boolean lattice meets the antichain at most once. Counting pairs consisting of a member of and a permutation whose associated maximal chain in a Boolean lattice contains it gives
Division by proves the LYM inequality, including the empty antichain and the levels containing or .
A symmetric chain decomposition of a Boolean lattice. A symmetric chain has one set at every size from to , with consecutive members related by inclusion. Start with the single symmetric chain containing when . Given a symmetric chain
in a symmetric chain decomposition of a Boolean lattice on , let and replace its two copies in the larger Boolean lattice by
and, when it is nonempty, by
The endpoint sizes of the first symmetric chain sum to ; those of the second symmetric chain also sum to . These symmetric chains partition the original symmetric chain together with its copy containing . Thus this construction inductively partitions the entire Boolean lattice into symmetric chains. Each symmetric chain contains exactly one set of size , so the number of symmetric chains is
The proposed sum bound for cross-intersecting families is false. Take and
Both are antichains, and any member of one meets any member of the other. Nevertheless,
The hypothesis permits the two antichains to coincide. Even if distinct antichains were wanted, taking gives .
For , write for multiplication by in . The algebraic differential operator ring is defined by the filtration
The order of an algebraic differential operator is the least for which ; the zero operator may be assigned order . In degree zero, commuting with all multiplication maps means , so . The commutator identity proves by induction that , so the union is a ring under addition and composition.
The derivations of an algebra form
Every such derivation has and , so has differential order at most one. Conversely, if , set and . Then and is a multiplication map. Evaluating at shows it is ; evaluating at gives the Leibniz rule. Hence the first-order algebraic differential operator decomposition is
It is a direct sum as -vector spaces: a multiplication map that is a derivation vanishes at , and is zero.
The complex Weyl algebra has generators and relations
Take . If a nonzero unital module had finite dimension of a vector space over , its representing matrices would satisfy . Taking the matrix trace gives , impossible in characteristic zero. The Weyl algebra has no nonzero finite-dimensional modules. For the algebra is and this assertion has the obvious exception.
For a nonzero finitely generated Weyl algebra module, use the Bernstein filtration
The ordered monomials form a vector space basis, so
To justify the ordered basis, the relations move all to the right and give spanning. Independence follows in the action on : apply a putative zero operator coefficientwise to the formal exponential , obtaining . Thus every coefficient vanishes.
Choose a finite-dimensional nonzero generating subspace and set . The associated graded module is finitely generated over the polynomial associated graded ring, so the Hilbert-Serre theorem implies is eventually a polynomial. Define
This Bernstein growth dimension of a Weyl algebra module equals the Gelfand–Kirillov dimension of a module, not its ordinary vector-space dimension. If a different finite generating subspace is used, each lies in some fixed filtration step of the other. The corresponding are sandwiched between shifted filtrations, so the degree is unchanged.
We prove Bernstein inequality for Weyl algebra modules using an injectivity estimate. The faithful finite-step action of a Weyl algebra claim is that the map
is injective for every . Induct on . For , a scalar annihilating is zero. Suppose annihilates . For any generator or , the commutator belongs to and annihilates : both and vanish. The induction hypothesis gives for every generator. In the ordered basis,
In characteristic zero these identities force to be a scalar. Since it annihilates , it is zero. This proves injectivity.
Consequently
The left side grows as a positive constant times ; the right side has growth degree . Comparing powers proves
The polynomial module , with the usual multiplication and differentiation actions, has , showing the bound is sharp.
A local ring is a nonzero ring with one maximal ideal . Write for its residue field. Its Krull dimension is the supremum of lengths of strict chains of prime ideals; in a local ring chains may be extended to end at .
For the local Hilbert-function convention, define the Hilbert–Samuel growth dimension
Equivalently it is the order of the pole at of the Hilbert series of the associated graded ring
This finite standard graded -algebra is generated by . The Hilbert-Serre theorem makes the cumulative Hilbert function eventually polynomial, which establishes the definition. For an Artinian local ring, the polynomial is constant and nonzero, so .
For every prime chain of length , the prime-chain lower bound for local length proved in Question 4 gives . A polynomial of degree cannot satisfy this when . Thus the requested inequality is
For clarity, the embedding dimension is the different invariant
The equality follows from the Nakayama lemma. Applying Question 4 to gives , while the polynomial-algebra surjection below also gives . In particular, growth dimension and embedding dimension should be kept distinct.
A regular local ring is a Noetherian local ring with . Let this common value be and choose a minimal generating set of . The initial forms give a surjective graded ring homomorphism
For , the Nakayama lemma gives , so is a field. Assume . If the kernel contained a nonzero homogeneous polynomial of degree , the cumulative Hilbert function of the target would be bounded by that of . Multiplication by is injective in the polynomial integral domain, so this bound is
But provides a prime chain of length , and Question 4 gives . This is a contradiction. Hence the associated graded ring of a regular local ring is
an integral domain.
Finally the Krull intersection theorem gives . One can see the needed separatedness directly: for the finitely generated ideal , the Artin-Rees lemma gives , and the Nakayama lemma gives . Therefore each nonzero has finite -adic order , with nonzero initial form in . For nonzero , their initial forms have nonzero product in the graded integral domain. It follows that , and indeed its order is the sum of their orders. Thus is an integral domain.

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact