User klim efremenko - MathOverflow

Representations of $GL(n)$ containing $S^kV$

2013-01-10T23:04:36Z

Let $V$ be a vector space of dimension $n$. Let $S^k V$ be a representation of $GL(n)$. I would like to know if there exists some characterization of finite dimensional $GL(n)$ modules $V_1,V_2$ such that exists $GL(n)$ mapping $T:S^k V \rightarrow V_1\otimes V_2$ such that for some $x$ matrix $T(x)$ is invertible .

Added: Just to clarify: The mapping $T$ itself may not be invertible I am asking that $T(x)$ will be invertible in $V_1\otimes V_2$. For example the mapping $S^2 V \rightarrow V\otimes V$ is not invariable, but $T(x)$ is invartable for most $x$'s.

I am interested for a base field $\mathbb{C}$. And of course this may happen only in case when $S^kV$ is a sub-representation of $V_1 \otimes V_2$. In fact I do not know for which irreps $V_1, V_2$ representation $V_1 \otimes V_2$ have $S^kV$ as a component. I will be happy if you can give me a reference for this question.

Good book on representation theory of GL(n)

2013-01-11T18:40:25Z

I am interested in a recommendation for a good book which discuses representation theory of GL(n)(say over field of complex numbers). I know only a basic representation theory. The question I am interested in are how looks decomposition of $GL(n)$ module $V\otimes W$, where $V$,$W$ irreps. I am interested in book or chapter in book which will not require too much preliminary.

Tensor rank of anti-symmetric tensor

2012-12-20T00:31:23Z

Let $V$ be a vector space of dimension $n$. Let us consider $V^{\otimes n}=V\otimes V \ldots \otimes V$. This vector space contains one dimentional vector space $\wedge^n V$. My question is does it something is known about the tensor rank of the vector $\wedge^n V$?

More formally let $e_1, e_2,\ldots e_n$ be a basis for $V$ than the question is what does it known about the tensor rank of:$$ T=\sum_{\sigma \in S_n}(-1)^{sign(\sigma)} e_{\sigma(1)}\otimes e_{\sigma(2)} \otimes \ldots \otimes e_{\sigma(n)}.$$

The trivial upper bound on the tensor rank of this form is $n!$. Does it know any better uper bound?

As far as I know without $(-1)^{sign(\sigma)}$(i.e. for a symmetric form) it know upper bound of $2^n$.

Maximal number of maximal subgroups

2012-08-15T12:13:11Z

Let $G$ be a finite group. I want to find an upper bound on the number of the maximal subgroups. My questions is does it possible to prove that the number of maximal subgroups of any finite group $G$ is at most $|G|^{100}$?

One can easily find that any subgroup is generated by at most $\log|G|$ elements thus the number of subgroups(in particular maximal subgroups) is at most $|G|^{\log|G|}$. Does it possible to improve this upper bound. For an abelian group the number of maximal subgroups is at most $|G|$ and in fact I do not know any example where the number of maximal subgroups is more than $|G|$.

I am almost sure that I am not the first who is asking this question I would like to know if the answer to this question is known or either this is a hard question.

Typical dimension of partial derivatives

2012-11-12T22:27:49Z

Let $V$ be the space of all homogenous polynomials over $\mathbb{C}$ in $n$ variables of degree $d$. Let $l,k$ be two integers and $f\in V$. Let $\partial^{=k}(f)$ be the space of all partial derivatives of $f$ of degree exactly $k$. I want to understand how the space of partial derivatives looks like. For example if we will allow to to multiply the partial derivatives by polynomial of degree up-to $l$ what the dimention of the space will we get? Let us define the space $$L_{k,l}(f)=span \left[ a(x)p(x): deg (a(x))=l, p(x)\in \partial^k(f)\right].$$

I wonder if it is possible to calculate the dimension of $L_{k,l}(f)$ for a typical $f$.

Basis of a group

2012-08-14T09:45:15Z

Let $G$ be a finite group. I will say that a set of a subgroups $H_1,\ldots ,H_k$ defines a basis for a group $G$ if any subgroup $H$ of $G$ there exists $S\subset [k]$ such that $H=\cap_{i\in S}H_i$.

