Show HN: I made a puzzle game that gently introduces my favorite math mysteries (rahulilango.com)
There were a lot of fun technical parts to building this:
- For implementation reasons, it’s much easier if the lines all have integer intersection points with each other. To do this, when a new line is added I “cheat” by rounding intersections to integers and then splitting the old lines at the intersection into new linds (with potentially different slopes) going through the rounded point
- I had to draw semi accurate maps of actual places (UK, South America, US west coast) in the HTML canvas using just line segments. I tried a few different solutions, including using SVG data. I ended up using the topojson library to give nice line approximations to GeoJSON maps
- I use a simple backtracking algorithm to handle the live coloring of graphs
- I use turf.js’s polygonize function to handle finding polygons from line segments (very happy I didn’t have to implement this myself!)
- I wanted to make the game as mobile friendly as possible (don’t think I’ve nailed this quite yet)
There were also a few tradeoffs I made:
- I wanted give links earlier in the game for players to learn more, but I decided to wait until the end to maintain the flow of the game
- In order to make the game more mobile-friendly, I generally stuck to maps with a small number of regions (at least for maps people have to interact with them). So for the most part all of the instances in the game are “easy”
176 comments
[ 3.2 ms ] story [ 167 ms ] threadI understand that you want to emphasize the fact that no human can understand the proof with a full overview, but I wonder whether the current sentence will not make people think mathematicians are not perfectly sure of the proof.
Or some such.
To top that up, it's fact that there have been "proves" that were wrong (or maybe that's just my believe? :^]) even for a long time.
Hence, I think we can say that there are 4 options for a theorem:
1) Some mathematician believes the theorem is correct (but can't prove it)
2) Some mathematician believes the theorem is incorrect (but can't prove it)
3) Some mathematician believes the proof of a theorem is correct
4) Some mathematician believes the proof of a theorem is incorrect
Proving that a proof is correct is kind of meaningless. At that point it's all believe anyways.
Mathematical poofs are either correct or false. There is no middle ground.
What is your criteria of "can be checked then"? If a proof for "sqrt(2) is not a rational number" can't be checked by a 5yo, it's still a proof no?
* The proof of the classification of simple groups[0]
* The work on topological four manifolds by M. Freedman [1]
[0]: https://en.m.wikipedia.org/wiki/Classification_of_finite_sim...
[1]: https://news.ycombinator.com/item?id=28471159
Yes.
The fact that we don't know the truth doesn't mean there isn't one.
And those many jobXtoY.v and taskXtoY.v files sure look like they also do the same as the Appel and Haken proof, namely enumerate lots and lots of cases that are then machine-checked. So I don't think the computerized Coq proof is really qualitatively different from other computerized proofs that enumerate so many cases that a manual check would be impractical.
https://github.com/clarus/falso
Proof and belief I think are pretty strongly intertwined, but I'm not going to pretend to have a particularly rigorous philosophy on the matter. Similarly, when the proof of Fermat's last theorem was published, I don't know if I should consider that to be a proof because it is well beyond my comprehension. I have no reason to question it, but should I consider it a proof? I know that people smarter than me (e.g. Wiles) thought the original version of it was a proof, but it had a subtle error in it which required a fix. While I haven't looked at the proof and revision, I would be surprised if I could look at the two versions as labelled and tell which one is the correct version.
I'm not sure how it works with the example of the primes, I lost the link to the later pages of the game so I can't read over it again, but I think it's guaranteed because there's just one number encoding all the assignments and you just get to unlock a single pair with the key given in response to your choice. There's an assumption that there isn't enough information in the key to fake any response, it has to reveal something that was already in there.
> Question: How do you do this in the digital world, without post-it notes?
Answer:
"When I give you a map labelled with numbers for each region, the numbers are the "post-it notes", "covering" the list of factors (which encodes a color). You can't see the primes factors inside them, because, even though generating an multiplying large primes is easy for computers, factoring numbers is much, much harder.)"
I think if, when the player checks "reply the demo, with numbers", you move the game down to where the prime number discussion is, it's easier to understand.
Also, note that the digital versionis better than the physical version. In the physical version, you can't stop me from removing extra notes. (A better example might be to put each color in a locked box, each with a different lock/key.) In the digital version, the factor lists are the "keys".
This demo was fun, and cool, and short (a undervalued virtue!). Awesome work. Thanks.
> As a term, "British Isles" is a geographical name and not a political unit.
Many, many people have died for this triviality.
"Somewhat fraught" is a very interesting choice of words, but then again, so is "The Troubles" (when the subject matter is decades of bombings and killings).
There’s not a 100% great term for the collective unit of land. Generally people go with “UK & Ireland” if they’re trying to be sensitive.
https://en.wikipedia.org/wiki/Terminology_of_the_British_Isl...
Obvious, really! :)
https://en.wikipedia.org/wiki/Names_of_the_British_Isles
The Irish may not like it, but they're fighting against two millenia of history.
Frankly, I find the term offensive, and think it should be discouraged in much the same way people have shifted away from "the Ukraine" to simply Ukraine.
It's the difference between a descriptive name for a region and a proper noun for a country.
Two thousand years ago Britain and Ireland were ethnically and linguistically pretty similar (I believe). Since then they have diverged in many ways - most significantly during the Reformation period when people in Britain largely left Catholicism, but people in Ireland remained Catholic. Changes like this and the legacy of colonialism this have ultimately resulted in Ireland having distinctly non-British identity. It is reasonable that our naming for things reflect this current state of affairs.
As always, it useful to consider other examples to clarify the point. For example, by the same argument, should we deprecate the phrase "Latin America"? After all, Latin Europeans only arrived in the Americas 500 years ago and the continent has had people for 10 thousand years before that. Are people who include a European adjective in the name of this cultural area "fighting against ten millenia of history"?
On another note, I dislike how “Zero-Knowledge Proofs” are called proofs. It’s not a proof. You iteratively increase your belief that the result is true, like in experimentation, but that’s not a proof.
I guess you also don't like the name Proof of Work.
I knew that 4 colours sufficed for any arbitrary map from back in the day when I learned this, but still I found it VERY rewarding by attempting to draw a map that needed 5 colors, and how intuitive this demo was for getting a "feel" for a thing that I knew only theoretically! Like I needed an impossible geometry to fit, either an area that stretched to a zero-width path (which would becomes a point, and thus 2 areas, so doesn't fit) or some other "impossible" geometry. Loved it, congrats on a really well executed idea!
https://en.m.wikipedia.org/wiki/Four_color_theorem
(I bought Paul Lockhart's "measurements" but gave up because I felt like I needed a sandbox to play with and little hints. Like, I don't want to be told the answer but I want to know feedback exactly like this demo. Very simple: "this is not right" or "this is right, but can be done with fewer")
(My dream is to have a little game jam where we make interactive versions of these concepts as puzzle)
As a suggestion, I would dearly enjoy a follow-up rigorously connecting those visual, intuitive ideas to actual mathematics.
The final though seemed like a huge leap for me, who don’t know anything about those math mysteries (which I assume is your target audience).
First I was curious to learn how is the fast way to understand that 1, 2, or 4 colors suffice. And why finding out such a way for 3 is so hard.
The zero-knowledge proof demonstration felt like “changing the subject”. Probably I missed the connection there.
It would help to clarify that in the beginning. The game is a bit of a shaggy dog tail. It would be good to give an outline and progress bar at the start (without spoilers)
It feels like something that got detached from the things that make it work during simplification. Or it could be that I just have a misunderstanding/oversight in the zero knowledge proof :).
In an unrelated note: I colored the larger graph and it didn't even play along!
This confused me at first.
That still leaves how to rely on chance of picks for a proof though.
It's not that the chances of lying are small, it's that they can be made arbitrarily small.
Let's say my standards of "proof" are that there's only 0.1% chance that you're cheating. We play that game several times, and I'm satisfied.
Next comes someone else whose standard is 0.001% chance of cheating. They simply play the game a few more times, and they're satisfied too.
If they change their mind and decide that only 0.0000001% will make them happy, they simply tack on a few more rounds.
The key here is that the probability that you can cheat for arbitrarily long is exactly zero — for the same reason that Zeno's paradox is resolvable (and limit of 1, 1/2, 1/4, 1/8, 1/16, ... is exactly zero, and not just a very small number).
For the ZK example, the math behind it is this: if there are m bordering regions and I am lying, you have a 1/m chance of catching me each time. Thus after k repetitions the chance you haven't caught me is (1-1/m)^k \approx e^{-k/m} which is extremely small for k sufficiently larger than m.
Now, you may rightfully say: hey that's still not a "proof," you could still be lying! There are two responses to this:
1. The probability can be made incredibly small, like smaller than the the chance, say, your computer got hit by a gamma ray burst that would flip bits from 0 to 1 (I really have no idea if this actually happens but people have said it to me).
2. It turns out it is mathematically impossible to get the zero knowledge property if you want true proofs (i.e., no probability of being wrong). So, there's a trade off: if you want zero knowledge, you have to accept some (small) failure probability
P.S. Adding an easter egg for coloring the larger graph is on the todo list :)
But none of that is telling you how much is "sufficient", or even which order of magnitude we're talking about. If the quantity has a real life cost, this would result in enormous practical differences.
(With the formula you have given for the ZK proof, we're at least one step further: You can start with the desired probability, e.g. the gamma ray burst und calculate the required minimum k from that - also, it's easy to see that the color problem lends itself well to such proofs because the probability of failure drops exponentially quickly with growing k, so the actual k you choose can be relatively small. But if all you have is a proof in the limit, that's not possible)
I think it would present better if introduced as "To show that there's no cheating going on behind the scenes, we will..."
I might use smaller factors then.
Looking forward to the easter egg :)
So isn't it possible that there is a polynomial time algorithm for integer factorization, but no polynominal time algorithm for 3-coloring, and therefore the "zero knowledge proof" actually reveals the answer?
However, if P = NP, there is no process that works here - there's nothing that is hard to do but easy to demonstrate, and therefore no zero knowledge proofs exist.
Actually, that's not true either. It requires the definition that all polynomial-time algorithms run quickly and all superpolynomial ones run slowly. This is not an accurate definition for all practical problem sizes and this is where the analogies all break down. Polynomial vs nonpolynomial is more interesting to complexity theorists than "how many years would this actually take with a fast computer".
IIRC technically, there are zero-knowledge proofs for all statements in P: the proof is "prove it yourself", which the verifier can do because it's in P.
And the demo could also tell you the expected number of iterations to catch the lie with (50/90/99%) probability. It'd be a pretty large number even for such a small graph, I'd bet.
(Of course the computer could also lie about the factorizations, since it's unlikely a human would bother to catch it in that kind of lie; but let's assume it doesn't ever do that.)
Readers might also be interested in the https://mathworld.wolfram.com/McGregorMap.html (reported, on 1 April 1975, to require five colors!)
Prior to this I'd only seen "proof" in math where it has meant you can absolutely guarantee there to bo no counterexample not just that it seems impossibly unlikely there could be a counterexample. E.g. the Tarry-Escott problem where we have proof there is no sets exists with n=4 and m=5 even though we haven't ever found numerical values of sets matching that description or Merten's conjecture where the smallest counterexample is estimated to be so large (~10 billion digits) we've not even been able to find the first counterexample value despite knowing it exists due to a proof. On the other side of things we have things like the Goldbach conjecture or Riemann Hypothesis where we've poured our hearts, brains, and souls into trying to find a counterexample or proof and don't claim to have either yet.
Adjusting to that definition of "proof" for the context it all makes a lot more sense now.
That's fine though, because the point isn't really to publish math papers without disclosing proofs. For example, presenting a valid digital signature is sometimes colloquially called a proof that you had the private key, even though there is 1 in gazillion chance that you didn't. For such practical tasks, very high chance tends to be good enough.
[1] sorry, 3-chromatic or whatever
Alternatively, you could automatically "close" figures after they have at least three points, and give a hint of a handle that allows dragging a new point out of the middle of an existing side.
Entirely my mistake because I was kind of ignoring everything you said lol
This was so much cooler than just being told that 4 colors is enough for every map – this one will stick with me.
It would be wonderful if schools taught a bit more like this – I almost felt like I discovered it myself!