The initial table of content was limited to the first level because it is larger than 1000 articles. There are 1749 articles in total. Expand a branch to load its children.
Use , and in the sl2 Lie algebra, so , , and . On the symmetric power, a monomial has weight . The tensor product of Lie algebra representations adds weights, because acts as .
Put and for . These eight vectors are a basis of ; their weights are and . Thus the weight-space decomposition and a weight basis for each summand areIn particular , with dimensions summing to eight. Here the subscripts are the eigenvalues of the chosen Cartan element .
Write for the irreducible representation of with highest weight , dimension and weights . The weight diagram below records multiplicities at weights .
The unique top weight four forces one copy of , by complete reducibility of semisimple Lie algebra representations. Removing its five weights, each with multiplicity one, leaves weights with multiplicity one, exactly the character of . HenceThe two lower rows draw their separate weight diagrams. The explicit invariant copies constructed next establish the Clebsch-Gordan splitting of a defining module and its cubic symmetric power within itself.
In the notation of part (i), the tensor raising operator and lowering operator act bywith terms beyond the stated index range omitted. Both and are killed by , and have respective weights four and two. They are the desired highest-weight vectors.
For , successive lowering givesThus a basis of the five-dimensional summand, in descending weight order, isFor , the successive vectors are , and . HenceThese spans are invariant under . The sl2 highest-weight lowering formula gives , so all interior raising coefficients in either chain are nonzero. Any nonzero submodule therefore contains the highest vector and then the whole chain; each span is irreducible.
At the shared weights , the two displayed summand vectors are independent: their coefficient determinants in the original weight bases are . At weights only the five-dimensional summand occurs. Consequently the eight displayed vectors form a basis of , proving that these are complementary submodules, not only modules with the right dimensions.
Let , and let be the weight of a representation defined by . Since the trace is zero, . The dual representation gives weight to . PutTaking gives an eighteen-vector tensor product basis. Its weight is .
For explicit coordinates use the usual simple coroots and , and write each weight as . Then , and . Collecting equal weights gives every weight space:The first six weights are with ; the next three are ; the last three are the defining weights . Thus there are nine multiplicity-one weights and three multiplicity-three weights, giving total dimension .
The planar coordinates are with and , so the weight diagram uses an equilateral root geometry rather than orthogonal Dynkin-coordinate axes. Every point is labelled with its complete weight-space basis.
Define an equivariant contraction byThis uses the natural dual pairing, so it commutes with the Lie algebra representation. Also define . The identity tensor is invariant, making equivariant. Direct contraction gives . Thus is injective and is surjective, andis a direct decomposition into and . In particular and is a defining irreducible module of highest weight .
For the usual upper-triangular choice of positive roots, lies in the kernel and is killed by both simple raising operators . Its highest weight is , with Dynkin labels . The highest-weight classification and complete reducibility give an irreducible copy generated by this vector. The Weyl dimension formula for isso . It fills the entire kernel. Therefore the sl3 decomposition of the symmetric-square dual tensor product, with its tensor factors exchanged, isThe weight diagrams below record both summands. Their labels use for and ; these are the weight bases detailed in part (iii).
The nine one-dimensional weight spaces from part (i) all lie in , because the dual index differs from every polynomial index. Their bases remain at weight for , and at weight for three distinct indices .
At weight , the full space has basis , where are the two other indices. Their contractions are . Thus the contraction kernel has the independent basis and . Explicitly the weight basis of the trace-free symmetric-square dual tensor module is completed byTogether with the nine single vectors, these give fifteen independent vectors. They are precisely the and labels on the fifteen-dimensional weight diagram.
The defining summand has only the following three weight spaces:Each is nonzero, has its indicated weight and satisfies . These are the labels on the three-dimensional diagram. The highest-weight vectors in the two summands areAt each repeated weight, the two kernel vectors together with span the original three-dimensional weight space, since the kernel has dimension two and . Thus the displayed diagrams specify all submodule weight-space bases.
Here the Cartan subalgebra of a finite-dimensional complex semisimple Lie algebra is a maximal toral subalgebra: it is abelian, its adjoint operators are simultaneously diagonalizable, and its centralizer is itself. These standard properties give the root-space decompositionThe roots of a root system are the nonzero linear functionals in for which ; is their finite set. Each root space is one-dimensional. The zero weight space is the centralizer of , hence exactly . Thus the displayed sum is a direct sum of simultaneous eigenspaces of the Adjoint representation. It is the Cartan root-space decomposition meant here.
The bracket respects weight addition: , where and a missing weight means the zero space. This follows by applying the Jacobi identity with to the bracket of two root vectors. It explains how the vector-space decomposition encodes the Lie algebra structure.
The Killing form is the bilinear formThe Adjoint representation is linear, giving bilinearity, and the cyclic property of trace gives symmetry. To prove invariance, abbreviate the adjoint matrices of by . The Jacobi identity gives , and cyclic trace then givesThus , equivalently . This is infinitesimal invariance of the Killing form, with no choice of basis affecting the trace.
First show that the Cartan subalgebra is orthogonal, for the Killing form, to every nonzero root space. For and , choose with . Invariance and the abelian nature of giveHence .
Now let be in the radical of the restriction to , so for every . The preceding argument also gives for every root. By the root-space decomposition, is orthogonal to all of . The assumed nondegeneracy on forces . Therefore the Killing form restricted to the Cartan subalgebra is nondegenerate.
Take the basis of , where , and is a matrix unit. For , and . Thus the Adjoint representation matrix isSquaring and taking the trace computes the Killing form directly:The independent identity for the special linear Lie algebra also gives .
For the embedded Lie group, the tangent space consists of velocities of smooth curves in satisfying . The ambient coordinates identify these velocities with vectors in , but the tangent space itself is intrinsic. Let . Since this conjugation map fixes , its derivative defines the Adjoint representation of a Lie group:The inverse is , and gives . Thus this is a smooth group homomorphism into the linear automorphisms of .
Differentiate that representation at the identity. The tangent space of at its identity is , so is a linear map from into those endomorphisms. The Lie bracket isEquivalently, if and , this is the mixed derivative at of in ambient coordinates. For a matrix Lie group, conjugation is ordinary matrix conjugation and this formula reduces to .
The checks required are that the derivative is independent of the representing curves, that it is bilinear and alternating, and that it satisfies the Jacobi identity. One must also check that each preserves this bracket. Equivalently identify with its left-invariant vector field ; the bracket above agrees with the Lie bracket of vector fields at . These checks make a Lie algebra and upgrade the adjoint maps to its Lie algebra automorphisms.
The tangent matrices areUse the derivative of conjugation from part (i), rather than assuming antisymmetry. Since , direct multiplication givesDifferentiating at zero yieldsFor the reverse order put , . The other conjugation isIts derivative at zero isBoth computations use actual curves in the special linear group; the opposite off-diagonal signs in ensure its determinant is one.
Use the finite-dimensional complex-module setting of the course. We prove the Weyl complete reducibility theorem by Haar averaging produces invariant complements, defining its constructions rather than invoking complete reducibility itself.
Choose a compact real form : it is a real Lie subalgebra with , and its simply connected Lie group is compact. Existence of this form and compact group is a standard fact for complex semisimple Lie algebras. Restrict the representation to ; integration of a Lie-algebra representation gives a group representation . Since is connected and generated by exponentials, the -invariant subspace is also -invariant.
Choose any positive-definite Hermitian inner product on . With the Haar measure of normalized to mass one, defineThis is a Hermitian inner product, and it is positive-definite: for every is nonzero, so the continuous positive integrand has positive integral. Right invariance of Haar measure gives for .
Let for this averaged inner product. Finite-dimensional inner-product linear algebra gives . If and , thenbecause . Thus is -invariant. Differentiating makes it -invariant, and since it is a complex vector subspace, also preserves it. ThereforeThe zero or whole-space submodule cases are included. This proves the required complement theorem without circularly assuming it.
The finite-dimensional hypothesis is essential to the statement. The nonsplit zero-weight Verma extension for sl2 is a counterexample for unrestricted modules: has basis with , and . Its submodule spanned by for has trivial one-dimensional quotient. A complement would be trivial and contained in the zero-weight line , yet . Hence no such complement exists in that infinite-dimensional case. The paper's finite-dimensional representation setting supplies the necessary hypothesis.
For a finite-dimensional Lie algebra representation , a weight of a representation relative to is a linear functional for which the simultaneous eigenspaceis nonzero. Its elements are weight vectors, and is the weight multiplicity. The set of weights is . For a complex semisimple Lie algebra, the Cartan action on a finite-dimensional module is simultaneously diagonalizable, giving . The set of weights and their multiplicities are distinct information: several basis vectors can occupy the same point of a weight diagram.
Let be the real span of the roots in . The weight lattice iswhere is the coroot in the root's sl2 subalgebra associated with a root, normalized by . It suffices to test the simple coroots. Equivalently, if defines the fundamental weights, then .
To prove integrality of representation weights on coroots, restrict a finite-dimensional module to the root's sl2 Lie algebra. By the classification of finite-dimensional sl2 representations, the eigenvalues of its Cartan element are integers. Thus every has . The simple coroots form a basis of the real Cartan space, so these integral values also put in . Therefore for every finite-dimensional representation in this setting. The weight lattice need not coincide with the smaller root lattice.
Choose a real linear functional nonzero on every root. Its positive system is . The other roots form . Thus exactly one of is positive, and a sum of positive roots that is a root is again positive because is additive.
The simple roots are the positive roots not expressible as a sum of two positive roots. They form a fundamental system of a root system; every positive root is a nonnegative integral combination of them. Positivity is a choice of ordering, rather than a property of a root independent of that choice.
For the chosen simple roots , the open fundamental chamber of a root system isEquivalently for every simple coroot. Since all positive roots are nonnegative combinations of simple roots, requiring the inequality for all positive roots gives the same chamber. It is a connected component of the complement of the root reflection hyperplanes; the Weyl group permutes those chambers simply transitively.
The Closed dominant Weyl chamber is obtained by replacing the inequalities by . It is the cone generated by the fundamental weights. When the fundamental Weyl chamber is taken to include its walls, this closed convention is intended; both conventions determine the same positive system and boundary rays.
For the usual diagonal Cartan subalgebra, write . The roots are for . The three diagonal entries of the specified have orderingTherefore the positive roots selected by areTheir positive evaluations are respectively , and . For this nonstandard ordering the simple roots are and ; the third positive root is their sum. These simple roots differ from the usual choice used in Question 1.
Identify the real weight plane with triples of sum zero. Pairing with these simple coroots gives the differences and . Consequently the fundamental chamber of a root system isIts closure replaces the inequalities by weak inequalities. The fundamental weights for this ordering are and , represented by and . Their simple-coroot pairings are and , so the two boundary rays areThe sketch uses , and in a Euclidean plane. The shaded sector is the sixty-degree closed chamber; its interior is the open chamber. The ordering vector , identified with its dual direction, lies inside it.
In the semisimple Lie algebra convention, an abstract root system is a finite subset of a finite-dimensional real Euclidean space with the following properties: it spans , does not contain zero, is reduced, is invariant under each of its root reflections, and satisfies crystallographic integrality. More explicitly, for every ,Here is a positive-definite inner product. The first condition is reducedness, the second gives closure under root reflections, and the last number is a Cartan integer. The rank is . A simple root basis is a basis of consisting of roots such that each root has integral coordinates that are either all nonnegative or all nonpositive. The two signs distinguish positive and negative roots. The diagrams in this problem concern these reduced crystallographic root systems; broader definitions sometimes omit one of these conditions.
The drawn simple roots have , and . Their Cartan integers are therefore and , identifying a B2 root system. The corresponding root reflections act on coordinates byIn particular and , so both new positive roots are forced. Reflection in any root also forces its negative. ThusThese eight roots are drawn below, with the given simple pair highlighted.
For completeness, no further roots can occur. In a finite reduced root system, every root is a Weyl group translate of a simple root: reflect a nonsimple positive root in a simple root with positive inner product to decrease its height, and iterate. This standard simple-root descent may also be quoted here. The eight-vector set just listed is stable under both generating reflections, and the orbits of the two simple roots already fill it. Hence no simple-root orbit, and therefore no root, lies outside that set. This establishes both the necessity of every drawn root and exhaustion of the root system.
The double-bond arrow points to the middle node in the PDF. Since and , the short root must occupy that middle node and the long root the left node. The right node , joined to by a single bond, is another short root. Thus the diagram is C3 root system type, labelled as follows.
Labelling the C3 Dynkin diagram with the given short and long roots
. Details. 
The bonds require , and . Writing gives , , and . One choice is thereforeThe opposite choice of the last coordinate reflects the entire realization across the first two coordinate axes' plane and is equally valid.
To enumerate exhaustively, set , and . These are orthonormal, andThe complete C3 root system is , with eighteen roots. Its nine roots with nonnegative coefficients in this simple basis are exactlyThere are six short and three long positive roots, and the other nine roots are their negatives.
The single-bond rank-two diagram is A2 root system type. Three suitable positive simple pairs for its root subsystems areEach pair has squared lengths one and inner product , so its angle is degrees. Its plane meets the full root set in , with respectively , and . These exhaust the roots of the plane, and their coordinates in the pair have one sign. Thus each pair is genuinely a simple basis of an subsystem.
The double-bond diagram is rank-two B2 root system type, equivalently . Three suitable pairs, written short root first, areFor each pair , , and . The remaining positive roots in its plane areTogether with their negatives these are precisely the eight plane roots, and all four positive roots have nonnegative integral pair-coordinates. Hence the displayed pairs are simple bases of the required subsystems. The rank-two subsystems of a C3 root system description explains these as the three coordinate-plane subsystems in the orthonormal realization; the chosen pairs lie in three different diagonal planes.
Let be a commutative Artinian ring. We prove finite composition length first, without assuming the conclusion that is Noetherian.
Every prime ideal is maximal. Indeed, an Artinian integral domain is a field: for , stabilization of gives , and cancellation gives . There are only finitely many maximal ideals. To see this, choose a minimal finite intersection using the descending chain condition. Minimality gives for any other maximal ideal . Since , primeness forces one , and maximality makes them equal. Thus the Jacobson radical is this finite intersection, and the Chinese remainder theorem gives
We also need nilpotence of . Its powers stabilize; put at a stabilization stage, so . If , choose an ideal minimal subject to . Since , minimality gives . Choose with . Minimality applied to the subideal gives . The equality then yields for some . But is a unit by the unit criterion for the Jacobson radical; hence , a contradiction. Therefore .
Each layer is an Artinian module over the finite product of fields . Its components over those fields are finite-dimensional: an infinite-dimensional vector space has a strictly descending chain of subspaces. Each layer consequently has finite composition length. The finite filtrationproves that itself has finite composition length, and therefore satisfies the ascending chain condition on ideals. Every commutative Artinian ring is Noetherian. The zero ring satisfies the conclusion trivially.
The relevant Artin–Wedderburn theorem says that a semisimple ring which is a right Artinian ring has the formwhere the are division rings and the positive integers and division rings are unique up to permutation and isomorphism. The division rings need not be commutative or finite-dimensional over a field. Conversely every such finite product is semisimple and a right Artinian ring.
Here is a proof which also works if semisimplicity is initially expressed as . A nonzero right ideal contains a minimal nonzero right ideal by the descending chain condition; is a simple module. If , then for every and , , so has inverse . The unit criterion for the Jacobson radical would give , a contradiction. Thus some induces a nonzero map by left multiplication. This map is an isomorphism, since is simple. Choose with . Then and injectivity on gives . We obtain and the splittingFor a right ideal containing , the same argument splits . Repeatedly split a minimal right ideal out of the remaining summand. The remaining summands form a strictly descending chain of right ideals, so the process terminates. Thusfor pairwise nonisomorphic simple modules .
A nonzero map between simple modules is an isomorphism: its kernel and image leave no alternatives. Thus is a division ring, and for . This is the needed Schur lemma. Taking endomorphisms of the direct sum gives . Finally, left multiplication identifies with : a right-module endomorphism sends to , and composition corresponds to multiplication in , not its opposite. This proves the displayed ring isomorphism.
For the converse, the right regular module of is the direct sum of its row modules. Each row module is simple, since elementary matrices and nonzero scalar inverses send any nonzero row to any prescribed row. A finite product therefore has a finite semisimple regular module and is a right Artinian ring. The simple-module multiplicities and their endomorphism division rings recover the factors, establishing uniqueness.
Put , and let be any ideal of this formal power series ring. For define an ideal of byMultiplication by shows . Since is Noetherian, this chain stabilizes at some , and each is finitely generated. For every , choose finitely many series whose degree- coefficients generate .
Given , cancel its degree-zero coefficient using the , then its degree-one coefficient using the , and so on. At a degree , use . Each residual remains in and has zero coefficients below the next cancellation degree. For each of the finitely many chosen , accumulate its multiplier into a formal power series . The higher-degree increments of these multipliers converge coefficientwise. At every degree the cancellation procedure gives the exact coefficient identity, soThus the finitely many lifts generate as an actual ideal. No assumption that is closed has been used. This proves Noetherianity of formal power series rings:Iterating the argument proves the assertion for , which is naturally the iterated formal power series ring.
For a surjective module map , define the adic completion of a module byTake and choose representatives for its components. Compatibility says . Choose with . If , surjectivity gives , so choose with and put . The classes of modulo are compatible and map to the chosen components of . HenceThis surjectivity on adic completions does not require finite generation of or . The compatibility of the lifts is the point; independent lifts of the finite-level classes would not suffice.
Since is Noetherian, write . Define a ring homomorphismModulo , evaluating a series requires only its finitely many terms of total degree below . These evaluations commute with the reduction maps, and define without needing the original ring to be complete or separated.
To prove surjectivity, begin with . Choose matching its component modulo . After terms of total degree below have been chosen, their evaluation differs from at level by a class in . This class is an -linear combination of the monomials with . Choose the corresponding homogeneous degree- polynomial as the next term. Then the series evaluates to at every level. This proves the power-series presentation of an adic completion, and thereforeA quotient of a Noetherian ring is Noetherian, since its ideals correspond to ideals containing the kernel. The cases and give and , respectively, and satisfy the conclusion as well.
A regular element of a ring is an element for which both multiplication maps are injective:It is thus neither a left nor a right zero divisor; it need not be a unit. Here “ideals” means two-sided ideals. Put , and let denote the specified upper triangular ring.
We first establish the additional facts about the Weyl algebra needed below. Its generators satisfyReordering gives a spanning set . These monomials are independent. Indeed, represent the generators by multiplication and differentiation on . In a putative zero operator , choose of maximal total derivative degree. Iterated commutation with multiplication by the coordinates, times in coordinate , gives multiplication by . All other derivative terms of that total degree disappear unless they have exactly the same multiindex, and lower-degree terms disappear. Thus , and descending induction eliminates all coefficients. This proves the ordered monomial basis of a Weyl algebra and faithfulness of its polynomial action.
The Weyl algebra is a simple ring. In a nonzero two-sided ideal choose a nonzero element of least Bernstein filtration degree, where both and have degree one. Commuting it with any generator stays in the ideal and lowers that degree. Minimality therefore makes all these commutators zero. Commutation with every forces all derivative coefficients with to vanish; commutation with every then forces all partial derivatives of the remaining polynomial to vanish. In characteristic zero the element is a nonzero scalar. The ideal consequently contains . This proves simplicity of a Weyl algebra in characteristic zero. Its Jacobson radical is zero, since the radical is a proper two-sided ideal of a nonzero unital simple ring.
Use the two diagonal idempotents to isolate the entries of any ideal of . It must have the formwhere all three entries are two-sided ideals of and . Conversely this condition makes the indicated set an ideal. Simplicity says that each is or , and either nonzero diagonal entry forces . Hence the five ideals of areFor a two-sided ideal of , multiplication on both sides by elementary matrices isolates any entry and moves it to any matrix position. The entries obtained form one two-sided ideal of , and the original ideal is . Thus the only ideals of are and .
Since , lies in the Jacobson radical of : for and , and has inverse . On the other hand, has zero radical, so the image of the radical in this quotient is zero. The elementary unit criterion for the Jacobson radical justifies both assertions. ThereforeThe second equality follows from simplicity of .
We now construct the denominators used to describe regular matrices. A left Noetherian noncommutative domain satisfies the left Ore condition. For if for two nonzero elements, the left ideals have direct sum: in a relation the first summand lies in , all the others in , so it vanishes; cancellation of the final repeats the argument. Their finite partial sums form a strictly ascending chain, contradicting left Noetherianity. Thus , giving common nonzero left multiples and the required Ore equations. The analogous argument with right ideals gives the right Ore condition under right Noetherianity. Both hypotheses for are allowed in the question.
The Ore localization therefore embeds in a division ring . Briefly, its elements are left fractions , with nonzero , and two fractions are identified after passing to a common left denominator. Common multiples supply addition and multiplication, while cancellation in the domain makes the embedding injective. A nonzero fraction has an inverse, obtained by interchanging its numerator and denominator in the appropriate Ore fraction calculation. The right fraction construction gives the same division ring, so finite lists have common left and common right denominators.
A triangular matrix with is invertible over , with inverseIt is consequently regular over . If , then ; if , then . Hence
A full matrix is regular exactly when it is invertible over :One implication follows immediately from invertibility. Conversely, a singular matrix over a division ring has a nonzero right kernel column and a nonzero left kernel row, by row reduction. A common right denominator turns the column into a nonzero column over , providing a right annihilator matrix over . A common left denominator does the same for the row and gives a left annihilator. Thus a singular matrix is not regular. Explicitly, for with , row elimination says that regularity is equivalent to in . If , it is equivalent to both and . A commutative determinant formula must not be substituted here.
Finally both classical left rings of quotients exist, andTo prove this directly, clear a common left denominator from all the finitely many entries of a matrix over . It becomes with in the original triangular or full ring and regular. Every original regular element becomes a unit in the corresponding ring over , by the descriptions above. For regular and in the original ring, write in this way; then , the left Ore condition. Since the denominators are regular, the additional annihilator condition for localization is automatic. This proves the matrix and triangular localization over an Ore domain assertions. In particular, the nonzero nilpotent radical of the triangular ring does not prevent its classical localization; that localization retains the triangular radical.
A precise version of the Hilbert-Serre theorem is as follows. Let be a commutative graded ring, generated over an Artinian degree-zero ring by homogeneous elements of positive degrees . Let be a finitely generated graded module, bounded below. Each component has finite module length over . Its Poincare series of a graded module, or Hilbert series, isWhen is a field, these lengths are dimensions. The theorem assertsFor a nonnegatively graded module the numerator can be taken in . The finite-generation and finite-length hypotheses specify the meaning of the series; they are part of the theorem's statement.
We prove it by induction on . Regard as a finite graded module over , with , acting through the specified generators of . This polynomial ring is Noetherian by the Hilbert basis theorem and Question 1. When , finitely many homogeneous generators over mean that only finitely many components are nonzero, so the series is a Laurent polynomial. For the induction step, put , , and . Both and are finite graded modules; annihilates them, so they are modules over . The finite generation of uses Noetherianity of .
The exact sequence of graded modulesgives, by additivity of component lengths,Here the shift is defined so that . By induction both series on the right have denominator . Dividing by proves the result. The annihilator term cannot be omitted unless multiplication by is injective.
In the standard grading , the coefficients of are . Multiplying by the finite numerator shows that the component dimensions agree with a polynomial for sufficiently large . Cumulative dimensions have generating function and are also eventually polynomial. This consequence supplies the dimension used for Weyl algebra modules.
Use the Bernstein filtration , in which both coordinate generators and differentiation generators have degree one. The ordered monomial basis of a Weyl algebra givesChoose a finite-dimensional generating subspace of a nonzero finitely generated left module and set . This is a good filtration of a module: the symbols of the generators generate its associated graded module over the displayed polynomial ring. The Hilbert-Serre theorem makes an eventual polynomial. Define the Bernstein growth dimension of a Weyl algebra module byThe dimension is independent of the chosen finite generating subspace. Each of two finite generating sets is contained in a fixed filtration step for the other, giving and . Such fixed shifts preserve the degree of growth. The same argument applies to any good Bernstein filtration. This dimension agrees with the Gelfand–Kirillov dimension of a module; one may set .
Let the nonconstant element have Bernstein degree . Since is a domain, the product of two nonzero symbols cannot vanish. HenceRight multiplication by is injective, using the domain property of . Thus the quotient filtration on has cumulative dimensionsThe leading terms of degree cancel, and the leading surviving term isIt is nonzero, because . ThereforeEquivalently the Hilbert series of the associated graded quotient is . Here is Bernstein degree, not differential order: multiplication by has differential order zero but Bernstein degree one. Using the order filtration in this dimension argument would lose the finite-dimensional filtration pieces.
The base ring must be specified in the algebraic definition. For a commutative -algebra , work in and let mean multiplication by . Set and define recursivelyThese are the operators of order at most . The order of a nonzero differential operator relative to a base ring is the least for which it belongs to ; the zero operator can be assigned order . An operator of order zero commutes with all multiplications and is itself multiplication by , so . The union is the ring of finite-order operators, with composition as multiplication. The identityand induction on the sum of orders give . Sums have order at most the maximum of their orders, proving that this union is a ring.
For an arbitrary commutative ring, the absolute version uses , so the ambient endomorphisms are additive. For the polynomial ring in this question, the intended Weyl-algebra identification is the relative one with . Absolute operators would also include nonzero derivations of the coefficient field : a derivation on a rational function field in a transcendence basis over extends to its algebraic closure in characteristic zero, and hence to . Extending it coefficientwise to gives an order-one additive operator which is not complex-linear. Such an operator cannot belong to the complex Weyl algebra. This explains why the linearity convention matters.
Now take . Coordinate multiplication has order zero, and each partial derivative has order one because . They satisfy the defining Weyl algebra relations, giving an algebra homomorphism . Reordering spans by . If an ordered expression acted as zero, commutation with the coordinates according to a maximal derivative multiindex would give multiplication by ; removing the top coefficients successively proves that every coefficient is zero. Thus the homomorphism is injective, as in the ordered monomial basis of a Weyl algebra proof.
For surjectivity, let have order at most , and put . The operations commute, since the coordinate multiplications commute. A product of more than of them kills . Define polynomial coefficientsCommuting through repeatedly gives the finite identityIt follows by induction on from and Pascal's identity. Terms with vanish. Sincefor , we obtain . The monomials are a complex basis of , so complex linearity yields equality of the operators on all of . HenceFor a nonzero ordered expression , its order is exactly . The upper bound follows from composition; the lower bound follows by taking that many coordinate commutators to extract a nonzero multiplication operator. This describes the order filtration of a Weyl algebra:
The associated graded ring is thereforeThe symbol of is . In a product of ordered operators, moving derivatives past coefficients introduces terms of lower differential order. Thus top-order symbols multiply as ordinary polynomials, and the ordered basis proves there are no further relations. In particular , with : the top-order symbols of the two products agree and cancel. Unlike the Bernstein filtration, the order filtration's degree-zero part is the entire polynomial ring and its pieces are infinite-dimensional over .
Form the Rees ring of a filtered algebraThe central element is a non-zero-divisor. This ring is generated by , the , and , withIts quotient modulo is the associated graded ring just computed. Explicitly the degree- component of is , so the degree- quotient is . The quotient modulo recovers .
Since is commutative, any two lifts of symbols have . DefineDivision by is unique because is a non-zero-divisor. If is replaced by , the quotient changes by , which is zero modulo ; changing works the same way. Thus the bracket is well defined. Antisymmetry and bilinearity follow from the commutator. The identity proves the Leibniz rule. For the Jacobi identity, lift each inner bracket by ; the cyclic sum of the outer expressions is the commutator Jacobi identity divided by , hence zero. These verifications prove that the graded polynomial ring is a Poisson algebra. This is the Poisson bracket from a central deformation parameter construction.
The generators give and all coordinate-coordinate and symbol-symbol brackets zero. The Leibniz rule therefore determines the answer on every polynomial:The sign here follows the chosen convention : in particular , rather than . For homogeneous symbols the bracket has order degree , and can equivalently be written .
Here is Witt's lemma with the hypotheses appropriate to the classical groups. Let be finite-dimensional with a nonsingular alternating bilinear form, a nonsingular symmetric bilinear form in characteristic different from two, or a nonsingular Hermitian form with nontrivial involution. Every isometry of a space with a form between vector subspaces extends to a form-preserving automorphism of . For quadratic forms, the same statement holds in every characteristic when the polar bilinear form of a quadratic form is nonsingular and the isometry of a space with a form preserves the quadratic form itself. The restricted forms on may be degenerate. We prove these versions, including the characteristic-two quadratic case needed later.
For an alternating bilinear form , split the restricted space as , where and is nonsingular. Choose a symplectic basis for and a basis of . The nondegenerate form on supplies vectors in with . Adding linear combinations of the to the makes : for each pair one may cancel its pairing by adding an appropriate multiple of to , without disturbing the dual pairings or previously treated pairs. This uses no division by two. Thus together with the pairs is nonsingular and its orthogonal complement for a sesquilinear form has a symplectic basis.
Apply the same construction to , choosing partners there. The two completed bases have identical alternating Gram matrices and equal remaining dimensions. The linear map matching these bases preserves and agrees with on . This proves the alternating version over an arbitrary field, including characteristic two.
For a quadratic form , define its polar bilinear form of a quadratic form by . Its symmetrypreserves . The zero-dimensional case is immediate. Induct on : choose and a hyperplane . Extending first reduces to . Put , , . If , completes the extension. Otherwise . The hyperplanes , are proper because .
For with , set . Thenand fixes and sends to . If no such exists and , the identityforces . The complement of two hyperplanes spans : adding a multiple of any outside vector avoids at most two forbidden scalars. Hence , so , forcing , contrary to .
Over , choose outside both hyperplanes. In the remaining case , and . The explicit maphas , preserves by cancellation of its two cross terms, fixes and sends to . This closes the induction. The characteristic-independent symmetry argument and its binary exceptional step are also treated in Casselman's quadratic-form notes and Elman, Karpenko and Merkurjev, section 8.
In odd characteristic a symmetric bilinear form is recovered by the polarization identity for , so the quadratic proof also proves its extension theorem. For completeness, the Hermitian form case has a similarly explicit induction. Take linear in the first variable, with conjugation . For anisotropic vectors for a form with equal value , let and . When , the rank-one mapsends to and preserves , since and the extra coefficient in isWhen , insert with , , and use two such maps. Such a scalar exists for a nontrivial involution: with works. If the source vector subspace contains an anisotropic vector for a form, align it this way and induct in its nonsingular orthogonal complement for a sesquilinear form.
If instead every source vector is isotropic, the Hermitian polarization identity makes its whole restricted form zero. Choose in its basis and a partner pairing to one with and to zero with the remaining source basis. Make by replacing by , where . The trace map is onto the fixed field: in odd characteristic divide by two; in characteristic two scale a nonzero trace. Choose . The orthogonal vectors and have nonzero values and its negative, so the preceding rank-one construction aligns this entire hyperbolic pair with its target pair. The remaining source basis lies in the pair's orthogonal complement for a sesquilinear form; induction finishes the Hermitian proof.
The hypotheses matter. For example, the identity-matrix symmetric bilinear form on has canonical vector characterized by , so every isometry of a space with a form fixes . The one-dimensional map preserves the restricted bilinear form but cannot extend. Thus “all symmetric forms in characteristic two” is not a correct replacement for the quadratic or alternating versions proved above.
The isomorphic pair is ; is different. All three have order , so order alone does not settle the question; explicitly . We give a concrete realization and an element-order distinction.
On , the Pfaffian isIt is a nonsingular plus-type quadratic form: the three displayed pairs give a hyperbolic decomposition. Change of basis multiplies the Pfaffian by the determinant, which is always one in . Hence the exterior-square realization of PSL4 over F2 embeds into . The kernel of a group homomorphism is trivial: an element acting trivially on the exterior square fixes every decomposable two-space, then every one-space as an intersection of two-spaces, and hence is a scalar; over this scalar is one.
For a second model let be the even-weight vector subspace of and quotient by the all-one vector. The dot product descends to a nondegenerate alternating bilinear form on the six-dimensional quotient, andis well defined, since complementing an even subset changes half its weight from to . It has zero vectors, so is plus type. Coordinate permutations give a faithful action: fixing the quotient fixes each weight-two subset, because its complement has weight six, and fixing all two-subsets forces the identity permutation.
From the independently derived symplectic order and quadratic orbit count below,Thus and the image of is its index-two subgroup . The index-two subgroup is unique: a nontrivial group homomorphism sends every transposition to the same nonidentity element and is the sign map.
To separate , observe that contains of order 15. An odd-order projective element of lifts to a semisimple linear operator, since its order upstairs divides three times an odd order in characteristic two. The possible eigenspace degree patterns are , and . In the split case all eigenvalues have order dividing three, so the projective element has no order 15. In the case the eigenvalues are with ; its fifth power is scalar because , so its projective order divides five. In the irreducible case the determinant-one torus has order and quotienting its scalar subgroup of order three gives projective order dividing seven. There is therefore no element of order 15 in .
Several small-parameter coincidences connect the finite classical groups to permutation groups. The projective-line action immediately gives , , and by faithful actions of degrees three, four and five and their orders. Also : its involutions have Klein-four centralizers, giving five Sylow subgroups; their conjugation action is faithful and embeds its order-60 simple group into . Simplicity here can be checked from class sizes : no proper nontrivial normal class union has order dividing 60. The same five-subgroup action extends to , with trivial kernel of a group homomorphism and order 120, giving . Indeed its kernel intersects trivially, so centralizes that normal subgroup. Commuting projectively with both upper and lower elementary unipotents forces a representing matrix to be scalar, so this kernel is trivial.
The less immediate coincidence can be exhibited on the ten unordered triple partitions used in Question 4. Let , , , assign to and to , and label the other partitions by applying to the zero partition, with and . Inspection of these nine partitions givesTranslations and inversion generate : conjugating the upper unitriangular matrices by inversion gives the lower ones, and elementary elimination generates . Their projective action has order . These partition permutations come from even permutations of six letters, whose partition action is faithful as proved below; hence they fill .
Finally, on the even-weight module of modulo its all-one vector, coordinate permutations preserve a nondegenerate alternating bilinear form in dimension four and act faithfully, again by the weight-two-subset argument. Both and have order 720, proving , with commutator subgroup . These examples illustrate both the need to quotient group centers and the low-rank exceptions to general simplicity. They do not make equal orders sufficient for group isomorphism, as the two order-20160 examples already demonstrate.
Let be a nondegenerate alternating bilinear form on of dimension over . A symplectic basis has and all and pairings zero. Such bases are built by choosing a nonzero , finding with , and continuing in their nonsingular orthogonal complement for a sesquilinear form. In these coordinates the group preserving isIts action on symplectic bases is regular. There are choices for and for , so induction gives the finite symplectic group orderThe center of a group consists of with , and has order . To see there are no other central elements, a central element commutes with every symplectic transvection and hence fixes every symplectic transvection center line; a linear map fixing every line is scalar. Consequently the projective symplectic group over a finite field has this order divided by .
Here is a proof of the main ingredients in simplicity. The symplectic transvectionpreserves , has inverse , and fixes pointwise. These transformations generate . Indeed if , then sends to . If the pairing is zero, choose an intermediate vector having nonzero pairing with both, so two symplectic transvections suffice. This aligns the first vector of any symplectic basis. For partners of the same , their difference lies in . If a symplectic transvection centered at aligns them and fixes . If it is zero and the partners differ, pairs nontrivially with both and still pairs to one with ; two such symplectic transvections work. After fixing the pair, induction in its orthogonal complement for a sesquilinear form aligns the rest of the basis.
The projective action on one-spaces is faithful. For , a line stabilizer has three orbits: the line itself, the other lines perpendicular to it, and the lines not perpendicular to it. Witt's lemma proves transitivity within the latter two orbits by matching the two-dimensional restricted form. This action is primitive. A block containing distinct perpendicular lines is invariant under both stabilizers and therefore contains a line perpendicular to but not to . A block containing distinct nonperpendicular lines likewise contains a line perpendicular to but not to , by using the stabilizer. Such lines exist by nonsingularity in dimension at least four. Either possibility makes the block contain both nontrivial stabilizer orbits, hence every line. For the action on the projective line is two-transitive and thus primitive.
Symplectic transvections with one fixed center line form an Abelian normal subgroup of its stabilizer, and their conjugates generate the whole group. The Iwasawa simplicity lemma now reduces simplicity to being perfect. Its short proof is useful: any nontrivial normal subgroup of a faithful primitive group is transitive, since its orbits are blocks. Writing , where is a point stabilizer, shows that all conjugates of the specified Abelian subgroup have the same image modulo . Thus is Abelian. If is perfect, .
The groups can also be shown to be perfect concretely. For choose with and let scale by and by . Thenso every symplectic transvection is a group commutator. For , symplectic transvections of coefficient one are conjugate, have order three, and the four with centers in a two-dimensional totally isotropic subspace multiply to the identity. They commute, and the sum of their rank-one terms is zero modulo three. Their common class in the abelianization is therefore annihilated by both three and four, hence is zero. For , use the seven nonzero vectors of a three-dimensional totally isotropic subspace. The symplectic transvections commute and their product is the identity, because each diagonal coefficient occurs four times and each cross coefficient twice. Their common abelianized class is annihilated by two and seven, hence is zero. Generation now proves these groups are perfect.
It follows thatThe exceptions are , and respectively. For odd the full symplectic group over a finite field has nontrivial center of a group, so simplicity refers to its quotient group; for even the center of a group is trivial.
A symplectic parabolic subgroup stabilizes a flag of totally isotropic subspaces. The maximal such parabolic subgroups stabilize a single -space, . In an adapted basis their Levi subgroup is , with an arbitrary block of parameters and a remaining symmetric block of parameters. ThusThese are the single-member flag stabilizers, equivalently the standard maximal parabolic subgroups obtained by omitting one node of the symplectic Dynkin diagram. Two particular cases have transparent descriptions.
For the symplectic point stabilizer, write . Its unipotent radical consists ofAll pairings are preserved by direct substitution. The product law is , so this radical has order . With group commutator convention , its commutator has central parameter : it is Heisenberg-type in odd characteristic, but Abelian in characteristic two. A Levi subgroup scales inversely and acts as , givingThis index counts the one-spaces, all of which are isotropic for an alternating bilinear form.
For a Lagrangian subspace , the symplectic Lagrangian stabilizer has block formSubstituting into proves both the inverse-transpose lower block and symmetry of . The unipotent radical is the additive group of symmetric matrices, and acts by . ThereforeThe last identity follows by canceling -powers and factors in the two order formulas; it counts maximal totally isotropic subspaces.
For the degree-ten partition action of S6, take unordered partitions of six letters into two triples. There are . Fix . Its stabilizer is , permuting each triple and interchanging them. The subgroup generated by a 3-cycle in each triple has order nine, so is a Sylow subgroup of . Any normalizer preserves its two three-point orbits; conversely all the indicated within-triple permutations and the swap normalize it. This proves the asserted normalizer exactly.
For any different partition , is one or two after excluding the identical partition. Interchanging and identifies these two possibilities. The stabilizer of is transitive on each fixed intersection pattern, hence on all other nine partitions. The degree-ten action is two-transitive. It is also faithful: two distinct partitions have a common refinement with two singleton cells and two cells of size two. Every unordered pair of letters occurs as those singleton cells. A permutation fixing every partition therefore fixes every pair and consequently every letter.
For the subgroup factorization from coset transitivity, use cosets (right cosets) and right multiplication by . The orbit of is precisely . This is every coset if and only if every can be written , provingA natural fixing one letter is transitive on the ten partitions: the triple containing the fixed letter is determined by any two of the other five. Taking , gives ; inversion gives the requested order as well,
Now let be the binary nondegenerate alternating bilinear form. Its binary quadratic refinements form an affine space: the difference of two such forms is linear, so for a fixed every one is uniquelyIn a symplectic basis each refinement isA two-dimensional summand with admits a basis of singular vectors paired to one and is hyperbolic; the summand is anisotropic. Two planes spanned by anisotropic vectors for a form together become two hyperbolic planes of a quadratic form: with anisotropic basis pairs , the singular vectors pair to one; their orthogonal complement for a sesquilinear form has singular paired basis . Consequently every refinement is equivalent to either hyperbolic planes of a quadratic form or hyperbolic planes of a quadratic form and one anisotropic plane (all three nonzero vectors are anisotropic vectors for a form).
These two types are different. Indeed the character sum of each plane is or , soThus there are exactly two symplectic orbits , the signs denoting . Counting the three coefficient pairs with product zero and the one with product one givesThe same character sum gives the corresponding numbers of singular vectors, including zero, in a fixed form of either type.
Fix a form of type . Completing the square by showsThe stabilizer of is exactly . It sends the parameter by its natural linear action or inverse action according to the chosen left/right convention. Other forms of the same type correspond to nonzero singular vectors , and all forms of opposite type correspond to nonsingular vectors . For two nonzero vectors of the same value, the map between their spans is an isometry of a space with a form. Witt's lemma extends it, so the orthogonal stabilizer is transitive on each of these two vector sets. This proves the two-transitive binary quadratic-form actions: the symplectic group over a finite field is transitive on each type and its point stabilizer is transitive on all other members of that type.
In particular is transitive on the plus orbit. Identify that orbit with the cosets (right cosets) of a plus stabilizer, using as a right action. The coset criterion then provesBoth genuine two-transitive actions require . At the plus orbit has three forms and the minus orbit is a singleton; transitivity and the factorization remain true, while two-transitive action on the singleton is only vacuous if one's convention permits degree one. No special simplicity assertion is needed for this argument. At the orbit sizes are ten and six, linking these actions with and the partition action above.
For the Johnson graph, an edge exchanges one member of a -set. Along one edge, intersection size with a fixed target can increase by at most one, so any path in a graph from to has length at least . Replacing the elements of successively by elements of gives a path in a graph attaining that bound. Hence the distance in a Johnson graph isIf two ordered pairs have the same distance , their four regions (intersection, first-only, second-only and outside the union) have sizes . Choose bijections between corresponding regions. Their union is a ground-set permutation sending the ordered pair to the other pair and preserving graph adjacency. The symmetric group is distance-transitive. For the graph diameter is .
For the Grassmann graph, a codimension-one exchange changes intersection dimension with a fixed target by at most one. More explicitly, if are adjacent, their common -space shows , and exchanging the two gives the reverse bound. Thus distance is at least .
Choose a basis of , complement it in by , and in by . These combined vectors are independent because . The spacesform a path in a graph of length . ConsequentlyEqual-distance ordered pairs have the same dimensions in this adapted basis construction. Extend both combined bases to bases of , and match them by a invertible linear map. It maps the first ordered pair to the second and preserves dimensions of intersections, hence graph adjacency. is distance-transitive, over an arbitrary field, with graph diameter under .
For the symplectic dual polar graph, vertices are Lagrangian -spaces. Let have dimension . The quotient is a nonsingular symplectic vector space of dimension , and are complementary Lagrangian subspaces. Their mutual pairing is nonsingular: a vector orthogonal to both lies in , so vanishes in the quotient. Choose dual bases in and in , and lift them into . Their span is a nonsingular symplectic -space. Complete it by a basis of and suitable dual partners. This gives the pair normal formThe spaces remain totally isotropic subspace: a present pairs only with the absent . They give an adjacent-step path in a graph of length . The previous intersection-dimension lower bound still applies, provingFor two ordered pairs at the same distance, match their adapted symplectic bases. The resulting map preserves the alternating bilinear form and sends the pairs to each other, so lies in . Equivalently, construct the isometry of a space with a form on from the displayed normal form and extend it by Witt's lemma. The action of the symplectic group over a field is distance-transitive, over every field, and its graph has graph diameter . The zero-dimensional boundary cases give a single vertex and trivial transitivity.
Use the homotopy lifting theorem for a covering map: a homotopy of paths has a unique lift once its initial path is lifted. Also use uniqueness of lifts to a covering space: a lift of a constant path with a specified starting point is constant.
Let be a loop based at whose image under is trivial. There is a homotopy from to the constant loop at , fixing both endpoints. Lift this homotopy with initial path . Both vertical boundary paths are constant lifts at . Its final path is a lift of the constant loop and hence is also constant at . Thus the lifted homotopy contracts relative to its endpoints. The kernel of the induced group homomorphism is trivial, provingNo universal-cover assumption is needed for this injection; it holds for any actual covering map.
For the classical subgroup-covering construction, assume is path-connected, locally path-connected, and semilocally simply connected. These are the usual hypotheses underlying the classification of connected covering spaces; an arbitrary space, as literally allowed by the wording, need not admit every subgroup covering.
Construct the path-class construction of a subgroup covering directly. Consider paths starting at , and identify when they have the same endpoint and the loop class belongs to . The subgroup properties make this an equivalence relation. Let be its set of classes and define .
Choose a path-connected open neighbourhood of whose loops become null-homotopic in . Such neighbourhoods form a local basis under the stated local hypotheses. Define a sheetFor each point of the resulting class is independent of the chosen path , since the difference is a loop in , conjugated by , and is trivial in . Thus maps this sheet bijectively onto . Give the topology generated by these sheets. Restrictions to smaller such neighbourhoods show that the sheets form a basis and that their endpoint maps are homeomorphisms. Two sheets over that intersect coincide, by concatenating and reversing paths within ; otherwise they are disjoint. Therefore is a disjoint union of copies of , and is a covering map.
The basepoint is the class of the constant path. The path lifts to its successive prefix classes, giving a path from this basepoint to ; hence is path-connected. A loop lifts closed exactly when its final prefix class agrees with the constant class, namely when . Consequently . Part (i) supplies injectivity, so
The missing local hypothesis is substantive. In the Hawaiian earring, every neighbourhood of the common basepoint contains a whole sufficiently small circle. Its loop is nontrivial in the whole space, since retracting onto that circle preserves it. An evenly covered neighbourhood would lift that loop to a closed loop in one sheet, so the image subgroup of any covering contains a nontrivial element. Therefore the trivial subgroup cannot be realized by a simply connected covering of this space. The intended result is valid under the local covering-space hypotheses above, not for every topological space.
Let be the free group on a set . Form the rose , a topological graph with one vertex and one oriented loop for each generator. Reading edge labels identifies with : cancellation of an edge followed by its reverse is exactly free reduction. This also applies to an infinite generating set, using the graph's CW topology rather than an accumulation topology.
Apply the subgroup-covering construction to obtain a connected covering graph with . Choose a spanning tree and a base vertex . For every edge , choose one orientation and form the loop consisting of the unique tree path from to the initial vertex of , the edge , and the unique tree path back from its terminal vertex.
These loops generate . Indeed, in any edge loop insert the tree paths to and from the base vertex between consecutive edges. A tree edge contributes a contractible loop; a non-tree edge contributes the chosen loop or its inverse. They are freely independent as well: reducing an edge path cancels backtracking, and, after suppressing the tree portions, a nonempty freely reduced word in the oriented non-tree edges cannot disappear. Equivalently, collapsing the tree gives a rose whose petals are precisely the non-tree edges, and the same edge-path reduction identifies its fundamental group with the free group on those petals.
Thus is free, and its isomorphism with proves the Nielsen–Schreier theorem:The non-tree edges may be infinite in number; the argument does not require to have finite index or be finitely generated.
A quasi-isometry has constants , such thatfor all , and every is within of some point of . One may use a separate coarse-surjectivity constant and enlarge to include it. No continuity is required.
Choose with . The triangle inequality givesCombining this with the distortion inequalities for yieldsAlso , so the lower distortion inequality gives . Hence every point of is within of the image of . Taking the larger common error constant shows that is a quasi-isometry. It is a quasi-inverse of a quasi-isometry; both composites are uniformly close to their respective identities.
For a finite generating set , use the symmetric alphabet . The Cayley graph has a vertex for each and an oriented edge labelled from to . Give every edge length one. Its vertex word metric isTwo finitely presented groups are quasi-isometric when their Cayley graphs, with these path metrics, are quasi-isometric. The choice of finite generating set is immaterial, as the following proof shows; the relators identify vertices but do not otherwise enter the metric definition.
Given finite generating sets of the same group, put and . Replace each letter in a shortest -word by a fixed -word to obtain . Reversing the roles gives . Therefore the vertex identity map satisfiesIt is onto, and hence a quasi-isometry. Map each edge to the fixed word path for its label, or pass through the uniformly dense vertex sets, to obtain the corresponding graph quasi-isometry with a bounded additive error. This proves equivalence of finite word metrics and independence of the two finite group presentations.
Choose representatives of the right cosets , including , and let . This is finite because the index is finite. For and , let represent . The elementsform a finite generating set for , after adjoining inverses and discarding identities. To see generation rather than merely quote Schreier's lemma, write and let represent . Then andEach factor is a Schreier generator. For a shortest -word this gives . Conversely every Schreier generator has -length at most , so . Hence the inclusion obeysEvery can be written , and . Thus the inclusion is coarsely onto and is a finite-index subgroup quasi-isometry.
Only finite generation of was needed for the metric argument. Under the given finite-presentation hypothesis, is also finitely presented: the corresponding finite-sheeted cover of a finite presentation complex has finitely many cells, and a spanning-tree reduction of its one-skeleton gives a finite group presentation. Therefore it belongs to the class of groups used in part (ii).
An algorithm is a finite effective procedure on finitely encoded inputs; a Turing machine is one precise model. A decision algorithm must halt on every permitted input and answer correctly. An algorithmic problem specifies the input encoding and the required output; enumerating positive answers alone is not a decision algorithm.
For a fixed finite group presentation , the word problem for a group takes a finite word in and asks whether it represents the identity. Equality of two represented elements is equivalent to testing . Positive answers are recursively enumerable: enumerate finite products of conjugates of relators and their inverses, freely reduce them, and compare with the input. Equivalently enumerate finite labelled disc diagrams. The van Kampen lemma ensures that every null word eventually appears. For a non-null word this search continues forever. Solvability requires a procedure that also terminates with a negative answer.
For a null word , define its area as the least number of conjugates of defining relators or their inverses whose product is in the free group. By the van Kampen lemma, this is also its minimum number of relator faces in a disc diagram. The Dehn function isThe maximum is finite because there are finitely many words of bounded length. An isoperimetric function of a group presentation is a nondecreasing upper bound on . Here subrecursive means bounded above by a total computable function, not merely recursively enumerable.
Suppose with computable. Let be the maximum relator length, taking even if there are no relators. A minimum-area diagram for a boundary word of length , with at most faces, can be chosen with no unnecessary tree branches. Every remaining edge occurs on a face boundary or the outside boundary, so there are at most edges. Thus only finitely many combinatorial planar diagrams of area at most and this edge bound exist. Their finite edge labels and face labels can be enumerated, and the planar contractible diagram topology (allowing boundary spurs and pinched vertices), relator face boundaries and outside boundary word can be checked by finite combinatorial operations.
For the input , compute and inspect all these diagrams. Answer yes if one has boundary , and no otherwise. The diagram bound and van Kampen lemma prove correctness, including the negative answer. This finite search avoids the invalid attempt to bound area while allowing unbounded conjugating words.
Conversely, suppose a word problem decider is available. For each , enumerate the finitely many words of length at most and use the decider to identify exactly the null words. For each such word search diagrams in increasing area, with the finite edge bound just given at each area. The search terminates, and the first successful area is its minimum area. Taking the maximum of these finitely many minima computes . This proves the recursive area bounds and the word problem equivalence:In fact, for finite group presentations, a word decider computes the minimal Dehn function itself.
The required quasi-isometry is the identity on the group vertices. For each choose a fixed -word representing it and map an -edge to that word path. The bounded substitutions in Q2(ii) prove the distortion inequalities.
For the area comparison, choose a reverse substitution sending each to an -word. Let bound the lengths of . Every word for a defining relator is null over the first group presentation. Since there are finitely many such words, their areas have a common bound . Similarly every generator correction has area bounded by a constant ; include inverses in this bound.
Let be null over with length at most . Its substituted word has length at most and a diagram of area at most . Replace each -edge by its -path. Each original relator face can then be filled over using at most faces, so has area at most . Attach the correction strips changing its letters back to those of , at cost at most . ThereforeThe reverse substitutions give the corresponding inequality for . Enlarging the constants to the single constant in the paper's comparison proves . This is Dehn functions under a change of finite presentation.
Two qualifications are necessary for the printed continuation. The invariant is the optimal isoperimetric function, namely the Dehn function, not arbitrary upper bounds. For example, the relator-free group presentation of has zero area on all null words, so both and are isoperimetric upper bounds for that same group presentation; they are not equivalent under .
Also, the comparison supplies no recursive bound unless one was available beforehand. Its actual consequence, by part (ii), isThe unconditional assertion that every finitely presented group has a solvable word problem is false. Finitely presented counterexamples are established in the primary paper The Word Problem. Thus the missing solvability premise cannot be inferred from group presentation equivalence alone.
Work with a finite symmetric alphabet . If , its path starts at , visits at integer time , travels at unit speed along the intervening generator edges, and stays at its endpoint for .
Two such paths synchronously -fellow travel ifAn asynchronous version permits increasing time reparametrizations. Checking all integer times suffices after a bounded enlargement of for the edge interiors.
A combing of a group chooses a representative word for every , with empty. A synchronous combing has a uniform constant such that representatives with adjacent endpoints satisfy the synchronous fellow-traveller property. A group admitting this is a synchronous combable group. The formal language need not be regular or computable. A regular language of representatives satisfying the synchronous condition instead gives an automatic group. This distinction is relevant to the finite-state automata request in part (iii); the present argument uses the synchronous meaning throughout. The definitions and distinction are also made explicitly in Combings of Groups and the Grammar of Reparameterization, Section 1.
Take an integer bounding synchronous distances at integer times. Let be all words over of length at most that represent the identity in . This is a finite set. We claim that presents , interpreting inverse letters in the usual way.
To prove it, let be any null word and let , with . Draw the combing paths as vertical columns, completed paths being padded by stationary steps. At each integer height join consecutive columns by a rung labelled by a word of length at most representing their displacement. At the bottom choose empty rungs, and at a common final height choose the actual boundary letters as rungs.
Every elementary strip cell has two rungs of length at most and two vertical steps of length at most one. Its boundary word has length at most and is null in , because the four paths close in the actual Cayley graph. It is therefore a relator in . Gluing all cells fills the top loop : the bottom row and the two copies of the identity column collapse to the basepoint. Thus every null word is a product of conjugates of these finitely many short relators. The reverse containment holds because each relator is already an identity in .
Hence the finite presentation from a synchronous combing provesThis is an existence proof of a finite relator set. It does not assume an algorithm for identifying identities in an arbitrary group presentation before establishing decidability.
Articles were limited to the first 100 out of 1749 total.
Articles by others on the same topic
There are currently no matching articles.