My question is does it possible to give any upper bounds on the size of the minimal basis for $G$. For example does it possible to prove that for any $G$ there exists a basis of size at most $|G|^{10}$?

For example for an Abalian group it is easy to show that there is always exists a basis of size $|G|$. For example in case $A=Z_p^n$ it will be all maximal subgroups.

Minimal degree of polynomial vanishing on the variety of small degree.

2012-07-24T20:24:22Z

My question is assume that we know that the degree of some irreducible variety is small does it possible to conclude that there exists polynomial of small degree vanishing on this variety.

Let us make the question more concrete: Let $V\subset A^{2n}$ be an irreducible algebraic variety of dimension $n$ and degree $d$ (say $2^n$). Let $I \triangleleft \mathbb{C}[x_1,\ldots, x_{2n}]$ be an ideal of all polynomials vanishing on $I$. My question is what is the best upper bound on the minimal degree of polynomials in $I$.

The best upper bound that I know is $2^n$, while I think that it is not the true. For example if $V$ is a complete intersection variety then $I$ must have polynomial of degree $2$.

What is the largest tensor rank on matrix.

2012-07-18T16:25:47Z

A tensor rank of tree dimentional matrix $M[i,j,k], i,j,k\in [1,\ldots,n]$ is a minimal number of vectors $x_i,y_i,z_i$, such that $M=\sum_{i=1}^d x_i\otimes y_i\otimes z_i$. From dimension argument it easily follows that there exists a matrix of tensor rank at least $\frac{1}{3}n^2$. One can also easily show that every matrix is of tensor rank at most $n^2$.

So I know that maximal tensor rank is between $\frac{1}{3}n^2$ and $n^2$. Does any one knows what is the maximal tensor rank.

p.s. As far as I understand maximal border rank is $\frac{1}{3}n^2$.

Answer by Klim Efremenko for Solving an arbitary polynomial in $Z_m$

2012-07-22T12:13:50Z

The first question is do you know the factoring of $m$?

If yes than using Chinese Reminder Theorem it is enough for you to solve it only for $p^k$. For $p^k$ you can use Hensel lifting its comlexity is $O(k\log{p} \mathrm{polylog}(k\log p))$ i.e., up to poly-logarithmic factor it is optimal.

If no than your problem is equivalent to factoring.

Jacobian and Algebraic independence

2012-07-18T16:58:20Z

Let us assume that we have $n$ polynomials in $n$ variables, $p_1(\vec{x}), p_2(\vec{x}),\ldots p_n(\vec{x})$. Jacobian, $J(p)$ of $\vec{p}$ is a matrix with $i,j$ entry $\frac{\partial p_i}{\partial x_j}$ Assume that $p_i$ are algebraically dependent, i.e., there exists polynomial $f$ such that $f(p_1,\ldots, p_n)=0$ then using chain rule of derivatives one can get that $J(p)\cdot (\partial f(p))=0$.

Over the field of zero characteristic the converse is also true. If Jacobian is not of the full rank then polynomials are algebraicly dependent. My question is if the stronger claim is true:

Assume that $\vec{v}=(v_1(x),\ldots, v_n(x))$ is a vector of polynomials such that $J(p)v=0$, then there exists polynomial $f$, such that $(\partial f)(\vec{p})=\vec{v}$.

Is Castelnuovo bound tight?

2012-04-29T08:31:50Z

Castelnuovo bound says that if we have a function field(algebraic curve) $F$ and a divisor on it $D$ then: $g\leq c\frac{\deg(D)^2}{\ell(D)}$(where $c$ is some global constant say 2 and $g$ is a genus of the curve). I would like to ask if the converse is true? My question is if the converse is true for every $\ell(D)$? Formally the question is the following:

Does there exists a constant $c$ such that for every function field $F$ and for every integer $2\leq l \leq g$ there exists a divisor $D$ with $\ell(D)= l$ and $g\geq c\frac{\deg(D)^2}{\ell(D)}$?

Spanning set for Lattice generated by an orbit of the group.

2012-03-01T18:25:59Z

