The Cross-Correlation Distribution of the Niho-Type Decimation $d=4(2^m-1)+1$

Maosheng Xiong; Haode Yan

Source-linked AI summary

The Cross-Correlation Distribution of the Niho-Type Decimation $d=4(2^m-1)+1$

Maosheng Xiong, Haode Yan

arXiv:2609.04683v1Sep 4, 2026cs.IT

TL;DR

The paper solves the cross-correlation distribution problem for the Niho-type decimation d = 4(2^m − 1) + 1 over F_{2^{2m}}. It normalizes four-element root subsets through their product and resolvent, then evaluates the resulting finite-field equations with character and Kloosterman sums. The outcome is an explicit distribution of all cross-correlation values and frequencies for every positive integer m.

Problem
The full cross-correlation distribution for d = 4(2^m − 1) + 1 remained open despite prior bounds on the number of values.
Method
The paper counts admissible four-element subsets of U_{q+1} by normalizing their product, analyzing an associated resolvent, and evaluating the resulting equations with character and Kloosterman sums.
Results
The paper determines the complete value distribution of C_d(τ), including explicit frequencies, for p = 2, q = 2^m, and d = 4(2^m − 1) + 1.
Takeaways & Limitations
The previously open distribution problem for this Niho-type decimation is solved for every positive integer m.

Abstract

from arXiv · show

The cross-correlation problem is a classical problem in sequence design. In this paper, we determine the cross-correlation distribution of the Niho-type decimation $d=4(2^m-1)+1$ over $\mathbb F_{2^{2m}}$ for every positive integer $m$. With $q=2^m$, this is equivalent to determining the distribution of the number of roots in $U_{q+1}$ of $f_a(x)=x^7+ax^4+\bar a x^3+1$ for $a\in\mathbb F_{q^2}$, where $U_{q+1}=\{x\in\mathbb F_{q^2}:x^{q+1}=1\}$. The main difficulty is to count the four-element subsets of $U_{q+1}$ that may occur as root sets of $f_a$. We normalize such subsets by their product and study the resulting condition through the associated resolvent. This reduces the required enumeration to several equations over $\mathbb F_q$, which are evaluated by character sums and Kloosterman sums. The remaining mixed Kloosterman sum is related to a Kloosterman sum over $\mathbb F_{2^{2m}}$ and is evaluated using a theorem of Carlitz. Consequently, we obtain explicit formulas for all the frequencies in the cross-correlation distribution.

I. INTRODUCTION

The paper studies the cross-correlation distribution of the Niho-type decimation d = 4(2^m − 1) + 1, solving the previously open full distribution problem. It proves the relevant value bounds and gives explicit small-m examples.

Motivation: The cross-correlation function compares an m-sequence with its d-decimation, where coprimality ensures the decimated sequence remains an m-sequence.The paper frames the distribution of correlation values and their frequencies as a classical sequence-design problem.
Background: Niho-type decimations have been studied since 1972 and have applications in sequence design, cryptography, and coding theory.The paper places the case d = 4(2^m − 1) + 1 within this longer research program.
Problem: For d = 4(2^m − 1) + 1, prior work established at most 5 values when m is even and at most 6 when m is odd, but the full distribution remained open.This paper also gives a new proof of the at-most-5-values conjecture.
Main result: Theorem 1 gives the value distribution of C_d(τ) for p = 2 and q = 2^m, with d = 4(2^m − 1) + 1.The theorem is the paper’s stated main result, with additional displayed frequency formulas.
Examples: For m = 4, the values −17, −1, 15, 31, and 63 occur 88, 89, 56, 20, and 2 times, respectively.Here T_4 = −17.

A. Notation •

This section establishes notation for finite fields, traces, trace-defined subsets, conjugation, the unit circle U_{q+1}, square roots, and four-element subsets with their elementary symmetric quantities.

