pith. sign in

arxiv: 2605.20947 · v1 · pith:ATYN3NA4new · submitted 2026-05-20 · 🧮 math.NT · cs.IT· math.IT

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

Yutong Zhang , Yaoran Yang This is my paper

Pith reviewed 2026-05-21 02:34 UTC · model grok-4.3

classification 🧮 math.NT cs.ITmath.IT
keywords Zadoff-Chu sequencesquadratic permutation polynomialsCAZAC sequencesp-adic valuationfinite differencessequence equivalenceinterleaved sequencesnumber theory
5
0 comments X

The pith

A valuation condition on the quadratic coefficient tells exactly when quadratic-permutation interleaved Zadoff-Chu sequences are equivalent to ordinary ones.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper gives an exact local arithmetic test that determines whether a quadratic-permutation-polynomial interleaved Zadoff-Chu sequence can be turned into a standard Zadoff-Chu sequence by the usual symmetry operations. Previous exhaustive checks had led to a conjecture that such equivalence fails only for certain prime-power lengths, but the new result shows the boundary is different and provides a simple check based on how divisible the quadratic coefficient is by each prime. The test works by tracking a third-order finite difference of the phase function, which stays the same under all the allowed operations. A reader cares because it replaces guesswork with a direct calculation for any length N, and it identifies the smallest counterexample length where new sequences appear outside the conjectured cases.

Core claim

For a normalized quadratic permutation polynomial π_{a,b}(k) = a k² + b k mod N, the interleaved Zadoff-Chu sequence is equivalent to an ordinary Zadoff-Chu sequence under the five standard operations if and only if the p-adic valuation of a meets or exceeds a specific threshold for every prime power dividing N: zero when p=2 and the power is one, one less than the power when p=2 or p=3 with higher powers, and equal to the power when p is larger than three.

What carries the argument

The third finite-difference invariant of the lifted phase function, which evaluates to 12a(2ak + 3a + b) and remains unchanged under CAZAC-preserving operations.

Load-bearing premise

The third finite-difference invariant of the phase is preserved under the five CAZAC-preserving operations and suffices to classify all equivalences to Zadoff-Chu sequences.

What would settle it

For the length N=25, take a normalized QPP with valuation of a equal to 1 and verify whether the resulting interleaved sequence can be transformed into a Zadoff-Chu sequence by the operations; the claim fails if it can.

read the original abstract

Berggren and Popovi\'c 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)=ak^2+bk\pmod 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\Vert N$, the valuation of $a$ satisfies \[ \nu_p(a)\ge \begin{cases} 0, & p=2,\ \alpha=1,\\ \alpha-1, & p=2,\ \alpha\ge2,\\ \alpha-1, & p=3,\\ \alpha, & p>3. \end{cases} \] The proof is based on a third finite-difference invariant of the lifted Zadoff--Chu phase, namely \[ \Delta^3\bigl((ak^2+bk+\varepsilon_N+2q)(ak^2+bk)\bigr) =12a(2ak+3a+b). \] 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\ge5$. In particular, $N=75=3\cdot5^2$ is the smallest non-prime-power counterexample to the conjectured ``only if'' direction. A second corollary records the corresponding statement for irreducible QPPs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript claims to derive an exact local arithmetic criterion based on p-adic valuations of the coefficient a in a normalized quadratic-permutation polynomial π_{a,b}(k) = a k^2 + b k mod N. This criterion determines precisely when the corresponding interleaved Zadoff-Chu sequence is equivalent to an ordinary Zadoff-Chu sequence under the five standard CAZAC-preserving operations. As a consequence, it corrects the Berggren-Popović conjecture by specifying the global conditions on N for which all such QPP-interleaved sequences are inequivalent, highlighting N = 75 as the smallest counterexample, and includes a corollary for irreducible QPPs. The proof centers on the invariance of the third finite difference Δ³((a k² + b k + ε_N + 2q)(a k² + b k)) = 12 a (2 a k + 3 a + b).

Significance. The result is significant for providing a complete resolution to the conjecture with a parameter-free derivation from the finite-difference invariant. This invariant approach is a strength, as it allows direct computation of the necessary valuation bounds without additional assumptions. The explicit counterexample and corollaries make the findings immediately applicable and falsifiable in small cases. If the invariant is indeed preserved and sufficient as claimed, the paper advances the classification of CAZAC sequences in a rigorous manner.

minor comments (2)
  1. The abstract states the third finite-difference invariant explicitly but does not detail the lifting process involving ε_N and q; a brief expansion in the introduction or a dedicated computation subsection would aid verification.
  2. The valuation criterion is presented as a cases statement; a compact table summarizing the lower bounds on ν_p(a) for p=2, p=3, and p>3 across different α would improve clarity and quick reference.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading, accurate summary of our results, and recommendation of minor revision. The referee's assessment of the significance of the finite-difference invariant and the explicit counterexample is appreciated.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper's central derivation computes the third finite-difference invariant explicitly as Δ³((ak² + bk + ε_N + 2q)(ak² + bk)) = 12a(2ak + 3a + b) and shows it is preserved under the five standard CAZAC-preserving operations. Equivalence to a Zadoff-Chu sequence then requires this invariant to match the corresponding quantity for ordinary ZC sequences, which directly forces the listed local valuation bounds on a for each prime power p^α || N. The resulting global condition on N corrects the Berggren-Popović conjecture as an immediate corollary. No step reduces to a fitted parameter renamed as prediction, a self-definitional loop, or a load-bearing self-citation; the argument is self-contained and rests on direct algebraic verification rather than external unverified premises.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard number-theoretic tools and sequence definitions from earlier work; no new free parameters or invented entities are introduced.

