return to table of content

Show HN: I made a puzzle game that gently introduces my favorite math mysteries

bgoated01
21 replies
22h28m

I showed this to my two kids, and we all three enjoyed it. The zero knowledge proof portion didnt really click for me, but we liked the four color map theorem stuff. This led me to download some maps for my kids to attempt coloring on paper, and also got me wondering about how this holds or doesn't on non-euclidian spaces. Turns out the maximum is four colors on a sphere, but 7 colors on a torus! More details here: https://mathworld.wolfram.com/TorusColoring.html

Thanks for leading us down this mathematical rabbit hole today.

ianseyer
7 replies
20h48m

The best analogy of zk-proofs I've heard is to suppose you have found Waldo in "Where's Waldo," and want to prove that you have done this without revealing the location.

You could take a piece of paper (much larger than the picture/book), and cut out a waldo-shaped hole it and position the paper such that he is shown in the hole. Then, when you show it to the challenger, they know that you have found him without you revealing where he is.

nroets
1 replies
14h41m

But it's a simplification: One iteration is enough to detect lying.

In a real ZK proof the probability of the prover lying reduces after each iteration but never reached 0.

pxx
0 replies
4h51m

there is a probabilistic interactive component. this protocol allows the prover to fake it by just using a book where they know where Waldo is. in each iteration you choose whether to confirm it's the original book and page under the paper or see Waldo (but not both). a cheating prover has p = .5 of fooling a verifier.

but your concern is invalid to begin with. nothing in the definition of a zkp requires them to be multi-round interactive. there exist non-interactive zkp.

isaacfung
1 replies
11h35m

How do I know if it is the original "Where's Waldo" under the paper?

pxx
0 replies
4h51m

in each iteration you choose whether to confirm it's the original book and page under the paper or see waldo

IshKebab
1 replies
10h25m

I think that conveys what a zero knowledge proof achieves but it doesn't really correspond to any real zero knowledge proof algorithms. You can't do that over the phone, which is kind of the whole point.

pxx
0 replies
4h36m

no, that's not even close to the whole point. the analogy is to introduce the concept of proving something to a verifier without giving the verifier the solution

the paint-mixing analogy of diffie-hellman also can't be done over the phone, but it helps people understand how a shared secret can be established even if all communication is intercepted

delecti
0 replies
18h59m

It took me a minute to fully get this, so I'm adding this so it's a bit more obvious for anyone else: the piece of paper is much larger than the picture/book so that it can hide the book's relative position underneath it.

dmurray
4 replies
11h36m

Four colours also isn't enough for some real-world country maps. Countries with enclaves (like Alaska, Kaliningrad or Sint-Maarten, though only the last actually makes 4- colouring impossible) change the topology: you can think of what shape the earth would have if there was also a tunnel connecting Alaska and New York.

Blammar
3 replies
9h29m

Torus, of course, but how does that relate to enclaves, which are planar ?

dmurray
2 replies
9h17m

You might want to colour the exclave the same colour as the rest of its country, even though no connection can exist between them on the plane.

etbebl
1 replies
5h26m

It seems like you're using "enclave" and "exclave" interchangeably, which is causing confusion. What you're referring to is an exclave; an enclave is when one region is completely surrounded by another, like Lesotho or Vatican City.

dmurray
0 replies
3h51m

You're right, my first post should say exclaves and the three examples I gave are all exclaves.

wonger_
0 replies
20h33m

Great video, thanks. My takeaways:

- The physical demonstrations at 1:16 and 3:48 were helpful

- thinking of proofs as between a prover and a verifier, not as classical deterministic proofs

- insight into the name "zero-knowledge", as in "you can already predict the answer, so you're not gaining any knowledge from that interaction"

enlyth
1 replies
22h0m

Regarding the zero knowledge proof, there'd be a chance that the two random ones you reveal are the same color, if three weren't enough.

So by doing this over and over again, if the two you choose are always different colors, you approach a 100% certainty that it's legit.

You never really get a 100% proof but the more times you repeat the closer you are to being sure. At 99.999999% after repeating this enough times, you'd most likely be satisfied.

Aardwolf
0 replies
3h36m

When I read the zero knowledge proof part the first time, my thought was:

The person can just always give two different colors (and never two same colors) when you reveal two post it notes, so you could never proof them false.

Only after re-reading I realized _all_ the colors are to be hidden under the post it notes _beforehand_, not at the time you choose two post it notes.

helboi4
0 replies
8h55m

same that was extremely fun but im not sure i'm going to grasp the zk proof thing

