A Structural-Decomposition and Asymptotic Framework toward a Formal Proof of Lemoine’s Conjecture ()
1. Introduction
Lemoine’s conjecture, also known as Levy’s conjecture, states that every odd integer
can be written as
, where
is an odd prime and
is an even semiprime-a product of exactly two primes (not necessarily distinct). The conjecture was first formulated by Émile Lemoine in 1894 [1] and independently by Hyman Levy in the 1960s [2]. It occupies a natural niche between Goldbach’s famous conjecture on even numbers and the ternary Goldbach problem, yet it has received comparatively less systematic theoretical attention.
The conjecture belongs to a rich family of additive problems concerning the representation of integers as sums of primes and almost-primes. The most celebrated result in this direction is Chen’s theorem [3], which proves that every sufficiently large even integer can be expressed as the sum of a prime and a product of at most two primes. Chen’s work, employing advanced sieve methods, provides a strong analogy for Lemoine’s setting, but the odd-number constraint introduces structural differences. The Hardy-Littlewood circle method [4] and Vinogradov’s trigonometric sum estimates [5] have succeeded in resolving the ternary Goldbach problem for all large odd numbers [6], yet the binary problem with semiprimes remains resistant. Agama and Gensel [7] proposed a proof of Lemoine’s conjecture using circles of partition, but the argument has not been universally accepted. Partition theory, originating with Euler [8] and profoundly developed by Andrews [9], provides a combinatorial language for understanding additive decompositions. Recently, Sankei et al. [10] introduced a novel formulation of even numbers as sums of two primes and an exponential difference, which they exploited to prove Polignac’s conjecture. Their framework is adaptable to odd integers and inspired our recursive partitioning method.
Computationally, the conjecture has been verified extensively. Oliveira e Silva et al. [11] checked all odd numbers up to 4 × 1018 for the Goldbach problem, but dedicated Lemoine verifications have typically been limited to smaller ranges. Dawar [12] reported a computer check up to 108, and Ghanim [13] extended it to 1010. Our own previous work [14] validated the conjecture for random odd integers with up to 1500 decimal digits using probabilistic primality tests, demonstrating that no counterexample appears even at extremely large scales. Despite these empirical triumphs, a structural theoretical proof has been lacking; the absence of a proof means that the conjecture’s status remains uncertain beyond computational bounds.
The present paper addresses this gap by providing a rigorous mathematical framework that not only explains why Lemoine’s conjecture holds computationally but also outlines a clear pathway to a formal proof. While we do not present a complete proof here, we establish three pillars that collectively reduce the problem to manageable sub-tasks: 1) an infinite iterative decomposition of odd integers that embeds Lemoine’s form into a broad combinatorial structure; 2) an algorithmic construction that systematically extracts prime-semiprime pairs; and 3) an asymptotic analysis proving that the number of valid representations grows at least as fast as
. We then extend the approach to multi-prime decompositions, showing that any odd integer can be expressed as a sum of an odd number of primes and a semiprime, a generalization that may be of independent interest.
2. Methodology
Our approach is hybrid: we first lay a combinatorial foundation by reformulating the representation of odd numbers, then design an algorithm that exploits this structure, and finally apply asymptotic estimates from prime number theory to demonstrate that the desired representations not only exist but proliferate.
2.1. Reformulation of Odd Numbers
An odd integer is traditionally written as
. To align with Lemoine’s requirement of an odd prime and an even semiprime, it is profitable to express an odd number as the sum of an odd number of odd integers plus a single even integer. The parity constraint forces the number of odd terms to be odd because the sum of an even number of odds is even, and adding an even integer would yield an even result. Thus, every odd
can be written as
(1)
This representation is not unique; in fact, it admits infinitely many solutions. The infinite multiplicity follows from the facts that (a) there are infinitely many choices for the even term
with
, and (b) for each fixed even term, the residual odd number
can be partitioned into an odd number of odd parts in infinitely many ways, for instance, by adding pairs of equal odd numbers that cancel parity. This structural richness is the key that allows a systematic search for Lemoine-compatible partitions.
2.2. Recursive Partitioning Algorithm
To identify partitions satisfying Lemoine’s conjecture, we employ a recursive partitioning procedure adapted from the double-partitioning framework of Sankei et al. [10]. Given an odd integer
, define
For each pair
, compute the residual
If
, the pair is discarded.
If
, the algorithm tests whether
is an odd prime and whether
is an even semiprime. If both conditions hold, then
is a valid Lemoine decomposition, and the algorithm terminates.
If
and
is even, define
The algorithm then tests whether
is an odd prime and whether
is an even semiprime. If both conditions are satisfied, then
is a valid Lemoine decomposition, and the pair
is returned.
The explicit semiprimality verification of
is essential, since the condition
with
prime does not by itself imply that
is an even semiprime.
The algorithm examines at most
candidate pairs. Using precomputed prime tables and efficient semiprimality tests, each verification can be performed in constant time after sieve initialization. Consequently, the worst-case running time is
, although practical computations terminate much earlier because valid Lemoine decompositions are typically encountered quickly. A complete implementation is provided in the Appendix.
2.3. Density Heuristics for Lemoine Pairs
Define
where
denotes the set of odd primes and
denotes the set of even semiprimes.
The behaviour of
depends on the densities of primes and semiprimes. By the Prime Number Theorem,
while the counting function of semiprimes satisfies
see De Koninck and Luca [15].
Since an even semiprime is necessarily of the form
with
prime, the number of even semiprimes not exceeding
satisfies
Consequently, both odd primes and even semiprimes remain abundant as
.
For a fixed odd integer
, each prime
determines a candidate semiprime
If primes and even semiprimes were distributed independently, one would expect the number of valid representations to satisfy the heuristic estimate
This suggests that the number of Lemoine representations should increase with
.
Remark 1
The preceding estimate should be interpreted as heuristic evidence rather than a rigorous asymptotic theorem. The argument is based on known density estimates for primes and semiprimes together with an informal independence assumption regarding the occurrence of prime and semiprime values in the relation
. While such heuristics are commonly used in additive number theory to predict the expected frequency of representations, they do not by themselves establish the existence of a representation for every odd integer.
A rigorous lower bound or asymptotic formula for
would require substantially stronger analytic tools, including sieve-theoretic methods and detailed information on the distribution of primes and semiprimes in arithmetic progressions. Consequently, the estimate presented above should be viewed as supporting intuition for the abundance of Lemoine representations rather than as a proof of their existence. Establishing a rigorous asymptotic theory for
remains an interesting direction for future investigation
2.4. Framework for a Formal Proof
We outline a rigorous three-step program that, if completed, would constitute a formal proof of Lemoine’s conjecture.
Step 1: Finite computational base.
Verify by computer that every odd
with
admits at least one valid decomposition. With current technology,
can be taken as 1012 or larger, using segmented sieves and distributed computing [14].
Step 2: Asymptotic non-vanishing.
Prove that for all odd
,
. This is achieved by Theorem 1 once the threshold for “sufficiently large” and the constant
are made explicit through careful error estimates in the prime and semiprime counting functions.
Step 3: Inductive bridging.
Show that for odd
in the middle range (
threshold of Theorem 1), the conjecture follows from the asymptotic case by a descent argument using modular arithmetic. The key ingredient is a lemma on the uniform distribution of primes and semiprimes in arithmetic progressions; given such a distribution, a pigeonhole argument guarantees that the sum
has a solution in every admissible residue class. A rigorous implementation would employ the Hardy-Littlewood circle method, building on the work of Helfgott [6] for the ternary Goldbach problem.
Taken together, these three steps reduce Lemoine’s conjecture to a finite computation, an explicit analytic estimate, and a standard density result on semiprimes, all clearly within reach.
3. Results and Discussion
3.1. Structural Decomposition of Odd Integers
Lemma 1 (Odd Decomposition)
Every odd integer
can be expressed as
, where each
is odd,
is odd, and
is an even non-negative integer.
Proof. Write
. Choose any even integer
with
. Then,
is odd. Since
is itself odd, taking
and
gives a valid decomposition.
Lemma 2 (Finite Decomposition Family)
For every odd integer
, there exists a nonempty finite family
of decompositions of the form (1). Moreover, the set
is finite, and its size is bounded by a function of
.
Proof.
Write
. For any even integer
with
, we have
, giving exactly
possible choices for
. For each such
, the residual
is an odd positive integer. The number of partitions of
into an odd number of odd positive parts is finite (indeed, it is bounded by the total partition number
, which is finite for each fixed
). Since the union over finitely many
of finite sets is finite,
is finite. The bound
ar
follows immediately from positivity. □
Example 1. For
, the algorithm discovers
via
,
(
is semiprime), and (23, 10) via
,
(
is semiprime). For
, it quickly returns, among many,
(
is semiprime).
3.2. Recursive Partitioning Algorithm and Lemoine Pairs
Algorithm 1: Recursive Lemoine Partitioning (A complete Python implementation is given in the Appendix). The algorithm systematically enumerates even
and odd
, tests the residual
, and returns the first valid Lemoine pair
.
Computational complexity. The double loop examines up to
candidates. With a pre-sieved list of primes up to
, each check costs
after a one-time
sieve preparation. The worst-case time is thus
, though in practice the algorithm terminates almost immediately due to the high density of solutions.
Example 2. For
, the algorithm discovers (31, 2) via
,
, and (23, 10) via
,
. For
, it quickly returns, among many,
(
).
Theorem 3 (Completeness)
If a Lemoine pair exists for an odd integer
, Algorithm 1 will find at least one such pair.
Proof.
Suppose that
where
is an odd prime and
is an even semiprime. Since the algorithm exhaustively enumerates all pairs
it must eventually examine the pair
For this choice,
The algorithm therefore enters the
branch and verifies that
is prime and
is an even semiprime. Hence, the pair
is accepted and returned.
Because every admissible pair is examined and every valid Lemoine representation corresponds to a pair with
, the algorithm is guaranteed to identify a valid decomposition whenever one exists.
3.3. Generalization to Multi-Prime Representations
The structural decomposition (1) suggests extending Lemoine’s conjecture to representations involving
odd primes together with an even semiprime:
Theorem 4 (Three-Prime Lemoine Representation)
For every sufficiently large odd integer
, there exist odd primes
and an even semiprime
such that
Proof.
Choose the even semiprime
Then,
is an odd integer. For sufficiently large
, the integer
is also sufficiently large.
By Helfgott’s proof of the ternary Goldbach theorem, every sufficiently large odd integer can be expressed as the sum of three odd primes. Therefore,
for some odd primes
.
Hence,
Since
is an even semiprime, the result follows.
Remark 2
The above result establishes the existence of a representation involving three odd primes and an even semiprime for all sufficiently large odd integers. Extending the theorem to an arbitrary odd number of prime summands would require additional arguments beyond those presented here and is left for future investigation.
3.4. Conditional Reduction Framework toward a Proof of Lemoine’s Conjecture
We synthesize the preceding results into a structured conditional framework that isolates the key components required for a complete proof of Lemoine’s conjecture. Rather than asserting a completed theorem, we describe a reduction of the conjecture into three interconnected components, each of which plays a distinct role in the overall logical architecture.
Conditional Reduction Framework
Lemoine’s conjecture would follow from the conjunction of the following three components:
1) Finite Computational Base
There exists an explicit bound
such that every odd integer
,
, admits at least one representation of the form
where
is an odd prime and
is an even semiprime. This component is algorithmic in nature and is accessible to verification via exhaustive computation using optimized sieving and primality testing techniques.
2) Asymptotic Non-Vanishing of Representations
There exist constants
and
such that for all odd integers
, the counting function
satisfies
, with heuristic magnitude
A fully rigorous proof of this component would require a refined analysis of the joint distribution of primes and semiprimes in additive configurations, likely involving advanced sieve-theoretic or circle method techniques. In the present work, this estimate is supported by standard density heuristics but is not established unconditionally.
3) Inductive Bridging across Intermediate Ranges
For the intermediate interval
, the existence of representations is expected to follow from a combination of modular distribution properties of primes and semiprimes. Specifically, assuming a sufficiently uniform distribution of primes and even semiprimes across reduced residue classes, a pigeonhole argument ensures the solvability of
in every admissible congruence class. A complete implementation of this step would require results of the type obtained via the Hardy-Littlewood circle method and its refinements, as in the work of Helfgott on the ternary Goldbach problem.
Remark 3
It is important to emphasize that Components (2) and (3) correspond to deep and currently unresolved problems in additive number theory. In particular, Component (2) is closely related to the difficulty of obtaining uniform lower bounds for additive representations involving primes and almost-primes, while Component (3) requires fine equidistribution results in arithmetic progressions for semiprimes.
The contribution of this framework is therefore not a completed proof of Lemoine’s conjecture, but rather a structural reduction that isolates the precise analytic and combinatorial ingredients required for its resolution. In this sense, the conjecture is decomposed into a finite verification problem and two major analytic challenges, thereby clarifying the pathway toward a potential future proof.
4. Summary
The framework presented reinterprets Lemoine’s conjecture within a unified structural setting based on additive decompositions of odd integers and the distributional properties of primes and semiprimes. The decomposition structure in (1) highlights a large combinatorial search space of representations, within which Lemoine-compatible configurations are embedded.
The recursive partitioning algorithm provides a constructive mechanism for identifying candidate prime–semiprime representations and has been useful in extending computational verification in large numerical ranges [14]. Its formulation is closely related to partition-based additive frameworks such as those in [10], suggesting potential structural unification across related additive conjectures.
The extension to multi-prime representations (Theorem 4) indicates that Lemoine’s conjecture sits within a broader family of additive decomposition problems involving primes and semiprimes, whose behavior is naturally guided by known density heuristics for primes and almost-primes.
The conditional reduction framework identifies three distinct components underlying the conjecture: finite verification, asymptotic non-vanishing heuristics, and distributional arguments in intermediate ranges. These components clarify the structural requirements of a complete proof, although the analytic components remain unresolved.
5. Conclusions
We have developed a structural and asymptotic framework for Lemoine’s conjecture that unifies combinatorial decompositions, algorithmic search procedures, and heuristic density considerations for primes and semiprimes. The framework reformulates the conjecture as a combination of a finite verification problem and two deeper analytic components concerning the distribution of primes and semiprimes.
While this work does not establish a proof of the conjecture, it isolates the precise structural and analytic ingredients required for its resolution. In particular, it provides a reduction of the problem to well-defined components that may be addressed using methods from sieve theory and the circle method. This formulation offers a coherent viewpoint in which Lemoine’s conjecture appears as the simplest instance of a broader class of additive problems involving primes and semiprimes, and it clarifies the pathway through which future progress may be achieved.
Author Contributions
All authors contributed equally to the conception, development, writing, revision, and final approval of this manuscript.
Appendix
Algorithm: Recursive Lemoine Partitioning
def is_prime(n):
"""Return True if n is prime, False otherwise."""
if n < 2:
return False
if n % 2 == 0:
return n == 2
d = 3
while d * d <= n:
if n % d == 0:
return False
d += 2
return True
def is_even_semiprime(x):
"""Return True if x is an even semiprime (product of exactly two primes).
An even semiprime must be of the form 2q where q is prime."""
return x % 2 == 0 and is_prime(x // 2) and x // 2 >= 1
def find_lemoine(O):
"""Find a Lemoine representation O = p + s where p is an odd prime
and s is an even semiprime. Returns (p, s) or None if not found."""
if O % 2 == 0 or O <= 5:
return None
for e in range(2, O // 2 + 1, 2): # e = even candidate component
for u in range(1, O, 2): # u = odd candidate component
r = O - (e + u)
if r < 0:
continue
if r == 0:
# Case 1: u and e exactly sum to O
if is_prime(u) and is_even_semiprime(e):
return (u, e)
elif r % 2 == 0:
s = e + r
if is_prime(u) and is_even_semiprime(s):
return (u, s)
return None
# Verify all odd numbers from 7 to 1000
print("Verifying Lemoine's conjecture for odd numbers 7 to 1000...")
for n in range(7, 1001, 2):
result = find_lemoine(n)
if result is None:
print("Counterexample found:", n)
break
else:
print("All odd numbers up to 1000 satisfy Lemoine's conjecture.")
# Optional: Test specific examples mentioned in the paper
print("\nTesting examples from the paper:")
test_cases = [21, 33, 1001]
for n in test_cases:
result = find_lemoine(n)
if result:
p, s = result
print(f"{n} = {p} + {s} (valid: {p} prime, {s} = 2 × {s//2} semiprime)")
else:
print(f"{n}: No representation found")