Gaussian Sums

Back to Contents

    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 =S1(N)
N +N-1 +N-2 +... +3 +2 +1 =S1(N)
N+1 +N+1 +N+1 +... +N+1 +N+1 +N+1 =2S1(N)

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

(Eq'n 1)

    We define the set of numbers S1(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 S1(N) with its argument N:

N 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
S1(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, Sj(N), equals the sum of the number above it, Sj(N-1), and the number above it on its left, Sj-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 Cni 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, Cni 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 Cni 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 Cni.

    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 Cni.  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 Cni 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 Cni 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

S2(N) = NS1(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 S1 or S2, at least not in a way that would allow me to express S2 as a function of S1. Thus stymied, I digressed into an exploration of the recursion relation that allows us to construct the Sj(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

Back to Contents

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 (23x3x3) 73 101 (2x3x17) 103 107 (22x33) 109
137 (2x3x23) 139 149 (2x3x52) 151 179 (22x32x5) 181
191 (26x3) 193 197 (2x32x11) 199 227 (22x3x19) 229
239 (24x3x5) 241 269 (2x33x5) 271 281 (2x3x47) 283
311 (23x3x13) 313 347 (22x3x29) 349 419 (22x3x5x7) 421
431 (24x33) 433 461 (2x3x7x11) 463 521 (2x32x29) 523
569 (2x3x5x19) 571 599 (23x3x52) 601 617 (2x3x103) 619
641 (2x3x107) 643 659 (22x3x5x11) 661 809 (2x34x5) 811
821 (2x3x137) 823 827 (22x32x23) 829 857 (2x3x11x13) 859
881 (2x32x72) 883 1019 (22x3x5x17) 1021 1031 (23x3x43) 1033
1049 (2x3x52x7) 1051 1061 (2x32x59) 1063 1091 (22x3x7x13) 1093
1151 (27x32) 1153 1229 (2x3x5x41) 1231 1277 (2x32x71) 1279
1289 (2x3x5x43) 1291 1301 (2x3x7x31) 1303 1319 (23x3x5x11) 1321
1427 (22x3x7x17) 1429 1451 (22x3x112) 1453 1481 (2x3x13x19) 1483
1487 (24x3x31) 1489 1607 (23x3x67) 1609 1619 (22x34x5) 1621
1667 (22x3x139) 1669 1697 (2x3x283) 1699 1721 (2x3x7x41) 1723
1787 (22x3x149) 1789 1871 (24x32x13) 1873 1877 (2x3x313) 1879
1931 (22x3x7x23) 1933 1949 (2x3x52x13) 1951 1997 (2x33x37) 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