guyomes
0 replies
12h31m

And it turns out that on the Klein bottle, the maximum is 6 colors. More generally, this number depends directly on the number of holes of the surface [1].

[1]: https://en.wikipedia.org/wiki/Heawood_conjecture

armchairhacker
0 replies
20h34m

Here's my explanation of the ZKP:

First, both you and the oracle know what the uncolored map looks like, and what the 3 colors are.

Step 1: The oracle sends the entire 3-colored map, but asymmetrically encrypted. So you can't see the map, but the oracle can't "un-send" it. If no 3-coloration of the map exists, the oracle has to send you something, and because you know what the map and colors look like, the only thing they can send is a map where some two adjacent regions have the same color.

Steps 2&3: You randomly pick two adjacent regions and ask the oracle for their decryption keys, so you can see their colors. When you initially received the encrypted map, you could not know whether it had two same-colored adjacent regions. But, if you happen to randomly choose the same-colored regions, the oracle has no way of not telling you. If the oracle refuses to send the decryption keys for those regions, or sends ones that don't successfully decrypt, you'll know something is up, and can assume the regions are the same color. And the only keys that successfully decrypt the regions' colors, decrypt into their original colors; so the regions will only decrypt into different colors, if they were different colors in the encrypted map the oracle originally sent.

To further illuminate: the "random pick after the map is received" ensures that the oracle must send you a map where all adjacent regions have different colors, even though you can't see all the colors yourself. Otherwise, the oracle can't guarantee that you won't ask for the two regions with different colors (because they sent the map before you randomly pick), and if you do ask for those regions, they can't respond in a way that re-assures you the colors are different (because the only way to do so is send keys that decrypt the regions into separate colors, and since they decrypt into the same color, such keys don't exist).

Step 4: Repeat steps 1-3 an unbounded number of times. This is necessary because in a single iteration, there's a chance that the oracle sends a map with two adjacent same-colored regions, but you pick two different regions; so the map is un-3-colorable, but you don't find out. In fact, this is a very high chance if it's a large map and only a single pair of adjacent regions have the same color. But more iterations increase the probability that you do find out indefinitely; with enough iterations, the probability that one of them you get lucky and select the same-colored region is 99.999...%.

Also, each time you repeat steps 1-3, the oracle sends the map with a different coloration. Otherwise, you'd slowly reveal the colors to get the fully-colored map, so it wouldn't be a zero-knowledge proof (two colors in each of two maps with different colors doesn't give you any more information than two colors in one map, so even with unbounded iterations the original coloration isn't revealed). If the map isn't 3-colorable, the randomization doesn't affect the probability: when the oracle randomizes the map, they could choose an entirely different coloration and give two different adjacent regions the same color, but the probability of you randomly choosing those two regions stays the same, so the probability of "getting lucky" in one of enough iterations also stays the same, at 99.999...%.

Aardwolf
0 replies
3h35m

Does the torus one apply to a wrap-around 2D map then? So if the edges don't wrap, the max amount of colors needed is 4, but if the edges do wrap, you could make a map requiring 7 colors?

EDIT: yep looks like it, the leftmost picture under 'snapshots' here is a 2D map of what's on the torus and looking at e.g. the blue band, it touches all 6 others (just barely the cyan and yellow ones with a few pixels of its tips when wrapping between top/bottom): https://demonstrations.wolfram.com/SevenColoringOfATorus/

zamadatix
20 replies
1d

Loved the interactions and flow overall but I'm a bit lost on the zero knowledge proof example. I'm familiar with the concept but I don't follow how the example is one. E.g. "By repeating the process enough times, the probability that you never catch me becomes smaller than, say, getting struck by lightning" doesn't seem to show it's a proof? If I pick a hundred numbers it'll look like I just proved some black box function which happens to be Sin[n] + 0.999999999999 is always positive even though I'd be able to clearly show it negative with the knowledge of the function.

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!

MCSP
7 replies
23h56m

Very glad you enjoyed it!

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 :)

ncruces
4 replies
23h9m

The problem with doing this on a computer is getting us to believe you didn't just make up the colors as we tell you to reveal them (after being “dishonest” before).

spencerflem
3 replies
22h34m

That's the idea at the end about presenting the "sticky notes" as products of primes. Assuming you can't factor the primes yourself, you can be given the whole grid of those products and then interactively ask for the factors or a pair of them. The requestor can't give an alternative factorization (ie. make up a color on the spot) since each number can only be factored one possible way and its easy to verify.

