Two points determine a line, three a quadratic — what has that got to do with CDs?

July 24, 2014 by . 4 comments

In this post I describe how simple facts about polynomials are applied in correcting errors, for example scratches on compact disks.  The same technique is used in many other places, e.g. in the 2-dimensional QuickResponse  bar codes.


The two facts from algebra that we need are:

Theorem 1. A polynomial of degree \(n\) has at most \(n\) zeros.

Theorem 2. If \((x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\) are \(n\) points on the \(xy\)-plane such that \(x_i\neq x_j\) whenever \(i\neq j\), then there is a unique polynomial \(f(x)\) of degree \(<n\) such that \(f(x_i)=y_i\) for all \(i\).

So, if \(n=2\), we want the polynomial \(f(x)\) to be linear. In that case, the graph \(y=f(x)\) will be the line passing through the points \((x_1,y_1)\) and \((x_2,y_2)\). Similarly, when \(n=3\) we want the polynomial to be (at most) quadratic, and we want its graph to pass through the given three points. Finding the coefficients of such a quadratic is not too arduous an exercise in linear systems of equations. For general \(n\) there is a known formula for the polynomial \(f(x)\) called Lagrange’s interpolation polynomial . The uniqueness of such a polynomial follows from Theorem 1. If \(f_1(x)\) and \(f_2(x)\) were two different polynomials of degree \(<n\) passing through all these \(n\) points, then their difference \(f_1(x)-f_2(x)\) is also of degree \(<n\) and vanishes at all the points \(x_i, i=1,2,\ldots,n\), which is impossible by Theorem 1.

Extending a message using a polynomial

The applications I discuss are about communication. We have two parties, a transmitter and a receiver. The transmitter wants to send a message to the receiver. We assume that they have in advance agreed upon a method of coding the messages to sequences of numbers \(y_1,y_2,\ldots,y_k\) for some natural number \(k\). The simplest way of communicating would be for the transmitter to simply write this list of numbers to a channel that the receiver can later read. The channel could be something like a note that you pass to a classmate or it could be compact disk, where the transmitter just writes the numbers. It could be something fancier like a radio frequency band, or an optical fiber, but we ignore the physical nature of the channel here.

If everything goes well, the receiver can read the message correctly. But, they may misread one or more of the numbers. Or, one of the numbers may get smeared and become illegible while the note is exchanging hands. What to do? The basic idea is to add some redundancy to the message. We seek to extend the message from \(k\) numbers to \(n\) numbers, \(n>k\), in such a way that the receiver can recover from a few such mishaps. A useful way of doing this is to:

  • Agree in advance on a sequence of \(n\) values for \(x\)-coordinates \(x_1,\ldots,x_n\).
  • View the message \(y_1,y_2,\ldots,y_k\) as a sequence of \(k\) points $$(x_1,y_1), (x_2,y_2),\ldots, (x_k,y_k).$$
  • Find the unique polynomial \(f(x)\) of degree \(<k\) passing through all these \(k\) points.
  • Extend the message to \(y_1,y_2,\ldots,y_n\) in such a way that \(y_i=f(x_i)\) for all \(i=1,2,\ldots,n\). Note that the actual ‘payload’ message consists of the \(k\) first numbers, the remaining \(r=n-k\) are the redundant numbers.

Toy Example #1 – recovery from an illegible number

In the Figures below I always use \(x_1=1,x_2=2,\ldots,x_n=n\) for simplicity. Let us consider as an example the case \(k=2, n=3\), so our polynomials will always have degree \(\le1\), and their graphs are thus lines. Let us further select the message to be \((y_1,y_2)=(3,4)\). In this case the polynomial \(f(x)=x+2\) as \(f(1)=y_1\) and \(f(2)=y_2\). As \(f(3)=5\) the extended message is then \((y_1,y_2,y_3)=(3,4,5)\). In the figure below the payload part of the message is formed by the \(y\)-coordinates of the black dots and the \(y\)-coordinates of the red dot(s) are there for redundancy. I also include the entire graph of \(f(x)\) to make what follows clearer.


How does this minimum amount of redundancy help? Consider the scenario when the second numbers was, indeed, smeared and the receiver could only read the sequence as \((3,?,5)\). Now, our scheme allows the receiver to deduce that the missing number must be equal to \(4\). This is because they know that the points \((1,3), (2,?)\) and \((3,5)\) must all be on the same line.  With the knowledge that two points determine a line, the value of \(y_2=4\). What the receiver sees is shown in the Figure below.


Observe that it is immaterial here which of the three numbers was garbled. The receiver knows two points on the line, and can thus recover the polynomial \(f(x)\) and hence also the message.

Toy example #2 – spotting an error, and correcting it

However, adding a single redundant number does not protect us from other kinds of errors. Suppose that one of the numbers is misread, and the receiver reads \((y_1,y_2,y_3)=(3,2,5)\) instead of the correct sequence above. Now they cannot cope. The receiver can notice that the three points are not collinear, so they know that something went wrong. But, they have no way of knowing which of the three numbers is incorrect. Any pair of points gives a line all right, but now the received version of the message matches equally well with three distinct lines — all passing through two out of three points. The picture is as follows.


How can we cope with such errors? The solution is to add more redundancy. Let’s try \(k=2, n=4, r=4-2=2\) with two redundant numbers. Let’s again use the message \((y_1,y_2)=(3,4)\). This time we add a fourth point \((x_4,y_4)=(4,f(4))=(4,6)\), so the extended message (payload + redundancy) is now \((3,4,5,6)\). The picture is as follows.


If, again, one of the numbers is read incorrectly, then this time we can tell which one is incorrect, because the other three points are collinear.

Theorem 3. Given four points \(P_1,P_2,P_3,P_4\) on the plane there can be at most a single line containing at least three of those points.

Proof. Assume contrariwise that there are two lines, \(L_1\) and \(L_2\), both passing through at least three of the points. Because at most one of the four points is not on \(L_1\), and similarly at most one of the points is not on \(L_2\), we see that the lines \(L_1\) and \(L_2\) share at least \(4-1-1=2\) of the points. But there is a unique line through those two points, so \(L_1=L_2\). Q.E.D.

If in our toy example the receiver again makes a mistake with the second number and reads \((y_1,y_2,y_3,y_4)=(3,2,5,6)\), it will be easy for them to tell from the following picture, which point is the odd one out. Even without the plot of \(y=f(x)\) that I added to make things easier for you.


Coping with many problems in a single message

Ok, let us generalize. Assume that the payload consists of \(k\) numbers, and that we tag \(r=n-k\) redundant numbers to it so the entire transmitted list has \(n\) numbers. What kind of problems does this scheme protect us against? Above we encountered two kinds of problems. An erasure happens when the receiver cannot make out the written number. Observe that the receiver still knows the \(x\)-coordinate of that point (those were agreed in advance) — only the \(y\)-coordinate is missing. Another type of problem was an error, an incorrectly read number. From the toy examples we already got the feeling that, of these two, an error is more difficult to cope with. We needed two redundant numbers to correct a single error, but a single redundant number was enough to cope with an erasure.

Assume that we want to cater for the possibility of \(t\) errors and \(e\) erasures in a single transmission. How many redundant numbers do we need to cope with that? Altogether, the message gives us \(n=k+r\) points. The erasures mean that we only have \(n-e\) points remaining, and must manage with them. The goal is that these should somehow determine a unique polynomial of degree \(<k\). The solution is provided by the following generalization of Theorem 3.

Theorem 4. Given \(k+2t\) points with distinct \(x\)-coordinates on the plane there can be at most a single polynomial of degree \(<k\) whose graph passes through all but at most \(t\) of the points.

Proof. I am feeling a bit naughty and leaving this as an exercise. Use Theorem 2 in the same way that I used the fact “two points determine a unique line” in the proof of Theorem 3.

Corollary. When we append \(r\) redundant numbers to a payload of \(k\) according to this scheme we can cope with a combination of \(e\) erasures and \(t\) errors, if $$r\ge 2t+e.$$

So we see that adding redundancy makes the scheme more robust against the prescribed types of problems created by the channel. Of course, the added redundancy comes with a cost. A redundant number consumes the same amount of channel resources as a payload number (space on a CD or that piece of paper). There the user of this kind of a system needs to consider the probabilities of both errors and erasures, and then settle on a certain quality of service such that the inequality of Corollary is satisfied with a high enough probability.

Snakes in the paradise – need more algebra

There is one serious concern that I need to mention and address. Above I have loosely used the concept of a number without specifying what I meant by that. The figures undoubtedly left you with the impression that the numbers are usual real numbers. Unfortunately that won’t do. The basic reason is that to write down a real number with full precision takes infinitely many bits. But the messages on e.g. CDs consist of bytes. Programmers are used to viewing the value of a byte as an integer \(b\) in the range \(0\le b\le 255\). Even if we restrict the payload numbers to this range we cannot guarantee that the redundant numbers to be tagged would also oblige. Consider the following example of \(k=7, r=4\) and the payload \((y_1,\ldots,y_7)=(3, 7, 0, 1, 9, 6, 8)\). Here’s what the Lagrange interpolation polynomial looks like with these inputs.


Where are the red dots indicating the redundant numbers? Well, you can guess from the plot that the polynomial \(f(x)\) (it is of degree six) will increase very rapidly after the last payload. Indeed, this sextic polynomial gives the values \(f(8)=164, f(9)=903, f(10)=3129\) and \(f(11)=8464\) as the redundant numbers. So we face a serious overflow problem. Here’s a rescaled version of the plot.


Underflow is also possible as the redundant numbers may very well be negative. One might also worry that even though the payload consists of integers the redundant numbers might not. After all, Lagrange’s interpolation formula introduces divisions. Actually, as in the above overflow example, this never happens. But this is an artefact of the way we set up things. I leave this as an exercise for the interested reader.

Exercise. Let \(f(x)\in\mathbb{Q}[x]\) be the Lagrange interpolation polynomial (of degree \(<k\)) passing through the points \((1,y_1), (2,y_2), \ldots, (k,y_k)\), where all the numbers \(y_i, i=1,2,\ldots,k\) are integers. Show that \(f(n)\) is then an integer for all \(n\in\mathbb{Z}\).

But, we absolutely don’t want to use more than a single byte to present the redundant numbers. Or, more precisely, we insist that a redundant number should use the same amount of memory as a number in the payload part (a byte, a word,…). People familiar with elementary number theory may already feel the urge to reinterpret byte as a residue class modulo \(256\), i.e. as an element of the residue class ring \(R=\mathbb{Z}_{256}\). Unfortunately the algebra breaks down if we do that. To wit, already Theorem 1 fails dramatically. As an example, consider the linear polynomial \(f(x)=16x\). Even though it is linear, it has no less than sixteen distinct zeros in the ring \(R\), namely the residue classes of the form \(\overline{16m}\) for \(m=0,1,\ldots,15\). When you learn a bit more about the structures in abstract algebra you realize that the problem is that the ring \(R\) is not a field. But there is a field with 256 elements that fits the bill exactly! Its construction requires familiarity with polynomial rings and their quotient rings, and I don’t want to reproduce scores of pages from a first textbook on abstract algebra. To a reader who knows what is going on I will tell that

$$\mathbb{F}_{256}\cong\mathbb{F}_2[x]/\langle x^8+x^4+x^3+x^2+1\rangle$$

is a popular way of describing this field. A consequence of this is that the total length (payload + redundancy) of the messages in bytes cannot exceed \(256\). This is because at that point we run out of \(x\)-coordinates!

Links to more information

Coding theory is a topic straddling mathematics and communication engineering. It deals (among other things) in the design of schemes, like the one outlined here, aiming at coping with errors produced into messages by the channel. Two American coding theorists, Irving S. Reed and Gustave Solomon were the first to figure out this way of using the algebra of finite fields. One of their inventions was to choose the sequence of \(x\)-coordinates in a clever way that makes the calculation of the redundant numbers very easy (they can skip the time consuming use of Lagrange’s interpolation formula entirely). The resulting codes are called Reed–Solomon codes (or just RS-codes) in their honor. The Wikipedia-article on RS-codes  describes the algebra very differently, but in the end it is equivalent. That description reflects the more efficient calculation of the redundant part. I chose to present the codes in this way because it makes it easier to understand why these codes can cope with the prescribed types of errors.

Practical issues

I will close my contribution with a few remarks about certain practical aspects. The receiver faces the task of figuring out the correct polynomial. In the toy example of four points we could just take any pair of points (there are only six pairs), and check whether the line determined by them passes through a third point. But if we use a RS-code capable of correcting five errors with parameters \(k=240, r=10\), then the receiver following an analogous approach would need to generate \(\binom{250}{10}=219005316087032475\) Lagrange interpolation polynomials of degree \(239\), and check if one gives a good enough match. Not efficient at all! Thankfully, much more efficient algorithms have been developed by several other coding theorists.

The other remark I want to make has to do with compact disks. There, Reed-Solomon codes are used in the following way that produces good protection against typical scratching of the disk surface. The data on a CD is split into blocks like the one shown below.


Here each dot represents a single byte (actually, there is another error correcting code involved in reading a single byte from the disk that one is working at the level of individual bits and does not concern us here). The rows and columns in such a matrix are all encoded using an appropriate RS-code. The black dots are payload bytes. The encoding is done as follows. First, we add to each column four redundant bytes (green). Then we also add four redundant bytes to all the rows — in the payload part (red) as well as in the redundant part (blue). The bytes of a single row are close to each other on the CD, so the CD-player can read them quickly. It attempts to correct eventual errors. Usually it succeeds, but if that row is in a scratchy area, it fails, and then marks the entire row as unreliable data (i.e. an erasure). But different rows are more spaced out on the CD surface, so there is a high hope that only few rows from a given a matrix are lost in this fashion. If at most four of the rows are marked as erasures the column by column RS-code can recover the lost data. For the CD-player to be able to retrieve such matrices from the disk fast the entire matrix is on the same track (at the same distance from the disk center). Thus, a circular scratch may wipe out enough of the matrix, and the scheme will fail.

A happy thought: algebraic tools triumph in solving problems arising in communication.

Zabreiko’s lemma and four fundamental theorems of functional analysis

June 25, 2014 by . 0 comments

There are no doubts that open mapping theorem, closed graph theorem, bounded inverse theorem, uniform boundedness principle are the fundamental theorems of functional analysis. All of them are similar in the sense that they explicitly or implicitly use the Baire category theorem, but in the details they are different. However, all these theorems can be formulated as continuity of certain seminorms defined on a normed spaces.

The proof of the lemma is very similar to the usual proof by Banach-Schauder of the open mapping theorem and is actually stronger than the usual consequences of the Baire category theorem in basic functional analysis. The lemma can be used to easily prove the aforementioned theorems.

I would like to thank the user t.b. for drawing our attention to this lemma and adaptation of the original proof from the general case of linear metric spaces, which he gave as an answer to the question Direct Approach to the Closed Graph Theorem on the main site.

Lemma. (Zabreiko, [1], [2]) Let \(X\) be a Banach space and let \(p: X \to [0,\infty)\) be a seminorm. If for all absolutely convergent series \(\sum_{n=1}^\infty x_n\) in \(X\) we have \[ p\left(\sum_{n=1}^\infty x_n\right) \leq \sum_{n=1}^\infty p(x_n) \in [0,\infty] \] then \(p\) is continuous. That is to say, there exists a constant \(C \geq 0\) such that \(p(x) \leq C\lvert x\rvert _{X}\) for all \(x \in X\).

Proof. Let \(A_n = p^{-1}([0,n])\) and \(F_n = \overline{A_n}\). Note that \(A_n\) and \(F_n\) are symmetric and convex because \(p\) is a seminorm. We have \(X = \bigcup_{n=1}^\infty F_n\) and Baire’s theorem implies that there is \(N\) such that the interior of \(F_N\) is nonempty.

Therefore, there are \(x_0 \in X\) and \(R \gt 0\) such that \(B_R(x_0) \subset F_N\). By symmetry of \(F_N\) we have \(B_{R}(-x_0) = -B_{R}(x_0) \subset F_n\), too. If \(\lvert x\rvert \lt R\) then \(x+x_0 \in B_{R}(x_0)\) and \(x-x_0 \in B_{R}(-x_0)\), so \(x \pm x_0 \in F_{N}\). By convexity of \(F_N\) it follows that \[ x = \frac{1}{2}(x-x_0) + \frac{1}{2}(x+x_0) \in F_N, \] so \(B_R(0) \subset F_N\). But, in fact, we can prove much more: \[ B_{R}(0) \subset A_N \] Suppose \(\lvert x\rvert \lt R\) and choose \(r\) such that \(\lvert x\rvert \lt r \lt R\). Fix \(0 \lt q \lt 1-\frac{r}{R}\), so \(\frac{1}{1-q} \frac{r}{R} \lt 1\). Then \(y = \frac{R}{r}x \in B_{R}(0) \subset F_N = \overline{A_N}\), so there is \(y_{0} \in A_N\) such that \(\lvert y-y_0\rvert \lt qR\), so \(q^{-1}(y-y_0) \in B_R\). Now choose \(y_1 \in A_N\) with \(\lvert q^{-1}(y-y_0) – y_1\rvert \lt q R\), so \(\lvert (y-y_0 – qy_1)\rvert \lt q^2 R\). By induction we obtain a sequence \( (y_k)\subset A_N\) such that \[ \left\lvert y - \sum_{k=0}^n q^k y_k\right\rvert \lt q^n R \quad \text{for all }n \geq 0, \] hence \(y = \sum_{k=0}^\infty q^k y_k\). Observe that by construction \(|y_k| \leq R + qR\) for all \(k\), so the series \(\sum_{k=0}^\infty q^k y_k\) is absolutely convergent. But then the countable subadditivity hypothesis in \(p\) implies that \[ p(y) = p\left(\sum_{k=0}^\infty q^k y_k\right) \leq \sum_{k=0}^\infty q^k p(y_k) \leq \frac{1}{1-q} N \] and thus \(p(x) \leq \frac{r}{R} \frac{1}{1-q} N \lt N\) which means \(x \in A_N\), as we wanted.

Finally, for any \(x \neq 0\), we have with \(\lambda = \frac{R}{\lvert x\rvert (1+\varepsilon)}\) that \(\lambda x \in B_{R}(0) \subset A_N\), so \(p(\lambda x) \leq N\) and thus \(p(x) \leq \frac{N(1+\varepsilon)}{R} \lvert x\rvert \), as desired. \(\blacksquare\)

Now the proof of the fundamental theorems becomes an easy exercise.

  1. The open mapping theorem. Hint: set \(p(y) = \inf_{x\in T^{-1}(y)}\lvert x\rvert \).
  2. The bounded inverse theorem. Hint: set \(p(x) = \lvert T^{-1}(x)\rvert \).
  3. The uniform boundedness principle. Hint: set \(p(x) = \sup_{i\in I}\lvert T_i (x)\rvert \).
  4. The closed graph theorem. Hint: set \(p(x) = \lvert T(x)\rvert \).

Detailed solutions can be found in theorems \(1.6.5\), \(1.6.6\), \(1.6.9\) and \(1.6.11\) in An Introduction to Banach Space Theory Graduate Texts in Mathematics. Robert E. Megginson.

[1] П. П. Забрейко, Об одной теореме для полуаддитивных функционалов, Функциональный анализ и его приложения, 3:1 (1969), 86–88

[2] P. P. Zabreiko, A theorem for semiadditive functionals, Functional analysis and its applications 3 (1), 1969, 70-72)

