The Zorach Additive Triangle

				1
			2		3
		4		6		9
	7		11		17		26
5		12		23		40		66
	...		...		...		...

The Zorach Additive Triangle:

(with open conjectures)
Motivation | Definition | Conjectures | Links

Motivation:

The Zorach additive triangle is a triangle of integers that arises naturally when studying the differences between terms in integer sequences.

When we first encounter integer sequences, as children, we instinctively look for a pattern. One of the easiest ways to learn something about a given sequence is to make a new sequence out of the differences between consecutive terms. A number of basic sequences are constructed by simple patterns in the sequences generated thus. For example:

The Natural Numbers: 1,2,3,4,5, ...
This sequence has the constant sequence of all 1's as the difference between each term.
Powers of 2: 1,2,4,8,16, ...
This sequence has the property that the new sequence formed by taking the difference of consecutive terms is the original sequence.
Fibonacci Numbers: 1,1,2,3,5, ... This famous sequence is self-similar in the sense that the differences between terms form the original sequence, with a 0 appended at the front. The fibonacci numbers are related to the logarithmic spiral, a continuous example of self-similarity.

As any combinatorist surely knows, the powers of 2 and Fibonacci numbers are simply special cases of exponential sequences, sequences that occur naturally as the solution of linear recurrences. The Zorach additive triangle is in some sense the opposite of an exponential sequence: it is self-dissimilar, in a sense to be made precise below.

Definition:

We label each term of the triangle a_i,j, where i denotes the row and j the column (in the sense of the left diagonal being the first column). Thus j ≤ i. The triangle is such that a_i,j=a_i,j-1+a_i-1,j-1. Note that this is not enough information to specify the triangle completely: the first row must be specified. Note however that this recurrence is enough to determine, and easily construct the triangle from either its right or left diagonal.

Definition: The Zorach additive triangle is the triangle satisfying the linear recurrence given above, with each a_i,j a positive integer, such that no integer occurs more than once, and such that the column j=1 (i.e. the left diagonal), when viewed as an infinite tuple, is the smallest in the dictionary ordering. In other words, this means that each a_i,1 is taken to be as small as possible, given that the previous terms have the similar property.

This definition provides a simple, but very costly algorithm for generating the triangle: test numbers in the left diagonal one-by-one, starting with the smallest unused number, until we find one that does not cause any number to appear twice. It is clear that some number will always suffice: obviously we can add 1 to the largest number in the previous row, and this will cause no conflicts. It is almost trivial that the triangle is well-defined, i.e. that there is a unique triangle satisfying the description above, because any set of positive integers has a least element, so for each row we have a unique choice of the smallest integer satisfying the constraints.

For example, in generating the triangle, the algorithm first places a 1, then a 2. The 3 is calculated. Next 4 is placed, which generates 6 and 9. The next number to be tested is 5, but 5+4=9, which is already in the triangle, thus 5 must be skipped. The next number to be tried, 7, works.

Self-Dissimilarity:

While the concept of self-dissimilarity has been studied extensively in electronic and biological networks, this triangle provides a new and simple form of self-dissimilarity in the context of integer sequences. First, we note that if you view the rightmost diagonal as a starting sequence, the other diagonals, moving left, are simply the sequences generated as the differences between terms. By our very definition of the triangle, we have the following remarkable fact:

The right diagonal of the Zorach additive triangle has the property that, in the infinite set of sequences formed by taking the original sequence, and progressively taking sequences of differences between consecutive terms, no integer occurs more than once. Furthermore, it is the smallest sequence of positive integers with this property. (This provides an interesting alternative definition of the triangle; it is a good thought exercise to convince yourself that the two definitions are indeed equivalent.)

Growth Rate:

We can easily get some very crude bounds on the growth rate of the smallest and largest diagonals of the triangle, but no close formulas for the smallest diagonal are known. The largest diagonal is more predictable, but only because it is produced by adding terms in a predictable fashion.

Conjectures:

Little is known about the Zorach additive triangle. Like the prime numbers, it is a sequence for which one can ask many simple questions that are devilishly difficult to answer. Some obvious questions or conjectures are:

Conjecture: the triangle contains all natural numbers. (1998)
Although it seems intuitively unlikely that the triangle does not contain all natural numbers, this fact has been very difficult to prove, due to the fact that a potential conflict in placing a new number can occur in a column separated from the original number by an arbitrarily large number of calculations.
Conjecture: when using the algorithm suggested above, conflicts actually do appear in a column of arbitrarily large index.
This conjecture is less obvious intuitively, yet it is similarly difficult to prove. It may also be difficult to disprove--it would be more than simply finding a counterexample.

Although these are the simplest and most obvious conjectures one can come up with, there are nevertheless many other questions. For example, does the left diagonal decrease for an arbitrarily large number of consecutive elements?

Links:

The following are links to entries in the Online Encyclopedia of Integer Sequences.