karmakaze
1 replies
19h51m

I really liked this part that shows all the numbers up front, and none of them change during the reveal step.

I think it would present better if introduced as "To show that there's no cheating going on behind the scenes, we will..."

spencerflem
0 replies
17h10m

Yeah I agree it could be presented clearer. Maybe make the analogy of multiplying the factors together and "covering with a post it" more explicit

ncruces
0 replies
11h38m

You're right. That does cover it. I was playing with my kid and I didn't get it at first.

I might use smaller factors then.

zamadatix
0 replies
18h39m

Thanks for the explanation, it seems the definition was slightly different than I assumed it to be previously and that was my missing link to it all making sense. Thanks also for the demonstration to share this info!

Looking forward to the easter egg :)

xg15
0 replies
23h27m

Yeah, I got tripped up by that formulation as well and it's actually something that annoys me with a lot of algorithms that have some properties proven in a limit: It's "easy" (or at least possible) to mathematically prove that in the limit of some variable, the property will hold: If you repeat the challenge increasingly often, the probability of being lied to will get arbitrarily close to zero; for sufficiently large input sizes, some algorithm runs in linear time; with sufficiently large amounts of training data and iterations, some prediction error will become arbitrarily small, etc etc.

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)

esquivalience
5 replies
1d

I think the answer is that each time you reveal the colours, you observe that they are within the set of three colours illustrated at the beginning of the proof. Whichever you reveal, you never find a fourth colour.

This confused me at first.

zamadatix
3 replies
1d

For anyone confused by this response I had edited my comment after reading https://news.ycombinator.com/item?id=40740557 but before equivalence had hit reply and now their reply is left hanging. Sorry esquivalience! To summarize the linked answer on trusting the second dot isn't just randomly assigned: keep the context as physical post-its. Barring something like a matter bending psychic you'd be able to tell the dot under the second post-it was swapped as you made your pick.

That still leaves how to rely on chance of picks for a proof though.

romwell
2 replies
23h59m

It's the same thing as limits in spirit.

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).

zamadatix
1 replies
18h33m

Great description in that "proof" in this context is more referring to the limiting behavior and being able to get to your desired level of arbitrary happiness than necessarily providing a traditional "proof" about it being a certainty within a finite amount of estimation. Thanks.

romwell
0 replies
10h53m

Thanks for the feedback, glad my comment was helpful!

gavindean90
0 replies
14h51m

Reminds me of different colored swans

raincole
2 replies
23h23m

I've got another problem about this zero knowledge proof. The digital version doesn't make a lot of sense to me. It depends on the fact we don't have a fast integer factorization algorithm. But integer factorization is not proven to be NP-complete, and 3-coloring is NP-complete.

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?

dmurray
1 replies
12h2m

I think you're right, and integer-factorization is often used in these examples as a process that is hard to do but easy to verify. There are plenty of other processes that could be substituted in, e.g. reversing SHA256 hashes, that would likely be even less tractable to the target audience.

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".

taejo
0 replies
7h48m

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.

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.

quuxplusone
1 replies
19h29m

OP: Although I'm not really in the target audience for this demo (I already knew all the punchlines), it does occur to me that it might be helpful to readers like the parent-commenter — and even perhaps thought-provoking to us know-it-alls — if you provided a mode at the end of the demo where the graph was in fact not three-colorable, and the computer actually would lie about its being three-colorable. So it would generate a "three-coloring" with a flaw somewhere, and display its representation as products of primes, and you'd get to choose two adjacent products and receive their factors... and so you could see for yourself exactly how long it took for you to luck into catching the computer in one of its lies.

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!)

zamadatix
0 replies
18h40m

For me it was less about the idea of how likely you'd quickly it converges to you almost certainly outing them vs misunderstanding the idea that a zero knowledge proof is about, more or less, the "limit" of the validation behavior to an arbitrary point choosable by the tester not necessarily an actual guarantee you can finitely reach the conclusion.

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.

DoktorL
0 replies
18h45m

E.g. "By repeating the process enough times, the probability that you never catch me becomes smaller than, say, getting struck by lightning" doesn't seem to show it's a proof?

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.

noodlesUK
13 replies
1d1h

Just FYI the “map of the UK” includes the Republic of Ireland, which is very much not part of the UK.

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.

MCSP
8 replies
1d1h

Thanks for pointing this out! Switched to "British Isles" -- update should be percolating now

messe
7 replies
1d1h

