Bossy Lobster

A blog by Danny Hermes; musing on tech, mathematics, etc.

Edit on GitHub

Conway's Topograph Part 3

This is the second (continued from Part 2) in a series of three blog posts. In the following we'll investigate a few properties of an object called Conway's topograph. John Conway conjured up a way to understand a binary quadratic form – a very important algebraic object – in a geometric context. This is by no means original work, just my interpretation of some key points from his The Sensual (Quadratic) FormAMZN Affiliate Ad that I'll need for some other posts.


Definition:

For the form f(x,y)=ax2+hxy+by2,f(x, y) = a x^2 + h x y + b y^2, we define the discriminant as the value ab(12h)2ab - \left(\frac{1}{2}h\right)^2. \blacksquare

The base (1,0)(1, 0) and (0,1)(0, 1) take values aa and bb on the form in the Definition above and are part of a sequence with common difference hh. In fact, if we know the values a,a', bb' and the difference hh' at any base (edge in the topograph), the value ab(12h)2a'b' - \left(\frac{1}{2}h'\right)^2 is independent of the base and the direction (left or right) which determines the sign of hh' and hence equal to the discriminant. To see this, first note the sign of hh' is immaterial since it is squared. Also, consider the two other bases (edges) in the superbase. As in the proof of the climbing lemma, one base takes values a=aa' = a and b=a+b+hb' = a + b + h with common difference h=2a+hh' = 2a + h which gives

