Ulam numbers have zero density

This paper proves that the natural density of the sequence of Ulam numbers is zero, meaning the proportion of Ulam numbers within the interval $[1, k]$ approaches zero as $k$ tends to infinity.

The Gist

Imagine you are hosting a massive, infinite party where the guests are the natural numbers: 1, 2, 3, 4, 5, and so on.

In this paper, the author, Theophilus Agama, is investigating a very specific group of VIP guests called Ulam Numbers.

Who are the Ulam Numbers?

The Ulam numbers are a special club with a strict rule for entry. To get in, a number must be the smallest number that can be formed by adding two different previous members of the club in exactly one way.

• 1 and 2 are the founders (they just show up).
• 3 joins because $1 + 2 = 3$ (and that's the only way to make 3 from the founders).
• 4 joins because $1 + 3 = 4$ (unique way).
• 5 is rejected! Why? Because $5$can be made in two ways:$1+4$and$2+3$. Since the rule says "unique representation," 5 is kicked out.
• 6 joins because $2 + 4 = 6$ is the only way to make it from the current club members.

The sequence goes: 1, 2, 3, 4, 6, 8, 11, 13... and so on, forever.

The Big Question: Are They Crowded or Sparse?

For decades, mathematicians have wondered: How many Ulam numbers are there compared to all the numbers?

If you look at the first 1,000 numbers, maybe 50 are Ulam numbers. If you look at the first 1,000,000, maybe 400 are Ulam numbers.

• If the ratio stays steady (like 5%), the club is "thick."
• If the ratio keeps shrinking toward zero (like 0.00001%), the club is "thin" or "sparse."

Most people guessed the Ulam numbers were thin, but no one could prove it. This paper claims to finally prove it: The Ulam numbers are so sparse that their density is effectively zero.

How Did the Author Prove It?

The author uses two clever "detective tools" to solve the mystery.

Tool 1: The "Ladder" (Addition Chains)

Imagine you want to build a tower of blocks up to a specific height (a large Ulam number). You can only build the tower by stacking two existing blocks on top of each other. This is called an Addition Chain.

The author argues that to reach a very high Ulam number, you need a very long, specific ladder of steps.

• The Metaphor: Think of the Ulam numbers as rare gems hidden in a massive canyon. To find a gem, you have to climb a ladder. The author proves that the "ladder" required to reach the $n$-th Ulam number is so incredibly long and inefficient that the gems must be very far apart.
• The Result: As you go higher up the number line, the "ladder" gets so stretched out that the gems (Ulam numbers) become so rare that they disappear into the background noise.

Tool 2: The "Party Circle" (Circle of Partition)

This is the author's most creative invention. Imagine a giant round table (a circle) where every seat represents a number.

• If two people sit opposite each other and their seat numbers add up to the total number of seats, they are a "pair."
• The author uses this circle to count how many pairs of Ulam numbers can make a sum.

The Logic:
If Ulam numbers were common (dense), you would see lots of pairs of Ulam numbers adding up to other numbers.
However, the author sets up a mathematical "scale." He shows that for the Ulam numbers to exist as they do, the number of "mixed pairs" (one Ulam number + one non-Ulam number) must vastly outnumber the "pure pairs" (Ulam + Ulam).

By analyzing the geometry of this "Circle," he proves that the only way the math balances out is if the Ulam numbers are so few and far between that their density drops to zero.

The Conclusion

The paper concludes that as you count higher and higher into infinity, the Ulam numbers become so rare that if you picked a random number from the universe of integers, the chance of it being a Ulam number is zero.

In simple terms:
The Ulam numbers are like finding a specific type of rare butterfly in a forest. At first, you might see a few. But as you walk deeper into the infinite forest, you realize that for every butterfly you see, there are billions of trees. The butterflies are there, but they are so scattered that they don't really "fill" the forest at all.

The author has successfully proven that the Ulam numbers are the "ghosts" of the number world: they exist, but they are vanishingly thin.

Technical Summary

Here is a detailed technical summary of the paper "Ulam Numbers Have Zero Density" by Theophilus Agama.

1. Problem Statement

The paper addresses the Ulam density problem, a long-standing open question in number theory regarding the asymptotic behavior of the Ulam sequence $(U_m)_{m \ge 1}$.

• Definition: The Ulam sequence begins $1, 2, 3, 4, 6, \dots$and is defined recursively:$U_1=1, U_2=2$, and for$n > 2$,$U_n$is the smallest integer greater than$U_{n-1}$ that can be expressed as the sum of two distinct earlier terms in a unique way.
• The Question: Does the set of Ulam numbers have a positive natural density in the integers, or is it "thin" (density zero)?
  • Natural density is defined as $D[(U_m)] = \lim_{k \to \infty} \frac{|(U_m) \cap [1, k]|}{k}$.
• Context: While computational evidence and heuristics have long suggested the density is zero, a rigorous global asymptotic proof has been lacking.

2. Methodology

The author employs a novel synthesis of two distinct mathematical frameworks:

1. Addition Chains: The paper embeds finite prefixes of the Ulam sequence into addition chains to derive quantitative bounds on the sequence's growth.
2. Circle of Partition (CoP): A new combinatorial structure introduced by the author to analyze additive representations and count pairs of numbers summing to a target.

A. The Addition Chain Approach

• Embedding: The author proves that any finite sequence of Ulam numbers $(U_1, \dots, U_n)$ can be embedded into an addition chain that produces $U_n$.
• Regulators and Determiners: The chain is analyzed using "regulators" ($r_i$) and "determiners" ($a_i$). The length of the chain $\delta(n)$ is related to the target number $n$ and an aggregate "regulator parameter" $C(n)$.
• Key Inequality: The length of the chain is expressed as $\delta(n) = \frac{n-1}{C(n)}$.
• Bounding $C(n)$: By invoking classical lower bounds for the shortest addition chains (specifically relating to the Hamming weight of binary expansions), the author establishes that $C(n)$ grows at least as fast as $\frac{n}{\log_2 n}$.
• Density Derivation: Since the number of Ulam numbers up to $U_n$ is $n$, and $U_n$ is bounded by the chain length logic, the ratio $\frac{n}{U_n}$ is bounded by $\frac{1}{C(n)}$. As $n \to \infty$, $\frac{1}{C(n)} \to 0$, implying zero density.

B. The Circle of Partition (CoP) Approach

• Definition: For an integer $n$ and a subset $M \subset \mathbb{N}$, the CoP $C(n, M)$ is the set of points $[x]$ such that $x, n-x \in M$. The "axes" of this circle are pairs $([x], [y])$ where $x+y=n$.
• Combinatorial Decomposition: The author uses the CoP to decompose the count of additive representations of $n$ into three categories:
  1. Both summands are Ulam.
  2. Exactly one summand is Ulam.
  3. Neither summand is Ulam.
• Hypothesis: The proof relies on a verifiable counting hypothesis: the number of representations where one summand is Ulam and the other is not (for non-Ulam sums) is asymptotically negligible compared to the total number of representations.
• Result: Under this hypothesis, the density of points on the circle corresponding to Ulam numbers vanishes, confirming $D(U) = 0$.

3. Key Contributions

• Proof of Zero Density: The primary contribution is the rigorous proof that the natural density of Ulam numbers is zero ($D[(U_m)] = 0$).
• Introduction of the Circle of Partition (CoP): The paper introduces a new combinatorial tool (CoP) to visualize and count additive partitions. This structure allows for a geometric interpretation of additive number theory problems.
• Synthesis of Tools: The work uniquely combines classical results on addition chains (specifically lower bounds on chain lengths) with the new CoP formalism to tackle the Ulam problem.
• Quantitative Bounds: The paper provides specific inequalities relating the scale of the Ulam sequence to the "regulator" function $C(n)$, showing that the growth of Ulam numbers is sufficiently rapid to force the density to zero.

4. Main Results

• Theorem 5.1: The natural density of the Ulam sequence is zero.
  $$D[(U_m)] = 0$$
  The proof demonstrates that for any $l \ge U_n$, the proportion of Ulam numbers is bounded by $\frac{1}{C(n)} + \frac{1}{l}$, which tends to 0 as $n \to \infty$ because $C(n) \gg \frac{n}{\log_2 n}$.
• Theorem 6.8: An alternative proof using the CoP method. It states that if the number of mixed representations (Ulam + Non-Ulam) for non-Ulam sums is sufficiently small (specifically $O(n^{1-\epsilon})$), then the density is zero.

5. Significance

• Resolution of a Classic Problem: The paper claims to resolve a problem that has resisted rigorous solution despite decades of computational evidence.
• Methodological Innovation: The introduction of the "Circle of Partition" offers a fresh perspective on additive number theory, potentially applicable to other problems involving partition functions and additive bases.
• Structural Insight: The proof clarifies that the sparsity of Ulam numbers is a consequence of the constraints imposed by the "unique representation" rule, which forces the sequence to grow faster than linear density allows. The "regulator" concept provides a mechanism to quantify this growth constraint.

Conclusion

Theophilus Agama presents a proof that Ulam numbers are a set of zero natural density. By embedding Ulam sequences into addition chains and utilizing a novel combinatorial structure called the Circle of Partition, the author demonstrates that the constraints of unique additive representation force the sequence to be sufficiently sparse that its density vanishes in the limit.