Is there an example of converting a mathematical statement into a three color mapping? https://youtu.be/5ovdoxnfFVc?t=1118
At this point, prof Wigderson says it is easy to go from a mathematical statement to a graph coloring problem. The video does not provide an example of this, and a brief read of the referred papers just confused me further.
For example, Is there a simple way to state the infinitude of primes as a graph coloring problem?
Thank you.
 A: The kind of mathematical statement you can convert into a three-coloring problem has the form

There exists a proof of that there exist infinitely many primes, in the formal system Peano Arithmetic, using at most 1,000,000 symbols.

We can replace "there exist infinitely many primes" with another mathematical statement, "Peano Arithmetic" with another formal system, and "1,000,000" with another number.
This is done by a step-by-step conversion process.
(1) Write a computer program that inputs a proof of length at most 1,000,000 in your formal system, and outputs "True" if it follows the rules of deduction and proves your desired statement, and "False" if the proof is invalid in any way.
For many formal systems, such computer programs actually exist and are used by computer scientists and mathematicians.
(2) Simulate the computer program on a circuit made of AND, OR, and NOT gates.
This is closely related to, but not quite the same as, what we have to do to build computers that actually run our computer programs. One big difference is that transistors in a computer can be used more than once, inputting and outputting different values, but in a circuit each gate can be used once. This can be handled by just making as many copies of a gate as needed.
(3) Replace each AND, OR, and NOT gate by an appropriate "gadget" piece of the graph, so that 3-colorings will flow through the graph just the way true and false values flow through the circuit.
The final size of the graph will end up being, for a reasonable circuit, at most a polynomial in the starting value N=1,000,000. But it's clear from all the steps we had to do that it might be a really big polynomial, and the graph is not going to be small enough that it will function as a reasonable example.