The British Isles is also a somewhat controversial term with colonial implications, and it's not used by the government of Ireland[1]. "Britain and Ireland" would be a safer bet, as the map doesn't include any other islands.

https://en.wikipedia.org/wiki/Names_of_the_British_Isles

russellbeattie
4 replies
1d

Diving into Wikipedia, apparently variations of the name "Britain" have been in use since 30BC, and referred to the big island, with the smaller islands grouped with it, e.g. British Isles.

The Irish may not like it, but they're fighting against two millenia of history.

messe
2 replies
23h48m

And it's use in English only comes from the mid 16th and 17th centuries, right around the time that much of Ireland was being colonized by the British.

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.

returningfory2
1 replies
23h43m

Why is "the Ukraine" bad?

returningfory2
0 replies
23h45m

Sure, but more recent history should have a higher weight. It is reasonable that our names for things reflect recent history and current affairs more than ancient history.

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"?

gowld
0 replies
23h52m

Safest to just remove Ireland from the map. It's not needed for the demo.

MCSP
0 replies
23h33m

Switched to "Britain + Ireland"!

HeatrayEnjoyer
2 replies
1d1h

'British Isles' identify the geographic islands.

messe
0 replies
1d

It's not a popular term in Ireland. Britain and Ireland is often preferred, and has less colonial implications.

L3viathan
0 replies
9h19m

These kind of things are also why four colours are actually _not_ always enough, in the real world. Countries can have exclaves :)

baruchel
13 replies
1d2h

Hi, my two cents; you claim "Although mathematicians believe their proof is correct, it is too complex to verify without computer assistance", but I'm not sure "believe" is the correct verb since the proof has been formally verified (see for instance https://github.com/coq-community/fourcolor for a formal verification in Coq).

I 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.

MCSP
10 replies
1d1h

Good point! I'll try to think about a better way to phrase this (happy to hear suggestions)

valenterry
7 replies
1d

Nah, actually I agree with you. What counts as believe and what as fact is rather abitrary. Is 2+2=4 a fact? Is global warming a fact? What about man-made global warming? Ask 100 people whether something is a fact or a believe.

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.

konschubert
5 replies
22h47m

^ Exhibit A why using "believe" is a bad choice of words.

Mathematical poofs are either correct or false. There is no middle ground.

karmakurtisaani
4 replies
22h38m

Well.. there is. Middle ground being a very complex, but somehow convincing argument that no one can reasonably check. There was one of these cases in number theory some years ago, can't remember the details. Proofs can be only true or false, but accepting proofs is in the end a social process.

unclad5968
1 replies
21h55m

A convincing argument that cannot be checked is not a proof. If you want to extend the definition of proofs you're welcome to do that, but for academic mathematics the meaning of proof doesn't contain a middle ground.

valenterry
0 replies
20h47m

Why would it not be a proof?

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?

konschubert
0 replies
21h13m

Proofs can be only true or false

Yes.

The fact that we don't know the truth doesn't mean there isn't one.

lcnPylGDnU4H9OF
0 replies
1d1h

"Although mathematicians have been able to prove this, the proof is too complex to verify without computer assistance."

Or some such.

ifdefdebug
0 replies
21h0m

s/believe/know

gergo_barany
0 replies
1d

That Coq proof is not "without computer assistance". No Coq proof is, as Coq is literally an "assistant" that runs on a computer.

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.

TheNewAndy
0 replies
19h42m

I would consider a proof to be a "repeatable argument". One you could show to someone and expect them to be convinced by it. I think it is a defensible viewpoint that a proof in coq is not 100% convincing. If you think otherwise, then how can you reconcile the existence of falso (a coq verified proof of "false")?

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.

chromy
7 replies
1d1h

The Republic of Ireland (the west most region on the first page) isn't part of the United Kingdom. The term for the group of regions shown is 'the British Isles'. See https://qntm.org/uk While it seems like a trivial distinction the whole thing is somewhat fraught (https://en.wikipedia.org/wiki/The_Troubles).

MCSP
4 replies
1d1h

Whoops! Switched to "British Isles" -- update should be percolating now

darajava
3 replies
23h46m

I prefer the term “Atlantic Archipelago”. The “British Isles” encompassing a non-british sovereign state is contentious. Other good terms are “Britain and Ireland” or the “British-Irish isles”

card_zero
0 replies
23h12m

Yeah, "Britain and Ireland" is straightforward. "Atlantic Archipelago" makes me think you mean the Canary Islands.

bumbledraven
0 replies
10h43m