When do n and 2n have the same decimal digits?

June 11, 2014 by . 2 comments

A recent question on math.stackexchange asks for the smallest positive number \( A \) for which the number \( 2A \) has the same decimal digits in some other order.

Math geeks may immediately realize that \( 142857 \) has this property, because it is the first 6 digits of the decimal expansion of \( \frac 17 \), and the cyclic behavior of the decimal expansion of \( \frac n7 \) is well-known. But is this the minimal solution? It is not. Brute-force enumeration of the solutions quickly reveals that there are 12 solutions of 6 digits each, all permutations of \( 142857 \), and that larger solutions, such as \( 1025874 \) and \( 1257489 \), seem to follow a similar pattern. What is happening here?

Stuck in Dallas-Fort Worth airport last month, I did some work on the problem, and although I wasn’t able to solve it completely, I made significant progress. I found a method that allows one to hand-calculate that there is no solution with fewer than six digits, and to enumerate all the solutions with 6 digits, including the minimal one. I found an explanation for the surprising behavior that solutions tend to be permutations of one another. The short form of the explanation is that there are fairly strict conditions on which sets of digits can appear in a solution of the problem. But once the set of digits is chosen, the conditions on that order of the digits in the solution are fairly lax.

So one typically sees, not only in base 10 but in other bases, that the solutions to this problem fall into a few classes that are all permutations of one another; this is exactly what happens in base 10 where all the 6-digit solutions are permutations of \( 124578 \). As the number of digits is allowed to increase, the strict first set of conditions relaxes a little, and other digit groups can (and do) appear as solutions.


