pith. sign in

arxiv: 2512.23194 · v3 · submitted 2025-12-29 · 💻 cs.IT · math.IT

A New Family of Binary Sequences via Elliptic Function Fields over Finite Fields of Odd Characteristics

Xiaofeng Liu , Jun Zhang , Fang-Wei Fu This is my paper

Pith reviewed 2026-05-16 19:52 UTC · model grok-4.3

classification 💻 cs.IT math.IT
keywords binary sequenceselliptic function fieldsodd characteristicquadratic residuecorrelationlinear complexitysequence construction
0
0 comments X

The pith

Cyclic elliptic function fields over odd finite fields produce binary sequences with bounded balance, correlation, and linear complexity.

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

This paper extends the construction of binary sequences from cyclic elliptic function fields to fields of odd characteristic. Instead of using the trace map as in the even-characteristic case, it employs the quadratic residue map to define the sequences. For any such field with q+1+t rational points and any d coprime to that number, a family is built with length q+1+t and size q^{d-1}-1. The balance is upper-bounded by (d+1) times floor of 2 sqrt q plus |t| plus d, correlation by (2d+1) times that floor plus |t| plus 2d, and linear complexity has a specific lower bound. Readers interested in sequence design for communications would care because these parameters control performance in applications like CDMA and cryptography.

Core claim

Using the quadratic residue map η on a cyclic elliptic function field over F_q (q odd) with q+1+t points, the authors define a family of binary sequences of length q+1+t and size q^{d-1}-1 for d coprime to q+1+t. They prove that the balance of any sequence in the family is at most (d+1)⌊2√q⌋ + |t| + d, the correlation between distinct sequences is at most (2d+1)⌊2√q⌋ + |t| + 2d, and the linear complexity is at least (q + 1 + 2t - d - (d+1)⌊2√q⌋) / (d + d ⌊2√q⌋).

What carries the argument

the quadratic residue map η on the points of the cyclic elliptic function field, which maps elements to ±1 or 0 and is used to generate the binary sequence values while preserving enough structure for the bounds.

If this is right

  • These sequences have explicit, computable bounds that depend on the field size q and the number of points t.
  • The construction works for any d coprime to the group order q+1+t, allowing flexibility in family size.
  • The lower bound on linear complexity grows roughly like q divided by d times sqrt q, which is large for large q.
  • Such families can be used directly in applications requiring low auto- and cross-correlation.
  • The method extends the even-char case, showing the approach is characteristic-independent under the cyclic assumption.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the bounds are tight, these sequences may outperform random sequences in correlation properties for certain parameters.
  • This fills the gap for odd-characteristic fields, which are common in many cryptographic settings.
  • One could test the construction on small fields like q=7 or q=9 to verify the bounds numerically.
  • Future work might combine this with other maps to improve the constants in the bounds.

Load-bearing premise

The quadratic residue map must induce sequences whose partial sums and products behave like those in the even case so that the Hasse-Weil bound and character sum estimates apply directly.

What would settle it

Select a small odd prime power q, find a cyclic elliptic curve with known t, choose d=1, explicitly list the sequences from the rational points, compute their actual maximum imbalance, and check whether it stays below (2)⌊2√q⌋ + |t| +1; violation for the computed value would falsify the general bound.

read the original abstract

Motivated by the constructions of binary sequences by utilizing the cyclic elliptic function fields over the finite field $\mathbb{F}_{2^{n}}$ by Jin \textit{et al.} in [IEEE Trans. Inf. Theory 71(8), 2025], we extend the construction to the cyclic elliptic function fields with odd characteristic by using the quadratic residue map $\eta$ instead of the trace map used therein. For any cyclic elliptic function field with $q+1+t$ rational points and any positive integer $d$ with $\gcd(d, q+1+t)=1$, we construct a new family of binary sequences of length $q+1+t$, size $q^{d-1}-1$, balance upper bounded by $(d+1)\cdot\lfloor2\sqrt{q}\rfloor+|t|+d,$ the correlation upper bounded by $(2d+1)\cdot\lfloor2\sqrt{q}\rfloor+|t|+2d$ and the linear complexity lower bounded by $\frac{q+1+2t-d-(d+1)\cdot\lfloor2\sqrt{q}\rfloor}{d+d\cdot\lfloor2\sqrt{q}\rfloor}$ where $\lfloor x\rfloor$ stands for the integer part of $x\in\mathbb{R}$.

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