For a vector spaces it always holds that any set of vectors spanning vector space $V$ has a subset of vectors which is a basis for $V$. While for lattices it is not true. For example consider one dimensional lattice spanned by $2,3$ then this lattice is $\mathbb{Z}$ and it is not spanned by any one of vectors. Simply stated my question is the following. Let $L$ be a lattice generated by an orbit of some vector $v\in V$ of dimension $k$. Does it always possible to find subset of the orbit which is a basis for lattice?

More formally: Let $G$ be a finite group. Let $\rho:G\rightarrow GL(V)$ be a representation such that $\rho(g)$ is an integer matrix for every $g$. Let $w\in V$ consider a lattice $$L= span_{\mathbb{Z}} ( {\rho(g)w: g\in G }). $$ Does it always possible to find $g_1,g_2,\ldots g_k$, where $k$ is the dimension of $L$ such that $( \rho(g_i)w)_{i=1}^k$ is a basis over $\mathbb{Z}$ for $L$?

Modular representations of the symplectic group

2012-02-07T19:35:03Z

Let G=Sp(2m,2) be a finite symplectic group acting on $F_2^{2m}$. This group G acts 2-transitively on $\Omega_{+}$ and on $\Omega_{-}$. Let $F$ be an algebraic closure of $F_2$. I am interested to know what are all $G$- invariant sub-spaces of $F^{\Omega_{+}}$ and ${F} ^{\Omega_{-}}$. Does anyone know good reference where this is calculated?

Automorphism group of algebraic function fields

2012-02-01T16:10:39Z

Let $K$ be a finite field and let $F/K$ be a function field. Is it possible to deduce the genus of $F/K$ from the automorphism group of $G=Aut(F/K)$? Is it possible to do so if we know that $|G|$ is greater than the genus?

Expanding sets in cyclic group of prime order.

2012-01-30T15:52:47Z

Let $S_1,S_2,\ldots S_k$ be a sequence of sets. We will call this sequence expanding if $S_i$ is not covered by $S_1,\ldots S_{i-1}$ i.e. $S_i$ contains at least one new element. Let $C_p$ be a cyclic group of size prime order $p$.

It is easy to show that for every $A\subset C_p$ there exists at least $k=\frac{p}{|A|}$ elements $a_1,\ldots a_k$, such that the sets $A+a_i$ are expanding.(Since each time we cover at most |A| new elements and we can cover all elements)

My question is if it is possible to improve this bound for $A$ of size at most $p/2$ to $k=\frac{p\log|A|}{|A|}$?

Dimension of affine variety

2011-10-27T16:16:43Z

Assume that I have $k$ polynomials $f_1(x_1,\ldots x_n),f_2(x_1,\ldots x_n),\ldots f_k(x_1,\ldots x_n)$ in $n>k$ variables. Is it possible to calculate, ,i.e., does there exist a fast algorithm, the dimension of the variety $Z(f_1,\ldots f_k)$?

Does there exist a good criterion to check if the dimension of $Z(f_1,\ldots f_k)$ is $n-k$ when all $f_i$ are quadratic polynomials?

Radical of $F_p[SL(2,p)]$

2011-10-17T15:06:16Z

Let $G=SL(2,p)$. Does anyone know what is the radical of the group algebra $F_p[G]$? Does there exists any book/paper where it is calculated?

By radical here I mean maximal ideal I of $F_p[G]$ such that $I^n=0$

Weil bound for characters sums. (reference-request )

2011-09-13T11:53:13Z

Do you know on any good reference on Weil bound for charcter sums over algebraic curves. I prefer reference which assume few previous knowlage.

Representations and support.

2011-02-26T19:46:37Z

I am interested in the question: Does there are exist concept of support in representation theory?

When I say support I mean number of non-zero values of $f \in C[G]$. Do you know theorems which talks about the action of elements of $C[G]$ with small support in different representations?

The only example I know about is uncertainty principle which says that for abelian group $supp(f)supp(\hat{f})\geq |A|$.

Answer by Klim Efremenko for Computation for composition of polynomials

2011-05-09T14:00:40Z