ab(12h)2=a(a+b+h)14(2a+h)2=a2+ab+ah(a2+ah+14h2)=ab(12h)2.\begin{aligned} a'b' - \left(\frac{1}{2}h'\right)^2 &= a(a + b + h) - \frac{1}{4}\left(2a + h\right)^2 \\ &= a^2 + a b + a h - \left(a^2 + a h + \frac{1}{4} h^2\right) \\ &= ab - \left(\frac{1}{2}h\right)^2. \end{aligned}

Similarly the other base in the given superbase gives

ab(12h)2=(a+b+h)b14(2b+h)2=b2+ab+bh(b2+bh+14h2)=ab(12h)2.\begin{aligned} a'b' - \left(\frac{1}{2}h'\right)^2 &= (a + b + h)b - \frac{1}{4}\left(2b + h\right)^2 \\ &= b^2 + a b + b h - \left(b^2 + b h + \frac{1}{4} h^2\right) \\ &= ab - \left(\frac{1}{2}h\right)^2. \end{aligned}

Having showed that there are no cycles when starting from a given superbase, our work in understanding the topographis not complete. We haven't actually showed that we can get from one superbase to any other superbases within the topograph. To show this, we'll use the discriminant and the following.

Definition:

A superbase WW is called a well if all the edges at WW point away from WW. \blacksquare

Conway Well

Notice a well is dependent on the values, hence depends on the form ff. In a positive-valued topograph, we may find a well by traveling along the topograph in the opposite direction of the edges. Eventually, we must encounter a superbase where all arrows point out (as above), leaving us nowhere to travel and thus becoming our well. This is because, assuming the topograph is positive-valued, we can only decrease in value for so long (eventually the values must approach the minimum).

Lemma: (The Well Lemma)

For a positive-valued form ff and a well W,W, the three values ff takes on the faces in WW are the smallest values that ff takes on the topograph.

Proof:

Using the labels from the well in the definition above, the Arithmetic Progression Rule for our differences gives

2α=b+ca,2β=c+ab,2γ=a+bc2\alpha = b + c - a, \quad 2\beta = c + a - b, \quad 2\gamma = a + b - c

and solving,

a=β+γ,b=α+γ,c=β+α.a = \beta + \gamma, \quad b = \alpha + \gamma, \quad c = \beta + \alpha.

Let the superbase W={e1,e2,e3}W = \left\{e_1, e_2, e_3\right\}. Since WW is a superbase, we may write any vector as

v=m1e1+m2e2+m3e3v = m_1 e_1 + m_2 e_2 + m_3 e_3

for m1,m_1, m2,m_2, m3Zm_3 \in \mathbf{Z}. Also due to the fact that WW is a superbase, e1+e2+e3=(0,0)e_1 + e_2 + e_3 = (0, 0) and so we may also write

v=(m1k)e1+(m2k)e2+(m3k)e3v = (m_1 - k) e_1 + (m_2 - k) e_2 + (m_3 - k) e_3

for kZk \in \mathbf{Z}. From this it is clear only the differences of the mim_i matter. With this as our inspiration we write

f(v)=α(m2m3)2+β(m1m3)2+γ(m1m2)2,f(v) = \alpha(m_2 - m_3)^2 + \beta(m_1 - m_3)^2 + \gamma(m_1 - m_2)^2,

a formula discovered by Selling.

To verify this, notice both sides of the equation are quadratic forms in vv and

f(e1)=a=β+γ=α02+β12+γ12f(e2)=b=α+γ=α12+β02+γ(1)2f(e3)=c=β+α=α(1)2+β(1)2+γ02.\begin{aligned} f(e_1) = a &= \beta + \gamma = \alpha \cdot 0^2 + \beta \cdot 1^2 + \gamma \cdot 1^2 \\ f(e_2) = b &= \alpha + \gamma = \alpha \cdot 1^2 + \beta \cdot 0^2 + \gamma \cdot (-1)^2 \\ f(e_3) = c &= \beta + \alpha = \alpha \cdot (-1)^2 + \beta \cdot (-1)^2 + \gamma \cdot 0^2. \end{aligned}

hence they must be equal since both sides are quadratics that agree on more than two points.

If two of the mim_i are equal, then vv must be an integral multiple of the third vector, hence the value f(v)f(v) will be at least as largeas the value of ff on the third vector. If not, all the differences must be nonzero (hence greater than or equal to 11 in absolute value, since integers), thus

f(v)α12+β12+γ12f(v) \geq \alpha \cdot 1^2 + \beta \cdot 1^2 + \gamma \cdot 1^2

which is greater than or equal to each of a=β+γ,a = \beta + \gamma, b=α+γ,b = \alpha + \gamma, and c=β+αc = \beta + \alpha since all of α,\alpha, β,\beta, and γ\gamma are non-negative. \blacksquare

Corollary:

The topograph is connected; one may travel along the topograph from any given superbase to any other.

Proof:

Using the same quadratic form ff as we did to show the topograph had no cycles, we can show it is connected. Any arbitrary superbase is on the topograph, hence must be in some connected component of the topograph, but there may be more than one component. Since ff is positive-valued, we must have some well in this component. But, by the above, the values at a well must be the absolute lowest values ff takes on the topograph. This implies the well must take the values 1,1, 1,1, 11 and shows all superbases must be in the same component. \blacksquare

From this point, we will concentrate on a special type of form relevant to our discussion. For a form ff which takes both positive and negative values, but never 0,0, the topograph has a special path thatseparates the which separates the faces where takes a positive value and those where ff takes a negative value.

Claim:

If a form ff takes both positive and negative values, but not zero, then there is a unique path of connected edges separating the positive and negative values. What's more, the values that occur on this river do so periodically.

Proof:

Since the topograph is connected, there must be some edge where positive and negative values meet. As we proceed along adjacent edges, we can choose to follow a path of edges which will separate positive and negative (each subsequent value must be positive or negative, allowing us to "turn" left or right).

Conway River

On first sight, there is no reason that this path should be unique. However, with the climbing lemma in mind, starting on the positive side of the path and moving away from the negative values, we must have only positive values. Using the logic of the climbing lemma instead with negative values, we similarly see that starting on the negative side and more away from the positive values will yield all negative numbers below the path. Hence nowhere above the path can positive and negative values meet and similarly below. Thus the path must be unique.

To show this path is periodic, we must utilize the discriminant. For each edge along the path, we have some positive value aa and a negative bb (by definition of the path) and the common difference hh. Thus the determinant DD must be negative since the product abab is, hence

D=ab+(12h)2.\left|D\right| = \left|ab\right| + \left(\frac{1}{2}h\right)^2.

Thus, both (12h)2\left(\frac{1}{2}h\right)^2 and ab\left|ab\right| are bounded by D\left|D\right|. So a,a, bb and hh are bounded by D\left|D\right|. Thus we have finitely many possible triples (a,b,h),(a, b, h), hence some value must be repeated in the path. This forces the path to be periodic since the triple starting from one triple (a,b,h)(a, b, h) determines next triple along the path and hence the entire path.

This path is so crucial that we give it it's own name.

Definition:

If a form ff takes both positive and negative values, but not zero, we call the path separating the positive and negative values the river. \blacksquare

Thanks for reading, I'll make use of all this in a few days!

Update 1:

This material is intentionally aimed at an intermediate (think college freshman/high school senior) audience. One can go deeper with it, and I'd love to get more technical off the post.

Update 2:

All images were created with the tikz LaTeX library and can be compiled with native LaTeX if pgf is installed.

Comments