User benjamin steinberg - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T04:13:42Z http://mathoverflow.net/feeds/user/15934 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36623/finitely-generated-monoids-are-finitely-presented/131214#131214 Answer by Benjamin Steinberg for Finitely generated monoids are finitely presented? Benjamin Steinberg 2013-05-20T12:21:32Z 2013-05-20T12:21:32Z <p>The answer is no if the OP means all relations should be consequences of the relations of the form w=1 with 1 the identity. Let S be the multiplicative monoid of the two-element field. If F is a free commutative monoid with generators A and if F maps onto S via f, then if we set B to be the generators mapping to 1 under f, we have a word represents the identity iff it is a product of letters from B. But if I add all such relations I will get as the quotient a free commutative monoid on A-B not S. </p> http://mathoverflow.net/questions/131110/what-are-the-main-structure-theorems-on-finitely-generated-commutative-monoids/131205#131205 Answer by Benjamin Steinberg for What are the main structure theorems on finitely generated commutative monoids? Benjamin Steinberg 2013-05-20T10:30:44Z 2013-05-20T10:30:44Z <p>The comments are getting a bit long so I'll put this as a partial answer. The case of von Neumann regular commutative semigroups was handled by Clifford in the 1940s. A semigroup is von Neumann regular if for all $a$, there exists $b$ with $aba=a$. Clifford proved a regular commutative semigroup is the same thing as a pair (E,F) where E is a poset with binary meets and F is a presheaf of abelian groups on E. If the semigroup is a finitely generated monoid then E will be a finite lattice. </p> <p>For example, given such a pair, the underlying set of the semigroup is the disjoint union of the F(e) with e in E (so the arrow set of the associated discrete fibration). The product of a in F(e) with b in F(e') is obtained by restricting both elements to the meet of e and e' and taking their product. </p> <p>The more general semilattice decompositions in the comments are not as good as this. </p> http://mathoverflow.net/questions/131042/random-walk-on-the-hypercube/131043#131043 Answer by Benjamin Steinberg for Random walk on the hypercube Benjamin Steinberg 2013-05-18T12:39:40Z 2013-05-18T12:39:40Z <p>The better thing to do is use the Fourier transform for $(Z/2)^n$, which will diagonalize the transition matrix, take powers then do the inverse Fourier transform. See the lecture notes of Diaconis for details <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.lnms/1215467407" rel="nofollow">http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.lnms/1215467407</a>. </p> http://mathoverflow.net/questions/130731/transformation-terminology-question/130741#130741 Answer by Benjamin Steinberg for Transformation terminology question Benjamin Steinberg 2013-05-15T17:06:56Z 2013-05-15T17:06:56Z <p>This question seems a bit ill-posed to me. There are two possible interpretations here.</p> <p>(1) If $s$ is an element of a finite semigroup, then $s^i=s^{i+p}$ where there is a minimal such $i$ and $p$. What is the common terminology for $i,p$? </p> <p>The "official" terminology is that $i$ is the index and $p$ is the period. Or one might call the elements $\lbrace s,..,s^{i-1}\rbrace$ the nilpotent part and $\lbrace s^i,..,s^{i+p-1}\rbrace$ the maximal subgroup or minimal ideal. </p> <p>This in any event has nothing to do with transformations.</p> <p>(2) You are interested in the analogue of cycle decomposition for a transformation. In this case, the situation is more complicated than a stem and cycle. </p> <p>The transformation $f$ has a set of recurrent points (also called the eventual image) on which $f$ acts like a permutation and hence decomposes into cycles. There may be several of them. Attached to each cycle are some number of trees which are directed toward the cycle. There is a only a stem followed by a cycle if there is a point from which every other point can be reached. The terminology is not so standard for this setup. I think there is a good chapter in Peter Higgins book Techniques of semigroups on this sort of thing.</p> http://mathoverflow.net/questions/129145/resolutions-chain-homotopic-to-projective-ones Resolutions chain homotopic to projective ones Benjamin Steinberg 2013-04-29T20:47:46Z 2013-05-14T02:22:00Z <p><strong>Motivation.</strong> In my research I have a situation where a monoid $M$ is acting by nice cellular maps on a contractible cell complex and so the augmented chain complex is a resolution of the trivial module over $\mathbb ZM$. Now I can show by a somewhat messy argument that this resolution is projective. I have a much smoother proof that the augmented chain complex of the barycentric subdivision is a projective resolution. These two chain complexes are chain homotopy equivalent as chain complexes of $\mathbb ZM$-modules by the naturality of the chain homtopy equivalence between the augmented cellular chain complexes of a regular cell complex and its barycentric subdivision. In a hope to avoid the messy computation I naively ask the following question. </p> <blockquote> <blockquote> <p><strong>Question.</strong> If $R$ is a unital ring and $M$ is an $R$-module, what can be said about a resolution of $M$ which is chain homotopy equivalent to a projective resolution of $M$? Is there any chance it to must be projective?</p> </blockquote> </blockquote> http://mathoverflow.net/questions/129647/unbounded-metrics-on-groups/129674#129674 Answer by Benjamin Steinberg for Unbounded metrics on groups Benjamin Steinberg 2013-05-04T19:52:08Z 2013-05-04T19:52:08Z <p>The answer is no. See Thm 1.2 of <a href="http://homepages.math.uic.edu/~rosendal/PapersWebsite/Property(OB)10.pdf" rel="nofollow">http://homepages.math.uic.edu/~rosendal/PapersWebsite/Property(OB)10.pdf</a>. There is a property discussed in the intro of this paper which is equivalent to all left invariant metrics are bounded. It is known that certain large permutation groups have this property. </p> http://mathoverflow.net/questions/127045/fixed-point-theorems/128884#128884 Answer by Benjamin Steinberg for Fixed point theorems Benjamin Steinberg 2013-04-27T03:14:31Z 2013-04-27T03:14:31Z <p>There is the Bruhat-Tits theorem that a group acting by isometries on a CAT(0) space with a bounded orbit has a fixed point. This is often applied to compact subgroups of grous acting on Euclidean buildings. </p> http://mathoverflow.net/questions/107391/applications-of-idempotent-ultrafilters Applications of idempotent ultrafilters Benjamin Steinberg 2012-09-17T15:16:58Z 2013-04-26T17:36:28Z <p>Recently Justin Moore has posted a solution to the amenability of Thompson's group F. A key(?) step exploits the existence of idempotent ultrafilters on $\mathbb N$ to construct an idempotent measure on the free non-associative semigroup on one-generator. </p> <p>Previously the main applications I knew of idempotent ultrafilters involved Ramsey theory, most specifically Hindman's theorem. </p> <blockquote> <blockquote> <p><strong>Question:</strong> What are other applications of idempotent ultrafilters?</p> </blockquote> </blockquote> <p>I have made this a big-list CW question, although a big list would pleasantly surprise me. </p> http://mathoverflow.net/questions/128592/algebras-with-finite-essential-arity/128633#128633 Answer by Benjamin Steinberg for Algebras with finite essential arity Benjamin Steinberg 2013-04-24T16:38:40Z 2013-04-25T14:28:53Z <p><strong>Summary</strong></p> <blockquote> <blockquote> <p>There are semigroups of finite essentially arity which are not strongly abelian. This follows from my original answer and a result I cite in the addition below that I have not read in detail.</p> </blockquote> </blockquote> <p><strong>Added.</strong> Here is a self-contained answer. Take the semigroup $S=\langle x\mid x^3=x^4\rangle$. Then consider the term $t(x_1,x_2)=x_1x_2$. One has $t(x,x^3)=x^3=t(x^2,x^3)$ but $t(x,x)=x^2\neq x^3=t(x^2,x)$. So $S$ is not strongly abelian. But the essential arity of $S$ is $3$ since the value of any word of length $\geq 3$ in $S$ is $x^3$. </p> <hr> <p><strong>Original Answer</strong></p> <p>A finite semigroup $S$ has finite essential arity iff it is locally trivial, that is, $eSe=e$ for all idempotents $e\in S$. </p> <p>Pf. First suppose that $S$ is not locally trivial. The either $S$ contains a subsemigroup isomorphic to the 2-element semilattice $\lbrace 0,1\rbrace$ with multiplication or it contains a non-trivial group $G$ as a subsemigroup. </p> <p>In the first case, the variety generated by $S$ contains the free semilattice on any set (i.e. the power set under union with singletons as free generators) and so the term function given by a word on m-letters depends on all those letters. If $S$ contains a non-trivial group $G$, then it contains a cyclic group of prime order $p$ and hence vector spaces over $\mathbb F_p$. But then again the term function depending on any word in m-letters depends on all letters by considering a vector space of dimension m.</p> <p>So finite essential arity implies locally trivial.</p> <p>Conversely, if $S$ is locally trivial, then it is known that $S$ satisfies an identity of the form $$x_1\cdots x_myz_1\cdots z_n = x_1\cdots x_mz_1\cdots z_n$$ and so any term operation coming from a word depends only on at most $m+n$ variables (the prefix of length $m$ and the suffix of length $n$).</p> <p>In particular, no non-trivial monoid has finite essential arity.</p> <hr> <p><strong>Added.</strong> If I understood correctly the results of Stepanova, A. A.(RS-FARE-IMC); Trikashnaya, N. V.(RS-FARE-IMC) Abelian and Hamiltonian varieties of groupoids, Algebra Logic 50 (2011), no. 3, 272–278 then a locally trivial semigroup is strongly abelian iff it is an inflation of a rectangular band. Most locally trivial semigroups are not inflations of a rectangular band. If $S$ is an inflation of a rectangular band, then $S^2=S^3$. But if one takes the semigroup $\langle x\mid x^3=x^4\rangle$, then it is locally trivial (hence essentially finite arity) but it is not strongly abelian.</p> http://mathoverflow.net/questions/127102/integral-leray-number Integral Leray Number? Benjamin Steinberg 2013-04-10T15:39:26Z 2013-04-10T15:39:26Z <p>The Leray number of a finite simplicial complex $K$ relative to a field $\Bbbk$ is defined to be the least $d\geq 0$ such that $\widetilde H^n(C,\Bbbk)=0$ for all $n\geq d$ and all induced subcomplexes $C$ of $K$.</p> <p>The Leray number is the Castelnuovo-Mumford regularity of the Stanley-Reisner ring of $K$ with base field $\Bbbk$ and is also relevant to Helly problems in combinatorial geometry.</p> <blockquote> <blockquote> <p><b>Question.</b> Do people consider the Leray number with respect to arbitrary commutative rings (defined analogously), and in particular, with respect to $\mathbb Z$? Does it still have meaning with respect to Castelnuovo-Mumford regularity and Helly theorems?</p> </blockquote> </blockquote> http://mathoverflow.net/questions/126747/ibn-for-algebraic-theories/126748#126748 Answer by Benjamin Steinberg for IBN for algebraic theories Benjamin Steinberg 2013-04-07T01:51:38Z 2013-04-07T02:09:29Z <p>I believe the answer to C is yes. By Stone duality $\beta X$ and $\beta Y$ are homomorphic if and ony if $2^X\cong 2^Y$ as Boolean algebras. But $2^X$ has the singletons as the atoms so you can recover $X$ up to bijection. </p> <p>Alternatively, the points of X are the only clopen points of $\beta X$. </p> <p>For B, the free Jonsson-Tarski algebra on any non-empty finite set is the same. </p> http://mathoverflow.net/questions/126499/embedding-a-semigroup-into-a-divisible-semigroup/126518#126518 Answer by Benjamin Steinberg for Embedding a semigroup into a divisible semigroup Benjamin Steinberg 2013-04-04T13:54:48Z 2013-04-04T14:00:34Z <p>I believe from what I saw in a survey article that Šutov, È. G. Embeddings of semigroups into simple and complete semigroups Mat. Sb. (N.S.) 62 (104) 1963 496–511 proves every semigroup embeds in a semigroup which is both congruence-free and divisible. I don't have access to the journal and don't know if an English translation exists. </p> <p>Neumann, B. H. Some remarks on semigroup presentations. Canad. J. Math. 19 1967 1018–1026. Shows how to embed in a divisible semigroup by adjoining roots of elements. </p> http://mathoverflow.net/questions/126106/are-there-any-nontrivial-ring-homomorphisms-m-n1r-rightarrow-m-nr/126137#126137 Answer by Benjamin Steinberg for Are there any nontrivial ring homomorphisms $M_{n+1}(R)\rightarrow M_n(R)$? Benjamin Steinberg 2013-03-31T22:30:05Z 2013-04-01T11:39:23Z <p>If $R$ is a local ring, possibly non-commutative, then there is no non-trivial homomorphism. Let $B_k$ be the semigroup of $k\times k$-matrix units and $0$. It is well known every proper homomorphic image of $B_k$ collapses all elements. So if $M_{n+1}(R)\to M_n(R)$ is nontrivial it must not collapse $B_{n+1}$ (since $B_{n+1}$ spans $M_{n+1}(R)$). But then $B_{n+1}$ embeds in $End(R^n)$ as a semigroup with zero. So $End(R^n)$ contains $n+1$ orthogonal idempotents. But this implies $R^n$ is a direct sum of at least $n+1$ non-zero projective modules. But projective is free for local rings and local rings have invariant basis number. This is a contradiction. </p> <p><strong>Added.</strong> This argument works as long as R has the invariant basis number property for finitely generated free modules and finitely generated projective $R$-modules are free. In particular it applies to free algebras and firs (free ideal rings) if memory serves. </p> http://mathoverflow.net/questions/125231/a-property-of-periodic-words/125269#125269 Answer by Benjamin Steinberg for A property of periodic words Benjamin Steinberg 2013-03-22T13:04:15Z 2013-03-22T13:38:39Z <p>As you observe, we may assume that $p'$ is empty, i.e., that $v$ starts with a power of $u$. If $p$ is not a multiple of $u$, then writing $u$ as a circular word, it means you can find two district places in the circle where you can read $u$. So $u=xy=yx$ for some $x,y$ (namely if $|p|$ is $r$ mod $|u|$ take $x$ to be the suffix of $p$ of length $r$ and $y$ the prefix of $v$ of length $|u|-r$). But then x,y are powers of a common element and hence u is not primitive. </p> http://mathoverflow.net/questions/94579/is-choice-needed-to-establish-the-existence-of-idempotent-ultrafilters Is choice needed to establish the existence of idempotent ultrafilters? Benjamin Steinberg 2012-04-19T23:36:30Z 2013-03-13T12:48:48Z <p>It is well known that the Stone–Čech compactification $\beta \mathbb N^+$ of the positive natural numbers has the structure of a compact left semitopological semigroup and hence, by Ellis's lemma, has idempotents. The usual proof of Ellis's lemma uses Zorn's lemma. Idempotent ultrafilters are clearly non-principal. It is known that the existence of non-principal ultrafilters is weaker than the axiom of choice. </p> <p>My question is whether the existence of idempotent ultrafilters in $\beta \mathbb N^+$ is still weaker than choice?</p> http://mathoverflow.net/questions/123894/is-every-topological-resp-lie-group-the-isometrygroup-of-a-metric-space-resp/123939#123939 Answer by Benjamin Steinberg for Is every topological (resp. Lie-) group the isometrygroup of a metric space (resp. Riemannian manifold)? Benjamin Steinberg 2013-03-08T03:31:38Z 2013-03-10T13:53:54Z <p>This seems to be completely answered in the topological category by Thm 1.4 of <a href="http://arxiv.org/pdf/1202.3368v3.pdf" rel="nofollow">http://arxiv.org/pdf/1202.3368v3.pdf</a>. </p> <p><strong>Edit</strong></p> <p>If X is a topological space which is not Dieudonne complete (meaning its topology cannot be given by a complete uniformity), then it seems theorem 7.24 of <a href="http://books.google.com/books?id=v3_PVdvJek4C&amp;pg=PA35&amp;lpg=PA35&amp;dq=free+topological+group+dieudonne+complete&amp;source=bl&amp;ots=QIt0C2TCjN&amp;sig=d4BJjO2h3zM4jDLoTzijrDVYt3w&amp;hl=en&amp;sa=X&amp;ei=VIw8UeuBJpO30QHek4C4AQ&amp;ved=0CC4Q6AEwAA" rel="nofollow">http://books.google.com/books?id=v3_PVdvJek4C&amp;pg=PA35&amp;lpg=PA35&amp;dq=free+topological+group+dieudonne+complete&amp;source=bl&amp;ots=QIt0C2TCjN&amp;sig=d4BJjO2h3zM4jDLoTzijrDVYt3w&amp;hl=en&amp;sa=X&amp;ei=VIw8UeuBJpO30QHek4C4AQ&amp;ved=0CC4Q6AEwAA</a> and Thm 1.4 of the paper above shows that the free topological group on X is not the isometry group of a metric space. Googling shows completely regular spaces exist which are not Dieudonne. </p> <p>I believe that any polish group or locally compact group is an isometry group of a metric space by the paper I linked. </p> <p>Also the author of the first paper has shown that every Lie group is the isometry group of another Lie group with respect to some proper metric. <a href="http://arxiv.org/pdf/1201.5675v2.pdf" rel="nofollow">http://arxiv.org/pdf/1201.5675v2.pdf</a></p> http://mathoverflow.net/questions/124025/idempotents-in-compact-semigroups/124041#124041 Answer by Benjamin Steinberg for Idempotents in compact semigroups Benjamin Steinberg 2013-03-09T02:55:01Z 2013-03-09T02:55:01Z <p>Let me supplement Boris's answer since the result you ask for is easier than the result Boris cites.</p> <p>Let $T$ be a (nonempty) semigroup. Then an easy exercise is the following: $T$ is a group iff $tT=T=Tt$ for all $t\in T$.</p> <p>Suppose now that $S$ is a compact semigroup. Then by Zorn's lemma and compactness it contains a minimal closed subsemigroup $T$. By minimality and continuity of multiplication $tT=T=Tt$ for all $t\in T$ and hence $T$ is a group. Thus $T$ has an idempotents (its identity) and so $S$ has an idempotent.</p> <p>Suppose now that $S$ is a compact monoid containing no idempotent apart from its identity. If $s\in S$, then $sS$ and $Ss$ are compact semigroups and so contain an idempotent which must be $1$ by assumption on $S$. It follows that $s$ is invertible. Thus $S$ is a group. In fact, it is easy to see that the inverse operation is then forced to be continuous and so $S$ is a compact group. </p> http://mathoverflow.net/questions/123681/invertibility-of-a-certain-matrix-indexed-by-the-hamming-cube/123699#123699 Answer by Benjamin Steinberg for Invertibility of a certain matrix indexed by the Hamming cube Benjamin Steinberg 2013-03-06T03:28:47Z 2013-03-06T04:26:03Z <p>The argument of Kim and Roush looks as follows after translating out the semigroup theory (and is essentially using a Mobius inversion idea).</p> <p>Let $T\colon \mathbb Z^S\to \mathbb Z^S$ be the group homomorphism corresponding to left multiplication by $A$. We show that in appropriate bases for the domain and codomain the matrix of $T$ is triangular with 1s on the diagonal and hence $A$ is invertible over $\mathbb Z$. Let $e_X$ be the unit vector corresponding to a non-empty subset $X$ of $F$. Put $e_{\emptyset}=0$ for convenience. Let $b_X=e_F-e_{X^c}$ where $X^c$ is the complement of $X$. Notice that $b_F=e_F$ and hence the $b_X$ form a basis for $\mathbb Z^S$. </p> <p>Now one computes $$Ab_X=A(e_F-e_{X^c})=\sum_{Y\subseteq X} e_Y.$$ If we use the $b_X$ with $X\in S$ as a basis for the domain of $T$, the $e_X$ with $X\in S$ as a basis for the codomain and total order $S$ by a topological sorting of $\subseteq$ then the matrix for $T$ with respect to these bases is triangular with 1s on the diagonal. Thus $A$ is invertible over $\mathbb Z$.</p> http://mathoverflow.net/questions/123135/modern-developments-in-finite-dimensional-linear-algebra/123151#123151 Answer by Benjamin Steinberg for Modern developments in finite-dimensional linear algebra Benjamin Steinberg 2013-02-27T21:53:39Z 2013-02-28T23:48:34Z <p>I would say the theory of quivers and in particular Gabriel's theorem on finite representation type and its extensions to tame type. Representations of quivers are essentially linear algebra problems in a different language. For instance Jordan canonical form is the description of indecomposable reps of a quiver with one vertex and a loop. In general things like the classification of two endomorphisms of vector spaces, matrix pencils and the n-subspace problem are all problems in the rep theory of quivers. The intro to the book of Gabriel-Roiter says more. </p> <p><strong>Added.</strong> A quiver is a directed multigraph, often assumed finite in this context. A representation of a quiver Q is an assignment of a vector space to each vertex and a linear transformation to each edge from the vector space at its source to the vector space if its target. Isomorphisms are isomorphisms of vertex spaces making commuting squares with the edge linear transformations. There is a fairly straightforward notion of direct sum and hence indecomposable rep. Finite rep type means finitely many isoclasses of indecomposables, tame type essentially means indecomposables come in 1-parameter families (plus finitely many exceptions) if you fix the dimensions of the vertex spaces. Wild means its representation theory contains that of all finite dinensional (and hence all finitely generated) algebras. In particular the first order theory is undecidable. Only finite, tame and wild occur. </p> http://mathoverflow.net/questions/123102/how-many-idempotent-relations-are-there-on-an-n-element-set/123103#123103 Answer by Benjamin Steinberg for How many idempotent relations are there on an $n$-element set? Benjamin Steinberg 2013-02-27T13:41:04Z 2013-02-27T14:03:15Z <p>The answer seems to be in Butler, K. K.-H.,The number of idempotents in (0,1)-matrix semigroups, Linear Algebra and Its Applications 5 (1972), 233–246. I will see if I have access to the journal and will tell you more.</p> <p><strong>Edit.</strong> The paper is <a href="http://ac.els-cdn.com/0024379572900055/1-s2.0-0024379572900055-main.pdf?_tid=8eece726-80e4-11e2-9fcb-00000aab0f26&amp;acdnat=1361973171_ff59deefabd771cffb05e77de54d3a1e" rel="nofollow">here</a> for free. It counts the idempotents by D-class so it is not written down in a simple succinct formula. If you google idempotent boolean matrix there are further papers which may be of use.</p> http://mathoverflow.net/questions/122465/strongly-complete-profinite-groups/122475#122475 Answer by Benjamin Steinberg for Strongly Complete Profinite Groups. Benjamin Steinberg 2013-02-20T23:06:23Z 2013-02-20T23:06:23Z <p>The profinite completion is the inverse limit of all quotients by finite index normal subgroups. Any profinite group is the inverse limit of its quotients by open normal subgroups. Since open normal subgroups have finite index a profinite group is strongly complete iff the open normal subgroups are cofinal among finite index notmal subgroups. But this is equivalent to all finite index subgroups are open. </p> http://mathoverflow.net/questions/122217/which-limits-does-group-cohomology-commute-with/122220#122220 Answer by Benjamin Steinberg for Which limits does group cohomology commute with? Benjamin Steinberg 2013-02-18T19:34:04Z 2013-02-18T19:34:04Z <p>Ken Brown shows in <a href="http://www.math.cornell.edu/~kbrown/scan/1975.0050.pdf" rel="nofollow">http://www.math.cornell.edu/~kbrown/scan/1975.0050.pdf</a> that group cohomology for a group G commutes with direct limits iff G is of type $FP_\infty$. That is the trivial module $\mathbb Z$ has a projective $\mathbb ZG$ resolution which is finitely generated in each degree. </p> http://mathoverflow.net/questions/122065/an-element-g-in-a-group-such-that-neither-g1-nor-g-ne-1-can-be-proved/122080#122080 Answer by Benjamin Steinberg for An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved. Benjamin Steinberg 2013-02-17T16:46:33Z 2013-02-17T17:49:24Z <p>For the adjusted question, take a group G with generators $x_n$ and relations $x_n=1$ if the statement with Gödel number n is provable. (This is recursively presented because you can enumerate all proofs.) Higman embed G into an fp group H. Take a Gödel number m of a statement which is true but not provable (exists by incompleteness). We cannot give a finite proof that $x_m\neq 1$ in H. </p> <p><strong>edit</strong> Following Joel's kind suggestion I should use Rosser sentences instead of Gödel sentences to be independent of the background meta theory.</p> http://mathoverflow.net/questions/121717/number-of-idempotent-n-times-n-matrices-over-mathbbz-m/121743#121743 Answer by Benjamin Steinberg for Number of idempotent $n\times n$ matrices over $\mathbb{Z}_m$ ? Benjamin Steinberg 2013-02-13T21:52:06Z 2013-02-15T13:20:51Z <p>I think it can be found the following way. If R is a commutative local ring then every idempotent matrix is <strike>equivalent</strike> conjugate to a diagonal idempotent $\begin{pmatrix} I_r &amp; 0\cr 0 &amp;0\end{pmatrix}$ . The point is projective is free for local rings. This lets you write $R^n$ as a direct sum of the image and the kernel, both of which are free. </p> <p>So now one has to just compute the size of the stabilizer of the standard rank r diagonal idempotent under the conjugation action of GL(R) for $R=Z_{p^{k}}$. </p> <p><strong>Added.</strong> I believe the stabilizer of the rank r idempotent for a local ring is GL(R,r)xGL(R,n-r)$like in the field case and so a formula is easily found. </p> <p><strong>Added.</strong> I compute the answer for nxn matrices over$Z_{p^k}$to be $$\sum_{r=0}^n \frac{p^{2r(n-r)(k-1)}|Gl(n,p)|}{|Gl(r,p)|Gl(n-r,p)|}.$$ Here I use a matrix is invertible over a local ring iff it is over the residue field. The orders of the Gl(m,p) are of course well known. </p> http://mathoverflow.net/questions/121739/free-product-of-categories/121740#121740 Answer by Benjamin Steinberg for Free product of categories Benjamin Steinberg 2013-02-13T20:58:32Z 2013-02-13T20:58:32Z <p>Probably you want to look at pushouts of categories along a common set of objects. For example, the free product of monoids is the pushout along the inclusion of the identity. Such things and their word problem can be foud in PJ Higgins notes on <a href="http://www.tac.mta.ca/tac/reprints/articles/7/tr7.pdf" rel="nofollow">Categories and Groupoids</a>. He uses it to prove Nielsen-Schreier and the Kurosh theorem. </p> http://mathoverflow.net/questions/121638/does-every-commutative-monoid-admit-a-translation-invariant-measure/121708#121708 Answer by Benjamin Steinberg for Does every commutative monoid admit a translation-invariant measure? Benjamin Steinberg 2013-02-13T12:29:44Z 2013-02-13T13:03:45Z <p>I think the integers Z with max is a counterexample. First note the set$I_n$of all integers bigger than or equal to n is open. Thus each singleton is Borel by looking at$I_n\setminus I_{n+1}$. Hence by countability of Z the measure is a weighted counting measure. But the inverse image of n under translation by n consists of all numbers less than or equal to n. Thus the weight of n is the weight of n plus the weights of all numbers less than n. Thus the weights of all numbers strictly less than n are zero. Since n is arbitrary all elements have weight 0. </p> http://mathoverflow.net/questions/121178/primes-occurring-as-orders-of-elements-of-a-finitely-presented-group/121267#121267 Answer by Benjamin Steinberg for Primes occurring as orders of elements of a finitely presented group Benjamin Steinberg 2013-02-09T04:08:20Z 2013-02-09T15:56:55Z <p>This should be a comment to HW's answer but it is too long. I believe that the correct theorem is that a collection P of primes is the set of prime orders of the finite order elements of a finitely presented group iff there is an re set U, a computable function$f\colon U\to Primes$and r.e. sets L,K contained in U such that$P=f(L-K)$. I don't know if such a set of primes must be a difference of r.e. sets (which is HW's) answer. </p> <p>Here is the proof. Suppose first that we have a finitely presented group. Then U will be all pairs (u,p) where u is a word over the generators and their inverses and p is a prime, f is the projection to the second coordinate, L is all pairs (u,p) with$u^p=1$in the group (r.e. by finiteness of the presentation) and K is all pairs (u,p) with u=1 (r.e. for the same reason). Clearly the prime orders of elements of the group is f(L-K). </p> <p>Conversely, given U,L,K,f as above consider the group G with generators U subject to the relations$x^{f(x)}=1$for x in L and$x=1$for x in K. This group has an r.e. set of generators and an r.e. set of relators and hence by the argument of HW can be embedded in a finitely presented group with the same finite orders. Now G is a free product of infinite cyclic groups (one for each element of U not in K or L) and finite cyclic groups of order from f(L-K) (there may be repetitions because f is many to one). </p> <p><b>Edit.</b> I have learned from <a href="http://mathoverflow.net/questions/121268/computable-images-of-differences-of-r-e-sets/121274#121274" rel="nofollow">http://mathoverflow.net/questions/121268/computable-images-of-differences-of-r-e-sets/121274#121274</a> that the sets of the above form are precisely the$\Sigma^0_2$sets of the arithmetic hierarchy and hence much broader than differences of re sets. In his comments to HW's answer François sketches how to construct the analogue of G above directly from a logical formula. </p> http://mathoverflow.net/questions/121268/computable-images-of-differences-of-r-e-sets Computable images of differences of r.e. sets Benjamin Steinberg 2013-02-09T04:20:27Z 2013-02-09T04:58:13Z <p>Suppose f is a computable function from a recursively enumerable set U to the natural numbers and that L,K are r.e. subsets of U. Is f(L-K) a difference of r.e. subsets? The motivation comes from</p> <p><a href="http://mathoverflow.net/questions/121178/primes-occurring-as-orders-of-elements-of-a-finitely-presented-group" rel="nofollow">http://mathoverflow.net/questions/121178/primes-occurring-as-orders-of-elements-of-a-finitely-presented-group</a></p> <p>A positive answer would mean that the theorem proposed in HW's nice answer is 100% correct. Otherwise the$\epsilon$-clarification in my answer is actually needed. </p> http://mathoverflow.net/questions/121200/is-a-variety-of-algebras-a-set/121210#121210 Answer by Benjamin Steinberg for Is a variety of algebras a set? Benjamin Steinberg 2013-02-08T16:07:39Z 2013-02-08T16:07:39Z <p>Summarizing the above, the answer is no. </p> http://mathoverflow.net/questions/121031/why-is-set-and-not-rel-so-ubiquitous-in-mathematics/121034#121034 Answer by Benjamin Steinberg for Why is Set, and not Rel, so ubiquitous in mathematics? Benjamin Steinberg 2013-02-07T01:12:07Z 2013-02-07T01:39:11Z <p>Notion 2 was first considered for groups in Wedderburn, J. H. M. Homomorphism of groups. Ann. of Math. (2) 42, (1941). 486–487. But the main results show for groups the notion is not so exciting. In semigroup theory relations satisfying 2 are called relational morphisms. They form the key notion of morphism in finite semigroup theory. They were introduced by Eilenberg and Tilson in Eilenberg's book on finite semigroup theory. </p> <p>For instance, one can consider which elements of a finite semigroup relate to 1 under all possible relational morphisms to a finite group. The answer is the smallest subsemigroup containing all idempotents and closed under$x\mapsto axb\$ whenever aba=a or bab=b. One proof uses that the product of finitely generated subgroups of a free group is closed in the profinite topology (which was conjectured by semigroup theorists interested in this problem and proved by Ribes and Zalesskii using profinite groups acting on profinite trees). </p> http://mathoverflow.net/questions/36623/finitely-generated-monoids-are-finitely-presented/131177#131177 Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-20T12:22:50Z 2013-05-20T12:22:50Z He is saying that the question was never answered. The question seems to be whether the finite presentation can be made to involve only relations of the form w=1 like for groups. http://mathoverflow.net/questions/131110/what-are-the-main-structure-theorems-on-finitely-generated-commutative-monoids Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-20T11:47:08Z 2013-05-20T11:47:08Z @Yemon, I didn't see your comment the other day. Sorry to duplicate in my comment. http://mathoverflow.net/questions/131110/what-are-the-main-structure-theorems-on-finitely-generated-commutative-monoids Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-19T12:40:40Z 2013-05-19T12:40:40Z Probably not what you are looking for but context-free subsets of commutative monoids are semilinear, so definable in pressburger arithmetic. They have decidable membership by integer programming. In particular integer programming decides membership in submonoids so the generalized word problem is decidable. http://mathoverflow.net/questions/131110/what-are-the-main-structure-theorems-on-finitely-generated-commutative-monoids Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-19T12:27:59Z 2013-05-19T12:27:59Z In fact every commutative semigroup is a semilattice of Archimedean semigroups. The Archimedean components can be strange but if you have some extra conditions they will be cancellative and hence group embeddable. http://mathoverflow.net/questions/131110/what-are-the-main-structure-theorems-on-finitely-generated-commutative-monoids Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-19T12:20:49Z 2013-05-19T12:20:49Z A finite commutative semigroup has a grading by a semilattice such that the homogeneous components are nilpotent extensions of abelian groups. The buzzword is semilattice of Archimedean semigroups. I think Grillet will give the best results on such decompositions. http://mathoverflow.net/questions/131110/what-are-the-main-structure-theorems-on-finitely-generated-commutative-monoids Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-19T12:17:22Z 2013-05-19T12:17:22Z Another big result is that the first order theory is decidable. I can't recall the reference but Mark Sapir knows it. Also finitely generated commutative monoids are residually finite. A lot more is known form numerical and affine semigroups, eg, subsemigroups of N and of Z^m. http://mathoverflow.net/questions/130731/transformation-terminology-question/130741#130741 Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-15T20:02:54Z 2013-05-15T20:02:54Z I am not on cstheory stackexchange. The answer to your question is the directed power graph of the semigroup, or at least <a href="http://groupprops.subwiki.org/wiki/Directed_power_graph_of_a_group" rel="nofollow">groupprops.subwiki.org/wiki/&hellip;</a> says this is the name in group theory for this. I think the undirected version is more commonly studied, see this paper <a href="http://www.sciencedirect.com/science/article/pii/S0012365X10000531" rel="nofollow">sciencedirect.com/science/article/pii/&hellip;</a> by Peter Cameron et al. http://mathoverflow.net/questions/130731/transformation-terminology-question/130741#130741 Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-15T19:58:06Z 2013-05-15T19:58:06Z @Chad, it seems then that it is the cycle/stem in the semigroup you are interested in. The situation I refer to in 2 is s=[1,2,1,2]. Then on the level on {0,1,2,3} one has s cycles {1,2} and has two branches 0-&gt;1 and 2&lt;-3. But on the semigroup it is still index 2, period 2. http://mathoverflow.net/questions/130745/grothendieck-fibrations-and-classifying-spaces Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-15T19:03:06Z 2013-05-15T19:03:06Z I'm totally not an expert on this, so I may be saying nonsense but doesn't one have by a result of Thomason that BD is homotopy equivalent to a homotopy colinit of the classify spaces of these groupoids induced by the action of C, or something like that? http://mathoverflow.net/questions/130401/simple-automorphism-groups-of-field-extensions-of-infinite-transcendence-degree/130412#130412 Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-12T14:16:32Z 2013-05-12T14:16:32Z I didn't carefully read the proof because it is too set-theoretic for me. But given the transfinite nature I'd be surprised if it has finite transcendence degree. http://mathoverflow.net/questions/130210/let-r-be-a-ring-and-e-e-idempotents Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-09T23:41:56Z 2013-05-09T23:41:56Z @Yemon, I agree that we have seen the question for. But the old version has long ago been deleted. http://mathoverflow.net/questions/129647/unbounded-metrics-on-groups/129674#129674 Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-04T21:15:32Z 2013-05-04T21:15:32Z Thanks Yves. I realized only the intro talks about this but I didn't have a link to Bergman's paper. http://mathoverflow.net/questions/129652/actions-of-thompson-group-f Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-04T19:39:29Z 2013-05-04T19:39:29Z <a href="http://arxiv.org/abs/1105.4017" rel="nofollow">arxiv.org/abs/1105.4017</a> might be relevant. http://mathoverflow.net/questions/129548/group-set-with-1-op-field-with-2-ops-with-3-ops Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-03T16:50:57Z 2013-05-03T16:50:57Z Rings have an associated lie bracket but I assume you don't count this because it is a derived operation. http://mathoverflow.net/questions/129377/is-it-possible-to-write-quasiprojective-and-quasifinite-without-a Comment by Benjamin Steinberg Benjamin Steinberg 2013-05-02T18:16:39Z 2013-05-02T18:16:39Z I vaguely seem to remember reading that British English tends to maintain hyphens and American English to drop them.