### Philippe Beaudoin

Shared publicly -**A hidden signal in the Ulam sequence**

The

**Ulam sequence**is a sequence of positive integers a_n, where a_1=1, a_2=2, and where each a_n for n > 2 is defined to be the smallest integer that can be expressed as the sum of two distinct earlier terms in a unique way.

The first few terms of the sequence are shown in the picture: 1, 2, 3, 4, 6, 8, 11, 13, 16, 18, 26, 28, 36, 38, 47. The third term is 3, because 3=1+2. The fourth term is 4, because although 4 can be expressed in two ways as the sum of two earlier terms (1+3, or 2+2) the sum “2+2” is not a sum of

*distinct*earlier terms. The fifth term is not 5, because 5=1+4=2+3; rather, it is 6, which is 2+4. The sixth term is not 7, because 7=1+6=3+4, but rather 8, which is 2+6. And so on.

The Ulam sequence is named after the Polish-American mathematician

**Stanisław Ulam**(1909–1984) who introduced it in 1964 in a survey on unsolved problems. Ulam remarked that it can be notoriously difficult to answer questions about the properties of sequences like this one, even if they are defined by a simple rule.

In particular, Ulam was interested in whether one could find the

**asymptotic density**of this particular sequence. Roughly speaking, this is asking what proportion of the integers in between 1 and N are members of the Ulam sequence if N is very large. Empirically, the answer seems to be about 7.4%, but there is not even a proof that the density is bigger than Ulam's predicted value of zero. Ulam's sequence has been described as “quite erratic” and it has been said that it “does not appear to follow any recognizable pattern”.

Even though the Ulam sequence has been around for 50 years, very little is known about it. However, the recent paper

*A Hidden Signal in the Ulam sequence*by

**Stefan Steinerberger**(http://arxiv.org/abs/1507.00267) unearths some surprisingly rigid structure in the sequence. In the context of Fourier series, it is natural to study the function f_N(x) obtained by summing the values of cos(a_n x) from n=1 to N. The expected result here is that whenever x is not zero, the absolute value of f_N(x) should be approximately equal to the square root of N. However, this is

*not*what happens, because there is a mysterious constant α, equal to about 2.571, such that f_N(α) is approximately equal to c times N, for a negative constant c around –0.8.

The existence of such a constant can be thought of (metaphorically) as a signal embedded in the sequence. Steinerberger shows that the constant α is given by 2.5714474995...; there is another such constant at 2π–α by symmetry. The signal can be demonstrated in an elementary way by considering the values of cos(α a_n), measuring angles in radians: remarkably, with a very small number of exceptions, the values are all negative.

The paper also considers versions of the Ulam sequence in which the first two terms are replaced with other numbers, and similar phenomena occur. The case where a_1=2 and a_2=3 seems to be especially striking.

**Relevant links**

Stanisław Ulam was the bomb: he participated in the Manhattan Project and originated the Teller–Ulam design of thermonuclear weapons. He was also the chair of my department in Boulder in the 1960s. More information on Ulam can be found here: https://en.wikipedia.org/wiki/Stanislaw_Ulam

*The On-Line Encyclopedia of Integer Sequences*has more about the Ulam sequence: https://oeis.org/A002858

#mathematics #scienceeveryday #spnetwork arXiv:1507.00267