With or Without Logic?
This connection between the Parah Adumah and the Chet Haegel actually seems very puzzling. At the beginning of Parshas Chukas, in which the commandment of the Parah Adumah is given, the Torah says, זאת חֻקַּת הַתּוֹרָה. Rashi says that the mitzvah of the Parah Adumah was a chok, וְאֵין לְךָ רְשׁוּת לְהַרְהֵר אַחֲרֶיהָ, and we are not permitted to seek a reason for this mitzvah. The reason has not been revealed to us, and we do not need to understand why we perform it. It is a גְּזֵרַת הַמֶּלֶךְ, a command of the King, which we need to follow without any knowledge of the reasons involved.
This is unlike many other mitzvos, such as לֹא תִגְנֹב or כַּבֵּד אֶת אָבִיךָ וְאֶת אִמֶּךָ it is understandable why the Torah commanded us to perform them. By other mitzvos, the reasons are not as obvious, however we might find an explanation in the Torah or Chazal. However, a chok is a mitzvah that we perform without trying to understand why. Therefore, the explanation that the Parah Adumah was an atonement for the chet haegel seems to contradict the nature of this mitzvah which the Torah states is explicitly not meant to be understood - if a reason is given, then it is no longer a chok. Indeed, this question is explored in many seforim.
Many commentaries answer that it is exactly because we perform this chok without any understanding of the reasons behind it, that it can serve as an atonement for the chet haegel. Because we do not seek to understand, and we do not make our own calculations, it can be mechaper for the eigel, which came about because of us making our own excessive calculations and reasoning.
A Result of Misguided Calculations
The chet haegel was not a straightforward case of idol-worship. It was shortly after matan Torah, and Klal Yisroel were in fact on a very elevated spiritual level. The cause that led to this terrible sin, was that they made too many calculations and came to their own conclusions. They did not follow the guidance of Aharon Hakohein and the ziknei hador.
The Ohr Hachaim expounds greatly on exactly what the yidden were thinking, and how it led them down a path which ended with the terrible sin of the golden calf. There were very few who actually explained the calf as a G-d, however there were many other classes of Yidden who participated in the sin on different levels, and had different calculations and reasoning as to why they created the golden calf.
The Yidden saw that Moshe, who was Hashem's emissary to them, was missing. They thought they need to create a different vessel to bring הַשְׁרָאַת הַשְּׁכִינָה into their midst. It was a tragic mistake which resulted from too much independent calculations, reasoning and misguided reckoning.
The Beis Halevi is one of the chief commentators who explains the connection between the Parah Adumah and the chet haegel in this way. He explains that all the mitzvos have taamim, both straightforward understandable explanations, and deeper, loftier reasons which only very holy people understand. The seforim tell us the extensive effects of every single mitzvah we perform, and how it influences phenomena in the upper-worlds.