Gaussian Sums

You may have heard the story of an incident that occurred
when Karl Friedrich Gauss attended grammar school. His teacher, apparently
having a bad day and wanting some quiet time for himself, gave young Gauss and
his classmates the task of adding up all of the integers from one to one
hundred. Gauss put his slate down long before any of the other boys did. The
skeptical teacher checked the result and, to his astonishment, saw that Gauss
had calculated the correct answer - 5050. While the other boys busily added
numbers one by one, Gauss had carried out a version of this:

1 | +2 | +3 | +4 | +... | +98 | +99 | +100 | =S |

100 | +99 | +98 | +97 | +... | +3 | +2 | +1 | =S |

101 | +101 | +101 | +101 | +... | +101 | +101 | +101 | =2S |

Thus Gauss transformed a tedious problem in addition into a simple problem of multiplication. We have from that table that 2S = 100 x 101, which we can divide by two to obtain S = 5050. We can generalize that procedure to find the sum of all of the integers up to any number N by writing more abstractly

1 | +2 | +3 | +... | +N-2 | +N-1 | +N | =S_{1}(N) |

N | +N-1 | +N-2 | +... | +3 | +2 | +1 | =S_{1}(N) |

N+1 | +N+1 | +N+1 | +... | +N+1 | +N+1 | +N+1 | =2S_{1}(N) |

which gives us the fact that 2S_{1}(N) = N x (N+1).
Dividing that equation by two gives us

