The Sums of Signed Quantities

From the first n integers we can form 2ⁿ sums, taking the integers as either positive or negative. For example, from the first three integers, 1, 2, 3, we can form the eight sums

In general the 2ⁿ sums range from –n(n+1)/2 to +n(n+1)/2. For any given n the sums all have the same parity (all odd or all even), because we can change from one to another by a sequence of sign reversals, each of which changes the value by an even number. The sums are all even for n congruent to 3 or 0 (mod 4), and otherwise all odd. As n increases, the number of sums increases exponentially, whereas the range of values increases only as the square of n, so there will be many duplicate sums. In fact, by the central limit theorem, the summands (of the appropriate parity) approach a normal distribution over the range, with the maximum density at 0 (or 1 for odd distributions). Thus the distribution of sums for a given n is (asymptotically) determined by the number of zero sums. We will call this Z_n(0). (As can be seen above, we have Z₃(0) =2, because two of the sums equal zero.) This distribution asymptotically approaches

Notice that t is divided by 2 in the expression for the Gaussian distribution because it ranges over only the even, or only the odd, integers. By inspection we find that the first several values of Z_n(0) are

As n increases, the number of terms increases exponentially, so to determine the exact values we obviously can’t simply evaluate each of the 2ⁿ sums. One method for evaluating Z_n(0) is in terms of the cosine function. Recall the basic trigonometric identity

This is obvious from considering the cosines written in exponential form. (We can also consider the generating function (x^–1 + x¹)(x^–2 + x²)…(x^–n + xⁿ).) Applying this repeatedly, we have the general identity

where the summation inside the cosine on the right side is evaluated over all the 2ⁿ combinations of signs. Now suppose we put A_j = jx. In that case the argument of each cosine on the right side is one of the 2ⁿ signed sums multiplied by x. Consequently, each of the terms for which the argument vanishes contributes a constant 1 to the summation, whereas terms for which the argument does not vanish are cosines whose integrals vanish over any whole number of half-cycles (i.e., 0 to π, since the cosine integral vanishes over this range). Thus we have

This equation is exact, although it must be evaluated with high numerical precision to yield exact results for large n. For example, the exact value of Z₄₈(0) is 1140994231458, but performing the calculation using the above formula with just 16 digits of precision we get the result 1140994231462, which differs (by 4) from the exact value due to the limited precision.

The product of cosines cos(1x)cos(2x)… cos(nx) approaches a sequence of pulses at multiples of π. If n is congruent to 1 or 2 (modulo 4) the pulses have opposite signs, as shown in the figure below for n=6, so the integral vanishes.

On the other hand, if n is congruent to 0 or 3 (modulo 4) the pulses are strictly positive, as illustrated for the case n=7 in the figure below, which results in a positive integral.

For larger values of n the product of cosines is virtually zero everywhere except very near multiples of π, where it approaches an impulse function with a normal (Gaussian) shape. This makes it possible to estimate Z_n(0) merely by evaluating the area under one of these Gaussian pulses. For example, the figure below shows the product of cosines for n = 60 in the region close to zero.

The function is virtually zero except for pulses of this shape centered on multiples of π. Hence we approximate Z_n(0) by just integrating over the small range that covers one of these pulses, or even just half a pulse (and doubling the result), since the shape is symmetrical.  Thus for some small d enclosing the pulse we have the approximation

Clearly for the case n = 60 we must take d greater than .01, but the precise choice affects the numerical accuracy since we are working at the limits of our computational precision. We find that the function has stable values for much of the range, as shown below.

This shows the difference between the approximate value for a given d and the exact value. Focusing on the first plateau, we can expand this range as shown below.

The local peak occurs at a value of d = 0.0325, which yields the result

Thus by integrating only over the range from 0 to 0.0322 with just 16 digits of precision we match the correct result to 13 significant digits.

This is an interesting example of how non-trivial information about a set of 2ⁿ sums can be extracted from the behavior, over a very short range, of a product of just n factors, especially considering that the product approaches a simple and well-behaved continuous shape, so the complexity of evaluating the area is low, i.e., it requires evaluating the product at only a small number of points. In fact, as the product of cosines (with arguments near zero) approaches a normal distribution with central value of 1, there is only a single degree of freedom, namely, the standard deviation parameter, and this can be evaluated at any single point. The product of cosines (near zero) approaches the Gaussian

and the area under this Gaussian pulse is simply s√(2π). (To prove that the product of cosines approaches the Gausian function for small x, it suffices to take the natural log of the left side and evaluate in the limit of small x.) Hence we have the asymptotic relation

Now, to determine the parameter s_n we need only evaluate C_n(x) for a single value of x (other than 0), and then we can solve the previous equation for s_n to give

Noting that as x approaches zero the value of ln(cos(u)) approaches –u²/2, we have

Inserting this into the previous expression for Zn(0) gives the asymptotic result

This expression provides a fairly close asymptotic result, as can be seen in the table below.

As n increases, equation (1) is asymptotic to the simple expression (2ⁿ/n^3/2)√(6/π), as has been noted previously (e.g., Sullivan, 2013), but the simplified form is significantly less close, as shown in the two right hand columns in the table above.

Return to MathPages Main Menu