How does Tupper’s self-referential formula work?

[I write this post with a certain degree of embarrassment, because in the end it turns out (1) to be more simple than I anticipated, and (2) already done before, as I could have found if I had internet access when I did this. :-)]

The so-called “Tupper’s self-referential formula” is the following, due to Jeff Tupper.

Graph the set of all points such that

in the region

where N is the following 544-digit integer:
48584506361897134235820959624942020445814005879832445494830930850619
34704708809928450644769865524364849997247024915119110411605739177407
85691975432657185544205721044573588368182982375413963433822519945219
16512843483329051311931999535024137587652392648746133949068701305622
95813219481113685339535565290850023875092856892694555974281546386510
73004910672305893358605254409666435126534936364395712556569593681518
43348576052669401612512669514215505395545191537854575257565907405401
57929001765967965480064427829131488548259914721248506352686630476300

The result is the following graph:

Figure 1: The graph of the formula, in some obscure region, is a picture of the formula itself.

Whoa. How does this work?

At first sight this is rather too incredible for words.

But after a few moments we can begin to guess what is going on, and see that—while clever—this is perhaps not so extraordinary after all. So let us calmly try to reverse-engineer this feat.

The first thing we notice is the size of N. As the “formula” is small and innocuous (just a few exponents, remainders and floors, no “unnatural” functions), and N is so disconcertingly huge, it is reasonable to guess that all the actual information that produces the graph is contained in N itself. This would mean that the formula is like a bare-bones “program”, and N is the “input” that somehow encodes the image that is the graph.

To understand the encoding, we must turn to the formula.

First, using the fact that , we see that the formula (relation, more properly) depends on and only through and . So the graph in each 1×1 square (with vertices having integer coordinates) is the same as at its bottom-left endpoint.

A part of Figure 1 enlarged, with grid turned on

(Just a sanity check at this point: this observation means that Figure 1 is essentially a 106×17 bitmap. 106×17=1802, and has about bits, which is roughly as many bits as the image. So we have another reason for our suspicion that N encodes the image.)

Accordingly, we can restrict our attention to integer values for and . Further, is the same as (I wonder why the obfuscation was there?), so we can simplify the formula:

We also notice a dependence on the value of y mod 17, so let’s write , where the remainder satisfies . So our graph is the set of all points for which

which is the same as saying that

is an odd number.

Note that the region in which the plotting is supposed to be done has a range of only 17 integers for , so remains the same for all (except possibly off by 1) while ranges from to . For a fixed value of , then, different values of correspond to different .

In case you haven’t noticed yet,

being odd is equivalent to the (17x+r)^th bit of (counting from the rightmost bit as the 0^th) being 1. So in the graph, the pixel at is 1 iff the bit at position (17x+r) in is 1: is merely a list of bits of the image! It’s a rather straightforward encoding after all: it just reads off the bits of the image, reading each column upwards, and going through the columns left-to-right.

In hindsight, we can see that this is in fact the natural encoding. If you were given a bitmap image ‘q’ got by concatenating each column (or row), and wanted to find a mathematical relation which for (x,r) was 1 iff the image had a bit at that point, this is more or less the relation you would come up with (for some orientation of the axes). Tupper’s further trick here is in folding the value of q into the value of y itself as y=17q+r.

The “mistake”

Actually, the value of N that I included above is one I found myself. Every source I’ve seen (examples: MathWorld, Wikipedia, “Implementation” webpage (doesn’t work), blog with code, etc., etc.) instead mentions a different constant for N, namely the 543-digit integer (call it N’)
96093937991895888497167296212785275471500433966012930665150551927170
28023952664246896428421743507181212671537827706233559932372808741443
07891325963941337723487857735749823926629715517173716995165232890538
22161240323885586618401323558513604882869333790249145422928866708109
61844960917051834540678277315517054053816273809676025656250169814820
83418783163849115590225610003652351370343874461848378737238198224849
86346503315941005497470059313833922649724946175154572836670236974546
1014655997933798537483143786841806593422227898388722980000748404719.

Graphing the function on the range gives the following figure:

What Tupper's formula as described in every source actually graphs

It is upside down. This is of course an entirely trivial goofup, probably based on the mathematical convention (the y-axis goes upwards) differing from computers’ screen convention (the y-axis goes downwards), but there’s something slightly comic about spending all this effort devising a very clever trick, but failing to ensure it’s not upside down. (‘The scene in Not the Nine O’clock News in which an elderly, exhausted monk unbent himself after years of illuminating the first page of the Bible, only to see that he had written, gloriously, “Benesis”’.) But that’s not a big deal, mistakes happen. What I find strange is that hundreds of people have been quoting and referencing this, without ever bothering to check it for themselves, and those who did bother and presumably noticed something amiss (e.g. here, Reddit, Hacker News,…) merely changed their code to “make it work” (a la voodoo programming) rather than confidently declaring that the constant was the wrong one, or at least specifying that the y-axis needs to go downwards. (Even the upside-down constant isn’t always consistently described: Stan Wagon’s nice list of favourite puzzles, mentioned as a source on MathWorld, calls it a 541-digit integer but prints all 543 digits, while the otherwise excellent book Experimental Mathematics in Action (by David H. Bailey, Jonathan M. Borwein, Neil J. Calkin, Roland Girgensohn, D. Russell Luke, and Victor H. Moll) calls it a 541-digit integer and actually cuts off the last two digits, which results in an image that looks like garbage.)

