2025-11-18T03:07:12.924694

Improved Bounds for the Index Conjecture in Zero-Sum Theory

Pendleton
The Index Conjecture in zero-sum theory states that when $n$ is coprime to $6$ and $k$ equals $4$, every minimal zero-sum sequence of length $k$ modulo $n$ has index $1$. While other values of $(k,n)$ have been studied thoroughly in the last 30 years, it is only recently that the conjecture has been proven for $n>10^{20}$. In this paper, we prove that said upper bound can be reduced to $4.6\cdot10^{13}$, and lower under certain coprimality conditions. Further, we verify the conjecture for $n<1.8\cdot10^6$ through the application of High Performance Computing (HPC).
academic

Improved Bounds for the Index Conjecture in Zero-Sum Theory

Basic Information

  • Paper ID: 2510.11976
  • Title: Improved Bounds for the Index Conjecture in Zero-Sum Theory
  • Author: Andrew Pendleton
  • Classification: math.NT (Number Theory), math.CO (Combinatorics)
  • Publication Date: October 13, 2025 (arXiv preprint)
  • Paper Link: https://arxiv.org/abs/2510.11976

Abstract

The Index Conjecture in zero-sum theory posits that when nn is coprime to 6 and k=4k=4, the index of every minimal zero-sum sequence of length kk modulo nn equals 1. While other (k,n)(k,n) values have been extensively studied over the past 30 years, this conjecture was only recently proven to hold for n>1020n>10^{20}. This paper reduces this upper bound to 4.6×10134.6\times10^{13}, with further reductions under specific coprimality conditions. Additionally, high-performance computing (HPC) verification confirms the conjecture for n<1.8×106n<1.8\times10^6.

Research Background and Motivation

Research Problem

This paper investigates the Index Conjecture in zero-sum theory, an important problem in combinatorial number theory. Specifically:

  1. Core Question: For positive integers nn coprime to 6, do all minimal zero-sum sequences of length 4 possess index 1?
  2. Theoretical Significance: This problem connects multiple mathematical branches including integer partitions, atomic monoid theory, Heegaard Floer homology, and Dedekind sums
  3. Computational Challenge: Requires handling extremely large numerical ranges where traditional methods are inadequate

Problem Significance

  • Theoretical Value: Index research has spanned 30 years with connections to multiple important mathematical fields
  • Classification Significance: For different (k,n)(k,n) pairs, all pairs are known to be "good" (index 1) when k≤3k≤3, "bad" when 5≤k≤n/2+15≤k≤n/2+1, and "good" when k>n/2+1k>n/2+1
  • Special Case: The k=4k=4 case is most complex with no simple characterization, representing the core difficulty in this field

Limitations of Existing Methods

  • Theoretical Bounds: Ge proved in 2021 that the conjecture holds for n>1020n>10^{20}, but this bound is excessively broad
  • Computational Verification: Ponomarenko in 2004 only verified up to n<1000n<1000, with computational capacity limiting the verification range
  • Technical Bottleneck: Requires more refined Fourier analysis techniques and stronger computational resources

Core Contributions

  1. Significant Improvement of Theoretical Bounds: Substantially reduces the theoretical proof upper bound for the Index Conjecture from 102010^{20} to 4.6×10134.6\times10^{13}
  2. Provision of Stronger Conditional Bounds: Provides smaller upper bounds under additional coprimality conditions (e.g., reducing to 1.4×10131.4\times10^{13} when nn is only divisible by powers of 5)
  3. Large-Scale Computational Verification: Extends computational verification range from n<1000n<1000 to n<1.8×106n<1.8\times10^6 utilizing HPC resources
  4. Improved Technical Methods: Optimizes key lemmas in Fourier analysis techniques and improves Ramanujan sum estimates

Detailed Methodology

Task Definition

Input: Positive integer nn satisfying gcd⁡(n,6)=1\gcd(n,6)=1Output: Determine whether all minimal zero-sum sequences S=(a1)(a2)(a3)(a4)S=(a_1)(a_2)(a_3)(a_4) of length 4 satisfy ind(S)=1\text{ind}(S)=1

