User anton klyachko - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T08:53:23Z http://mathoverflow.net/feeds/user/24165 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/126780/the-sum-of-same-powers-of-all-matrices-modulo-p The sum of same powers of all matrices modulo p Anton Klyachko 2013-04-07T15:14:56Z 2013-04-09T17:24:26Z <p>The following is a problem from our department algebra competition for students:</p> <blockquote> <p><strong>Non-question.</strong> An experimental-math geek was trying to raise all matrices $17\times17$ over the field with 17 elements to the power of 100, sum the returns, and observe the result, when his computer broke. Help him.</p> </blockquote> <p>Probably, the most of us can calculate the sum without use of computer (alternatively, Russian readers can find a solution <a href="http://halgebra.math.msu.su/Olympiad/2007/" rel="nofollow">here</a>). The problem seems to become much harder when we replace 100 by, say, 80. More generally, my question is the following:</p> <blockquote> <p><strong>Question.</strong> What is the sum $$\sum_{A\in M_p(\mathbb F_p)}A^k,$$ where $p$ is prime and $k$ is a multiple of $p-1$?</p> </blockquote> <p>It is easy to show that the sum is a scalar matrix, but which one? Note that the coincidence of the matrix size and the characteristic makes trace useless.</p> http://mathoverflow.net/questions/122065/an-element-g-in-a-group-such-that-neither-g1-nor-g-ne-1-can-be-proved/125996#125996 Answer by Anton Klyachko for An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved. Anton Klyachko 2013-03-30T11:13:48Z 2013-04-01T10:01:12Z <p>The following is an abridged translation of a philosophical digression from my <a href="http://halgebra.math.msu.su/staff/klyachko/lect22.pdf" rel="nofollow">lectures on Group Theory</a> (in Russian).</p> <hr> <p><strong>Metatheorem 3.5.1.</strong> For any finite (group) presentation $G$ with non-solvable word problem, there exists a word $w$ (called <em>bad</em>) such that it is possible to prove neither that $w=1$ in $G$ nor that $w\ne 1$ in $G$.</p> <p><strong>Proof.</strong> Note that any reasonable definition of the notion of <em>proof</em> has the following property:</p> <p><em>Any proof can be written in some fixed formal language; and there exists an algorithm VERIFICATION, which takes as input any text in this language and any assertion (also written in this language) and says whether or not the given text is a proof of the given assertion.</em></p> <p>Suppose now that there are no bad words for a given presentation. Then it is easy to construct an algorithm solving the word problem: for any input word $v$, we simply search all texts and feed them to the algorithm VERIFICATION until we find a text which is either a proof that $v=1$ in $G$ or a proof that $v\ne1$ in $G$.</p> <p><strong>Remark.</strong> Any word equal to a bad word in the group $G$ is bad itself (because for any two words equal in $G$, their equality can always be proven).</p> <p>So, we can speak about <em>bad elements</em> of a group (not only bad words). Moreover, it is easy to show that the badness of an element $g\in G$ does not depend on the choice of finite presentation of $G$.</p> <p>As a corollary, we obtain the following strange-looking fact.</p> <p><strong>Metatheorem 3.5.2.</strong> Any bad word is, actually, not equal to 1.</p> <p>(Because 1 is not a bad element, obviously.)</p> <p>Although bad words exist, no particular example can be constructed.</p> <p><strong>Metatheorem 3.5.3.</strong> For any bad element, it is impossible to prove that this element is bad.</p> <p><strong>Proof.</strong> Indeed, a proof of the badness of an element $g$ would prove, in particular, that $g\ne1$ (by Metatheorem 3.5.2) that contradicts the definition of a bad element.</p> <hr> <p>A similar argument and the Adyan$-$Rabin theorem show that:</p> <ul> <li><p>There exists a <em>bad group</em>, i.e. a finitely presented group such that it is possible to prove neither that this group is trivial nor that this group is non-trivial.</p></li> <li><p>Each bad group is non-trivial.</p></li> <li><p>For any bad group, it is impossible to prove that this group is bad.</p></li> </ul> http://mathoverflow.net/questions/93257/number-of-relations-and-free-subgroups/126085#126085 Answer by Anton Klyachko for Number of relations and free subgroups Anton Klyachko 2013-03-31T09:00:09Z 2013-03-31T09:00:09Z <p>Another way to prove that $f(n)=n-2$ works is to recall Romanovskii's Freiheitssatz:</p> <blockquote> <p>In any finitely presented group<br> $$G=⟨x_1,…,x_n∣r_1,…,r_k⟩,$$ some $n-k$ of {$x_i$} freely generate a free subgroup of $G$ (if $n\ge k$).</p> </blockquote> <p>See</p> <p>N.S. Romanovskii, "Free subgroups of finitely presented groups" Algebra i Logika , 16 (1977) pp. 88–97 (In Russian).</p> http://mathoverflow.net/questions/94084/groups-where-every-two-generator-subgroup-is-free/126080#126080 Answer by Anton Klyachko for Groups where every two generator subgroup is free Anton Klyachko 2013-03-31T07:55:02Z 2013-03-31T07:55:02Z <p>There is a widely used term <em>binary finite</em> (<em>бинарно конечная</em>, in Russian) group, see papers of Shunkov, Chernikov and their school. This means a group where all 2-generated subgruops are finite.</p> <p>For instance, the <a href="http://math.nsc.ru/~alglog/17kt.pdf" rel="nofollow"><em>Kourovka Notebook</em></a> contains the following question (still open, as far as I know).</p> <p><strong>Question 4.74(b)</strong> (V.P.Shunkov, 1973). Does there exist a simple infinite binary finite 2-group?</p> <p>Also, I stumbled across <em>binary solvable</em> and <em>binary nilpotent</em> groups... As you can guess, I am hinting that you may call your groups <strong>binary free</strong> if you like this terminology.</p> http://mathoverflow.net/questions/116362/polynomial-maps-between-noncommutative-groups/116393#116393 Answer by Anton Klyachko for Polynomial maps between noncommutative groups Anton Klyachko 2012-12-14T19:47:50Z 2012-12-15T08:35:17Z <p>See <a href="http://mi.mathnet.ru/eng/mz240" rel="nofollow">a paper of Anokhin</a>. He considered only the case where $H$ is abelian (and $G$ is arbitrary) and his definition of degree is slightly different. For instance, he says that the degree of $f$ is at most one if $$f(x)-f(xy)+f(xyz)-f(xz)=0$$ for all $x,y,z\in G$ (see Lemma 2).</p> <p>In that paper, it was proved, e.g., that</p> <p><i> all functions from a nontrivial group $G$ to a nontrivial abelian group $H$ are polynomial iff, for some prime $p$, $G$ is a finite $p$-group and $H$ is an abelian $p$-group </i> (Theorem 2). </p> http://mathoverflow.net/questions/115574/ascending-chain-condition-on-ideals-of-free-products/116093#116093 Answer by Anton Klyachko for Ascending chain condition on ideals of free products Anton Klyachko 2012-12-11T15:14:39Z 2012-12-11T15:14:39Z <p>You do not need to know small-cancellation thery. Take your favorite finitely generated but non-finitely presented group $$\langle x_1,\dots,x_n\;|\;w_1=1,w_2=1,\dots\rangle.$$ Then $A*F(x_1,\dots,x_n)$ has an ascending chain of `ideals' $$\langle\langle w_1\rangle\rangle \subset \langle\langle w_1,w_2\rangle\rangle \subset \dots.$$ Here, $\langle\langle\dots\rangle\rangle$ means the normal closure in $A*F(x_1,\dots,x_n)$.</p> <p>The group $A$ plays no role here.</p> http://mathoverflow.net/questions/110373/sylow-theorems-for-infinite-groups/110377#110377 Answer by Anton Klyachko for Sylow theorems for infinite groups Anton Klyachko 2012-10-23T00:44:09Z 2012-10-23T00:44:09Z <p>You may also read Chapter 13 of <a href="http://books.google.ru/books/about/Theory_of_Groups.html?id=B3lHYIuqPuQC&amp;redir_esc=y" rel="nofollow">Kurosh's book</a>. For instance, it contains a proof of Baer's theorem (cited by @Igor) which says that </p> <p><strong>all p-Sylow subgroups of a locally normal group are isomorphic.</strong></p> <p><em>Locally normal</em> means periodic with finite conjugacy classes.</p> http://mathoverflow.net/questions/109027/applications-of-frobenius-theorem-and-conjecture/109078#109078 Answer by Anton Klyachko for Applications of Frobenius theorem and conjecture Anton Klyachko 2012-10-07T16:28:34Z 2012-10-07T16:28:34Z <p>P. Hall's paper <i><a href="http://plms.oxfordjournals.org/content/s2-40/1/468.full.pdf" rel="nofollow">On a theorem of Frobenius</a></i> contains a generalisation of the Frobenius theorem and some applications of this result. For example, he obtained the following Sylow-like theorem.</p> <p><b> THEOREM 4.6. </b> If $p$ is an odd prime, and if the $p$-Sylow subgroups of $G$ are of order $p^l$ and not cyclical, then, for $0 &lt; k &lt; l$, the total number of subgroups of order $p^k$ in $G$ is congruent to $1+p\pmod {p^2}$.</p> http://mathoverflow.net/questions/108719/if-each-strict-subgroup-of-g-is-free-must-g-be-free-or-cyclic-of-prime-order/108721#108721 Answer by Anton Klyachko for If each strict subgroup of G is free, must G be free or cyclic of prime order ? Anton Klyachko 2012-10-03T16:48:36Z 2012-10-04T09:30:52Z <p>No. There is a variation of Tarski monster: a nonabelian group whose each proper nontrivial subgroup is infinite cyclic, see <a href="http://books.google.ru/books?hl=en&amp;lr=&amp;id=jwNkqFQn-GcC&amp;oi=fnd&amp;pg=PR5&amp;dq=olshanskii+geometry+of+defining&amp;ots=XQQkt5vng4&amp;sig=jNhR97XokHHkZU_qaDboCH6EbDc&amp;redir_esc=y#v=onepage&amp;q&amp;f=false" rel="nofollow">the book of Olshanskii</a>.</p> <p>Concerning Misha's comment. For any countable family of countable involution-free groups $G_1,G_2,\dots$, there is a group $H$ containing all $G_i$ as proper subgroups such that each proper subgroup of $H$ is either infinite cyclic or a conjugate of a subgroup of some $G_i$. This is <a href="http://www.mathnet.ru/php/archive.phtml?wshow=paper&amp;jrnid=sm&amp;paperid=2990&amp;option_lang=eng" rel="nofollow">Obraztsov's embedding theorem</a>.</p> http://mathoverflow.net/questions/107895/vanishing-sums-of-powers-modulo-n Vanishing sums of powers modulo n Anton Klyachko 2012-09-23T10:12:52Z 2012-09-23T10:18:40Z <p>Is it possible to describe all positive integer sequences ${x_i}$ such that $$\sum_i x_i=n \quad \hbox{and} \quad \sum_i x_i^k\equiv 0\pmod n \quad \hbox{for all k (and a given n)?}$$</p> <h2>Background</h2> <p>We say that two elements of a group belong to the same <em>tribe</em> if their squares are equal. Then </p> <p><i> the sum of $k$</i>th <i>powers of tribe sizes is divisible by the order of the group for any positive integer $k$</i> [<a href="http://arxiv.org/abs/1205.2824" rel="nofollow">http://arxiv.org/abs/1205.2824</a>, Example 1].</p> <p>This remains true if we replace squares (in the definition of tribes) with cubes or any other powers.</p> http://mathoverflow.net/questions/98639/the-number-of-group-elements-whose-squares-lie-in-a-given-subgroup The number of group elements whose squares lie in a given subgroup Anton Klyachko 2012-06-02T08:00:32Z 2012-06-04T23:04:49Z <p><b> This number is divisible by the order of the subgroup </b> <a href="http://arxiv.org/abs/1205.2824" rel="nofollow">http://arxiv.org/abs/1205.2824</a>.</p> <p>The proof is short but non-trivial. Is this fact new or is it known for a long time?</p> http://mathoverflow.net/questions/9754/magic-trick-based-on-deep-mathematics/19911#19911 Comment by Anton Klyachko Anton Klyachko 2013-05-12T22:39:12Z 2013-05-12T22:39:12Z The sum of all elements of a finite abelian group is non-zero if and only if the 2-Sylow subgroup of this group is a nontrivial cyclic. http://mathoverflow.net/questions/130274/example-of-a-group-with-unsolvable-word-problem Comment by Anton Klyachko Anton Klyachko 2013-05-12T20:11:53Z 2013-05-12T20:11:53Z The Russian original of Borisov's paper is freely available here: <a href="http://mi.mathnet.ru/eng/mz6959" rel="nofollow">mi.mathnet.ru/eng/mz6959</a> http://mathoverflow.net/questions/127106/elements-of-minimal-length-in-normal-closures-of-elements-in-free-groups Comment by Anton Klyachko Anton Klyachko 2013-04-11T17:42:10Z 2013-04-11T17:42:10Z Thank you, Alexey. I did not know that. http://mathoverflow.net/questions/127106/elements-of-minimal-length-in-normal-closures-of-elements-in-free-groups Comment by Anton Klyachko Anton Klyachko 2013-04-11T10:18:46Z 2013-04-11T10:18:46Z I think there are no good answers. Sometimes there are no non-trivial normal roots, e.g., when $w$ is a proper power (by Newman's theorem); sometimes such normal roots exist, e.g., $[x,y]\in \langle\langle xy^{2013}\rangle\rangle$. http://mathoverflow.net/questions/126780/the-sum-of-same-powers-of-all-matrices-modulo-p/126918#126918 Comment by Anton Klyachko Anton Klyachko 2013-04-11T08:19:52Z 2013-04-11T08:19:52Z Matthieu, the solution goes as follows: Ilya showed that the sum in question vanishes for sufficiently small $k$; then ya-tayr showed that if the sum vanishes for all sufficiently large $k$, than it vanishes always; when these bounds have met, &quot;we're done!&quot;. This is all right, but honestly I hoped for a simpler solution. ---- Thanks, ya-tayr, Ilya, Will, and everybody involved! http://mathoverflow.net/questions/126780/the-sum-of-same-powers-of-all-matrices-modulo-p/126918#126918 Comment by Anton Klyachko Anton Klyachko 2013-04-09T07:01:53Z 2013-04-09T07:01:53Z ... and it is easy to find the LCM of all unitary polynomials of degree $p$. http://mathoverflow.net/questions/126780/the-sum-of-same-powers-of-all-matrices-modulo-p/126918#126918 Comment by Anton Klyachko Anton Klyachko 2013-04-09T06:45:12Z 2013-04-09T06:45:12Z ya-tayr, Ilya, I am not sure I understand. Should &quot;determinant of $A$&quot; read &quot;determinant of $I-Ax$&quot;? If so, there are exactly $p^{p-1}$ different denominators: they are just polynonomials reciprocal to characteristic polynomials of all matrices (= all unitary polynomials of degree $p$). http://mathoverflow.net/questions/126780/the-sum-of-same-powers-of-all-matrices-modulo-p/126804#126804 Comment by Anton Klyachko Anton Klyachko 2013-04-08T09:54:45Z 2013-04-08T09:54:45Z Thanks, Ilya!!! http://mathoverflow.net/questions/126780/the-sum-of-same-powers-of-all-matrices-modulo-p/126803#126803 Comment by Anton Klyachko Anton Klyachko 2013-04-08T09:53:38Z 2013-04-08T09:53:38Z Thanks, Sergey! http://mathoverflow.net/questions/126780/the-sum-of-same-powers-of-all-matrices-modulo-p Comment by Anton Klyachko Anton Klyachko 2013-04-08T09:52:08Z 2013-04-08T09:52:08Z Will, if the size is not a multiple of the characteristic, it suffice to evaluate the sum of traces. because the sum in question is, clearly, a scalar matrix. But I argee that the problem seems non-trivial for any sizes. The case where size $=p$ is just an additional difficulty. http://mathoverflow.net/questions/126499/embedding-a-semigroup-into-a-divisible-semigroup/126518#126518 Comment by Anton Klyachko Anton Klyachko 2013-04-04T14:41:11Z 2013-04-04T14:41:11Z The Russian original of Shutov's paper is freely available: <a href="http://www.mathnet.ru/php/archive.phtml?wshow=paper&amp;jrnid=sm&amp;paperid=4610&amp;option_lang=eng" rel="nofollow">mathnet.ru/php/&hellip;</a> . http://mathoverflow.net/questions/126174/intersection-of-conjugates-of-subgroups-in-free-groups Comment by Anton Klyachko Anton Klyachko 2013-04-01T18:09:19Z 2013-04-01T18:09:19Z Ashot, if you find $g$ such no power of $x$ belongs to $B^g$, then the problem would be solved (just conjugate $B$ by $g$ and then by $x^n$ and the resulting group $B^{gx^n}$ intersects $A$ trivially). So, the problem is as follow: you have two subgroups: cyclic $\langle x\rangle$ and infinite−index f.g. $B$ and have to find an element $g$ such that $\langle x\rangle\cap B^g=1$. This is the same as Fact 1 but with cyclic subgroup instead of $A$. http://mathoverflow.net/questions/126174/intersection-of-conjugates-of-subgroups-in-free-groups Comment by Anton Klyachko Anton Klyachko 2013-04-01T17:33:40Z 2013-04-01T17:33:40Z Ashot, you are right. But this is the only problem. Hence, Fact 1 is reduced to the case where $A=\langle x\rangle$ is cyclic (generated by a letter). Now, once again recall that $B$ is a free factor in a finite-index subgroup. This reduces the situation to the case where $B$ is a free factor of $F$ and $A$ is cyclic (arbitrary). In this case, we have no problems, right? http://mathoverflow.net/questions/126174/intersection-of-conjugates-of-subgroups-in-free-groups Comment by Anton Klyachko Anton Klyachko 2013-04-01T16:32:34Z 2013-04-01T16:32:34Z If $A$ is a free factor, i.e. $A$ is generated by some letters (after a change of basis), then it is easy to conjugate $B$ so that all elements of $B^f$ would start and end with a letter not belonging to $A$. (You can take $f=x^n$, where $x$ is a letter not lying in $A$ and $n$ is an integer large enough with respect to the Schreier basis of $B$.) http://mathoverflow.net/questions/126174/intersection-of-conjugates-of-subgroups-in-free-groups Comment by Anton Klyachko Anton Klyachko 2013-04-01T15:24:23Z 2013-04-01T15:24:23Z If you like to avoid mentioning graphs, you may recall that any f.g. subgroup is just a free factor of a finite-index subgroup. This reduces the problem to the case where $A$ is a free factor of $F$...