MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Barry Mazur and I have come across the question below, motivated by (but independent of) issues regarding the Leopoldt conjecture.

Suppose that $\mathbf{C}$ is the complex numbers.

Let $H$ be a finite set, and let $S$ be a subset of $H$. The vector space $X = \mathbf{C}^{H}$ has a canonical basis consisting of the generators $[h]$ for $h \in H$. Let $X_S$ denote the subspace generated by $[h]$ for $h \in S$. Suppose we consider a subspace $U$ of $X$, and ask for the dimension of $U \cap X_S$. The answer will depend on $U$, but we expect the codimension of the intersection will generically be the sum of the codimensions of each space. In other words, let $G(X,U)$ denote the set of vector spaces $V$ inside $X$ which are abstractly isomorphic to $U$ - that is, $\dim(V) = \dim(U)$. Then $$\min \{ \dim(V \cap X_S), \ | \ V \in G(X,U)\} = \min\{0,\dim(U) + |S| - |H|\}\}.$$ Indeed, $G(X,U)$ is a Grassmannian, and equality holds on an open set in $G(X,U)$.

Suppose we now assume that $H$ is a group. We continue to assume that $S$ is a subset of $H$ (not necessarily a subgroup), and that $X_S$ is the subspace generated by $[h]$ for $h \in S$. The vector space $X$ now has extra structure --- it has a left and right action of $H$, indeed, $X \simeq \mathbf{C}[H]$ is just the regular representation of $H$. Suppose that $U$ is a subspace of $X$, and let us additionally assume that $H.U = U$, that is, $U$ is a representation of $H$, and the inclusion $U \subseteq X$ is an inclusion of left $X = \mathbf{C}[H]$-modules. We now suppose that $G_H(X,U)$ is the set of left $X$-modules $V$ inside $X$ which are abstractly isomorphic to $U$ as representations of $H$ --- this is contained in but generally much smaller than the space of vector subspaces isomorphic to $U$. The question is: can one compute $$\delta(H,S,U) := \min \{ \dim(V \cap X_S), \ | \ V \in G_H(X,U)\}.$$ That is: what is the expected dimension of this intersection given the structure of $U$ as an $H$-module?

$G_H(X,U)$ can be identified with a product of Grassmannians, namely $G(v_i,u_i)$ where $V_i$ are the irreducible representations of $H$, $v_i = \dim(V_i)$, and $u_i = \dim \mathrm{Hom}_H(V_i,U)$. A lower bound for $\delta(H,S,U)$ is given by $\min\{0,\dim(U) + |S| - |H|\}$, but this is not optimal in general.

Remark: If $u_i \in \{0,v_i\}$ for all $i$, then $G_H(X,U)$ consists of a single point.

Example: Let $H = \langle \sigma \rangle$ be cyclic of order four. Let $U$ consist of the subspace generated by $[1] + [\sigma^2]$ and $[\sigma] + [\sigma^3]$. Then $G_H(X,U) = \{U\}$ is a point. If $S = \{[1],[\sigma^2]\}$ then $\dim X_S \cap U = 1$, even though $\dim(U) + |S| -|H| = 0$.

The most general question is: Can one compute $\delta(H,S,U)$ in a nice way?

A more specific question is: Can one compute $\delta(H,S,U)$ when $H$ has an element $c$ of order two and $U = X^{c = 1}$, that is, the elements of $X$ which $c$ acts by $1$ on the right. $u_i = \dim \mathrm{Hom}_H(U,V_i)$ is equal to $\dim(V_i,c = 1)$ in this case.