The index of a sequence is defined as: ind(S)=min⁡{∑i=14(gai)nn:g∈G∗}\text{ind}(S) = \min\left\{\frac{\sum_{i=1}^4(ga_i)_n}{n} : g \in G^*\right\}

Theoretical Method Architecture

1. Fourier Analysis Framework

Utilizes periodic indicator function χ(t)\chi(t) and its smoothed version f(t)f(t):

1, & \text{if } 0 < \{t\} < 1/2 \\ 1/2, & \text{if } \{t\} = 1/2 \\ 0, & \text{if } \{t\} > 1/2 \end{cases}$$ #### 2. Key Sum Decomposition Decomposes the main sum $S_1$ into three parts: $$S_1 = \phi(n) \cdot (f̂(0))^3 + f̂(0) \cdot \left(\sum_{h_2}\sum_{h_3} + \sum_{h_3}\sum_{h_1} + \sum_{h_1}\sum_{h_2}\right)$$ Further decomposes each double sum as: $$\sum_{h_2}\sum_{h_3} = S_b^* + \tilde{T}_b + R_b$$ #### 3. Technical Innovations **Improved Ramanujan Sum Estimates** (Lemma 3.1): - For cases satisfying specific linear relationships, improves coefficients from approximately 0.05 to 0.079021 - Key observation: $|c_n(3mb+(3m)^*)| ≤ \phi(n)/4$ **Optimized Parameter Selection**: - Selects optimal $H≈7000$ by minimizing the ratio $H/c_1$ - Balances contributions from different error terms ### Computational Method Architecture #### 1. High-Performance Parallel Algorithm ```rust fn big_check(n: i64) { let coprimes: Vec<i64> = (1..n) .into_par_iter() .filter(|&i| i.gcd(&n) == 1) .collect(); // Parallel verification of all possible sequences coprimes_a.into_par_iter().for_each(|a| { for &b in coprimes_b.iter() { // Verify sequence conditions and index computation } }); } ``` #### 2. Search Space Optimization Exploits structural properties of Lemma 3.7: - Fixes first element as 1 (via multiplication by inverse) - Restricts search range: $2 ≤ a < n/2 < b$ - Further constraints: $n+2-a ≤ b ≤ (n-3)/2 - a/2$ ## Experimental Setup ### Computational Resources - **Platform**: Kuro high-performance computing cluster at William & Mary - **Scale**: 8-16 nodes with approximately 1024 parallel threads - **Storage**: Lustre file system for distributed storage management ### Verification Range - **Target Set**: All $n < 1.8\times10^6$ satisfying $\gcd(n,6)=1$ and $5|n$ - **Quantity Estimate**: Approximately $\lfloor N/15 \rfloor$ such $n$ values ### Algorithm Optimization - **Language Choice**: Rust (compiled language with excellent multithreading support) - **Parallelization**: Data parallelism implemented using Rayon library - **Load Balancing**: Dynamic task allocation prevents race conditions ## Experimental Results ### Theoretical Improvement Results **Main Theorem 1.4**: Conjecture 1.3 holds for $n > 4.6\times10^{13}$ **Conditional Improvements** (Remark 4.1): | Coprimality Condition $P_n$ | Upper Bound | |---|---| | $\{2,3\}$ | $4.6\times10^{13}$ | | $\{2,3,7\}$ | $3.4\times10^{13}$ | | $\{2,3,11\}$ | $2.9\times10^{13}$ | | $\{2,3,13\}$ | $2.6\times10^{13}$ | | $\{2,3,17\}$ | $2.3\times10^{13}$ | | $\{2,3,19\}$ | $2.2\times10^{13}$ | ### Computational Verification Results - **Verification Range**: Successfully verified all cases with $n < 1.8\times10^6$, $\gcd(n,6)=1$, and $5|n$ - **Computational Efficiency**: Significant performance improvements compared to Python implementations - **Reliability**: Distributed computing and file system ensure result completeness ### Technical Improvement Effects - **Bound Improvement**: Reduces theoretical upper bound by approximately 6-7 orders of magnitude - **Computational Extension**: Expands verification range by approximately 1800-fold - **Method Optimization**: Coefficient improvements in key lemmas directly contribute to final bound enhancement ## Related Work ### Historical Development 1. **Early Work**: Lemke & Kleitman (1989) and Geroldinger (1990) established foundations 2. **Index Concept**: Chapman et al. (1999) first formally defined the index 3. **Classification Results**: Savchev & Chen, Yuan (2007) provided complete characterization for most $(k,n)$ pairs ### Recent Progress - **Ge (2021)**: First proof for large $n$, but with bound $10^{20}$ - **Zeng & Qi (2017)**: Proved special case when $n$ is coprime to 30 - **Computational Aspects**: Ponomarenko (2004) computational verification work ### Paper Positioning This paper achieves dual improvements based on Ge's work: 1. **Theoretical Aspect**: Substantially improves bounds through more refined analysis 2. **Computational Aspect**: Expands verification range utilizing modern HPC technology ## Conclusions and Discussion ### Main Conclusions 1. **Theoretical Breakthrough**: Reduces the proof upper bound for the Index Conjecture from $10^{20}$ to $4.6\times10^{13}$ 2. **Computational Verification**: Confirms conjecture correctness for $n < 1.8\times10^6$ 3. **Methodological Contribution**: Improves application of Fourier analysis techniques in zero-sum theory ### Limitations 1. **Theoretical Bounds**: Despite substantial improvement, a massive gap remains between $4.6\times10^{13}$ and computational verification at $1.8\times10^6$ 2. **Computational Constraints**: Limited by current computational resources, preventing further expansion of verification range 3. **Method Limitations**: Fourier analysis methods show diminishing efficiency when handling smaller $n$ values ### Future Directions 1. **Theoretical Improvement**: Seek new number-theoretic techniques to further narrow theoretical bounds 2. **Computational Extension**: Utilize more powerful computational resources to expand verification range 3. **Algorithm Optimization**: Develop more efficient parallel algorithms and data structures ## In-Depth Evaluation ### Strengths 1. **Significant Theoretical Progress**: Seven orders of magnitude improvement in bounds represents major breakthrough in the field 2. **Technical Innovation**: Substantial improvements in Fourier analysis and Ramanujan sum estimation 3. **Computational Methodology**: Demonstrates effective application of HPC to number-theoretic problems 4. **Completeness**: Rigorous theoretical proofs and sufficient computational verification ### Weaknesses 1. **Remaining Gap**: The gap between theoretical bounds and computational verification remains unresolved 2. **Limited Generality**: Methods primarily target the special case $k=4$ 3. **Computational Scalability**: Current algorithm time complexity limits further extension ### Impact 1. **Theoretical Contribution**: Provides new analytical tools for zero-sum theory 2. **Methodological Value**: Demonstrates HPC application in number theory 3. **Foundation for Future Work**: Establishes basis for further narrowing theory-computation gap ### Applicable Scenarios 1. **Number Theory Research**: Zero-sum theory and additive combinatorics problems 2. **Computational Mathematics**: Reference for large-scale number-theoretic computations 3. **Algorithm Design**: Implementation example for parallel number-theoretic algorithms ## References This paper cites 21 related references, primarily including: - Ge, F. (2021): Solution to the index conjecture in zero-sum theory - Ponomarenko, V. (2004): Minimal zero sequences of finite cyclic groups - Chapman et al. (1999): Minimal zero-sequences and the strong Davenport constant - Rosser & Schoenfeld (1962): Euler totient function bounds --- **Overall Assessment**: This is an important contribution to zero-sum theory that significantly advances research on the Index Conjecture through dual theoretical and computational improvements. While complete resolution of the conjecture requires further work, this paper's methods and results provide valuable tools and insights for the field.