"British Isles" is the commonly-accepted term, and it doesn't seem to be particularly contentious outside of Ireland. As https://en.wikipedia.org/wiki/British_Isles notes:

As a term, "British Isles" is a geographical name and not a political unit.
MCSP
0 replies
23h14m

Now switched to "Britain + Ireland," thanks!

romwell
1 replies
23h54m

It's about as "trivial" a distinction as considering Crimea (or the entirety of Ukraine, for that matter) a part of Russia.

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).

djeastm
0 replies
22h45m

Naming things is hard

umvi
6 replies
22h44m

Seems easy to intuitively prove that 5 colors is impossible.

In order to need 5 colors, you'd need to construct a graph with 5 nodes where each of the nodes connects to all other nodes, but without any edges crossing: https://imgur.com/U52SFSi

You can just tell after playing around with the graph that it's impossible to move the nodes around on a 2d plane without an edge crossing; you need a 3rd dimension.

tomsmeding
2 replies
22h7m

Why would it be necessary for a graph requiring 5 colours to have a 5-clique (as it's called [1])? The western-US example in the OP [2] has no 4-clique, yet it requires 4 colours. (Try drawing out the incidence graph of the faces, i.e. a vertex is a US state and an edge is two states bordering. Lots of 3-cliques (triangles), but no 4-clique!)

Side note: indeed, 5-cliques are not planar: that is to say, there is no map you can draw that has five regions all bordering each other. This is not too difficult to prove, actually. Proving that 4 colours is enough is a whole different league!

[1]: https://en.wikipedia.org/wiki/Clique_(graph_theory)

[2]: https://www.rahulilango.com/coloring/wus

umvi
1 replies
19h46m

"The western-US example in the OP [2] has no 4-clique, yet it requires 4 colours."

It has something very similar to a 4-clique that can be simplified to a 4-clique for the purposes of the coloring exercise: https://imgur.com/a/oRJBkFp

Or more generally, if you have any hub-and-spoke topology with an odd number of spokes, it can be simplified to a 4-clique and have the same properties.

So I concede that a graph requiring 5 colours doesn't have to have a 5-clique exactly, but it needs something that is either a 5-clique or can be simplified to a 5-clique.

I'm not a graph theory expert, so I'm assuming the complexity of the colors proof comes from the difficulty of being able to simplify complex graphs into simple atoms/cliques.

JohnKemeny
0 replies
51m

Impressive deduction from someone not into graph theory, but what you're saying is actually known as the Hadwiger conjecture. It says that if a graph isn't t-colorable, then it must have K_t as a minor, where the concept of minor is what you mean (perhaps) with "simplified to".

It so happens that planar graphs are K_5 minor free.

This is touching in on extremely deep theory in the graph theory field.

SamBam
2 replies
22h39m

I've always found what happens in the third dimension weird.

A 0-dimensional space needs up to: 1 color.

A 1-dimensional space needs up to: 2 colors.

A 2-dimensional space needs up to: 4 colors.

A 3-dimensional space needs up to: ∞ colors.

I can easily picture why a 3D space has no limit to the number of colors (personally I always imagine color blocks hanging in space connected to every other color block by bendable wires), but I don't quite understand why the pattern is that way.

Halfwhit
1 replies
20h20m

Imagine the colours of a hypercube in 4-dimensional space!

genewitch
0 replies
16h48m

A mantis shrimp told me, quote, "it's alright, i guess, if you're in to that sort of thing"

AndrewOMartin
6 replies
1d2h

Can you add to the FAQ at the end an answer to the question "How do I know you're not just showing me two random colors?"? It's possible this is already addressed and I missed it.

hcs
2 replies
1d1h

You do need to prove that you have assigned the colors before the choice of what to reveal is made, I think. Physically this is guaranteed by the presence of the colors under the post-its (barring dynamic e-paper or something).

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.

MCSP
1 replies
1d1h

You're exactly right. The definition via primes ensures there is only one color consistent with each number (formally, this is called a perfectly binding commitment scheme). Also, here's the link if you want to go back: rahulilango.com/coloring/zk

hcs
0 replies
1d

Thanks! And this is a great exercise, thanks for sharing it.

MCSP
2 replies
1d1h

Thanks for the feedback! As hcs suggests, this is part of the physical post-it assumption. I'll think about ways to make it more clear -- adding an FAQ is a good idea :)

gowld
0 replies
23h54m

All that's missing is more info in the answer to this question:

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".

AndrewOMartin
0 replies
9h29m

Thanks for the response, this and the rest of the comments here helped it finally click for me. I'm "recreationally" familiar with ZKPs, and always found the example of "video recording of alibaba" the most disappointing explanation, and the "I'm not color blind" demonstration the easiest to understand.

This demo was fun, and cool, and short (a undervalued virtue!). Awesome work. Thanks.

joshlk
3 replies
1d1h

That was fun.

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.

tyilo
0 replies
1d

If someone has signed something cryptographically, wouldn't you say that the signature was a proof of someone with the private key signing it? (Even though it is possible to construct a valid signature without the private key - you just have to be very very very lucky)

I guess you also don't like the name Proof of Work.

hcs
0 replies
1d

It might help to think of the sense of "proof" that's synonymous with "trial", rather than a specific formal math sense of proving a theorem from axioms by formal transformations.

fragmede
0 replies
18h29m

zero knowledge corroboration isn't the same thing as a zero knowledge proof. If the provided evidence isn't enough, then you keep iterating until it's proven.

franciscop
3 replies
1d1h

[spoiler alert]

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!

genewitch
1 replies
16h56m

there has to be a layman's explanation. I knew the easiest way to get four colors was to put a split square inside another split square "donut", but the reason you can't force 5 colors is that word "inside". There has to be a nice, tidy "verbal proof" that no matter what, one or more colors will be "trapped" inside at most 3 other colors.

waterproof
0 replies
15h19m

You would think. The easier, five-color theorem proof fits in a few paragraphs but the four-color theorem really resists a simple explanation. Even the simplified 1990s version of the proof (which came ~20 years after the original proof and 100 years after the 5CT proof) required enumeration of hundreds of individual cases.

https://en.m.wikipedia.org/wiki/Four_color_theorem

8organicbits
0 replies
10h2m

It was really enjoyable to try. I got an optimal 4-color map on the first try, so I was over confident. My approach was something like: put a bunch of the 4-color maps next to a long Chile-like thing. When that didn't work I added borders until my device couldn't render it any longer. Very very fun.

SilasX
3 replies
1d

Uh, when you draw the map that requires three colors, I couldn't figure out how to submit it to at least be told it's not good enough. Or if it automatically accepts for a 3-min [1], then it was too hard to make sure that the boundary reached the edge of the screen. (I thought I successfully drew five regions around a point.)

[1] sorry, 3-chromatic or whatever

MCSP
2 replies
23h30m

Hmm, my guess is you're trying to use the box's borders as lines (they don't count, only the lines you draw count). Let me know if that's not the issue. Also, I'll think about ways to make this more clear!

SilasX
0 replies
21h56m

Ah okay -- the second one had a map with the same shape as the border, which I think made me mentally lump the map's border with the box's borders and invalidate the claim that it's looking at the box's borders as part of the map. I also assumed you wouldn't possibly expect someone to have to explicitly draw all their borders when they can piggyback off the box.

Entirely my mistake because I was kind of ignoring everything you said lol

JoshTriplett
0 replies
23h6m

You could automatically "zoom out" what they draw if they get too close to the border.

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.

gpnt
2 replies
18h8m

Warning: very difficult! Skip after trying a lot.

I think "very difficult" is misleading here. It implies there is an answer if you try hard enough.

zild3d
0 replies
8h14m

i appreciate the intention to let you struggle with it on your own for a bit, but not go crazy.

a better experience might be having the warning reveal more after a few attempts, but I don't mind starting with a "warning it's surprisingly tricky"

genewitch
0 replies
16h51m

well, i knew there was no answer and i still tried for 15 minutes. I think that's the point!

dunefox
2 replies
1d1h

In Android using Firefox the button to go to the next challenge doesn't seem to work.

MCSP
1 replies
23h26m

Will look into this. Did it happen on the first page (map of Britain + Ireland)?

dunefox
0 replies
20h0m

Yes.

trirpi
1 replies
23h45m

There seems to be an error in the backtracking algorithm. E.g.: https://imgur.com/a/1miv1AK

MCSP
0 replies
23h37m

Good catch -- I'll look into this!

teddarific
1 replies
22h29m

Wow, this was a lot of fun.

3 was a lot harder than expected — a great exercise for anyone honestly. I'm a math nerd so this was cool visualized!

genewitch
0 replies
16h37m

the easiest 3 is an equilateral triangle split in half with any shape containing it - for 4 split the container perpendicular to the split in the triangle.

|-/|\-|

soneca
1 replies
1d

Great job! I enjoyed going through the steps.

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.

gowld
0 replies
23h53m

ZKP is the subject. The maps part is a helper lemma.

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)

personjerry
1 replies
20h33m

How does the zero-knowledge solution make sense? Can't you just cheat and show me two random different colors whenever I click two post-its?

namjh
0 replies
16h44m

In reality, the entire map should be sent first to the verifier (with colors hid behind the post-it) so if it was a bogus randomly colored map, you may find two adjacent points having same color if you try extremely many(think hundreds or thousands in the website's case) times. If you sufficiently try many times and fail to find the adjacent points, you will convince that the prover have the map which is correctly 3-colored.

Note that the entire map is sent again, shuffled its color each time after you choose the two points.

nirolo
1 replies
21h34m

You might want to get into touch with some museums on science topics to see if they are up to show it. I live in Germany at the moment and know of at least two MINT focused museums that let visitors engage a lot with their (sometimes digital) exhibits and this here checks all the boxes to make a great exhibit.

Very well done, I'll try to see if my children will enjoy that already too.

wrsh07
0 replies
21h25m

Absolutely!! Talk to MoMath in NYC too

I'm happy to find a contact there if you want

NegativeLatency
1 replies
19h45m

Something about 4 colors makes sense to me intuitively because you've got 0 or 1 color for each of the two cartesian axes (2 * 2 = 4). Not sure there's anything behind that though.

zem
0 replies
1d2h

great work!

your_friend
0 replies
22h24m

How cool! I didn’t expect it will end up with ZK proofs that I was curious about for a long time. (After reading it I still don’t quite get the details of how they are working tho)

yochem
0 replies
8h34m

You mention that this problem has overlap with training neural nets. Could you link some further reading for this? :)

windowshopping
0 replies
1d

I went in skeptical and got completely hooked. Well played. Very neat thing to build. Wish more math were taught creatively like this.

vavooom
0 replies
1d

that was fun :)