Field notation: The paper sets n = 2m and q = 2^m, and uses F_q for the finite field with q elements.Finite-field notation underlies the later enumeration arguments.
Trace: For t dividing s, the trace from F_{2^s} to F_{2^t} is defined by summing the successive 2^t-powers.The shorthand Tr denotes the trace from F_q to F_2.
Trace-defined sets: The sets H_i and D_i collect field elements according to the binary trace of x and x^−1, respectively.H_i allows zero, whereas D_i is defined over F_q^*.
Conjugation and unit circle: For x in F_{q^2}, the notation x̄ denotes x^q, and U_{q+1} is the set of elements satisfying x^{q+1} = 1.The paper also uses the unique square root available in characteristic 2.
Auxiliary field: The field F_4 is represented as {0, 1, ω, ω^2}, with ω satisfying ω^2 + ω + 1 = 0.This fixes the primitive element used in the paper’s notation.
Set notation: For a four-element set V, σ_i denotes its elementary symmetric quantities, while kA denotes scalar multiplication of a set.The notation is introduced for later analysis of four-element subsets.

B. On 4-element subsets of Uq+1 with product 1

The paper studies four-element subsets of U_{q+1} whose product is 1 by encoding them with a three-element resolvent. This encoding constrains the resolvent to F_q and determines how many subsets correspond to it.

Resolvent: For V ⊂ U_{q+1} with four distinct elements and σ_4(V) = 1, the resolvent is the three-element set of pairwise product sums.It is defined as {v_1v_2 + v_3v_4, v_1v_3 + v_2v_4, v_1v_4 + v_2v_3}.
Resolvent: Every resolvent element lies in F_q, and more precisely in D_1 ∪ {0}.Each element corresponds to a quadratic whose roots lie in U_{q+1}.
Recovery and counting: A resolvent R ⊆ D_1 ∪ {0} with three elements determines one V when 0 ∈ R and exactly two such V when 0 ∉ R.This multiplicity is central to recovering and counting the four-element subsets.
Recovery and counting: When 0 ∈ R, the proof reduces one resolvent relation to v_1v_4 = v_2v_3 = 1 and then enumerates possible products.The displayed intermediate cases support the unique-recovery conclusion.
Recovery and counting: A direct computation shows that a specified resolvent can correspond to a unique normalized set V in the stated case.The paper uses this uniqueness in its resolvent analysis.
Symmetric relations: The symmetric quantities σ_1(V) and σ_2(V) can be expressed through the resolvent elements r_1, r_2, and r_3.In particular, σ_2(V) = r_1 + r_2 + r_3, with additional relations involving σ_1(V).

III. ON KLOOSTERMAN SUMS

This section develops character- and Kloosterman-sum tools used to evaluate the paper’s finite-field enumerations. It relates the key sum S_m to Kloosterman sums, with parity-dependent formulas and an explicit recurrence-based expression.

The Kloosterman sum over F_q is introduced as a central object for the section’s character-sum calculations.
For odd m, S_m equals −K_{F_{q^2}}(ω).
For even m, S_m equals (K_{F_q}(ω))^2.
Carlitz’s theorem supplies initial values and a recurrence for T_m=K_{F_{4^m}}(ω), yielding an explicit integer formula.The section then expresses S_m through T_m according to the parity of m.
The resulting character-sum identities are used in subsequent evaluations involving substitutions, trace counts, and rational functions.

IV. ON THE NUMBER OF SOLUTIONS OF CERTAIN EQUATIONS

This section counts solutions of selected equations over finite fields by transforming them into trace and character-sum conditions. The analysis distinguishes odd and even m and establishes bijections and solution-count formulas needed later.

Character sums are used to determine the number of solutions of certain finite-field equations.
For each admissible y in H_1, the quadratic condition yields exactly one x in H_1, subject to the stated trace constraint.
A change of variables expresses x, y, and z uniquely in terms of y+z, θ, and φ.
For a given θ, solvability of Δ_θ(φ)=0 is characterized by a finite-field condition.
When m is odd, Δ_θ(φ) is nonzero for every φ, while when m is even, exactly two φ values satisfy Δ_θ(φ)=0.
The resulting character-sum evaluations complete the required solution counts.