axioms (2)
  • standard math Standard properties of p-adic valuations and modular arithmetic
    Invoked to formulate the precise lower bounds on ν_p(a) for each prime power dividing N.
  • domain assumption The third finite difference of the lifted quadratic phase equals the stated linear expression in k
    Central computational step cited in the abstract as the basis of the equivalence criterion.

pith-pipeline@v0.9.0 · 5906 in / 1383 out tokens · 71374 ms · 2026-05-21T02:34:20.540524+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

  1. [1]

    Permutation polynomial interleaved Zadoff–Chu sequences,

    F. Berggren and B. M. Popovi ´c, “Permutation polynomial interleaved Zadoff–Chu sequences,”IEEE Transactions on Information Theory, vol. 70, no. 8, pp. 6068–6075, Aug. 2024

    work page 2024

  2. [2]

    On the construction and correlation properties of permutation-interleaved Zadoff–Chu sequences,

    Q. Yuan, C. Li, and X. Zeng, “On the construction and correlation properties of permutation-interleaved Zadoff–Chu sequences,” arXiv:2601.12107, 2026

    work page arXiv 2026

  3. [3]

    Polyphase codes with good periodic correlation properties (Corresp.),

    D. C. Chu, “Polyphase codes with good periodic correlation properties (Corresp.),”IEEE Transactions on Information Theory, vol. 18, no. 4, pp. 531–532, Jul. 1972

    work page 1972

  4. [4]

    Phase shift pulse codes with good periodic correlation properties (Corresp.),

    R. L. Frank, S. A. Zadoff, and R. C. Heimiller, “Phase shift pulse codes with good periodic correlation properties (Corresp.),”IRE Transactions on Information Theory, vol. IT-8, no. 6, pp. 381–382, Oct. 1962

    work page 1962

  5. [5]

    Generalized chirp-like polyphase sequences with optimum correlation properties,

    B. M. Popovi ´c, “Generalized chirp-like polyphase sequences with optimum correlation properties,”IEEE Transactions on Information Theory, vol. 38, no. 4, pp. 1406–1409, Jul. 1992

    work page 1992

  6. [6]

    Theory and applications ofq-ary interleaved sequences,

    G. Gong, “Theory and applications ofq-ary interleaved sequences,”IEEE Transactions on Information Theory, vol. 41, no. 2, pp. 400–411, Mar. 1995

    work page 1995

  7. [7]

    Interleavers for turbo codes using permutation polynomials over integer rings,

    J. Sun and O. Y . Takeshita, “Interleavers for turbo codes using permutation polynomials over integer rings,”IEEE Transactions on Information Theory, vol. 51, no. 1, pp. 101–119, Jan. 2005

    work page 2005

  8. [8]

    On maximum contention-free interleavers and permutation polynomials over integer rings,

    O. Y . Takeshita, “On maximum contention-free interleavers and permutation polynomials over integer rings,”IEEE Transactions on Information Theory, vol. 52, no. 3, pp. 1249–1253, Mar. 2006

    work page 2006

  9. [9]

    Permutation polynomials modulo2 w,

    R. L. Rivest, “Permutation polynomials modulo2 w,”Finite Fields and Their Applications, vol. 7, no. 2, pp. 287–292, Apr. 2001

    work page 2001

  10. [10]

    On quadratic inverses for quadratic permutation polynomials over integer rings,

    J. Ryu and O. Y . Takeshita, “On quadratic inverses for quadratic permutation polynomials over integer rings,”IEEE Transactions on Information Theory, vol. 52, no. 3, pp. 1254–1260, Mar. 2006

    work page 2006

  11. [11]

    On the degree of the inverse of quadratic permutation polynomial interleavers,

    J. Lahtonen, J. Ryu, and E. Suvitie, “On the degree of the inverse of quadratic permutation polynomial interleavers,”IEEE Transactions on Information Theory, vol. 58, no. 6, pp. 3925–3932, Jun. 2012

    work page 2012

  12. [12]

    Lidl and H

    R. Lidl and H. Niederreiter,Finite Fields, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 1997

    work page 1997

  13. [13]

    G. H. Hardy and E. M. Wright,An Introduction to the Theory of Numbers, 5th ed. Oxford, U.K.: Clarendon Press, 1979

    work page 1979

  14. [14]

    On vanishing sums of roots of unity,

    T. Y . Lam and K. H. Leung, “On vanishing sums of roots of unity,”Journal of Algebra, vol. 224, no. 1, pp. 91–109, Feb. 2000

    work page 2000

  15. [15]

    Sequences with low correlation,

    D. J. Katz, “Sequences with low correlation,” inArithmetic of Finite Fields: 7th International Workshop, WAIFI 2018, Bergen, Norway, June 14–16, 2018, Revised Selected Papers, L. Budaghyan and F. Rodr ´ıguez-Henr´ıquez, Eds., Lecture Notes in Computer Science, vol. 11321. Cham, Switzerland: Springer, 2018, pp. 149–172

    work page 2018