The property of interest, \( P_R(A) \), is that the numbers \( A \) and \( B=2A \) have exactly the same base-\( R \) digits. We would like to find numbers \( A \) having property \( P_R \) for various \( R \), and we are most interested in \( R=10 \). Suppose \( A \) is an \( n \)-digit numeral having property \( P_R \); let the (base-\( R \)) digits of \( A \) be \( a_{n-1}\ldots a_1a_0 \) and similarly the digits of \( B = 2A \) are \( b_{n-1}\ldots b_1b_0 \). The reader is encouraged to keep in mind the simple example of \( R=8, n=4, A=\mathtt{1042}, B=\mathtt{2104} \) which we will bring up from time to time.

Since the digits of \( B \) and \( A \) are the same, in a different order, we may say that \( b_i = a_{P(i)} \) for some permutation \( P \). In general \( P \) might have more than one cycle, but we will suppose that \( P \) is a single cycle. All the following discussion of \( P \) will apply to the individual cycles of \( P \) in the case that \( P \) is a product of two or more cycles. For our example of \( A=\mathtt{1042}, B=\mathtt{2104} \), we have \( P = (0\,1\,2\,3) \) in cycle notation. We won’t need to worry about the details of \( P \), except to note that \( i, P(i), P(P(i)), \ldots, P^{n-1}(i) \) completely exhaust the indices \( 0. \ldots n-1 \), and that \( P^n(i) = i \) because \( P \) is an \( n \)-cycle.