V. THE CROSS CORRELATION DISTRIBUTION

This section connects the cross-correlation distribution to the distribution of root counts of a polynomial on U_{q+1}. For d=4q−3, the paper reduces the problem to determining the frequencies N_0 through N_7.

The cross-correlation function is defined as a binary trace sum between an m-sequence and its d-decimation.
Determining the cross-correlation distribution reduces to determining the multiset of sequence values over F_{2^n}.
For Niho-type exponents with n=2m, prior results relate sequence values to the number N(a) of roots in U_{q+1} satisfying the associated equation.
The frequencies of the possible values are characterized through the quantities N_i, with four power moments also available from prior work.
The paper specializes to q=2^m and d=4q−3, then seeks the distribution of the number of roots of f_a(x) in U_{q+1}.

A. Determination of N4 and N6

This subsection determines the frequencies associated with four- and six-root cases of f_a in U_{q+1}. It proves that six roots never occur, while four roots occur only under a parity-dependent condition on m.

Roots outside U_{q+1} occur in conjugate pairs, constraining possible root counts in U_{q+1}.
The four-root case is analyzed through multiple-root conditions, which force a∈U_{q+1} and constrain the repeated root.
N_6=0 for every m.
When m is odd, the three roots of x^3=a lie in U_{q+1} exactly when the relevant index is divisible by 3, producing the stated N_4 count.

B. Determination of N7

The section proves that f_a(x) cannot have seven distinct roots in U_{q+1}, establishing N7=0. The contradiction follows from a double-counting argument that forces S=0 while the root configuration implies S≠0.

Assuming seven roots, the proof defines a symmetric quantity S and obtains S=0 through coefficient comparison.
N7=0: no polynomial f_a(x) has seven distinct roots in U_{q+1}.
The root ratios t_ij belong to U_{q+1}\{1}, and quadratic trace criteria produce a contradiction with S=0.

C. Determination of N5

The section counts normalized four-element root sets by translating the determinant condition into equations involving the resolvent. Separate cases according to whether the resolvent contains zero are reduced to finite-field counts and then combined to determine |W|.

Scaling by U_{q+1} gives a unique normalization with σ4(V)=1, so |W| is obtained from the total determinant-zero count by dividing by q+1.
The determinant condition D(V)=0 characterizes four-element subsets V⊆U_{q+1} relevant to the root-set enumeration.
When 0∈Res(V), the resolvent parameters reduce the condition to an equation in x,y∈H1, with ordered-pair symmetries handled explicitly.
When 0∉Res(V), three distinct normalized variables x,y,z∈H1 satisfy an equation Φ(x,y,z)=0, and the resulting sets are counted modulo two-to-one correspondence.
The normalized root-set count is combined with the preceding formulas to obtain the stated expression for |W|.

D. Main result

This section completes the value distribution by solving the remaining finite-field equation and assembling the frequencies N0 through N3 from earlier results. The resulting distribution then yields the cross-correlation distribution.

The equation (x^q+x)^4(x^2+x+1)=0 has q solutions when m is even and q+2 solutions when m is odd.
The values of N4, N5, N6, and N7 are supplied by earlier theorems, while Theorem 26 gives N0, N1, N2, and N3.
The completed multiset {s(a): a∈F_{q^2}} directly implies the cross-correlation distribution through the relation between C_d(τ) and s(a).

VI. CONCLUDING REMARKS

The paper determines the complete cross-correlation distribution for the Niho-type decimation d=4(2^m−1)+1, equivalently the root-count distribution of f_a on U_{q+1}. Its approach combines normalized root subsets, resolvents, character sums, and Kloosterman sums to obtain explicit frequencies.

The paper determines the complete cross-correlation distribution between a binary m-sequence and its d-decimation, equivalently the root-count distribution of f_a in U_{q+1}.
The enumeration reduces four-element root subsets to equations over F_q, which are evaluated using character sums, Kloosterman sums, and Carlitz’s theorem.
The normalized-root-subset and resolvent method may also apply to other Niho-type decimations whose unit-circle equations remain manageable.