Overview
This research establishes a precise local arithmetic criterion for assessing the equivalence of quadratic-permutation-polynomial (QPP) interleaved Zadoff-Chu sequences to standard Zadoff-Chu sequences. The criterion determines equivalence under the standard five CAZAC-preserving operations. The findings clarify conditions under which such interleaved sequences are either equivalent or inequivalent to their ordinary counterparts, refuting a prior conjecture.
Research Context
Berggren and Popović previously introduced quadratic-permutation-polynomial interleaved Zadoff-Chu sequences. Based on exhaustive data, they conjectured that all normalized QPP-interleaved Zadoff-Chu sequences are inequivalent to ordinary Zadoff-Chu sequences exclusively for prime-power lengths $N=p^n$ where $p \ge 3$ and $n \ge 1$. This prior conjecture provided a boundary condition for inequivalence linked to specific prime-power structures of $N$.
Approach
The proof developed in this research is founded on a third finite-difference invariant of the lifted Zadoff-Chu phase. Specifically, for a normalized QPP $\pi_{a,b}(k)=ak^2+bk\pmod N$, the third finite-difference invariant is given by:
$\Delta^3\bigl((ak^2+bk+\varepsilon_N+2q)(ak^2+bk)\bigr) =12a(2ak+3a+b).$
This invariant serves as a foundational component for deriving the local arithmetic criterion. The criterion is expressed in terms of the valuation of $a$, denoted $\nu_p(a)$, relative to prime-power factors $p^\alpha\Vert N$ of the sequence length $N$.
Findings
The research provides an exact local arithmetic criterion for determining the equivalence of a normalized QPP interleaved sequence to a Zadoff-Chu sequence. Under the standard five CAZAC-preserving operations, an interleaved sequence is equivalent to a Zadoff-Chu sequence if and only if, for every prime power $p^\alpha\Vert N$, the valuation of $a$ satisfies the following conditions:
- If $p=2$ and $\alpha=1$, then $\nu_p(a) \ge 0$.
- If $p=2$ and $\alpha\ge2$, then $\nu_p(a) \ge \alpha-1$.
- If $p=3$, then $\nu_p(a) \ge \alpha-1$.
- If $p \ge 3$, then $\nu_p(a) \ge \alpha$.
As a direct consequence of this criterion, the previously conjectured prime-power boundary presented by Berggren and Popović is not entirely accurate. The non-vacuous condition for all nonzero normalized QPPs to be inequivalent to Zadoff-Chu sequences is that $N$ is odd, $9\nmid N$, and $p^2\mid N$ for at least one prime $p\ge5$. The research identifies $N=75=3\cdot5^2$ as the smallest non-prime-power counterexample to the "only if" direction of the original conjecture. A second corollary records the corresponding statement specifically for irreducible QPPs.
Why This Matters
This research refines the understanding of Zadoff-Chu sequence properties, particularly concerning their equivalence when interleaved with quadratic-permutation polynomials. The precise arithmetic criterion provides a definitive method for determining equivalence, correcting previous conjectures based on exhaustive data. This clarification is relevant for applications relying on the distinctness and mathematical properties of Zadoff-Chu sequences and their variations.