tzs
0 replies
19h38m

Step 1. I put a <purple circle>, <blue circle>, or <red circle> color dot on each region, but hide it under a post-it

Step 2. You click any two bordering regions, and I pull off their post-its

Step 3. You check that the revealed colors are different

I would add explicitly in step 1 that you tell me what 3 colors you used, and in step 3 that I check that the revealed colors are different from each other and are both from that set of 3. Similar in the explanation of why this should convince me.

sverona
0 replies
1d

This is cute. You should flag the "I claim that three colors suffice" map if the user actually 3-colors it. At least, I think I did...

stop50
0 replies
1d2h

Very nice. I had no problems playing it.

snthpy
0 replies
10h34m

Nice!

I knew the 4-colour theorem but the zero knowledge proof illustration was great. I didn't get it initially but the FAQ cleared it up and I felt like I learned something as it wasn't obvious on the first look.

sn41
0 replies
18h47m

Just a quick note: Rahul Ilango is a phenomenal theoretical CS researcher who has made great progress towards understanding the "Minimum Circuit Size Problem" [MCSP], long believed to be, but not yet proven, NP hard. Needless to add, "the username checks out".

segfaltnh
0 replies
7h14m

Well done, enjoyed this a lot.

sakras
0 replies
1d1h

This was fun, I went into this thinking "Ha I already know this theorem" but came out learning something about zero knowledge proofs!