2 major / 2 minor

Summary. The manuscript extends binary sequence constructions from cyclic elliptic function fields over even-characteristic finite fields to the odd-characteristic case. It replaces the trace map with the quadratic residue map η on the rational points of a cyclic elliptic curve with q+1+t points, yielding a family of binary sequences of length N=q+1+t and size q^{d-1}-1 (d coprime to N) together with explicit upper bounds on balance ((d+1)⌊2√q⌋+|t|+d) and correlation ((2d+1)⌊2√q⌋+|t|+2d) and a lower bound on linear complexity.

Significance. If the stated bounds are rigorously justified, the work supplies a parametric family of sequences whose correlation and balance scale with the Hasse-Weil quantity ⌊2√q⌋, thereby enlarging the repertoire of algebraic constructions available for applications in communications and cryptography. The explicit dependence on the group order and the auxiliary parameter d is a concrete strength.

major comments (2)
  1. [Abstract and main theorem] Abstract (and the derivation of the main bounds): the claimed balance and correlation upper bounds are obtained by bounding character sums of the form |∑_P η(f(P))| and |∑_P η(f(P))η(f(P+Q))| where f is a degree-d rational function. Because η is multiplicative, these are Kummer-type sums on the elliptic curve rather than additive trace sums; the manuscript must supply an explicit Weil estimate that accounts for the zeros and poles of f and the cyclic group structure. The numerical constants (d+1) and (2d+1) are not automatic from the standard Hasse bound and require separate justification.
  2. [Construction section] Construction (definition of the sequence family): the map that associates to each element of the cyclic group of rational points a binary value via η must be shown to produce exactly q^{d-1}-1 distinct sequences when d is coprime to q+1+t. The proof that the gcd condition guarantees the required algebraic independence or non-degeneracy is load-bearing for the family size claim.
minor comments (2)
  1. [Linear complexity bound] The linear-complexity lower bound can be algebraically simplified by factoring d out of the denominator; the present expanded form obscures the dependence on ⌊2√q⌋.
  2. [Notation] The floor function ⌊·⌋ is used without an explicit statement that it denotes the greatest integer ≤ x for all real x; this should be added for clarity.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. We address the major comments point by point below, agreeing to incorporate additional justifications and proofs in the revised manuscript.

read point-by-point responses

  1. Referee: [Abstract and main theorem] Abstract (and the derivation of the main bounds): the claimed balance and correlation upper bounds are obtained by bounding character sums of the form |∑_P η(f(P))| and |∑_P η(f(P))η(f(P+Q))| where f is a degree-d rational function. Because η is multiplicative, these are Kummer-type sums on the elliptic curve rather than additive trace sums; the manuscript must supply an explicit Weil estimate that accounts for the zeros and poles of f and the cyclic group structure. The numerical constants (d+1) and (2d+1) are not automatic from the standard Hasse bound and require separate justification.

    Authors: We agree with the referee that an explicit derivation of the character sum bounds is necessary. In the revised manuscript, we will add a dedicated subsection in the main theorem proof that applies Weil's bound for character sums on elliptic curves to the Kummer sums involving the quadratic residue character η. Specifically, we will show that for a degree-d rational function f, the sum |∑_P η(f(P))| is bounded by (d+1)⌊2√q⌋ + |t| + d by counting the contributions from the poles and zeros of f and using the Hasse-Weil estimate adjusted for the curve's point count q+1+t. A similar detailed estimate will be provided for the correlation sums, leading to the factor (2d+1). This will make the origin of the constants transparent. revision: yes

  2. Referee: [Construction section] Construction (definition of the sequence family): the map that associates to each element of the cyclic group of rational points a binary value via η must be shown to produce exactly q^{d-1}-1 distinct sequences when d is coprime to q+1+t. The proof that the gcd condition guarantees the required algebraic independence or non-degeneracy is load-bearing for the family size claim.

    Authors: We concur that the distinctness of the sequences under the condition gcd(d, q+1+t)=1 requires explicit verification. In the updated construction section, we will include a proof that the sequences are distinct by showing that if two different elements in the function field lead to the same sequence, it would imply a linear dependence contradicting the coprimality. This will establish that the family size is indeed q^{d-1}-1. revision: yes

