New properties of the $\varphi$-representation of integers

This paper establishes new properties of the $\varphi$-representation of integers, including a proof of Kimberling's 2012 conjecture, utilizing the Walnut theorem-prover and ChatGPT 5 as computational aids.

The Gist

Imagine you have a magical ruler, but instead of inches or centimeters, it's marked with powers of a special number called the Golden Ratio (let's call it $\phi$). This number, roughly 1.618, appears everywhere in nature, from the spirals of seashells to the arrangement of sunflower seeds.

Usually, when we write numbers, we use a base-10 system (powers of 10: 1, 10, 100...). In this paper, the authors explore a different way of writing numbers using powers of $\phi$. It's like trying to build a house using only specific, oddly shaped bricks.

Here is the breakdown of their discoveries, translated into everyday language:

1. The Golden Blueprint

Just as you can build any house using a combination of standard bricks, the authors explain that every whole number can be built using a unique combination of powers of $\phi$.

• The Rule: You can use $\phi^3$, $\phi^2$, $\phi^{-1}$ (which is like a fraction), etc.
• The Catch: You can't use two powers right next to each other (like $\phi^3$ and $\phi^2$). It's like a "no adjacent bricks" rule to keep the structure stable.
• The Result: Every number gets a unique "Golden Blueprint" (a string of 0s and 1s) showing exactly which powers of $\phi$ are needed to build it.