The answer is yes. You can do it using Fast Fourier Transform(FFT) to make FFT you need $n \log^k n$ operations. You not really need to know what FFT do. You need only to know that you can evaluate polynomial at some $n$ points using one FFT and you can calculate the polynomial from its values at $n$ points in one FFT.

The following algorithm should work: Using FFT evaluate $F(aX+b)$ at n points it is the same as to calculate F(X) at $n$ points. Next again using FFT you can calculate $F(aX+b)$.

How does the group algebra look as a Lie algebra

2011-04-03T16:31:29Z

It's probably a well known question, so it is just a reference question. Let $G$ be a finite group and let $C[G]$ be a group algebra. Then we can define a bracket on $C[G]$ by $[f,h]=f*h-h*f$. What does $C[G]$ look like as a Lie algebra? When is it solvable?

Answer by Klim Efremenko for Complexity of computing matrix rank over integers

2011-04-28T11:03:17Z

The answer to your question is yes. Note that you can bound determinant(in fact you need to bound the size of lattice spanned by rows of the matrix) of the matrix with integer of size polynomial in the length input. Let $p$ be a prime with is large than this bound then the rank of the integer matrix will be equal to the rank of the matrix mod $p$.

Approximated characters

2011-04-03T21:25:51Z

Is it possible to construct series of groups $G_i, |G_i|\mapsto \infty$ and functions $f_i:G_i\mapsto$ {$ 1,0,-1$} such that $f_i(1)=0$, $f_i(g) \in ${$-1,1$} for $g\neq 1$ such that dimension of $C[G_i]*f_i$ is small (i.e. $\dim C[G_i]*f_i\leq O(|G_i|^{\varepsilon })$ for every $\varepsilon>0$).

Group not leaving subset invariant

2011-03-31T17:46:58Z

Let $Y,X$ be two sets of size n,m. Let $Y\subset X$. What is the maximal group(in size) $G< Sym(X)$ such that gY=Y imply that $g=1$? Here I mean that the only permutation which permutes elements of $Y$ between themselves is identity.

Small sum of group elements acting as rank 1 matrix.

2011-03-28T07:22:53Z

I am interested in constructing small (as possible) group $G$ with large dimensional irreducible representation $\rho,V$ such that exist three elements of $g_1,g_2,g_3\in G$ such that for some $c_1,c_2,c_3\in C$ the matrix $c_1\rho(g_1)+c_2\rho(g_2)+c_3\rho(g_3)$ has rank one.($3$ elements here is arbitrary it may be any constant number)

In fact I know that if there is only two elements then $|G|\geq 2^{n}$, where $n=dim V$. It is easily floows from the post: http://mathoverflow.net/questions/57806/irreducible-representation-flipping-two-elements

My question is how to construct such irreducible representation of dimension $n>>log|G|$?

Example when $|G|>2^n$ is symmetric group $S_n$ acting on $n$ elements induces reps on $F^n$. If $\rho$ is $n-1$ dimensional irreducible sub-representation then $id-(1,2)$ acts as rank one matrix.

Irreducible representation flipping two elements

2011-03-08T10:35:41Z

Does there are exist simple proof for the following statement? Let $\rho,V$ be an irreducible representation of group $G$ of dimention $n$. Assume that there are exist $g \in G$ such that $\rho(g)$ just flips two coordinates. (that is $\rho(g)e_1=e_2,\ \rho(g)e_2=e_1,\ \rho(g)e_i=e_i$) Then $|G|\geq 2^n$, where $n$ is a dimention of the representation.

Answer by Klim Efremenko for Fast Matrix Multiplication

2011-03-03T23:12:56Z

http://www-cc.cs.uni-saarland.de/teaching/SS09/ComplexityofBilinearProblems/script.pdf It has some typos but except this it is really good.

Answer by Klim Efremenko for Convolution on symmetric group Sn

2011-03-03T22:29:08Z

It is not an answer to your question, but I hope it will help:

In general arithmetic complexity of convolution in non-anelian groups "equivalent" to the complexity of matrix multiplication. Here is the reason why:

The way of doing Fourier Transform in abelian group $A$ can be described in the is the following way: Let $f,g \in F[A]$ We know that $F[A]$ is isomorphic to the space $F^A$ with pointwise multiplication. Let $T$(which is acctually Fourier Transform) be this isomorphism. If we want calculate $f*g$ then calculate $T^{-1}(T(f)\cdot T(g))$. In case of non abelian group like $S_n$ It holds that $F[G]$ is isomorphic to the direct sum of matrix algebras that is $F[G]\simeq\oplus M_{n_i}$. Thus using the same formula you can calculate convolution in $S_n$, but now you will need to multiply matrixes.

Answer by Klim Efremenko for Probability of return vs. probability of return in minimal number of steps

2011-03-03T10:41:41Z

Your question is slightly ambiguous.

I think that there is almost no relation between $P(x), P(y)$ and $P_d(x),P_d(y)$.

Here is the reason: You can take any graph $G(V,E)$ and add two edges to it edge from $x$ to $O$ and edge from $y$ to $O$ such that $Pr(x\mapsto O)=\varepsilon_1$ and $Pr(y\mapsto O)=\varepsilon_2$. If $\varepsilon_i$ are small enough then it will not affect $P(x), P(y)$, but in this case $P_d(x)=\varepsilon_1$ and $P_d(y)=\varepsilon_2$. Therefore $P(x), P(y)$ are almost unrelated to $P_d(x),P_d(y)$.

Hope that this is helps.

Representations of central extensions

2011-02-25T08:49:01Z

Let $G$ be central extension of an abelian group $A$ by some group $H$. Is it possible to characterize all irreducible representions of $G$ in terms of irreducible representations of $A$ and $H$?

Comment by Klim Efremenko

2013-01-12T23:45:31Z

Made community wiki, I am interested only in finite dim reps.

Comment by Klim Efremenko

2013-01-11T13:20:39Z

Thanks for answer. Why do you say that $k=|\mu|-|\lambda|$? For example take $k$ even then definitely $S^k$ is subreps of $S^{k/2}\otimes S^{k/2}$

Comment by Klim Efremenko

2013-01-11T09:22:54Z

Thanks for your answer, Now I have added the comments so that there will be no more confusion. I think it will be better if you will delete your answer.(Just when people see question without answer more likely they will look on it.)

Comment by Klim Efremenko

2013-01-11T09:11:28Z

Dear Prasad, Thanks for your comment, but I am not asking for $T$, but for $T(x)$ to be invertible in $V_1\otimes V_2$.

Comment by Klim Efremenko

2012-11-13T15:56:13Z

I am interested in the case where $k$ is much smaller than d. In this case case the dimension of $\partial^{=k}(f)$ is upper bounded by number of monomials of degree $k$.

Comment by Klim Efremenko

2012-08-16T12:55:05Z

Thanks very much for an answer. Do you know by chance any survey/ book on a group lattices?

Comment by Klim Efremenko

2012-08-15T13:15:12Z

Thanks. For a reference. I assume you forgot power in the answer. i.e. |G|^{1/4}\log|G|

Comment by Klim Efremenko

2012-08-15T12:26:54Z

Thanks. I will accept your answer. And ask the question again in the form what is the maximal number of maximal subgroups.

Comment by Klim Efremenko

2012-08-14T22:09:31Z

Thanks for your comment. In fact I even do not know how to prove that the number of maximal subgroups is at most $|G|$

Comment by Klim Efremenko

2012-08-14T13:14:04Z

Because I believe that representation theory and lie groups may help to solve this problem. But may be it is not sufficient reason to tag it.

Comment by Klim Efremenko

2012-08-14T10:15:00Z

The name basis of a group I invented just now, may be this notion have an other name in the literature.

Comment by Klim Efremenko

2012-08-14T10:11:39Z

To Florian Eisele: thanks for a comment I made a change.

Comment by Klim Efremenko

2012-08-02T11:57:01Z

It is not really an answer, but since bounty ends soon I will accept it.

Comment by Klim Efremenko

2012-07-30T11:29:58Z

Thanks for an answer.

Comment by Klim Efremenko

2012-07-25T07:32:57Z

Probably in this question co-dimension of the variety is more important than its dimension, but for simplicity let us assume that both of them $n$.