The Golden Sieve

This paper revisits the golden sieve to demonstrate its generation of Wythoff pairs from natural numbers, establishes its connection to hiccup sequences and Fraenkel's partitions when applied to arithmetic progressions, and introduces a new extraction sieve governed by affine transformations of hiccup parameters.

The Gist

Imagine you have a long line of people standing in order, holding numbers on their chests: 1, 2, 3, 4, 5, and so on. This is the starting point of our story.

Now, imagine a magical game called "The Golden Sieve." It's a game of elimination, but with a twist: the rules are written in the line itself. The game doesn't just delete random people; it uses the people currently standing in the line to decide who gets kicked out next.

Here is how the game works, explained simply:

The Game Rules (The "Golden Sieve")

1. The Pointer: At every step, you look at the person standing in the $n$-th spot in the current line. Let's say their number is $X$.
2. The Target: You then count $X$ spots down the line. The person standing at that new spot is the one who gets removed.
3. The Loop: The line closes up the gap. You repeat this forever.

The Magic: Even though the rule is simple, the pattern of who survives and who gets deleted is incredibly rigid and beautiful. It's like a machine that, once started, can never change its rhythm.

The "Wythoff" Connection (The Golden Ratio)

When you start with the natural numbers (1, 2, 3...), the survivors and the deleted people form two perfect, interlocking lines.

• The Survivors are the people who never get kicked out.
• The Deleted are the ones who leave.

The author of this paper discovered that these two lines are governed by the Golden Ratio ($\phi \approx 1.618$), a famous number found in sunflowers, seashells, and art.

• The survivors are roughly at positions $1.618, 3.236, 4.854...$
• The deleted people fill in the gaps perfectly.

This is a known mathematical puzzle called the Wythoff Pair, but the author shows us a new, dynamic way to create it: by playing this "pointer game" instead of just calculating formulas.

The "Hiccup" Effect

The most fascinating part is how the gaps between survivors behave.
Imagine the survivors are walking down a path. Sometimes they take a small step (1 unit), and sometimes a big step (2 units).

• The Rule: Whether they take a small or big step depends on a "hiccup."
• The Hiccup: If the current step number ($n$) is a number that already exists in the list of survivors, they take a big step. If it's not, they take a small step.

It's like a self-fulfilling prophecy: Because you are a survivor, you get to take a bigger step next time. This creates a rhythm that is complex but perfectly predictable, known as a Sturmian word (which sounds like a fancy way of saying "a pattern that never repeats exactly but follows a strict rule").

The "Silver Sieve" (The Extraction Method)

The paper also introduces a second game called the "Extraction Sieve" (or Silver Sieve).

• Instead of looking at the $n$-th person to find a target, this game simply grabs the first person in line (the smallest number), keeps them as a survivor, and then deletes a specific number of people after them based on a rule.
• This method is more direct. It's like a factory conveyor belt: grab the first item, toss out the next few, grab the next, and so on.
• This "Silver Sieve" creates a different famous sequence (the Bosma–Dekking–Steiner sequence), which is related to the "Silver Ratio" ($1 + \sqrt{2}$).

What Happens with Different Starting Lines?

The author tested this game not just on 1, 2, 3... but on other lines, like:

• Even numbers: 2, 4, 6, 8...
• Numbers with a remainder: 3, 6, 9, 12...

The result? The game still works perfectly, but the "steps" change size.

• If you start with numbers that jump by 2, the survivors jump by 2 or 4.
• If you start with numbers that jump by 3, the survivors jump by 3 or 6.

The math shows that the "Golden Sieve" is a universal machine. No matter what arithmetic line you feed it, it spits out a perfectly organized pattern of survivors and deletions, governed by a simple quadratic equation (a type of math formula).

The "Square" Twist

The author also tried the game on Perfect Squares: 1, 4, 9, 16, 25...
This gets weird. Because the gaps between squares get bigger and bigger, the "pointer" jumps wildly.

• The pattern here isn't a simple "hiccup." It's a nested hiccup.
• The rule for taking a big step depends on whether the step number is a square of a survivor.
• It's like a Russian nesting doll: the rule for the outer layer depends on the rule for the inner layer, which depends on the rule for the layer inside that.

