Introduction

Given a sequence {a1,a2,...,an}, we can compute the 2n sums ±a1±a2,...±an. We can also compute the frequency of any particular value. For example, given the sequence {1,2,3,4}, the 16 sums are {-10,-8,-6,-4,-4,-2,-2,0,0,2,2,4,4,6,8,10} and the frequency of the even numbers between -10 and 10 is {1,1,1,2,2,2,2,2,1,1,1}. This simple example is not very interesting. However, as the number of terms in the sequence is increased, the frequency curve becomes more interesting. We examine several sequences below.


Consecutive Numbers

The curve below shows the frequency distribution of sums of the first 20 numbers {1,2,3,...,20}. In this case, and any sequence that grows slowly, the result is a near-Gaussian distribution. The horizontal axis gives the value of the sum; the vertical axis gives the frequency of the sum.

Frequency of sums of consecutive integers


Prime Numbers

The curves below show the frequency distribution of sums of the first 17, 18, 19, and 20 odd primes {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73}. As in the case above, the result is a near-Gaussian distribution.

Let Sn = a1+a2+...+an. If n is even, then all the even numbers between -Sn+20 and Sn-20 are represented as an extremal sum of the sequence.

Frequence of sums of prime numbers


Squares

The curve below shows the frequency distribution of sums of the first 27 squares {1,4,9,...,729}. Although the curve has a Gaussian appearance, there is additional structure. This gives us a hint that frequency may be less predictable than suggested by the examples above.

Frequency of sums of squares


Powers of Sqrt(2)

The curve below shows the frequency distribution of sums of the first 20 powers of Sqrt(2), rounded to the nearest integer {1,2,3,4,6,8,11,16,23,32,45,64,91,128,181,256,362,512,724,1024}. Rather surprisingly, the distribution is not Gaussian. All odd numbers from -601 to 601 have the same frequency: 512.

Frequency of sums of powers of sqrt(2)


Powers of 1.6

The curve below shows the frequency distribution of sums of the first 20 powers of 1.6, rounded to the nearest integer {1,2,3,4,7,10,17,27,43,69,110,176,281,450,721,1153,1845,2951,4722,7556}. Again, the non-smooth shape of the curve is rather surprising. Also note that the maximum frequency is not at 0 or ±1.

Frequency of sums of powers of 1.6


Fibonacci Numbers

The curve below shows the frequency distribution of sums of 20 Fibonacci numbers F(2) to F(21) {1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946}. The chaotic shape of the curve is amazing! Although the frequency distribution is positive for all even numbers, the frequency is only 2 in 68 instances. Recall that the Fibonacci numbers have a limiting common ratio of about 1.62. Hence, one may have expected that this curve would be similar to the curve for the powers of 1.6. However, the exact construction of the Fibonacci numbers must have a powerful effect here.

Frequency of sums of Fibonacci numbers


More Details

  • For the constant sequence {1,1,...,1}, the frequency is exactly the binomial distribution.

  • For the doubling sequence {1,2,4,...,2n}, the frequency of all sums is 1; all sums are odd. If a sequence grows faster than 2n, its frequency plot is not interesting.

  • All the sums for a given sequence have the same parity; sums of opposite parity are not possible.

  • A lemma due to Littlewood and Offord, but improved by Erdos, shows that frequency of every sum must be ≤ Binomial(n,Floor(n/2)). Equality is attained only for a constant sequence, such as {1,1,...,1}.

  • It appears that Erdos' result can be improved; the highest frequency is approximately Binomial(n,Floor(n/2)) / SD, where SD is the standard deviation of the 2n numbers ±a1,±a2,...,±an. For example, for large n,
    • SD(± consecutive integers) ≈ Sqrt(1/3) n
    • SD(± consecutive squares) ≈ Sqrt(1/5) n^2
    • SD(± primes) ≈ 0.577 Prime(n)
    There is good agreement between the maximum frequency in the plots above and the formulas given here.

  • The computation of the distributions is very easy. The 2n individual sums are not computed.

  • Roland Bacher points out that the frequencies can be viewed as the possible winnings in a game between two players. The wagers are the numbers a1,a2,...,an.

  • The frequencies are the coefficients of the product (1/x^a1 + x^a1)(1/x^a2 + x^a2)...(1/x^an + x^an) when it is expanded as a polynomial in positive and negative powers of x.

  • Ron Knott points out that the frequency distribution is essentially the same as sums of all subsets of the set {a1,a2,...,an}. In that case, the sums range from 0 to S, instead of -S to S, where S = a1+a2 +...+an.

  • Pieter Moree points out that a theorem of H. F. Scherk (proved by Pillai in 1928), states that a prime p of even index (3,7,13,19,...) can be represented as an extremal sum of the set consisting of 1 and the primes less than p. This is proved in chapter 3, section 11, of Sierpinski's "Elementary Theory of Numbers" book. Sierpinski's book on-line.

  • Question: given a frequency distribution, can the sequence {a1,a2,...,an} be determined?

Last updated on 14 August 2003, T. D. Noe, [email protected]