The GF(p)-Linear Complexity of Nested Leap-Year Sequences

Abstract

For a positive integer n and a prime p, the staircase sequence g_n(Y) = ⌊Y/n⌋ mod p is a linear recurring sequence over F_p with minimal polynomial (x-1)(x^n-1) and linear complexity n+1.

We determine the linear complexity of every F_p-linear combination of such sequences: it is M+1 minus a sum of Euler-φ terms, one for each divisor d of M = lcm(m_i) at which a certain linear form in the coefficients vanishes modulo p.

For the nested leap-correction sequence L_{a,b,c} = g_a - g_{ab} + g_{abc}, the finite-field model of a calendar with leap rule "every a years, except every ab, except every abc", this specializes to:

L(L_{a,b,c}) = abc+1 − (ab−a)·[p | c−1] − a·[p | bc−c+1]

For the Gregorian rule (a,b,c)=(4,25,4) the leap-year count Λ(Y) therefore has linear complexity exactly 401 modulo every prime p ∤ 400 except p=3 (complexity 305) and p=97 (complexity 397).

The Problem

The weekday of a Gregorian date is determined by Y modulo 400 and by the day-of-year; the only irregular ingredient is the number of leap years before year Y:

Λ(Y) = ⌊Y/4⌋ − ⌊Y/100⌋ + ⌊Y/400⌋

Reduced modulo 7, Λ is a periodic sequence over F_7 and therefore a linear recurring sequence. One can ask for its linear complexity: the length of the shortest linear feedback shift register that generates it. This note answers that question for the general family obtained by replacing (4, 100, 400) with (a, ab, abc) and 7 with any prime p not dividing abc.

Key Theorems

Theorem A: Single Staircase

For every positive integer n and every prime p, the sequence g_n over F_p has minimal polynomial (x-1)(x^n-1) and linear complexity n+1.

Theorem B: Upper Bound

For positive integers a, b, c and any prime p, L(L_{a,b,c}) ≤ abc+1, and the minimal polynomial of L_{a,b,c} divides (x-1)(x^{abc}-1).

Theorem C: Exact Value (Gregorian Calendar)

Let a, b, c be positive integers and p a prime with p ∤ abc. Then:

L(L_{a,b,c}) =
  abc+1 − (ab−a)        if p | c−1
  abc+1 − a             if p | bc−c+1
  abc+1                 otherwise

The first two conditions cannot hold simultaneously.

Theorem D: Arbitrary Linear Combinations

For arbitrary moduli m_1, …, m_k, let M = lcm(m_i) and σ_d = Σ_{i: d|m_i} c_i·(M/m_i) for each divisor d of M. Then:

L(s) = M+1 − Σ_{d|M, d>1} φ(d)·[σ_d=0] − ε

where ε ∈ {0,1,2} depends on whether certain divisibility conditions hold at x=1.

Results for Key Primes

Methodology

The standard approach for linear recurring sequences over a field: write the generating function as a reduced rational function and read the linear complexity off the degree of the denominator.

For the staircase sequence, the generating function is:

Σ_{Y≥0} ⌊Y/n⌋·x^Y = (x^n) / ((1−x)(1−x^n))

For linear combinations, we find the gcd of the numerator and denominator after combining over a common denominator. The deficit—how much the complexity falls short of the upper bound—is exactly this gcd degree, computed via root-counting.

All proofs are elementary, using only root-counting on the numerator and denominator of the generating function. No deep algebra or machinery is required.

Files

• nested-leap-complexity.pdf — Full paper (10 pages, all proofs)
• nested-leap-complexity.tex — LaTeX source
• nested-leap-complexity.md — Markdown version
• verify.py — Regenerates every computational claim

Reproducibility

To verify all computational claims in the paper, run:

python3 code/verify.py

Requirements: Python 3 with numpy and sympy
Runtime: ~1 minute on a typical machine

Citation

Bibtex:

@article{bonfioli2026leap,
  title={The $\mathrm{GF}(p)$-Linear Complexity of Nested Leap-Year Sequences},
  author={Bonfioli, Vico},
  year={2026},
  doi={10.5281/zenodo.22540620}
}