As mentioned already, folklore gadget reductions show that either Triangle or 4-Cycle can be reduced to a single instance of \(k\) -Cycle detection on the same number of edges, for any \(k\ge 3\)  (we add a proof of this statement in Appendix REF , similar reductions appear, for example, in [1]}).
Thus, we establish a super-linear \(\Omega (m^{1.1194})\)  lower bound for \(k\) -Cycle detection for all constant \(k\ge 3\) .