riffraff
0 replies
12m

I loved this, and, like others, walked through it with my two kids (7,9). They have up at the last page but they seemed to enjoy the process nonetheless!

Good job, would love to see more.

poopcat
0 replies
19h36m

Had a great time with this! Great break to get my mental gears moving

passwordoops
0 replies
19h41m

So addictive! And it's great how you tie it in to the greater mathematical concept. I'm loving it!!

next_xibalba
0 replies
16h57m

Although I still didn't fully understand the relation between zero knowledge proofs and the post-it example, this game is just kind of fun in its own right!

neuron-enix
0 replies
23h1m

There goes my 2hrs of sleep, trying to solve feeling that I was close to solving, only to see myself draw shapes that I have never seen or imagined in my life.

Well in the end it was fun, but the warning is very misleading at least from a game perspective. I have played games at the same level but it certainly wasnt this hard, haha...

But hey, saying that it was difficult, was the only thing that kept me going for 2hrs, only to be annoyed and have a face palm moment after seeing the answer.

Nonetheless it's good post

namjh
0 replies
16h38m

Great work! I really enjoyed the interactivity. Actually I already was aware of the concept of zero-knowledge proof from the wonderful article by ZCash(which is a privacy-oriented cryptocurrency) core developer Matthew Green, worth to check it out: https://blog.cryptographyengineering.com/2014/11/27/zero-kno...