Why Does This Matter?

You might ask, "Who cares about deleting numbers?"

1. Game Theory: These patterns describe the winning strategies for certain board games (like Nim). If you know the pattern, you know how to win.
2. Computer Science: These sequences are used to generate random-looking numbers that are actually predictable, which is useful for cryptography and data compression.
3. Beauty: It shows that even in a chaotic process of "deleting things," nature (or math) finds a way to create perfect, interlocking order.

Summary Analogy

Think of the Golden Sieve as a dance floor.

• The dancers are the numbers.
• The DJ (the rule) looks at the person at position $n$ to decide who gets to leave the floor.
• The people who stay form a rhythm (the survivors).
• The people who leave fill the gaps.
• The rhythm is so perfect that it matches the Golden Ratio, the most famous number in nature.

The paper is essentially a manual on how to run this dance floor for different types of music (different starting lines) and discovering that the dancers always find a way to sync up, creating beautiful, mathematical patterns out of chaos.

Technical Summary

Here is a detailed technical summary of the paper "The Golden Sieve" by Benoit Cloitre.

1. Problem Statement and Context

The paper investigates a deterministic deletion process on increasing sequences of positive integers, termed the Golden Sieve. Introduced by the author in 2002 (OEIS A099267), this process is a self-referential mechanism where the value of the $n$-th element in a sequence determines the position of the element to be deleted in the next step.

The primary objectives are:

1. To rigorously analyze the sieve when applied to arithmetic progressions $W_0 = aN + b$.
2. To establish connections between the sieve's output and hiccup sequences (a class of self-referential two-gap recurrences studied by Fokkink and Joshi).
3. To link the sieve to Fraenkel's complementary equations, Wythoff's game, and Kimberling's rank transforms.
4. To introduce a complementary mechanism, the Extraction Sieve, and compare its behavior with the Golden Sieve.

2. Methodology

The author employs a combination of combinatorial analysis, number theory, and dynamical systems theory:

• Inductive Construction: The sieve is defined inductively. At step $n$, the pointer $h_n$ reads the $n$-th element of the current working sequence $W_{n-1}$. The element at position $h_n$ is then deleted to form $W_n$.
• Normalization: For arithmetic progressions $W_0 = \{an+b\}$, the author introduces normalized sequences $\sigma_n$ (survivors) and $\delta_n$ (deletions) by mapping $w \mapsto (w-b)/a$. This reduces the problem to a sieve on $\mathbb{N}$ with modified parameters.
• Rank Identities: The core analytical tool is deriving an affine relationship between the rank of a deleted element and the value of the survivor sequence.
• Gap Analysis: The paper analyzes the "gap word" $H(n)$, which encodes the difference between consecutive terms in the survivor sequence. It investigates whether this word is Sturmian, automatic, or morphic.
• Comparative Dynamics: A second mechanism, the Extraction Sieve, is defined where the minimum element is extracted, and subsequent elements are deleted based on a membership test. This is compared to the positional Golden Sieve.

3. Key Contributions and Results

A. The Golden Sieve on Natural Numbers ($W_0 = \mathbb{N}$)

• Wythoff Identification: When starting with $W_0 = \mathbb{N}$, the survivor sequence (shifted) and the deletion sequence correspond exactly to the lower and upper Wythoff sequences ($\lfloor n\phi \rfloor$ and $\lfloor n\phi^2 \rfloor$), where $\phi$ is the golden ratio.
• Hiccup Rules: Both sequences satisfy a self-referential "hiccup" recurrence where the gap between terms is determined by whether the current index belongs to the sequence itself.
  • Deletions: $d_n - d_{n-1} \in \{2, 3\}$.
  • Survivors: $s_n - s_{n-1} \in \{1, 2\}$.
• Fibonacci Invariance: The Fibonacci numbers form an invariant subset of the survivor function ($s_{F_k} = F_{k+1}$).

B. The Golden Sieve on Arithmetic Progressions ($W_0 = aN + b$)

This is the paper's main theoretical contribution.

