# programming to compute kernel quotient image of a $\mathbb{Z}$-module endomorphism

Let the integers $n\geq 2$, $k\geq 1$, $v=0$ or $1$ and $n_1,\cdots,n_k\geq 1$ such that
$$\sum_{i=1}^k n_i+v=n.$$

Define $P_a^b=0$ if both $a,b$ are odd and $P_a^b={{[a/2]}\choose {[(a+b)/2]}}$ otherwise.

Given a fixed $n$, consider the free $\mathbb{Z}$-module generated by $$c[v,n_1,\cdots,n_k]$$ for all possible $k,v,n_1,\cdots,n_k$, considered as ordered tuples. We define an endomorphism $\partial$ of the above $\mathbb{Z}$-module by $$\partial c[0,n_1,\cdots,n_k]=\sum_{i=1}^{k-1}(-1)^{i-1}P^{n_i}_{n_{i+1}}c[0,n_1,\cdots,n_{i-1},n_i+n_{i+1},n_{i+2},\cdots,n_k]\\ +\sum_{i=1,n_i\geq 2}^{k}(1+(-1)^{n_i})(-1)^{\sum_{j=1}^{i-1}n_j}c[1,n_1,\cdots,n_i-1,\cdots,n_k],$$ $$\partial c[1,n_1,\cdots,n_k]=\sum_{i=1}^{k-1}(-1)^{i-1}P^{n_i}_{n_{i+1}}c[1,n_1,\cdots,n_{i-1},n_i+n_{i+1},n_{i+2},\cdots,n_k].$$ Then it can be proved $\partial\circ \partial =0$.

Question. I want to compute the modules $$\text{Kernel} \partial /\text{Image} \partial$$ for $n=2,3,4,5,6,7, ......,99$. I want to obtain a list. For example, $$n=2: \mathbb{Z}\oplus\mathbb{Z}_2.$$ $$n=3: \mathbb{Z}\oplus\mathbb{Z}\oplus\mathbb{Z}_4.$$ How to use programming to solve the problem? Thanks!

• This is going to be horrendous for large $n$. The size of your set of $c's$ for a given $n$ is going to grow exponentially in $n$ so I don't fancy your chances for $n \sim 10^4$. – David Loeffler Jan 26 '16 at 9:03
• Thanks, Prof! How about $n=3,5, 7,$......,$91, 97$? – QSH Jan 26 '16 at 10:56
• My gut feeling is that your computer is going to start emitting clouds of smoke for $n$ bigger than a dozen or so, since the size of the set of $c$'s is something like $2^n$, meaning you'd be trying to find kernels and images of matrices with tens of thousands of rows and columns. Did you try writing a program to list all the possible $(k, v, n_1, \dots, n_k)$ for a given $n$? – David Loeffler Jan 26 '16 at 14:13
• You should state clearly if you are thinking of the $[n_1,\dots,n_k]$ as ordered or unordered, your $n=3$ computation suggests that the order of $[n_1,\dots,n_k]$ is fixed (as does of course the definition of the differential). However, it seems to me that your definition of the differential implies $\partial^2(c[0,2,2])=8c[1,3]$ so that it fails to be a complex. – Matthias Wendt Jan 27 '16 at 10:34
• @MatthiasWendt Dear Prof., the tuples are ordered. – QSH Jan 28 '16 at 2:39

Ok, not really beautiful, but the lines below are a simple SAGE implementation of the map $\partial$, computing both the representing matrix and the elementary divisors. In the implementation I assumed that $P^b_a$ is actually the binomial coefficient $\binom{\lfloor (a+b)/2\rfloor}{\lfloor a/2\rfloor}$ (the order in the question did not seem to make sense).

