An Effective Version of the $p$-Curvature Conjecture for Order One Differential Equations

1. Problem Statement

The paper addresses the algebraicity problem for solutions of first-order linear differential equations of the form:
$$y'(x) = u(x)y(x)$$
where $u(x) \in \mathbb{Q}(x)$ is a rational function.

• The Core Question: Given such an equation, does it possess a non-zero algebraic solution?
• Context: While it is known that algebraic functions satisfy linear differential equations (Abel's theorem), the converse is not always true. Deciding if a specific solution is algebraic is a classical problem (dating back to Fuchs and Liouville).
• The p-Curvature Conjecture: Grothendieck's conjecture states that a differential equation has a basis of algebraic solutions if and only if its p-curvature vanishes for almost all prime numbers $p$.
  • Limitation: The conjecture is a "local-global" principle involving infinitely many primes, making it non-algorithmic in its original form.
• Specific Challenge: For first-order equations, Honda (1981) proved the conjecture by reducing it to Kronecker's Theorem (if a polynomial splits modulo almost all primes, it splits over $\mathbb{Q}$). However, Honda's proof was non-constructive regarding which finite set of primes suffices to verify the condition. The authors aim to provide an effective (computable) bound on the number of primes required.

2. Methodology

The authors develop a constructive proof of an effective version of Kronecker's Theorem using Hermite-Padé approximation, following the asymptotic arguments of the Chudnovsky brothers but converting them into explicit bounds.

A. Reduction to Number Theory

For the equation $y' = u(x)y$ with $u(x) = a(x)/b(x)$, the existence of an algebraic solution is equivalent to the Rothstein-Trager resultant $R(w) = \text{res}_x(b(x), a(x) - w \cdot b'(x))$ splitting completely into linear factors over $\mathbb{Q}$.

• The roots of $R(w)$ correspond to the residues of $u(x)$.
• The problem reduces to: If $R(w)$ splits modulo $p$ for a finite set of primes, does it split over $\mathbb{Q}$?

B. Effective Kronecker's Theorem (Theoretical Core)

The authors prove Theorem 1.2, an effective version of Kronecker's Theorem:

• Input: An irreducible polynomial $R(w) \in \mathbb{Z}[w]$ with leading coefficient $r_n$, discriminant $\Delta_R$, and root bound $B$.
• Mechanism: They assume $R(w)$ does not split over $\mathbb{Q}$ (i.e., has an irrational root $\alpha$) but splits modulo all primes $p < \sigma$.
• Contradiction: Using Hermite-Padé approximants for the powers $(1-z)^{i\alpha}$, they construct a specific algebraic integer.
  • They derive an upper bound on the norm of this integer (using Stirling's approximation and properties of the sine function).
  • They derive an upper bound on the denominator of this integer (using $p$-adic valuations and the assumption that $R(w)$ splits modulo small primes).
  • By choosing specific parameters $M$ and $N$ (dependent on $r_n, \Delta_R, B$), they show that the product of the norm and the denominator leads to a contradiction (a non-zero algebraic integer with absolute value $< 1$).
• Result: They explicitly calculate the bound $\sigma$ such that if $R(w)$ splits modulo all primes $p < \sigma$ (excluding those dividing $r_n$), then $R(w)$ must split over $\mathbb{Q}$.

C. Algorithm Design

Based on the theoretical bound, they propose Algorithm 3:

1. Pre-checks: Verify degree conditions and square-free denominators.
2. Early Exit (Transcendence): Compute p-curvatures for small primes (up to the discriminant of the denominator). If any is non-zero, the solution is transcendental.
3. Bound Calculation: Compute the Rothstein-Trager resultant $R(w)$, its discriminant, and the root bound $B$. Calculate the explicit threshold $\sigma$.
4. Verification: Compute p-curvatures for all primes up to $\sigma$. If all vanish, the solution is algebraic.

3. Key Contributions

1. Explicit Bounds: The paper provides the first explicit, computable bound $\sigma$ for the number of primes needed to verify the algebraicity of solutions to first-order differential equations.
   • The bound depends on the height ($H$) and degree ($n$) of the coefficients.
   • Formula: $\sigma \approx (2M+1)N + 2M$, where $M \approx 2.826 \cdot r_n^3 \cdot \delta(\Delta_R)^3$ and $N \approx 6.076 \cdot B \cdot M$.
2. Effective Proof of Honda's Theorem: They make the Chudnovsky brothers' asymptotic proof of Kronecker's Theorem fully effective, deriving concrete constants ($2.826$, $6.076$) rather than just existence.
3. Algorithm Implementation: They implemented the algorithm in SageMath, utilizing fast algorithms (Bostan-Schost) for computing p-curvatures.
4. Complexity Analysis:
   • Theoretical complexity: $\tilde{O}(\Delta_b^6 B) \approx \tilde{O}(H^{12n})$. This is exponential in the degree, which is expected for such problems.
   • Practical behavior: While verifying algebraicity is hard (requires checking up to $\sigma$), verifying transcendence is extremely fast.

4. Results and Performance

• Transcendence Detection: The algorithm is highly efficient at detecting transcendental solutions. In generic cases (random coefficients), the p-curvature is non-zero for very small primes (often $p \le 17$). The algorithm terminates almost instantly in these cases, outperforming methods that require computing the full Rothstein-Trager resultant.
• Algebraicity Verification: Verifying that a solution is algebraic is computationally expensive due to the large bound $\sigma$.
  • Example: For the equation $y' = \frac{1}{x^2-4}y$, the bound $\sigma \approx 10^{11}$. Computing p-curvatures up to this limit is infeasible (estimated > 2 years), even though the solution is obviously algebraic.
• Comparison:
  • Compared to Maple's istranscendental (based on singularity analysis) and Rational Root Finding (factoring the resultant), the p-curvature method is slower for algebraic cases but significantly faster for transcendental cases.
  • The authors note that for "generic" inputs, the p-curvature method is the fastest way to prove transcendence.

5. Significance

• Theoretical Advancement: It bridges the gap between the abstract p-curvature conjecture and practical computation for order-one equations. It confirms that the "local-global" principle can be made effective with a finite, albeit large, set of primes.
• Algorithmic Insight: The paper highlights a dichotomy in computational complexity: proving a function is transcendental is easy (often requires only small primes), while proving it is algebraic is hard (requires checking a massive range of primes).
• Practical Utility: The implementation serves as a powerful semi-algorithm. It is ideal for filtering out transcendental solutions in large datasets of differential equations, which is a common task in symbolic computation and mathematical physics.
• Future Directions: The authors suggest that significant improvements in the "algebraic" case would likely come from new theoretical results (e.g., better bounds on the least prime of non-splitting) rather than algorithmic optimizations, given the current exponential complexity.

In summary, the paper successfully transforms a deep arithmetic conjecture into a concrete, implementable algorithm that excels at identifying non-algebraic solutions, while providing the first explicit bounds for the general case of first-order differential equations.