• Pointer-Survivor Identity: For $a \ge 2$, the pointer $h_n$ at step $n$ always equals the $n$-th survivor $s_n$. This "prefix stabilization" prevents the degenerate first-step behavior seen in the $a=1$ case.
• Rank Identity: The normalized survivors ($\sigma_n$) and deletions ($\delta_n$) satisfy the affine relation:
  $$\delta_n = a\sigma_n + n + (b-1)$$
  This generalizes the Wythoff relation $B_n = A_n + n$.
• Two-Gap Property: The normalized survivor gaps are strictly $\{1, 2\}$. The deletion gaps are $\{a+1, 2a+1\}$.
• Hiccup Rule for Survivors: The survivor sequence is a $(0, s_1, 2a, a)$-hiccup sequence. The gap is $2a$if$n$is a survivor, and$a$ otherwise.
• Connection to Fraenkel Games: The partition satisfies a Fraenkel-type complementary equation. For $b=1$, the survivor/deletion pairs correspond exactly to the P-positions (winning positions) of the combinatorial game NIM($a, 1$).
• Asymptotic Slope: The limit $\alpha(a) = \lim_{n \to \infty} \sigma_n/n$ exists and is the unique positive root of the quadratic equation:
  $$a\alpha^2 - a\alpha - 1 = 0 \implies \alpha(a) = \frac{a + \sqrt{a^2 + 4a}}{2a}$$
  For $a \ge 2$, the sequences are not Beatty sequences (unlike the $a=1$ case).
• Kimberling Rank Transform: The sieve is identified as Kimberling's rank transform applied to a specific block sequence $u_{a,b}$.

C. The Square Sieve ($W_0 = \{n^2\}$)

• When applied to perfect squares, the sieve exhibits a quadratic nesting.
• The gap rule depends on whether the index $n$ belongs to the set of squares of the survivors ($M = \{\mu_m^2\}$).
• The growth of the survivor root-indices $\mu_n$ is given by an alternating root tower expansion:
  $$\mu_n = n + n^{1/2} - n^{1/4} + n^{1/8} - \dots + O(\log \log n)$$

D. The Extraction Sieve

• Defined as a process where the minimum is extracted, and a fixed number of subsequent minima are deleted based on a membership test.
• Affine Transformation: Unlike the Golden Sieve, the Extraction Sieve on $aN+b$ produces a hiccup sequence with parameters transformed linearly:
  $$C_{j,y,z}(aN+b) = \text{hiccup}(j, a+b, ay, az)$$
• Beatty Representations: For cases where $|y-z|=1$, the author derives explicit Beatty formulas ($s_n = \lfloor \alpha n + \beta \rfloor$) for the Extraction Sieve, covering known sequences like the Bosma–Dekking–Steiner sequence (A086377).

4. Significance and Implications

• Unification of Concepts: The paper unifies disparate areas of combinatorial number theory: self-referential sequences, Beatty partitions, Wythoff's game, and Kimberling's rank transforms. It shows that the Golden Sieve is a dynamical origin for these structures.
• Generalization of Wythoff's Game: It provides a constructive, algorithmic derivation of the P-positions for the generalized NIM($a, 1$) game, extending the classical Wythoff result ($a=1$) to all $a \ge 1$.
• New Combinatorial Objects: The paper introduces the "Silver Sieve" (Extraction Sieve $C_{1,3,2}$) and identifies it as the generator of the Bosma–Dekking–Steiner sequence, offering a new dynamical perspective on this sequence.
• Open Problems: The author identifies the combinatorial nature of the gap word $H$ for $a \ge 2$ as a major open question, hypothesizing it may be Ostrowski-automatic or related to the continued fraction of $\alpha(a)$, suggesting the use of the Walnut theorem prover for future verification.

5. Conclusion

Benoit Cloitre's "The Golden Sieve" establishes a rigorous framework for understanding self-referential deletion processes. It demonstrates that while the Golden Sieve on $\mathbb{N}$ yields the classic Wythoff partition, its extension to arithmetic progressions generates a rich family of complementary sequences governed by quadratic slopes and affine rank identities. The introduction of the Extraction Sieve further clarifies the relationship between positional deletion and parameterized hiccup recurrences, providing explicit Beatty formulas for a broad class of sequences.