Conditions on the set of digits in a solution

For each \( i \) we have $$ a_{P(i)} = b_{i} \equiv 2a_{i} + c_i\pmod R $$ where the ‘carry bit’ \( c_i \) is either 0 or 1 and depends on whether there was a carry when doubling \( a_{i-1} \). (When \( i=0 \) we are in the rightmost position and there is never a carry, so \( c_0= 0 \).) We can then write:

$$ \begin{align} a_{P(P(i))} &= 2a_{P(i)} + c_{P(i)} \\ &= 2(2a_{i} + c_i) + c_{P(i)} &&= 4a_i + 2c_i + c_{P(i)}\\ a_{P(P(P(i)))} &= 2(4a_i + 2c_i + c_{P(P(i)})) + c_{P(i)} &&= 8a_i + 4c_i + 2c_{P(i)} + c_{P(P(i))}\\ &&&\vdots\\ a_{P^n(i)} &&&= 2^na_i + v \end{align} $$

all equations taken \( \bmod R \). But since \( P \) is an \( n \)-cycle, \( P^n(i) = i \), so we have $$ a_i \equiv 2^na_i + v\pmod R $$ or equivalently $$ \big(2^n-1\big)a_i + v \equiv 0\pmod R\tag{\( \star \)} $$ where \( v\in\{0,\ldots 2^n-1\} \) depends only on the values of the carry bits \( c_i \)—the \( c_i \) are precisely the binary digits of \( v \).

Specifying a particular value of \( a_0 \) and \( v \) that satisfy this equation completely determines all the \( a_i \). For example, \( a_0 = 2, v = \color{darkblue}{0010}_2 = 2 \) is a solution when \( R=8, n=4 \) because \( \bigl(2^4-1\bigr)\cdot2 + 2\equiv 0\pmod 8 \), and this solution allows us to compute

$$ \def\db#1{\color{darkblue}{#1}}\begin{align} a_0&&&=2\\ a_{P(0)} &= 2a_0 &+ \db0 &= 4\\ a_{P^2(0)} &= 2a_{P(0)} &+ \db0 &= 0 \\ a_{P^3(0)} &= 2a_{P^2(0)} &+ \db1 &= 1\\ \hline a_{P^4(0)} &= 2a_{P^3(0)} &+ \db0 &= 2\\ \end{align} $$

where the carry bits \( c_i = \langle 0,0,1,0\rangle \) are visible in the third column, and all the sums are taken \( \pmod 8 \). Note that \( a_{P^n(0)} = a_0 \) as promised. This derivation of the entire set of \( a_i \) from a single one plus a choice of \( v \) is crucial, so let’s see one more example. Let’s consider \( R=10, n=3 \). Then we want to choose \( a_0 \) and \( v \) so that \( \left(2^3-1\right)a_0 + v \equiv 0\pmod{10} \) where \( v\in\{0\ldots 7\} \). One possible solution is \( a_0 = 5, v=\color{darklue}{101}_2 = 5 \). Then we can derive the other \( a_i \) as follows:

$$ \begin{align} a_0&&&=5\\ a_{P(0)} &= 2a_0 &+ \db1 &= 1\\ a_{P^2(0)} &= 2a_{P(0)} &+ \db0 &= 2 \\\hline a_{P^3(0)} &= 2a_{P^2(0)} &+ \db1 &= 5\\ \end{align} $$

And again we have \( a_{P^n(0)}= a_0 \) as required.

