Exploiting Problem Structure in Combinatorial Landscapes: A Case Study on Pure Mathematics Application

Xiao-Feng Xie, Zun-Jing WangIJCAI 2016

Introduction

In the field of number theory, the search for "narrow admissible tuples" has become a cornerstone for proving significant results regarding the distribution of prime numbers. An admissible $k$-tuple is a set of $k$ integers that does not occupy all possible remainders (residue classes) for any prime $p$. The goal is to find such tuples with the minimum possible diameter—the difference between the largest and smallest elements. These narrow tuples were instrumental in the breakthroughs by Yitang Zhang and the Polymath project concerning finite gaps between primes.

Historically, mathematicians have relied on "sieves"—constructive algorithms that filter integers based on mathematical rules. However, as $k$ increases, these greedy approaches often become trapped in local optima. This paper presents a shift toward AI-driven combinatorial optimization, introducing the Region-based Adaptive Local Search (RALS) to explore these complex landscapes more effectively.

The RALS Framework

The core of the proposed approach is treating the search for admissible tuples as a combinatorial optimization problem. The RALS algorithm decomposes the search space into regions based on the starting value ($h_1$) of the tuple, allowing for independent exploration of different "neighborhoods" on the number line.

Internal data structures for tracking residue classes and admissibility constraints.

To navigate this space, RALS employs several specialized operators:

  • InsertMove: Uses "violation check clues" to intelligently identify candidates for addition to the set without violating admissibility.
  • Plateau Escaping: Implements "Level 2" moves to traverse neutral regions of the search space where the diameter remains constant but a configuration change is needed to reach a better state.
  • Database Management: A global database tracks high-quality solutions, using tournament selection to prioritize the most promising regions for further refinement.

Insights into the Fitness Landscape

A key contribution of this work is the visualization and analysis of the "Virtual Fitness Landscape." By plotting the quality of solutions against their starting positions, the authors revealed a structure that is both noisy and rugged, yet contains distinct "valleys" of high-quality solutions.

Visualization of the virtual fitness landscape $f(v)$ for various $k$ values, showing the emergence of 'valleys' of high-quality solutions.

As shown in the landscape analysis, the search space is often "neutral," meaning many configurations yield the same diameter. Standard greedy searches fail in these flat regions. The RALS algorithm's ability to traverse these plateaus is what allows it to outperform traditional mathematical constructions.

Results and Impact

The RALS algorithm was benchmarked against the Sutherland Online Database and various state-of-the-art sieves, including the Eratosthenes, Hensley-Richards, and Shifted Greedy sieves. The results were significant:

  • 48 New Records: RALS discovered new upper bounds for $k$ values between 2500 and 5000, reducing diameters by 10 or more in several instances.
  • Superior Efficiency: The method consistently achieved a higher success rate than the best existing sieve methods as search time increased. For $k=1000$, RALS reached a 100% success rate in finding the best-known solutions.

Conclusion

This study demonstrates that general-purpose AI search strategies can successfully tackle deep problems in pure mathematics. By exploiting the underlying structure of combinatorial landscapes, RALS overcomes the "greedy traps" inherent in traditional sieves. Future work will focus on automated parameter tuning and deeper landscape analysis to further refine these search operators for even larger-scale mathematical challenges.

Summary updated

BibTeX
@inproceedings{xie2016exploiting,
  author = {Xiao-Feng Xie and Zun-Jing Wang},
  title = {{Exploiting Problem Structure in Combinatorial Landscapes: A Case Study on Pure Mathematics Application}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure