Squarefree Gaps in Arithmetic Progressions

ISEF Category: Mathematics

Subcategory: Number Theory  ·  Difficulty: Advanced  ·  Setup: University Lab  ·  Time: Full Year

The Hook

Some number patterns hide for a long time, then one better proof changes what you can say about them. Squarefree numbers are the integers not divisible by any perfect square bigger than one. If you place them on a number line and sort them by residue class, the gaps start to look less random. Your job is to measure, compare, and explain those gaps.

What Is It?

Squarefree numbers are numbers like 6, 10, 15, and 21. They are not divisible by 4, 9, 16, or any other perfect square larger than one. Think of them like numbers that escaped every square-shaped trap. A gap between consecutive squarefree numbers is the stretch of integers in between two such numbers. In an arithmetic progression, you only look at numbers of the form an + b, so you are studying squarefree numbers inside one repeating pattern, not across the whole number line.

The Selberg sieve is a counting method from analytic number theory. You can think of it like a filter that estimates how many numbers survive after you remove the ones hit by square divisibility rules. It does not list the survivors one by one. Instead, it gives upper or lower bounds for how many are left. For this topic, the key idea is to compare what the sieve predicts with actual computed tables, then ask where the sieve bound is sharp, where it is loose, and how the gap behavior changes with the modulus.

Why This Is a Good Topic

This topic works well for a science fair because you can turn a deep number theory claim into concrete tests. You can compute squarefree gaps for chosen arithmetic progressions, compare residue classes, and check where a theoretical lower bound matches the data. The project connects to prime-like spacing, sieves, and pattern detection in integers, which gives it real mathematical weight. You can also learn how proof and computation support each other in modern research.

Research Questions

• How does the smallest observed gap between consecutive squarefree numbers change across residue classes modulo a fixed small modulus?
• What is the effect of increasing the modulus on the distribution of squarefree gaps in arithmetic progressions?
• Does the Selberg sieve lower bound stay close to the computed gap data for moduli below a chosen threshold?
• To what extent do different residue classes with the same modulus show the same gap pattern?
• Which moduli produce the largest deviation between theoretical lower bounds and computed gaps?
• What is the effect of restricting the search to squarefree numbers below 10^11 on the stability of the gap estimate?

Basic Materials

• Laptop or desktop computer with enough memory for large integer lists.
• PARI/GP installed for fast number theory computation.
• Spreadsheet software for organizing gap counts and residue classes.
• Text editor for keeping a proof log and code notes.
• Access to a math reference on sieves and squarefree numbers.
• Calculator for quick sanity checks on small cases.

Advanced Materials

• University computer or workstation for larger enumerations.
• PARI/GP with custom scripts for squarefree sieving and table checks.
• SageMath for cross-checking number theory computations.
• Python with NumPy and pandas for data cleaning and summary tables.
• LaTeX for writing a formal proof summary.
• Access to a journal database for reading paper abstracts and related results.

Software & Tools

• PARI/GP: Computes squarefree counts, residue class tables, and gap data quickly for large ranges.
• Python: Organizes output, checks patterns, and makes plots of gap sizes by modulus.
• SageMath: Verifies number theory calculations and compares independent implementations.
• NumPy: Handles numeric arrays when you sort and compare large gap tables.
• Matplotlib: Draws plots that show how gap sizes change across arithmetic progressions.

Experiment Steps

1. Define the exact family of arithmetic progressions you will study, including the modulus range and residue classes.
2. Choose one numerical gap statistic, then decide how you will record it for each progression.
3. Build a computation plan that filters squarefree numbers and stores only the data you need.
4. Compare the computed gaps with the sieve-based lower bound and mark where they agree or fail.
5. Test whether the same pattern holds across several moduli, not just one example.
6. Summarize the evidence in a proof-and-data story that explains what the computation adds to the theory.

Common Pitfalls

• Treating all squarefree numbers the same, which hides how residue class restrictions change the gaps.
• Mixing up consecutive squarefree numbers in the full integers with consecutive squarefree numbers inside one arithmetic progression.
• Trusting one computed table without cross-checking it in a second system, which can hide a coding error.
• Using a modulus range that is too wide, which makes the project look random instead of structured.
• Reporting a bound without explaining whether it is theoretical, computed, or verified against data.

What Makes This Competitive

A strong version of this project goes beyond listing gaps. You would compare several moduli, test a careful conjecture, and explain why the sieve bound works where it does. You would also separate raw computation from the proof idea, then show that your code reproduces the published table pattern. If you add a clean statistical comparison or a new residue-class viewpoint, the project starts to look like real research rather than a classroom demo.

Project Variations

• Study squarefree gaps only in prime moduli and compare them with composite moduli.
• Replace squarefree numbers with cube-free numbers and test whether the same gap behavior appears.
• Analyze the gap distribution visually with histograms, then compare the shapes across residue classes.

Learn More

• MIT OpenCourseWare, Number Theory: Search MIT OpenCourseWare for undergraduate lectures on arithmetic functions, sieves, and congruences.
• Introduction to Analytic Number Theory by Tom M. Apostol: Find a library copy or preview chapters for sieve basics and squarefree counts.
• Journal of Number Theory: Search for review articles and papers on squarefree numbers, sieves, and arithmetic progressions.
• PubMed, not for the math itself but for learning how to read abstracts and methods in technical papers, search the site for examples of concise research writing.
• PARI/GP documentation: Use the official manual and reference help to learn the functions for arithmetic functions and fast integer computation.