Aluffi II.8.3 suggests proving that every finite group can be finitely presented.
Clearly, we could just present a group via its whole underlying set as the set over which we construct the free group, and $\{ g_i g_j = g_k | \forall g_i, g_j \in G \}$ as the relations, so the proof is easy.
But the question I have is slightly different: is it possible to do this more effectively (with less relations listed explicitly) for an arbitrary group? For instance, $S_3$ is represented as $(\{ x, y \} \mid x^2, y^3, xyxy)$ earlier in the book, which lists far less relations than the whole multiplication table for $S_3$.
There is a formula which goes by the names "the Schreier index formula" and "the Nielsen–Schreier formula". Interpreted for this question, it says that a generating set of size $n$ for $G$ requires at most $1+|G|(n-1)$ relators. This gives a reasonable upper-bound for the size of a presentation (where size=#gen+#rel). If $n$ is the minimum possible size of a generating set then: $$\min(\text{size of presentation})\leq|G|(n-1)+n+1$$ According to the comments to the question, $n\leq\log_2(|G|)$ so we get: $$\min(\text{size of presentation})\leq|G|(\log_2(|G|)-1)+\log_2(|G|)+1$$ For example, if $G$ is a non-abelian finite simple group then $G$ can be generated by $2$ elements (this is a theorem). Hence, $G$ has a presentation of size $|G|+3$, which is pretty neat!
We can usually do better because this formula is about generation of a subgroup of a free group, while we want normal generation of the same subgroup.