A Local Valuation Criterion for Quadratic-Permutation Interleaved Zadoff--Chu Sequences

Berggren and Popović introduced quadratic-permutation-polynomial interleaved Zadoff–Chu sequences and, from exhaustive data, conjectured that all normalized QPP-interleaved Zadoff–Chu sequences are inequivalent to ordinary Zadoff–Chu sequences precisely for prime-power lengths $N=p^n$ with $p>3$ and $n>1$. We give an exact local arithmetic criterion. For a normalized QPP ${\pi }_{a,b}(k)=a{k}^2+bk(\mathrm{m}\mathrm{o}\mathrm{d}N)$, the interleaved sequence is equivalent, under the standard five CAZAC-preserving operations, to a Zadoff–Chu sequence if and only if, for every prime power $p^{\alpha }\mathrm{\parallel }N$, the valuation of $a$ satisfies $${\nu }_p(a)\ge \{\begin{array}{ll}0,& p=2,\alpha =1,\\ \alpha -1,& p=2,\alpha \ge 2,\\ \alpha -1,& p=3,\\ \alpha ,& p>3.\end{array}$$ The proof is based on a third finite-difference invariant of the lifted Zadoff–Chu phase, namely $${\mathrm{\Delta }}^3((a{k}^2+bk+{\epsilon }_N+2q)(a{k}^2+bk))=12a(2ak+3a+b)\mathrm{.}$$ As a consequence, the conjectured prime-power boundary is not correct: the exact 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\ge 5$. In particular, $N=75=3\cdot 5^2$ is the smallest non-prime-power counterexample to the conjectured ``only if’’ direction. A second corollary records the corresponding statement for irreducible QPPs.