Since the bits of \( v \) are used cyclically, not every pair of \( \langle a_0, v\rangle \) will yield a different solution. Rotating the bits of \( v \) and pairing them with different choices of \( a_0 \) will yield the same cycle of digits starting from a different place. In the first example above, we had \( a_0 = 2, v = 0010_2 = 2 \). If we were to take \( a_0 = 4, v = 0100_2 = 4 \) (which also solves \( (\star) \)) we would get the same cycle of values of the \( a_i \) but starting from \( 4 \) instead of from \( 2 \), and similarly if we take \( a_0=0, v = 1000_2 = 8 \) or \( a_0 = 1, v = 0001_2 \). So we can narrow down the solution set of \( (\star) \) by considering only the so-called bracelets of \( v \) rather than all \( 2^n \) possible values. Two values of \( v \) are considered equivalent as bracelets if one is a rotation of the other. When a set of \( v \)-values are equivalent as bracelets, we need only consider one of them; the others will give the same cyclic sequence of digits, but starting in a different place. For \( n=4 \), for example, the bracelets are \( 0000, 0001, 0011, 0101, 0111, \) and \( 1111 \); the sequences \( 0110, 1100, \) and \( 1001 \) being equivalent to \( 0011 \), and so on.


Let us take \( R=9, n=3 \), so we want to find 3-digit numerals with property \( P_9 \). According to \( (\star) \) we need \( 7a_i + v \equiv 0\pmod{9} \) where \( v\in\{0\ldots 7\} \). There are 9 possible values for \( a_i \); for each one there is at most one possible value of \( v \) that makes the sum zero:

$$ \begin{array}{rrr} a_i & 7a_i & v \\ \hline 0 & 0 & 0 \\ 1 & 7 & 2 \\ 2 & 14 & 4 \\ 3 & 21 & 6 \\ 4 & 28 & \\ 5 & 35 & 1 \\ 6 & 42 & 3 \\ 7 & 49 & 5 \\ 8 & 56 & 7 \\ \end{array} $$

(For \( a_i=4 \) there is no solution.) We may disregard the non-bracelet values of \( v \), as these will give us solutions that are the same as those given by bracelet values of \( v \). The bracelets are:

$$ \begin{array}{rl} 000 & 0 \\ 001 & 1 \\ 011 & 3 \\ 111 & 7 \end{array} $$

so we may disregard the solutions exacpt when \( v=0,1,3,7 \). Calculating the digit sequences from these four values of \( v \) and the corresponding \( a_i \) we find:

$$ \begin{array}{ccl} a_0 & v & \text{digits} \\ \hline 0 & 0 & 000 \\ 5 & 1 & 512 \\ 6 & 3 & 637 \\ 8 & 7 & 888 \ \end{array} $$

(In the second line, for example, we have \( v=1 = 001_2 \), so \( 1 = 2\cdot 5 + 0; 2 = 1\cdot 2 + 0; \) and \( 5 = 2\cdot 2 + 1 \).)

Any number \( A \) of three digits, for which \( 2A \) contains exactly the same three digits, in base 9, must therefore consist of exactly the digits \( 000, 125, 367, \) or \( 888 \).

A warning

All the foregoing assumes that the permutation \( P \) is a single cycle. In general, it may not be. Suppose we did an analysis like that above for \( R=10, n=5 \) and found that there was no possible digit set, other than the trivial set 00000, that satisfied the governing equation \( (2^5-1)a_0 + v\equiv 0\pmod{10} \). This would not completely rule out a base-10 solution with 5 digits, because the analysis only rules out a cyclic set of digits. There could still be a solution where \( P \) was a product of a \( 2 \) and a \( 3 \)-cycle, or a product of still smaller cycles.

Something like this occurs, for example, in the \( n=4, R=8 \) case. Solving the governing equation \( (2^5-1)a_0 + v \equiv 0\pmod 8 \) yields only four possible digit cycles, namely \( \{0,1,2,4\}, \{1,3,6,4\}, \{2,5,2,5\} \), and \( \{3,7,6,5\} \). But there are several additional solutions: \( 2500_8\cdot 2 = 5200_8, 2750_8\cdot 2 = 5720_8, \) and \( 2775_8\cdot 2 = 5772_8 \). These correspond to permutations \( P \) with more than one cycle. In the case of \( 5720_8 \), for example, \( P \) exchanges the \( 5 \) and the \( 2 \), and leaves the \( 0 \) and the \( 7 \) fixed.

For this reason we cannot rule out the possibility of an \( n \)-digit solution without first considering all smaller \( n \).

The Large Equals Odd rule

When \( R \) is even there is a simple condition we can use to rule out certain sets of digits from being single-cycle solutions. Recall that \( A=a_{n-1}\ldots a_0 \) and \( B=b_{n-1}\ldots b_0 \). Let us agree that a digit \( d \) is large if \( d\ge \frac R2 \) and small otherwise. That is, \( d \) is large if, upon doubling, it causes a carry into the next column to the left.

Since \( b_i =(2a_i + c_i)\bmod R \), where the \( c_i \) are carry bits, we see that, except for \( b_0 \), the digit \( b_i \) is odd precisely when there is a carry from the next column to the right, which occurs precisely when \( a_{i-1} \) is large. Thus the number of odd digits among \( b_1,\ldots b_{n-1} \) is equal to the number of large digits among \( a_1,\ldots a_{n-2} \). This leaves the digits \( b_0 \) and \( a_{n-1} \) uncounted. But \( b_0 \) is never odd, since there is never a carry in the rightmost position, and \( a_{n-1} \) is always small (since otherwise \( B \) would have \( n+1 \) digits, which is not allowed). So the number of large digits in \( A \) is exactly equal to the number of odd digits in \( B \). And since \( A \) and \( B \) have exactly the same digits, the number of large digits in \( A \) is equal to the number of odd digits in \( A \). Observe that this is the case for our running example \( 1042_8 \): there is one odd digit and one large digit (the 4).

When \( R \) is odd the analogous condition is somewhat more complicated, but since the main case of interest is \( R=10 \), we have the useful rule that:

For \( R \) even, the number of odd digits in any solution \( A \) is equal to the number of large digits in \( A \).

Conditions on the order of digits in a solution

We have determined, using the above method, that the digits \( \{5,1,2\} \) might form a base-9 numeral with property \( P_9 \). Now we would like to arrange them into a base-9 numeral that actually does have that property. Again let us write \( A = a_2a_1a_0 \) and \( B=b_2b_1b_0 \), with \( B=2A \). Note that if \( a_i = 1 \), then \( b_i = 3 \) (if there was a carry from the next column to the right) or \( 2 \) (if there was no carry), but since \( b_i=3 \) is impossible, we must have \( a_i = 2 \) and therefore \( a_{i-1} \) must be small, since there is no carry into position \( i \). But since \( a_{i-1} \) is also one of \( \{5,1,2\} \), and it cannot also be \( 1 \), it must be \( 2 \). This shows that the \( 1 \), unless it appears in the rightmost position, must be to the left of the \( 2 \); it cannot be to the left of the \( 5 \). Similarly, if \( a_i = 2 \) then \( b_i = 5 \), because \( 4 \) is impossible, so the \( 2 \) must be to the left of a large digit, which must be the \( 5 \). Similar reasoning produces no constraint on the position of the \( 5 \); it could be to the left of a small digit (in which case it doubles to \( 1 \)) or a large digit (in which case it doubles to \( 2 \)). We can summarize these findings as follows:

$$ \begin{array}{cl} \text{digit} & \text{to the left of} \\ \hline 1 & 1, 2, \text{end} \\ 2 & 5 \\ 5 & 1,2,5,\text{end} \end{array} $$

Here “end” means that the indicated digit could be the rightmost.

Furthermore, the left digit of \( A \) must be small (or else there would be a carry in the leftmost place and \( 2A \) would have 4 digits instead of 3) so it must be either \( 1 \) or \( 2 \). It is not hard to see from this table that the digits must be in the order \( 125 \) or \( 251 \), and indeed, both of those numbers have the required property: \( 125_9\cdot 2 = 251_9 \), and \( 251_9\cdot 2 = 512_9 \).

This was a simple example, but in more complicated cases it is helpful to draw the order constraints as a graph. Suppose we draw a graph with one vertex for each digit, and one additional vertex to represent the end of the numeral. The graph has an edge from vertex \( v \) to \( v’ \) whenever \( v \) can appear to the left of \( v’ \). Then the graph drawn for the table above looks like this:

Graph for 125 base 9

A 3-digit numeral with property \( P_9 \) corresponds to a path in this graph that starts at one of the nonzero small digits (marked in blue), ends at the red node marked ‘end’, and visits each node exactly once. Such a path is called hamiltonian. Obviously, self-loops never occur in a hamiltonian path, so we will omit them from future diagrams.

Now we will consider the digit set \( 637 \), again base 9. An analysis similar to the foregoing allows us to construct the following graph:

Graph for 367 base 9

Here it is immediately clear that the only hamiltonian path is \( 3-7-6-\text{end} \), and indeed, \( 376_9\cdot 2 = 763_9 \).

In general there might be multiple instances of a digit, and so multiple nodes labeled with that digit. Analysis of the \( 0,0,0 \) case produces a graph with no legal start nodes and so no solutions, unless leading zeroes are allowed, in which case \( 000 \) is a perfectly valid solution. Analysis of the \( 8,8,8 \) case produces a graph with no path to the end node and so no solutions. These two trivial patterns appear for all \( R \) and all \( n \), and we will ignore them from now on.

Returning to our ongoing example, \( 1042 \) in base 8, we see that \( 1 \) and \( 2 \) must double to \( 2 \) and \( 4 \), so must be to the left of small digits, but \( 4 \) and \( 0 \) can double to either \( 0 \) or \( 1 \) and so could be to the left of anything. Here the constraints are so lax that the graph doesn’t help us narrow them down much:

Graph for 1024 base 8

Observing that the only arrow into the 4 is from 0, so that the 4 must follow the 0, and that the entire number must begin with 1 or 2, we can enumerate the solutions:

If leading zeroes are allowed we have also:
All of these are solutions in base 8.

The case of \( R=10 \)

Now we turn to our main problem, solutions in base 10.

To find all the solutions of length 6 requires an enumeration of smaller solutions, which, if they existed, might be concatenated into a solution of length 6. This is because our analysis of the digit sets that can appear in a solution assumes that the digits are permuted cyclically; that is, the permutations \( P \) that we considered had only one cycle each. If we perform the analy

There are no smaller solutions, but to prove that the length 6 solutions are minimal, we must analyze the cases for smaller \( n \) and rule them out. We now produce a complete analysis of the base 10 case with \( R=10 \) and \( n\le 6 \). For \( n=1 \) there is only the trivial solution of \( 0 \), which we disregard. (The question asked for a positive number anyway.)

\( n=2 \)

For \( n=2 \), we want to find solutions of \( 3a_i + v \equiv 0\pmod{10} \) where \( v \) is a two-bit bracelet number, one of \( 00_2, 01_2, \) or \( 11_2 \). Tabulating the values of \( a_i \) and \( v\in\{0,1,3\} \) that solve this equation we get:

$$ \begin{array}{ccc} v& a_i \\ \hline 0 & 0 \\ 1& 3 \\ 3& 9 \\ \end{array} $$

We can disregard the \( v=0 \) and \( v=3 \) solutions because the former yields the trivial solution \( 00 \) and the latter yields the nonsolution \( 99 \). So the only possibility we need to investigate further is \( a_i = 3, v = 1 \), which corresponds to the digit sequence \( 36 \): Doubling \( 3 \) gives us \( 6 \) and doubling \( 6 \), plus a carry, gives us \( 3 \) again.

But when we tabulate of which digits must be left of which, we see that there is no solution with just \( 3 \) and \( 6 \), because the graph we get, once self-loops are eliminated, looks like this:

graph for 36 base 10

which obviously has no hamiltonian path. Thus there is no solution for \( R=10, n=2 \).

\( n=3 \)

For \( n=3 \) we need to solve the equation \( 7a_i + v \equiv 0\pmod{10} \) where \( v \) is a bracelet number in \( \{0,\ldots 7\} \), specifically one of \( 0,1,3, \) or \( 7 \). Since \( 7 \) and \( 10 \) are relatively prime, for each \( v \) there is a single \( a_i \) that solves the equation. Tabulating the possible values of \( a_i \) as before, and this time omitting rows with no solution, we have:

$$ \begin{array}{rrl} v & a_i & \text{digits}\\ \hline 0& 0 & 000\\ 1& 7 & 748 \\ 3& 1 & 125\\ 7&9 & 999\\ \end{array} $$

The digit sequences \( 0,0,0 \) and \( 9,9,9 \) yield trivial solutions or nonsolutions as usual, and we will omit them in the future. The other two lines suggest the digit sets \( 1,2,5 \) and \( 4,7,8 \), both of which fails the “odd equals large” rule.

This analysis rules out the possibility of a digit set with \( a_0 \to a_1 \to a_2 \to a_1 \), but it does not completely rule out a 3-digit solution, since one could be obtained by concatenating a one-digit and a two-digit solution, or three one-digit solutions. However, we know by now that no one- or two-digit solutions exist. Therefore there are no 3-digit solutions in base 10.

\( n=4 \)

For \( n=4 \) the governing equation is \( 15a_i + v \equiv 0\pmod{10} \) where \( v \) is a 4-bit bracelet number, one of \( \{0,1,3,5,7,15\} \). This is a little more complicated because \( \gcd(15,10)\ne 1 \). Tabulating the possible digit sets, we get:

$$ \begin{array}{crrl} a_i & 15a_i& v & \text{digits}\\ \hline 0 & 0 & 0 & 0000\\ 1 & 5 & 5 & 1250\\ 1 & 5 & 15 & 1375\\ 2 & 0 & 0 & 2486\\ 3 & 5 & 5 & 3749\\ 3 & 5 & 15 & 3751\\ 4 & 0 & 0 & 4862\\ 5 & 5 & 5 & 5012\\ 5 & 5 & 5 & 5137\\ 6 & 0 & 0 & 6248\\ 7 & 5 & 5 & 7493\\ 7 & 5 & 5 & 7513\\ 8 & 0 & 0 & 8624 \\ 9 & 5 & 5 & 9874\\ 9 & 5 & 15 & 9999 \\ \end{array} $$

where the second column has been reduced mod \( 10 \). Note that even restricting \( v \) to bracelet numbers the table still contains duplicate digit sequences; the 15 entries on the right contain only the six basic sequences \( 0000, 0125, 1375, 2486, 3749, 4987 \), and \( 9999 \). Of these, only \( 0000, 9999, \) and \( 3749 \) obey the odd equals large criterion, and we will disregard \( 0000 \) and \( 9999 \) as usual, leaving only \( 3749 \). We construct the corresponding graph for this digit set as follows: \( 3 \) must double to \( 7 \), not \( 6 \), so must be left of a large number \( 7 \) or \( 9 \). Similarly \( 4 \) must be left of \( 7 \) or \( 9 \). \( 9 \) must also double to \( 9 \), so must be left of \( 7 \). Finally, \( 7 \) must double to \( 4 \), so must be left of \( 3,4 \) or the end of the numeral. The corresponding graph is:

graph for 3749 base 10

which evidently has no hamiltonian path: whichever of 3 or 4 we start at, we cannot visit the other without passing through 7, and then we cannot reach the end node without passing through 7 a second time. So there is no solution with \( R=10 \) and \( n=4 \).

\( n=5 \)

We leave this case as an exercise. There are 8 solutions to the governing equation, all of which are ruled out by the odd equals large rule.

\( n=6 \)

For \( n=6 \) the possible solutions are given by the governing equation \( 63a_i + v \equiv 0\pmod{10} \) where \( v \) is a 6-bit bracelet number, one of \( \{0,1,3,5,7,9,11,13,15,21,23,27,31,63\} \). Tabulating the possible digit sets, we get:

$$ \begin{array}{crrl} v & a_i & \text{digits}\\ \hline 0 & 0 & 000000\\ 1 & 3 & 362486 \\ 3 & 9 & 986249 \\ 5 & 5 & 500012 \\ 7 & 1 & 124875 \\ 9 & 7 & 748748 \\ 11 & 3 & 362501 \\ 13 & 9 & 986374 \\ 15 & 5 & 500137 \\ 21 & 3 & 363636 \\ 23 & 9 & 989899 \\ 27 & 1 & 125125 \\ 31 & 3 & 363751 \\ 63 & 9 & 999999 \\ \end{array} $$

After ignoring \( 000000 \) and \( 999999 \) as usual, the large equals odd rule allows us to ignore all the other sequences except \( 124875 \) and \( 363636 \). The latter fails for the same reason that \( 36 \) did when \( n=2 \). But \( 142857 \) , the lone survivor, gives us a complicated derived graph containing many hamiltonian paths, every one of which is a solution to the problem:

graph for 124578 base 10

It is not hard to pick out from this graph the minimal solution \( 125874 \), for which \( 125874\cdot 2 = 251748 \), and also our old friend \( 142857 \) for which \( 142857\cdot 2 = 285714 \).

We see here the reason why all the small numbers with property \( P_{10} \) contain the digits \( 124578 \). The constraints on which digits can appear in a solution are quite strict, and rule out all other sequences of six digits and all shorter sequences. But once a set of digits passes these stringent conditions, the constraints on it are much looser, because \( B \) is only required to have the digits of \( A \) in some order, and there are many possible orders, many of which will satisfy the rather loose conditions involving the distribution of the carry bits. This graph is typical: it has a set of small nodes and a set of large nodes, and each node is connected to either all the small nodes or all the large nodes, so that the graph has many edges, and, as in this case, a largish clique of small nodes and a largish clique of large nodes, and as a result many hamiltonian paths.


This analysis is tedious but is simple enough to perform by hand in under an hour. As \( n \) increases further, enumerating the solutions of the governing equation becomes very time-consuming. I wrote a simple computer program to perform the analysis for given \( R \) and \( n \), and to emit the possible digit sets that satisfied the large equals odd criterion. I had wondered if every base-10 solution contained equal numbers of the digits \( 1,2,4,8,5, \) and \( 7 \). This is the case for \( n=7 \) (where the only admissible digit set is \( \{1,2,4,5,7,8\}\cup\{9\} \)), for \( n=8 \) (where the only admissible sets are \( \{1,2,4,5,7,8\}\cup \{3,6\} \) and \( \{1,2,4,5,7,8\}\cup\{9,9\} \)), and for \( n=9 \) (where the only admissible sets are \( \{1,2,4,5,7,8\}\cup\{3,6,9\} \) and \( \{1,2,4,5,7,8\}\cup\{9,9,9\} \)). But when we reach \( n=10 \) the increasing number of bracelets has loosened up the requirements a little and there are 5 admissible digit sets. I picked two of the promising-seeming ones and quickly found by hand the solutions \( 4225561128 \) and \( 1577438874 \), both of which wreck any theory that the digits \( 1,2,4,5,8,7 \) must all appear the same number of times.


Thanks to Karl Kronenfeld for corrections to this article, any many helpful suggestions about what to omit.

Green’s Theorem and Area of Polygons

June 4, 2014 by . 10 comments

A common method used to find the area of a polygon is to break the polygon into smaller shapes of known area. For example, one can separate the polygon below into two triangles and a rectangle:

Figure 1

By breaking this composite shape into smaller ones, the area is at hand: $$\begin{align}A_1 &= bh = 5\cdot 2 = 10 \\ A_2 = A_3 &= \frac{bh}{2} = \frac{2\cdot 1}{2} = 1 \\ A_{total} &= A_1+A_2+A_3 = 12\end{align}$$

Unfortunately, this approach can be difficult for a person to use when they cannot physically (or mentally) see the polygon, such as when a polygon is given as a list of many vertices.



Happily, there is a formula for the area of any simple polygon that only requires knowledge of the coordinates of each vertex. It is as follows: $$A = \sum_{k=0}^{n} \frac{(x_{k+1} + x_k)(y_{k+1}-y_{k})}{2} \tag{1}$$ (Where \({n}\) is the number of vertices, \({(x_k, y_k)}\) is the \({k}\)-th point when labelled in a counter-clockwise manner, and \({(x_{n+1}, y_{n+1}) = (x_0, y_0)}\); that is, the starting vertex is found both at the start and end of the list of vertices.)

