What is a Mystery?

We were talking on Discord about mystery game campaigns and ended up asking the basic question. What is a mystery?
I think a mystery is an epistemic problem. It asks who killed the king, why the people are disappearing at night, or what the monster actually does. There is something about the fictional world that you don't understand and the challenge is figuring out what is true.
A mystery isn't a puzzle. A puzzle is a procedural problem. It asks how you open the secret door, how you cross the river, or what order you should kill these enemies in. A mystery might involve procedural problems in its solution, and hidden information may be involved in solving a puzzle, but they are still different kinds of problems.
The third thing is investigation, which is related to mystery but not the same thing. An investigation is about acquiring information, while a mystery is about understanding it. You could begin a session by handing the players the witness statements, the map, the autopsy report, and even the murder weapon. None of it needs to be discovered through investigation, but the question of who killed the mayor can still remain unanswered. The players have the clues. They just don't understand what they mean yet.
This is crucial because I've been in games, and seen people talk about games, where mystery is created and maintained by withholding information. And as an ICI Doctrine apostle this triggers me to no end. Withholding information doesn't make your mystery more mysterious or harder. It usually just makes the mystery harder to access, or even to notice. Some people seem to think being a GM means the whole game should be shrouded in mystery for the players, which is frustrating as fuck. Conversely, giving out information doesn't solve your mystery. It may be exactly what gets players to start thinking and wondering on their own, instead of waiting for the GM to feed them the questions.
The bitter pill to swallow is that players may simply not give a shit about the same mystery as the person running it. The GM gets to see all the information, all the connections, and all the implications, while the players only see whatever actually makes it across the table. Your cool mystery doesn't inherently deserve their attention either, especially when they have found some other mystery in the world that they care about more. Giving players information lets them decide what is interesting and make meaningful choices about it. Keeping them in the dark doesn't.
You can make information available in multiple ways. Most information can be obvious and freely given, some can be hidden and require interaction and some can come at a cost, often time. But these are questions about information access. They are not the mystery itself.

The difficulty of accessing information and the difficulty of understanding it are separate dials you can use. Clues could be very easy to obtain while the mystery is still hard because interpreting them is difficult. Or you could do it the other way around and make clues extremely hard to obtain, but their implications so obvious that the mystery practically solves itself once the players find them. Often these two difficulties get treated as if they are the same thing.
The fabled Three Clue Rule is staple advice for investigation games. Roughly, if the players need to reach a certain conclusion, you should provide several clues pointing toward it so that missing one clue doesn't bring the game to a halt. Which makes sense if your game requires the players to reach that conclusion. For me, the rule makes it more likely that players reach the conclusions the scenario expects them to reach. That's useful if you're designing around those conclusions, but it leaves intact the assumption that there are particular conclusions the players are eventually supposed to reach.
The obligatory banger opposite point is allow them to fail. If they fail to identify the murderer, the murderer kills again. If they fail to discover the dark ritual, it happens and summons the demon into this plane of existence. If they follow the wrong lead, the situation changes, but play continues. I'm diverging here and showing my strong preference, but I think the contrast is useful. The two approaches are solving slightly different problems. One makes sure the information pipeline doesn't break. The other asks whether a broken information pipeline needs to break the game at all.
Either can work, but neither changes what the mystery is. A mystery isn't a lack of information. It's a lack of understanding. You can tell the players a lot without telling them the answer. Often that's exactly what makes the mystery interesting in the first place. Keeping players ignorant isn't preserving the mystery, it's just keeping them away from it.