It’s remarkable that no one would check something so easy to check, even in these days when nearly any computer user has access to tools that make it easy. Maybe they are using the wrong tools? Something as simple as this will work:

#!/usr/bin/env python
N = 96093937991895888497# Truncated, but you can paste the full constant here
H = 17
W = 106
import sys
for y in range(N+H-1, N-1, -1):
    for x in range(W):
        if 0.5 < ((y//H) // (2**(H*x + y%H))) % 2: sys.stdout.write('*')
        else: sys.stdout.write(' ')
    sys.stdout.write('\n')

producing

*** *                                                               ***  *** *                 ***        
*   *                                                               *      * *                   *        
*  *                                                                *  * * *  *                  *     ***
*  *      *                                                         *  * * *  *                  *       *
*  *     *                                                          * *  * *  *                  *      * 
* *      *                                                          * *  * *   *                 *     *  
* * ****                                                       **** * ** * *   * ***   **  * * * * *    **
* *    *                                                          * *      *   * *  * *  * * * * *  *     
* *   *                                                          *  * **** *   * *  * *  * * * * *   * ***
* *  *     *       * *** *** *                   *** ***        *   *      *   * ***   **   * ** *  *     
* * *  *   *      *  *     * *                   *     *       *  * *   *  *   * *               * *   ***
* *  **   *       *  *   * *  *                  *     *        **  *  *   *   * *               *      * 
*  *      *   * *    *  *  *  * *** *** * * *    * * * *  * *       * * *  *  *                  *      * 
*  *      *   * *    * * * *  * * * * * * * *    *  *  *  * *       * * *  *  *                  *      * 
*  *      *  *  *    * * * *  * *** ***  **** ** * * * * *  * **    *      *  *                  *      **
*   *      * *  *    *     * *  *                *     * *  *       *      * *                   *        
*   *      * ** *    *     * *  *                *     * ** *                *                   *        

which (if you squint) you can see is the formula upside-down. (The appendix below contains a better version that uses matplotlib and was used to generate the images in the post.)

Author, Background

Apparently Tupper included the formula in his 2001 SIGGRAPH paper on graphing methods, merely as an example of the kind of graphs his method can handle. (And he didn’t call it self-referential.) I’m pleased to discover that Tupper is the author of GrafEq which I remember trying some ten-odd years ago. It was at that time the best graphing software in certain respects (precision, correctness, etc.), and as far as I can tell, it still is. I hope its ideas get incorporated in all graphing programs in the future. In the paper, Tupper writes:

Many students currently studying mathematics are using automated graphing tools that produce incorrect graphs for some of the equations discussed in their curricula. I have written this paper in the hope that, in the future, more students will have access to graphing tools that work correctly.

The gallery page for GrafEq contains many other ingenious exploits that use implicit relations to get beautiful graphs. The one closest to the formula here is probably Decimal Squares, but many of the others are truly mind-boggling.

Tupperware and beyond

More bitmaps

Now that we see that graphing Tupper’s formula is just a “program” to decode a bitmap, it follows that the formula is also “universal”: for any bitmap image (of height at most 17 pixels), there exists an integer N such that graphing Tupper’s formula on the range 0 < x < width-of-image, N < y < N+17 produces the image. All possible images are contained in the graph of Tupper’s formula. For instance, N=6064344935827571835614778444061589919313891311 gives this:

N = 114461430485773228734207468860322536020810361768206377253515727288242
0531935654859544357377819147833060031564802551634741838422783909813925261
4970555108049338384907856705947495396329029490965408180552069582726103040 gives this, a different kind of “self-reference”:

And so on. The appendix below contains a program that can read (some) .bmp files and generate corresponding N.

Self-reference

This also means that the formula is not self-referential at all (though one may argue it’s something better), any more than a program that prints all possible strings can be called a quine. So in the spirit of actual self-reference, here is

Exercise 1 (easy): Find N such that the graph of Tupper’s formula (in the range given by N) is a picture of N, or prove that it is impossible.

Exercise 2 (hard): Find N such that the graph of Tupper’s formula (in the range given by N) is a picture of , or prove that it is impossible.

Pixellation

It is easy to get a similar formula with higher resolution. For instance, the formula

graphed in the region and for a certain 6859-digit integer, produces the following graph:

More height means more resolution. (More care would avoid the bitmap artifacts.)

Generalisation

What we have so far is limited to images of a fixed height. So finally,
Exercise 3 (not so hard!): Find a variant of Tupper’s formula whose graph contains all W×H images, for all W and H.

Acknowledgments

I was going to mention Mohan’s post on Rubel’s Universal Differential Equation for inspiration (and his mentions of Tupper’s formula for provocation), but on finding it again, I notice that (1) it already mentions an earlier post by him on precisely this Tupper’s formula, and (2) its style is unmatchable, anyway. :p

Appendix

• plot-tupper.py: Plots Tupper’s formula using matplotlib.
• plot-old-full.py: Older version that prints to terminal or file, if matplotlib is not available or desired
• bmp2tupper.py: Reads a bitmap file (works with 32-bpp BMP files, not all) and generates N.