The crosscorrelation distribution of the Niho decimation d=4(2ᵐ-1)+1: one unknown, and its value for m ≤ 15

Abstract

Let n=2m, let α be a primitive element of 𝔽_(2ⁿ), let sₜ=Tr(αᵗ) be the binary m-sequence it generates, and let C_d(τ) be the crosscorrelation between {sₜ} and its decimation by d. For the Niho decimation d=4(2ᵐ-1)+1=2ᵐ⁺²-3, Helleseth, Katz and Li proved that C_d takes at most five values when m is even and at most six when m is odd; the multiplicities are Open Problems 7 and 9 of the 2024 survey of Helleseth and Li, where both are stated to be open. We contribute three things. First, an elementary reduction: the four power moments available in the literature — three classical, the fourth a specialisation of a recent formula of Cui, Luo and Xiang — form a linear system that determines every multiplicity from N₄ alone when m is even, and from N₃ and N₄ when m is odd. We solve it explicitly, so each open problem becomes one missing integer (two for odd m). Second, we determine that integer exactly for every m with 2 ≤ m ≤ 15, by an exhaustive computation of the whole distribution over 𝔽_(2²ᵐ) for 2 ≤ m ≤ 11 inside a proof assistant and for 12 ≤ m ≤ 15 outside it. Third, we observe that the answer is governed at every one of those m by the same integer Tₘ=2ᵐτₘ, satisfying T₁=1, T₂=-7 and Tₖ₊₂=Tₖ₊₁-4Tₖ, that Xia, Li, Zeng and Helleseth found for the neighbouring decimation 3(2ᵐ-1)+1: for odd m the two decimations have the identical distribution, although they are inequivalent for m ≥ 5, and for even m the distribution of 4(2ᵐ-1)+1 is that of 3(2ᵐ-1)+1 after the single substitution Tₘ ↦ 2ᵐ⁺¹+2-Tₘ. We state this as a conjecture and are explicit that no proof for general m is offered. Apart from the conjecture itself, the four values computed outside the proof assistant, one elementary enumeration and one polynomial identity — each flagged where it occurs — every assertion below is machine-checked in Lean 4.

Open review

This founding-collection manuscript received AI review before publication. Independent human review is open. Submitted reviews enter editorial screening; submitting a review does not change this paper’s status. Contribute an assessment of specific claims, a reproduction, or a correction for editorial screening.

Archived files

1. Version 1 · current (opens in a new tab)

   Source snapshot 2026-09-07 03:53 UTC

   File fingerprint

   e3cf635887435c01fa025427e5553d37d359b49372a7bf5d3838db1a0bdea9e3