It should be noted that the formula is not “symmetric” with respect to the signs of the \({x}\) and \({y}\) coordinates. This can be explained by considering the “negative areas” incurred when adding the signed areas of the triangles with vertices \({(0,0)-(x_k, y_k)-(x_{k+1}, y_{k+1})}\).

In the next sections, I derive this formula using Green’s Theorem, show an example of its use, and provide some applications.



Green’s Theorem states that, for a “well-behaved” curve \({C}\) forming the boundary of a region \({D}\):

\(\displaystyle \oint_C P(x, y)\;\mathrm dx + Q(x, y)\;\mathrm dy = \iint_D \frac{\partial Q}{\partial x} – \frac{\partial P}{\partial y}\;\mathrm dA \ \ \ \ \ (2)\)

(In this context, “well behaved” means, among other things, that \({C}\) is piecewise smooth. For a full listing of the requirements for \({C}\) and \({D}\), please see here.)

Recalling that the area of \({D}\) is equal to \({\iint_D \;\mathrm dA}\), we can use Green’s Theorem to calculate area if we choose \({P}\) and \({Q}\) such that \({\frac{\partial Q}{\partial x} – \frac{\partial P}{\partial y}=1}\). Clearly, choosing \({P(x, y) = 0}\) and \({Q(x, y) = x}\) satisfies this requirement.

Thus, letting \({A}\) be the area of the region \({D}\):

\(\displaystyle A = \oint_C x\;\mathrm dy \ \ \ \ \ (3)\)

Now, consider the polygon below, bordered by the piecewise-smooth curve \({C = C_0\cup C_1\cup\cdots\cup C_{n-1}\cup C_n}\), where \({C_k}\) starts at the point \({(x_k, y_k)}\) and ends at the “next” point along the polygon’s edge when proceeding counter-clockwise. (N.B. If we proceed in a clockwise manner, we get the negative of the area of the polygon.)

Figure 2

Note: the dashed lines indicate that there could be any number of points between \({(x_2, y_2)}\) and \({(x_{n-1}, y_{n-1})}\); this is a complete polygon.

Because line integrals over piecewise-smooth curves are additive over length, we have that:

\(\displaystyle A = \oint_C x\;\mathrm dy = \int_{C_0} x\;\mathrm dy + \cdots + \int_{C_n} x\;\mathrm dy \ \ \ \ \ (4)\)

To compute the \({k}\)-th line line integral above, parametrize the segment from \({(x_k, y_k)}\) to \({(x_{k+1}, y_{k+1})}\):

\(\displaystyle C_k:\; \vec{r}=\left((x_{k+1} – x_k)t + x_k,\; (y_{k+1} – y_k)t + y_k\right),\quad 0\le t\le 1 \ \ \ \ \ (5)\)

Substituting this parametrization into the integral, we find: $$\begin{align}\int_{C_k} x\;\mathrm dy &= \int_0^1 \left((x_{k+1} – x_k)t + x_k\right)\left(y_{k+1} – y_k\right)\;\mathrm dt \\ &= \frac{(x_{k+1} + x_k)(y_{k+1}-y_{k})}{2}\end{align}$$

Summing all of the \(C_k\)’s, we then find the total area: $$A = \sum_{k=0}^{n} \frac{(x_{k+1} + x_k)(y_{k+1}-y_{k})}{2} \tag{6}$$


To demonstrate use of this formula, let us apply this to the shape at the beginning of the document. A copy of the image is found below, but this one is marked with the coordinates of the vertices.

FIgure 3

Starting with the coordinate \({(0, 0)}\) and proceeding counter-clockwise (again, if we go in the opposite direction, we get the negative of the correct area), we apply our formula:

$$\begin{align} A &= \sum_{k=0}^{n} \frac{(x_{k+1} + x_k)(y_{k+1}-y_{k})}{2} \\ &= \frac{(1.5 + 0)(0 – 0)}{2} + \frac{(2.5 + 1.5)(-1 – 0)}{2} + \frac{(3.5 + 2.5)(0 – (-1))}{2} + \frac{(5+3.5)(0-0)}{2} \\ &\quad + \frac{(5+5)(2-0)}{2} + \frac{(3.5+5)(2-2)}{2} + \frac{(2.5+3.5)(3-2)}{2}\\ &\quad +\frac{(1.5+2.5)(2-3)}{2} + \frac{(0+1.5)(2-2)}{2} + \frac{(0+0)(0-2)}{2}\\ &= 0 + (-2) + 3 + 0 + 10 + 0 + 3 + (-2) + 0 + 0\\ &= 12 \end{align}$$

We arrive at the same answer we had above, which is good. (Obviously!)

Possible Applications

Although this formula is an interesting application of Green’s Theorem in its own right, it is important to consider why it is useful. As can be seen above, this approach involves a lot of tedious arithmetic. Thus, its main benefit arises when applied in a computer program, when the tedium is no longer an issue.

From an engineering perspective, this formula could be used to determine the area (and, using similarly-derived formulas for the moments of a polygon about the \({x}\) and \({y}\) axes, the centroid) of component in a CAD program. Many computer programs estimate all shapes as polygons or connected line segments (rather than exact curves/circles), which means this formula can be directly applied to the existing representation in software.

In a contrived context, this formula can also be useful in collegiate programming competitions. (This was why I first took note of this formula.) Some problems in the “computational geometry” category may involve computing the area of specific polygons, such as the convex hull of a set of points. Knowing the derivation can make it easier to recall during a competition event.

As a final example, one can use this formula to approximate the area of a plot of land. Over a small region, surface area on a sphere can be approximated as that on a rectangle. Thus, an irregularly-shaped plot of land can be modelled as an polygon. Once coordinates are established for each vertex, the formula derived above can be applied to find its area.

Welcome to the Math.SE Blog!

June 3, 2014 by . 1 comments

Welcome to the Math StackExchange community blog!

Four years ago today, Dan Dumitru proposed the creation of Math.StackExchange. The site has evolved into a community with hundreds of thousands of questions and answers, and over 30 thousand questions and answers appearing each month.

Now, we have a blog.

This blog provides a way of going beyond the Q&A format to allow exposition and discussion. There might be posts about mathematics, or Math.SE, or a book review, or whatever seems appropriate. Anyone can contribute to the blog. This blog is written and edited by community members, and we are actively soliticing both one-time and regular contributors! So if you have an idea of something you’d like to hear about or read about, or if you would like to contribute, check out the blog chat room and the Blog FAQ thread on meta.

I’m looking forward to see what we make here.


Filed under all levels, expository