MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

6 edited tags
5 deleted 274 characters in body

Proofs without words'' is a popular column in the Mathematics magazine.

Question: What would be a nice way to characterize which assertions have such visual proofs? What definitions would one need?

I suspect that in order to make this question precise, one will have to define a computational model for the visual verifier'' and postulate the possibility of a visual proof if there is a quick verification algorithm, and the visual proof itself is short.

Rev. 1:

To elaborate: the intriguing and essential feature of a visual proof is that the proof can be read'' or verified rather quickly using primitive operations that are different than those involved in reading and verifying textual proofs (e.g., area comparison or counting). These are operations that are native and quick for the visual system. (There may be other operations that could be used as well: color, texture, shape, or any other visual cue could be part of the repertoire.) It is not necessary that for an assertion to have a visual proof, that it involve inequalities, though this feature does lend itself relatively easily to a direct visual proof.

Thus, one could frame the notion of a visual proof as follows: An assertion has a visual proof if there is a map from the space of assertions (strings over an alphabet) to the space of pictures (strings over a visual alphabet) such that assuming a particular computational model of a visual verifier, there is an algorithm for reading the visual proof that is faster than the best one for reading the textual proof.

The computational model of the verifier allows one to specify what visual primitives may be used and how costly'' they are in the algorithm. (For example, if a proof is mapped to a picture that only uses length of a line to represent elements in the proof, then reading the proof will likely be slow, whereas if it uses length and area, the proof might be immediately verified.)

This leads to a sort of complexity theory of visualizations. In fact, it implies that visualization is a special case of a more general activity: re-encoding a given problem so that one can exploit a fast algorithm.

There may be some assertions that have no maps that can be verified quicker than the original proof. What might these be?

I hope this provides a better context for my question.

Rev. 2:

(Meta question: If I accept an answer, will that essentially close this topic? Will others be less likely to see this question and respond? Is there any other way---other than upvoting---to reward the current answers without accepting any of them? Thanks MO.)

4 added 274 characters in body

Proofs without words'' is a popular column in the Mathematics magazine.

Question: What would be a nice way to characterize which assertions have such visual proofs? What definitions would one need?

I suspect that in order to make this question precise, one will have to define a computational model for the visual verifier'' and postulate the possibility of a visual proof if there is a quick verification algorithm, and the visual proof itself is short.

Rev. 1:

To elaborate: the intriguing and essential feature of a visual proof is that the proof can be read'' or verified rather quickly using primitive operations that are different than those involved in reading and verifying textual proofs (e.g., area comparison or counting). These are operations that are native and quick for the visual system. (There may be other operations that could be used as well: color, texture, shape, or any other visual cue could be part of the repertoire.) It is not necessary that for an assertion to have a visual proof, that it involve inequalities, though this feature does lend itself relatively easily to a direct visual proof.

Thus, one could frame the notion of a visual proof as follows: An assertion has a visual proof if there is a map from the space of assertions (strings over an alphabet) to the space of pictures (strings over a visual alphabet) such that assuming a particular computational model of a visual verifier, there is an algorithm for reading the visual proof that is faster than the best one for reading the textual proof.

The computational model of the verifier allows one to specify what visual primitives may be used and how costly'' they are in the algorithm. (For example, if a proof is mapped to a picture that only uses length of a line to represent elements in the proof, then reading the proof will likely be slow, whereas if it uses length and area, the proof might be immediately verified.)

This leads to a sort of complexity theory of visualizations. In fact, it implies that visualization is a special case of a more general activity: re-encoding a given problem so that one can exploit a fast algorithm.

There may be some assertions that have no maps that can be verified quicker than the original proof. What might these be?

I hope this provides a better context for my question.