Circularity Check

0 steps flagged

No circularity; algebraic construction with external Hasse-Weil bounds

full rationale

The paper extends an even-characteristic construction to odd characteristic by substituting the quadratic residue map η for the trace map. All stated bounds on balance, correlation, and linear complexity are expressed in terms of the sequence length q+1+t, the parameter d, and the external Hasse bound |t| ≤ 2√q. No equation reduces a claimed prediction to a fitted parameter by construction, no uniqueness theorem is imported from the authors' own prior work, and no ansatz is smuggled via self-citation. The derivation chain remains self-contained against independent algebraic and number-theoretic results.

Axiom & Free-Parameter Ledger

3 free parameters · 2 axioms · 0 invented entities

The construction introduces no new entities but relies on standard elliptic curve theory and the new use of quadratic residue map for sequence definition.

free parameters (3)
  • d
    Positive integer coprime to q+1+t, chosen for the family size.
  • q
    Size of the finite field base.
  • t
    Trace parameter for number of rational points q+1+t.
axioms (2)
  • domain assumption Properties of quadratic residue map on the function field
    Used to define the sequences instead of trace map.
  • standard math Hasse's theorem bounding |t| <= 2 sqrt q
    Used in the bounds implicitly.

pith-pipeline@v0.9.0 · 5530 in / 1529 out tokens · 54948 ms · 2026-05-16T19:52:35.273720+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Binary sequences with gold-like correlation but larger linear span

    S. Boztas and P. V . Kummer, “Binary sequences with gold-like correlation but larger linear span”, IEEE Trans. Inf. Theory, vol. 40,no. 2, pp: 532-537, Mar. 1994

    work page 1994

  2. [2]

    S., Stein, W., Joyner, D., Kohel, D., Cremona, J., Er ¨ocal, B

    Developers, T. S., Stein, W., Joyner, D., Kohel, D., Cremona, J., Er ¨ocal, B. (2020). SageMath, version 9.0. Retrieved from http://www.sagemath.org

    work page 2020

  3. [3]

    New designs for signal sets with low cross correlation, balance property, and large linear span:GF(p)case

    G. Gong, “New designs for signal sets with low cross correlation, balance property, and large linear span:GF(p)case ”, IEEE Trans. Inf. Theory, vol. 48,no. 11, pp: 2847-2867, Feb. 2002

    work page 2002

  4. [4]

    Golomb, Shift Register Sequences

    S. Golomb, Shift Register Sequences. Kolympia, Greece: Aegean Park Press, 1967

    work page 1967

  5. [5]

    A new class of binary sequences with low correlation and large linear complexity from function fields,

    H. Hu, L. Hu and D. Feng, “A new class of binary sequences with low correlation and large linear complexity from function fields,” Proceedings. International Symposium on Information Theory, 2005. ISIT 2005., Adelaide, SA, 2005, pp. 1997-2001

    work page 2005

  6. [6]

    On a class of Pseudorandom sequences from elliptic curves over finite fields,

    H. Hu, L. Hu and D. Feng, “On a class of Pseudorandom sequences from elliptic curves over finite fields,” IEEE Trans. on Inform. Theory, vol. 53,no. 7, pp: 2598-2605, Jul. 2007

    work page 2007

  7. [7]

    Binary sequences with a low correlation via cyclotomic function fields of odd Characteristic,

    X. Hu, L. Jin, L. Ma and C. Xing, “Binary sequences with a low correlation via cyclotomic function fields of odd Characteristic,” IEEE Trans. Inf. Theory, vol. 70, no. 2, pp: 1397-1407, Feb. 2024

    work page 2024

  8. [8]

    Binary sequences with a low correlation via cyclotomic function fields,

    L. Jin, L. Ma and C. Xing, “Binary sequences with a low correlation via cyclotomic function fields,” IEEE Trans. Inf. Theory, vol. 68, no. 5, pp: 3445-3454, May. 2022

    work page 2022

  9. [9]

    A new family of binary sequences with a low correlation via elliptic curves,

    L. Jin, L. Ma, C. Xing and R. Zhu, “A new family of binary sequences with a low correlation via elliptic curves,” IEEE Trans. Inf. Theory, vol. 71, no. 8, pp: 6470-6478, Aug. 2025

    work page 2025

  10. [10]

    Weight distribution formula for some class of cyclic codes

    T. Kasami, “Weight distribution formula for some class of cyclic codes”, Coordinated Sci. Library, Univ. IIIionis-Urbana, Champaign, IL, USA, Tech, Rep. R-285, 1996

    work page 1996

  11. [11]

    Construction of sequences with high nonlinear complexity from function fields,

    Y . Luo, C. Xing and L. You, “Construction of sequences with high nonlinear complexity from function fields,” IEEE Trans. Inf. Theory, vol. 63, no. 12, pp: 7646-7650, Dec. 2017. January 1, 2026 DRAFT 23

    work page 2017

  12. [12]

    The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes,

    L. Ma and C. Xing, “The group structures of automorphism groups of elliptic curves over finite fields and their applications to optimal locally repairable codes,” J. Combinat. Theory A, vol. 193, Jan. 2023, Art. no. 105686

    work page 2023

  13. [13]

    Niederreiter and C

    H. Niederreiter and C. Xing, Rational Points on Curves over Finite Fields: Theory and Applications, LMS 285, Cambridge, 2001

    work page 2001

  14. [14]

    Sequences with high nonlinear complexity,

    H. Niederreiter and C. Xing, “Sequences with high nonlinear complexity,” IEEE Trans. Inf. Theory, vol. 60, no. 10, pp. 6696-6701, Oct. 2014

    work page 2014

  15. [15]

    A note on elliptic curves over finite fields,

    H. Ruck, “A note on elliptic curves over finite fields,” Math. Comput., vol.49, no. 179, pp. 301-304, 1987

    work page 1987

  16. [16]

    Weil sequences: A family of binary sequences with good correlation properties,

    J. Rushanan, “Weil sequences: A family of binary sequences with good correlation properties,” Proc. IEEE Int. Symp. Inf. Theory, pp.1648-1652, Jul. 2006

    work page 2006

  17. [17]

    Stichtenoth, Algebraic Function Fields and Codes, vol

    H. Stichtenoth, Algebraic Function Fields and Codes, vol. 254, 2nd ed. Berlin, Germany: Springer-Verlag, 2009

    work page 2009

  18. [18]

    Generalized binary Udaya-Siddiqi sequences

    X. Tang, P. Udaya, and P. Fan, “Generalized binary Udaya-Siddiqi sequences ”, IEEE Trans. Inf. Theory, vol. 53,no. 3, pp: 1225-1230, Mar. 2007

    work page 2007

  19. [19]

    Two new families of optimal binary sequences obtained from quaternary sequences

    X. Tang, T.Helleseth, L. Hu, and W. Jiang, “Two new families of optimal binary sequences obtained from quaternary sequences ”, IEEE Trans. Inf. Theory, vol. 55,no. 4, pp: 1833-1840, Apr. 2009

    work page 2009

  20. [20]

    Low-correlation, large linear span sequences from function fields

    C. Xing, P. Kumar, and C. Ding, “Low-correlation, large linear span sequences from function fields”, IEEE Trans. Inf. Theory, vol. 49, no. 6, pp: 1439-1446, Jun. 2003

    work page 2003

  21. [21]

    Sequences with almost perfect linear complexity and curves over the finite fields

    C. Xing and K. Lam, “Sequences with almost perfect linear complexity and curves over the finite fields”, IEEE Trans. Inf. Theory, vol. 45, pp: 1267-1270, 1999

    work page 1999

  22. [22]

    Generalized modified gold sequences

    Z. Zhou and X. Tang, “Generalized modified gold sequences”, Des., Codes Cryptogr., vol. 60, no. 3, pp.241-253, Sep. 2011. January 1, 2026 DRAFT

    work page 2011