2. The "Mirror" Mystery (Kimberling's Conjecture)

The authors solved a puzzle proposed by a mathematician named Clark Kimberling in 2012.

The Puzzle:
Imagine you have a number's Golden Blueprint. Some numbers look like a perfect mirror image, but with a twist. If the blueprint has a power at position $+3$, it must also have a power at position $-3$. If it has $+5$, it must have $-5$. This is called being "antipalindromic."

Kimberling guessed: "If a number's blueprint is this perfect mirror image, then if you double all the numbers in the blueprint (turning $+3$ into $+6$ and $-3$ into $-6$), the result will still be a whole number."

The Solution:
The authors proved Kimberling was right!

• The Analogy: Think of the blueprint as a balanced scale. If the weights on the left side perfectly match the weights on the right side (the mirror rule), the scale is balanced. When you "double" the distances of the weights, the balance holds, and the total weight remains a whole number.
• They used a computer program called Walnut (a "theorem-prover") to check millions of cases and confirm this rule holds true for all integers.

3. The "Odd vs. Even" Brick Problem

The researchers also looked at the "parity" (odd or even nature) of the positions in these blueprints.

• The Discovery: You can build numbers using only even positions (like $\phi^2, \phi^{-4}, \phi^6$). These are the "Mirror" numbers mentioned above.
• The Twist: You cannot build a number using only odd positions (like $\phi^1, \phi^{-3}$). It's physically impossible to build a whole house using only odd-numbered bricks; the structure collapses.
• The Exception: However, you can build numbers that have exactly one odd brick and the rest even. Or exactly two odd bricks.

4. The Digital Detectives (Automata)

How did they prove all this? They didn't just do math on paper; they built digital detectives (called Finite Automata).

• The Metaphor: Imagine a robot that reads a number's blueprint like a barcode. The robot has a set of rules (states). As it scans the blueprint from left to right, it jumps between different "rooms" in its brain.
• If the robot ends up in the "Green Room," the number has a special property (like having exactly one odd exponent). If it ends in the "Red Room," it doesn't.
• The authors wrote code to build these robots, which then scanned thousands of numbers to verify their theories. They even used ChatGPT (an AI) to help write a part of the proof, showing how modern AI is becoming a partner in mathematical discovery.

Summary

This paper is about finding the hidden patterns in how we can build numbers using the Golden Ratio.

1. Pattern Found: Numbers with a "mirror" blueprint have a special property where doubling their blueprint parts keeps them as whole numbers.
2. Rule Discovered: You can't build a whole number using only odd-positioned powers of the Golden Ratio.
3. Method: They used clever computer programs (automata) to act as proof-checkers, verifying these patterns across the infinite landscape of numbers.

It's a beautiful mix of ancient mathematical curiosity (the Golden Ratio) and modern computational power, revealing that even in the chaotic world of numbers, there are strict, elegant rules governing how they fit together.

Technical Summary

Here is a detailed technical summary of the paper "New properties of the $\phi$-representation of integers" by Jeffrey Shallit and Ingrid Vukusic.

1. Problem Statement

The paper investigates the properties of the $\phi$-representation (also known as the golden ratio base or base-$\phi$) of integers. In this system, every positive integer $x$ can be uniquely represented as a finite sum of distinct powers of the golden ratio $\phi = (1+\sqrt{5})/2$:
$$x = \sum_{i=a}^{b} e_i \phi^i$$
where $e_i \in \{0, 1\}$ and the "no consecutive 1s" condition ($e_i e_{i-1} = 0$) is imposed to ensure uniqueness.

The authors focus on two specific structural questions regarding these representations:

1. Kimberling's Conjecture (2012): Does the set of integers whose $\phi$-representation is "antipalindromic" (exponent $t$ appears if and only if $-t$ appears) correspond exactly to the set of integers where doubling every exponent in the representation results in another integer?
2. Parity of Exponents: What are the constraints on the parity (evenness or oddness) of the exponents in the $\phi$-representations of natural numbers? Specifically, the authors explore sets of integers where the representation contains only even exponents, only odd exponents, or a specific count of odd/even exponents.

2. Methodology

The authors employ a hybrid methodology combining classical number theory with automata theory and formal verification:

• Theoretical Proofs: They utilize properties of the golden ratio conjugate $\bar{\phi} = (1-\sqrt{5})/2$, Fibonacci numbers ($F_n$), and Lucas numbers ($L_n$). They apply Galois conjugation (mapping $\phi \to \bar{\phi}$) to derive bounds and contradictions regarding the integer nature of specific sums.
• Automata Theory & Walnut: A significant portion of the work relies on Walnut, a theorem-prover for first-order logic statements about automatic sequences.
  • The authors utilize a pre-existing 39-state finite automaton named saka (developed in a previous work by Shallit). This automaton accepts triples $(n, x, y)$ where $n$ is an integer, and $x.y^R$ (where $y^R$ is the reversal of $y$) is the $\phi$-representation of $n$.
  • They construct regular expressions and logical predicates within Walnut to define sets of integers based on the structure of their Zeckendorf (Fibonacci) representations, which map directly to the $\phi$-representation.
  • The tool verifies complex logical implications (e.g., "For all $n$, if $n$ has property $P$, then $n$ has property $Q$") by constructing and minimizing finite automata.
• AI Assistance: The authors explicitly note using ChatGPT 5 to assist in generating a standard, non-automata proof for one of the theorem claims (Theorem 8, part a).

3. Key Contributions and Results

A. Proof of Kimberling's Conjecture

The authors prove that the set $S$ (OEIS A178482) of integers with antipalindromic $\phi$-representations is exactly the set of integers $n$ such that replacing every exponent $t$ in $n$'s $\phi$-representation with $2t$ yields an integer.

• Key Lemma: An integer's $\phi$-expansion is antipalindromic if and only if all exponents in the expansion are even.
• Mechanism: If exponents are even, $\phi^{2k} + \phi^{-2k} = L_{2k}$ (a Lucas number, which is an integer). If odd exponents exist, the sum involves $\sqrt{5}$, preventing the result from being an integer.

B. Parity Constraints on Exponents

The paper establishes strict rules regarding the parity of exponents in canonical $\phi$-representations:

• All Even Exponents: There are infinitely many integers with all even exponents (the set $S$).
• All Odd Exponents: No integer $n \ge 2$ has a $\phi$-representation consisting entirely of odd exponents. The smallest exponent must always be even.
• Exactly One Even Exponent: The authors characterize the set of integers with exactly one even exponent.
  • They provide a Deterministic Finite Automaton (DFA) (Figure 3) accepting the Zeckendorf representations of these numbers.
  • Theorem 9: An integer $n$ has exactly one even exponent in its $\phi$-expansion if and only if $n-1$ is a sum of distinct odd-indexed Lucas numbers ($L_{2i+1}$).
• Exactly One Odd Exponent: The authors characterize integers with exactly one odd exponent.
  • Theorem 10: Such an integer $n$ exists if and only if $n-2$ is a sum of distinct even-indexed Lucas numbers ($L_{2i}$ for $i \ge 2$). Furthermore, for these numbers, the single odd exponent is always 1.
• Exactly Two Odd Exponents:
  • Theorem 11: If an integer has exactly two odd exponents, they must be either $\{3, 1\}$ or $\{2i+1, 1-2i\}$ for some $i \ge 1$. The paper proves that both cases occur infinitely often.

C. Structural Properties of Negative Parts

The paper refines the understanding of the "negative part" of the $\phi$-representation (the part after the decimal point).

• Theorem 8: For any integer $n \ge 2$, the negative part of its canonical $\phi$-representation (viewed as a binary string in Zeckendorf form) must have an even length and cannot contain two consecutive 1s.

4. Significance

• Resolution of Open Problems: The paper definitively resolves a conjecture made by Clark Kimberling in 2012 regarding the relationship between antipalindromic $\phi$-representations and the integrality of doubled exponents.
• Bridging Fields: It demonstrates the power of combining classical analytic number theory with automated theorem proving. The use of Walnut allows for the verification of properties that would be extremely tedious or difficult to prove via manual induction alone, particularly those involving the complex interaction of Fibonacci and Lucas numbers.
• Characterization of Integer Sets: The work provides precise characterizations (via automata and Lucas number sums) for subsets of integers defined by the parity structure of their base-$\phi$ expansions. This deepens the understanding of $\beta$-numeration systems and the arithmetic properties of the ring $\mathbb{Z}[\phi]$.
• Methodological Innovation: The paper serves as a case study for using AI (ChatGPT) as a collaborative tool in mathematical research, specifically for generating alternative proof strategies.

In summary, the paper advances the theory of $\phi$-representations by proving a long-standing conjecture and providing a comprehensive classification of integers based on the parity of the exponents in their golden ratio expansions, utilizing a novel blend of automata theory and traditional number theory.