ECDLP: Combinatorial and Holonomic Research Directions

Overview

This document outlines potential research directions for investigating the Elliptic Curve Discrete Logarithm Problem (ECDLP) inspired by:

• Norman Wildberger's recent work on solving polynomial equations using hyper-Catalan numbers and the Geode series
• Doron Zeilberger's WZ method and the theory of holonomic functions

These directions are genuinely unexplored, representing conceptual bridges rather than established paths.

The Core Tension

The ECDLP lives in a finite algebraic world ($\mathbb{F}_p$), while Wildberger's hyper-Catalan series and the WZ method typically operate with power series, recurrences, and algebraic structures over characteristic zero. The first challenge is finding the right "port of entry" where these worlds meet productively.

However, both Wildberger and Zeilberger share a philosophical commitment to finitary, constructive, algorithmically explicit mathematics—a sensibility that might reveal structure that classical transcendental approaches obscure.

Direction 1: Division Polynomials as the Natural Meeting Point

Background

The division polynomials $\psi_n(x, y)$ encode $n$-torsion on an elliptic curve: the point $P$ satisfies $nP = \mathcal{O}$ if and only if $\psi_n(P) = 0$.

These polynomials satisfy a bilinear recurrence:

$\psi_{m+n} \psi_{m-n} = \psi_{m+1} \psi_{m-1} \psi_n^2 - \psi_{n+1} \psi_{n-1} \psi_m^2$

This structure is reminiscent of recurrences in holonomic function theory, though bilinear rather than linear with polynomial coefficients.

Research Questions

1. Can the WZ machinery be extended to handle bilinear recurrences of this type?
2. Do the coefficients of $\psi_n$ (as polynomials in the curve parameters $a, b$ and coordinates $x, y$) satisfy holonomic recurrences in $n$?
3. If holonomic structure exists, can the WZ method provide closed-form or asymptotic characterizations?
4. Is there a hyper-Catalan-like combinatorial interpretation of these coefficients?

Why This Direction

Division polynomials are already central to the best algorithms for elliptic curves (point counting, computing isogenies). Their explicit recurrence structure may interface naturally with the WZ machinery.

Direction 2: The Scalar Multiplication Map as a Polynomial System

Background

Given a base point $G = (g_x, g_y)$, the coordinates of $nG = (X_n, Y_n)$ are rational functions in $g_x, g_y, a, b$ satisfying recurrence relations derived from doubling and addition formulas.

Wildberger's Geode approach treats polynomial root-finding as a fundamentally algebraic operation, expressing roots as formal power series with hyper-Catalan coefficients.

Research Questions

1. Is there an analogous "explicit algebraic formula" for the inverse operation in ECDLP—expressing $n$ as some algebraic quantity given $Q = nG$?
2. Consider the formal group associated with the elliptic curve. Near the identity, the group law is a formal power series with coefficients rational in $a, b$. The formal logarithm and exponential satisfy differential equations. Could a hyper-Catalan-style analysis of these formal power series reveal structure relevant to discrete logarithms?

Direction 3: Holonomic Analysis of Isogenies

Background

Isogenies between elliptic curves are algebraic maps respecting group structure. The modular polynomial $\Phi_\ell(X, Y)$ relates the $j$-invariants of $\ell$-isogenous curves. Computing isogenies efficiently relates to ECDLP via algorithms like Schoof-Elkies-Atkin.

Modular forms and hypergeometric functions are deeply intertwined, and hypergeometric functions are canonical examples of holonomic functions.

Research Questions

1. Can the holonomic structure of hypergeometric functions associated with elliptic curves (like the periods satisfying Picard-Fuchs equations) be "reduced mod $p$" in a way revealing structure relevant to ECDLP?
2. This connects to Dwork's $p$-adic methods for counting points on varieties. Could a Zeilberger-style algorithmic approach to $p$-adic differential equations yield new insights?

Direction 4: Combinatorial Interpretation of the Group Law

Background

Wildberger's hyper-Catalan numbers count decorated trees (equivalently, lattice paths or decorated non-crossing partitions). The elliptic curve group law involves a cubic—three points on a line.

Research Questions

1. Is there a combinatorial structure (trees, paths, tableaux) whose enumeration is governed by the elliptic curve group law?
2. The addition law defines a trivalent structure (any two points determine a third), analogous to tree structures. Can this analogy be made precise enough for Wildberger-style combinatorial enumeration?
3. If such a combinatorial interpretation exists, does the inverse problem (ECDLP) translate into a combinatorial search problem with different algorithmic properties?

Direction 5: Finite Field Analogues of Power Series Methods

Background

Wildberger's hyper-Catalan series for polynomial roots are formal power series converging to actual roots. Over finite fields, convergence works differently, but we have:

• Teichmüller lifts: lifting elements of $\mathbb{F}_p$ to $p$-adic integers $\mathbb{Z}_p$
• Witt vectors: functorial construction of characteristic-zero rings from characteristic-$p$ data
• Artin-Hasse exponentials and related $p$-adic power series

Research Questions

1. Does a $p$-adic version of the hyper-Catalan series exist?
2. Can such $p$-adic series analyze ECDLP?
3. Since $p$-adic differential equations often have holonomic character, can Zeilberger's approach interface with this structure?

Recommended Starting Point

If prioritizing one direction for initial exploration:

Study the division polynomials $\psi_n$ through the lens of holonomic function theory.

Specific Initial Questions

1. Do the coefficients of $\psi_n$ (as polynomials in curve parameters and coordinates) satisfy holonomic recurrences in $n$?
2. If so, can the WZ method produce "certificates" simplifying analysis of $\psi_n \mod p$?
3. Is there a hyper-Catalan-like combinatorial interpretation of these coefficients?
4. Can combinatorial structure be exploited to factor $\psi_n$ over $\mathbb{F}_p$ more efficiently?

Concrete First Steps

1. Compute the first 20-30 division polynomials explicitly
2. Extract coefficient sequences and test for holonomic recurrences using EKHAD or similar tools
3. Look for combinatorial patterns in coefficient growth
4. Investigate whether any identified structure survives reduction mod $p$

Philosophical Note

Even if this research program doesn't "break" ECDLP, exploring these connections has intrinsic value. Wildberger's methods provide explicit algebraic formulas for quantities that classically required transcendental methods, suggesting hidden algebraic structure may exist elsewhere. Zeilberger's holonomic approach has repeatedly found structure in unexpected places.

The elliptic curve group law is algebraic, combinatorial, and recurrence-governed—it should be amenable to these methods, even if we don't yet see how.

References for Background

• Wildberger, N.J. - Work on hyper-Catalan numbers and the Geode series for polynomial equations
• Zeilberger, D. - The WZ method and holonomic systems
• Silverman, J.H. - The Arithmetic of Elliptic Curves (for division polynomials and formal groups)
• Koblitz, N. - p-adic Numbers, p-adic Analysis, and Zeta-Functions (for p-adic methods)
• Washington, L.C. - Elliptic Curves: Number Theory and Cryptography (for cryptographic context)