Timothy Chow's comment applies also to Mark Schultz-Wu's comment. The non-probabilistic proofs are harder, but often yield more information than mere existence. There is a reason so many problems in extremal combinatorics and CS are of the form "We know this exists by a probabilistic argument, but we need to find one concretely/constructively."

I knew about that application of Hopf, but hadn't thought about the (|G|-1)^2 as the number of relators in the multiplication table. That's a nice way to think about it.

@TomWilde: Ah yes, thanks! I think that is right, I must have been misremembering about $C_n$. I will double-check and then update the question at some point.

Ah nice, thanks! The part I was missing was that the image was free so the sequence splits. And then that means my question about the distribution of elementary divisors becomes equivalent to asking about the distribution of orders in the torsion part of group cohomology, which I guess is a well-known question.

I'm confused...I thought $H^k(G, \mathbb{Z}) \cong H^k(BG, \mathbb{Z})$ (LHS=group cohomology, RHS=simplicial cohomology) for all groups. I know this question is about real coefficients since that's where the de Rham isomorphism holds, but doesn't the universal coefficient theorem give a pretty close relation between (the free part of) $H_k(BG, \mathbb{Z})$ and $H^k(BG, \mathbb{R})$?

@LSpice: Nice! Thanks for sharing. Looks not far from things I know. Is there a good place to read about it? Is it at least an "exact sequence" of pointed $G_x$-sets? And when $G_x$ is normal in $G$, is it actually an exact sequence of groups?

@Lspice: Is that just an "exact sequence in spirit"? More precisely: in what category does your more general exact sequence live? If $G_x$ is not normal in $G$, then the orbit $G \cdot x$ is not naturally a group...

@MartinBrandenburg "every complete treatment of linear algebra also contains multilinear algebra" this sounds like a plausible statement to me, but I do not know great refs for multilinear algebra that aren't either (a) physics (so they are really doing tensor fields/bundles, rather than "plain" tensors) or (b) relatively advanced algebra texts. Do you know good linear algebra texts that cover multilinear algebra in a way accessible to people learning it for the first time?

Very appropriate for a question based on a Rota quotation!