My two cents of the ZKP illustration is that directly using hashes are more likely to convince "computer-friendly" people to introduce the commitment scheme.

mbivert
0 replies
1d1h

Enjoyed the tutorial very much, thanks.

As a suggestion, I would dearly enjoy a follow-up rigorously connecting those visual, intuitive ideas to actual mathematics.

js98
0 replies
1d1h

Nice work! I spent a bit too much time creating a map with 5 colors… ;)

jostylr
0 replies
22h4m

That was enjoyable. You could submit this to the summer of math exposition: https://some.3b1b.co/

hooby
0 replies
9h12m

So, there was this one question "Can every map be colored with just 4 colors?"...

And there I sit, knowing that every map of CONTIGUOUS territories can be colored with 4 colors - but on real world maps, there are enclaves - little islands that belong to a country that they have not connection to. And if those shall have the same color as their parent country, then 4 colors is not enough...

So I pick the answer "NO".

you are wrong!!!!! every map can be colored with 4 colors! it has been proven!!!!!
hgyjnbdet
0 replies
12h39m

Spent way too long on the five colour thing refusing to skip. You always have to surround one colour which then protects it. You simply can't touch four colours at once. Then I skipped it and found out it was impossible, FML.

gsuuon
0 replies
9m

This is awesome and I hope in-general that a lot more education is done this way, especially with complicated concepts. I wonder if this sort of interactive toy explanation is currently used in classrooms?

gkoberger
0 replies
23h22m

This was one of the cooler teaching examples I've ever played with... awesome job! Appreciate the warning that the 5 color map is "very difficult". It felt easy enough, and I would have spent an hour on it!

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!

gexaha
0 replies
5h27m

Nice puzzle, congrats! I also like this part of maths, and there's a related concept of Snark graphs.

https://en.wikipedia.org/wiki/Snark_(graph_theory)

First is that "One of the equivalent forms of the four color theorem is that every snark is a non-planar graph". Second, is as strengthened form of the four color theorem: "every snark has the Petersen graph as a minor", which is kind of proven (already 25 years ago), but still lacks 1 paper: https://thomas.math.gatech.edu/FC/generalize.html https://math.stackexchange.com/questions/3692582/what-is-the...

And another related concept is of nowhere-zero flows, and even more stronger conjecture that "every bridgeless graph with no Petersen minor has a nowhere zero 4-flow". https://en.wikipedia.org/wiki/Nowhere-zero_flow

ehershey
0 replies
14h48m

Wow what a fun little interesting time. My wife and I made it to the end on mobile!

dylanjcastillo
0 replies
23h34m

Thanks for sharing. This was instructive and fun in equal parts

ceva
0 replies
8h32m

Would be nice to Introduce another continent like Europe :) it looks really nice tho!

barbariangrunge
0 replies
18h23m

This is lovely. The Ux isn’t my favourite when it’s time to draw but it’s pretty great besides that

andrei-akopian
0 replies
23h44m

1. Nice site, bookmarked to give it to people. 2. You are a very bad and annoying person ;)

aib
0 replies
20h33m

Ahh, very nice. It was fun to rediscover/relearn some of these things through this game.

Very nice wording on the 5-color challenge! I think it was the perfect balance.

One thing I was missing was the ability to move the points already on canvas. I assume you already considered, though. (As well as right-click-to-remove?)

PUSH_AX
0 replies
10h43m

Thanks for taking me on that journey!

OmarShehata
0 replies
1d1h

I love this! I'd for this to be a more typical experience in math class

(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)

MrZander
0 replies
18h29m

I know that it is impossible, but it was fun to try to make a 5 color map work. That being said, is this a bug? https://imgur.com/a/zbkYg9j

I can't seem to wrap my head around why this isn't 3 colors.

ModernMech
0 replies
23h9m

It's very fun!

Only thing I would change is to make it so clicking on the picture doesn't trigger a text select, it was hard to play because a context menu kept popping up every time I changed map color.

JohnMakin
0 replies
20h51m

This gave me PTSD flashbacks to an extremely difficult computational geometry course I took once, but this is cool.

Guvante
0 replies
16h31m

Fun fact, one of the reasons the four color problem is hard to prove is there isn't an algorithm that can color a map in four colors.

Well beyond effectively trivial ones where you try over and over again.

But the algorithm for coloring with five is pretty easy (relatively speaking still involves fun graph theory)