def P(a,b): return (1-(a%2)*(b%2))*binomial((a+b)//2,b//2)

def index_help(list,index,j):
if j<index: return list[j]
elif j>index: return list[j+1]
else: return list[j]+list[j+1]
def sum_help(list,i): return [index_help(list,i,n-1) for n in range(1,len(list))]

def dec_help(list,index,j):
if j==index: return list[j]-1
else: return list[j]

def generators(n): return map(lambda x:[0,x], Compositions(n).list())
+ map(lambda x:[1,x], Compositions(n-1).list())

def differential(list):
tmp = list[1]
if list[0] == 1:
return [[(-1)^(n-1)*P(tmp[n-1],tmp[n]),[1,sum_help(tmp,n-1)]]
for n in range(1,len(tmp))]
elif list[0]==0:
return [[(-1)^(n-1)*P(tmp[n-1],tmp[n]),[0,sum_help(tmp,n-1)]]
for n in range(1,len(tmp))] +
[[(1+(-1)^(tmp[n]))*(-1)^(sum([tmp[p] for p in range(0,n)])),
[1,[dec_help(tmp,n,j) for j in range(0,len(tmp))]]]
for n in range(0,len(tmp)) if tmp[n]>=2]

def coefficient(comp,list): return sum([l[0] for l in list if comp == l[1]])

g = generators(5)
m = matrix([[coefficient(g[j],differential(g[i]))
for i in range(0,len(g))] for j in range(0,len(g))])
m.elementary_divisors()


If $\partial^2=0$, then the isomorphism type $\ker\partial/\operatorname{Im}\partial$ can be computed from the elementary divisors. For $n=2$ and $n=3$, the above program reproduces the computation mentioned in the question (suggesting that I eliminated the most obvious mistakes in my implementation). With my short attention span, I could not get to values $n>10$. The elementary divisors exhibited interesting patterns -- if there were actual homology groups to talk about, the rank would be $2$ for all $n\geq 3$ and the torsion somehow reflects the prime divisors of $n$.

However, the experimentations actually showed that $\partial^2\neq 0$ in general. Examples are $c[0,2,2]$ mentioned in my comment or $c[0,1,2,2]$ (in case you want to have an example where $n$ is prime). The problem seems to be with the terms in the differential which go from $c[0,\dots]$ to $c[1,\dots]$.

I also checked using unordered tuples (use Partitions(n) instead Compositions(n) and sort the results in the differential computation). The matrices are smaller, but still the map fails to be a differential (I guess this is more obvious, since summing only adjacent terms makes no sense for unordered tuples).

Maybe I misunderstood something in the definition of the $\partial$. However, if the implementation is correct, then you need to change something to get a differential. What would be the conceptual explanation of $\partial$ anyway, and is there a high-level explanation why we should expect it to be a differential?

• Thanks, Prof. Matthias Wendt! My question is from the paper ON THE COHOMOLOGY OF CONFIGURATION SPACES ON SURFACES, jlms.oxfordjournals.org/content/68/2/477.full.pdf+html, Section 2.2. Since $\partial\circ\partial \neq 0$, it seems I interpreted the boundary maps there wrongly. How to write out the correct boundary maps there? – QSH Jan 28 '16 at 12:45
• Prof. M. Wendt, I want to expand the table of $H^i(B(S^2,n);\mathbb{Z})$ in Section 2.2 of the paper ON THE COHOMOLOGY OF CONFIGURATION SPACES ON SURFACES, jlms.oxfordjournals.org/content/68/2/477.full.pdf+html for larger $n$. Is it possible? – QSH Jan 28 '16 at 13:01
• @R.S.: At first glance the complex in your question seems slightly different from the Fuks-Vainshtein complex. There is however a significant agreement between the table in the paper you mention and the computations of my program. Definitely, one should not omit the grading on the group generated by the $c[i,n_1,\dots,n_k]$. This could mean that the computations of elementary divisors go a bit further, but likely not beyond 20. – Matthias Wendt Jan 28 '16 at 18:57
• I could adjust the program if you want (or you could do it yourself). However, it is not clear what the gain would be. The table can not be significantly extended by computer use alone. Are you after the stabilization theorems? I don't know much about the topic, but if that's the case you might want to try looking for "representation stability" for homology of configuration spaces. – Matthias Wendt Jan 28 '16 at 19:00