I want to respond to some of the unanswered questions here as follows.
I see mathematics as something that comes before physics but I don't see mathematics as a platonic realm. Mathematics is just the study of logical possibilities and our physical experience is just a stream of those logical possibilities being played out. We don't need to explain existence and reality any more than that. Our intuition may demand a causal and structural explanation for why it all happens but that is just part of our psychological makeup and has no answer. However, we do need to explain why the laws of physics follow certain mathematical rules.
When people started doing mathematics they were interested in counting and measurement. There was no mystery about why the mathematics was effective in physics, because it was derived from it. But then mathematicians saw interesting logical structures that did not have obvious applications, such as prime numbers. Mathematics took on a life of its own.
Logical possibilities include stuff that is very interesting to mathematicians and stuff that is less interesting. The interesting stuff is characterised by its universality. It is applicable to a range of problems. Mathematicians are delighted when something they formulated for one problem turns out to be useful for another. They get a sense that those logical structures are discovered while others are merely invented. This is what distinguishes pure mathematics from other intellectual endeavours such as art and literature where we consider things to be created rather than discovered. All these things are logical possibilities but the mathematically interesting structures are more universal. They would probably be discovered by an alien race of mathematicians no matter what point they started from.
Already there seems to be some mysteriousness about this universality. Why is it there? Some people are not convinced. They see no mystery yet, so let's look further.
As pure mathematicians continued to study these objects for their own sake without any remaining interest in physics they went beyond the naturally occurring logical structures. They discovered the mathematics of complex numbers, non-Euclidean geometry and higher dimensional spaces. They did not expect these things to be useful to physicists but later they were. Already the unreasonable effectiveness of mathematics seemed mysterious to Wigner, but some people still shrugged their shoulders. They can say that these things were still inspired by physical ideas originally or that the universe is obviously going to be mathematical so of course these things are going to be useful.
For me the real clincher came when string theory was used to prove the monstrous moonshine conjectures. These were mysterious problems connecting areas of number theory and algebraic geometry that nobody would have expected to be connected to the real world. String theory has not yet been shown to be real physics but it was certainly discovered by physicists generalising the framework of quantum field theory with the goal of forming new physical theories. The distance across mathematics spanned by string theory and monstrous moonshine could not have been greater, and yet they turned out to be deeply connected in an unavoidable way.
This is no longer just a simple matter of the unreasonable effectiveness of mathematics in physics. It is also about the unreasonable effectiveness of physics in mathematics. The mystery is deep and cannot be shrugged off. It demands an explanation.
In my opinion, that explanation will come from a better understanding of universality and how it emerges in complex systems. It must be a self-organised structure embedded in the complex system of logical possibilities and their interrelations. It may be characterised by scale-free networks, self-similar fractal structures, path integrals over the grand ensemble of algorithms, iterated quantisation, n-category theory, symmetries etc. Our experience then unfolds according to laws of physics that form as a hierarchy of solutions derived from these universal systems. That is how our universe is put together and it explains the mysterious links that bind mathematics and physics together because this universality is ultimately what both mathematicians and physicists are drawn towards for different reasons.