🔢 mathematics

On integers of the form $p+F_{2^k}+F_q$

This paper proves that the set of integers representable as the sum of a prime, a Fibonacci number with an index that is a power of two, and another prime has positive lower asymptotic density, a property that also holds for the set of integers that cannot be represented in this form.

Original authors: Yang Gao

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yang Gao

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have an infinite bag of building blocks. Some blocks are Primes (numbers like 2, 3, 5, 7 that can't be divided evenly by anything else), some are Fibonacci numbers (a special sequence where you add the last two numbers to get the next one: 0, 1, 1, 2, 3, 5, 8, 13...), and some are just regular Integers (1, 2, 3, 4...).

For a long time, mathematicians have been playing a game: "Can you build every single integer using a specific recipe?"

The Old Recipe

Back in 1934, a mathematician named Romanoff asked: "Can you build every odd number by adding one Prime and one Power of Two (like 1, 2, 4, 8, 16...)"?
He found that you can build a lot of them, but not all. Later, another mathematician named Erdős showed that there are actually infinite "gaps"—whole lines of numbers that simply cannot be built this way.

The New Recipe

In this paper, the author, Yang Gao, changes the recipe. Instead of powers of two, he uses Fibonacci numbers. But he adds a twist:

He uses one Prime ( $p$ ).
He uses one Fibonacci number where the position is an even number ( $F_{2k}$ , like $F_0, F_2, F_4...$ ).
He uses another Prime ( $q$ ) as the index for a third Fibonacci number ( $F_q$ ).

So the recipe is: $n = \text{Prime} + \text{Even-Position Fibonacci} + \text{Prime-Position Fibonacci}$ .

The big question is: If you try to build numbers using this new recipe, do you cover enough of the number line? Or are there huge gaps?

The Two Main Discoveries

The paper proves two surprising things about this new recipe:

1. The "Unbuildable" Highway (Theorem 1.1)

Imagine a long, straight highway where every single mile marker represents a number. The author proves that you can find a specific section of this highway (an infinite arithmetic progression) where none of the numbers can be built using the recipe.

The Analogy: Think of a lock and key. The author designed a specific "lock" (a set of rules based on remainders when divided by small numbers like 2, 3, 5, 7, etc.). He showed that no matter how you try to mix your Primes and Fibonacci numbers, the result will never fit into this specific lock.

Result: There is an infinite line of numbers that cannot be written as $p + F_{2k} + F_q$ . Because this line is infinite and regular, it means the "unbuildable" numbers make up a significant chunk of the number world.

2. The "Buildable" Crowd (Theorem 1.2)

Here is the twist: Even though there is a whole highway of "unbuildable" numbers, the numbers that can be built are also everywhere.

The Analogy: Imagine a crowded party. Even though there is a specific group of people who cannot enter the VIP room (the unbuildable numbers), the VIP room is still packed with a "positive density" of guests. In math terms, this means if you look at the first 1,000,000 numbers, a significant percentage of them (not just a tiny handful) can be built using the recipe.

Result: The set of numbers you can build is large enough to be considered "positive density." It's not just a few scattered islands; it's a substantial continent.

How Did They Do It? (The Tools)

To prove these things, the author used two main tools:

The Sieve (for the "Unbuildable" proof):
Think of a sieve used to separate sand from rocks. The author set up a series of filters (congruences) based on small prime numbers. He showed that if you try to build a number using his recipe, it will always get caught in one of these filters. It's like trying to walk through a maze where every path leads to a dead end for a specific group of numbers.
The Counting Game (for the "Buildable" proof):
To prove that many numbers can be built, the author had to count how many ways you can make a number.
- First, he showed that there are so many combinations of Primes and Fibonacci numbers that you could theoretically make roughly as many numbers as there are integers up to $x$ .
- Then, he had to prove that you aren't just making the same number over and over again (like making 100 using 50 different combinations). He proved that most numbers are made in unique or few ways.
- The "Cauchy-Schwarz" Trick: He used a mathematical inequality (a fancy way of saying "if you have a lot of total combinations, and you aren't repeating them too much, then you must have a lot of different numbers"). This proved that the "buildable" numbers are dense.

Summary

In simple terms, this paper solves a puzzle about how numbers are constructed. It shows that if you mix Primes and Fibonacci numbers in this specific way:

You will never be able to build a specific, infinite line of numbers (they are "unreachable").
However, you will be able to build a huge, significant portion of the rest of the numbers (they are "reachable").

It's a bit like saying: "You can't build a house out of these specific bricks on this specific street, but on the rest of the city, you can build houses on almost every other lot."

Technical Summary: Integers of the Form $p + F_{2k} + F_q$

Problem Statement
This paper investigates the distribution of positive integers representable in the form $n = p + F_{2k} + F_q$ , where $p$ and $q$ are prime numbers and $k$ is a non-negative integer. Here, $\{F_n\}$ denotes the Fibonacci sequence defined by $F_0=0, F_1=1$ , and $F_{n+2}=F_{n+1}+F_n$ . The study addresses a "Romanoff-type" problem, extending the classical question of whether integers can be written as the sum of a prime and a power of two ( $p + 2^n$ ) to sums involving primes and specific sparse sequences (Fibonacci numbers). Specifically, the paper seeks to determine the lower asymptotic density of the set of integers representable in this form and the density of its complement.

Methodology
The authors employ a combination of elementary number theory, properties of the Fibonacci sequence modulo primes, and analytic number theory techniques, specifically sieve methods.

Preliminary Lemmas: The proof relies on fundamental properties of Fibonacci numbers, including their growth rates (Binet's formula approximations), Zeckendorf representations, and periodicity modulo integers (Pisano periods). Key lemmas establish bounds on the number of Fibonacci numbers up to $x$ and the distribution of residues modulo primes.
Covering Systems (Theorem 1.1): To prove that the set of non-representable integers has positive lower density, the authors construct an explicit infinite arithmetic progression $A$ . This is achieved by defining a system of congruences modulo a product of specific primes ( $M = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 19 \cdot 23 \cdot 47$ ). By analyzing the parity and modular residues of $F_{2k}$ and $F_q$ against these moduli, the authors demonstrate that no integer in this progression can satisfy the equation $n = p + F_{2k} + F_q$ .
Sieve Methods and Uniqueness (Theorem 1.2): To prove that the set of representable integers has positive lower density, the authors utilize the Cauchy–Schwarz inequality. This requires estimating two quantities:
- $R(x) = \sum_{n \le x} r(n)$ , the total number of representations, where $r(n)$ counts the number of triples $(p, k, q)$ such that $n = p + F_{2k} + F_q$ .
- $\sum_{n \le x} r(n)^2$ , the second moment, which counts the number of pairs of representations for the same integer.
- Uniqueness Analysis: A critical step involves Lemma 4.1, which establishes that the equation $F_{2k_1} + F_{q_1} = F_{2k_2} + F_{q_2}$ has very few solutions (essentially only trivial permutations or specific small cases). This ensures that the number of "collisions" (where different triples yield the same sum) is controlled.
- Sieve Estimates: The authors apply the Bombieri–Davenport estimate and the Brun–Titchmarsh inequality to bound the number of solutions where the difference between two sums is a fixed even integer. They carefully handle the sum over the divisors of the difference term using properties of the Pisano periods and the distribution of primes in arithmetic progressions.

Key Contributions and Results
The paper establishes two main theorems regarding the set of integers of the form $p + F_{2k} + F_q$ :

Theorem 1.1: There exists an infinite arithmetic progression of positive integers such that no integer in this progression can be written as $p + F_{2k} + F_q$ . Consequently, the set of integers not representable in this form has positive lower asymptotic density.
Theorem 1.2: The set of positive integers representable as $p + F_{2k} + F_q$ (with $p, q$ prime and $k \ge 0$ ) has positive lower asymptotic density.

Additionally, the authors note in Remark 1 that analogous results hold for Lucas numbers ( $L_n$ ), as the proof relies on similar modular properties.

Significance
The paper contributes to the broader theory of Romanoff-type problems by addressing sums involving two sparse terms from linear recurrence sequences (specifically Fibonacci numbers) and a prime. While previous work had established positive density for sums of a prime and a single Fibonacci number ( $p + F_k$ ) or sums of a prime and two powers of two ( $p + 2^a + 2^b$ ), this work extends the understanding to mixed forms involving indices that are themselves primes ( $q$ ) and even indices ( $2k$ ). The result confirms that despite the sparsity of the Fibonacci sequence and the restriction on indices, the additive combination with primes is sufficiently dense to cover a positive proportion of the integers, while simultaneously leaving a positive proportion uncovered, as demonstrated by the constructed arithmetic progression. The methodology demonstrates the effectiveness of combining covering systems with sieve estimates in the context of linear recurrences.