(Eq'n 1)

We define the set of numbers S_{1}(N) generated by
all values of N as the set of the first-order Gaussian sums. We can lay this set
out in linear array, just as we lay out the integers of the counting sequence,
and match it, element for element, with that primal sequence, each S_{1}(N)
with its argument N:

N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | ... |

S_{1}(N) |
1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 | 66 | 78 | 91 | ... |

By analogy we can define a second-order Gaussian sum of
argument N as the sum of the first-order Gaussian sums up through the
first-order Gaussian sum of argument N. So we have

N | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

S1(N) | 1 | 3 | 6 | 10 | 15 | 21 | 28 | 36 | 45 | 55 |

S2(N) | 1 | 4 | 10 | 20 | 35 | 56 | 84 | 120 | 165 | 220 |

In the same manner we can define in general the j-th order
Gaussian sum as the sum of the (j-1)-th Gaussian sums up through the appropriate
argument; that is,

(Eq'n 2)

We can also write that equation as

(Eq'n 3)

In that form the equation gives us an obvious algorithm for
generating Gaussian sums in an array. If we draw the natural numbers in a column
and define them as the zeroth-order Gaussian sums, then we can say that any
element in the array, S_{j}(N), equals the sum of the number above it, S_{j}(N-1),
and the number above it on its left, S_{j-1}(N). Thus, we obtain

1 | |||||||||

2 | 1 | ||||||||

3 | 3 | 1 | |||||||

4 | 6 | 4 | 1 | ||||||

5 | 10 | 10 | 5 | 1 | |||||

6 | 15 | 20 | 15 | 6 | 1 | ||||

7 | 21 | 35 | 35 | 21 | 7 | 1 | |||

8 | 28 | 56 | 70 | 56 | 28 | 8 | 1 | ||

9 | 36 | 84 | 126 | 126 | 84 | 36 | 9 | 1 | |

10 | 45 | 120 | 210 | 252 | 210 | 120 | 45 | 10 | 1 |

If we add an extra column of ones to the left side of this array, we obtain a skewed version of Pascal's triangle. The j-th column of the array shown above comprises the set of all (j-1)-th order Gaussian sums, but Blaise Pascal had something completely different in mind when he devised his version of the array; rather than the columns, he saw the rows as the important subsets, doing so for a simple reason that will become clear shortly.

If we refer to the array above, imagining the extra column of
ones, we can see that we can convert the algorithm for generating the elements
into an algorithm that generates the rows. Pick any row, write it down, and then
immediately below it write it down again, but with the elements shifted one
column to the right. If you then add those two copies, column by column, you
will obtain a perfect copy of the row below the one that you chose. If we were
to start with the first row and apply that procedure repeatedly, we would
generate the whole array as far as we wish to go. The first four repetitions,
for example, give us

1 | 1 | ||||

+ | 1 | 1 | |||

1 | 2 | 1 | |||

+ | 1 | 2 | 1 | ||

1 | 3 | 3 | 1 | ||

+ | 1 | 3 | 3 | 1 | |

1 | 4 | 6 | 4 | 1 | |

+ | 1 | 4 | 6 | 4 | 1 |

1 | 5 | 10 | 10 | 5 | 1 |

Looking at that example, we must be impressed with its resemblance to the process of multiplication by the addition of partial products. Indeed, if we use commas to separate the elements of each subset, we can write, for example,

(1, | 3, | 3, | 1) | |

x | (1, | 1) | ||

1, | 3, | 3, | 1 | |

1, | 3, | 3, | 1 | |

(1, | 4, | 6, | 4, | 1) |

Because we can generate every row in Pascal's triangle by
multiplying the row above it by (1, 1) in that manner and because the first row
is (1, 1), we can see clearly that the n-th row of the triangle is simply the n-th
power of (1, 1). If we replace (1, 1) by (p, q), we recognize the rows of the
triangle as comprising the sets of the coefficients of the binomial theorem, the
n-th row comprising the coefficients of (p, q)^{n}.

Now identify p and q as representing the probabilities of two
mutually exclusive events such that p+q = 1. That means that one of the events
must happen and that both events cannot occur together. The Drunkard's Walk
gives us the classic example of such a binary probability. In that imaginary
experiment we envision ourselves sitting on a bus bench, observing a drunk
leaning against a lamppost across the street, and attempting to predict where he
will end up once he gets himself moving. We decide to let p represent the
probability that he staggers one step to our left and that q will represent the
probability that he staggers one step to our right. Those are certainly mutually
exclusive events and, seeing how drunk the man is, we figure that they are
equally likely to occur; that is, we figure that p = q = 0.5. For analysis of
the Drunkard's Walk we draw Pascal's triangle as an isoceles triangle with zero
at the apex:

n = 0 | 0 | ||||||||||||||||||

n = 1 | 1 | 1 | |||||||||||||||||

n = 2 | 1 | 2 | 1 | ||||||||||||||||

n = 3 | 1 | 3 | 3 | 1 | |||||||||||||||

n = 4 | 1 | 4 | 6 | 4 | 1 |

The line labeled n = 1 clearly represents the two possible positions that the drunk can occupy after taking one step: one step to the right and one step to the left of the lamppost (marked by the zero on line n = 0). After taking two steps the drunk could occupy one of three possible positions; two steps to the right of the lamppost, at the lamppost, and two steps to the left of the lamppost. We see only one way in which he could be two steps to the right of the lamppost (he took two successive steps to the right), two ways in which he could return to the lamppost (he took one step to the right and then one step to the left or he took one step to the left and then one step to the right), and only one way in which he can end up two steps to the left of the lamppost: line n = 2 shows those counts. In general the n-th line of the triangle represents the positions that the drunk could occupy after taking n steps and the number in each position represents the number of ways in which the drunk could have reached that position (that is, the number of different sequences of left and right steps that come to that position). Each number is proportional to the probability, relative to the probabilities associated with the other possible positions, that the drunk will occupy the given position after taking the requisite number of steps.

For convenience we want a formula that will enable us to
calculate directly the number in the i-th position of the n-th row (with the
index i counted from the left end of the row and taking the successive values 0
through n). To reach the i-th position the drunk must have taken i steps to the
right and n-i steps to the left, so we need to ask in how many different ways
can we combine i rightward steps and n-i leftward steps. To answer that question
we could, in theory, mark n spaces on a line and then place n-i markers, each
bearing an L, and i markers, each bearing an R, on the spaces. We might begin
with the simplest arrangement, then shift the markers, two at a time, to create
new arrangements, and tally up the number of different arrangements that we
generate. However, it's easier to notice that we have n ways to place the first
L-marker, n-1 ways to place the second L-marker for each way of placing the
first L-marker, and so on up to i+1 ways to place the n-i-th L-marker; thus, the
number of different ways in which we can place all n-i L-markers on n spaces
equals

(Eq'n 4)

Likewise, we can count n!/(n-i)! different ways to place the i R-markers on n spaces. (Note that we are obliged to define 0! = 1).

Neither of those formulae gives us the correct answer to our question. We know that's true to logic because neither formula satisfies the criterion that for any given value of n, the sequence of Pascal numbers generated by all possible values of i must be symmetrical about the position corresponding to i = n/2. But our analysis was correct, as far as we can see, so the formulae are wrong in the sense of missing something rather than in the sense of being misguided.

We can discern what's missing from our formulae by laying n-i
L-markers on n-i spaces. Using the procedure above, we count (n-i)! different
ways to create the specified arrangement, but they're all the same arrangement,
one marker to a square. Thus, we have incorporated into our derivation the
distinguishability error, the tacit assumption that of all the markers each
carries a serial number or other trait that makes it unique and distinguishable
from all the other markers. We have counted each arrangement, properly defined
as the set of n-i squares on which the L-markers are laid, (n-i)! times instead
of once, as we should have done, though we correctly, if tacitly, assumed that
we have only one way to lay down the i R-markers once we have laid down the
L-markers. We can correct the formula in Equation 4, then, by dividing it by (n-i)!
(and correct our second formula by dividing __it__ by i!). So now we know
that the correct number of ways to arrange n-i L-markers and i R-markers on n
spaces is given by

(Eq'n 5)

That formula certainly satisfies the symmetry criterion
stated above, but now we may wonder whether C_{ni} is guaranteed to be
an integer for all possible values of n and i. In order to address that concern
we eliminate (n-i)! from Equation 5 by writing

(Eq'n 6)

We thus have i successive integers as factors multiplied
together, which product is divided by the product of the first i integers. But
for any given integer k every k-th integer on the number line is evenly
divisible; therefore, if we have k or more successive integers, then at least
one of them will be evenly divisible by k. In Equation 6 we have the product of
i successive integers in the numerator and the product of the first i integers
in the denominator, each of which is thus guaranteed to have at least one
integer in the numerator that it divides evenly. Thus, for any values n and i, C_{ni}
will be an integer.

But now a question comes up and wants to be answered.
What happens if one or more of the integers in that sequence of i successive
integers is a prime number? Does the fact that a prime number contains no
factors other than itself interfere with our requirement that the numbers C_{ni}
comprise only integers?

We know that we must answer no to that last question.
So now the answer to the first question becomes clear: the composite numbers in
the sequence must contain all of the factors necessary to preserve the integrity
of the C_{ni}.

As an example, consider the twin primes, pairs of prime
numbers that differ each from the other by two. With the composite number
that lies between them on the number line, each set of twin primes makes up a
trio of successive integers. Necessarily an even number, the composite
number of the trio contains two as a factor at least once. But each
composite number in these trios also contains three at least once as a factor,
as required to preserve the integrity of the C_{ni}. To illustrate
that fact I have listed all of the prime twins up to 1997/1999 in an appendix to
this essay and included the maximal factorization of the composite number in
each pair.

That example does not constitute any kind of proof that the C_{ni}
must always be integers: my statement that any product of i successive integers
must be evenly divisible by the first i integers came with its own proof.
Instead, the example tells us something new about prime numbers.

If you examine the maximal factorizations of the composite numbers on the number line, you will see that the even numbers include a large set whose members do not contain three as a factor. A naive guess would tell us that a pair of twin primes could flank any of those three-less composites, but the proposition given above necessarily entails that such a thing cannot happen. We thus have a criterion that restricts where prime numbers can occur on the number line.

That's a small thing to discover about numbers. But if we accumulate enough such small things, we may eventually have enough information to create a true Mendeleevian table of the prime numbers, what mathematicians like to call the atoms of arithmetic.

Now we can return to Gaussian sums and relate the numbers C_{ni}
to them. The index i-1 = j is the same as the order of the Gaussian sum: we can
see that in the fact that each value of i represents a column in the
left-justified version of Pascal's triangle (which I have depicted, minus the
0-th column, just below Equation 3). Because each column is shifted down one
space relative to the column to its left, we have the relation of the row
indices as N = n=i+1 = n-j, so we can make the replacements n = N+j and i = j+1
in Equation 5 to obtain

(Eq'n 7)

This derivation, the replacement of a series of sums with a
ratio of multiple products, did not go as I expected it to go. Once I had
obtained the formula for calculating the first-order Gaussian sums, as Gauss
did, I attempted to devise a similar formula for the second-order Gaussian sums.
I drew the sum of the first-order elements horizontally and then below each
element I drew vertically the sum of the zero-th order elements that comprise
it. I then added __those__ elements diagonally, obtaining the overall sum of
N ones, N-1 twos, N-2 threes, and so on; thus, I ended up with

S_{2}(N) = NS_{1}(N) + (0x1 +
1x2 + 2x3 + ... + (N-1)xN).

(Eq'n 8)

This observation might simply reflect my own ignorance, but I
was unable to find a way to express the series that comprises the second term on
the right side of that equation as a function of either S_{1} or S_{2},
at least not in a way that would allow me to express S_{2} as a function
of S_{1}. Thus stymied, I digressed into an exploration of the recursion
relation that allows us to construct the S_{j}(N) through successive
additions.

That exploration led through the binomial theorem to Pascal's triangle and then, via the Drunkard's Walk and combinatorics, to the formula by which we can calculate any Gaussian sum from its order index (j) and its argument (N). That formula is what I was seeking to derive through the kind of analysis that led to Equation 8. I am tempted to think that the necessity of deriving that formula by an indirect route offers some evidence in the argument over whether mathematics is invented or discovered, but before I pursue that thought I need to point out one minor distinction.

We have fundamentally two kinds of sets into which we place numbers. The first kind is the set whose members are selected by an arithmetic process that generates them. The Gaussian sums provide a perfect example of such a set. The numbers generated by successive additions are guaranteed to be members of the set because the process of successive additions defines those members, automatically satisfying the "all and only" standard for generating members. The second kind of set is one whose members are selected by some criterion that they must satisfy, a criterion established independent of any process that generates the members. The set of Pythagorean Triples is a perfect example of such a set. Only those trios of integers that satisfy the Pythagorean Equation are members of the set and we are obliged then to devise some algorithm that generates all of those trios and only those trios. Although the generating equations for those trios can be deduced from a graphic representation of the defining equation, the need for additional criteria to restrict the range of the seeds that generate the trios indicates that deriving the generating equations alone is not necessarily adequate to meet the "all and only" standard for membership in the defined set. Those criteria act as boundary conditions, shaping the "field equations" into specific solutions.

Finally, let's consider an analogy. If I create a landscape, I can go anywhither within it, unless I have created within it barriers that diminish my power to traverse it (and I wonder whether I could actually give up the power to traverse what I create). On the other hand, if I encounter a landscape that I did not create, then I have no guarantee that I can reach any point within it: I am obliged to find paths through that landscape by exploring it. My experience with Gaussian sums implies that mathematics is a landscape of the second kind. It seems that mathematics couldn't be a landscape of the first kind, unless I have somehow built in constraints that oblige me to take the indirect route to the formula that I want. Perhaps the rules of logic, devised prior to mathematics, automatically create such constraints, but then who created the rules of logic?

bcbcbccbcbcb

Appendix I

The following list of twin primes is adapted from the table on Pages 242-249 in the 43rd Edition (1961-1962) of the Chemical Rubber Company's Handbook of Chemistry and Physics.

5 (2x3) 7 | 11 (2x2x3) 13 | 17 (2x3x3) 19 |

29 (2x3x7) 31 | 41 (2x3x7) 43 | 59 (2x2x3x5) 61 |

71 (2^{3}x3x3) 73 |
101 (2x3x17) 103 | 107 (2^{2}x3^{3}) 109 |

137 (2x3x23) 139 | 149 (2x3x5^{2}) 151 |
179 (2^{2}x3^{2}x5) 181 |

191 (2^{6}x3) 193 |
197 (2x3^{2}x11) 199 |
227 (2^{2}x3x19) 229 |

239 (2^{4}x3x5) 241 |
269 (2x3^{3}x5) 271 |
281 (2x3x47) 283 |

311 (2^{3}x3x13) 313 |
347 (2^{2}x3x29) 349 |
419 (2^{2}x3x5x7) 421 |

431 (2^{4}x3^{3}) 433 |
461 (2x3x7x11) 463 | 521 (2x3^{2}x29) 523 |

569 (2x3x5x19) 571 | 599 (2^{3}x3x5^{2}) 601 |
617 (2x3x103) 619 |

641 (2x3x107) 643 | 659 (2^{2}x3x5x11) 661 |
809 (2x3^{4}x5) 811 |

821 (2x3x137) 823 | 827 (2^{2}x3^{2}x23) 829 |
857 (2x3x11x13) 859 |

881 (2x3^{2}x7^{2}) 883 |
1019 (2^{2}x3x5x17) 1021 |
1031 (2^{3}x3x43) 1033 |

1049 (2x3x5^{2}x7) 1051 |
1061 (2x3^{2}x59) 1063 |
1091 (2^{2}x3x7x13) 1093 |

1151 (2^{7}x3^{2}) 1153 |
1229 (2x3x5x41) 1231 | 1277 (2x3^{2}x71) 1279 |

1289 (2x3x5x43) 1291 | 1301 (2x3x7x31) 1303 | 1319 (23x3x5x11) 1321 |

1427 (2^{2}x3x7x17) 1429 |
1451 (2^{2}x3x11^{2}) 1453 |
1481 (2x3x13x19) 1483 |

1487 (2^{4}x3x31) 1489 |
1607 (2^{3}x3x67) 1609 |
1619 (2^{2}x3^{4}x5) 1621 |

1667 (2^{2}x3x139) 1669 |
1697 (2x3x283) 1699 | 1721 (2x3x7x41) 1723 |

1787 (2^{2}x3x149) 1789 |
1871 (2^{4}x3^{2}x13) 1873 |
1877 (2x3x313) 1879 |

1931 (2^{2}x3x7x23) 1933 |
1949 (2x3x5^{2}x13) 1951 |
1997 (2x3^{3}x37) 1999 |

Appendix II

The Prime Numbers up to 499

1 | 2 | 3 | 5 | 7 | 11 | 13 | 17 | 19 | 23 | 29 | 31 |

37 | 41 | 43 | 47 | 53 | 59 | 61 | 67 | 71 | 73 | 79 | 83 |

89 | 97 | 101 | 103 | 107 | 109 | 113 | 127 | 131 | 137 | 139 | 149 |

151 | 157 | 163 | 167 | 173 | 179 | 181 | 191 | 193 | 197 | 199 | 211 |

223 | 227 | 229 | 233 | 239 | 241 | 251 | 257 | 263 | 269 | 271 | 277 |

281 | 283 | 293 | 307 | 311 | 313 | 317 | 331 | 337 | 347 | 349 | 353 |

359 | 367 | 373 | 379 | 383 | 389 | 397 | 401 | 409 | 419 | 421 | 431 |

433 | 439 | 443 | 449 | 457 | 461 | 463 | 467 | 479 | 487 | 491 | 499 |