An even more specific question is: Can one compute $\delta(H,S,U)$ when $H = S_4$ (with representations of dimension $1$, $1$, $2$, $3$ and $3$, and $U = X^{(12) = 1}$ has corresponding multiplicities $1$, $0$, $1$, $1$, and $2$? What about $H = D_{8}$ or $D_{10}$, and $c$ is a reflection?

Example: Suppose that $U = X^{c = 1}$, and suppose that $c$ is central in $H$. This is exactly the condition on $c$ to ensure that $G_H(X,U)$ is a point. Then $$\delta(H,S,U) = \frac{1}{2} | \{ s \in S \ | \ cs \in S\}|.$$ This generalizes the previous Example, where $c = \sigma^2$.

Let me make the following remark. As I mentioned in the question, One can obtain the complete answer when $c$ is central. In this case, one obtains generic intersections that are "larger" than what one expects from the linear algebra, at least when $|G| > 2$. It follows that a similar thing happens whenever $G$ admits a quotient $G/H$ of order $> 2$ where $c$ is central. This explains why one would expect degenerate answers in dihedral groups $D_{2n}$ of order divisible by $4$. Having done $D_3 = S_3$ by hand, the next "interesting" case is $D_5$. If I understand Greg's answer correctly, the generic intersection is always as small as possible for $D_5$ and $D_7$ and any $S$. Thus the most optimistic conjecture is that this is always the case providing that $|G^{ab}| \le 2$, for example, if $G = S_4$.

share|cite|improve this question
up vote 6 down vote accepted

This is not a complete solution, but it is a way to compute things in sort-of a nice way. The module $U$ has a complementary module $U^\perp$, and the kernel of a generic module map $F:X \to U^\perp$ is isomorphic to $U$. Then you can look at the restriction $F:X_S \to U^\perp$ and try to compute its generic rank. This puts things as close as possible to linear algebra, because $F$ comes from a linear family of linear maps. The first question is whether there is any anomalous intersection, which amounts to asking whether $F$ has maximal rank, which amounts to computing the full minors of $F$. Each maximal minor simply corresponds to restricting to $X_T$ for a subset $T \subseteq S$ such that $|T| = \dim U^\perp$. This is simply the statement that $$\dim (X_S \cap V) - \dim (X_T \cap V) \le \dim X_S - \dim X_T,$$ which is true solely because $X_T$ is a subspace of $X_S$.

You ask about certain special cases in which $U$ comes from a permutation representation $H/c$, and $U^\perp$ is thus induced from the sign representation $c = -1$. In such a case, the matrix of $F$ has a simple form in which each entry is a single variable, and the variables are negated or repeated across entries. For example, if $H = S_3$ and $c$ is a transposition, then I get $$F = \begin{pmatrix} x & -y & -x & z & y & -z \\ y & -x & -z & x & z & -y \\ z & -z & -y & y & x & -x \end{pmatrix}$$ for all of $X$. We are interested in determinants and ranks of minors of this matrix, and evidently we can remove all of the minus signs without changing any answers. This is explained by the fact that $c$ is complemented by the alternating group and we can tensor $X$ by the sign representation to switch $U$ with $U^\perp$. For the same reason, we can switch $U$ and $U^\perp$ for the dihedral cases as well, because $c$ is complemented by a subgroup of index 2. Then $F$ becomes a generic module map between two permutation representations of $H$; each matrix entry of such an $F$ is a single variable.

It is easy to check that for the example of $S_3$ and $c$ a transposition, every full minor has the property that one of three variables ($x$, $y$, or $z$) is a transversal. This is a sufficient condition for that minor to be generically non-zero. So, there are no anomalous generic intersections for this $H$ and this $U$.

If $c$ is central, then the matrix of $F$ has repeated columns. Obviously, if a minor of $F$ has repeated columns, then it vanishes. But this is not the only way to get an anomalous generic intersection. For instance, if $H = D_4$ and $c$ is a reflection, then (if you switch from $U = X^{c=1}$ to $U = X^{c=-1}$ as I argued you can), you get the matrix $$F = \begin{pmatrix} x & y & z & w & x & y & z & w \\ w & x & y & z & y & z & w & x \\ z & w & x & y & z & w & x & y \\ y & z & w & x & w & x & y & z \end{pmatrix}$$ The odd-numbered columns are a vanishing minor. The reason is that the vector $$(1, 0, 1, 0,-1, 0, -1, 0)$$ is always in $V$.

So, although I certainly don't have a complete solution, I can find examples of $S$ where there isn't an anomalous intersection (because one of the variables is a transversal), and examples where there is an anomalous intersection (because every admissible $V$ contains the same vector in $X_S$). And, this formulation of the problem makes it easier to check a given $S$ by computer.

In other words, the question is essentially a matroid problem. The set $F(H)$ is a spanning set in the module $U^\perp$, and you are interested in the matroid structure of $F(H)$ for a generic $H$, because a circuit or linearly dependent subset $F(S)$ gives you an $S$ such that $V \cap X_S$ is larger than expected. I wrote a short program in Sage to compute this matroid for $D_n$, where the element $c$ is a reflection, using a convenient matroid package written by David Joyner.

n = 6                   # For the dihedral group D_n
gen = primes(100,200)   # Generic parameters

load 'matroid_class.sage'

R.<x,y> = PolynomialRing(ZZ,2)
names = [x^k for k in range(n)] + [x^k*y for k in xrange(n)]
a = list(gen)[:n]
F = matrix(QQ,[[a[(i-j)%n] for i in range(n)] + [a[(i+j)%n] for i in range(n)]
    for j in range(n)])
for S in vector_matroid(F).circuits():
    if len(S) <= n: print [names[k] for k in S]

For $D_4$ and $D_6$, the program found various matroid circuits of size 4 and 6, respectively. For $D_5$ and $D_7$, it did not find any non-trivial circuits. I do not understand their full structure, but there they are. For $D_8$, it eventually reporteed that there are 362 non-trivial circuits of size 8 and none that are smaller. The first one listed is $S = \{1,x,x^2,x^3,y,xy,x^2y,x^3y\}$, if the group is $$D_8 = \langle x,y | x^8 = y^2 = xyxy = 1 \rangle$$ and $y=c$.

Although this package is convenient, it is not efficient. With a more efficient code, it should be possible to find all of the non-trivial circuits in $D_{10}$ and maybe $S_4$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.