User anton klyachko - MathOverflow

The sum of same powers of all matrices modulo p

2013-04-07T15:14:56Z

The following is a problem from our department algebra competition for students:

Non-question. 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.

Probably, the most of us can calculate the sum without use of computer (alternatively, Russian readers can find a solution here). The problem seems to become much harder when we replace 100 by, say, 80. More generally, my question is the following:

Question. 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$?

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.

Answer by Anton Klyachko for An element $g$ in a group such that neither $g=1$ nor $g\ne 1$ can be proved.

2013-03-30T11:13:48Z

The following is an abridged translation of a philosophical digression from my lectures on Group Theory (in Russian).

Metatheorem 3.5.1. For any finite (group) presentation $G$ with non-solvable word problem, there exists a word $w$ (called bad) such that it is possible to prove neither that $w=1$ in $G$ nor that $w\ne 1$ in $G$.

Proof. Note that any reasonable definition of the notion of proof has the following property:

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.

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$.

Remark. 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).

So, we can speak about bad elements 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$.

As a corollary, we obtain the following strange-looking fact.

Metatheorem 3.5.2. Any bad word is, actually, not equal to 1.

(Because 1 is not a bad element, obviously.)

Although bad words exist, no particular example can be constructed.

Metatheorem 3.5.3. For any bad element, it is impossible to prove that this element is bad.

Proof. 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.

A similar argument and the Adyan$-$Rabin theorem show that:

There exists a bad group, 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.
Each bad group is non-trivial.
For any bad group, it is impossible to prove that this group is bad.

Answer by Anton Klyachko for Number of relations and free subgroups

2013-03-31T09:00:09Z

Another way to prove that $f(n)=n-2$ works is to recall Romanovskii's Freiheitssatz:

In any finitely presented group
$$ 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$).

See

N.S. Romanovskii, "Free subgroups of finitely presented groups" Algebra i Logika , 16 (1977) pp. 88–97 (In Russian).

Answer by Anton Klyachko for Groups where every two generator subgroup is free

2013-03-31T07:55:02Z

There is a widely used term binary finite (бинарно конечная, in Russian) group, see papers of Shunkov, Chernikov and their school. This means a group where all 2-generated subgruops are finite.

For instance, the Kourovka Notebook contains the following question (still open, as far as I know).

Question 4.74(b) (V.P.Shunkov, 1973). Does there exist a simple infinite binary finite 2-group?

Also, I stumbled across binary solvable and binary nilpotent groups... As you can guess, I am hinting that you may call your groups binary free if you like this terminology.

Answer by Anton Klyachko for Polynomial maps between noncommutative groups

2012-12-14T19:47:50Z

See a paper of Anokhin. 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).

In that paper, it was proved, e.g., that

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 (Theorem 2).

Answer by Anton Klyachko for Ascending chain condition on ideals of free products

2012-12-11T15:14:39Z

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)$.

The group $A$ plays no role here.

Answer by Anton Klyachko for Sylow theorems for infinite groups

2012-10-23T00:44:09Z

You may also read Chapter 13 of Kurosh's book. For instance, it contains a proof of Baer's theorem (cited by @Igor) which says that

all p-Sylow subgroups of a locally normal group are isomorphic.

Locally normal means periodic with finite conjugacy classes.

Answer by Anton Klyachko for Applications of Frobenius theorem and conjecture

2012-10-07T16:28:34Z

P. Hall's paper On a theorem of Frobenius contains a generalisation of the Frobenius theorem and some applications of this result. For example, he obtained the following Sylow-like theorem.

THEOREM 4.6. 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 < k < l$, the total number of subgroups of order $p^k$ in $G$ is congruent to $1+p\pmod {p^2}$.

Answer by Anton Klyachko for If each strict subgroup of G is free, must G be free or cyclic of prime order ?

2012-10-03T16:48:36Z

No. There is a variation of Tarski monster: a nonabelian group whose each proper nontrivial subgroup is infinite cyclic, see the book of Olshanskii.

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 Obraztsov's embedding theorem.

Vanishing sums of powers modulo n

2012-09-23T10:12:52Z

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$)?} $$

Background

We say that two elements of a group belong to the same tribe if their squares are equal. Then

the sum of $k$th powers of tribe sizes is divisible by the order of the group for any positive integer $k$ [http://arxiv.org/abs/1205.2824, Example 1].

This remains true if we replace squares (in the definition of tribes) with cubes or any other powers.

The number of group elements whose squares lie in a given subgroup

2012-06-02T08:00:32Z

This number is divisible by the order of the subgroup http://arxiv.org/abs/1205.2824.

The proof is short but non-trivial. Is this fact new or is it known for a long time?

Comment by Anton Klyachko

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.

Comment by Anton Klyachko

2013-05-12T20:11:53Z

The Russian original of Borisov's paper is freely available here: mi.mathnet.ru/eng/mz6959

Comment by Anton Klyachko

2013-04-11T17:42:10Z

Thank you, Alexey. I did not know that.

Comment by Anton Klyachko

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$.

Comment by Anton Klyachko

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, "we're done!". This is all right, but honestly I hoped for a simpler solution. ---- Thanks, ya-tayr, Ilya, Will, and everybody involved!

Comment by Anton Klyachko

2013-04-09T07:01:53Z

... and it is easy to find the LCM of all unitary polynomials of degree $p$.

Comment by Anton Klyachko

2013-04-09T06:45:12Z

ya-tayr, Ilya, I am not sure I understand. Should "determinant of $A$" read "determinant of $I-Ax$"? 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$).

Comment by Anton Klyachko

2013-04-08T09:54:45Z

Thanks, Ilya!!!

Comment by Anton Klyachko

2013-04-08T09:53:38Z

Thanks, Sergey!

Comment by Anton Klyachko

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.

Comment by Anton Klyachko

2013-04-04T14:41:11Z

The Russian original of Shutov's paper is freely available: mathnet.ru/php/… .

Comment by Anton Klyachko

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$.

Comment by Anton Klyachko

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?

Comment by Anton Klyachko

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$.)

Comment by Anton Klyachko

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$...