{"id":"0398e766-29cf-493e-bad3-fad2796cd8ba","arxiv_id":"2507.23200","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The DFT of a prime-length Zadoff-Chu sequence is rewritten as a cumulative micro-frequency-hopping phase, enabling a single-pass O(P) algorithm with a Gauss-sum starting phase.","lead":"Signals used in 4G and 5G are made of Zadoff-Chu sequences, and this paper shows their Fourier spectra can be built by stepping through a simple frequency-hopping grid. That yields a fast, low-operation recipe for computing these spectra, which matters for base stations and handsets.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The algorithm's correctness hinges on the unverified Gauss-sum phase QPo (Eqs. 11–12); a sign or normalization error there would rotate every DFT output.","rationale":"The recurrence in Algorithm 1 is internally consistent: after k updates, phase equals −QPo + Σ_{t=1}^{k}(Fs − t·u^{−1}), so the output is √P·exp(i2πQPo/P)·Z*_{u^{−1}}(k)·exp(−i2πFs·k/P). This algebraically matches Eq. 4 and Eq. 10 provided Fs and QPo are correct. Thus the only fragile external input to the central claim is QPo, exactly the reader's weakest assumption. The paper provides no numerical validation and no baseline comparison, so the conditional verdict is appropriate. The concrete test directly isolates QPo by comparing full complex DFT values, not just magnitudes, which is necessary because a constant phase error would be invisible in amplitude-only checks. I do not recommend ACCEPT or REJECT because the algebra appears sound; the manuscript simply needs the numerical anchor that its central claim currently lacks.","tokens_in":6484,"tokens_out":26411,"duration_ms":291201,"concrete_test":"Implement Algorithm 1 / Eq. 13 with exact or high-precision arithmetic for P ∈ {3, 5, 7, 11, 13, 17, 19, 23, 29, 31}, all u ∈ {1, …, P−1}, and Ts = 0 and Ts = 2. Compare complex-valued outputs against the direct DFT F(k) = Σ_{n=0}^{P−1} exp(−iπu·n(n+1)/P)·exp(−2πi·nk/P). Fail if the maximum absolute complex error exceeds 1e−10, or if all outputs share a constant phase rotation while magnitudes match. Include P ≡ 3 (mod 4) values (7, 11, 19, 23) to exercise the η_P = −i branch.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 1 computes each DFT coefficient as exp(-i2π·phase/P), where the absolute phase reference is set entirely by QPo from Eq. 12. If QPo is wrong by any constant, all P output coefficients are multiplied by the same unit-magnitude phase rotation: magnitudes stay correct, so any check that only compares |DFT| would pass, but the complex DFT values would be wrong. QPo is imported from Proposition 1 of Ref. [4] via Eq. 11 and algebraically repackaged in Eq. 12; the paper neither derives it nor checks it numerically, and it does not state the DFT sign convention used in Eq. 4 that anchors the phase of Fu(0). Because ℓ_{2u} is ±1 and η_P is 1 or −i, a sign error in either term would flip the constant phase by π or π/2, respectively, and would not be caught by the relative-phase argument in Section 2. I spot-checked P=5, u=1 and u=2 and found Eq. 12 consistent with direct summation, so this is not a demonstrated error; it is an unsecured load-bearing assumption that the manuscript should explicitly test.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes a direct O(P) algorithm for computing the length-P DFT of a prime-length Zadoff-Chu sequence with root u and cyclic shift T_s. The key idea is to express every DFT coefficient as a single complex exponential whose argument is a cumulative sum of frequency points in the 'linear micro-frequency hopping' (lmFH) pattern, with the absolute phase anchored by the Gauss-sum value F_u(0). The paper motivates the identity visually by reflecting the time-frequency pattern, imports an expression for F_u(0) from a generalized quadratic Gauss sum, and presents Algorithm 1 with a claimed cost of 2(P-1) additions, 2(P-1) modulo operations, and P complex exponentials. The Appendix contains a derivation for the cyclic-shift case.","tokens_in":6666,"tokens_out":20716,"duration_ms":211141,"significance":"If correct, the algorithm is an interesting contribution: it avoids FFT-style butterfly structures and can generate all DFT bins of a prime-length ZC sequence with a simple accumulator, which is attractive for hardware implementations. The paper correctly recognizes that the known DFT identity Eq. (4) can be recast as a linear-phase cumulative-sum form, and the Gauss-sum expression for F_u(0) removes the need for a length-P summation at the DC bin. The visual interpretation is instructive. However, the correctness of every output phase rests on externally cited formulas, and the manuscript contains no numerical validation; the significance is therefore conditional until those formulas are checked in the paper's own notation.","major_comments":[{"comment":"The central claim that Algorithm 1 computes the exact DFT values is not tested anywhere in the manuscript. Because every output coefficient is multiplied by the same unit-magnitude phase exp(i2π QPo/P), an error in the Gauss-sum phase QPo (Eqs. 11–12) would rotate all P coefficients while leaving their magnitudes unchanged; a magnitude-only comparison would not detect this. The paper should include a numerical comparison against direct summation or a standard FFT for several (P,u,Ts) choices, and it should state the DFT sign convention used in Eq. (4) so that the phase anchor is unambiguous.","section":"§3.2, Algorithm 1"},{"comment":"The phase QPo is imported from Proposition 1 of Ref. [4] and algebraically repackaged, but no derivation or independent check is provided. Since QPo is the absolute phase reference for the whole algorithm, this is a load-bearing external dependency. The manuscript should either derive Eq. (11) in the same notation or verify it numerically for a range of small primes; a sign or normalization error in ℓ_{2u} or η_P would introduce a global π or π/2 rotation in every DFT output.","section":"§3.1, Eqs. (11)–(12)"},{"comment":"Eq. (13) writes the phase as sum_{t=0}^k(-u^{-1}t+F_s)-QPo, which at k=0 equals F_s-QPo, while Algorithm 1 initializes phase=-QPo and outputs exp(i2π QPo/P). The two agree only if F_s in Eq. (13) is understood as F'_s, which is zero at t=0, per the note after Eq. (2); this is not stated in Eq. (13) or in the definition of F_s there. The notation should be made explicit, otherwise the printed central formula and the pseudocode appear inconsistent.","section":"§3.2, Eq. (13) and Algorithm 1"},{"comment":"The claimed efficiency improvement over Ref. [5] is not substantiated. Algorithm 1 still performs P complex exponential evaluations, the same order as direct use of Eq. (4) if each Z^*_{u^{-1}}(k) is generated recursively; the genuine savings are in avoiding complex multiplications, not in asymptotic complexity. The paper should include a concrete operations count or a benchmark to support the statement that the computational efficiency is 'significantly further enhanced'.","section":"§4, Conclusion"}],"minor_comments":[{"comment":"The summation notation in Eq. (1) is typeset ambiguously; it should be written explicitly as exp(i 2π P^{-1} sum_{t=0}^k s t) or with clear parentheses.","section":"Eq. (1)"},{"comment":"The paper says 'prime length P', but the derivation uses 2^{-1} ≡ (P+1)/2, which requires P to be odd; P=2 should be excluded or handled separately.","section":"Throughout"},{"comment":"The captions are minimal and the axes are not labeled consistently across figures, which makes the visual reflection argument harder to follow; marking representative coordinates would help.","section":"Figs. 2–4"},{"comment":"The algebra cancels u u^{-1} as 1 in integer expressions; this is only valid modulo P and should be stated explicitly, since the equality of phases relies on that modular reduction.","section":"Appendix A"},{"comment":"The term 'quasi phase offset' (QPo) is nonstandard; since QPo can be rational rather than an integer, the paper should define it as the phase numerator and explain how arithmetic modulo P is applied to it in Algorithm 1.","section":"§3.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's main risk is the unverified Gauss-sum phase, which anchors the absolute phase of every output coefficient; adding numerical validation and clarifying the F_s/F'_s convention would address the load-bearing issues. The visual derivation is heuristic but the paper does not rely on it for the final algorithm, and the imported identities are standard. I would not reject on novelty grounds, as the accumulator formulation is a simple and potentially useful reformulation, but the current version lacks the verification needed for a confident accept."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"My take: this is a clean, honest technical note that repackages known results into a nicer algorithm. The core identity (Eq. 4) is from Beyme and Leung, and the Gauss-sum formula for the DC term is imported from Gregoratti et al. What the paper adds is the lmFH visualization and the compact recurrence in Algorithm 1: one pass over k, keeping a running phase and a running frequency offset. For prime P and root u, that really does compute all P DFT coefficients with about 2(P-1) additions, 2(P-1) mods, and P complex exponentials. The algebra is internally consistent; I spot-checked P=5 for u=1 and u=2 and Eq. 12 matches direct summation. The appendix derivation of the cyclic-shift formula is also correct.\n\nThe soft spots are real but not disqualifying. The absolute phase of every DFT coefficient is fixed by QPo from Eq. 12, which comes from an unverified Gauss-sum expression. A sign error there would rotate the entire output. The stress-test note is right to flag this, but it is not a demonstrated error—my spot checks passed. Still, the paper should include a numerical test against direct DFT for several primes and roots, and state the DFT sign convention used in Eq. 4. Without that, the reader is asked to trust two imported formulas without verification. The efficiency claim over Ref. [5] is also asserted, not benchmarked; the recurrence is simple, but the comparison is anecdotal.\n\nNovelty is limited: this is a reformulation of known identities into a more elegant and implementable form, not a new complexity regime or a new discovery. That is fine for a short letter, but the paper should be honest about the incremental nature. The visual flip heuristic is useful for intuition, though it is not a proof.\n\nBottom line: the paper deserves a serious referee, but with a request for proper numerical validation and a clearer handling of the Gauss-sum phase. If those are supplied, it is a publishable technical note for practitioners in 4G/5G receiver design. For my own work, I would not cite it in the next year, but I would read a revised version.","headline":"The paper is a legitimate but modest reformulation: a one-pass phase-accumulator DFT for prime-length ZC sequences built on two cited identities, with the main open risk being the unverified Gauss-sum phase constant.","tokens_in":118,"tokens_out":1361,"would_cite":false,"duration_ms":30377,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["11L05","94A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"The DFT of a prime-length Zadoff-Chu sequence can be computed by a single phase recursion over P output points, with no FFT, using the lmFH pattern and a Gauss-sum phase offset.","keywords":["Zadoff-Chu sequences","DFT","linear micro-frequency hopping","lmFH pattern","Generalized Quadratic Gauss Sum","Legendre symbol","CORDIC","modular arithmetic"],"falsifier":"Compute F_u(0) by direct summation of the ZC sequence for a small prime, say P=13 and u=3, and compare with √P exp(i2π QPo/P); then run Algorithm 1 to produce all 13 coefficients and compare with a direct DFT or FFT. Any systematic phase mismatch across all outputs would disprove the formula, while exact agreement at several small primes and roots would support it.","tokens_in":6240,"feed_emoji":"📡","tokens_out":7012,"duration_ms":76922,"temperature":0.7,"pith_summary":"This paper claims that the discrete Fourier transform (DFT) of a Zadoff-Chu sequence of prime length P and root u needs no FFT: each output coefficient can be generated sequentially by accumulating frequency points in a linear micro-frequency hopping (lmFH) pattern, with a phase offset supplied by a generalized quadratic Gauss sum. If correct, the whole transform costs 2(P−1) additions, 2(P−1) modulo operations, and P complex exponentials after two one-time parameter calculations. The paper also gives a visual reason why the DFT of a ZC sequence is a conjugated, frequency-shifted dual ZC sequence: reflecting the time–frequency pattern across the line f=t turns the slope u into its modular inverse $u^{{-1}}$. A sympathetic reader would care because this turns a transform usually computed with an FFT into a direct point-by-point rule, which is attractive for hardware that already computes ZC sequences via frequency hopping.","feed_headline":"Prime-length Zadoff-Chu DFT needs no FFT — one pass does it","feed_subtitle":"A phase recursion plus one Gauss-sum offset reproduces every coefficient.","key_machinery":"The carrying object is the linear micro-frequency hopping (lmFH) pattern: a time–frequency staircase whose phase at time k is the cumulative sum of frequency points. The paper treats a ZC sequence as such a symbol, then observes that the DFT identity supplied by Ref. [3] rewrites the transform as another lmFH symbol with slope $u^{{-1}}$, frequency shift F_s, and phase offset ∠F_u(0). The offset is evaluated in closed form via the Generalized Quadratic Gauss Sum, Proposition 1 of Ref. [4], turning F_u(0) into √P times a known unit phase. Algorithm 1 then walks through the output frequencies with a two-line recursion: freq ← freq − $u^{{-1}}$ mod P, phase ← phase + freq mod P.","core_discovery":"The central claim is Algorithm 1: for prime P, root u, and cyclic shift Ts, every DFT coefficient obeys $$F_u(k)=\\sqrt{P}\\,\\exp\\!\\left(-\\frac{i2\\pi}{P}\\left(\\sum_{t=0}^{k}(-$u^{{-1}}$t+F_s)-QPo\\right)\\right),$$ with $$F_s=\\frac{P+1}{2}($u^{{-1}}$-1)-T_s$$ and $$QPo=\\frac{(3-2\\ell_{2u}-\\operatorname{mod}(P,4))P+u(P+1)^3}{8},$$ where \\(\\ell_{2u}\\) is the Legendre symbol of 2u modulo P. The paper derives this by rewriting the known DFT identity as an lmFH symbol and evaluating the DC phase through the Generalized Quadratic Gauss Sum. It further shows that IDFT uses the same recursion with the frequency-shift constant changed by 1 modulo P, and that a cyclic time shift Ts simply adds Ts to the output frequency shift.","pith_inferences":["Beyond the paper, the phase recursion suggests that all P output coefficients can be produced in parallel by evaluating the cumulative phase independently per k, which would map naturally onto SIMD or CORDIC pipelines; the paper does not develop this parallel view.","The flip-the-pattern interpretation treats the DFT as a geometric map sending slope u to u^{-1}; a natural untested extension is whether other quadratic-phase chirp-like sequences admit the same visual derivation, which the paper does not discuss.","A concrete testable extension is to check whether the same recursion survives when P is replaced by a prime power or a composite length; the Gauss-sum factor changes and the simple inverse-root relation may fail, but the lmFH viewpoint gives a concrete conjecture to verify numerically."],"forward_implications":["The FFT becomes unnecessary for prime-length ZC sequences: the recursion generates all P coefficients in one forward pass.","Total arithmetic per transform is 2(P−1) additions, 2(P−1) modulo operations, and P complex exponentials, plus one-time computation of a modular inverse and a Legendre symbol.","The same recursion computes IDFT with only a one-unit change in the frequency-shift constant, since the DFT and IDFT shifts differ by 1 modulo P.","A cyclic time shift Ts in the ZC sequence appears as an additive frequency shift Ts in the DFT, so multi-user cyclic-shift differentiation costs no extra computation.","The DC coefficient F_u(0) is exactly √P times a known unit phase, giving a closed-form Gauss-sum evaluation for the transform's overall scale and rotation."],"supporting_citations":[{"why":"Defines the micro-frequency hopping symbol whose phase is the cumulative sum of frequency points; this is the phase-accumulation mechanism Algorithm 1 uses.","marker":"[1]"},{"why":"Supplies the DFT identity expressing F_u(k) as a conjugated, frequency-shifted dual ZC sequence times F_u(0), the starting point for the lmFH rewriting.","marker":"[3]"},{"why":"Supplies Proposition 1, the Generalized Quadratic Gauss Sum giving F_u(0) as √P times a known unit phase, which becomes the QPo offset.","marker":"[4]"},{"why":"Supplies the prior efficient DFT formula and the cyclic-shift identity used in Appendix A, serving as the baseline the paper's algorithm improves on.","marker":"[5]"}],"fun_headline_variants":["ZC DFT without FFT: one recursion via lmFH","Prime Zadoff-Chu DFT done in one pass","Gauss-sum shortcut for Zadoff-Chu DFT","No FFT: lmFH pattern computes ZC DFT","Efficient ZC DFT via linear mFH recursion"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire phase of every coefficient rides on the imported Gauss-sum formula for F_u(0) being exactly right under the DFT convention used by Ref. [3]; if that formula has a sign or normalization error, every output coefficient is rotated by the same wrong phase.","fun_headline_variants_meta":{"raw":{"variants":["ZC DFT without FFT: one recursion via lmFH","Prime Zadoff-Chu DFT done in one pass","Gauss-sum shortcut for Zadoff-Chu DFT","No FFT: lmFH pattern computes ZC DFT","Efficient ZC DFT via linear mFH recursion"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000593,"raw_usage":{"total_tokens":2739,"prompt_tokens":864,"completion_tokens":1875,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":480,"completion_tokens_details":{"reasoning_tokens":1795}},"tokens_in":480,"tokens_out":1875,"duration_ms":17424,"temperature":1.0,"reasoning_tokens":1795,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T11:00:31.984400+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute F_u(0) by direct summation of the ZC sequence for a small prime, say P=13 and u=3, and compare with √P exp(i2π QPo/P); then run Algorithm 1 to produce all 13 coefficients and compare with a direct DFT or FFT. Any systematic phase mismatch across all outputs would disprove the formula, while exact agreement at several small primes and roots would support it.","supporting_citations":[{"cited_title":"Efficient computation of DFT of Zadoff-Chu sequences,","cited_arxiv_id":null,"evidence_quote":"Supplies the DFT identity expressing F_u(k) as a conjugated, frequency-shifted dual ZC sequence times F_u(0), the starting point for the lmFH rewriting."},{"cited_title":"Mathematical Properties of the Zadoff-Chu Sequences","cited_arxiv_id":"2311.01035","evidence_quote":"Supplies Proposition 1, the Generalized Quadratic Gauss Sum giving F_u(0) as √P times a known unit phase, which becomes the QPo offset."},{"cited_title":"Efficient DFT of Zadoff-Chu sequences","cited_arxiv_id":null,"evidence_quote":"Supplies the prior efficient DFT formula and the cyclic-shift identity used in Appendix A, serving as the baseline the paper's algorithm improves on."}],"review_version":1}